source: src/main/java/agents/anac/y2010/AgentFSEGA/MyBayesianOpponentModel.java

Last change on this file was 127, checked in by Wouter Pasman, 6 years ago

#41 ROLL BACK of rev.126 . So this version is equal to rev. 125

File size: 13.6 KB
Line 
1package agents.anac.y2010.AgentFSEGA;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.List;
6
7import genius.core.Bid;
8import genius.core.issue.Issue;
9import genius.core.issue.IssueDiscrete;
10import genius.core.issue.IssueReal;
11import genius.core.utility.AdditiveUtilitySpace;
12import genius.core.utility.EVALFUNCTYPE;
13import genius.core.utility.EvaluatorDiscrete;
14import genius.core.utility.EvaluatorReal;
15
16public class MyBayesianOpponentModel extends OpponentModel {
17 private AdditiveUtilitySpace uUS;
18 private ArrayList<UtilitySpaceHypothesis> uUSHypothesis;
19 private double previousBidUtility;
20 private double SIGMA = 0.25;
21 private double CONCESSION_STRATEGY = 0.035; // estimated opponent concession
22 // strategy
23
24 // scalable
25 private boolean bUseMostProb = true;
26 private ArrayList<UtilitySpaceHypothesis> mostProbHyps;
27
28 public MyBayesianOpponentModel(AdditiveUtilitySpace pUS) {
29 if (pUS == null)
30 throw new NullPointerException(
31 "MyBayesianOpponentModel: utility space = null");
32 uUS = pUS;
33
34 previousBidUtility = 1;
35 dDomain = pUS.getDomain();
36 // aBiddingHistory = new ArrayList<Bid>();
37
38 List<Issue> issues = dDomain.getIssues();
39 ArrayList<ArrayList<EvaluatorHypothesis>> aaEvaluatorHypothesis = new ArrayList<ArrayList<EvaluatorHypothesis>>();
40
41 int numberOfIssues = issues.size();
42
43 // generate weight hypothesis ==> <count of issues>! hypothesis
44 WeightHypothesis[] weightHypothesis = new WeightHypothesis[factorial(numberOfIssues)];
45
46 // createFrom all permutations
47 double[] P = new double[numberOfIssues];
48
49 // normalize weights
50 for (int i = 0; i < numberOfIssues; i++)
51 P[i] = 2.0 * (i + 1)
52 / (double) (numberOfIssues * (numberOfIssues + 1));
53 weightPermutations(0, weightHypothesis, P, numberOfIssues - 1);
54
55 // add initial probabilities
56 for (int i = 0; i < weightHypothesis.length; i++)
57 weightHypothesis[i].setProbability(1.0 / weightHypothesis.length);
58
59 // generate evaluator hypotheses
60 for (int i = 0; i < numberOfIssues; i++) {
61 ArrayList<EvaluatorHypothesis> lEvalHyps;
62 switch (uUS.getEvaluator(issues.get(i).getNumber()).getType()) {
63 case DISCRETE:
64 lEvalHyps = new ArrayList<EvaluatorHypothesis>();
65 aaEvaluatorHypothesis.add(lEvalHyps);
66 IssueDiscrete lDiscIssue = (IssueDiscrete) (dDomain.getIssues()
67 .get(i));
68
69 // uphill
70 EvaluatorDiscrete lDiscreteEvaluator = new EvaluatorDiscrete();
71 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
72 lDiscreteEvaluator.addEvaluation(lDiscIssue.getValue(j),
73 1000 * j + 1);
74 EvaluatorHypothesis lEvaluatorHypothesis = new EvaluatorHypothesis(
75 lDiscreteEvaluator, "uphill");
76
77 lEvalHyps.add(lEvaluatorHypothesis);
78
79 // downhill
80 lDiscreteEvaluator = new EvaluatorDiscrete();
81 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
82 lDiscreteEvaluator
83 .addEvaluation(
84 lDiscIssue.getValue(j),
85 1000 * (lDiscIssue.getNumberOfValues() - j - 1) + 1);
86 lEvaluatorHypothesis = new EvaluatorHypothesis(
87 lDiscreteEvaluator, "downhill");
88
89 lEvalHyps.add(lEvaluatorHypothesis);
90
91 // triangular
92 lDiscreteEvaluator = new EvaluatorDiscrete();
93 int halfway = lDiscIssue.getNumberOfValues() / 2;
94 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
95 if (j < halfway)
96 lDiscreteEvaluator.addEvaluation(
97 lDiscIssue.getValue(j), 1000 * j + 1);
98 else
99 lDiscreteEvaluator
100 .addEvaluation(lDiscIssue.getValue(j),
101 1000 * (lDiscIssue.getNumberOfValues()
102 - j - 1) + 1);
103 lEvaluatorHypothesis = new EvaluatorHypothesis(
104 lDiscreteEvaluator, "triangular");
105
106 lEvalHyps.add(lEvaluatorHypothesis);
107 break;
108
109 // Eval hypothesis for real attributes
110 case REAL:
111 lEvalHyps = new ArrayList<EvaluatorHypothesis>();
112 aaEvaluatorHypothesis.add(lEvalHyps);
113 IssueReal lRealIssue = (IssueReal) (dDomain.getIssues().get(i)); // Laptop
114 // |
115 // Harddisk
116 // |
117 // Monitor
118
119 // uphill
120 EvaluatorReal lRealEvaluator = new EvaluatorReal();
121 lRealEvaluator.setLowerBound(lRealIssue.getLowerBound());
122 lRealEvaluator.setUpperBound(lRealIssue.getUpperBound());
123 lRealEvaluator.setType(EVALFUNCTYPE.LINEAR);
124 lRealEvaluator.addParam(1, 1.0 / (lRealEvaluator
125 .getUpperBound() - lRealEvaluator.getLowerBound()));
126 lRealEvaluator
127 .addParam(
128 0,
129 -lRealEvaluator.getLowerBound()
130 / (lRealEvaluator.getUpperBound() - lRealEvaluator
131 .getLowerBound()));
132 lEvaluatorHypothesis = new EvaluatorHypothesis(lRealEvaluator,
133 "uphill");
134 lEvalHyps.add(lEvaluatorHypothesis);
135
136 // downhill
137 lRealEvaluator = new EvaluatorReal();
138 lRealEvaluator.setLowerBound(lRealIssue.getLowerBound());
139 lRealEvaluator.setUpperBound(lRealIssue.getUpperBound());
140 lRealEvaluator.setType(EVALFUNCTYPE.LINEAR);
141 lRealEvaluator
142 .addParam(
143 1,
144 -1.0
145 / (lRealEvaluator.getUpperBound() - lRealEvaluator
146 .getLowerBound()));
147 lRealEvaluator
148 .addParam(
149 0,
150 1.0
151 + lRealEvaluator.getLowerBound()
152 / (lRealEvaluator.getUpperBound() - lRealEvaluator
153 .getLowerBound()));
154 lEvaluatorHypothesis = new EvaluatorHypothesis(lRealEvaluator,
155 "downhill");
156 lEvalHyps.add(lEvaluatorHypothesis);
157
158 // triangular
159 int lTotalTriangularFns = 1;
160 for (int k = 1; k <= lTotalTriangularFns; k++) {
161 lRealEvaluator = new EvaluatorReal();
162 lRealEvaluator.setLowerBound(lRealIssue.getLowerBound());
163 lRealEvaluator.setUpperBound(lRealIssue.getUpperBound());
164 lRealEvaluator.setType(EVALFUNCTYPE.TRIANGULAR);
165 lRealEvaluator.addParam(0, lRealEvaluator.getLowerBound());
166 lRealEvaluator.addParam(1, lRealEvaluator.getUpperBound());
167 lRealEvaluator
168 .addParam(
169 2,
170 lRealEvaluator.getLowerBound()
171 + (double) k
172 * (lRealEvaluator.getUpperBound() - lRealEvaluator
173 .getLowerBound())
174 / (lTotalTriangularFns + 1));
175 lEvaluatorHypothesis = new EvaluatorHypothesis(
176 lRealEvaluator, "triangular");
177 lEvaluatorHypothesis.setProbability((double) 1 / 3);
178 lEvalHyps.add(lEvaluatorHypothesis);
179 }
180 for (int k = 0; k < lEvalHyps.size(); k++) {
181 lEvalHyps.get(k).setProbability(
182 (double) 1 / lEvalHyps.size());
183 }
184
185 break;
186
187 default:
188 throw new NullPointerException(
189 "Evaluator type not implemented: eval type - "
190 + uUS.getEvaluator(issues.get(i).getNumber())
191 .getType());
192 }
193 }
194
195 // build evaluation hypothesis
196 ArrayList<EvaluatorHypothesis[]> evalHypothesis = new ArrayList<EvaluatorHypothesis[]>();
197 EvaluatorHypothesis[] ehTmp = new EvaluatorHypothesis[uUS
198 .getNrOfEvaluators()];
199
200 buildEvaluationHypothesis(evalHypothesis, ehTmp,
201 uUS.getNrOfEvaluators() - 1, aaEvaluatorHypothesis);
202
203 // build user space hypothesis
204 buildUtilitySpaceHypothesis(weightHypothesis, evalHypothesis);
205 }
206
207 private void buildEvaluationHypothesis(
208 ArrayList<EvaluatorHypothesis[]> pHyps,
209 EvaluatorHypothesis[] pEval, int m,
210 ArrayList<ArrayList<EvaluatorHypothesis>> paaEval) {
211 if (m == 0) {
212 ArrayList<EvaluatorHypothesis> lEvalHyps = paaEval.get(uUS
213 .getNrOfEvaluators() - 1);
214 for (int i = 0; i < lEvalHyps.size(); i++) {
215 pEval[uUS.getNrOfEvaluators() - 1] = lEvalHyps.get(i);
216 EvaluatorHypothesis[] lTmp = new EvaluatorHypothesis[uUS
217 .getNrOfEvaluators()];
218 // copy to temporary array
219 for (int j = 0; j < lTmp.length; j++)
220 lTmp[j] = pEval[j];
221 pHyps.add(lTmp);
222 }
223 } else {
224 ArrayList<EvaluatorHypothesis> lEvalHyps = paaEval.get(uUS
225 .getNrOfEvaluators() - m - 1);
226 for (int i = 0; i < lEvalHyps.size(); i++) {
227 pEval[uUS.getNrOfEvaluators() - m - 1] = lEvalHyps.get(i);
228 buildEvaluationHypothesis(pHyps, pEval, m - 1, paaEval);
229 }
230 }
231 }
232
233 private void buildUtilitySpaceHypothesis(
234 WeightHypothesis[] pWeightHypothesis,
235 ArrayList<EvaluatorHypothesis[]> pEvalHypothesis) {
236 uUSHypothesis = new ArrayList<UtilitySpaceHypothesis>();
237 for (int i = 0; i < pWeightHypothesis.length; i++) {
238 for (int j = 0; j < pEvalHypothesis.size(); j++) {
239 UtilitySpaceHypothesis lUSHyp = new UtilitySpaceHypothesis(
240 dDomain, uUS, pWeightHypothesis[i],
241 pEvalHypothesis.get(j));
242 uUSHypothesis.add(lUSHyp);
243 }
244 }
245
246 // set initial probability for all hyps
247 for (int i = 0; i < uUSHypothesis.size(); i++) {
248 uUSHypothesis.get(i).setProbability(
249 1.0 / (double) (uUSHypothesis.size()));
250 }
251 }
252
253 private Integer weightPermutations(Integer index, WeightHypothesis[] hyps,
254 double[] P, int m) {
255 if (m == 0) {
256 WeightHypothesis lWH = new WeightHypothesis(dDomain);
257 for (int i = 0; i < P.length; i++)
258 lWH.setWeight(i, P[i]);
259 hyps[index] = lWH;
260 index++;
261 } else {
262 for (int i = 0; i <= m; i++) {
263 index = weightPermutations(index, hyps, P, m - 1);
264 if (i < m) {
265 // swap elements i and m
266 double tmp = P[i];
267 P[i] = P[m];
268 P[m] = tmp;
269 reverse(P, m - 1);
270 } // if
271 }
272 }
273 return index;
274 }
275
276 private void reverse(double[] array, int size) {
277 int i = 0, j = size;
278 while (i < j) {
279 // swap i <-> j
280 double tmp = array[i];
281 array[i] = array[j];
282 array[j] = tmp;
283 i++;
284 j--;
285 }
286 }
287
288 private int factorial(int n) {
289 int result = 1;
290 for (; n > 1; n--) {
291 result *= n;
292 }
293 return result;
294 }
295
296 public void updateBeliefs(Bid pBid) throws Exception {
297 // calculate probability for the given bid
298 double lProbSum = 0;
299 double lMaxProb = 0;
300 for (int i = 0; i < uUSHypothesis.size(); i++) {
301 UtilitySpaceHypothesis hyp = uUSHypothesis.get(i);
302 double condDistrib = hyp.getProbability()
303 * conditionalDistribution(
304 uUSHypothesis.get(i).getUtility(pBid),
305 previousBidUtility);
306 lProbSum += condDistrib;
307 if (condDistrib > lMaxProb)
308 lMaxProb = condDistrib;
309 hyp.setProbability(condDistrib);
310 }
311
312 if (bUseMostProb)
313 mostProbHyps = new ArrayList<UtilitySpaceHypothesis>();
314
315 double mostProbHypSum = 0;
316
317 // receiveMessage the weights hyps and evaluators hyps
318 for (int i = 0; i < uUSHypothesis.size(); i++) {
319 UtilitySpaceHypothesis hyp = uUSHypothesis.get(i);
320 double normalizedProbability = hyp.getProbability() / lProbSum;
321
322 if (bUseMostProb)
323 if (normalizedProbability > lMaxProb * 0.95 / lProbSum) {
324 mostProbHyps.add(hyp);
325 mostProbHypSum += normalizedProbability;
326 }
327
328 // exclude if probability is 0
329 if (normalizedProbability > 0)
330 hyp.setProbability(normalizedProbability);
331 else {
332 uUSHypothesis.remove(i);
333 }
334 // --- end exclude hyps with prob. around 0
335 }
336
337 // normalize most probable hypothesis
338 if (bUseMostProb) {
339 for (int i = 0; i < mostProbHyps.size(); i++) {
340 UtilitySpaceHypothesis tmpHyp = mostProbHyps.get(i);
341 double normalizedProbability = tmpHyp.getProbability()
342 / mostProbHypSum;
343 tmpHyp.setProbability(normalizedProbability);
344 }
345 }
346
347 // calculate utility of the next partner's bid according to the
348 // concession functions
349 previousBidUtility = previousBidUtility - CONCESSION_STRATEGY;
350
351 // sort hypotesis by probability
352 Collections.sort(uUSHypothesis);
353
354 // exclude bids with sum under 0.95
355 int cutPoint = Integer.MAX_VALUE;
356
357 double cummulativeSum = 0;
358
359 // get cutPoint
360 // and cumulative sum for normalization
361 for (int i = 0; i < uUSHypothesis.size(); i++) {
362 cummulativeSum += uUSHypothesis.get(i).getProbability();
363 if (cummulativeSum > 0.95) {
364 cutPoint = i;
365 break;
366 }
367 }
368 // eliminate from cutPoint to last item
369 if (cutPoint != Integer.MAX_VALUE) {
370 for (int i = uUSHypothesis.size() - 1; i >= cutPoint; i--) {
371 uUSHypothesis.remove(i);
372 }
373 }
374
375 // normalize remained hypothesis probability
376 for (int i = 0; i < uUSHypothesis.size(); i++) {
377 UtilitySpaceHypothesis currentHyp = uUSHypothesis.get(i);
378 double newProbability = currentHyp.getProbability()
379 / cummulativeSum;
380 currentHyp.setProbability(newProbability);
381 }
382 }
383
384 private double conditionalDistribution(double pUtility,
385 double pPreviousBidUtility) {
386 if (pPreviousBidUtility < pUtility)
387 return 0;
388 else {
389 double x = (pPreviousBidUtility - pUtility) / pPreviousBidUtility;
390 double distribution = (1 / (SIGMA * Math.sqrt(2 * Math.PI)) * Math
391 .exp(-(x * x) / (2 * SIGMA * SIGMA)));
392 return distribution;
393 }
394 }
395
396 public double getExpectedUtility(Bid pBid) throws Exception {
397 double lExpectedUtility = 0;
398
399 if (bUseMostProb && (mostProbHyps != null)) {
400
401 for (int i = 0; i < mostProbHyps.size(); i++) {
402 UtilitySpaceHypothesis tmpUSHypothesis = mostProbHyps.get(i);
403 double p = tmpUSHypothesis.getProbability();
404 double u = tmpUSHypothesis.getUtility(pBid);
405 lExpectedUtility += p * u;
406 }
407 } else {
408 for (int i = 0; i < uUSHypothesis.size(); i++) {
409 UtilitySpaceHypothesis tmpUSHypothesis = uUSHypothesis.get(i);
410 double p = tmpUSHypothesis.getProbability();
411 double u = tmpUSHypothesis.getUtility(pBid);
412 lExpectedUtility += p * u;
413 }
414 }
415
416 return lExpectedUtility;
417 }
418
419 public double getExpectedWeight(int pIssueNumber) {
420 double lExpectedWeight = 0;
421 for (int i = 0; i < uUSHypothesis.size(); i++) {
422 UtilitySpaceHypothesis lUSHyp = uUSHypothesis.get(i);
423 double p = lUSHyp.getProbability();
424 double u = lUSHyp.getHeightHyp().getWeight(pIssueNumber);
425 lExpectedWeight += p * u;
426 }
427 return lExpectedWeight;
428 }
429}
Note: See TracBrowser for help on using the repository browser.