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

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

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