source: src/main/java/agents/anac/y2018/condagent/BayesianOpponentModel.java@ 341

Last change on this file since 341 was 341, checked in by Katsuhide Fujita, 4 years ago

Katsuhide Fujita added ANAC2018 agents.
File size: 14.7 KB
Line 
1package agents.anac.y2018.condagent;
2
3import java.io.PrintStream;
4import java.util.ArrayList;
5import java.util.List;
6import negotiator.Bid;
7import negotiator.Domain;
8import negotiator.issue.Issue;
9import negotiator.issue.IssueDiscrete;
10import negotiator.issue.IssueReal;
11import negotiator.utility.AdditiveUtilitySpace;
12import negotiator.utility.EVALFUNCTYPE;
13import negotiator.utility.EvaluatorDiscrete;
14import negotiator.utility.EvaluatorReal;
15
16
17
18
19
20
21public class BayesianOpponentModel
22 extends OpponentModel
23{
24 private AdditiveUtilitySpace fUS;
25 private WeightHypothesis[] fWeightHyps;
26 private ArrayList<ArrayList<EvaluatorHypothesis>> fEvaluatorHyps;
27 private ArrayList<EvaluatorHypothesis[]> fEvalHyps;
28 private ArrayList<UtilitySpaceHypothesis> fUSHyps;
29 private boolean fUseMostProbableHypsOnly = false;
30 private ArrayList<UtilitySpaceHypothesis> fMostProbableUSHyps;
31 private double fPreviousBidUtility;
32 private double EXPECTED_CONCESSION_STEP = 0.035D;
33 private double SIGMA = 0.25D;
34 private boolean USE_DOMAIN_KNOWLEDGE = false;
35 List<Issue> issues;
36
37 public BayesianOpponentModel(AdditiveUtilitySpace pUtilitySpace) {
38 if (pUtilitySpace == null)
39 throw new NullPointerException("pUtilitySpace=null");
40 fDomain = pUtilitySpace.getDomain();
41 fPreviousBidUtility = 1.0D;
42 fUS = pUtilitySpace;
43 fBiddingHistory = new ArrayList();
44 issues = fDomain.getIssues();
45 int lNumberOfHyps = factorial(issues.size());
46 fWeightHyps = new WeightHypothesis[lNumberOfHyps];
47
48 int index = 0;
49 double[] P = new double[issues.size()];
50
51 for (int i = 0; i < issues.size(); i++) {
52 P[i] =
53 ((i + 1) / (issues.size() * (fDomain.getIssues().size() + 1) / 2.0D));
54 }
55 antilex(new Integer(index), fWeightHyps, P,
56 fDomain.getIssues().size() - 1);
57
58
59
60
61
62
63
64 for (int i = 0; i < fWeightHyps.length; i++) {
65 fWeightHyps[i].setProbability(1.0D / fWeightHyps.length);
66 }
67
68 fEvaluatorHyps = new ArrayList();
69 int lTotalTriangularFns = 1;
70 for (int i = 0; i < fUS.getNrOfEvaluators(); i++) {
71 ArrayList<EvaluatorHypothesis> lEvalHyps = new ArrayList();
72 lEvalHyps = new ArrayList();
73 fEvaluatorHyps.add(lEvalHyps);
74 switch (fUS.getEvaluator(((Issue)issues.get(i)).getNumber()).getType())
75 {
76
77 case OBJECTIVE:
78 IssueReal lIssue = (IssueReal)fDomain.getIssues().get(i);
79 EvaluatorReal lHypEval = new EvaluatorReal();
80
81 if (USE_DOMAIN_KNOWLEDGE)
82 {
83 lHypEval = new EvaluatorReal();
84 lHypEval.setUpperBound(lIssue.getUpperBound());
85 lHypEval.setLowerBound(lIssue.getLowerBound());
86 lHypEval.setType(EVALFUNCTYPE.LINEAR);
87 lHypEval.addParam(1,
88 1.0D / (lHypEval.getUpperBound() - lHypEval
89 .getLowerBound()));
90 lHypEval.addParam(
91 0,
92 -lHypEval.getLowerBound() / (
93 lHypEval.getUpperBound() - lHypEval
94 .getLowerBound()));
95 EvaluatorHypothesis lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
96 lEvaluatorHypothesis.setDesc("uphill");
97 lEvalHyps.add(lEvaluatorHypothesis);
98 }
99 else
100 {
101 lHypEval = new EvaluatorReal();
102 lHypEval.setUpperBound(lIssue.getUpperBound());
103 lHypEval.setLowerBound(lIssue.getLowerBound());
104 lHypEval.setType(EVALFUNCTYPE.LINEAR);
105 lHypEval.addParam(1,
106 1.0D / (lHypEval.getUpperBound() - lHypEval
107 .getLowerBound()));
108 lHypEval.addParam(
109 0,
110 -lHypEval.getLowerBound() / (
111 lHypEval.getUpperBound() - lHypEval
112 .getLowerBound()));
113 EvaluatorHypothesis lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
114 lEvaluatorHypothesis.setDesc("uphill");
115 lEvalHyps.add(lEvaluatorHypothesis);
116
117 lHypEval = new EvaluatorReal();
118 lHypEval.setUpperBound(lIssue.getUpperBound());
119 lHypEval.setLowerBound(lIssue.getLowerBound());
120 lHypEval.setType(EVALFUNCTYPE.LINEAR);
121 lHypEval.addParam(
122 1,
123 -1.0D / (
124 lHypEval.getUpperBound() - lHypEval
125 .getLowerBound()));
126 lHypEval.addParam(
127 0,
128 1.0D +
129 lHypEval.getLowerBound() / (
130 lHypEval.getUpperBound() - lHypEval
131 .getLowerBound()));
132 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
133 lEvalHyps.add(lEvaluatorHypothesis);
134 lEvaluatorHypothesis.setDesc("downhill");
135
136 for (int k = 1; k <= lTotalTriangularFns; k++)
137 {
138 lHypEval = new EvaluatorReal();
139 lHypEval.setUpperBound(lIssue.getUpperBound());
140 lHypEval.setLowerBound(lIssue.getLowerBound());
141 lHypEval.setType(EVALFUNCTYPE.TRIANGULAR);
142 lHypEval.addParam(0, lHypEval.getLowerBound());
143 lHypEval.addParam(1, lHypEval.getUpperBound());
144 lHypEval.addParam(
145 2,
146 lHypEval.getLowerBound() +
147 k * (
148 lHypEval.getUpperBound() - lHypEval
149 .getLowerBound()) / (
150 lTotalTriangularFns + 1));
151 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
152 lEvaluatorHypothesis.setProbability(0.3333333333333333D);
153 lEvalHyps.add(lEvaluatorHypothesis);
154 lEvaluatorHypothesis.setDesc("triangular");
155 }
156 }
157 for (int k = 0; k < lEvalHyps.size(); k++) {
158 ((EvaluatorHypothesis)lEvalHyps.get(k)).setProbability(
159 1.0D / lEvalHyps.size());
160 }
161
162 break;
163
164 case DISCRETE:
165 lEvalHyps = new ArrayList();
166 fEvaluatorHyps.add(lEvalHyps);
167
168 IssueDiscrete lDiscIssue =
169 (IssueDiscrete)fDomain.getIssues().get(i);
170 if (USE_DOMAIN_KNOWLEDGE)
171 {
172 EvaluatorDiscrete lDiscreteEval = new EvaluatorDiscrete();
173 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
174 lDiscreteEval.addEvaluation(lDiscIssue.getValue(j),
175 Integer.valueOf(1000 * j));
176 EvaluatorHypothesis lEvaluatorHypothesis = new EvaluatorHypothesis(
177 lDiscreteEval);
178 lEvaluatorHypothesis.setDesc("uphill");
179 lEvalHyps.add(lEvaluatorHypothesis);
180 }
181 else
182 {
183 EvaluatorDiscrete lDiscreteEval = new EvaluatorDiscrete();
184 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
185 lDiscreteEval.addEvaluation(lDiscIssue.getValue(j),
186 Integer.valueOf(1000 * j + 1));
187 EvaluatorHypothesis lEvaluatorHypothesis = new EvaluatorHypothesis(
188 lDiscreteEval);
189 lEvaluatorHypothesis.setDesc("uphill");
190 lEvalHyps.add(lEvaluatorHypothesis);
191
192 lDiscreteEval = new EvaluatorDiscrete();
193 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
194 {
195 lDiscreteEval.addEvaluation(lDiscIssue.getValue(j),
196 Integer.valueOf(1000 * (lDiscIssue.getNumberOfValues() -
197 j - 1) + 1)); }
198 lEvaluatorHypothesis = new EvaluatorHypothesis(
199 lDiscreteEval);
200 lEvalHyps.add(lEvaluatorHypothesis);
201 lEvaluatorHypothesis.setDesc("downhill");
202
203 lDiscreteEval = new EvaluatorDiscrete();
204 int halfway = lDiscIssue.getNumberOfValues() / 2;
205 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++) {
206 if (j < halfway) {
207 lDiscreteEval.addEvaluation(lDiscIssue.getValue(j),
208 Integer.valueOf(1000 * j + 1));
209 }
210 else
211 {
212 lDiscreteEval.addEvaluation(
213 lDiscIssue.getValue(j),
214 Integer.valueOf(1000 * (lDiscIssue
215 .getNumberOfValues() - j - 1) + 1)); }
216 }
217 lEvaluatorHypothesis = new EvaluatorHypothesis(
218 lDiscreteEval);
219 lEvalHyps.add(lEvaluatorHypothesis);
220 lEvaluatorHypothesis.setDesc("triangular");
221 }
222
223
224
225 break;
226 }
227
228 }
229
230
231 buildEvaluationHyps();
232
233 buildUniformHyps();
234 }
235
236 private void buildUniformHyps() {
237 fUSHyps = new ArrayList();
238 for (int i = 0; i < fWeightHyps.length; i++)
239 {
240
241 for (int j = 0; j < fEvalHyps.size(); j++) {
242 UtilitySpaceHypothesis lUSHyp = new UtilitySpaceHypothesis(
243 fDomain, fUS, fWeightHyps[i], (EvaluatorHypothesis[])fEvalHyps.get(j));
244 fUSHyps.add(lUSHyp);
245 }
246 }
247
248 for (int i = 0; i < fUSHyps.size(); i++) {
249 ((UtilitySpaceHypothesis)fUSHyps.get(i)).setProbability(1.0D / fUSHyps.size());
250 }
251 }
252
253 private void reverse(double[] P, int m) {
254 int i = 0;int j = m;
255 while (i < j)
256 {
257 double lTmp = P[i];
258 P[i] = P[j];
259 P[j] = lTmp;
260 i++;
261 j--;
262 }
263 }
264
265 private Integer antilex(Integer index, WeightHypothesis[] hyps, double[] P, int m)
266 {
267 if (m == 0) {
268 WeightHypothesis lWH = new WeightHypothesis(fDomain);
269 for (int i = 0; i < P.length; i++)
270 lWH.setWeight(i, P[i]);
271 hyps[index.intValue()] = lWH;
272 index = Integer.valueOf(index.intValue() + 1);
273 } else {
274 for (int i = 0; i <= m; i++) {
275 index = antilex(index, hyps, P, m - 1);
276 if (i < m)
277 {
278 double lTmp = P[i];
279 P[i] = P[m];
280 P[m] = lTmp;
281 reverse(P, m - 1);
282 }
283 }
284 }
285 return index;
286 }
287
288
289 private double conditionalDistribution(double pUtility, double pPreviousBidUtility)
290 {
291 if (pPreviousBidUtility < pUtility) {
292 return 0.0D;
293 }
294
295 double x = (pPreviousBidUtility - pUtility) / pPreviousBidUtility;
296 double lResult = 1.0D / (SIGMA * Math.sqrt(6.283185307179586D)) *
297 Math.exp(-(x * x) / (2.0D * SIGMA * SIGMA));
298 return lResult;
299 }
300
301 public void updateBeliefs(Bid pBid) throws Exception
302 {
303 fBiddingHistory.add(pBid);
304 if (haveSeenBefore(pBid)) {
305 return;
306 }
307 double lFullProb = 0.0D;
308 double lMaxProb = 0.0D;
309 for (int i = 0; i < fUSHyps.size(); i++) {
310 UtilitySpaceHypothesis hyp = (UtilitySpaceHypothesis)fUSHyps.get(i);
311 double condDistrib = hyp.getProbability() *
312 conditionalDistribution(((UtilitySpaceHypothesis)fUSHyps.get(i)).getUtility(pBid),
313 fPreviousBidUtility);
314 lFullProb += condDistrib;
315 if (condDistrib > lMaxProb)
316 lMaxProb = condDistrib;
317 hyp.setProbability(condDistrib);
318 }
319 if (fUseMostProbableHypsOnly) {
320 fMostProbableUSHyps = new ArrayList();
321 }
322 double lMostProbableHypFullProb = 0.0D;
323 for (int i = 0; i < fUSHyps.size(); i++) {
324 UtilitySpaceHypothesis hyp = (UtilitySpaceHypothesis)fUSHyps.get(i);
325 double normalizedProbability = hyp.getProbability() / lFullProb;
326 hyp.setProbability(normalizedProbability);
327 if ((fUseMostProbableHypsOnly) &&
328 (normalizedProbability > lMaxProb * 0.99D / lFullProb)) {
329 fMostProbableUSHyps.add(hyp);
330 lMostProbableHypFullProb += normalizedProbability;
331 }
332 }
333 if (fUseMostProbableHypsOnly) {
334 for (int i = 0; i < fMostProbableUSHyps.size(); i++) {
335 UtilitySpaceHypothesis hyp = (UtilitySpaceHypothesis)fMostProbableUSHyps.get(i);
336 double normalizedProbability = hyp.getProbability() /
337 lMostProbableHypFullProb;
338 hyp.setProbability(normalizedProbability);
339 }
340 }
341
342
343
344
345
346 System.out.println("BA: Using " +
347 String.valueOf(fMostProbableUSHyps.size()) + " out of " +
348 String.valueOf(fUSHyps.size()) + "hyps");
349 System.out.println(getMaxHyp().toString());
350
351
352 fPreviousBidUtility -= EXPECTED_CONCESSION_STEP;
353 }
354
355
356
357 private void buildEvaluationHypsRecursive(ArrayList<EvaluatorHypothesis[]> pHyps, EvaluatorHypothesis[] pEval, int m)
358 {
359 if (m == 0) {
360 ArrayList<EvaluatorHypothesis> lEvalHyps = (ArrayList)fEvaluatorHyps.get(fUS
361 .getNrOfEvaluators() - 1);
362 for (int i = 0; i < lEvalHyps.size(); i++) {
363 pEval[(fUS.getNrOfEvaluators() - 1)] = ((EvaluatorHypothesis)lEvalHyps.get(i));
364 EvaluatorHypothesis[] lTmp = new EvaluatorHypothesis[fUS
365 .getNrOfEvaluators()];
366
367 for (int j = 0; j < lTmp.length; j++)
368 lTmp[j] = pEval[j];
369 pHyps.add(lTmp);
370 }
371 } else {
372 ArrayList<EvaluatorHypothesis> lEvalHyps = (ArrayList)fEvaluatorHyps.get(fUS
373 .getNrOfEvaluators() - m - 1);
374 for (int i = 0; i < lEvalHyps.size(); i++) {
375 pEval[(fUS.getNrOfEvaluators() - m - 1)] = ((EvaluatorHypothesis)lEvalHyps.get(i));
376 buildEvaluationHypsRecursive(pHyps, pEval, m - 1);
377 }
378 }
379 }
380
381 private void buildEvaluationHyps() {
382 fEvalHyps = new ArrayList();
383 EvaluatorHypothesis[] lTmp = new EvaluatorHypothesis[fUS
384 .getNrOfEvaluators()];
385 buildEvaluationHypsRecursive(fEvalHyps, lTmp,
386 fUS.getNrOfEvaluators() - 1);
387 }
388
389 public double getExpectedUtility(Bid pBid) throws Exception {
390 double lExpectedUtility = 0.0D;
391 if ((fUseMostProbableHypsOnly) && (fMostProbableUSHyps != null)) {
392 for (int i = 0; i < fMostProbableUSHyps.size(); i++) {
393 UtilitySpaceHypothesis lUSHyp = (UtilitySpaceHypothesis)fMostProbableUSHyps.get(i);
394 double p = lUSHyp.getProbability();
395 double u = lUSHyp.getUtility(pBid);
396 lExpectedUtility += p * u;
397 }
398 } else {
399 for (int i = 0; i < fUSHyps.size(); i++) {
400 UtilitySpaceHypothesis lUSHyp = (UtilitySpaceHypothesis)fUSHyps.get(i);
401 double p = lUSHyp.getProbability();
402 double u = lUSHyp.getUtility(pBid);
403 lExpectedUtility += p * u;
404 }
405 }
406 return lExpectedUtility;
407 }
408
409 public double getExpectedWeight(int pIssueNumber) {
410 double lExpectedWeight = 0.0D;
411 for (int i = 0; i < fUSHyps.size(); i++) {
412 UtilitySpaceHypothesis lUSHyp = (UtilitySpaceHypothesis)fUSHyps.get(i);
413 double p = lUSHyp.getProbability();
414 double u = lUSHyp.getHeightHyp().getWeight(pIssueNumber);
415 lExpectedWeight += p * u;
416 }
417 return lExpectedWeight;
418 }
419
420 public double getNormalizedWeight(Issue i, int startingNumber) {
421 double sum = 0.0D;
422 for (Issue issue : fDomain.getIssues()) {
423 sum += getExpectedWeight(issue.getNumber() - startingNumber);
424 }
425 return getExpectedWeight(i.getNumber() - startingNumber) / sum;
426 }
427
428 private UtilitySpaceHypothesis getMaxHyp() {
429 UtilitySpaceHypothesis lHyp = (UtilitySpaceHypothesis)fUSHyps.get(0);
430 for (int i = 0; i < fUSHyps.size(); i++) {
431 if (lHyp.getProbability() < ((UtilitySpaceHypothesis)fUSHyps.get(i)).getProbability())
432 lHyp = (UtilitySpaceHypothesis)fUSHyps.get(i);
433 }
434 return lHyp;
435 }
436
437
438
439
440
441
442
443
444
445
446
447
448 private int factorial(int n)
449 {
450 if (n <= 1) {
451 return 1;
452 }
453 return n * factorial(n - 1);
454 }
455
456 public void setMostProbableUSHypsOnly(boolean value) {
457 fUseMostProbableHypsOnly = value;
458 }
459}
Note: See TracBrowser for help on using the repository browser.