source: src/main/java/agents/anac/y2019/kakesoba/KakeSoba.java@ 202

Last change on this file since 202 was 202, checked in by Katsuhide Fujita, 5 years ago

Add ANAC 2019 agents (3)
  • Property svn:executable set to *
File size: 14.2 KB
Line 
1package agents.anac.y2019.kakesoba;
2
3import genius.core.Bid;
4import genius.core.BidIterator;
5import genius.core.Domain;
6import genius.core.actions.*;
7import genius.core.issue.Issue;
8import genius.core.issue.IssueDiscrete;
9import genius.core.issue.ValueDiscrete;
10import genius.core.parties.AbstractNegotiationParty;
11import genius.core.parties.NegotiationInfo;
12import genius.core.uncertainty.AdditiveUtilitySpaceFactory;
13import genius.core.uncertainty.BidRanking;
14import genius.core.utility.AbstractUtilitySpace;
15import genius.core.utility.AdditiveUtilitySpace;
16import genius.core.utility.EvaluatorDiscrete;
17import genius.core.timeline.Timeline.Type;
18
19import java.util.*;
20
21/**
22 * KakeSoba
23 */
24public class KakeSoba extends AbstractNegotiationParty {
25 private int nrChosenActions = 0; // number of times chosenAction was called.
26 private boolean isFirstParty;
27 private boolean isDebug = false;
28 private boolean isInvalid = false;
29 private Map<String, Map<String, Double>> counts = new HashMap<String, Map<String, Double>>();
30
31 @Override
32 public void init(NegotiationInfo info) {
33 super.init(info);
34
35 if (!(utilitySpace instanceof AdditiveUtilitySpace)) {
36 System.out.println("This agent displays more interesting behavior with a additive utility function; now it simply generates random bids.");
37 isInvalid = true;
38 return;
39 }
40
41 AdditiveUtilitySpace additiveUtilitySpace = (AdditiveUtilitySpace) utilitySpace;
42 for (Issue issue : additiveUtilitySpace.getDomain().getIssues()) {
43 if (!(issue instanceof IssueDiscrete)) {
44 System.out.println("This agent displays more interesting behavior with a discrete issue domain; now it simply generates random bids.");
45 isInvalid = true;
46 return;
47 }
48 Map<String, Double> h = new HashMap<String, Double>();
49 for (ValueDiscrete value : ((IssueDiscrete)issue).getValues()) {
50 h.put(value.getValue(), 0.0D);
51 }
52 counts.put(issue.getName(), h);
53 }
54 }
55
56 public Action chooseAction(List<Class<? extends Action>> validActions) {
57 double t = this.getTimeLine().getTime();
58 nrChosenActions++;
59
60 if (this.isInvalid) {
61 return new Offer(getPartyId(), generateRandomBid());
62 }
63
64 // 最初のエージェントかどうかの判定
65 if (!(getLastReceivedAction() instanceof Offer) && !(getLastReceivedAction() instanceof Accept)){
66 isFirstParty = true;
67 }
68
69 // 受信処理
70 if (getLastReceivedAction() instanceof Offer) {
71 Bid receivedBid = ((Offer) getLastReceivedAction()).getBid();
72
73 // 受け取ったbidが良ければ承諾
74 if (isAcceptableBid(receivedBid, t)) {
75 return new Accept(getPartyId(), receivedBid);
76 }
77
78 // ラウンド制の例外処理
79 if (timeline.getType() == Type.Rounds) {
80 // 自分が最初のエージェントでなければ最終bidは受け入れ
81 // きっと相手がopponent modelingしているはず
82 if (!isFirstParty && timeline.getCurrentTime() >= timeline.getTotalTime() - 1) {
83 if (this.utilitySpace.getUtilityWithDiscount(receivedBid, t) > this.utilitySpace.getReservationValueWithDiscount(t)) {
84 return new Accept(getPartyId(), receivedBid);
85 }
86 }
87 }
88 }
89
90 if (isDebug) {
91 System.out.println(getPartyId() + ": " + getError());
92 System.out.println(getPartyId() + ": " + counts);
93 System.out.println(getPartyId() + ": " + utilitySpace);
94 }
95
96 // 初回は最も良いbidを提案
97 if(nrChosenActions == 1) {
98 try {
99 Bid bid = getUtilitySpace().getMaxUtilityBid();
100 countBid(bid);
101 return new Offer(getPartyId(), bid);
102 } catch (Exception e) {
103 e.printStackTrace();
104 }
105 }
106
107 // 相手の効用推定がうまくいく提案をする
108 Bid bid = generateBid(t);
109 countBid(bid);
110 return new Offer(getPartyId(), bid);
111 }
112
113 private void countBid(Bid bid, double weight) {
114 // 各論点について
115 for (Issue issue : bid.getIssues()) {
116 Map<String, Double> h = counts.get(issue.getName());
117 String value = ((ValueDiscrete) bid.getValue(issue)).getValue();
118 // 選ばれた選択肢のcountを重み分増やす
119 h.put(value, h.get(value) + weight);
120 }
121 }
122
123 private void countBid(Bid bid) { countBid(bid, 1.0D); }
124
125 private double getError() {
126 double error = 0.0D;
127
128 AdditiveUtilitySpace additiveUtilitySpace = (AdditiveUtilitySpace) utilitySpace;
129 // 各論点について
130 for (Issue issue : additiveUtilitySpace.getDomain().getIssues()) {
131 Map<String, Double> h = counts.get(issue.getName());
132 EvaluatorDiscrete evaluator = (EvaluatorDiscrete) additiveUtilitySpace.getEvaluator(issue);
133 // 最も提案された選択肢の提案回数
134 double max = h.values().stream().mapToDouble(Double::doubleValue).max().getAsDouble();
135 // 各選択肢の誤差
136 for (ValueDiscrete value : ((IssueDiscrete) issue).getValues()) {
137 error += Math.abs((h.get(value.getValue()) / max) - evaluator.getDoubleValue(value));
138 }
139 }
140 return error;
141 }
142
143 private double getErrorWithNewBid(Bid bid) {
144 double error;
145
146 // 提案回数に入れる
147 countBid(bid, 1.0D);
148 // 誤差を計算
149 error = getError();
150 // 提案回数を戻す
151 countBid(bid, -1.0D);
152
153 return error;
154 }
155
156 private Bid generateBid(double t) {
157 BidIterator bidIterator = new BidIterator(this.getDomain());
158
159 // 誤差が最小となる提案を探す
160 Bid bestBid;
161 try {
162 bestBid = utilitySpace.getMaxUtilityBid();
163 } catch (Exception e) {
164 bestBid = bidIterator.next();
165 }
166 double minError = getErrorWithNewBid(bestBid);
167 while (bidIterator.hasNext()) {
168 Bid bid = bidIterator.next();
169 if (!isProposableBid(bid, t)) {
170 continue;
171 }
172 double error = getErrorWithNewBid(bid);
173 if (error < minError) {
174 bestBid = bid;
175 minError = error;
176 }
177 }
178 return bestBid;
179 }
180
181 private boolean isProposableBid(Bid bid, double t) {
182 double utility ;
183 try {
184 utility = utilitySpace.getUtilityWithDiscount(bid, t);
185 } catch (Exception e) {
186 utility = -1.0D;
187 }
188
189 return getLowerBound(t) <= utility && utility <= getUpperBound(t) && utility >= utilitySpace.getReservationValueWithDiscount(t);
190 }
191
192 private boolean isAcceptableBid(Bid bid, double t) {
193 double utility ;
194 try {
195 utility = utilitySpace.getUtilityWithDiscount(bid, t);
196 } catch (Exception e) {
197 utility = -1.0D;
198 }
199
200 return getLowerBound(t) <= utility && utility >= utilitySpace.getReservationValueWithDiscount(t);
201 }
202
203 private double getUpperBound(double t) {
204 return 1.0D;
205 }
206
207 private double getLowerBound(double t) {
208 return 0.85D;
209 }
210
211 public AbstractUtilitySpace estimateUtilitySpace() {
212 List<Movement> TabuList = new ArrayList<Movement>();
213 AdditiveUtilitySpace additiveUtilitySpace = generateRandomUtilitySpace();
214 AdditiveUtilitySpace hallOfFame = additiveUtilitySpace;
215 double hallOfFameScore = getScore(hallOfFame, false);
216
217 if (this.isInvalid) {
218 return defaultUtilitySpaceEstimator(getDomain(), userModel);
219 }
220
221 // ドメインのサイズ(論点数＋総選択肢数)
222 int domainSize = 0;
223 for (Issue issue : this.getDomain().getIssues()) {
224 domainSize += ((IssueDiscrete) issue).getValues().size() + 1;
225 }
226
227 // パラメータ
228 int numOfMovement = 5000;
229 final double wightRate = this.getDomain().getIssues().size() * 1.0D / domainSize;
230
231 // タブーサーチ
232 for (int i = 0; i < numOfMovement; i ++) {
233 Map<Movement, AdditiveUtilitySpace> moveToNeighbors = new HashMap<Movement, AdditiveUtilitySpace>();
234
235 // 近傍を適当に列挙
236 for (int j = 0; j < domainSize; j ++) {
237 Movement movement = new Movement(this.getDomain(), wightRate);
238 // タブーリストにないやつで頼む
239 while (TabuList.contains(movement)) {
240 movement = new Movement(this.getDomain(), wightRate);
241 }
242 moveToNeighbors.put(movement, getNeighbor(additiveUtilitySpace, movement));
243 }
244
245 // 列挙した近傍の中で最もスコアが良いものを採用
246 Iterator<Map.Entry<Movement, AdditiveUtilitySpace>> iterator = moveToNeighbors.entrySet().iterator();
247 Map.Entry<Movement, AdditiveUtilitySpace> bestEntry = iterator.next();
248 double bestScore = -100.0D;
249 while (iterator.hasNext()) {
250 Map.Entry<Movement, AdditiveUtilitySpace> entry = iterator.next();
251 double score = getScore(entry.getValue(), false);
252 if (score > bestScore) {
253 bestEntry = entry;
254 bestScore = score;
255 }
256 }
257
258 // 効用空間の更新
259 additiveUtilitySpace = bestEntry.getValue();
260 // 殿堂入り
261 if (bestScore > hallOfFameScore) {
262 hallOfFame = additiveUtilitySpace;
263 hallOfFameScore = bestScore;
264 }
265
266 // タブーリストの更新
267 TabuList.add(bestEntry.getKey());
268 if (TabuList.size() > Math.sqrt(domainSize) / 2) {
269 TabuList.remove(0);
270 }
271
272 // デバッグ用
273 if (isDebug) {
274 getScore(additiveUtilitySpace, true);
275 }
276 }
277
278 // デバッグ用
279 if (isDebug) {
280 getScore(additiveUtilitySpace, true);
281 }
282
283 // 一番良かったのを返す
284 return hallOfFame;
285 }
286
287 private double getScore(AdditiveUtilitySpace additiveUtilitySpace, boolean isPrint) {
288 BidRanking bidRank = this.userModel.getBidRanking();
289
290 Map<Bid, Integer> realRanks = new HashMap<Bid, Integer>();
291 List<Double> estimatedUtils = new ArrayList<Double>();
292 for (Bid bid : bidRank.getBidOrder()) {
293 // 実際の順位を取得
294 realRanks.put(bid, realRanks.size());
295 // 推定した効用を取得
296 estimatedUtils.add(additiveUtilitySpace.getUtility(bid));
297 }
298 Collections.sort(estimatedUtils);
299
300 Map<Bid, Integer> estimatedRanks = new HashMap<Bid, Integer>();
301 for (Bid bid : bidRank.getBidOrder()) {
302 // 推定した効用から推定の順位を計算
303 estimatedRanks.put(bid, estimatedUtils.indexOf(additiveUtilitySpace.getUtility(bid)));
304 }
305
306 double errors = 0;
307 for (Bid bid : bidRank.getBidOrder()) {
308 errors += Math.pow(realRanks.get(bid) - estimatedRanks.get(bid), 2);
309 }
310
311 double spearman = 1.0D - 6.0D * errors / (Math.pow(realRanks.size(), 3) - realRanks.size());
312 double lowDiff = Math.abs(bidRank.getLowUtility().doubleValue() - additiveUtilitySpace.getUtility(bidRank.getMinimalBid()));
313 double highDiff = Math.abs(bidRank.getHighUtility().doubleValue() - additiveUtilitySpace.getUtility(bidRank.getMaximalBid()));
314 if(isPrint) {
315 System.out.println("spearman = " + spearman + ", lowDiff = " + lowDiff + ", highDiff = " + highDiff);
316 }
317
318 return spearman * 10.0D + (1.0D - lowDiff) + (1.0D - highDiff);
319 }
320
321
322 private AdditiveUtilitySpace generateRandomUtilitySpace() {
323 AdditiveUtilitySpaceFactory additiveUtilitySpaceFactory = new AdditiveUtilitySpaceFactory(this.getDomain());
324
325 // 値をランダムに設定
326 for (IssueDiscrete issue : additiveUtilitySpaceFactory.getIssues()) {
327 additiveUtilitySpaceFactory.setWeight(issue, this.rand.nextDouble());
328
329 for (ValueDiscrete value : issue.getValues()) {
330 additiveUtilitySpaceFactory.setUtility(issue, value, this.rand.nextDouble());
331 }
332 }
333
334 // 正規化して返す
335 normalize(additiveUtilitySpaceFactory);
336 return additiveUtilitySpaceFactory.getUtilitySpace();
337 }
338
339 private AdditiveUtilitySpace getNeighbor(AdditiveUtilitySpace current, Movement movement) {
340 double speed = 1.0D; // 遷移時に値をどれくらい動かすか
341 AdditiveUtilitySpaceFactory neighbor = getAdditiveUtilitySpaceFactoryFrom(current);
342
343 // 遷移
344 IssueDiscrete issue = neighbor.getIssues().get(movement.getIssueID());
345 if (movement.getIsWeight()) {
346 // 重みを変える
347 if (rand.nextBoolean()) {
348 neighbor.setWeight(issue, current.getWeight(issue) + speed * rand.nextDouble() / neighbor.getIssues().size());
349 } else {
350 neighbor.setWeight(issue, Math.abs(current.getWeight(issue) - speed * rand.nextDouble() / neighbor.getIssues().size()));
351 }
352
353 } else {
354 // 評価値の平均
355 double averageEval = 0;
356 for (ValueDiscrete v : issue.getValues()) {
357 averageEval += ((EvaluatorDiscrete)current.getEvaluator(issue)).getDoubleValue(v);
358 }
359 averageEval /= issue.getValues().size();
360
361 // 評価値を変える
362 ValueDiscrete value = issue.getValue(movement.getValueID());
363 double eval = ((EvaluatorDiscrete)current.getEvaluator(issue)).getDoubleValue(value);
364 if (rand.nextBoolean()) {
365 neighbor.setUtility(issue, value, eval + speed * averageEval * rand.nextDouble());
366 } else {
367 neighbor.setUtility(issue, value, Math.abs(eval - speed * averageEval * rand.nextDouble()));
368 }
369 }
370
371 // 正規化して返す
372 normalize(neighbor);
373 return neighbor.getUtilitySpace();
374 }
375
376 private AdditiveUtilitySpaceFactory getAdditiveUtilitySpaceFactoryFrom(AdditiveUtilitySpace additiveUtilitySpace){
377 AdditiveUtilitySpaceFactory additiveUtilitySpaceFactory = new AdditiveUtilitySpaceFactory(getDomain());
378 // もとの効用空間をコピー
379 for (IssueDiscrete issue : additiveUtilitySpaceFactory.getIssues()) {
380 additiveUtilitySpaceFactory.setWeight(issue, additiveUtilitySpace.getWeight(issue));
381 for (ValueDiscrete value : issue.getValues()) {
382 additiveUtilitySpaceFactory.setUtility(issue, value, ((EvaluatorDiscrete) additiveUtilitySpace.getEvaluator(issue)).getDoubleValue(value));
383 }
384 }
385 return additiveUtilitySpaceFactory;
386 }
387
388 private void normalize(AdditiveUtilitySpaceFactory additiveUtilitySpaceFactory){
389 // 重み正規化
390 additiveUtilitySpaceFactory.normalizeWeights();
391
392 // 評価値正規化
393 for (IssueDiscrete issue : additiveUtilitySpaceFactory.getIssues()) {
394 double max = issue.getValues().stream().map(value -> additiveUtilitySpaceFactory.getUtility(issue, value)).max(Double::compareTo).get();
395 for (ValueDiscrete value : issue.getValues()) {
396 double eval = additiveUtilitySpaceFactory.getUtility(issue, value);
397 additiveUtilitySpaceFactory.setUtility(issue, value, eval / max);
398 }
399 }
400 }
401
402 public String getDescription() {
403 return "KakeSoba";
404 }
405
406
407 private class Movement {
408 private int issueID;
409 private int valueID;
410 private boolean isWeight;
411
412 public Movement(int issueID, int valueID) {
413 this.issueID = issueID;
414 this.valueID = valueID;
415 this.isWeight = false;
416 }
417
418 public Movement(int issueID) {
419 this.issueID = issueID;
420 this.valueID = 0;
421 this.isWeight = true;
422 }
423
424 public Movement(Domain domain, double wightRate) {
425 List<Issue> issues = domain.getIssues();
426 this.issueID = rand.nextInt(issues.size());
427
428 if (rand.nextDouble() > wightRate) {
429 this.isWeight = true;
430 this.valueID = 0;
431 } else {
432 this.isWeight = false;
433 this.valueID = rand.nextInt(((IssueDiscrete) issues.get(this.issueID)).getNumberOfValues());
434 }
435 }
436
437 private int getIssueID() {
438 return this.issueID;
439 }
440
441 private int getValueID() {
442 return this.valueID;
443 }
444
445 private boolean getIsWeight() {
446 return this.isWeight;
447 }
448 }
449}
Note: See TracBrowser for help on using the repository browser.