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