source: src/main/java/agents/anac/y2014/Gangster/GenAlg.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: 15.2 KB
Line 
1package agents.anac.y2014.Gangster;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.PriorityQueue;
6import java.util.Random;
7
8import genius.core.Bid;
9import genius.core.bidding.BidDetails;
10import genius.core.issue.IssueInteger;
11import genius.core.issue.Value;
12import genius.core.issue.ValueInteger;
13import genius.core.utility.NonlinearUtilitySpace;
14
15class GenAlg {
16
17 NonlinearUtilitySpace utilitySpace;
18 int numIssues;
19
20 int initialGenerationSize;
21 int numSurvivors;
22 int numGenerations;
23 int minDistance; // the minimum distance between any pair of elements in a
24 // survivor set.
25
26 PriorityQueue<BidDetails> generation;
27 ArrayList<BidDetails> newGeneration;
28 ArrayList<BidDetails> survivors;
29 ArrayList<BidDetails> newSurvivors;
30
31 ArrayList<ArrayList<ValueInteger>> genesTable1;
32 ArrayList<ArrayList<ValueInteger>> genesTable2;
33 boolean useTable1 = true;
34
35 Random random = new Random();
36
37 GenAlg(NonlinearUtilitySpace utilitySpace, int initialGenerationSize,
38 int numSurvivors, int numGenerations, int minDistance) {
39
40 this.utilitySpace = utilitySpace;
41 this.numIssues = utilitySpace.getDomain().getIssues().size();
42
43 this.initialGenerationSize = initialGenerationSize;
44 this.numSurvivors = numSurvivors;
45 this.numGenerations = numGenerations;
46 this.minDistance = minDistance;
47
48 generation = new PriorityQueue<BidDetails>(initialGenerationSize);
49 newGeneration = new ArrayList(initialGenerationSize);
50 survivors = new ArrayList<BidDetails>(numSurvivors);
51 newSurvivors = new ArrayList<BidDetails>(numSurvivors);
52
53 genesTable1 = new ArrayList<ArrayList<ValueInteger>>(numIssues + 1);
54 genesTable2 = new ArrayList<ArrayList<ValueInteger>>(numIssues + 1);
55
56 // Fill the table
57 genesTable1.add(null);
58 genesTable2.add(null);
59 for (int i = 1; i <= numIssues; i++) {
60
61 int highestVal = ((IssueInteger) utilitySpace.getDomain()
62 .getIssues().get(i - 1)).getUpperBound();
63 int lowestVal = ((IssueInteger) utilitySpace.getDomain()
64 .getIssues().get(i - 1)).getLowerBound();
65
66 ArrayList<ValueInteger> list1 = new ArrayList<ValueInteger>(
67 highestVal + 1);
68 ArrayList<ValueInteger> list2 = new ArrayList<ValueInteger>(
69 highestVal + 1);
70
71 for (int j = lowestVal; j <= highestVal; j++) {
72 list1.add(new ValueInteger(j));
73 }
74
75 genesTable1.add(list1);
76 genesTable2.add(list2);
77 }
78
79 }
80
81 ArrayList<BidDetails> globalSearch() throws Exception {
82 return go(null, -1);
83 }
84
85 ArrayList<BidDetails> localSearch(Bid latestBid, int maxDistance)
86 throws Exception {
87 return go(latestBid, maxDistance);
88 }
89
90 private ArrayList<BidDetails> go(Bid latestBid, int maxDistance)
91 throws Exception {
92
93 generation.clear();
94
95 // generate initial generation and request their utilities.
96 for (int i = 0; i < initialGenerationSize; i++) {
97 generation.add(getSample(latestBid, maxDistance));
98 }
99
100 for (int k = 1; k < numGenerations; k++) {
101
102 // get the survivors of the generation.
103 fillSurvivorList(generation);
104
105 // if the survivors are not diverse enough the algorithm has
106 // converged and we return the previous generation
107 if (newSurvivors.size() < numSurvivors) {
108 return survivors;
109 }
110 survivors.clear();
111 survivors.addAll(newSurvivors);
112
113 newGeneration.clear();
114
115 // recombine the best ones, to create babies.
116 for (int i = 0; i < numSurvivors; i++) {
117 for (int j = i + 1; j < numSurvivors; j++) {
118
119 // 45 pairs, for each pair generate 2 babies.
120 if (latestBid == null) { // global search
121 newGeneration.addAll(crossOver(survivors.get(i),
122 survivors.get(j), 2));
123 } else { // local search
124 newGeneration.addAll(crossOver(latestBid, maxDistance,
125 survivors.get(i), survivors.get(j)));
126 }
127 }
128 }// size = n*(n-1)
129
130 // create a new random sample.
131 BidDetails randomSample = getSample(latestBid, maxDistance);
132 for (int j = 0; j < numSurvivors; j++) {
133
134 // 10 pairs, for each pair generate 2 babies.
135 if (latestBid == null) { // global search
136 newGeneration.addAll(crossOver(survivors.get(j),
137 randomSample, 2));
138 } else { // local search
139 newGeneration.addAll(crossOver(latestBid, maxDistance,
140 survivors.get(j), randomSample));
141 }
142 }// size = n*(n-1) + 2n = n^2 + n
143
144 // add the survivors from the previous generation.
145 for (int i = 0; i < numSurvivors; i++) {
146 newGeneration.add(survivors.get(i));
147 }// size n^2 + 2n
148
149 generation.clear();
150 generation.addAll(newGeneration);
151
152 }
153
154 fillSurvivorList(generation);
155
156 // if the survivors are not diverse enough the algorithm has converged
157 // and we return the previous generation
158 if (newSurvivors.size() < numSurvivors) {
159 return survivors;
160 }
161
162 return newSurvivors;
163
164 }
165
166 /**
167 * Clears the list of survivors, sorts the given generation, and fills the
168 * list of survivors again with the best n samples from the given
169 * generation. If this is not possible it means that we have converged, so
170 * we should return the list.
171 *
172 * @param generation
173 * @throws Exception
174 */
175 void fillSurvivorList(PriorityQueue<BidDetails> generation)
176 throws Exception {
177
178 newSurvivors.clear();
179 newSurvivors.add(generation.poll());
180 int l = 1;
181 while (newSurvivors.size() < numSurvivors && l < generation.size()) {
182
183 // get the next best sample from the generation
184 BidDetails samp = generation.poll();
185 l++;
186
187 // test if it isn't too close to any other survivor.
188 boolean shouldBeAdded = true;
189 for (BidDetails survivor : newSurvivors) {
190 int dist = Utils.calculateManhattanDistance(samp.getBid(),
191 survivor.getBid());
192 if (dist < minDistance) {
193 shouldBeAdded = false;
194 break;
195 }
196 }
197
198 if (shouldBeAdded) {
199 newSurvivors.add(samp);
200 }
201
202 }
203
204 }
205
206 Bid getRandomBid() throws Exception {
207
208 HashMap<Integer, Value> newValues = new HashMap<Integer, Value>(
209 numIssues, 2);
210
211 ArrayList<ArrayList<ValueInteger>> table;
212 ArrayList<ArrayList<ValueInteger>> bin;
213 if (useTable1) {
214 table = genesTable1;
215 bin = genesTable2;
216 } else {
217 table = genesTable2;
218 bin = genesTable1;
219 }
220
221 for (int i = 1; i <= numIssues; i++) {
222
223 int r = random.nextInt(table.get(i).size());
224 ValueInteger val = table.get(i).remove(r);
225 bin.get(i).add(val);
226
227 newValues.put(new Integer(i), val);
228 }
229
230 if (table.get(1).size() == 0) { // table.get(0) is null.
231 useTable1 = !useTable1;
232 }
233
234 Bid newBid = new Bid(utilitySpace.getDomain(), newValues);
235 return newBid;
236 }
237
238 BidDetails getSample(Bid latestBid, int maxDistance) throws Exception {
239
240 Bid bid;
241 if (latestBid != null) {
242 bid = getRandomBid(latestBid, maxDistance);
243 } else {
244 // bid = utilitySpace.getDomain().getRandomBid();
245 bid = getRandomBid();
246 }
247
248 double val = utilitySpace.getUtility(bid);
249
250 return new BidDetails(bid, val);
251 }
252
253 /**
254 * Returns a bid with distance smaller than or equal to maxDistance from the
255 * reference bid.
256 *
257 *
258 * @param utilitySpace
259 * @param referencebid
260 * @param maxDistance
261 * @return
262 * @throws Exception
263 */
264 Bid getRandomBid(Bid referencebid, int maxDistance) throws Exception {
265
266 // the direction in which we make the random step.
267 int[] directions = new int[numIssues + 1];
268
269 // make a copy of the reference bid.
270 HashMap<Integer, Value> oldValues = referencebid.getValues();
271 HashMap<Integer, Value> newValues = new HashMap<Integer, Value>(
272 oldValues); // Do NOT move this variable to outside the method,
273 // cause this will lead to problems!!
274
275 int distance = random.nextInt(maxDistance) + 1;
276
277 for (int i = 0; i < distance; i++) {
278
279 // pick a random index to increase or decrease:
280 int issue = random.nextInt(numIssues) + 1;
281
282 // we will increase or decrease this issue by 1
283
284 // first determine the direction:
285 if (directions[issue] == 0) { // we have to remain consistent. if
286 // one time we increase a value, we
287 // cannot decrease it the next time.
288 // Therefore we store the direction
289 // and re-use it.
290 directions[issue] = 2 * random.nextInt(2) - 1; // set direction
291 // to 1 or -1.
292 }
293
294 int lowestVal = ((IssueInteger) utilitySpace.getDomain()
295 .getIssues().get(issue - 1)).getLowerBound(); // WARNING:
296 // the
297 // issues
298 // are
299 // numbered
300 // 1 to 30,
301 // but
302 // when
303 // calling
304 // getIssue,
305 // they are
306 // indexed
307 // with the
308 // values 0
309 // to 29
310 int highestVal = ((IssueInteger) utilitySpace.getDomain()
311 .getIssues().get(issue - 1)).getUpperBound();
312
313 int oldValue = ((ValueInteger) oldValues.get(new Integer(issue)))
314 .getValue();
315 if (oldValue == highestVal && directions[issue] == 1
316 || oldValue == lowestVal && directions[issue] == -1) {
317 i--;
318 continue;
319 }
320 newValues.put(new Integer(issue), new ValueInteger(oldValue
321 + directions[issue]));
322
323 }
324
325 Bid newBid = new Bid(utilitySpace.getDomain(), newValues);
326 return newBid;
327 }
328
329 /**
330 * Creates two children from bid1 and bid2, and repeats this until
331 * numChildren children have been created.
332 *
333 * @param bid1
334 * @param bid2
335 * @param numChildren
336 * @return
337 * @throws Exception
338 */
339 ArrayList<BidDetails> crossOver(BidDetails bid1, BidDetails bid2,
340 int numChildren) throws Exception {
341
342 HashMap<Integer, Value> vals1 = bid1.getBid().getValues();
343 HashMap<Integer, Value> vals2 = bid2.getBid().getValues();
344
345 // Note: we can set the load factor as high as we want because we are
346 // sure that the number of entries will never exceed the number of
347 // buckets, so re-hashing should never occur.
348 HashMap<Integer, Value> newVals1 = new HashMap<Integer, Value>(
349 numIssues, 2);
350 HashMap<Integer, Value> newVals2 = new HashMap<Integer, Value>(
351 numIssues, 2);
352
353 ArrayList<BidDetails> children = new ArrayList(numChildren);
354
355 for (int c = 0; c < numChildren / 2; c++) {
356 for (Integer i = 1; i <= numIssues; i++) {
357 if (random.nextBoolean()) {
358 newVals1.put(i, vals1.get(i));
359 newVals2.put(i, vals2.get(i));
360 } else {
361 newVals1.put(i, vals2.get(i));
362 newVals2.put(i, vals1.get(i));
363 }
364 }
365
366 Bid _child1 = new Bid(utilitySpace.getDomain(), newVals1);
367 double value1 = utilitySpace.getUtility(_child1);
368 BidDetails child1 = new BidDetails(_child1, value1);
369 children.add(child1);
370
371 Bid _child2 = new Bid(utilitySpace.getDomain(), newVals2);
372 double value2 = utilitySpace.getUtility(_child2);
373 BidDetails child2 = new BidDetails(_child2, value2);
374 children.add(child2);
375 }
376
377 return children;
378 }
379
380 /**
381 * Creates two babies that are close enough to the reference bid. Assumes
382 * that bid1 and bid2 are also close enough to the reference bid.
383 *
384 * First creates two children in the standard way, then calculates the
385 * distances of both if not both are close enough randomly swaps genes until
386 * it is achieved.
387 *
388 * @param refBid
389 * @param maxDistance
390 * @param bid1
391 * @param bid2
392 * @param numChildren
393 * @return
394 * @throws Exception
395 */
396 ArrayList<BidDetails> crossOver(Bid refBid, int maxDistance,
397 BidDetails bid1, BidDetails bid2) throws Exception {
398
399 HashMap<Integer, Value> refVals = refBid.getValues();
400
401 HashMap<Integer, Value> vals1 = bid1.getBid().getValues();
402 HashMap<Integer, Value> vals2 = bid2.getBid().getValues();
403
404 // Note: we can set the load factor as high as we want because we are
405 // sure that the number of entries will never exceed the number of
406 // buckets, so re-hashing should never occur.
407 HashMap<Integer, Value> newVals1 = new HashMap<Integer, Value>(
408 numIssues, 2);
409 HashMap<Integer, Value> newVals2 = new HashMap<Integer, Value>(
410 numIssues, 2);
411
412 ArrayList<BidDetails> children = new ArrayList(2);
413
414 int totalDistance1 = 0; // the distance between child1 and the reference
415 // bid.
416 int totalDistance2 = 0; // the distance between child2 and the reference
417 // bid.
418 int[] distances1 = new int[numIssues + 1]; // the distance between
419 // child1 and the reference
420 // bid, for each issue.
421 int[] distances2 = new int[numIssues + 1]; // the distance between
422 // child1 and the reference
423 // bid, for each issue.
424
425 for (Integer i = 1; i <= numIssues; i++) {
426
427 if (random.nextBoolean()) {
428 newVals1.put(i, vals1.get(i));
429 newVals2.put(i, vals2.get(i));
430 } else {
431 newVals1.put(i, vals2.get(i));
432 newVals2.put(i, vals1.get(i));
433 }
434
435 // iteratively calculate the distances between the new children and
436 // the reference bid.
437 distances1[i] = Math.abs(((ValueInteger) newVals1.get(i))
438 .getValue() - ((ValueInteger) refVals.get(i)).getValue());
439 distances2[i] = Math.abs(((ValueInteger) newVals2.get(i))
440 .getValue() - ((ValueInteger) refVals.get(i)).getValue());
441 totalDistance1 += distances1[i];
442 totalDistance2 += distances2[i];
443 }
444
445 int counter = 0;
446 while (totalDistance1 > maxDistance || totalDistance2 > maxDistance) {
447
448 int randomIndex = 0;
449
450 if (totalDistance1 > totalDistance2) {
451
452 do {
453 randomIndex = random.nextInt(numIssues) + 1;
454 } while (distances1[randomIndex] < distances2[randomIndex]); // search
455 // for
456 // an
457 // index
458 // for
459 // which
460 // child1
461 // is
462 // closer
463 // to
464 // ref
465 // than
466 // child2
467
468 } else {
469 do {
470 randomIndex = random.nextInt(numIssues) + 1;
471 } while (distances1[randomIndex] > distances2[randomIndex]); // search
472 // for
473 // an
474 // index
475 // for
476 // which
477 // child2
478 // is
479 // closer
480 // to
481 // ref
482 // than
483 // child1
484 }
485
486 // swap the two values.
487 Value temp = newVals1.get(randomIndex);
488 newVals1.put(randomIndex, newVals2.get(randomIndex));
489 newVals2.put(randomIndex, temp);
490
491 // Recalculate the distances of the new children, in 3 steps
492
493 // 1.subtract the issue distances for the swapped issue from the
494 // total distances
495 totalDistance1 -= distances1[randomIndex];
496 totalDistance2 -= distances2[randomIndex];
497
498 // 2.swap the issue distances.
499 int tempp = distances1[randomIndex];
500 distances1[randomIndex] = distances2[randomIndex];
501 distances2[randomIndex] = tempp;
502
503 // 3.add the issue swapped distances again to the total distances.
504 totalDistance1 += distances1[randomIndex];
505 totalDistance2 += distances2[randomIndex];
506
507 // SECURITY MEASURE TO MAKE SURE THAT WE DON'T LOOP FOR EVER.
508 counter++;
509 if (counter > 500) {
510 System.out
511 .println("GenAlg.crossOver() WARNING!!! There seems to be an infinite loop in the genetic algorithm!!");
512 break;
513 }
514
515 }
516
517 Bid _child1 = new Bid(utilitySpace.getDomain(), newVals1);
518 double value1 = utilitySpace.getUtility(_child1);
519 BidDetails child1 = new BidDetails(_child1, value1);
520 children.add(child1);
521
522 Bid _child2 = new Bid(utilitySpace.getDomain(), newVals2);
523 double value2 = utilitySpace.getUtility(_child2);
524 BidDetails child2 = new BidDetails(_child2, value2);
525 children.add(child2);
526
527 return children;
528 }
529}
Note: See TracBrowser for help on using the repository browser.