source: src/main/java/agents/anac/y2019/agentgp/etc/BidSearch.java

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

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