source: src/main/java/agents/anac/y2017/agentf/etc/bidSearch.java@ 346

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

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