source: src/main/java/agents/anac/y2014/Flinch/Flinch.java@ 319

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

Initial import : Genius 9.0.0
File size: 15.6 KB
Line 
1package agents.anac.y2014.Flinch;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.HashSet;
6import java.util.List;
7import java.util.Random;
8import java.util.Set;
9
10import genius.core.Agent;
11import genius.core.Bid;
12import genius.core.NegotiationResult;
13import genius.core.actions.Accept;
14import genius.core.actions.Action;
15import genius.core.actions.ActionWithBid;
16import genius.core.actions.EndNegotiation;
17import genius.core.actions.Offer;
18import genius.core.bidding.BidDetails;
19import genius.core.issue.Issue;
20import genius.core.issue.IssueDiscrete;
21import genius.core.issue.IssueInteger;
22import genius.core.issue.IssueReal;
23import genius.core.issue.Value;
24import genius.core.issue.ValueDiscrete;
25import genius.core.issue.ValueInteger;
26import genius.core.issue.ValueReal;
27
28public class Flinch extends Agent {
29 private Action actionOfPartner = null;
30
31 private ArrayList<BidDetails> history = null; // opponent's bid history
32 private ArrayList<BidDetails> myHistory = null; // my bid history
33 private Bid bestBidFromOpponent = null;
34
35 private double estimatedMaxUtil = 1.0; // estimated best utility for me,
36 // default at 1.0
37 private boolean defaultEMU = true;
38
39 private double acceptThreshold = 0.0;
40
41 private int round = 0;
42
43 // parameter for acceptThreshold calculation
44 private double t_lambda;
45 private final double t_lambda_min = 0.1;
46 private final double t_lambda_max = 0.8; // @POINT
47 // private final double t_lambda_max = 1.0;
48
49 private final double beta = 2;
50 private final double p_max = 0.95;
51 private final double p_min = 0.84; // @POINT
52
53 // parameter for the assess function
54 private double Kop; // dynamic
55
56 // parameter for kernel function
57 private double h; // dynamic
58
59 private final int MINIMUM_TRAIN_DATA = 20;
60 // private final double MINIMUM_PANIC_CHECK_TIME = 0.9;
61
62 // parameter for GA
63 private int GA_MAX_ITERATIONS = 200;
64 private int POP_SIZE = 20;
65 private double Ps = 0.6;
66 private double Pm = 0.4;
67
68 /**
69 * init is called when a next session starts with the same opponent.
70 */
71 @Override
72 public void init() {
73 history = new ArrayList<BidDetails>();
74 myHistory = new ArrayList<BidDetails>();
75
76 t_lambda = getLambda();
77 }
78
79 @Override
80 public String getVersion() {
81 return "1.0";
82 }
83
84 @Override
85 public String getName() {
86 return "Flinch";
87 }
88
89 @Override
90 public void endSession(NegotiationResult dUtil) {
91
92 }
93
94 @Override
95 public void ReceiveMessage(Action opponentAction) {
96 actionOfPartner = opponentAction;
97 }
98
99 @Override
100 public Action chooseAction() // main function
101 {
102 // System.out.println("===============");
103
104 Action action = null;
105
106 try {
107 double t = timeline.getTime();
108 updateAcceptThreshold(timeline.getTime());
109 // System.out.println("updated acceptThreshold = " +
110 // acceptThreshold);
111 // System.out.println("estimatedMaxUtil = " + estimatedMaxUtil);
112 // System.out.println("t = " + t + "\tt_lambda = " + t_lambda);
113 // if(bestBidFromOpponent != null)
114 // System.out.println("U_bbo = " +
115 // utilitySpace.getUtility(bestBidFromOpponent));
116
117 round++;
118
119 if (actionOfPartner == null) {
120 Bid myBid = chooseNextBid();
121 myHistory.add(
122 new BidDetails(myBid, utilitySpace.getUtility(myBid)));
123
124 action = new Offer(getAgentID(), myBid);
125 } else {
126 if (actionOfPartner instanceof Offer) {
127 Bid partnerBid = ((Offer) actionOfPartner).getBid();
128 double offeredUtilFromOpponent = utilitySpace
129 .getUtility(partnerBid);
130
131 history.add(new BidDetails(partnerBid,
132 offeredUtilFromOpponent, t));
133 if (bestBidFromOpponent == null
134 || offeredUtilFromOpponent > utilitySpace
135 .getUtility(bestBidFromOpponent)) {
136 bestBidFromOpponent = partnerBid;
137 }
138
139 if (isAcceptable(offeredUtilFromOpponent)) {
140 action = new Accept(getAgentID(), partnerBid);
141 } else if (shouldTerminate(offeredUtilFromOpponent)) {
142 action = new EndNegotiation(getAgentID());
143 } else {
144 Bid myBid = chooseNextBid();
145 myHistory.add(new BidDetails(myBid,
146 utilitySpace.getUtility(myBid)));
147
148 action = new Offer(getAgentID(), myBid);
149 }
150 } else {
151 throw new Exception("partner action type should be Offer!");
152 }
153 }
154 } catch (Exception e) {
155 System.out.println("Exception in ChooseAction:" + e.getMessage());
156 e.printStackTrace();
157
158 action = new Accept(getAgentID(),
159 ((ActionWithBid) actionOfPartner).getBid());
160 }
161
162 return action;
163 }
164
165 private int estimatedRoundsLeft() {
166 int n = history.size();
167 if (n <= 10) {
168 return 1000; // infinity
169 }
170
171 double dur = history.get(n - 1).getTime()
172 - history.get(n - 1 - 10).getTime();
173 double timeForOneRound = dur / 10;
174 double round = (1.0 - timeline.getTime()) / timeForOneRound;
175
176 return (int) round;
177 }
178
179 private double getLambda() {
180 double beta = 1.5;
181 double delta = utilitySpace.getDiscountFactor();
182
183 if (delta > 0.75) {
184 beta = 2.5;
185 } else if (delta > 0.5) {
186 beta = 2;
187 } else {
188 beta = 1.5;
189 }
190
191 return t_lambda_min
192 + (t_lambda_max - t_lambda_min) * Math.pow(delta, beta);
193 }
194
195 private double getAcceptThreshold(double t) {
196 double ret = 1.0;
197 double r = utilitySpace.getReservationValue();
198 double M = estimatedMaxUtil;
199
200 double left = Math.max(r, M * p_max);
201 double right = Math.max(r, M * p_min);
202
203 double middle = 0.5 * left + 0.5 * right;
204
205 assert left >= middle;
206 assert middle >= right;
207
208 if (t <= t_lambda) {
209 ret = left + (middle - left) * Math.pow(t / t_lambda, 1 / beta);
210 } else { // @POINT
211 try {
212 right = Math.min(right,
213 utilitySpace.getUtility(bestBidFromOpponent));
214 } catch (Exception e) {
215 }
216
217 ret = middle + (right - middle)
218 * Math.pow((t - t_lambda) / (1 - t_lambda), 1 / beta);
219 }
220
221 if (Double.isNaN(ret) || Double.isInfinite(ret)) { // @TODO
222 System.out.println(
223 "Errors in calculating acceptThreshold, default to M*p = "
224 + left);
225 ret = left;
226 }
227
228 return ret;
229 }
230
231 private void updateAcceptThreshold(double t) {
232 acceptThreshold = getAcceptThreshold(t);
233 }
234
235 private boolean isAcceptable(double offeredUtilFromOpponent) {
236 return offeredUtilFromOpponent > acceptThreshold;
237 }
238
239 private boolean shouldTerminate(double offeredUtilFromOpponent) {
240 return utilitySpace.getReservationValue() > acceptThreshold;
241 }
242
243 private double distance(Bid b1, Bid b2) throws Exception {
244 double sweight = 0.0;
245 double r = 0.0;
246
247 List<Issue> issues = b1.getIssues();
248 for (int i = 0; i < issues.size(); i++) {
249 Issue issue = issues.get(i);
250 double diff = 0.0;
251
252 switch (issue.getType()) {
253 case DISCRETE: {
254 IssueDiscrete lIssueDiscrete = (IssueDiscrete) issue;
255 ValueDiscrete v1d = (ValueDiscrete) b1
256 .getValue(issue.getNumber());
257 ValueDiscrete v2d = (ValueDiscrete) b2
258 .getValue(issue.getNumber());
259 if (!v1d.equals(v2d)) {
260 diff = 1.0;
261 }
262
263 break;
264 }
265 case REAL: {
266 IssueReal lIssueReal = (IssueReal) issue;
267 ValueReal v1r = (ValueReal) b1.getValue(issue.getNumber());
268 ValueReal v2r = (ValueReal) b2.getValue(issue.getNumber());
269 double abs_diff = Math.abs(v1r.getValue() - v2r.getValue());
270 diff = abs_diff / (lIssueReal.getUpperBound()
271 - lIssueReal.getLowerBound());
272 break;
273 }
274 case INTEGER: {
275 IssueInteger lIssueInteger = (IssueInteger) issue;
276 ValueInteger v1i = (ValueInteger) b1
277 .getValue(issue.getNumber());
278 ValueInteger v2i = (ValueInteger) b2
279 .getValue(issue.getNumber());
280 double abs_diff = Math.abs(v1i.getValue() - v2i.getValue());
281 diff = abs_diff / (lIssueInteger.getUpperBound()
282 - lIssueInteger.getLowerBound());
283 break;
284 }
285
286 default:
287 throw new Exception("issue type " + issue.getType()
288 + " not supported by Flinch");
289 }
290
291 r += diff * 1.0;
292 sweight += 1.0;
293 }
294
295 assert r / sweight >= 0.0 && r / sweight <= 1.0;
296
297 return r / sweight;
298 }
299
300 private double kernel_function(double x) {
301 if (x <= 1.0 && x >= -1.0) {
302 return Math.pow(1 - x * x, 3);
303 }
304
305 return 0.0;
306 }
307
308 private double kernel(Bid b1, Bid b2) throws Exception {
309 return kernel_function(distance(b1, b2) / h);
310 }
311
312 private double estimatedOpponentUtility(Bid b) throws Exception {
313 if (history.size() < MINIMUM_TRAIN_DATA) {
314 return 1.0;
315 }
316
317 int n = history.size();
318 double gamma = 1.0;
319
320 double ret = 0.0;
321 double k = 1.0;
322 double denom = 0.0;
323
324 for (BidDetails bd : history) {
325 ret += k * kernel(bd.getBid(), b);
326 denom += k;
327 k *= gamma;
328 }
329
330 return ret / denom;
331 }
332
333 private Bid chooseNextBid() throws Exception {
334 Bid[] candidates = search(1.0);
335 double f = 0.98;
336 while (candidates.length == 0) {
337 candidates = search(f);
338 f *= f;
339 }
340
341 // dynamic parameter
342 h = 0.3 + (1.0 - 0.3) * Math.random();
343 Kop = 0.5 + (0.9 - 0.5) * Math.pow(timeline.getTime(), 0.5); // @POINT
344
345 double[] opUtils = new double[candidates.length];
346 double[] myUtils = new double[candidates.length];
347 double maxOpUtil = 0.0;
348 double maxMyUtil = 0.0;
349
350 double[] score = new double[candidates.length];
351
352 for (int i = 0; i < candidates.length; i++) {
353 myUtils[i] = utilitySpace.getUtility(candidates[i])
354 / estimatedMaxUtil;
355
356 if (myUtils[i] > maxMyUtil) {
357 maxMyUtil = myUtils[i];
358 }
359 }
360 if (maxMyUtil > 0.0) {
361 for (int i = 0; i < candidates.length; i++) {
362 myUtils[i] /= maxMyUtil;
363 assert myUtils[i] >= 0 && myUtils[i] <= 1.0;
364 }
365 }
366
367 for (int i = 0; i < candidates.length; i++) {
368 opUtils[i] = estimatedOpponentUtility(candidates[i]);
369
370 if (opUtils[i] > maxOpUtil) {
371 maxOpUtil = opUtils[i];
372 }
373 }
374 if (maxOpUtil > 0.0) {
375 for (int i = 0; i < candidates.length; i++) {
376 opUtils[i] /= maxOpUtil;
377 assert opUtils[i] >= 0 && opUtils[i] <= 1.0;
378 }
379 }
380
381 int maxi = 0;
382 for (int i = 0; i < candidates.length; i++) {
383 score[i] = myUtils[i] * (1 - Kop) + opUtils[i] * Kop;
384 if (score[i] > score[maxi])
385 maxi = i;
386 }
387
388 // select max
389 int i = 0;
390 for (int j = 1; j < candidates.length; j++) {
391 if (score[j] > score[i])
392 i = j;
393 }
394 Bid result = candidates[i];
395
396 for (BidDetails bd : history) {
397 double s = bd.getMyUndiscountedUtil();
398 if (s > utilitySpace.getUtility(result)) {
399 result = bd.getBid();
400 }
401 }
402
403 return result;
404 }
405
406 // ==============================
407 // LocalSearch
408 // ================================
409
410 public Bid getRandomBid() throws Exception {
411 HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
412 // <issuenumber,chosen
413 // value
414 // string>
415 List<Issue> issues = utilitySpace.getDomain().getIssues();
416 Random randomnr = new Random();
417
418 Bid bid = null;
419
420 for (Issue lIssue : issues) {
421 switch (lIssue.getType()) {
422 case DISCRETE:
423 IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
424 int optionIndex = randomnr
425 .nextInt(lIssueDiscrete.getNumberOfValues());
426 values.put(lIssue.getNumber(),
427 lIssueDiscrete.getValue(optionIndex));
428 break;
429 case REAL:
430 IssueReal lIssueReal = (IssueReal) lIssue;
431 int optionInd = randomnr.nextInt(
432 lIssueReal.getNumberOfDiscretizationSteps() - 1);
433 values.put(lIssueReal.getNumber(),
434 new ValueReal(lIssueReal.getLowerBound() + (lIssueReal
435 .getUpperBound() - lIssueReal.getLowerBound())
436 * (optionInd) / (lIssueReal
437 .getNumberOfDiscretizationSteps())));
438 break;
439 case INTEGER:
440 IssueInteger lIssueInteger = (IssueInteger) lIssue;
441 int optionIndex2 = lIssueInteger.getLowerBound()
442 + randomnr.nextInt(lIssueInteger.getUpperBound()
443 - lIssueInteger.getLowerBound());
444 values.put(lIssueInteger.getNumber(),
445 new ValueInteger(optionIndex2));
446 break;
447
448 default:
449 throw new Exception("issue type " + lIssue.getType()
450 + " not supported by Flinch LocalSearch");
451 }
452 }
453
454 bid = new Bid(utilitySpace.getDomain(), values);
455
456 return bid;
457 }
458
459 double sq(double x) {
460 return x * x;
461 }
462
463 // ======================
464 // GA functions
465 // =======================
466
467 private double GA_fitness(Bid b) throws Exception {
468 return utilitySpace.getUtility(b);
469 }
470
471 private Bid GA_select(Bid[] population, double[] score, double N)
472 throws Exception { // currently
473 // using
474 // roulette
475 double r = Math.random();
476
477 double s = 0.0;
478 for (int i = 0; i < POP_SIZE; i++) {
479 double f = score[i];
480 if (s <= r && r < s + f / N) {
481 return population[i];
482 }
483
484 s += f / N;
485 }
486
487 assert false;
488 return population[POP_SIZE - 1];
489 }
490
491 private Bid GA_crossover(Bid b1, Bid b2) throws Exception {
492 List<Issue> issues = utilitySpace.getDomain().getIssues();
493 Random randomnr = new Random();
494 int k = (int) Math.random() * issues.size();
495 Bid ret = new Bid(b1);
496
497 for (int i = k; i < issues.size(); i++) {
498 int issuenr = issues.get(i).getNumber();
499 ret = ret.putValue(issuenr, b2.getValue(issuenr));
500 }
501
502 return ret;
503 }
504
505 private Bid GA_mutate(Bid b) throws Exception {
506 List<Issue> issues = utilitySpace.getDomain().getIssues();
507 Random randomnr = new Random();
508 int k = randomnr.nextInt(issues.size());
509 int issuenr = issues.get(k).getNumber();
510
511 Value v = null;
512
513 switch (issues.get(k).getType()) {
514 case DISCRETE: {
515 IssueDiscrete lIssueDiscrete = (IssueDiscrete) issues.get(k);
516 int optionIndex = randomnr
517 .nextInt(lIssueDiscrete.getNumberOfValues());
518 v = lIssueDiscrete.getValue(optionIndex);
519 break;
520 }
521 case REAL: {
522 IssueReal lIssueReal = (IssueReal) issues.get(k);
523 int optionInd = randomnr
524 .nextInt(lIssueReal.getNumberOfDiscretizationSteps() - 1);
525 v = new ValueReal(lIssueReal.getLowerBound()
526 + (lIssueReal.getUpperBound() - lIssueReal.getLowerBound())
527 * (optionInd)
528 / (lIssueReal.getNumberOfDiscretizationSteps()));
529 break;
530 }
531 case INTEGER: {
532 IssueInteger lIssueInteger = (IssueInteger) issues.get(k);
533 int optionIndex2 = lIssueInteger.getLowerBound()
534 + randomnr.nextInt(lIssueInteger.getUpperBound()
535 - lIssueInteger.getLowerBound());
536 v = new ValueInteger(optionIndex2);
537 break;
538 }
539
540 default:
541 throw new Exception("issue type " + issues.get(k).getType()
542 + " not supported by Flinch LocalSearch");
543 }
544 assert v != null;
545
546 b = b.putValue(issuenr, v);
547 return b;
548 }
549
550 private void updateCandidatesSet(Set<Bid> ret, Bid[] population, double f)
551 throws Exception {
552 double t = timeline.getTime();
553 for (int i = 0; i < POP_SIZE; i++) {
554 double score = utilitySpace.getUtility(population[i]);
555
556 if (defaultEMU || score > estimatedMaxUtil) {
557 defaultEMU = false;
558 estimatedMaxUtil = score;
559 }
560
561 if (acceptThreshold * f < score) {
562 ret.add(population[i]);
563 }
564 }
565 }
566
567 private Bid[] GA(double f) throws Exception {
568 Set<Bid> ret = new HashSet<Bid>();
569 Bid[] population = new Bid[POP_SIZE];
570 double[] score = new double[POP_SIZE];
571
572 for (int i = 0; i < POP_SIZE; i++) {
573 population[i] = getRandomBid();
574 }
575
576 int iter = 0;
577 while (iter < GA_MAX_ITERATIONS) {
578 iter++;
579
580 updateCandidatesSet(ret, population, f);
581
582 Bid[] newpopulation = new Bid[POP_SIZE];
583 int to_select = (int) Ps * POP_SIZE;
584
585 double sum_f = 0.0;
586 for (int i = 0; i < POP_SIZE; i++) {
587 score[i] = GA_fitness(population[i]);
588 sum_f += score[i];
589 }
590
591 for (int i = 0; i < to_select; i++) {
592 newpopulation[i] = new Bid(GA_select(population, score, sum_f));
593 }
594
595 for (int i = 0; i < POP_SIZE - to_select; i++) {
596 Bid b1 = GA_select(population, score, sum_f);
597 Bid b2 = GA_select(population, score, sum_f);
598
599 newpopulation[i + to_select] = GA_crossover(b1, b2);
600 }
601
602 for (int i = to_select; i < POP_SIZE; i++) {
603 if (Math.random() < Pm) {
604 newpopulation[i] = GA_mutate(newpopulation[i]);
605 }
606 }
607
608 population = newpopulation;
609 }
610 updateCandidatesSet(ret, population, f);
611
612 return ret.toArray(new Bid[0]);
613 }
614
615 public Bid[] search(double f) throws Exception {
616 return GA(f);
617 }
618
619 @Override
620 public String getDescription() {
621 return "ANAC2014 compatible with non-linear utility spaces";
622 }
623}
Note: See TracBrowser for help on using the repository browser.