source: src/main/java/agents/anac/y2018/agent33/etc/BidSearch.java

Last change on this file was 343, checked in by Tim Baarslag, 4 years ago

Fixed all errors in all 2018 agents
File size: 22.8 KB
Line 
1package agents.anac.y2018.agent33.etc;
2
3import java.util.List;
4
5import java.util.ArrayList;
6import java.util.Collections;
7import java.util.HashMap;
8import java.util.Random;
9
10import genius.core.Bid;
11import genius.core.issue.Issue;
12import genius.core.issue.Value;
13import genius.core.parties.NegotiationInfo;
14
15
16public class BidSearch {
17 private NegotiationInfo info;
18 private boolean isPrinting = false; // デバッグ用
19 private boolean isPrinting_Search = true;
20
21 private NegoStats negoStats; // 交渉情報
22 /**
23 * 2018/5/27
24 * 交渉戦略
25 */
26 private NegoStrategy negoStrategy;
27
28 private NegoHistory negoHistory;
29 private Bid maxBid = null; // 最大効用値Bid
30 /**
31 * 2018/5/20
32 * reject率を拡大するための係数
33 */
34 double pow = 3.0; //各issueの各valueのrejectとagreeの確率を計算する時使う平方数
35 double judgeReject = 0.8; //reject率がこれ以上の場合変換する
36 double judgeAgree = 0.6; //agree率がこれ以上の場合変換する
37
38
39 public BidSearch(NegotiationInfo info, boolean isPrinting, NegoStats negoStats, NegoHistory negoHistory) throws Exception {
40 this.info = info;
41 this.isPrinting = isPrinting;
42
43 this.negoStats = negoStats;
44 this.negoHistory = negoHistory;
45
46 initMaxBid(); // 最大効用値Bidの初期探索
47 negoStats.setValueRelativeUtility(maxBid); // 相対効用値を導出する
48
49 if(this.isPrinting){
50 System.out.println("[isPrinting] BidSearch: success");
51 }
52
53 }
54
55 /**
56 * Bidを返す
57 * @param baseBid
58 * @param threshold
59 * @return
60 */
61 public Bid getBid(Bid baseBid, double threshold) {
62 try {
63
64 double time = info.getTimeline().getTime();
65 double thresholdChange = 0.0;
66 double judgeNum = 0.1;//thresholdとの差分
67 Bid bid = getBidbyAppropriateSearch(baseBid, threshold); // 閾値以上の効用値を持つ合意案候補を探索
68 /**
69 * 2018/5/29
70 * thresholdと比較
71 */
72 for(int i = 0; i < 50; i++) {
73
74 bid = relativeUtilitySearch1(threshold);
75 //System.out.println("線形効用空間:bid " + bid);
76 //System.out.println("線形効用空間　bid value " + info.getUtilitySpace().getUtility(bid));
77 //System.out.println("threshold:" + threshold);
78
79 //if (info.getUtilitySpace().getUtility(bid) >= threshold) {
80 /**
81 * 2018/6/1
82 * thresholdとの差分で判断
83 */
84 if (Math.abs(info.getUtilitySpace().getUtility(bid) - threshold) <= judgeNum) {
85 break;
86 }
87 }
88
89 //}
90 /*
91 // 探索によって得られたBidがthresholdよりも小さい場合，最大効用値Bidを基準とする
92 if (info.getUtilitySpace().getUtility(bid) < threshold) {
93 bid = new Bid(maxBid);
94 }
95 */
96
97 ArrayList<Object> rivals = negoStats.getRivals();
98 Bid tempBid = bid;
99 //System.out.println("tempBid:" + tempBid);
100 //System.out.println("bid utility and threshold:" + info.getUtilitySpace().getUtility(bid) + " and " + threshold);
101
102 /**
103 * 2018/5/31
104 * bid valueがthresholdより小さい場合
105 */
106 //if (info.getUtilitySpace().getUtility(bid) < threshold) {
107 if (Math.abs(info.getUtilitySpace().getUtility(bid) - threshold) > judgeNum) {
108 /**
109 * 2018/6/1
110 * time <= 0.8 && time > 0.4
111 */
112
113 thresholdChange = threshold - info.getUtilitySpace().getUtility(bid);
114 for(int i = 0; i < 50; i++) {
115 //bid = relativeUtilitySearch1(threshold);
116 //bid = relativeUtilitySearch1(negoStrategy.getThreshold(info.getTimeline().getTime()));
117 bid = relativeUtilitySearch1(threshold);
118 //System.out.println("線形効用空間:bid " + bid);
119 //System.out.println("線形効用空間　bid value " + info.getUtilitySpace().getUtility(bid));
120 //System.out.println("thresholdChange:" + (threshold - thresholdChange));
121
122 //if (info.getUtilitySpace().getUtility(bid) >= threshold - thresholdChange) {
123 if (Math.abs(info.getUtilitySpace().getUtility(bid) - threshold) < judgeNum) {
124 break;
125 }
126 }
127
128 }
129 System.out.println("bid utility and thresholdChange:" + info.getUtilitySpace().getUtility(bid) + " and " + (threshold- thresholdChange));
130
131
132 /**
133 * 2018/5/20
134 * bidの中にreject率高いissueのvalueをagree率の方を変更
135 * 2018/5/25
136 * time>0.7の時実行
137 */
138 System.out.println("time:" + time);
139
140 if(time > 0.80) {
141 //if (info.getUtilitySpace().getUtility(bid) < threshold) {
142 if (Math.abs(info.getUtilitySpace().getUtility(bid) - threshold) >= judgeNum) {
143 for(int i = 0; i < 30; i++) {
144 for (Object rival : rivals) {
145 tempBid = getReplacedBidByAR(rival,bid);
146 }
147 //if (info.getUtilitySpace().getUtility(tempBid) >= threshold) {
148 if (Math.abs(info.getUtilitySpace().getUtility(bid) - threshold) < judgeNum) {
149 //System.out.println("bid find!!!!!!!");
150 if(info.getUtilitySpace().getUtility(tempBid) > info.getUtilitySpace().getUtility(bid)) {
151 bid = tempBid;
152 }
153 break;
154 }
155 }
156 }
157 }
158
159 /**
160 * 2018/5/29
161 * thresholdと比較しない
162 */
163 /*
164 if (info.getUtilitySpace().getUtility(bid) < threshold) {
165 bid = new Bid(maxBid);
166 }
167 */
168 return bid;
169
170
171 } catch (Exception e) {
172 System.out.println("[Exception_Search] Bidの探索に失敗しました");
173 e.printStackTrace();
174 return baseBid;
175 }
176 }
177
178 // Bidの探索
179 private static int SA_ITERATION = 1;
180 /**
181 * Bidの探索
182 * @param baseBid
183 * @param threshold
184 * @return
185 */
186 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
187 Bid bid = new Bid(baseBid);
188 try {
189 // 線形効用空間用の探索
190 if(negoStats.isLinerUtilitySpace()){
191 bid = relativeUtilitySearch(threshold);
192 /**
193 * 2018/5/27
194 * 重要issueを除き探索
195 */
196 //System.out.println("線形効用空間でbid探索が始まる");
197 //bid = relativeUtilitySearch1(threshold);
198 //System.out.println("線形効用空間:bid " + bid);
199 //System.out.println("線形効用空間　bid value " + info.getUtilitySpace().getUtility(bid));
200
201 /**
202 * 2018/5/29
203 * thresholdと比較
204 */
205 /*
206 for(int i = 0; i < 50; i++) {
207 //bid = relativeUtilitySearch1(threshold);
208 //bid = relativeUtilitySearch1(negoStrategy.getThreshold(info.getTimeline().getTime()));
209 bid = relativeUtilitySearch1(threshold);
210 System.out.println("線形効用空間:bid " + bid);
211 System.out.println("線形効用空間　bid value " + info.getUtilitySpace().getUtility(bid));
212 System.out.println("threshold:" + threshold);
213
214 if (info.getUtilitySpace().getUtility(bid) >= threshold) {
215 break;
216 }
217 }
218 */
219 // 探索に失敗した場合，非線形効用空間用の探索に切り替える
220 /*
221 if(info.getUtilitySpace().getUtility(bid) < threshold){
222 negoStats.utilSpaceTypeisNonLiner();
223 }
224 */
225 }
226
227
228 // 非線形効用空間用の探索
229 if(!negoStats.isLinerUtilitySpace()){
230 Bid currentBid = null;
231 double currentBidUtil = 0;
232 double min = 1.0;
233 for (int i = 0; i < SA_ITERATION; i++) {
234 currentBid = SimulatedAnnealingSearch(bid, threshold);
235 currentBidUtil = info.getUtilitySpace().getUtility(currentBid);
236 if (currentBidUtil <= min && currentBidUtil >= threshold) {
237 bid = new Bid(currentBid);
238 min = currentBidUtil;
239 }
240 }
241 }
242 } catch (Exception e) {
243 System.out.println("[Exception_Search] SA探索に失敗しました");
244 System.out.println("[Exception_Search] Problem with received bid(SA:last):" + e.getMessage() + ". cancelling bidding");
245 }
246 //System.out.println("get bid:" + bid);
247 return bid;
248 }
249
250
251
252 /**
253 * 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する)
254 * @throws Exception
255 */
256 private void initMaxBid() throws Exception{
257 int tryNum = info.getUtilitySpace().getDomain().getIssues().size(); // 試行回数
258
259 Random rnd = new Random(info.getRandomSeed()); //Randomクラスのインスタンス化
260 //maxBid = info.getUtilitySpace().getDomain().getRandomBid(rnd);
261 maxBid = info.getUtilitySpace().getMaxUtilityBid();
262 for (int i = 0; i < tryNum; i++) {
263 try {
264 do{
265 SimulatedAnnealingSearch(maxBid, 1.0);
266 } while (info.getUtilitySpace().getUtility(maxBid) < info.getUtilitySpace().getReservationValue());
267 if(info.getUtilitySpace().getUtility(maxBid) == 1.0){
268 break;
269 }
270 } catch (Exception e) {
271 System.out.println("[Exception_Search] 最大効用値Bidの初期探索に失敗しました");
272 e.printStackTrace();
273 }
274 }
275
276 System.out.println("[isPrinting_Search]:" + maxBid.toString() + " " + info.getUtilitySpace().getUtility(maxBid));
277 }
278
279 /**
280 * 論点ごとに最適化を行う探索
281 * @param threshold
282 * @return
283 * @throws Exception
284 */
285 private Bid relativeUtilitySearch(double threshold) throws Exception{
286 Bid bid = new Bid(maxBid);
287 double d = threshold - 1.0; // 最大効用値との差
288 double concessionSum = 0.0; // 減らした効用値の和
289 double relativeUtility = 0.0;
290 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negoStats.getValueRelativeUtility();
291 ArrayList<Issue> randomIssues = (ArrayList<Issue>) negoStats.getIssues();
292 Collections.shuffle(randomIssues);
293
294 //ArrayList<Value> randomValues = null;
295 ArrayList<Value> randomValues = new ArrayList<Value>();
296
297 // シャップルされた論点毎に
298 for(Issue issue:randomIssues){
299 randomValues = negoStats.getValues(issue);
300 Collections.shuffle(randomValues);
301
302 // シャップルされた選択肢毎に
303 for(Value value:randomValues){
304 relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
305 if(d <= concessionSum + relativeUtility){
306 bid = bid.putValue(issue.getNumber(), value);
307 concessionSum += relativeUtility;
308 break;
309 }
310 }
311 }
312 return bid;
313 }
314
315 /**
316 * 2018/5/25
317 * 重視issue以外の論点ごとに最適化を行う探索
318 */
319 private Bid relativeUtilitySearch1(double threshold) throws Exception{
320 /*
321 double time = info.getTimeline().getCurrentTime();
322 double threshold = negoStrategy.getThresholdForBidSearch(time);//bid探索のための譲歩関数
323 System.out.println("!!!!!!!!threshold:" + threshold);
324 */
325 Bid bidPrior = new Bid(maxBid);
326 //System.out.println("valuePriorAll:" + negoStats.getValuePriorAll());
327 //重視issueと重視valueをbidPriorに入れる
328 //if(negoStats.getValuePriorAll() != null) {
329 if(!negoStats.getValuePriorAll().isEmpty()) {
330 for(Issue issue: negoStats.getValuePriorAll().keySet()) {
331 //System.out.println("issue:" + issue);
332 //System.out.println("issue.getNumber():" + issue.getNumber());
333 //System.out.println("negoStats.getValuePriorAll().get(issue).size():" + negoStats.getValuePriorAll().get(issue).size());
334 Random rand = new Random();
335 int r = rand.nextInt(11) % (negoStats.getValuePriorAll().get(issue).size());//valuelistからランダムにvalueを選ぶ
336 //System.out.println("r:" + r);
337 //System.out.println("negoStats.getValuePriorAll().get(issue).get(r):" + negoStats.getValuePriorAll().get(issue).get(r));
338 bidPrior = bidPrior.putValue(issue.getNumber(), negoStats.getValuePriorAll().get(issue).get(r));
339 //System.out.println("bidPrior:" + bidPrior);
340 }
341 }
342 double d = threshold - 1.0; // 最大効用値との差
343 double concessionSum = 0.0; // 減らした効用値の和
344 double relativeUtility = 0.0;
345 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negoStats.getValueRelativeUtility();
346 ArrayList<Issue> randomIssues = (ArrayList<Issue>) negoStats.getIssues();
347 Collections.shuffle(randomIssues);
348
349 //ArrayList<Value> randomValues = null;
350 ArrayList<Value> randomValues = new ArrayList<Value>(); //errorを解決する
351 // シャップルされた論点毎に
352 for(Issue issue:randomIssues){
353 //System.out.println("issue:" + issue);
354 randomValues = negoStats.getValues(issue);
355 Collections.shuffle(randomValues);
356
357 //重視issueかどうか確認
358 boolean isPriorIssue = false;
359 //if(negoStats.getValuePriorAll() != null) {
360 if(!negoStats.getValuePriorAll().isEmpty()) {
361 for(Issue issuePrior: negoStats.getValuePriorAll().keySet()) {
362 if(issue == issuePrior) {
363 isPriorIssue = true;
364 }
365 }
366 }
367 // シャップルされた選択肢毎に
368 for(Value value:randomValues){
369 relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
370 //System.out.println("d and concessionSum and relativeUtility:" + d + " and "+ concessionSum + " and " + relativeUtility);
371 /**
372 * 2018/5/29
373 *
374 */
375 if(d <= concessionSum + relativeUtility && !isPriorIssue){//重視issueの場合交換しない
376 //if(!isPriorIssue) {
377 //if(d <= concessionSum + relativeUtility) {
378 bidPrior = bidPrior.putValue(issue.getNumber(), value);
379 concessionSum += relativeUtility;
380 //System.out.println("d and concessionSum and relativeUtility:" + d + " and "+ concessionSum + " and " + relativeUtility);
381 break;
382 }
383 }
384 }
385 //System.out.println("bidPrior:" + bidPrior);
386 return bidPrior;
387
388 }
389
390
391 // SA
392 static double START_TEMPERATURE = 1.0; // 開始温度
393 static double END_TEMPERATURE = 0.0001; // 終了温度
394 static double COOL = 0.999; // 冷却度
395 static int STEP = 1;// 変更する幅
396 static int STEP_NUM = 1; // 変更する回数
397 /**
398 * SA
399 * @param baseBid
400 * @param threshold
401 * @return
402 * @throws Exception
403 */
404 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold) throws Exception {
405 Bid currentBid = new Bid(baseBid); // 初期解の生成
406 double currenBidUtil = info.getUtilitySpace().getUtility(baseBid);
407 Bid nextBid = null; // 評価Bid
408 double nextBidUtil = 0.0;
409 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
410 double targetBidUtil = 0.0;
411 double p; // 遷移確率
412 Random randomnr = new Random(); // 乱数
413 double currentTemperature = START_TEMPERATURE; // 現在の温度
414 double newCost = 1.0;
415 double currentCost = 1.0;
416 List<Issue> issues = negoStats.getIssues();
417
418 // 温度が十分下がるまでループ
419 while (currentTemperature > END_TEMPERATURE) {
420 nextBid = new Bid(currentBid); // next_bidを初期化
421
422 // 近傍のBidを取得する
423 for (int i = 0; i < STEP_NUM; i++) {
424 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
425 Issue issue = issues.get(issueIndex); // 指定したindexのissue
426 ArrayList<Value> values = negoStats.getValues(issue);
427 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
428 nextBid = nextBid.putValue(issue.getNumber(), values.get(valueIndex));
429 nextBidUtil = info.getUtilitySpace().getUtility(nextBid);
430
431 // 最大効用値Bidの更新
432 if (maxBid == null || nextBidUtil >= info.getUtilitySpace().getUtility(maxBid)) {
433 maxBid = new Bid(nextBid);
434 }
435 }
436
437 newCost = Math.abs(threshold - nextBidUtil);
438 currentCost = Math.abs(threshold - currenBidUtil);
439 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
440 if (newCost < currentCost || p > randomnr.nextDouble()) {
441 currentBid = new Bid(nextBid); // Bidの更新
442 currenBidUtil = nextBidUtil;
443 }
444
445 // 更新
446 if (currenBidUtil >= threshold){
447 if(targetBids.size() == 0){
448 targetBids.add(new Bid(currentBid));
449 targetBidUtil = info.getUtilitySpace().getUtility(currentBid);
450 } else{
451 if(currenBidUtil < targetBidUtil){
452 targetBids.clear(); // 初期化
453 targetBids.add(new Bid(currentBid)); // 要素を追加
454 targetBidUtil = info.getUtilitySpace().getUtility(currentBid);
455 } else if (currenBidUtil == targetBidUtil){
456 targetBids.add(new Bid(currentBid)); // 要素を追加
457 }
458 }
459 }
460 currentTemperature = currentTemperature * COOL; // 温度を下げる
461 }
462
463 if (targetBids.size() == 0) {
464 // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
465 return new Bid(baseBid);
466 } else {
467 // 効用値が境界値付近となるBidを返す
468 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
469 }
470 }
471
472 /**
473 * AR (Agree / Reject)
474 * @param sender
475 * @param bid
476 * @return
477 */
478 Bid getReplacedBidByAR(Object sender, Bid bid){
479 Random rnd = new Random(info.getRandomSeed()); //Randomクラスのインスタンス化
480
481 List<Issue> issues = negoStats.getIssues();
482 for(Issue issue : issues) {
483 double r = Math.random();
484 HashMap<Value, ArrayList<Double>> cpr = negoStats.getCPRejectedValue(sender, issue);
485 /**
486 * 2018/5/18
487 */
488 //HashMap<Value, ArrayList<Double>> cpr = negoStats.getCPRejectedValue1(sender, issue, pow);
489
490 // もし累積Reject率における範囲に入った場合は置換
491 if(cpr.get(bid.getValue(issue.getNumber())).get(0) < r
492 && cpr.get(bid.getValue(issue.getNumber())).get(1) >= r){
493 //System.out.println("startpoint:" + cpr.get(bid.getValue(issue.getNumber())).get(0));
494 //System.out.println("endpoint:" + cpr.get(bid.getValue(issue.getNumber())).get(1));
495 //System.out.println("r:" + r);
496 double a = Math.random();
497 HashMap<Value, ArrayList<Double>> cpa = negoStats.getCPAgreedValue(sender, issue);
498 /**
499 * 2018/5/18
500 */
501 //HashMap<Value, ArrayList<Double>> cpa = negoStats.getCPAgreedValue1(sender, issue, pow);
502
503 // 各valueについて置換先を確率的に決める
504 ArrayList<Value> values = negoStats.getValues(issue);
505 for(Value value : values){
506 if (cpa.get(value).get(0) < a && cpa.get(value).get(1) >= a){
507 bid = bid.putValue(issue.getNumber(), value);
508 }
509 break; // １つのvalueに何回も置換しない
510 }
511
512 }
513 }
514
515 return bid;
516 }
517
518 /**
519 * 2018/5/20
520 * AR (Agree / Reject)
521 * @param sender
522 * @param bid
523 * @return
524 */
525 Bid getReplacedBidByAR1(Object sender, Bid bid){
526 Random rnd = new Random(info.getRandomSeed()); //Randomクラスのインスタンス化
527
528 List<Issue> issues = negoStats.getIssues();
529 for(Issue issue : issues) {
530 //double r = Math.random();
531 //HashMap<Value, ArrayList<Double>> cpr = negoStats.getCPRejectedValue(sender, issue);
532 /**
533 * 2018/5/18
534 */
535 HashMap<Value, ArrayList<Double>> cpr = negoStats.getCPRejectedValue1(sender, issue, pow);
536
537 // もし累積Reject率における範囲に入った場合は置換
538
539 if((cpr.get(bid.getValue(issue.getNumber())).get(1) - cpr.get(bid.getValue(issue.getNumber())).get(0)) > judgeReject) {
540 double a = Math.random();
541 //HashMap<Value, ArrayList<Double>> cpa = negoStats.getCPAgreedValue(sender, issue);
542 /**
543 * 2018/5/18
544 */
545 HashMap<Value, ArrayList<Double>> cpa = negoStats.getCPAgreedValue1(sender, issue, pow);
546
547 // 各valueについて置換先を確率的に決める
548 ArrayList<Value> values = negoStats.getValues(issue);
549 for(Value value : values){
550
551 if((cpa.get(value).get(1) - cpa.get(value).get(0)) > judgeAgree) {
552 bid = bid.putValue(issue.getNumber(), value);
553 break; // １つのvalueに何回も置換しない
554 }
555 }
556
557 }
558 }
559
560 return bid;
561 }
562
563}
Note: See TracBrowser for help on using the repository browser.