source: src/main/java/agents/anac/y2016/syagent/bidSearch.java@ 201

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

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