source: src/main/java/agents/anac/y2015/AgentW/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.0 KB
Line 
1package agents.anac.y2015.AgentW;
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 try {
63 Bid bid = getBidbyAppropriateSearch(baseBid, threshold); // 閾値以上の効用値を持つ合意案候補を探索
64 if (utilitySpace.getUtility(bid) < threshold) {
65 bid = new Bid(maxBid);
66 } // 探索によって得られたBidがthresholdよりも小さい場合，最大効用値Bidを基準とする
67 return bid;
68 } catch (Exception e) {
69 System.out.println("Bidの探索に失敗しました");
70 e.printStackTrace();
71 return baseBid;
72 }
73 }
74
75 // ランダム探索
76 private Bid getRandomBid(double threshold) throws Exception {
77 HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
78 // <issuenumber,chosen
79 // value
80 // string>
81 List<Issue> issues = utilitySpace.getDomain().getIssues();
82 Random randomnr = new Random();
83
84 Bid bid = null;
85 do {
86 for (Issue lIssue : issues) {
87 switch (lIssue.getType()) {
88 case DISCRETE:
89 IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
90 int optionIndex = randomnr.nextInt(lIssueDiscrete
91 .getNumberOfValues());
92 values.put(lIssue.getNumber(),
93 lIssueDiscrete.getValue(optionIndex));
94 break;
95 case REAL:
96 IssueReal lIssueReal = (IssueReal) lIssue;
97 int optionInd = randomnr.nextInt(lIssueReal
98 .getNumberOfDiscretizationSteps() - 1);
99 values.put(
100 lIssueReal.getNumber(),
101 new ValueReal(lIssueReal.getLowerBound()
102 + (lIssueReal.getUpperBound() - lIssueReal
103 .getLowerBound())
104 * (double) (optionInd)
105 / (double) (lIssueReal
106 .getNumberOfDiscretizationSteps())));
107 break;
108 case INTEGER:
109 IssueInteger lIssueInteger = (IssueInteger) lIssue;
110 int optionIndex2 = lIssueInteger.getLowerBound()
111 + randomnr.nextInt(lIssueInteger.getUpperBound()
112 - lIssueInteger.getLowerBound());
113 values.put(lIssueInteger.getNumber(), new ValueInteger(
114 optionIndex2));
115 break;
116 default:
117 throw new Exception("issue type " + lIssue.getType()
118 + " not supported by Atlas3");
119 }
120 }
121 bid = new Bid(utilitySpace.getDomain(), values);
122 } while (utilitySpace.getUtility(bid) < threshold);
123
124 return bid;
125 }
126
127 // Bidの探索
128 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
129 Bid bid = new Bid(baseBid);
130 try {
131 // 線形効用空間用の探索
132 if (negotiatingInfo.isLinerUtilitySpace()) {
133 bid = relativeUtilitySearch(threshold);
134 if (utilitySpace.getUtility(bid) < threshold) {
135 negotiatingInfo.utilitySpaceTypeisNonLiner();
136 } // 探索に失敗した場合，非線形効用空間用の探索に切り替える
137 }
138
139 // 非線形効用空間用の探索
140 if (!negotiatingInfo.isLinerUtilitySpace()) {
141 Bid currentBid = null;
142 double currentBidUtil = 0;
143 double min = 1.0;
144 for (int i = 0; i < SA_ITERATION; i++) {
145 currentBid = SimulatedAnnealingSearch(bid, threshold);
146 currentBidUtil = utilitySpace.getUtility(currentBid);
147 if (currentBidUtil <= min && currentBidUtil >= threshold) {
148 bid = new Bid(currentBid);
149 min = currentBidUtil;
150 }
151 }
152 }
153 } catch (Exception e) {
154 System.out.println("SA探索に失敗しました");
155 System.out.println("Problem with received bid(SA:last):"
156 + e.getMessage() + ". cancelling bidding");
157 }
158 return bid;
159 }
160
161 // 相対効用値に基づく探索
162 private Bid relativeUtilitySearch(double threshold) throws Exception {
163 Bid bid = new Bid(maxBid);
164 double d = threshold - 1.0; // 最大効用値との差
165 double concessionSum = 0.0; // 減らした効用値の和
166 double relativeUtility = 0.0;
167 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiatingInfo
168 .getValueRelativeUtility();
169 List<Issue> randomIssues = negotiatingInfo.getIssues();
170 Collections.shuffle(randomIssues);
171 ArrayList<Value> randomValues = null;
172 for (Issue issue : randomIssues) {
173 randomValues = negotiatingInfo.getValues(issue);
174 Collections.shuffle(randomValues);
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 // SA
188 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold)
189 throws Exception {
190 Bid currentBid = new Bid(baseBid); // 初期解の生成
191 double currenBidUtil = utilitySpace.getUtility(baseBid);
192 Bid nextBid = null; // 評価Bid
193 double nextBidUtil = 0.0;
194 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
195 double targetBidUtil = 0.0;
196 double p; // 遷移確率
197 Random randomnr = new Random(); // 乱数
198 double currentTemperature = START_TEMPERATURE; // 現在の温度
199 double newCost = 1.0;
200 double currentCost = 1.0;
201 List<Issue> issues = negotiatingInfo.getIssues();
202
203 while (currentTemperature > END_TEMPERATURE) { // 温度が十分下がるまでループ
204 nextBid = new Bid(currentBid); // next_bidを初期化
205 for (int i = 0; i < STEP_NUM; i++) { // 近傍のBidを取得する
206 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
207 Issue issue = issues.get(issueIndex); // 指定したindexのissue
208 ArrayList<Value> values = negotiatingInfo.getValues(issue);
209 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
210 nextBid = nextBid.putValue(issue.getNumber(),
211 values.get(valueIndex));
212 nextBidUtil = utilitySpace.getUtility(nextBid);
213 if (maxBid == null
214 || nextBidUtil >= utilitySpace.getUtility(maxBid)) {
215 maxBid = new Bid(nextBid);
216 } // 最大効用値Bidの更新
217 }
218
219 newCost = Math.abs(threshold - nextBidUtil);
220 currentCost = Math.abs(threshold - currenBidUtil);
221 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
222 if (newCost < currentCost || p > randomnr.nextDouble()) {
223 currentBid = new Bid(nextBid); // Bidの更新
224 currenBidUtil = nextBidUtil;
225 }
226
227 // 更新
228 if (currenBidUtil >= threshold) {
229 if (targetBids.size() == 0) {
230 targetBids.add(new Bid(currentBid));
231 targetBidUtil = utilitySpace.getUtility(currentBid);
232 } else {
233 if (currenBidUtil < targetBidUtil) {
234 targetBids.clear(); // 初期化
235 targetBids.add(new Bid(currentBid)); // 要素を追加
236 targetBidUtil = utilitySpace.getUtility(currentBid);
237 } else if (currenBidUtil == targetBidUtil) {
238 targetBids.add(new Bid(currentBid)); // 要素を追加
239 }
240 }
241 }
242 currentTemperature = currentTemperature * COOL; // 温度を下げる
243 }
244
245 if (targetBids.size() == 0) {
246 return new Bid(baseBid);
247 } // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
248 else {
249 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
250 } // 効用値が境界値付近となるBidを返す
251 }
252}
Note: See TracBrowser for help on using the repository browser.