Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 1 | package org.onlab.graph; |
| 2 | |
| 3 | import java.util.ArrayList; |
| 4 | import java.util.Collections; |
| 5 | import java.util.List; |
| 6 | import java.util.Random; |
| 7 | |
| 8 | /** |
| 9 | * Represents a population of GAOrganisms. This class can be used |
| 10 | * to run a genetic algorithm on the population and return the fittest solutions. |
| 11 | */ |
| 12 | class GAPopulation<Organism extends GAOrganism> extends ArrayList<Organism> { |
| 13 | Random r = new Random(); |
| 14 | |
| 15 | /** |
| 16 | * Steps the population through one generation. The 75% least fit |
| 17 | * organisms are killed off and replaced with the children of the |
| 18 | * 25% (as well as some "random" newcomers). |
| 19 | */ |
| 20 | void step() { |
| 21 | Collections.sort(this, (org1, org2) -> { |
| 22 | double d = org1.fitness() - org2.fitness(); |
| 23 | if (d < 0) { |
| 24 | return -1; |
| 25 | } else if (d == 0) { |
| 26 | return 0; |
| 27 | } |
| 28 | return 1; |
| 29 | }); |
| 30 | int maxSize = size(); |
| 31 | for (int i = size() - 1; i > maxSize / 4; i--) { |
| 32 | remove(i); |
| 33 | } |
| 34 | for (Organism org: this) { |
| 35 | if (r.nextBoolean()) { |
| 36 | org.mutate(); |
| 37 | } |
| 38 | } |
| 39 | while (size() < maxSize * 4 / 5) { |
| 40 | Organism org1 = get(r.nextInt(size())); |
| 41 | Organism org2 = get(r.nextInt(size())); |
| 42 | add((Organism) org1.crossWith(org2)); |
| 43 | } |
| 44 | |
| 45 | while (size() < maxSize) { |
| 46 | Organism org1 = get(r.nextInt(size())); |
| 47 | add((Organism) org1.random()); |
| 48 | } |
| 49 | } |
| 50 | |
| 51 | /** |
| 52 | * Runs GA for the specified number of iterations, and returns |
| 53 | * a sample of the resulting population of solutions. |
| 54 | * |
| 55 | * @param generations Number of generations to run GA for |
| 56 | * @param populationSize Population size of GA |
| 57 | * @param sample Number of solutions to ask for |
| 58 | * @param template Template GAOrganism to seed the population with |
| 59 | * @return ArrayList containing sample number of organisms |
| 60 | */ |
| 61 | List<Organism> runGA(int generations, int populationSize, int sample, Organism template) { |
| 62 | for (int i = 0; i < populationSize; i++) { |
| 63 | add((Organism) template.random()); |
| 64 | } |
| 65 | |
| 66 | for (int i = 0; i < generations; i++) { |
| 67 | step(); |
| 68 | } |
| 69 | for (int i = size() - 1; i >= sample; i--) { |
| 70 | remove(i); |
| 71 | } |
| 72 | return new ArrayList<>(this); |
| 73 | } |
| 74 | } |
| 75 | |