source: src/main/java/agents/anac/y2015/Atlas3/etc/bidSearch.java@ 1

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

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