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

Last change on this file since 341 was 341, checked in by Katsuhide Fujita, 5 years ago

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