source: src/main/java/agents/anac/y2016/terra/etc/bidSearch.java@ 46

Last change on this file since 46 was 1, checked in by Wouter Pasman, 6 years ago

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