source: src/main/java/agents/anac/y2018/seto/etc/BidSearch.java@ 343

Last change on this file since 343 was 343, checked in by Tim Baarslag, 4 years ago

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