source: src/main/java/agents/anac/y2016/atlas3/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.1 KB
Line 
1package agents.anac.y2016.atlas3.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 if (this.isPrinting) {
37 System.out.println("bidSearch:success");
38 }
39 }
40
41 // 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する)
42 private void initMaxBid() throws Exception {
43 int tryNum = utilitySpace.getDomain().getIssues().size(); // 試行回数
44 maxBid = utilitySpace.getDomain().getRandomBid(null);
45 for (int i = 0; i < tryNum; i++) {
46 try {
47 do {
48 SimulatedAnnealingSearch(maxBid, 1.0);
49 } while (utilitySpace.getUtility(maxBid) < utilitySpace
50 .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 // Bidを返す
62 public Bid getBid(Bid baseBid, double threshold) {
63 // Type:Realに対応（暫定版）
64 for (Issue issue : negotiationInfo.getIssues()) {
65 switch (issue.getType()) {
66 case REAL:
67 try {
68 return (getRandomBid(threshold));
69 } catch (Exception e) {
70 System.out.println("Bidのランダム探索に失敗しました(Real)");
71 e.printStackTrace();
72 }
73 break;
74 default:
75 break;
76 }
77 }
78
79 // Type:Integer or Discrete
80 try {
81 Bid bid = getBidbyNeighborhoodSearch(baseBid, threshold); // 近傍探索
82 if (utilitySpace.getUtility(bid) < threshold) {
83 bid = getBidbyAppropriateSearch(baseBid, threshold);
84 } // 閾値以上の効用値を持つ合意案候補を探索
85 if (utilitySpace.getUtility(bid) < threshold) {
86 bid = new Bid(maxBid);
87 } // 探索によって得られたBidがthresholdよりも小さい場合，最大効用値Bidを基準とする
88 bid = getConvertBidbyFrequencyList(bid); // FrequencyListに従ってBidのValueを置換する
89 return bid;
90 } catch (Exception e) {
91 System.out.println("Bidの探索に失敗しました(Integer or Discrete)");
92 e.printStackTrace();
93 return baseBid;
94 }
95 }
96
97 // Bidの探索
98 private static int SA_ITERATION = 1;
99
100 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
101 Bid bid = new Bid(baseBid);
102 try {
103 // 線形効用空間用の探索
104 if (negotiationInfo.isLinerUtilitySpace()) {
105 bid = relativeUtilitySearch(threshold);
106 if (utilitySpace.getUtility(bid) < threshold) {
107 negotiationInfo.utilitySpaceTypeisNonLiner();
108 } // 探索に失敗した場合，非線形効用空間用の探索に切り替える
109 }
110
111 // 非線形効用空間用の探索
112 if (!negotiationInfo.isLinerUtilitySpace()) {
113 Bid currentBid = null;
114 double currentBidUtil = 0;
115 double min = 1.0;
116 for (int i = 0; i < SA_ITERATION; i++) {
117 currentBid = SimulatedAnnealingSearch(bid, threshold);
118 currentBidUtil = utilitySpace.getUtility(currentBid);
119 if (currentBidUtil <= min && currentBidUtil >= threshold) {
120 bid = new Bid(currentBid);
121 min = currentBidUtil;
122 }
123 }
124 }
125 } catch (Exception e) {
126 System.out.println("SA探索に失敗しました");
127 System.out.println("Problem with received bid(SA:last):"
128 + e.getMessage() + ". cancelling bidding");
129 }
130 return bid;
131 }
132
133 // 論点ごとに最適化を行う探索
134 private Bid relativeUtilitySearch(double threshold) throws Exception {
135 Bid bid = new Bid(maxBid);
136 double d = threshold - 1.0; // 最大効用値との差
137 double concessionSum = 0.0; // 減らした効用値の和
138 double relativeUtility = 0.0;
139 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiationInfo
140 .getValueRelativeUtility();
141 List<Issue> randomIssues = negotiationInfo.getIssues();
142 Collections.shuffle(randomIssues);
143 ArrayList<Value> randomValues = null;
144 for (Issue issue : randomIssues) {
145 randomValues = negotiationInfo.getValues(issue);
146 Collections.shuffle(randomValues);
147 for (Value value : randomValues) {
148 relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
149 if (d <= concessionSum + relativeUtility) {
150 bid = bid.putValue(issue.getNumber(), value);
151 concessionSum += relativeUtility;
152 break;
153 }
154 }
155 }
156 return bid;
157 }
158
159 // ランダム探索
160 private Bid getRandomBid(double threshold) throws Exception {
161 HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
162 // <issuenumber,chosen
163 // value
164 // string>
165 List<Issue> issues = utilitySpace.getDomain().getIssues();
166 Random randomnr = new Random();
167
168 Bid bid = null;
169 do {
170 for (Issue lIssue : issues) {
171 switch (lIssue.getType()) {
172 case DISCRETE:
173 IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
174 int optionIndex = randomnr.nextInt(lIssueDiscrete
175 .getNumberOfValues());
176 values.put(lIssue.getNumber(),
177 lIssueDiscrete.getValue(optionIndex));
178 break;
179 case REAL:
180 IssueReal lIssueReal = (IssueReal) lIssue;
181 int optionInd = randomnr.nextInt(lIssueReal
182 .getNumberOfDiscretizationSteps() - 1);
183 values.put(
184 lIssueReal.getNumber(),
185 new ValueReal(lIssueReal.getLowerBound()
186 + (lIssueReal.getUpperBound() - lIssueReal
187 .getLowerBound())
188 * (double) (optionInd)
189 / (double) (lIssueReal
190 .getNumberOfDiscretizationSteps())));
191 break;
192 case INTEGER:
193 IssueInteger lIssueInteger = (IssueInteger) lIssue;
194 int optionIndex2 = lIssueInteger.getLowerBound()
195 + randomnr.nextInt(lIssueInteger.getUpperBound()
196 - lIssueInteger.getLowerBound());
197 values.put(lIssueInteger.getNumber(), new ValueInteger(
198 optionIndex2));
199 break;
200 default:
201 throw new Exception("issue type " + lIssue.getType()
202 + " not supported by Atlas3");
203 }
204 }
205 bid = new Bid(utilitySpace.getDomain(), values);
206 } while (utilitySpace.getUtility(bid) < threshold);
207
208 return bid;
209 }
210
211 // SA
212 static double START_TEMPERATURE = 1.0; // 開始温度
213 static double END_TEMPERATURE = 0.0001; // 終了温度
214 static double COOL = 0.999; // 冷却度
215 static int STEP = 1;// 変更する幅
216 static int STEP_NUM = 1; // 変更する回数
217
218 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold)
219 throws Exception {
220 Bid currentBid = new Bid(baseBid); // 初期解の生成
221 double currenBidUtil = utilitySpace.getUtility(baseBid);
222 Bid nextBid = null; // 評価Bid
223 double nextBidUtil = 0.0;
224 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
225 double targetBidUtil = 0.0;
226 double p; // 遷移確率
227 Random randomnr = new Random(); // 乱数
228 double currentTemperature = START_TEMPERATURE; // 現在の温度
229 double newCost = 1.0;
230 double currentCost = 1.0;
231 List<Issue> issues = negotiationInfo.getIssues();
232
233 while (currentTemperature > END_TEMPERATURE) { // 温度が十分下がるまでループ
234 nextBid = new Bid(currentBid); // next_bidを初期化
235 for (int i = 0; i < STEP_NUM; i++) { // 近傍のBidを取得する
236 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
237 Issue issue = issues.get(issueIndex); // 指定したindexのissue
238 ArrayList<Value> values = negotiationInfo.getValues(issue);
239 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
240 nextBid = nextBid.putValue(issue.getNumber(),
241 values.get(valueIndex));
242 nextBidUtil = utilitySpace.getUtility(nextBid);
243 if (maxBid == null
244 || nextBidUtil >= utilitySpace.getUtility(maxBid)) {
245 maxBid = new Bid(nextBid);
246 } // 最大効用値Bidの更新
247 }
248
249 newCost = Math.abs(threshold - nextBidUtil);
250 currentCost = Math.abs(threshold - currenBidUtil);
251 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
252 if (newCost < currentCost || p > randomnr.nextDouble()) {
253 currentBid = new Bid(nextBid); // Bidの更新
254 currenBidUtil = nextBidUtil;
255 }
256
257 // 更新
258 if (currenBidUtil >= threshold) {
259 if (targetBids.size() == 0) {
260 targetBids.add(new Bid(currentBid));
261 targetBidUtil = utilitySpace.getUtility(currentBid);
262 } else {
263 if (currenBidUtil < targetBidUtil) {
264 targetBids.clear(); // 初期化
265 targetBids.add(new Bid(currentBid)); // 要素を追加
266 targetBidUtil = utilitySpace.getUtility(currentBid);
267 } else if (currenBidUtil == targetBidUtil) {
268 targetBids.add(new Bid(currentBid)); // 要素を追加
269 }
270 }
271 }
272 currentTemperature = currentTemperature * COOL; // 温度を下げる
273 }
274
275 if (targetBids.size() == 0) {
276 return new Bid(baseBid);
277 } // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
278 else {
279 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
280 } // 効用値が境界値付近となるBidを返す
281 }
282
283 // 近傍探索によるBidの探索
284 private static int NEAR_ITERATION = 1;
285
286 private Bid getBidbyNeighborhoodSearch(Bid baseBid, double threshold) {
287 Bid bid = new Bid(baseBid);
288 try {
289 for (int i = 0; i < NEAR_ITERATION; i++) {
290 bid = NeighborhoodSearch(bid, threshold);
291 }
292 } catch (Exception e) {
293 System.out.println("近傍探索に失敗しました");
294 System.out.println("Problem with received bid(Near:last):"
295 + e.getMessage() + ". cancelling bidding");
296 }
297 return bid;
298 }
299
300 // 近傍探索
301 private Bid NeighborhoodSearch(Bid baseBid, double threshold)
302 throws Exception {
303 Bid currentBid = new Bid(baseBid); // 現在のBid
304 double currenBidUtil = utilitySpace.getUtility(baseBid);
305 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
306 double targetBidUtil = 0.0;
307 Random randomnr = new Random(); // 乱数
308 ArrayList<Value> values = null;
309 List<Issue> issues = negotiationInfo.getIssues();
310
311 for (Issue issue : issues) {
312 values = negotiationInfo.getValues(issue);
313 for (Value value : values) {
314 currentBid.putValue(issue.getNumber(), value); // 近傍のBidを求める
315 currenBidUtil = utilitySpace.getUtility(currentBid);
316 if (maxBid == null
317 || currenBidUtil >= utilitySpace.getUtility(maxBid)) {
318 maxBid = new Bid(currentBid);
319 } // 最大効用値Bidの更新
320 // 更新
321 if (currenBidUtil >= threshold) {
322 if (targetBids.size() == 0) {
323 targetBids.add(new Bid(currentBid));
324 targetBidUtil = utilitySpace.getUtility(currentBid);
325 } else {
326 if (currenBidUtil < targetBidUtil) {
327 targetBids.clear(); // 初期化
328 targetBids.add(new Bid(currentBid)); // 要素を追加
329 targetBidUtil = utilitySpace.getUtility(currentBid);
330 } else if (currenBidUtil == targetBidUtil) {
331 targetBids.add(new Bid(currentBid)); // 要素を追加
332 }
333 }
334 }
335 }
336 currentBid = new Bid(baseBid); // base_bidにリセットする
337 }
338
339 if (targetBids.size() == 0) {
340 return new Bid(baseBid);
341 } // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
342 else {
343 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
344 } // 効用値が境界値付近となるBidを返す
345 }
346
347 // 頻度行列に基づきBidを改良する
348 private Bid getConvertBidbyFrequencyList(Bid baseBid) {
349 try {
350 Bid currentBid = new Bid(baseBid);
351 ArrayList<Object> randomOrderOpponents = negotiationInfo
352 .getOpponents();
353 Collections.shuffle(randomOrderOpponents); // ランダムに並び替える(毎回同じ順番で評価した場合，出現数が同値の場合に返却値が偏るため)
354
355 // for(Object sender:randomOrderOpponents){
356 List<Issue> randomOrderIssues = utilitySpace.getDomain()
357 .getIssues();
358 Collections.shuffle(randomOrderIssues); // ランダムに並び替える
359 for (Issue issue : randomOrderIssues) {
360 Bid nextBid = new Bid(currentBid);
361 nextBid = nextBid.putValue(issue.getNumber(),
362 negotiationInfo.getValuebyAllFrequencyList(issue)); // 頻出valueを優先してセットする
363 // nextBid.setValue(issue.getNumber(),
364 // negotiationInfo.getValuebyFrequencyList(sender, issue)); //
365 // 頻出valueを優先してセットする
366 if (utilitySpace.getUtility(nextBid) >= utilitySpace
367 .getUtility(currentBid)) {
368 currentBid = new Bid(nextBid);
369 }
370 }
371 // }
372 return currentBid;
373 } catch (Exception e) {
374 System.out.println("頻度行列に基づくBidの改良に失敗しました");
375 e.printStackTrace();
376 return baseBid;
377 }
378 }
379
380 // Bidにおける重要論点一覧を返す
381 public ArrayList<Issue> criticalIssue(Bid baseBid) throws Exception {
382 Bid currentBid = new Bid(baseBid); // 現在のBid
383 ArrayList<Issue> criticalIssues = new ArrayList<Issue>(); // Bidにおける重要論点一覧
384 ArrayList<Value> values = null;
385 List<Issue> issues = negotiationInfo.getIssues();
386
387 for (Issue issue : issues) {
388 values = negotiationInfo.getValues(issue);
389 for (Value value : values) {
390 currentBid = currentBid.putValue(issue.getNumber(), value); // 近傍のBidを求める
391 if (utilitySpace.getUtility(currentBid) != utilitySpace
392 .getUtility(baseBid)) {
393 criticalIssues.add(issue);
394 break;
395 }
396 }
397 // baseBidにリセットする
398 currentBid = new Bid(baseBid);
399 }
400 return criticalIssues;
401 }
402}
Note: See TracBrowser for help on using the repository browser.