source: src/main/java/agents/anac/y2017/agentkn/etc/bidSearch.java@ 326

Last change on this file since 326 was 1, checked in by Wouter Pasman, 6 years ago

Initial import : Genius 9.0.0
File size: 11.4 KB
Line 
1package agents.anac.y2017.agentkn.etc;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.Iterator;
7import java.util.List;
8import java.util.Random;
9
10import genius.core.Bid;
11import genius.core.issue.Issue;
12import genius.core.issue.IssueDiscrete;
13import genius.core.issue.IssueInteger;
14import genius.core.issue.IssueReal;
15import genius.core.issue.Value;
16import genius.core.issue.ValueInteger;
17import genius.core.issue.ValueReal;
18import genius.core.utility.AbstractUtilitySpace;
19
20public class bidSearch {
21 private AbstractUtilitySpace utilitySpace;
22 private negotiationInfo negotiationInfo; // 交渉情報
23 private Bid maxBid = null; // 最大効用値Bid
24
25 private boolean isPrinting = false; // デバッグ用
26
27 public bidSearch(AbstractUtilitySpace utilitySpace, negotiationInfo negotiationInfo, boolean isPrinting)
28 throws Exception {
29 this.utilitySpace = utilitySpace;
30 this.negotiationInfo = negotiationInfo;
31 this.isPrinting = isPrinting;
32
33 initMaxBid(); // 最大効用値Bidの初期探索
34 negotiationInfo.setValueRelativeUtility(maxBid); // 相対効用値を導出する
35 }
36
37 /**
38 * 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する)
39 *
40 * @throws Exception
41 */
42 private void initMaxBid() throws Exception {
43 int tryNum = utilitySpace.getDomain().getIssues().size(); // 試行回数
44 maxBid = this.utilitySpace.getDomain().getRandomBid((Random) null);
45
46 for (int i = 0; i < tryNum; i++) {
47 try {
48 do {
49 SimulatedAnnealingSearch(maxBid, 1.0);
50 } while (utilitySpace.getUtility(maxBid) < utilitySpace.getReservationValue());
51 if (utilitySpace.getUtility(maxBid) == 1.0) {
52 break;
53 }
54 } catch (Exception e) {
55 System.out.println("最大効用値Bidの初期探索に失敗しました");
56 e.printStackTrace();
57 }
58 }
59 }
60
61 /**
62 * Bidを返す
63 *
64 * @param baseBid
65 * @param threshold
66 * @return
67 */
68 public Bid getBid(Bid baseBid, double threshold) {
69 Iterator var5 = negotiationInfo.getIssues().iterator();
70
71 System.out.println("AgentKN's Threshold : " + threshold);
72 while (true) {
73 threshold = Math.max(emax(), threshold);
74 System.out.println("search threshold: " + threshold);
75 try {
76 Bid e1 = this.getBidbyAppropriateSearch(baseBid, threshold);
77 // 自分の最大効用知となるものを取得
78 List<Bid> targets = new ArrayList<>();
79 for (int i = 0; i < 10; i++) {
80 Bid e = this.getBidbyAppropriateSearch(getRandomBid(utilitySpace.getUtility(e1)), threshold);
81 System.out.println("search result--------------------------------------");
82 System.out.println("result : " + e);
83 System.out.println("frequency : " + negotiationInfo.getBidFrequcncy(e));
84 System.out.println("searched utility : " + this.utilitySpace.getUtility(e1));
85 System.out.println("---------------------------------------------------");
86 targets.add(e);
87 }
88
89 // 頻度と自分の効用ちでソーと
90 // targets.sort((b1, b2) -> (sortFuncUtility(b1) >
91 // sortFuncUtility(b2)) ? 1 : 0);
92 e1 = targets.get(0);
93
94 if (this.utilitySpace.getUtility(e1) < threshold) {
95 e1 = new Bid(this.maxBid);
96 }
97 return e1;
98 } catch (Exception var7) {
99 System.out.println("Bidの探索に失敗しました");
100 var7.printStackTrace();
101 return baseBid;
102 }
103 }
104 }
105
106 private double sortFuncUtility(Bid aBid) {
107 int frequency = negotiationInfo.getBidFrequcncy(aBid);
108 int k = (int) (Math.log10(frequency) + 1);
109 return utilitySpace.getUtility(aBid) + Math.pow(0.1, k) * frequency;
110 }
111
112 private boolean frequencyCheck(Bid aSearchedBid) {
113 System.out.println("check!!!!!!!!!!!!!!!!!!!!!!!");
114 List issues = this.negotiationInfo.getIssues();
115 ArrayList senders = this.negotiationInfo.getOpponents();
116 Iterator var6 = senders.iterator();
117 int point = 0;
118 while (var6.hasNext()) {
119 Object sender = var6.next();
120 Iterator var8 = issues.iterator();
121 while (var8.hasNext()) {
122 Issue issue = (Issue) var8.next();
123 Value freqValue = this.negotiationInfo.getHighFrequencyValue(sender, issue);
124 if (aSearchedBid.getValues().get(issue).equals(freqValue))
125 point++;
126 }
127 }
128 System.out.println("searched bid frequency point : " + point);
129 return point > issues.size() * 0.6;
130 }
131
132 // Bidの探索
133 private static int SA_ITERATION = 1;
134
135 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
136 Bid bid = new Bid(baseBid);
137 try {
138 // 線形効用空間用の探索
139 if (negotiationInfo.isLinerUtilitySpace()) {
140 bid = relativeUtilitySearch(threshold);
141 if (utilitySpace.getUtility(bid) < threshold) {
142 negotiationInfo.utilitySpaceTypeisNonLiner();
143 } // 探索に失敗した場合，非線形効用空間用の探索に切り替える
144 }
145
146 // 非線形効用空間用の探索
147 if (!negotiationInfo.isLinerUtilitySpace()) {
148 Bid currentBid = null;
149 double currentBidUtil = 0;
150 double min = 1.0;
151 for (int i = 0; i < SA_ITERATION; i++) {
152 currentBid = SimulatedAnnealingSearch(bid, threshold);
153 currentBidUtil = utilitySpace.getUtility(currentBid);
154 System.out.println(currentBidUtil);
155 bid = currentBid;
156 if (currentBidUtil <= min && currentBidUtil >= threshold) { // 効用値は推定値を用いている。
157 bid = new Bid(currentBid);
158 min = currentBidUtil;
159 }
160 }
161 }
162 } catch (Exception e) {
163 System.out.println("SA探索に失敗しました");
164 System.out.println("Problem with received bid(SA:last):" + e.getMessage() + ". cancelling bidding");
165 }
166 return bid;
167 }
168
169 /**
170 * 論点ごとに最適化を行う探索
171 *
172 * @param threshold
173 * @return
174 * @throws Exception
175 */
176
177 private Bid relativeUtilitySearch(double threshold) throws Exception {
178 Bid bid = new Bid(maxBid);
179 double d = threshold - 1.0; // 最大効用値との差
180 double concessionSum = 0.0; // 減らした効用値の和
181 double relativeUtility = 0.0;
182 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiationInfo.getValueRelativeUtility();
183 List<Issue> randomIssues = negotiationInfo.getIssues();
184 Collections.shuffle(randomIssues);
185 ArrayList<Value> randomValues = null;
186 for (Issue issue : randomIssues) {
187 randomValues = negotiationInfo.getValues(issue);
188 Collections.shuffle(randomValues);
189 for (Value value : randomValues) {
190 relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
191 if (d <= concessionSum + relativeUtility) {
192 bid = bid.putValue(issue.getNumber(), value);
193 concessionSum += relativeUtility;
194 break;
195 }
196 }
197 }
198 return bid;
199 }
200
201 // SA
202 static double START_TEMPERATURE = 1.0; // 開始温度
203 static double END_TEMPERATURE = 0.0001; // 終了温度
204 static double COOL = 0.999; // 冷却度
205 static int STEP = 1;// 変更する幅
206 static int STEP_NUM = 1; // 変更する回数
207
208 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold) throws Exception {
209 Bid currentBid = new Bid(baseBid);
210 double currenBidUtil = this.utilitySpace.getUtility(baseBid);
211 Bid nextBid = null;
212 double nextBidUtil = 0.0D;
213 ArrayList targetBids = new ArrayList();
214 double targetBidUtil = 0.0D;
215 Random randomnr = new Random();
216 double currentTemperature = START_TEMPERATURE;
217 double newCost = 1.0D;
218 double currentCost = 1.0D;
219
220 for (List issues = this.negotiationInfo
221 .getIssues(); currentTemperature > END_TEMPERATURE; currentTemperature *= COOL) {
222 nextBid = new Bid(currentBid);
223
224 for (int i = 0; i < STEP_NUM; ++i) {
225 int issueIndex = randomnr.nextInt(issues.size());
226 Issue issue = (Issue) issues.get(issueIndex);
227 ArrayList values = this.negotiationInfo.getValues(issue);
228 int valueIndex = randomnr.nextInt(values.size());
229 nextBid = nextBid.putValue(issue.getNumber(), (Value) values.get(valueIndex));
230 nextBidUtil = this.utilitySpace.getUtility(nextBid);
231 if (this.maxBid == null || nextBidUtil >= this.utilitySpace.getUtility(this.maxBid)) {
232 this.maxBid = new Bid(nextBid);
233 }
234 }
235
236 newCost = Math.abs(threshold - nextBidUtil);
237 currentCost = Math.abs(threshold - currenBidUtil);
238 double p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
239 if (newCost < currentCost || p > randomnr.nextDouble()) {
240 currentBid = new Bid(nextBid);
241 currenBidUtil = nextBidUtil;
242 }
243
244 if (currenBidUtil >= threshold) {
245 if (targetBids.size() == 0) {
246 targetBids.add(new Bid(currentBid));
247 targetBidUtil = this.utilitySpace.getUtility(currentBid);
248 } else if (currenBidUtil < targetBidUtil) {
249 targetBids.clear();
250 targetBids.add(new Bid(currentBid));
251 targetBidUtil = this.utilitySpace.getUtility(currentBid);
252 } else if (currenBidUtil == targetBidUtil) {
253 targetBids.add(new Bid(currentBid));
254 }
255 }
256 }
257
258 if (targetBids.size() == 0) {
259 return new Bid(baseBid);
260 } else {
261 return new Bid((Bid) targetBids.get(randomnr.nextInt(targetBids.size())));
262 }
263 }
264
265 /**
266 * @return a random bid with high enough utility value.
267 * @throws Exception
268 * if we can't compute the utility (eg no evaluators have been
269 * set) or when other evaluators than a DiscreteEvaluator are
270 * present in the util space.
271 */
272 private Bid getRandomBid(double minUtil) throws Exception {
273 HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
274 // <issuenumber,chosen
275 // value
276 // string>
277 List<Issue> issues = utilitySpace.getDomain().getIssues();
278 Random randomnr = new Random();
279
280 // create a random bid with utility>MINIMUM_BID_UTIL.
281 // note that this may never succeed if you set MINIMUM too high!!!
282 // in that case we will search for a bid till the time is up (3 minutes)
283 // but this is just a simple agent.
284 Bid bid = null;
285 do {
286 for (Issue lIssue : issues) {
287 switch (lIssue.getType()) {
288 case DISCRETE:
289 IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
290 int optionIndex = randomnr.nextInt(lIssueDiscrete.getNumberOfValues());
291 values.put(lIssue.getNumber(), lIssueDiscrete.getValue(optionIndex));
292 break;
293 case REAL:
294 IssueReal lIssueReal = (IssueReal) lIssue;
295 int optionInd = randomnr.nextInt(lIssueReal.getNumberOfDiscretizationSteps() - 1);
296 values.put(lIssueReal.getNumber(),
297 new ValueReal(lIssueReal.getLowerBound()
298 + (lIssueReal.getUpperBound() - lIssueReal.getLowerBound()) * (double) (optionInd)
299 / (double) (lIssueReal.getNumberOfDiscretizationSteps())));
300 break;
301 case INTEGER:
302 IssueInteger lIssueInteger = (IssueInteger) lIssue;
303 int optionIndex2 = lIssueInteger.getLowerBound()
304 + randomnr.nextInt(lIssueInteger.getUpperBound() - lIssueInteger.getLowerBound());
305 values.put(lIssueInteger.getNumber(), new ValueInteger(optionIndex2));
306 break;
307 default:
308 throw new Exception("issue type " + lIssue.getType() + " not supported by SimpleAgent2");
309 }
310 }
311 bid = new Bid(utilitySpace.getDomain(), values);
312 } while (utilitySpace.getUtility(bid) < minUtil);
313
314 return bid;
315 }
316
317 private double emax() {
318 double ave = 0.0D;
319 double extra = 0.0D;
320 ArrayList opponents = negotiationInfo.getOpponents();
321
322 double sd = 0.0D;
323 for (Iterator i = opponents.iterator(); i.hasNext(); extra = sd) {
324 Object sender = i.next();
325 if (negotiationInfo.getPartnerBidNum(sender) % 10 == 0) {
326 ave = 0.0D;
327 extra = 0.0D;
328 }
329
330 double m = negotiationInfo.getAverage(sender);
331 sd = negotiationInfo.getStandardDeviation(sender);
332 ave = m;
333 }
334
335 double d = Math.sqrt(3) * sd / Math.sqrt(ave * (1 - ave));
336
337 return ave + (1 - ave) * d;
338 }
339}
Note: See TracBrowser for help on using the repository browser.