source: src/main/java/agents/anac/y2017/farma/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: 9.8 KB
Line 
1package agents.anac.y2017.farma.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.Value;
12import genius.core.parties.NegotiationInfo;
13
14/**
15 * Created by tatsuya_toyama on 2017/05/08.
16 */
17public class BidSearch {
18 private NegotiationInfo info;
19 private boolean isPrinting = false; // デバッグ用
20 private boolean isPrinting_Search = true;
21
22 private NegoStats negoStats; // 交渉情報
23 private NegoHistory negoHistory;
24 private Bid maxBid = null; // 最大効用値Bid
25
26 public BidSearch(NegotiationInfo info, boolean isPrinting, NegoStats negoStats, NegoHistory negoHistory)
27 throws Exception {
28 this.info = info;
29 this.isPrinting = isPrinting;
30
31 this.negoStats = negoStats;
32 this.negoHistory = negoHistory;
33
34 initMaxBid(); // 最大効用値Bidの初期探索
35 negoStats.setValueRelativeUtility(maxBid); // 相対効用値を導出する
36
37 if (this.isPrinting) {
38 System.out.println("[isPrinting] BidSearch: success");
39 }
40
41 }
42
43 /**
44 * Bidを返す
45 *
46 * @param baseBid
47 * @param threshold
48 * @return
49 */
50 public Bid getBid(Bid baseBid, double threshold) {
51 try {
52 Bid bid = getBidbyAppropriateSearch(baseBid, threshold); // 閾値以上の効用値を持つ合意案候補を探索
53
54 // 探索によって得られたBidがthresholdよりも小さい場合，最大効用値Bidを基準とする
55 if (info.getUtilitySpace().getUtility(bid) < threshold) {
56 bid = new Bid(maxBid);
57 }
58
59 ArrayList<Object> rivals = negoStats.getRivals();
60 Bid tempBid = new Bid(bid);
61 for (int i = 0; i < 100; i++) {
62 for (Object rival : rivals) {
63 tempBid = getReplacedBidByAR(rival, tempBid);
64 }
65
66 if (info.getUtilitySpace().getUtility(bid) >= threshold) {
67 break;
68 }
69 }
70
71 // 探索によって得られたBidがthresholdよりも小さい場合
72 if (info.getUtilitySpace().getUtility(tempBid) < threshold) {
73 return bid;
74 } else {
75 return tempBid;
76 }
77
78 } catch (Exception e) {
79 System.out.println("[Exception_Search] Bidの探索に失敗しました");
80 e.printStackTrace();
81 return baseBid;
82 }
83 }
84
85 // Bidの探索
86 private static int SA_ITERATION = 1;
87
88 /**
89 * Bidの探索
90 *
91 * @param baseBid
92 * @param threshold
93 * @return
94 */
95 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
96 Bid bid = new Bid(baseBid);
97 try {
98 // 線形効用空間用の探索
99 if (negoStats.isLinerUtilitySpace()) {
100 bid = relativeUtilitySearch(threshold);
101
102 // 探索に失敗した場合，非線形効用空間用の探索に切り替える
103 if (info.getUtilitySpace().getUtility(bid) < threshold) {
104 negoStats.utilSpaceTypeisNonLiner();
105 }
106 }
107
108 // 非線形効用空間用の探索
109 if (!negoStats.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 = info.getUtilitySpace().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("[Exception_Search] SA探索に失敗しました");
124 System.out.println(
125 "[Exception_Search] Problem with received bid(SA:last):" + e.getMessage() + ". cancelling bidding");
126 }
127 return bid;
128 }
129
130 /**
131 * 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する)
132 *
133 * @throws Exception
134 */
135 private void initMaxBid() throws Exception {
136 int tryNum = info.getUtilitySpace().getDomain().getIssues().size(); // 試行回数
137
138 Random rnd = new Random(info.getRandomSeed()); // Randomクラスのインスタンス化
139 // maxBid = info.getUtilitySpace().getDomain().getRandomBid(rnd);
140 maxBid = info.getUtilitySpace().getMaxUtilityBid();
141 for (int i = 0; i < tryNum; i++) {
142 try {
143 do {
144 SimulatedAnnealingSearch(maxBid, 1.0);
145 } while (info.getUtilitySpace().getUtility(maxBid) < info.getUtilitySpace().getReservationValue());
146 if (info.getUtilitySpace().getUtility(maxBid) == 1.0) {
147 break;
148 }
149 } catch (Exception e) {
150 System.out.println("[Exception_Search] 最大効用値Bidの初期探索に失敗しました");
151 e.printStackTrace();
152 }
153 }
154
155 System.out
156 .println("[isPrinting_Search]:" + maxBid.toString() + " " + info.getUtilitySpace().getUtility(maxBid));
157 }
158
159 /**
160 * 論点ごとに最適化を行う探索
161 *
162 * @param threshold
163 * @return
164 * @throws Exception
165 */
166 private Bid relativeUtilitySearch(double threshold) throws Exception {
167 Bid bid = new Bid(maxBid);
168 double d = threshold - 1.0; // 最大効用値との差
169 double concessionSum = 0.0; // 減らした効用値の和
170 double relativeUtility = 0.0;
171 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negoStats.getValueRelativeUtility();
172 ArrayList<Issue> randomIssues = (ArrayList<Issue>) negoStats.getIssues();
173 Collections.shuffle(randomIssues);
174 ArrayList<Value> randomValues = null;
175
176 // シャップルされた論点毎に
177 for (Issue issue : randomIssues) {
178 randomValues = negoStats.getValues(issue);
179 Collections.shuffle(randomValues);
180
181 // シャップルされた選択肢毎に
182 for (Value value : randomValues) {
183 relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
184 if (d <= concessionSum + relativeUtility) {
185 bid = bid.putValue(issue.getNumber(), value);
186 concessionSum += relativeUtility;
187 break;
188 }
189 }
190 }
191 return bid;
192 }
193
194 // SA
195 static double START_TEMPERATURE = 1.0; // 開始温度
196 static double END_TEMPERATURE = 0.0001; // 終了温度
197 static double COOL = 0.999; // 冷却度
198 static int STEP = 1;// 変更する幅
199 static int STEP_NUM = 1; // 変更する回数
200
201 /**
202 * SA
203 *
204 * @param baseBid
205 * @param threshold
206 * @return
207 * @throws Exception
208 */
209 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold) throws Exception {
210 Bid currentBid = new Bid(baseBid); // 初期解の生成
211 double currenBidUtil = info.getUtilitySpace().getUtility(baseBid);
212 Bid nextBid = null; // 評価Bid
213 double nextBidUtil = 0.0;
214 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
215 double targetBidUtil = 0.0;
216 double p; // 遷移確率
217 Random randomnr = new Random(); // 乱数
218 double currentTemperature = START_TEMPERATURE; // 現在の温度
219 double newCost = 1.0;
220 double currentCost = 1.0;
221 List<Issue> issues = negoStats.getIssues();
222
223 // 温度が十分下がるまでループ
224 while (currentTemperature > END_TEMPERATURE) {
225 nextBid = new Bid(currentBid); // next_bidを初期化
226
227 // 近傍のBidを取得する
228 for (int i = 0; i < STEP_NUM; i++) {
229 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
230 Issue issue = issues.get(issueIndex); // 指定したindexのissue
231 ArrayList<Value> values = negoStats.getValues(issue);
232 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
233 nextBid = nextBid.putValue(issue.getNumber(), values.get(valueIndex));
234 nextBidUtil = info.getUtilitySpace().getUtility(nextBid);
235
236 // 最大効用値Bidの更新
237 if (maxBid == null || nextBidUtil >= info.getUtilitySpace().getUtility(maxBid)) {
238 maxBid = new Bid(nextBid);
239 }
240 }
241
242 newCost = Math.abs(threshold - nextBidUtil);
243 currentCost = Math.abs(threshold - currenBidUtil);
244 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
245 if (newCost < currentCost || p > randomnr.nextDouble()) {
246 currentBid = new Bid(nextBid); // Bidの更新
247 currenBidUtil = nextBidUtil;
248 }
249
250 // 更新
251 if (currenBidUtil >= threshold) {
252 if (targetBids.size() == 0) {
253 targetBids.add(new Bid(currentBid));
254 targetBidUtil = info.getUtilitySpace().getUtility(currentBid);
255 } else {
256 if (currenBidUtil < targetBidUtil) {
257 targetBids.clear(); // 初期化
258 targetBids.add(new Bid(currentBid)); // 要素を追加
259 targetBidUtil = info.getUtilitySpace().getUtility(currentBid);
260 } else if (currenBidUtil == targetBidUtil) {
261 targetBids.add(new Bid(currentBid)); // 要素を追加
262 }
263 }
264 }
265 currentTemperature = currentTemperature * COOL; // 温度を下げる
266 }
267
268 if (targetBids.size() == 0) {
269 // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
270 return new Bid(baseBid);
271 } else {
272 // 効用値が境界値付近となるBidを返す
273 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
274 }
275 }
276
277 /**
278 * AR (Agree / Reject)
279 *
280 * @param sender
281 * @param bid
282 * @return
283 */
284 Bid getReplacedBidByAR(Object sender, Bid bid) {
285 Random rnd = new Random(info.getRandomSeed()); // Randomクラスのインスタンス化
286
287 List<Issue> issues = negoStats.getIssues();
288 for (Issue issue : issues) {
289 double r = Math.random();
290 HashMap<Value, ArrayList<Double>> cpr = negoStats.getCPRejectedValue(sender, issue);
291
292 // もし累積Reject率における範囲に入った場合は置換
293 if (cpr.get(bid.getValue(issue.getNumber())).get(0) < r
294 && cpr.get(bid.getValue(issue.getNumber())).get(1) >= r) {
295
296 double a = Math.random();
297 HashMap<Value, ArrayList<Double>> cpa = negoStats.getCPAgreedValue(sender, issue);
298
299 // 各valueについて置換先を確率的に決める
300 ArrayList<Value> values = negoStats.getValues(issue);
301 for (Value value : values) {
302 if (cpa.get(value).get(0) < a && cpa.get(value).get(1) >= a) {
303 bid = bid.putValue(issue.getNumber(), value);
304 }
305 break; // １つのvalueに何回も置換しない
306 }
307
308 }
309 }
310
311 return bid;
312 }
313
314}
Note: See TracBrowser for help on using the repository browser.