source: src/main/java/agents/anac/y2015/agenth/BidHelper.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: 9.5 KB
Line 
1package agents.anac.y2015.agenth;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.List;
7import java.util.Random;
8
9import agents.anac.y2015.agenth.BidHistory.Entry;
10import genius.core.Bid;
11import genius.core.Domain;
12import genius.core.issue.Issue;
13import genius.core.issue.IssueDiscrete;
14import genius.core.issue.IssueInteger;
15import genius.core.issue.IssueReal;
16import genius.core.issue.Value;
17import genius.core.issue.ValueDiscrete;
18import genius.core.issue.ValueInteger;
19import genius.core.issue.ValueReal;
20import genius.core.utility.AbstractUtilitySpace;
21
22public class BidHelper {
23 // 探索のパラメータ
24 private static final int SA_ITERATION = 1;
25 private static final double START_TEMPERATURE = 1.0; // 開始温度
26 private static final double END_TEMPERATURE = 0.0001; // 終了温度
27 private static final double COOL = 0.999; // 冷却度
28 private static final int STEP = 1;// 変更する幅
29 private static final int STEP_NUM = 1; // 変更する回数
30
31 /** エージェント */
32 private AgentH mAgent;
33 /** 乱数 */
34 private Random mRandom;
35 /** 自身の効用空間における各論点値の相対効用値行列（線形効用空間用) */
36 private HashMap<Issue, HashMap<Value, Double>> mValueRelativeUtility;
37 /** 効用値 MAX の bid */
38 private Bid mMaxBid;
39
40 public BidHelper(AgentH agent) throws Exception {
41 mAgent = agent;
42 mRandom = new Random();
43 mValueRelativeUtility = new HashMap<Issue, HashMap<Value, Double>>();
44
45 initMaxBid();
46 initValueRelativeUtility();
47 setValueRelativeUtility(mMaxBid);
48 }
49
50 /** 相対効用行列の初期化 */
51 private void initValueRelativeUtility() throws Exception {
52 final List<Issue> issues = getIssues();
53 for (Issue issue : issues) {
54 // 論点行の初期化
55 mValueRelativeUtility.put(issue, new HashMap<Value, Double>());
56 // 論点行の要素の初期化
57 final ArrayList<Value> values = getValuesForIssue(issue);
58 for (Value value : values) {
59 mValueRelativeUtility.get(issue).put(value, 0.0);
60 }
61 }
62 }
63
64 /** 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため，SAを用いて探索する) */
65 private void initMaxBid() throws Exception {
66 final AbstractUtilitySpace utilitySpace = mAgent.getUtilitySpace();
67
68 int tryNum = getIssues().size(); // 試行回数
69 mMaxBid = mAgent.getUtilitySpace().getDomain().getRandomBid(null);
70 for (int i = 0; i < tryNum; i++) {
71 do {
72 generateFromSimulatedAnnealingSearch(mMaxBid, 1.0);
73 } while (utilitySpace.getUtility(mMaxBid) < utilitySpace
74 .getReservationValue());
75
76 if (utilitySpace.getUtility(mMaxBid) == 1.0) {
77 break;
78 }
79 }
80 }
81
82 /** 相対効用行列の導出 */
83 public void setValueRelativeUtility(Bid maxBid) throws Exception {
84 final AgentH agent = mAgent;
85
86 Bid currentBid = null;
87 final List<Issue> issues = getIssues();
88 for (Issue issue : issues) {
89 currentBid = new Bid(maxBid);
90 final ArrayList<Value> values = getValuesForIssue(issue);
91 for (Value value : values) {
92 currentBid = currentBid.putValue(issue.getNumber(), value);
93 mValueRelativeUtility.get(issue)
94 .put(value,
95 agent.getUtility(currentBid)
96 - agent.getUtility(maxBid));
97 }
98 }
99 }
100
101 public Domain getDomain() {
102 return mAgent.getUtilitySpace().getDomain();
103 }
104
105 public List<Issue> getIssues() {
106 return getDomain().getIssues();
107 }
108
109 public ArrayList<Value> getValuesForIssue(Issue issue) {
110 final ArrayList<Value> values = new ArrayList<Value>();
111 switch (issue.getType()) {
112 case DISCRETE:
113 List<ValueDiscrete> valuesDis = ((IssueDiscrete) issue).getValues();
114 for (Value value : valuesDis) {
115 values.add(value);
116 }
117 break;
118 case INTEGER:
119 int min_value = ((IssueInteger) issue).getUpperBound();
120 int max_value = ((IssueInteger) issue).getUpperBound();
121 for (int j = min_value; j <= max_value; j++) {
122 Object valueObject = new Integer(j);
123 values.add((Value) valueObject);
124 }
125 break;
126 default:
127 try {
128 throw new Exception("issue type " + issue.getType()
129 + " not supported by Atlas3");
130 } catch (Exception e) {
131 // System.out.println("論点の取り得る値の取得に失敗しました");
132 // e.printStackTrace();
133 }
134 }
135 return values;
136 }
137
138 /** 相対効用値に基づく探索 */
139 public Bid generateFromRelativeUtilitySearch(double threshold) {
140 Bid bid = new Bid(mMaxBid);
141 double d = threshold - 1.0; // 最大効用値との差
142 double concessionSum = 0.0; // 減らした効用値の和
143 double relativeUtility = 0.0;
144 final HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = mValueRelativeUtility;
145
146 List<Issue> randomIssues = getIssues();
147 Collections.shuffle(randomIssues);
148 ArrayList<Value> randomValues = null;
149 for (Issue issue : randomIssues) {
150 randomValues = getValuesForIssue(issue);
151 Collections.shuffle(randomValues);
152 for (Value value : randomValues) {
153 // 最大効用値を基準とした相対効用値
154 relativeUtility = valueRelativeUtility.get(issue).get(value);
155 if (d <= concessionSum + relativeUtility) {
156 bid = bid.putValue(issue.getNumber(), value);
157 concessionSum += relativeUtility;
158 break;
159 }
160 }
161 }
162 return bid;
163 }
164
165 /** SA */
166 public Bid generateFromSimulatedAnnealingSearch(Bid baseBid,
167 double threshold) {
168 final AgentH agent = mAgent;
169 final List<Issue> issues = getIssues();
170
171 Bid currentBid = new Bid(baseBid); // 初期解の生成
172 double currenBidUtil = agent.getUtility(baseBid);
173 Bid nextBid = null; // 評価Bid
174 double nextBidUtil = 0.0;
175 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // 最適効用値BidのArrayList
176 double targetBidUtil = 0.0;
177 double p; // 遷移確率
178 Random randomnr = new Random(); // 乱数
179 double currentTemperature = START_TEMPERATURE; // 現在の温度
180 double newCost = 1.0;
181 double currentCost = 1.0;
182
183 while (currentTemperature > END_TEMPERATURE) { // 温度が十分下がるまでループ
184 nextBid = new Bid(currentBid); // next_bidを初期化
185 for (int i = 0; i < STEP_NUM; i++) { // 近傍のBidを取得する
186 int issueIndex = randomnr.nextInt(issues.size()); // 論点をランダムに指定
187 Issue issue = issues.get(issueIndex); // 指定したindexのissue
188 ArrayList<Value> values = getValuesForIssue(issue);
189 int valueIndex = randomnr.nextInt(values.size()); // 取り得る値の範囲でランダムに指定
190 nextBid = nextBid.putValue(issue.getNumber(),
191 values.get(valueIndex));
192 nextBidUtil = agent.getUtility(nextBid);
193
194 // 最大効用値Bidの更新
195 if (mMaxBid == null || nextBidUtil >= agent.getUtility(mMaxBid)) {
196 mMaxBid = new Bid(nextBid);
197 }
198 }
199
200 newCost = Math.abs(threshold - nextBidUtil);
201 currentCost = Math.abs(threshold - currenBidUtil);
202 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
203 if (newCost < currentCost || p > randomnr.nextDouble()) {
204 currentBid = new Bid(nextBid); // Bidの更新
205 currenBidUtil = nextBidUtil;
206 }
207
208 // 更新
209 if (currenBidUtil >= threshold) {
210 if (targetBids.size() == 0) {
211 targetBids.add(new Bid(currentBid));
212 targetBidUtil = agent.getUtility(currentBid);
213 } else {
214 if (currenBidUtil < targetBidUtil) {
215 targetBids.clear(); // 初期化
216 targetBids.add(new Bid(currentBid)); // 要素を追加
217 targetBidUtil = agent.getUtility(currentBid);
218 } else if (currenBidUtil == targetBidUtil) {
219 targetBids.add(new Bid(currentBid)); // 要素を追加
220 }
221 }
222 }
223 currentTemperature = currentTemperature * COOL; // 温度を下げる
224 }
225
226 if (targetBids.size() == 0) {
227 return new Bid(baseBid);
228 } // 境界値より大きな効用値を持つBidが見つからなかったときは，baseBidを返す
229 else {
230 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
231 } // 効用値が境界値付近となるBidを返す
232 }
233
234 /**
235 * 過去の bid から次の bid を生成
236 *
237 * @param threshold
238 * @return
239 */
240 public Bid generateFromHistory(double threshold) {
241 Bid nextBid = null;
242 double nextUtility = 0;
243
244 // 過去の bid を効用値の高い順に持ってくる
245 final BidHistory bidHistory = mAgent.mBidHistory;
246 final List<Entry> entries = bidHistory.getSortedList();
247 for (BidHistory.Entry e : entries) {
248 nextBid = null;
249 nextUtility = e.utility;
250
251 // bid を少し変えたものを次の bid とする
252 final List<Issue> issues = e.bid.getIssues();
253 for (Issue issue : issues) {
254 final int issueNr = issue.getNumber();
255 Bid bid = new Bid(e.bid);
256 switch (issue.getType()) {
257 case DISCRETE: {
258 final List<ValueDiscrete> values = ((IssueDiscrete) issue)
259 .getValues();
260 Collections.shuffle(values);
261 bid = bid.putValue(issueNr, values.get(0));
262 }
263 break;
264 case INTEGER: {
265 final int upperBound = ((IssueInteger) issue)
266 .getUpperBound();
267 final int lowerBound = ((IssueInteger) issue)
268 .getLowerBound();
269 bid = bid.putValue(issueNr, new ValueInteger(lowerBound
270 + mRandom.nextInt(upperBound - lowerBound)));
271 }
272 break;
273 case REAL: {
274 final double upperBound = ((IssueReal) issue)
275 .getUpperBound();
276 final double lowerBound = ((IssueReal) issue)
277 .getLowerBound();
278 bid = bid
279 .putValue(issueNr, new ValueReal(lowerBound
280 + mRandom.nextDouble()
281 * (upperBound - lowerBound)));
282 }
283 break;
284 }
285 if (nextUtility - mAgent.getUtility(bid) < threshold
286 && !bidHistory.containsBid(bid)) {
287 nextBid = bid;
288 // System.out.println("OreoreAgent#generateNextBid(): nextBid="+nextBid);
289 }
290 }
291
292 if (nextBid != null) {
293 break;
294 }
295 }
296
297 return nextBid;
298 }
299}
Note: See TracBrowser for help on using the repository browser.