source: src/main/java/agents/anac/y2015/SENGOKU/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: 12.7 KB
Line 
1package agents.anac.y2015.SENGOKU.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 private ArrayList<Bid> MyBidHistory = new ArrayList<Bid>();; // 提案履歴 自分！
24
25 // デバッグ用
26 public static boolean isPrinting = false; // メッセージを表示する
27
28 // 探索のパラメータ
29 private static int SA_ITERATION = 1;
30 static double START_TEMPERATURE = 1.0; // 開始温度
31 static double END_TEMPERATURE = 0.0001; // 終了温度
32 static double COOL = 0.999; // 冷却度
33 static int STEP = 1;// 変更する幅
34 static int STEP_NUM = 1; // 変更する回数
35
36 public bidSearch(AdditiveUtilitySpace utilitySpace,
37 negotiatingInfo negotiatingInfo) throws Exception {
38 this.utilitySpace = utilitySpace;
39 this.negotiatingInfo = negotiatingInfo;
40 initMaxBid(); // 最大効用値Bidの初期探索
41 negotiatingInfo.setValueRelativeUtility(maxBid); // 相対効用値を導出する
42 }
43
44 // 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する)
45 private void initMaxBid() throws Exception {
46 int tryNum = utilitySpace.getDomain().getIssues().size(); // 試行回数
47 maxBid = utilitySpace.getDomain().getRandomBid(null);
48 for (int i = 0; i < tryNum; i++) {
49 try {
50 do {
51 SimulatedAnnealingSearch(maxBid, 1.0);
52 } while (utilitySpace.getUtility(maxBid) < utilitySpace
53 .getReservationValue());
54 if (utilitySpace.getUtility(maxBid) == 1.0) {
55 break;
56 }
57 } catch (Exception e) {
58 System.out.println("最大効用値Bidの初期探索に失敗しました");
59 e.printStackTrace();
60 }
61 }
62 }
63
64 // 新しい探索　相手の提案をいじり閾値以上を探す
65 public Bid shiftBidSerch(Bid baseBid, double threshold) {
66 if (threshold > 0.99) {
67 return getBid(baseBid, threshold);
68 }
69
70 int backNum = 40; // どれだけ以前の履歴までさかのぼってみるのか
71 if (negotiatingInfo.getMyBidHistory().size() < backNum + 10) {
72 backNum = negotiatingInfo.getMyBidHistory().size();
73 }
74
75 ArrayList<Object> opponents = negotiatingInfo.getOpponents(); // 相手のリスト
76 int playerNum = opponents.size(); // プレイヤーの人数
77
78 // ハッシュマップの初期化
79 HashMap<Object, ArrayList<Bid>> opponentsBidHistory = new HashMap<Object, ArrayList<Bid>>();
80 opponentsBidHistory.put(opponents, new ArrayList<Bid>());
81
82 for (Object sender : opponents) {
83 ArrayList<Bid> bidHistry = negotiatingInfo.getPartnerBid(sender);
84 opponentsBidHistory.put(sender, bidHistry);
85 }
86
87 for (int i = 0; i < backNum; i++) {
88 for (int t = 0; t < playerNum; t++) {
89 ArrayList<Bid> bidHistry = opponentsBidHistory.get(opponents
90 .get(t));
91 int n = bidHistry.size();
92 // System.out.println(bidHistry);
93 if (i + 1 > n) {
94 return getBid(baseBid, threshold);
95 }
96 Bid bid = bidHistry.get(n - 1 - i);
97 ArrayList<Bid> bidArray = shiftBidArray(bid);
98 // System.out.println("置換したビッドのひすとり"+bidArray);
99 for (Bid currentbid : bidArray) {
100 // System.out.println("変換ビットの日tぽつこれから値チェック"+currentbid);
101 double util = 0.0;
102 try {
103 util = utilitySpace.getUtility(currentbid);
104 } catch (Exception e) {
105 // TODO Auto-generated catch block
106 e.printStackTrace();
107 }
108 if (isPrinting) {
109 System.out.println("置換中:" + util + "目標閾値:" + threshold);
110 }
111 if (util > threshold) {
112 for (Bid mybid : MyBidHistory) {// 今までのここで使って提案と同じのだったらオファーしない
113 if (currentbid.equals(mybid)) {
114 // System.out.println(MyBidHistory.indexOf(currentbid));
115 MyBidHistory.remove(MyBidHistory
116 .indexOf(currentbid));
117 if (isPrinting) {
118 System.out
119 .println("同じのでてきたーーーーーーーーーーーーーーーー");
120 }
121 return getBid(baseBid, threshold);
122 }
123 }
124
125 // 今までのオファーで同じのはない
126 if (isPrinting) {
127 System.out.println("置換したビットをオファーする");
128 }
129 MyBidHistory.add(currentbid);
130 return currentbid;
131 }
132 }
133 }
134 }
135
136 return getBid(baseBid, threshold);
137 }
138
139 // ビッドの値を一つ変えたすべてのビッドリストをすべて返す
140 private ArrayList<Bid> shiftBidArray(Bid baseBid) {
141 ArrayList<Bid> bidArray = new ArrayList<Bid>();
142 List<Issue> issues = negotiatingInfo.getIssues();
143 ArrayList<Value> values = null;
144 for (Issue issue : issues) {
145 values = negotiatingInfo.getValues(issue);
146 Bid currentBid = new Bid(baseBid);
147 for (Value value : values) {
148 currentBid = currentBid.putValue(issue.getNumber(), value);
149 // System.out.println("変換中ビット"+currentBid);
150 bidArray.add(currentBid);
151 }
152 }
153 return bidArray;
154 }
155
156 // Bidを返す
157 public Bid getBid(Bid baseBid, double threshold) {
158 // Type:Realに対応（暫定版）
159 for (Issue issue : negotiatingInfo.getIssues()) {
160 switch (issue.getType()) {
161 case REAL:
162 try {
163 return (getRandomBid(threshold));
164 } catch (Exception e) {
165 System.out.println("Bidのランダム探索に失敗しました(Real)");
166 e.printStackTrace();
167 }
168 break;
169 default:
170 break;
171 }
172 }
173
174 // Type:Integer and Discrete
175 try {
176 Bid bid = getBidbyAppropriateSearch(baseBid, threshold); // 閾値以上の効用値を持つ合意案候補を探索
177 if (utilitySpace.getUtility(bid) < threshold) {
178 bid = new Bid(maxBid);
179 } // 探索によって得られたBidがthresholdよりも小さい場合，最大効用値Bidを基準とする
180 return bid;
181 } catch (Exception e) {
182 System.out.println("Bidの探索に失敗しました");
183 e.printStackTrace();
184 return baseBid;
185 }
186 }
187
188 // ランダム探索
189 private Bid getRandomBid(double threshold) throws Exception {
190 HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
191 // <issuenumber,chosen
192 // value
193 // string>
194 List<Issue> issues = utilitySpace.getDomain().getIssues();
195 Random randomnr = new Random();
196
197 Bid bid = null;
198 do {
199 for (Issue lIssue : issues) {
200 switch (lIssue.getType()) {
201 case DISCRETE:
202 IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
203 int optionIndex = randomnr.nextInt(lIssueDiscrete
204 .getNumberOfValues());
205 values.put(lIssue.getNumber(),
206 lIssueDiscrete.getValue(optionIndex));
207 break;
208 case REAL:
209 IssueReal lIssueReal = (IssueReal) lIssue;
210 int optionInd = randomnr.nextInt(lIssueReal
211 .getNumberOfDiscretizationSteps() - 1);
212 values.put(
213 lIssueReal.getNumber(),
214 new ValueReal(lIssueReal.getLowerBound()
215 + (lIssueReal.getUpperBound() - lIssueReal
216 .getLowerBound())
217 * (double) (optionInd)
218 / (double) (lIssueReal
219 .getNumberOfDiscretizationSteps())));
220 break;
221 case INTEGER:
222 IssueInteger lIssueInteger = (IssueInteger) lIssue;
223 int optionIndex2 = lIssueInteger.getLowerBound()
224 + randomnr.nextInt(lIssueInteger.getUpperBound()
225 - lIssueInteger.getLowerBound());
226 values.put(lIssueInteger.getNumber(), new ValueInteger(
227 optionIndex2));
228 break;
229 default:
230 throw new Exception("issue type " + lIssue.getType()
231 + " not supported by Atlas3");
232 }
233 }
234 bid = new Bid(utilitySpace.getDomain(), values);
235 } while (utilitySpace.getUtility(bid) < threshold);
236
237 return bid;
238 }
239
240 // Bidの探索
241 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
242 Bid bid = new Bid(baseBid);
243 try {
244 // 線形効用空間用の探索
245 if (negotiatingInfo.isLinerUtilitySpace()) {
246 bid = relativeUtilitySearch(threshold);
247 if (utilitySpace.getUtility(bid) < threshold) {
248 negotiatingInfo.utilitySpaceTypeisNonLiner();
249 } // 探索に失敗した場合，非線形効用空間用の探索に切り替える
250 }
251
252 // 非線形効用空間用の探索
253 if (!negotiatingInfo.isLinerUtilitySpace()) {
254 Bid currentBid = null;
255 double currentBidUtil = 0;
256 double min = 1.0;
257 for (int i = 0; i < SA_ITERATION; i++) {
258 currentBid = SimulatedAnnealingSearch(bid, threshold);
259 currentBidUtil = utilitySpace.getUtility(currentBid);
260 if (currentBidUtil <= min && currentBidUtil >= threshold) {
261 bid = new Bid(currentBid);
262 min = currentBidUtil;
263 }
264 }
265 }
266 } catch (Exception e) {
267 System.out.println("SA探索に失敗しました");
268 System.out.println("Problem with received bid(SA:last):"
269 + e.getMessage() + ". cancelling bidding");
270 }
271 return bid;
272 }
273
274 // 相対効用値に基づく探索
275 private Bid relativeUtilitySearch(double threshold) throws Exception {
276 Bid bid = new Bid(maxBid);
277 double d = threshold - 1.0; // 最大効用値との差
278 double concessionSum = 0.0; // 減らした効用値の和
279 double relativeUtility = 0.0;
280 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiatingInfo
281 .getValueRelativeUtility();
282 List<Issue> randomIssues = negotiatingInfo.getIssues();
283 Collections.shuffle(randomIssues);
284 ArrayList<Value> randomValues = null;
285 for (Issue issue : randomIssues) {
286 randomValues = negotiatingInfo.getValues(issue);
287 Collections.shuffle(randomValues);
288 for (Value value : randomValues) {
289 relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
290 if (d <= concessionSum + relativeUtility) {
291 bid = bid.putValue(issue.getNumber(), value);
292 concessionSum += relativeUtility;
293 break;
294 }
295 }
296 }
297 return bid;
298 }
299
300 // SA
301 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold)
302 throws Exception {
303 Bid currentBid = new Bid(baseBid); // 初期解の生成
304 double currenBidUtil = utilitySpace.getUtility(baseBid);
305 Bid nextBid = null; // 評価Bid
306 double nextBidUtil = 0.0;
307 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
308 double targetBidUtil = 0.0;
309 double p; // 遷移確率
310 Random randomnr = new Random(); // 乱数
311 double currentTemperature = START_TEMPERATURE; // 現在の温度
312 double newCost = 1.0;
313 double currentCost = 1.0;
314 List<Issue> issues = negotiatingInfo.getIssues();
315
316 while (currentTemperature > END_TEMPERATURE) { // 温度が十分下がるまでループ
317 nextBid = new Bid(currentBid); // next_bidを初期化
318 for (int i = 0; i < STEP_NUM; i++) { // 近傍のBidを取得する
319 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
320 Issue issue = issues.get(issueIndex); // 指定したindexのissue
321 ArrayList<Value> values = negotiatingInfo.getValues(issue);
322 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
323 nextBid = nextBid.putValue(issue.getNumber(),
324 values.get(valueIndex));
325 nextBidUtil = utilitySpace.getUtility(nextBid);
326 if (maxBid == null
327 || nextBidUtil >= utilitySpace.getUtility(maxBid)) {
328 maxBid = new Bid(nextBid);
329 } // 最大効用値Bidの更新
330 }
331
332 newCost = Math.abs(threshold - nextBidUtil);
333 currentCost = Math.abs(threshold - currenBidUtil);
334 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
335 if (newCost < currentCost || p > randomnr.nextDouble()) {
336 currentBid = new Bid(nextBid); // Bidの更新
337 currenBidUtil = nextBidUtil;
338 }
339
340 // 更新
341 if (currenBidUtil >= threshold) {
342 if (targetBids.size() == 0) {
343 targetBids.add(new Bid(currentBid));
344 targetBidUtil = utilitySpace.getUtility(currentBid);
345 } else {
346 if (currenBidUtil < targetBidUtil) {
347 targetBids.clear(); // 初期化
348 targetBids.add(new Bid(currentBid)); // 要素を追加
349 targetBidUtil = utilitySpace.getUtility(currentBid);
350 } else if (currenBidUtil == targetBidUtil) {
351 targetBids.add(new Bid(currentBid)); // 要素を追加
352 }
353 }
354 }
355 currentTemperature = currentTemperature * COOL; // 温度を下げる
356 }
357
358 if (targetBids.size() == 0) {
359 return new Bid(baseBid);
360 } // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
361 else {
362 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
363 } // 効用値が境界値付近となるBidを返す
364 }
365}
Note: See TracBrowser for help on using the repository browser.