source: src/main/java/agents/anac/y2016/myagent/etc/bidSearch.java@ 345

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

Initial import : Genius 9.0.0
File size: 7.1 KB
Line 
1package agents.anac.y2016.myagent.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.Value;
12import genius.core.utility.UtilitySpace;
13
14public class bidSearch {
15 private UtilitySpace utilitySpace;
16 private negotiationInfo negotiationInfo; // 交渉情報
17 private Bid maxBid = null; // 最大効用値Bid
18
19 private boolean isPrinting = false; // デバッグ用
20
21 public bidSearch(UtilitySpace utilitySpace,
22 negotiationInfo negotiationInfo, boolean isPrinting)
23 throws Exception {
24 this.utilitySpace = utilitySpace;
25 this.negotiationInfo = negotiationInfo;
26 this.isPrinting = isPrinting;
27
28 initMaxBid(); // 最大効用値Bidの初期探索
29 negotiationInfo.setValueRelativeUtility(maxBid); // 相対効用値を導出する
30 }
31
32 // 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する)
33 private void initMaxBid() throws Exception {
34 int tryNum = utilitySpace.getDomain().getIssues().size(); // 試行回数
35 maxBid = utilitySpace.getDomain().getRandomBid(null);
36 for (int i = 0; i < tryNum; i++) {
37 try {
38 do {
39 SimulatedAnnealingSearch(maxBid, 1.0);
40 } while (utilitySpace.getUtility(maxBid) < utilitySpace
41 .getReservationValue());
42 if (utilitySpace.getUtility(maxBid) == 1.0) {
43 break;
44 }
45 } catch (Exception e) {
46 System.out.println("最大効用値Bidの初期探索に失敗しました");
47 e.printStackTrace();
48 }
49 }
50 }
51
52 // Bidを返す
53 public Bid getBid(Bid baseBid, double threshold) {
54 try {
55 Bid bid = getBidbyAppropriateSearch(baseBid, threshold); // 閾値以上の効用値を持つ合意案候補を探索
56 if (utilitySpace.getUtility(bid) < threshold) {
57 bid = new Bid(maxBid);
58 } // 探索によって得られたBidがthresholdよりも小さい場合，最大効用値Bidを基準とする
59 return bid;
60 } catch (Exception e) {
61 System.out.println("Bidの探索に失敗しました");
62 e.printStackTrace();
63 return baseBid;
64 }
65 }
66
67 // Bidの探索
68 private static int SA_ITERATION = 1;
69
70 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
71 Bid bid = new Bid(baseBid);
72 try {
73 // 線形効用空間用の探索
74 if (negotiationInfo.isLinerUtilitySpace()) {
75 bid = relativeUtilitySearch(threshold);
76 if (utilitySpace.getUtility(bid) < threshold) {
77 negotiationInfo.utilitySpaceTypeisNonLiner();
78 } // 探索に失敗した場合，非線形効用空間用の探索に切り替える
79 }
80
81 // 非線形効用空間用の探索
82 if (!negotiationInfo.isLinerUtilitySpace()) {
83 Bid currentBid = null;
84 double currentBidUtil = 0;
85 double min = 1.0;
86 for (int i = 0; i < SA_ITERATION; i++) {
87 currentBid = SimulatedAnnealingSearch(bid, threshold);
88 currentBidUtil = utilitySpace.getUtility(currentBid);
89 if (currentBidUtil <= min && currentBidUtil >= threshold) {
90 bid = new Bid(currentBid);
91 min = currentBidUtil;
92 }
93 }
94 }
95 } catch (Exception e) {
96 System.out.println("SA探索に失敗しました");
97 System.out.println("Problem with received bid(SA:last):"
98 + e.getMessage() + ". cancelling bidding");
99 }
100 return bid;
101 }
102
103 // 論点ごとに最適化を行う探索
104 private Bid relativeUtilitySearch(double threshold) throws Exception {
105 Bid bid = new Bid(maxBid);
106 double d = threshold - 1.0; // 最大効用値との差
107 double concessionSum = 0.0; // 減らした効用値の和
108 double relativeUtility = 0.0;
109 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiationInfo
110 .getValueRelativeUtility();
111 List<Issue> randomIssues = negotiationInfo.getIssues();
112 Collections.shuffle(randomIssues);
113 ArrayList<Value> randomValues = null;
114 for (Issue issue : randomIssues) {
115 randomValues = negotiationInfo.getValues(issue);
116 Collections.shuffle(randomValues);
117 for (Value value : randomValues) {
118 relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
119 if (d <= concessionSum + relativeUtility) {
120 bid = bid.putValue(issue.getNumber(), value);
121 concessionSum += relativeUtility;
122 break;
123 }
124 }
125 }
126 return bid;
127 }
128
129 // SA
130 static double START_TEMPERATURE = 1.0; // 開始温度
131 static double END_TEMPERATURE = 0.0001; // 終了温度
132 static double COOL = 0.999; // 冷却度
133 static int STEP = 1;// 変更する幅
134 static int STEP_NUM = 1; // 変更する回数
135
136 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold)
137 throws Exception {
138 Bid currentBid = new Bid(baseBid); // 初期解の生成
139 double currenBidUtil = utilitySpace.getUtility(baseBid);
140 Bid nextBid = null; // 評価Bid
141 double nextBidUtil = 0.0;
142 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
143 double targetBidUtil = 0.0;
144 double p; // 遷移確率
145 Random randomnr = new Random(); // 乱数
146 double currentTemperature = START_TEMPERATURE; // 現在の温度
147 double newCost = 1.0;
148 double currentCost = 1.0;
149 List<Issue> issues = negotiationInfo.getIssues();
150
151 while (currentTemperature > END_TEMPERATURE) { // 温度が十分下がるまでループ
152 nextBid = new Bid(currentBid); // next_bidを初期化
153 for (int i = 0; i < STEP_NUM; i++) { // 近傍のBidを取得する
154 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
155 Issue issue = issues.get(issueIndex); // 指定したindexのissue
156 ArrayList<Value> values = negotiationInfo.getValues(issue);
157 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
158 nextBid = nextBid.putValue(issue.getNumber(),
159 values.get(valueIndex));
160 nextBidUtil = utilitySpace.getUtility(nextBid);
161 if (maxBid == null
162 || nextBidUtil >= utilitySpace.getUtility(maxBid)) {
163 maxBid = new Bid(nextBid);
164 } // 最大効用値Bidの更新
165 }
166
167 newCost = Math.abs(threshold - nextBidUtil);
168 currentCost = Math.abs(threshold - currenBidUtil);
169 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
170 if (newCost < currentCost || p > randomnr.nextDouble()) {
171 currentBid = new Bid(nextBid); // Bidの更新
172 currenBidUtil = nextBidUtil;
173 }
174
175 // 更新
176 if (currenBidUtil >= threshold) {
177 if (targetBids.size() == 0) {
178 targetBids.add(new Bid(currentBid));
179 targetBidUtil = utilitySpace.getUtility(currentBid);
180 } else {
181 if (currenBidUtil < targetBidUtil) {
182 targetBids.clear(); // 初期化
183 targetBids.add(new Bid(currentBid)); // 要素を追加
184 targetBidUtil = utilitySpace.getUtility(currentBid);
185 } else if (currenBidUtil == targetBidUtil) {
186 targetBids.add(new Bid(currentBid)); // 要素を追加
187 }
188 }
189 }
190 currentTemperature = currentTemperature * COOL; // 温度を下げる
191 }
192
193 if (targetBids.size() == 0) {
194 return new Bid(baseBid);
195 } // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
196 else {
197 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
198 } // 効用値が境界値付近となるBidを返す
199 }
200}
Note: See TracBrowser for help on using the repository browser.