source: src/main/java/agents/anac/y2015/DrageKnight/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.4 KB
Line 
1package agents.anac.y2015.DrageKnight.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.IssueDiscrete;
12import genius.core.issue.IssueInteger;
13import genius.core.issue.IssueReal;
14import genius.core.issue.Value;
15import genius.core.issue.ValueInteger;
16import genius.core.issue.ValueReal;
17import genius.core.utility.AdditiveUtilitySpace;
18
19public class bidSearch {
20 private AdditiveUtilitySpace utilitySpace;
21 private negotiatingInfo negotiatingInfo; // 交渉情報
22 private Bid maxBid = null; // 最大効用値Bid
23
24 // 探索のパラメータ
25 private static int SA_ITERATION = 1;
26 static double START_TEMPERATURE = 1.0; // 開始温度
27 static double END_TEMPERATURE = 0.0001; // 終了温度
28 static double COOL = 0.999; // 冷却度
29 static int STEP = 1;// 変更する幅
30 static int STEP_NUM = 1; // 変更する回数
31
32 public bidSearch(AdditiveUtilitySpace utilitySpace,
33 negotiatingInfo negotiatingInfo) throws Exception {
34 this.utilitySpace = utilitySpace;
35 this.negotiatingInfo = negotiatingInfo;
36 initMaxBid(); // 最大効用値Bidの初期探索
37 negotiatingInfo.setValueRelativeUtility(maxBid); // 相対効用値を導出する
38 }
39
40 // 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する)
41 private void initMaxBid() throws Exception {
42 int tryNum = utilitySpace.getDomain().getIssues().size(); // 試行回数
43 maxBid = utilitySpace.getDomain().getRandomBid(null);
44 for (int i = 0; i < tryNum; i++) {
45 try {
46 do {
47 SimulatedAnnealingSearch(maxBid, 1.0);
48 } while (utilitySpace.getUtility(maxBid) < utilitySpace
49 .getReservationValue());
50 if (utilitySpace.getUtility(maxBid) == 1.0) {
51 break;
52 }
53 } catch (Exception e) {
54 System.out.println("最大効用値Bidの初期探索に失敗しました");
55 e.printStackTrace();
56 }
57 }
58 }
59
60 // Bidを返す
61 public Bid getBid(Bid baseBid, double threshold) {
62 // Type:Realに対応（暫定版）
63 for (Issue issue : negotiatingInfo.getIssues()) {
64 switch (issue.getType()) {
65 case REAL:
66 try {
67 return (getRandomBid(threshold));
68 } catch (Exception e) {
69 System.out.println("Bidのランダム探索に失敗しました(Real)");
70 e.printStackTrace();
71 }
72 break;
73 default:
74 break;
75 }
76 }
77
78 // Type:Integer and Discrete
79 try {
80 Bid bid = getBidbyAppropriateSearch(baseBid, threshold); // 閾値以上の効用値を持つ合意案候補を探索
81 if (utilitySpace.getUtility(bid) < threshold) {
82 bid = new Bid(maxBid);
83 } // 探索によって得られたBidがthresholdよりも小さい場合，最大効用値Bidを基準とする
84 return bid;
85 } catch (Exception e) {
86 System.out.println("Bidの探索に失敗しました");
87 e.printStackTrace();
88 return baseBid;
89 }
90 }
91
92 // ランダム探索
93 private Bid getRandomBid(double threshold) throws Exception {
94 HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
95 // <issuenumber,chosen
96 // value
97 // string>
98 List<Issue> issues = utilitySpace.getDomain().getIssues();
99 Random randomnr = new Random();
100
101 Bid bid = null;
102 do {
103 for (Issue lIssue : issues) {
104 switch (lIssue.getType()) {
105 case DISCRETE:
106 IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
107 int optionIndex = randomnr.nextInt(lIssueDiscrete
108 .getNumberOfValues());
109 values.put(lIssue.getNumber(),
110 lIssueDiscrete.getValue(optionIndex));
111 break;
112 case REAL:
113 IssueReal lIssueReal = (IssueReal) lIssue;
114 int optionInd = randomnr.nextInt(lIssueReal
115 .getNumberOfDiscretizationSteps() - 1);
116 values.put(
117 lIssueReal.getNumber(),
118 new ValueReal(lIssueReal.getLowerBound()
119 + (lIssueReal.getUpperBound() - lIssueReal
120 .getLowerBound())
121 * (double) (optionInd)
122 / (double) (lIssueReal
123 .getNumberOfDiscretizationSteps())));
124 break;
125 case INTEGER:
126 IssueInteger lIssueInteger = (IssueInteger) lIssue;
127 int optionIndex2 = lIssueInteger.getLowerBound()
128 + randomnr.nextInt(lIssueInteger.getUpperBound()
129 - lIssueInteger.getLowerBound());
130 values.put(lIssueInteger.getNumber(), new ValueInteger(
131 optionIndex2));
132 break;
133 default:
134 throw new Exception("issue type " + lIssue.getType()
135 + " not supported by Atlas3");
136 }
137 }
138 bid = new Bid(utilitySpace.getDomain(), values);
139 } while (utilitySpace.getUtility(bid) < threshold);
140
141 return bid;
142 }
143
144 // Bidの探索
145 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
146 Bid bid = new Bid(baseBid);
147 try {
148 // 線形効用空間用の探索
149 if (negotiatingInfo.isLinerUtilitySpace()) {
150 bid = relativeUtilitySearch(threshold);
151 if (utilitySpace.getUtility(bid) < threshold) {
152 negotiatingInfo.utilitySpaceTypeisNonLiner();
153 } // 探索に失敗した場合，非線形効用空間用の探索に切り替える
154 }
155
156 // 非線形効用空間用の探索
157 if (!negotiatingInfo.isLinerUtilitySpace()) {
158 Bid currentBid = null;
159 double currentBidUtil = 0;
160 double min = 1.0;
161 for (int i = 0; i < SA_ITERATION; i++) {
162 currentBid = SimulatedAnnealingSearch(bid, threshold);
163 currentBidUtil = utilitySpace.getUtility(currentBid);
164 if (currentBidUtil <= min && currentBidUtil >= threshold) {
165 bid = new Bid(currentBid);
166 min = currentBidUtil;
167 }
168 }
169 }
170 } catch (Exception e) {
171 System.out.println("SA探索に失敗しました");
172 System.out.println("Problem with received bid(SA:last):"
173 + e.getMessage() + ". cancelling bidding");
174 }
175 return bid;
176 }
177
178 // 相対効用値に基づく探索
179 private Bid relativeUtilitySearch(double threshold) throws Exception {
180 Bid bid = new Bid(maxBid);
181 double d = threshold - 1.0; // 最大効用値との差
182 double concessionSum = 0.0; // 減らした効用値の和
183 double relativeUtility = 0.0;
184 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiatingInfo
185 .getValueRelativeUtility();
186 List<Issue> randomIssues = negotiatingInfo.getIssues();
187 Collections.shuffle(randomIssues);
188 ArrayList<Value> randomValues = null;
189 for (Issue issue : randomIssues) {
190 randomValues = negotiatingInfo.getValues(issue);
191 Collections.shuffle(randomValues);
192 for (Value value : randomValues) {
193 relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
194 if (d <= concessionSum + relativeUtility) {
195 bid = bid.putValue(issue.getNumber(), value);
196 concessionSum += relativeUtility;
197 break;
198 }
199 }
200 }
201 return bid;
202 }
203
204 // SA
205 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold)
206 throws Exception {
207 Bid currentBid = new Bid(baseBid); // 初期解の生成
208 double currenBidUtil = utilitySpace.getUtility(baseBid);
209 Bid nextBid = null; // 評価Bid
210 double nextBidUtil = 0.0;
211 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
212 double targetBidUtil = 0.0;
213 double p; // 遷移確率
214 Random randomnr = new Random(); // 乱数
215 double currentTemperature = START_TEMPERATURE; // 現在の温度
216 double newCost = 1.0;
217 double currentCost = 1.0;
218 List<Issue> issues = negotiatingInfo.getIssues();
219
220 while (currentTemperature > END_TEMPERATURE) { // 温度が十分下がるまでループ
221 nextBid = new Bid(currentBid); // next_bidを初期化
222 for (int i = 0; i < STEP_NUM; i++) { // 近傍のBidを取得する
223 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
224 Issue issue = issues.get(issueIndex); // 指定したindexのissue
225 ArrayList<Value> values = negotiatingInfo.getValues(issue);
226 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
227 nextBid = nextBid.putValue(issue.getNumber(),
228 values.get(valueIndex));
229 nextBidUtil = utilitySpace.getUtility(nextBid);
230 if (maxBid == null
231 || nextBidUtil >= utilitySpace.getUtility(maxBid)) {
232 maxBid = new Bid(nextBid);
233 } // 最大効用値Bidの更新
234 }
235
236 newCost = Math.abs(threshold - nextBidUtil);
237 currentCost = Math.abs(threshold - currenBidUtil);
238 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
239 if (newCost < currentCost || p > randomnr.nextDouble()) {
240 currentBid = new Bid(nextBid); // Bidの更新
241 currenBidUtil = nextBidUtil;
242 }
243
244 // 更新
245 if (currenBidUtil >= threshold) {
246 if (targetBids.size() == 0) {
247 targetBids.add(new Bid(currentBid));
248 targetBidUtil = utilitySpace.getUtility(currentBid);
249 } else {
250 if (currenBidUtil < targetBidUtil) {
251 targetBids.clear(); // 初期化
252 targetBids.add(new Bid(currentBid)); // 要素を追加
253 targetBidUtil = utilitySpace.getUtility(currentBid);
254 } else if (currenBidUtil == targetBidUtil) {
255 targetBids.add(new Bid(currentBid)); // 要素を追加
256 }
257 }
258 }
259 currentTemperature = currentTemperature * COOL; // 温度を下げる
260 }
261
262 if (targetBids.size() == 0) {
263 return new Bid(baseBid);
264 } // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
265 else {
266 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
267 } // 効用値が境界値付近となるBidを返す
268 }
269}
Note: See TracBrowser for help on using the repository browser.