source: src/main/java/agents/anac/y2016/agentsmith/bidSearch.java@ 345

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

Initial import : Genius 9.0.0
File size: 7.9 KB
Line 
1package agents.anac.y2016.agentsmith;
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,
22 negotiationInfo negotiationInfo, boolean isPrinting)
23 throws Exception {
24 this.utilitySpace = utilitySpace;
25 this.negotiationInfo = negotiationInfo;
26 this.isPrinting = isPrinting;
27
28 initMaxBid(); // 最大効用値Bidの初期探索
29 negotiationInfo.setValueRelativeUtility(maxBid); // 相対効用値を導出する
30 }
31
32 // 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する)
33 private void initMaxBid() throws Exception {
34 int tryNum = utilitySpace.getDomain().getIssues().size(); // 試行回数
35 maxBid = utilitySpace.getDomain().getRandomBid(null);
36 for (int i = 0; i < tryNum; i++) {
37 try {
38 do {
39 SimulatedAnnealingSearch(maxBid, 1.0);
40 } while (utilitySpace.getUtility(maxBid) < utilitySpace
41 .getReservationValue());
42 if (utilitySpace.getUtility(maxBid) == 1.0) {
43 break;
44 }
45 } catch (Exception e) {
46 System.out.println("最大効用値Bidの初期探索に失敗しました");
47 e.printStackTrace();
48 }
49 }
50 }
51
52 // Bidを返す
53 public Bid getBid(Bid baseBid, double threshold) {
54 try {
55
56 // Bid bid = utilitySpace.getDomain().getRandomBid(); // 適当なBidを取得
57 // if (utilitySpace.getUtility(bid) < threshold){
58 Bid bid = getBidbyAppropriateSearch(baseBid, threshold);
59 // }
60 if (utilitySpace.getUtility(bid) < threshold) {
61 bid = new Bid(maxBid);
62 }
63 bid = ImprovementBid(bid); // 頻度行列を用いてBidを改良
64 return bid;
65 } catch (Exception e) {
66 System.out.println("Bidの探索に失敗しました");
67 e.printStackTrace();
68 return baseBid;
69 }
70 }
71
72 // Bidの探索
73 private static int SA_ITERATION = 1;
74
75 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
76 Bid bid = new Bid(baseBid);
77 try {
78 // 線形効用空間用の探索
79 if (negotiationInfo.isLinerUtilitySpace()) {
80 bid = relativeUtilitySearch(threshold);
81 if (utilitySpace.getUtility(bid) < threshold) {
82 negotiationInfo.utilitySpaceTypeisNonLiner();
83 } // 探索に失敗した場合，非線形効用空間用の探索に切り替える
84 }
85
86 // 非線形効用空間用の探索
87 if (!negotiationInfo.isLinerUtilitySpace()) {
88 Bid currentBid = null;
89 double currentBidUtil = 0;
90 double min = 1.0;
91 for (int i = 0; i < SA_ITERATION; i++) {
92 currentBid = SimulatedAnnealingSearch(bid, threshold);
93 currentBidUtil = utilitySpace.getUtility(currentBid);
94 if (currentBidUtil <= min && currentBidUtil >= threshold) {
95 bid = new Bid(currentBid);
96 min = currentBidUtil;
97 }
98 }
99 }
100 } catch (Exception e) {
101 System.out.println("SA探索に失敗しました");
102 System.out.println("Problem with received bid(SA:last):"
103 + e.getMessage() + ". cancelling bidding");
104 }
105 return bid;
106 }
107
108 // 論点ごとに最適化を行う探索
109 private Bid relativeUtilitySearch(double threshold) throws Exception {
110 Bid bid = new Bid(maxBid);
111 double d = threshold - 1.0; // 最大効用値との差
112 double concessionSum = 0.0; // 減らした効用値の和
113 double relativeUtility = 0.0;
114 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiationInfo
115 .getValueRelativeUtility();
116 List<Issue> randomIssues = negotiationInfo.getIssues();
117 Collections.shuffle(randomIssues);
118 ArrayList<Value> randomValues = null;
119 for (Issue issue : randomIssues) {
120 randomValues = negotiationInfo.getValues(issue);
121 Collections.shuffle(randomValues);
122 for (Value value : randomValues) {
123 relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
124 if (d <= concessionSum + relativeUtility) {
125 bid = bid.putValue(issue.getNumber(), value);
126 concessionSum += relativeUtility;
127 break;
128 }
129 }
130 }
131 return bid;
132 }
133
134 // SA
135 static double START_TEMPERATURE = 1.0; // 開始温度
136 static double END_TEMPERATURE = 0.0001; // 終了温度
137 static double COOL = 0.999; // 冷却度
138 static int STEP = 1;// 変更する幅
139 static int STEP_NUM = 1; // 変更する回数
140
141 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold)
142 throws Exception {
143 Bid currentBid = new Bid(baseBid); // 初期解の生成
144 double currenBidUtil = utilitySpace.getUtility(baseBid);
145 Bid nextBid = null; // 評価Bid
146 double nextBidUtil = 0.0;
147 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
148 double targetBidUtil = 0.0;
149 double p; // 遷移確率
150 Random randomnr = new Random(); // 乱数
151 double currentTemperature = START_TEMPERATURE; // 現在の温度
152 double newCost = 1.0;
153 double currentCost = 1.0;
154 List<Issue> issues = negotiationInfo.getIssues();
155
156 while (currentTemperature > END_TEMPERATURE) { // 温度が十分下がるまでループ
157 nextBid = new Bid(currentBid); // next_bidを初期化
158 for (int i = 0; i < STEP_NUM; i++) { // 近傍のBidを取得する
159 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
160 Issue issue = issues.get(issueIndex); // 指定したindexのissue
161 ArrayList<Value> values = negotiationInfo.getValues(issue);
162 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
163 nextBid = nextBid.putValue(issue.getNumber(),
164 values.get(valueIndex));
165 nextBidUtil = utilitySpace.getUtility(nextBid);
166 if (maxBid == null
167 || nextBidUtil >= utilitySpace.getUtility(maxBid)) {
168 maxBid = new Bid(nextBid);
169 } // 最大効用値Bidの更新
170 }
171
172 newCost = Math.abs(threshold - nextBidUtil);
173 currentCost = Math.abs(threshold - currenBidUtil);
174 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
175 if (newCost < currentCost || p > randomnr.nextDouble()) {
176 currentBid = new Bid(nextBid); // Bidの更新
177 currenBidUtil = nextBidUtil;
178 }
179
180 // 更新
181 if (currenBidUtil >= threshold) {
182 if (targetBids.size() == 0) {
183 targetBids.add(new Bid(currentBid));
184 targetBidUtil = utilitySpace.getUtility(currentBid);
185 } else {
186 if (currenBidUtil < targetBidUtil) {
187 targetBids.clear(); // 初期化
188 targetBids.add(new Bid(currentBid)); // 要素を追加
189 targetBidUtil = utilitySpace.getUtility(currentBid);
190 } else if (currenBidUtil == targetBidUtil) {
191 targetBids.add(new Bid(currentBid)); // 要素を追加
192 }
193 }
194 }
195 currentTemperature = currentTemperature * COOL; // 温度を下げる
196 }
197
198 if (targetBids.size() == 0) {
199 return new Bid(baseBid);
200 } // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
201 else {
202 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
203 } // 効用値が境界値付近となるBidを返す
204 }
205
206 // 頻度行列によってBidを改良
207 private Bid ImprovementBid(Bid baseBid) {
208 Bid currentBid = new Bid(baseBid);
209 ArrayList<Object> AllOpponents = negotiationInfo.getOpponents();
210 Collections.shuffle(AllOpponents); // ランダマイズ
211
212 List<Issue> AllIssues = utilitySpace.getDomain().getIssues();
213 Collections.shuffle(AllIssues); // ランダマイズ
214 for (Issue issue : AllIssues) {
215 Bid nextBid = new Bid(currentBid);
216 nextBid.putValue(issue.getNumber(),
217 negotiationInfo.getValuebyAllFrequencyList(issue)); // 頻度の高いものを優先
218 if (utilitySpace.getUtility(nextBid) >= utilitySpace
219 .getUtility(currentBid)) {
220 currentBid = new Bid(nextBid);
221 }
222 }
223 return currentBid;
224 }
225
226}
Note: See TracBrowser for help on using the repository browser.