source: src/main/java/agents/anac/y2016/farma/etc/bidSearch.java

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

Initial import : Genius 9.0.0
File size: 14.2 KB
Line 
1package agents.anac.y2016.farma.etc;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.List;
7import java.util.Random;
8
9import genius.core.Bid;
10import genius.core.issue.Issue;
11import genius.core.issue.IssueDiscrete;
12import genius.core.issue.IssueInteger;
13import genius.core.issue.IssueReal;
14import genius.core.issue.Value;
15import genius.core.issue.ValueInteger;
16import genius.core.issue.ValueReal;
17import genius.core.utility.AbstractUtilitySpace;
18
19public class bidSearch {
20 private AbstractUtilitySpace utilitySpace;
21 private negotiationInfo negotiationInfo; // 交渉情報
22 private Bid maxBid = null; // 最大効用値Bid
23
24 private boolean isPrinting = false; // デバッグ用
25
26 public bidSearch(AbstractUtilitySpace utilitySpace,
27 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 // 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する)
38 private void initMaxBid() throws Exception {
39 int tryNum = utilitySpace.getDomain().getIssues().size(); // 試行回数
40 maxBid = utilitySpace.getDomain().getRandomBid(null);
41 for (int i = 0; i < tryNum; i++) {
42 try {
43 do {
44 SimulatedAnnealingSearch(maxBid, 1.0);
45 } while (utilitySpace.getUtility(maxBid) < utilitySpace
46 .getReservationValue());
47
48 if (utilitySpace.getUtility(maxBid) == 1.0) {
49 break;
50 }
51 } catch (Exception e) {
52 System.out.println("最大効用値Bidの初期探索に失敗しました");
53 e.printStackTrace();
54 }
55 }
56 }
57
58 public boolean isOfferMaxBid(int turn, double df) {
59 if (turn <= 3)
60 return true;
61 if (turn % (int) (75 / df) == 0)
62 return true;
63 return false;
64 }
65
66 // Bidを返す
67 public Bid getBid(Bid baseBid, double threshold) {
68 int myTurn = negotiationInfo.getRound();
69 double df = utilitySpace.getDiscountFactor();
70
71 if (myTurn == 1 && negotiationInfo.getValueNum() < 1000) {
72
73 }
74
75 // もし、第1回目のターンの場合、maxBidを返す
76 if (isOfferMaxBid(myTurn, df)) {
77 // System.out.println("Offer Max Bid!!!");
78 return maxBid;
79 }
80
81 try {
82 Bid bid = neighborhoodBidSearch(threshold);
83
84 // 閾値以上の効用値を持つ合意案候補を探索
85 // 適切なbidが見つからなかった場合
86 if (bid == null) {
87 bid = getBidbyAppropriateSearch(baseBid, threshold);
88 ArrayList<Bid> neighborhoodBid = frequencyBidSearch(bid);
89 Bid newBid = priorityShiftBid(neighborhoodBid, threshold);
90 if (newBid != null)
91 bid = newBid;
92 }
93
94 // 探索によって得られたBidがthresholdよりも小さい場合，最大効用値Bidを基準とする
95 if (utilitySpace.getUtility(bid) < threshold) {
96 bid = new Bid(maxBid);
97 }
98
99 System.out.println("Threshold: " + threshold);
100 System.out.println("・MyOffer-> " + bid);
101 return bid;
102 } catch (Exception e) {
103 System.out.println("Bidの探索に失敗しました");
104 e.printStackTrace();
105 return baseBid;
106 }
107 }
108
109 // ランダム探索
110 private Bid getRandomBid(double threshold) throws Exception {
111 // pairs <issuenumber,chosen value string>
112 HashMap<Integer, Value> values = new HashMap<Integer, Value>();
113 List<Issue> issues = utilitySpace.getDomain().getIssues();
114 Random randomnr = new Random();
115
116 Bid bid = null;
117 do {
118 for (Issue lIssue : issues) {
119 switch (lIssue.getType()) {
120 case DISCRETE:
121 IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
122 int optionIndex = randomnr.nextInt(lIssueDiscrete
123 .getNumberOfValues());
124 values.put(lIssue.getNumber(),
125 lIssueDiscrete.getValue(optionIndex));
126 break;
127
128 case REAL:
129 IssueReal lIssueReal = (IssueReal) lIssue;
130 int optionInd = randomnr.nextInt(lIssueReal
131 .getNumberOfDiscretizationSteps() - 1);
132 values.put(
133 lIssueReal.getNumber(),
134 new ValueReal(lIssueReal.getLowerBound()
135 + (lIssueReal.getUpperBound() - lIssueReal
136 .getLowerBound())
137 * (double) (optionInd)
138 / (double) (lIssueReal
139 .getNumberOfDiscretizationSteps())));
140 break;
141
142 case INTEGER:
143 IssueInteger lIssueInteger = (IssueInteger) lIssue;
144 int optionIndex2 = lIssueInteger.getLowerBound()
145 + randomnr.nextInt(lIssueInteger.getUpperBound()
146 - lIssueInteger.getLowerBound());
147 values.put(lIssueInteger.getNumber(), new ValueInteger(
148 optionIndex2));
149 break;
150
151 default:
152 throw new Exception("issue type " + lIssue.getType()
153 + " not supported by Atlas3");
154 }
155 }
156 bid = new Bid(utilitySpace.getDomain(), values);
157 } while (utilitySpace.getUtility(bid) < threshold);
158
159 return bid;
160 }
161
162 // Bidの探索
163 private static int SA_ITERATION = 1;
164
165 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
166 Bid bid = new Bid(baseBid);
167 try {
168 // 線形効用空間用の探索
169 if (negotiationInfo.isLinerUtilitySpace()) {
170 bid = relativeUtilitySearch(threshold);
171
172 // 探索に失敗した場合，非線形効用空間用の探索に切り替える
173 if (utilitySpace.getUtility(bid) < threshold) {
174 negotiationInfo.utilitySpaceTypeisNonLiner();
175 }
176 }
177
178 // 非線形効用空間用の探索
179 if (!negotiationInfo.isLinerUtilitySpace()) {
180 Bid currentBid = null;
181 double currentBidUtil = 0;
182 double min = 1.0;
183
184 for (int i = 0; i < SA_ITERATION; i++) {
185 currentBid = SimulatedAnnealingSearch(bid, threshold);
186 currentBidUtil = utilitySpace.getUtility(currentBid);
187
188 if (currentBidUtil <= min && currentBidUtil >= threshold) {
189 bid = new Bid(currentBid);
190 min = currentBidUtil;
191 }
192 }
193 }
194 } catch (Exception e) {
195 System.out.println("SA探索に失敗しました");
196 System.out.println("Problem with received bid(SA:last):"
197 + e.getMessage() + ". cancelling bidding");
198 }
199 return bid;
200 }
201
202 // 論点ごとに最適化を行う探索
203 private Bid relativeUtilitySearch(double threshold) throws Exception {
204 Bid bid = new Bid(maxBid);
205 double d = threshold - 1.0; // 最大効用値との差
206 double concessionSum = 0.0; // 減らした効用値の和
207 double relativeUtility = 0.0;
208 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiationInfo
209 .getValueRelativeUtility();
210 List<Issue> randomIssues = negotiationInfo.getIssues();
211 Collections.shuffle(randomIssues);
212 ArrayList<Value> randomValues = null;
213
214 for (Issue issue : randomIssues) {
215 randomValues = negotiationInfo.getValues(issue);
216 Collections.shuffle(randomValues);
217
218 for (Value value : randomValues) {
219 // 最大効用値を基準とした相対効用値
220 relativeUtility = valueRelativeUtility.get(issue).get(value);
221
222 if (d <= concessionSum + relativeUtility) {
223 bid = bid.putValue(issue.getNumber(), value);
224 concessionSum += relativeUtility;
225 break;
226 }
227 }
228 }
229 return bid;
230 }
231
232 // SA
233 static double START_TEMPERATURE = 1.0; // 開始温度
234 static double END_TEMPERATURE = 0.0001; // 終了温度
235 static double COOL = 0.999; // 冷却度
236 static int STEP = 1; // 変更する幅
237 static int STEP_NUM = 1; // 変更する回数
238
239 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold)
240 throws Exception {
241 Bid currentBid = new Bid(baseBid); // 初期解の生成
242 double currenBidUtil = utilitySpace.getUtility(baseBid);
243 Bid nextBid = null; // 評価Bid
244 double nextBidUtil = 0.0;
245 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
246 double targetBidUtil = 0.0;
247 double p; // 遷移確率
248 Random randomnr = new Random(); // 乱数
249 double currentTemperature = START_TEMPERATURE; // 現在の温度
250 double newCost = 1.0;
251 double currentCost = 1.0;
252 List<Issue> issues = negotiationInfo.getIssues();
253
254 while (currentTemperature > END_TEMPERATURE) { // 温度が十分下がるまでループ
255 nextBid = new Bid(currentBid); // next_bidを初期化
256
257 for (int i = 0; i < STEP_NUM; i++) { // 近傍のBidを取得する
258 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
259 Issue issue = issues.get(issueIndex); // 指定したindexのissue
260 ArrayList<Value> values = negotiationInfo.getValues(issue);
261 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
262 nextBid = nextBid.putValue(issue.getNumber(),
263 values.get(valueIndex));
264 nextBidUtil = utilitySpace.getUtility(nextBid);
265
266 // 最大効用値Bidの更新
267 if (maxBid == null
268 || nextBidUtil >= utilitySpace.getUtility(maxBid)) {
269 maxBid = new Bid(nextBid);
270 }
271 }
272
273 newCost = Math.abs(threshold - nextBidUtil);
274 currentCost = Math.abs(threshold - currenBidUtil);
275 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
276
277 if (newCost < currentCost || p > randomnr.nextDouble()) {
278 currentBid = new Bid(nextBid); // Bidの更新
279 currenBidUtil = nextBidUtil;
280 }
281
282 // 更新
283 if (currenBidUtil >= threshold) {
284 if (targetBids.size() == 0) {
285 targetBids.add(new Bid(currentBid));
286 targetBidUtil = utilitySpace.getUtility(currentBid);
287 } else {
288 if (currenBidUtil < targetBidUtil) {
289 targetBids.clear(); // 初期化
290 targetBids.add(new Bid(currentBid)); // 要素を追加
291 targetBidUtil = utilitySpace.getUtility(currentBid);
292 } else if (currenBidUtil == targetBidUtil) {
293 targetBids.add(new Bid(currentBid)); // 要素を追加
294 }
295 }
296 }
297 currentTemperature = currentTemperature * COOL; // 温度を下げる
298 }
299
300 // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
301 if (targetBids.size() == 0) {
302 return new Bid(baseBid);
303 } else {
304 // 効用値が境界値付近となるBidを返す
305 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
306 }
307 }
308
309 // new function
310
311 /**
312 * baseBidについて、各issueについて変更したBid列をbidInfoに追加
313 *
314 * @param baseBid
315 * @return
316 */
317 public void shiftBidSearch(Bid baseBid) {
318 List<Issue> issues = negotiationInfo.getIssues();
319
320 for (Issue issue : issues) {
321 ArrayList<Value> values = negotiationInfo.getValues(issue);
322
323 for (Value value : values) {
324 Value targetValue = baseBid.getValue(issue.getNumber());
325
326 // shiftして異なるbidになった場合
327 if (!targetValue.equals(value)) {
328 Bid tempBid = baseBid.putValue(issue.getNumber(), value);
329 double utilityValue = utilitySpace.getUtility(tempBid);
330
331 // 今まで登録していないbidであった場合
332 double rv = utilitySpace.getReservationValue();
333 if (utilityValue >= rv
334 && !negotiationInfo
335 .isNeighborhoodBidContain(tempBid)) {
336 negotiationInfo.updateNeighborhoodBid(tempBid);
337 frequencyBidSearch(tempBid);
338 }
339 }
340 }
341 }
342 // System.out.println("BidInfo NUM: " +
343 // negotiationInfo.getNeighborhoodBidSize());
344 }
345
346 /**
347 * 頻度探索
348 *
349 * @param baseBid
350 */
351 public ArrayList<Bid> frequencyBidSearch(Bid baseBid) {
352 ArrayList<Bid> freqBids = new ArrayList<Bid>();
353
354 List<Issue> issues = negotiationInfo.getIssues();
355 ArrayList<Object> senders = negotiationInfo.getOpponents();
356 for (Object sender : senders) {
357 for (Issue issue : issues) {
358 Value freqValue = negotiationInfo.getHighFrequencyValue(sender,
359 issue);
360 Bid tempBid = baseBid.putValue(issue.getNumber(), freqValue);
361 double utilityValue = utilitySpace.getUtility(tempBid);
362
363 freqBids.add(tempBid);
364
365 // 今まで登録していないbidであった場合
366 double rv = utilitySpace.getReservationValue();
367 if (utilityValue >= rv
368 && !negotiationInfo.isNeighborhoodBidContain(tempBid)) {
369 negotiationInfo.updateNeighborhoodBid(tempBid);
370 }
371 }
372 }
373 return freqBids;
374 }
375
376 /**
377 * bidInfoの探索において、thresholdを超えるものを返す
378 *
379 * @param threshold
380 * @return
381 */
382 public Bid neighborhoodBidSearch(double threshold) {
383 HashMap<Bid, Integer> nextBids = negotiationInfo.getNeighborhoodBid();
384 ArrayList<Bid> overThresholdBids = new ArrayList<Bid>();
385
386 for (Bid nowBid : nextBids.keySet()) {
387 double util = utilitySpace.getUtility(nowBid);
388
389 // thresholdを超えたbidについて
390 if (util >= threshold) {
391 overThresholdBids.add(nowBid);
392 }
393 }
394
395 // 該当するbidが存在しなかった場合、次の探索に移行する
396 if (overThresholdBids.isEmpty()) {
397 return null;
398 }
399 // 該当するbidが存在した場合は、どのbidを提案するか評価する
400 return priorityShiftBid(overThresholdBids, threshold);
401 }
402
403 /**
404 * 優先度の高いbidを返す
405 *
406 * @param bids
407 * @return
408 */
409 public Bid priorityShiftBid(ArrayList<Bid> bids, double threshold) {
410 Bid ansBid = null;
411 Bid subAnsBid = null;
412
413 ArrayList<Object> opponents = negotiationInfo.getOpponents();
414 HashMap<Object, Bid> opponentsFrequencyBids = new HashMap<Object, Bid>();
415 for (Object sender : opponents) {
416 opponentsFrequencyBids.put(sender,
417 negotiationInfo.getHighFrequencyBid(sender, maxBid));
418 }
419
420 double similarityMax = 0.0;
421 double acceptNumMax = 0.0;
422 for (Bid bid : bids) {
423 double MyUtil = utilitySpace.getUtility(bid);
424
425 // まずthreshold近辺であるかどうか
426 if (isNearThreshold(MyUtil, threshold)) {
427
428 // 重み付き類似度の最大Bidを探索
429 double similarity = 0.0;
430 for (Object sender : opponents) {
431 similarity = negotiationInfo.calImportanceRate(sender)
432 * negotiationInfo.cosSimilarity(bid,
433 opponentsFrequencyBids.get(sender));
434 }
435 if (similarity > similarityMax) {
436 similarityMax = similarity;
437 subAnsBid = bid;
438 }
439
440 double acceptNum = negotiationInfo.getAcceptNumByBid(bid, true)
441 + similarity;
442 if (acceptNum > acceptNumMax) {
443 acceptNumMax = acceptNum;
444 ansBid = bid;
445 }
446 }
447 }
448 if (ansBid != null) {
449 return ansBid;
450 } else {
451 return subAnsBid;
452 }
453 }
454
455 private static double EPS = 0.125;
456
457 /**
458 * thresholdとの誤差の許容範囲内かを判別
459 *
460 * @param util
461 * @param threshold
462 * @return
463 */
464 public boolean isNearThreshold(double util, double threshold) {
465 double dist = util - threshold;
466 if (dist >= 0 && dist < EPS) {
467 return true;
468 } else {
469 return false;
470 }
471 }
472
473}
Note: See TracBrowser for help on using the repository browser.