source: src/main/java/agents/anac/y2010/Southampton/analysis/BidSpace.java

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

Initial import : Genius 9.0.0
File size: 31.6 KB
Line 
1package agents.anac.y2010.Southampton.analysis;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.List;
7
8import agents.anac.y2010.Southampton.utils.OpponentModel;
9import agents.anac.y2010.Southampton.utils.Pair;
10import agents.anac.y2010.Southampton.utils.concession.ConcessionUtils;
11import genius.core.Bid;
12import genius.core.Domain;
13import genius.core.issue.ISSUETYPE;
14import genius.core.issue.Issue;
15import genius.core.issue.IssueDiscrete;
16import genius.core.issue.Value;
17import genius.core.issue.ValueDiscrete;
18import genius.core.issue.ValueInteger;
19import genius.core.issue.ValueReal;
20import genius.core.utility.AdditiveUtilitySpace;
21import genius.core.utility.EvaluatorDiscrete;
22import genius.core.utility.EvaluatorInteger;
23import genius.core.utility.EvaluatorReal;
24
25public class BidSpace {
26
27 private final boolean TEST_EQUIVALENCE = false;
28
29 /**
30 * @return the continuousWeights
31 */
32 public ArrayList<Double> getContinuousWeights() {
33 return continuousWeights;
34 }
35
36 /**
37 * @return the count of discreteCombinations
38 */
39 public int getDiscreteCombinationsCount() {
40 return discreteCombinations.length;
41 }
42
43 /**
44 * @return the continuousWeightsZero
45 */
46 public boolean isContinuousWeightsZero() {
47 return continuousWeightsZero;
48 }
49
50 /**
51 * @return the discreteWeights
52 */
53 public ArrayList<Double> getDiscreteWeights() {
54 return discreteWeights;
55 }
56
57 public class EvaluatedDiscreteCombination implements
58 Comparable<EvaluatedDiscreteCombination> {
59
60 /**
61 * @return the discreteCombination
62 */
63 public ValueDiscrete[] getDiscreteCombination() {
64 return discreteCombination;
65 }
66
67 private ValueDiscrete[] discreteCombination;
68 private double jointUtility;
69
70 public EvaluatedDiscreteCombination(
71 ValueDiscrete[] discreteCombination, double jointUtility) {
72 this.discreteCombination = discreteCombination;
73 this.jointUtility = jointUtility;
74 }
75
76 public int compareTo(EvaluatedDiscreteCombination o) {
77 return this.jointUtility < o.jointUtility ? -1
78 : (this.jointUtility == o.jointUtility ? 0 : 1);
79 }
80 }
81
82 private Domain domain;
83
84 ArrayList<Double> continuousWeights;
85 double[] continuousPreference;
86 double[] range;
87 double[] offset;
88 ArrayList<ContinuousSection> continuousSections;
89 ValueDiscrete[][] discreteCombinations;
90 ISSUETYPE[] issueTypes;
91 List<Issue> issues;
92
93 ArrayList<EvaluatorDiscrete> discreteEvaluators;
94 ArrayList<EvaluatorReal> realEvaluators;
95 ArrayList<EvaluatorInteger> integerEvaluators;
96
97 private boolean continuousWeightsZero;
98
99 private ArrayList<HashMap<ValueDiscrete, Double>> discreteEvaluationFunctions;
100 private ArrayList<Double> discreteWeights;
101
102 private double discountFactor;
103
104 /**
105 * Build the bid space based on a utility space.
106 *
107 * @param space
108 * the utility space.
109 * @throws Exception
110 */
111 public BidSpace(AdditiveUtilitySpace space) throws Exception {
112
113 domain = space.getDomain();
114
115 discountFactor = space.getDiscountFactor();
116 if (!space.isDiscounted()) {
117 discountFactor = 0.0; // in 2011 no discount had value 0.0 instead
118 // of 1.0
119 }
120
121 issues = domain.getIssues();
122 double[] weights = new double[issues.size()];
123 issueTypes = new ISSUETYPE[issues.size()];
124
125 discreteEvaluationFunctions = new ArrayList<HashMap<ValueDiscrete, Double>>();
126 discreteWeights = new ArrayList<Double>();
127
128 ArrayList<ContinuousEvaluationFunction> continuousEvaluationFunctions = new ArrayList<ContinuousEvaluationFunction>();
129 continuousWeights = new ArrayList<Double>();
130 continuousWeightsZero = true;
131 ArrayList<Double> tmpContinuousPreference = new ArrayList<Double>();
132
133 ArrayList<Double> tmpRange = new ArrayList<Double>();
134 ArrayList<Double> tmpOffset = new ArrayList<Double>();
135
136 realEvaluators = new ArrayList<EvaluatorReal>();
137 integerEvaluators = new ArrayList<EvaluatorInteger>();
138 discreteEvaluators = new ArrayList<EvaluatorDiscrete>();
139
140 int i = 0;
141 for (Issue issue : issues) {
142 weights[i] = space.getWeight(issue.getNumber());
143 issueTypes[i] = issue.getType();
144 switch (issueTypes[i]) {
145 case DISCRETE:
146 IssueDiscrete issueDiscrete = (IssueDiscrete) issue;
147 List<ValueDiscrete> values = issueDiscrete.getValues();
148 HashMap<ValueDiscrete, Double> evaluationFunction = new HashMap<ValueDiscrete, Double>();
149 EvaluatorDiscrete evaluatorDiscrete = (EvaluatorDiscrete) space
150 .getEvaluator(issue.getNumber());
151 discreteEvaluators.add(evaluatorDiscrete);
152 for (ValueDiscrete value : values) {
153 evaluationFunction.put(value,
154 evaluatorDiscrete.getEvaluation(value));
155 }
156 discreteEvaluationFunctions.add(evaluationFunction);
157 discreteWeights.add(space.getWeight(issue.getNumber()));
158 break;
159 case REAL:
160 EvaluatorReal evaluatorReal = (EvaluatorReal) space
161 .getEvaluator(issue.getNumber());
162 realEvaluators.add(evaluatorReal);
163
164 tmpRange.add(evaluatorReal.getUpperBound()
165 - evaluatorReal.getLowerBound());
166 tmpOffset.add(evaluatorReal.getLowerBound());
167
168 ArrayList<RealEvaluationSection> realSections = new ArrayList<RealEvaluationSection>();
169 switch (evaluatorReal.getFuncType()) {
170 case LINEAR: {
171 double lb = normalise(evaluatorReal.getLowerBound(),
172 evaluatorReal.getLowerBound(),
173 evaluatorReal.getUpperBound());
174 double ub = normalise(evaluatorReal.getUpperBound(),
175 evaluatorReal.getLowerBound(),
176 evaluatorReal.getUpperBound());
177 RealEvaluationSection res = new RealEvaluationSection(lb,
178 evaluatorReal.getEvaluation(evaluatorReal
179 .getLowerBound()), ub,
180 evaluatorReal.getEvaluation(evaluatorReal
181 .getUpperBound()));
182 realSections.add(res);
183 tmpContinuousPreference.add(res.getTopPoint());
184 break;
185 }
186 case TRIANGULAR: {
187 double lb = normalise(evaluatorReal.getLowerBound(),
188 evaluatorReal.getLowerBound(),
189 evaluatorReal.getUpperBound());
190 double tp = normalise(evaluatorReal.getTopParam(),
191 evaluatorReal.getLowerBound(),
192 evaluatorReal.getUpperBound());
193 double ub = normalise(evaluatorReal.getUpperBound(),
194 evaluatorReal.getLowerBound(),
195 evaluatorReal.getUpperBound());
196 realSections
197 .add(new RealEvaluationSection(lb, evaluatorReal
198 .getEvaluation(evaluatorReal
199 .getLowerBound()), tp,
200 evaluatorReal.getEvaluation(evaluatorReal
201 .getTopParam())));
202 realSections.add(new RealEvaluationSection(tp,
203 evaluatorReal.getEvaluation(evaluatorReal
204 .getTopParam()), ub, evaluatorReal
205 .getEvaluation(evaluatorReal
206 .getUpperBound())));
207 tmpContinuousPreference.add(tp);
208 break;
209 }
210 }
211 continuousEvaluationFunctions
212 .add(new ContinuousEvaluationFunction(realSections,
213 space.getWeight(issue.getNumber())));
214 if (space.getWeight(issue.getNumber()) > 0)
215 continuousWeightsZero = false;
216 continuousWeights.add(space.getWeight(issue.getNumber()));
217 break;
218 case INTEGER:
219 EvaluatorInteger evaluatorInteger = (EvaluatorInteger) space
220 .getEvaluator(issue.getNumber());
221 integerEvaluators.add(evaluatorInteger);
222
223 tmpRange.add((double) evaluatorInteger.getUpperBound()
224 - evaluatorInteger.getLowerBound());
225 tmpOffset.add((double) evaluatorInteger.getLowerBound());
226
227 ArrayList<IntegerEvaluationSection> integerSections = new ArrayList<IntegerEvaluationSection>();
228 switch (evaluatorInteger.getFuncType()) {
229 case LINEAR: {
230 int lb = normalise(evaluatorInteger.getLowerBound(),
231 evaluatorInteger.getLowerBound(),
232 evaluatorInteger.getUpperBound());
233 int ub = normalise(evaluatorInteger.getUpperBound(),
234 evaluatorInteger.getLowerBound(),
235 evaluatorInteger.getUpperBound());
236 IntegerEvaluationSection ies = new IntegerEvaluationSection(
237 lb, evaluatorInteger.getEvaluation(evaluatorInteger
238 .getLowerBound()), ub,
239 evaluatorInteger.getEvaluation(evaluatorInteger
240 .getUpperBound()));
241 integerSections.add(ies);
242 tmpContinuousPreference.add(ies.getTopPoint());
243 break;
244 }
245 }
246 continuousEvaluationFunctions
247 .add(new ContinuousEvaluationFunction(integerSections,
248 space.getWeight(issue.getNumber())));
249 if (space.getWeight(issue.getNumber()) > 0)
250 continuousWeightsZero = false;
251 continuousWeights.add(space.getWeight(issue.getNumber()));
252 break;
253 }
254 i++;
255 }
256
257 range = new double[tmpRange.size()];
258 for (i = 0; i < range.length; i++) {
259 range[i] = tmpRange.get(i);
260 }
261
262 offset = new double[tmpOffset.size()];
263 for (i = 0; i < offset.length; i++) {
264 offset[i] = tmpOffset.get(i);
265 }
266
267 continuousPreference = new double[tmpContinuousPreference.size()];
268 for (i = 0; i < continuousPreference.length; i++) {
269 continuousPreference[i] = tmpContinuousPreference.get(i);
270 }
271
272 // Print out the discrete issues.
273 // BidSpacePrinter.printDiscreteIssues(discreteEvaluationFunctions);
274
275 // Print out the continuous issues.
276 // BidSpacePrinter.printContinuousIssues(continuousEvaluationFunctions);
277
278 // Work out what the combinations of the discrete issues are...
279 discreteCombinations = BidSpaceDiscrete.getDiscreteCombinations(
280 discreteEvaluationFunctions, discreteWeights);
281
282 // Work out what the continuous sections are...
283 continuousSections = BidSpaceReal.getContinuousCombinations(
284 continuousEvaluationFunctions, continuousWeights);
285 }
286
287 public double getBeta(
288 ArrayList<Pair<Double, Double>> bestOpponentBidUtilityHistory,
289 double time, double utility0, double utility1) {
290 return ConcessionUtils.getBeta(bestOpponentBidUtilityHistory, time,
291 discountFactor, utility0, utility1);
292 }
293
294 public double getBeta(
295 ArrayList<Pair<Double, Double>> bestOpponentBidUtilityHistory,
296 double time, double utility0, double utility1,
297 double minDiscounting, double minBeta, double maxBeta,
298 double defaultBeta, double ourTime, double opponentTime) {
299 return ConcessionUtils.getBeta(bestOpponentBidUtilityHistory, time,
300 discountFactor, utility0, utility1, minDiscounting, minBeta,
301 maxBeta, defaultBeta, ourTime, opponentTime);
302 }
303
304 private double normalise(double value, double lowerBound, double upperBound) {
305 return (value - lowerBound) / (upperBound - lowerBound);
306 }
307
308 private int normalise(int value, double lowerBound, double upperBound) {
309 return (int) normalise((double) value, lowerBound, upperBound);
310 }
311
312 /**
313 * Get a point in an iso-utility space.
314 *
315 * @param utility
316 * the utility of the iso-utility space.
317 * @param normal
318 * the normal to the space.
319 * @return a point in an iso-utility space.
320 */
321 private double[] getPointOnLine(double utility, double[] normal,
322 double utilityA, double[] pointA, double utilityB, double[] pointB) {
323 if (utilityA == utilityB)
324 throw new AssertionError("utilityA must not equal utilityB");
325
326 double m = (utility - utilityA) / (utilityB - utilityA);
327
328 double[] pointX = new double[normal.length];
329
330 for (int i = 0; i < normal.length; i++) {
331 pointX[i] = pointA[i] + m * (pointB[i] - pointA[i]);
332 }
333
334 return pointX;
335 }
336
337 /**
338 * Project a point onto an iso-utility space.
339 *
340 * @param pointToProject
341 * the point to project.
342 * @param utility
343 * the utility of the iso-utility space.
344 * @param opponentModel
345 * @param utilitySpace
346 * @return an array list of bids that lie closest to the point (for all
347 * combinations of discrete values) and have the given utility.
348 */
349 public ArrayList<Bid> Project(double[] pointToProject, double utility,
350 int limit, AdditiveUtilitySpace utilitySpace,
351 OpponentModel opponentModel) {
352 ArrayList<Bid> bids = new ArrayList<Bid>();
353 if (discreteCombinations.length == 0) {
354 ArrayList<double[]> tmpPoints = new ArrayList<double[]>();
355 for (ContinuousSection continuousSection : continuousSections) {
356 Project(tmpPoints, pointToProject, utility, continuousSection,
357 null, range);
358 }
359 for (double[] point : getClosestPoints(tmpPoints, pointToProject)) {
360 addUniqueBid(bids, createBid(point, null));
361 }
362 } else {
363 ValueDiscrete[][] bestCombinations = getBestCombinations(
364 discreteCombinations, limit, continuousPreference,
365 utilitySpace, opponentModel);
366
367 for (ValueDiscrete[] discreteCombination : bestCombinations) {
368 ArrayList<double[]> tmpPoints = new ArrayList<double[]>();
369 if (continuousWeightsZero) {
370 if (evaluate(discreteCombination,
371 discreteEvaluationFunctions, discreteWeights) >= utility) {
372 Project(tmpPoints, pointToProject, 0, null, null, null);
373 }
374 } else {
375 for (ContinuousSection continuousSection : continuousSections) {
376 Project(tmpPoints,
377 pointToProject,
378 utility
379 - evaluate(discreteCombination,
380 discreteEvaluationFunctions,
381 discreteWeights),
382 continuousSection, discreteCombination, range);
383 }
384 }
385 for (double[] point : getClosestPoints(tmpPoints,
386 pointToProject)) {
387 addUniqueBid(bids, createBid(point, discreteCombination));
388 }
389 }
390 }
391
392 return bids;
393 }
394
395 private double evaluate(
396 ValueDiscrete[] discreteCombination,
397 ArrayList<HashMap<ValueDiscrete, Double>> discreteEvaluationFunctions,
398 ArrayList<Double> discreteWeights) {
399 double value = 0;
400 for (int j = 0; j < discreteCombination.length; j++) {
401 value += discreteWeights.get(j)
402 * discreteEvaluationFunctions.get(j).get(
403 discreteCombination[j]);
404 }
405 return value;
406 }
407
408 private ValueDiscrete[][] getBestCombinations(
409 ValueDiscrete[][] discreteCombinations, int limit,
410 double[] continuousPreference, AdditiveUtilitySpace utilitySpace,
411 OpponentModel opponentModel) {
412 if (limit == 0 || limit >= discreteCombinations.length)
413 return discreteCombinations;
414 List<EvaluatedDiscreteCombination> options = new ArrayList<EvaluatedDiscreteCombination>();
415 for (ValueDiscrete[] discreteCombination : discreteCombinations) {
416 Bid b = createBid(continuousPreference, discreteCombination);
417 double jointUtility = 0;
418 try {
419 jointUtility = utilitySpace.getUtility(b)
420 + opponentModel.getNormalizedUtility(b);
421 } catch (Exception e) {
422 e.printStackTrace();
423 }
424 options.add(new EvaluatedDiscreteCombination(discreteCombination,
425 jointUtility));
426 }
427 Collections.sort(options);
428 options = options.subList(options.size() - limit, options.size());
429 ValueDiscrete[][] bestCombinations = new ValueDiscrete[limit][discreteCombinations[0].length];
430 int i = 0;
431 for (EvaluatedDiscreteCombination edc : options) {
432 bestCombinations[i] = edc.getDiscreteCombination();
433 i++;
434 }
435 return bestCombinations;
436 }
437
438 /**
439 * @param points
440 * @param pointToProject
441 * @param utility
442 * @param continuousSection
443 * @param discreteCombination
444 */
445 private void Project(ArrayList<double[]> points, double[] pointToProject,
446 double utility, ContinuousSection continuousSection,
447 ValueDiscrete[] discreteCombination, double[] range) {
448
449 if (continuousSection == null) {
450 addUniquePoint(points, pointToProject);
451 return;
452 }
453
454 double[] pointA = continuousSection.getKnownPoint1();
455 double[] pointB = continuousSection.getKnownPoint2();
456
457 double utilityA = continuousSection.getEvalKnownPoint1();
458 double utilityB = continuousSection.getEvalKnownPoint2();
459
460 double[] pointOnLine = getPointOnLine(utility,
461 continuousSection.getNormal(), utilityA, pointA, utilityB,
462 pointB);
463 double[] projectedPoint = Project(pointToProject,
464 continuousSection.getNormal(), pointOnLine);
465 if (WithinConstraints(projectedPoint, continuousSection.getMinBounds(),
466 continuousSection.getMaxBounds())) {
467
468 addUniquePoint(points, projectedPoint);
469 } else {
470 projectedPoint = getEndPoint(continuousSection.getMinBounds(),
471 continuousSection.getMaxBounds(),
472 continuousSection.getNormal(), utility,
473 discreteCombination, pointToProject, utilityA, pointA,
474 utilityB, pointB, range);
475 if (projectedPoint != null) {
476 addUniquePoint(points, projectedPoint);
477 }
478 }
479 }
480
481 /**
482 * Project a point onto a hyperplane.
483 *
484 * @param pointToProject
485 * the point to project onto the hyperplane.
486 * @param normal
487 * the normal to the hyperplane.
488 * @param pointOnLine
489 * a point on the hyperplane.
490 * @return the projected point.
491 */
492 private double[] Project(double[] pointToProject, double[] normal,
493 double[] pointOnLine) {
494 if (pointToProject.length != normal.length)
495 throw new AssertionError(
496 "Lengths of pointToProject and normal do not match");
497 if (pointOnLine.length != normal.length)
498 throw new AssertionError(
499 "Lengths of pointOnLine and normal do not match");
500
501 int dimensions = pointToProject.length;
502
503 double projectedPoint[] = new double[dimensions];
504 double suma = 0;
505 double sumb = 0;
506 double sumc = 0;
507 for (int i = 0; i < dimensions; i++) {
508 suma += (normal[i] * pointOnLine[i]);
509 sumb += (normal[i] * pointToProject[i]);
510 sumc += (normal[i] * normal[i]);
511 }
512 double sum = (suma - sumb) / sumc;
513 for (int i = 0; i < dimensions; i++) {
514 projectedPoint[i] = pointToProject[i] + (sum * normal[i]);
515 }
516 return projectedPoint;
517 }
518
519 /**
520 * Add a bid to an array list of bids, but only if the array list does not
521 * already contain an identical bid.
522 *
523 * @param bids
524 * the array list of bids.
525 * @param bid
526 * the bid to try to add.
527 */
528 private void addUniquePoint(ArrayList<double[]> points, double[] point) {
529 for (double[] p : points) {
530 if (p.equals(point)) {
531 return;
532 }
533 }
534 points.add(point);
535 }
536
537 /**
538 * Add a bid to an array list of bids, but only if the array list does not
539 * already contain an identical bid.
540 *
541 * @param bids
542 * the array list of bids.
543 * @param bid
544 * the bid to try to add.
545 */
546 private void addUniqueBid(ArrayList<Bid> bids, Bid bid) {
547 for (Bid b : bids) {
548 if (b.equals(bid)) {
549 return;
550 }
551 }
552 bids.add(bid);
553 }
554
555 /**
556 * Get the endpoints of a bounded hyperplane that are closest to a target
557 * point.
558 *
559 * @param min
560 * the minimum bound of the space.
561 * @param max
562 * the maximum bound of the space.
563 * @param normal
564 * the normal to the hyperplane.
565 * @param utility
566 * the utility value of the hyperplane.
567 * @param discreteCombination
568 * the combination of discrete values to use in the bids.
569 * @param target
570 * the target point.
571 * @return the endpoints of a bounded hyperplane that are closest to a
572 * target point.
573 */
574 private double[] getEndPoint(double[] min, double[] max, double[] normal,
575 double utility, ValueDiscrete[] discreteCombination,
576 double[] target, double utilityA, double[] pointA, double utilityB,
577 double[] pointB, double[] range) {
578 if (min.length != normal.length)
579 throw new AssertionError("Lengths of min and normal do not match");
580 if (max.length != normal.length)
581 throw new AssertionError("Lengths of max and normal do not match");
582 if (pointA.length != normal.length)
583 throw new AssertionError(
584 "Lengths of pointA and normal do not match");
585 if (pointB.length != normal.length)
586 throw new AssertionError(
587 "Lengths of pointB and normal do not match");
588 if (target.length != normal.length)
589 throw new AssertionError(
590 "Lengths of target and normal do not match");
591
592 int dimension = normal.length;
593
594 double[] pointOnLine = getHillClimbStartPoint(min, max, normal,
595 utility, discreteCombination, target, utilityA, pointA,
596 utilityB, pointB);
597
598 if (pointOnLine == null)
599 return null;
600
601 if (!WithinConstraints(pointOnLine, min, max)) {
602 throw new AssertionError("Get Intersection fail");
603 }
604
605 for (int precision = 1; precision < 5; precision++)
606 while (true) {
607 double step = Math.pow(0.1, precision);
608 ArrayList<double[]> nearbyPointsOnLine = new ArrayList<double[]>();
609 nearbyPointsOnLine.add(pointOnLine);
610 Double[] nearbyPoint = new Double[dimension];
611 double[] proposedPoint;
612 for (int shiftDimension = 0; shiftDimension < dimension; shiftDimension++) {
613 for (int unknownDimension = 0; unknownDimension < dimension; unknownDimension++) {
614 if (shiftDimension == unknownDimension)
615 continue;
616 for (int i = 0; i < dimension; i++) {
617 nearbyPoint[i] = pointOnLine[i];
618 }
619 nearbyPoint[unknownDimension] = null;
620
621 nearbyPoint[shiftDimension] += step
622 * range[shiftDimension];
623 proposedPoint = getIntersection(nearbyPoint, normal,
624 pointOnLine);
625 if (WithinConstraints(proposedPoint, min, max))
626 nearbyPointsOnLine.add(proposedPoint);
627
628 nearbyPoint[shiftDimension] -= 2 * step
629 * range[shiftDimension];
630 proposedPoint = getIntersection(nearbyPoint, normal,
631 pointOnLine);
632 if (WithinConstraints(proposedPoint, min, max))
633 nearbyPointsOnLine.add(proposedPoint);
634 }
635 }
636
637 ArrayList<double[]> closestPoints = getClosestPoints(
638 nearbyPointsOnLine, target);
639 if (closestPoints.size() == 0)
640 break;
641
642 double[] closestPoint;
643 if (TEST_EQUIVALENCE) {
644 closestPoint = closestPoints.get(0);
645 } else {
646 closestPoint = closestPoints.get((int) Math.random()
647 * closestPoints.size());
648 }
649
650 if (getDistance(closestPoint, target) == getDistance(
651 pointOnLine, target))
652 break;
653 else
654 pointOnLine = closestPoint;
655 }
656 return pointOnLine;
657 }
658
659 private double[] getHillClimbStartPoint(double[] min, double[] max,
660 double[] normal, double utility,
661 ValueDiscrete[] discreteCombination, double[] target,
662 double utilityA, double[] pointA, double utilityB, double[] pointB) {
663 if (min.length != normal.length)
664 throw new AssertionError("Lengths of min and normal do not match");
665 if (max.length != normal.length)
666 throw new AssertionError("Lengths of max and normal do not match");
667 if (pointA.length != normal.length)
668 throw new AssertionError(
669 "Lengths of pointA and normal do not match");
670 if (pointB.length != normal.length)
671 throw new AssertionError(
672 "Lengths of pointB and normal do not match");
673 if (target.length != normal.length)
674 throw new AssertionError(
675 "Lengths of target and normal do not match");
676
677 ArrayList<Double[]> bounds = getBounds(min, max);
678
679 ArrayList<double[]> endPoints = new ArrayList<double[]>();
680
681 double[] pointOnLine = getPointOnLine(utility, normal, utilityA,
682 pointA, utilityB, pointB);
683
684 for (Double[] bound : bounds) {
685 double[] endPoint = getIntersection(bound, normal, pointOnLine);
686 if (WithinConstraints(endPoint, min, max)) {
687 endPoints.add(endPoint);
688 }
689 }
690
691 ArrayList<double[]> closestPoints = getClosestPoints(endPoints, target);
692 if (closestPoints.size() == 0)
693 return null;
694 return closestPoints.get((int) Math.random() * closestPoints.size());
695 }
696
697 private ArrayList<double[]> getClosestPoints(ArrayList<double[]> endPoints,
698 double[] target) {
699 double closestDistance = Double.MAX_VALUE;
700
701 for (double[] endPoint : endPoints) {
702 double distance = getDistance(endPoint, target);
703 closestDistance = Math.min(closestDistance, distance);
704 }
705
706 ArrayList<double[]> closestEndPoints = new ArrayList<double[]>();
707
708 for (double[] endPoint : endPoints) {
709 if (getDistance(endPoint, target) == closestDistance) {
710 closestEndPoints.add(endPoint);
711 }
712 }
713
714 return closestEndPoints;
715 }
716
717 /**
718 * Get the distance between two points in multi-dimensional space.
719 *
720 * @param pointA
721 * the first point.
722 * @param pointB
723 * the second point.
724 * @return the distance between two points in multi-dimensional space.
725 */
726 private double getDistance(double[] pointA, double[] pointB) {
727 if (pointA.length != pointB.length)
728 throw new AssertionError(
729 "Lengths of pointA and pointB do not match");
730 if (pointA.length != range.length)
731 throw new AssertionError("Lengths of pointA and range do not match");
732
733 double distance = 0;
734 for (int i = 0; i < pointB.length; i++) {
735 distance += Math.pow((pointA[i] - pointB[i]), 2);
736 }
737 return Math.sqrt(distance);
738 }
739
740 /**
741 * Create a bid.
742 *
743 * @param point
744 * the point in the multi-dimensional space that represents the
745 * continuous issues of the domain.
746 * @param discreteCombination
747 * the combination of discrete values.
748 * @return a bid.
749 */
750 private Bid createBid(double[] point, ValueDiscrete[] discreteCombination) {
751 HashMap<Integer, Value> bidInternals = new HashMap<Integer, Value>();
752 int continuousPos = 0;
753 int discretePos = 0;
754 for (int i = 0; i < issueTypes.length; i++) {
755 if (issueTypes[i] == ISSUETYPE.REAL) {
756 bidInternals.put(issues.get(i).getNumber(), new ValueReal(
757 (point[continuousPos] * range[continuousPos])
758 + offset[continuousPos]));
759 continuousPos++;
760 } else if (issueTypes[i] == ISSUETYPE.INTEGER) {
761 bidInternals
762 .put(issues.get(i).getNumber(),
763 new ValueInteger(
764 (int) Math
765 .round((point[continuousPos] * range[continuousPos])
766 + offset[continuousPos])));
767 continuousPos++;
768 } else if (issueTypes[i] == ISSUETYPE.DISCRETE) {
769 bidInternals.put(issues.get(i).getNumber(),
770 discreteCombination[discretePos]);
771 discretePos++;
772 }
773 }
774 try {
775 return new Bid(domain, bidInternals);
776 } catch (Exception e) {
777 return null;
778 }
779 }
780
781 /**
782 * Get the intersection between a bound and a hyperplane.
783 *
784 * @param bound
785 * the bound.
786 * @param normal
787 * the normal to the hyperplane.
788 * @param utility
789 * the utility of the hyperplane.
790 * @return the intersection between a bound and a hyperplane.
791 */
792 private double[] getIntersection(Double[] bound, double[] normal,
793 double[] pointOnLine) {
794 if (bound.length != normal.length)
795 throw new AssertionError("Lengths of bound and normal do not match");
796 int dimensions = normal.length;
797
798 double c = 0;
799 for (int i = 0; i < dimensions; i++) {
800 c += normal[i] * pointOnLine[i];
801 }
802
803 int unknown = -1;
804 double sum = 0;
805 double[] intersection = new double[dimensions];
806 for (int i = 0; i < dimensions; i++) {
807 if (bound[i] == null) {
808 unknown = i;
809 } else {
810 sum += bound[i] * normal[i];
811 intersection[i] = bound[i];
812 }
813 }
814
815 if (unknown < 0)
816 throw new AssertionError("bound has no unknown");
817
818 intersection[unknown] = (c - sum) / normal[unknown];
819
820 return intersection;
821 }
822
823 /**
824 * Get all bounds of a space.
825 *
826 * @param min
827 * the minimum bound of the space.
828 * @param max
829 * the maximum bound of the space.
830 * @return all bounds of a space.
831 */
832 private ArrayList<Double[]> getBounds(double[] min, double[] max) {
833 if (min.length != max.length)
834 throw new AssertionError("Lengths of min and max do not match");
835
836 int dimensions = min.length;
837
838 ArrayList<Double[]> bounds = new ArrayList<Double[]>();
839
840 int boundCount = dimensions * (int) Math.pow(2, dimensions - 1);
841 for (int i = 0; i < boundCount; i++) {
842 int dimension = (int) Math.floor(i / (boundCount / dimensions));
843 Double[] bound = new Double[dimensions];
844 for (int j = 0; j < dimensions; j++) {
845 if (j == dimension)
846 continue;
847 if (j < dimension)
848 bound[j] = (i & (1 << j)) == 0 ? min[j] : max[j];
849 else
850 bound[j] = (i & (1 << (j - 1))) == 0 ? min[j] : max[j];
851 }
852 bounds.add(bound);
853 }
854
855 return bounds;
856 }
857
858 /**
859 * Check whether a point lies within a set of bounds.
860 *
861 * @param point
862 * the point to check.
863 * @param min
864 * the minimum bounds.
865 * @param max
866 * the maximum bounds.
867 * @return true if the point lies within the bounds, false otherwise.
868 */
869 private boolean WithinConstraints(double[] point, double[] min, double[] max) {
870 if (min.length != point.length)
871 throw new AssertionError("Lengths of min and point do not match");
872 if (max.length != point.length)
873 throw new AssertionError("Lengths of max and point do not match");
874
875 for (int i = 0; i < point.length; i++) {
876 if (point[i] < min[i] || point[i] > max[i]) {
877 return false;
878 }
879 }
880 return true;
881 }
882
883 /**
884 * Get all combinations of integers in a space.
885 *
886 * @param space
887 * the size of the space.
888 * @return all combinations of integers in a space.
889 */
890 public static ArrayList<int[]> getCombinationValues(int[] space) {
891 ArrayList<int[]> combinationValues = new ArrayList<int[]>();
892 if (space.length == 1) {
893 return combinationValues;
894 }
895 for (int i = 0; i < space[space.length - 1]; i++) {
896 int[] combination = new int[space.length - 1];
897 for (int j = 0; j < combination.length; j++) {
898 combination[j] = (int) Math.floor((i / space[j])
899 % (space[j + 1] / space[j]));
900 }
901
902 combinationValues.add(combination);
903 }
904 return combinationValues;
905 }
906
907 /**
908 * Get the point in multi-dimensional space that represents a bid.
909 *
910 * @param bid
911 * the bid.
912 * @return the point in multi-dimensional space that represents a bid.
913 */
914 public double[] getPoint(Bid bid) {
915 double[] point = new double[continuousWeights.size()];
916 int i = 0;
917 int j = 0;
918 for (ISSUETYPE issueType : issueTypes) {
919 if (issueType == ISSUETYPE.REAL) {
920 ValueReal valueReal;
921 try {
922 valueReal = (ValueReal) bid.getValue(issues.get(j)
923 .getNumber());
924 point[i] = (valueReal.getValue() - offset[i]) / range[i];
925 } catch (Exception e) {
926 e.printStackTrace();
927 }
928 i++;
929 }
930 if (issueType == ISSUETYPE.INTEGER) {
931 ValueInteger valueInteger;
932 try {
933 valueInteger = (ValueInteger) bid.getValue(issues.get(j)
934 .getNumber());
935 point[i] = (valueInteger.getValue() - offset[i]) / range[i];
936 } catch (Exception e) {
937 e.printStackTrace();
938 }
939 i++;
940 }
941 j++;
942 }
943 return point;
944 }
945
946 public Bid getMaxUtilityBid() {
947
948 int discreteIssues = 0;
949 int continuousIssues = 0;
950
951 for (int i = 0; i < issueTypes.length; i++) {
952 switch (issueTypes[i]) {
953 case DISCRETE:
954 discreteIssues++;
955 break;
956 case REAL:
957 case INTEGER:
958 continuousIssues++;
959 break;
960 }
961 }
962
963 int discreteCount = 0;
964 int realCount = 0;
965 int integerCount = 0;
966
967 ValueDiscrete[] discreteCombination = new ValueDiscrete[discreteIssues];
968 double[] continuousValues = new double[continuousIssues];
969
970 for (Issue issue : issues) {
971 switch (issue.getType()) {
972 case DISCRETE:
973 IssueDiscrete issueDiscrete = (IssueDiscrete) issue;
974 List<ValueDiscrete> values = issueDiscrete.getValues();
975 double maxEval = 0;
976 ValueDiscrete maxValue = null;
977 for (ValueDiscrete value : values) {
978 double tmpEval;
979 try {
980 tmpEval = discreteEvaluators.get(discreteCount)
981 .getEvaluation(value);
982 if (tmpEval > maxEval) {
983 maxEval = tmpEval;
984 maxValue = value;
985 }
986 } catch (Exception e) {
987 e.printStackTrace();
988 }
989 }
990 discreteCombination[discreteCount] = maxValue;
991 discreteCount++;
992 break;
993 case REAL:
994 EvaluatorReal realEvaluator = realEvaluators.get(realCount);
995 switch (realEvaluator.getFuncType()) {
996 case LINEAR:
997 if (realEvaluator.getEvaluation(realEvaluator
998 .getLowerBound()) < realEvaluator
999 .getEvaluation(realEvaluator.getUpperBound()))
1000 continuousValues[realCount + integerCount] = 1;
1001 else
1002 continuousValues[realCount + integerCount] = 0;
1003 break;
1004 case TRIANGULAR:
1005 continuousValues[realCount + integerCount] = normalise(
1006 realEvaluator.getTopParam(),
1007 realEvaluator.getLowerBound(),
1008 realEvaluator.getUpperBound());
1009 break;
1010 }
1011 realCount++;
1012 break;
1013 case INTEGER:
1014 EvaluatorInteger integerEvaluator = integerEvaluators
1015 .get(integerCount);
1016 switch (integerEvaluator.getFuncType()) {
1017 case LINEAR:
1018 if (integerEvaluator.getEvaluation(integerEvaluator
1019 .getLowerBound()) < integerEvaluator
1020 .getEvaluation(integerEvaluator.getUpperBound()))
1021 continuousValues[realCount + integerCount] = 1;
1022 else
1023 continuousValues[realCount + integerCount] = 0;
1024 break;
1025 /*
1026 * case TRIANGULAR: realValues[integerCount] =
1027 * integerEvaluator.getTopParam(); break;
1028 */
1029 }
1030 integerCount++;
1031 break;
1032 }
1033 }
1034
1035 return createBid(continuousValues, discreteCombination);
1036 }
1037}
Note: See TracBrowser for help on using the repository browser.