source: src/main/java/agents/anac/y2017/tucagent/BayesianOpponentModel.java@ 316

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

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