Thomas Vachuska | 58de416 | 2015-09-10 16:15:33 -0700 | [diff] [blame] | 1 | /* |
Brian O'Connor | a09fe5b | 2017-08-03 21:12:30 -0700 | [diff] [blame] | 2 | * Copyright 2015-present Open Networking Foundation |
Thomas Vachuska | 58de416 | 2015-09-10 16:15:33 -0700 | [diff] [blame] | 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 16 | package org.onlab.graph; |
| 17 | |
| 18 | import java.util.ArrayList; |
| 19 | import java.util.Collections; |
| 20 | import java.util.List; |
| 21 | import java.util.Random; |
| 22 | |
| 23 | /** |
| 24 | * Represents a population of GAOrganisms. This class can be used |
| 25 | * to run a genetic algorithm on the population and return the fittest solutions. |
| 26 | */ |
| 27 | class GAPopulation<Organism extends GAOrganism> extends ArrayList<Organism> { |
| 28 | Random r = new Random(); |
| 29 | |
| 30 | /** |
| 31 | * Steps the population through one generation. The 75% least fit |
| 32 | * organisms are killed off and replaced with the children of the |
| 33 | * 25% (as well as some "random" newcomers). |
| 34 | */ |
| 35 | void step() { |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 36 | Collections.sort(this, (org1, org2) -> |
| 37 | org1.fitness().compareTo(org2.fitness())); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 38 | int maxSize = size(); |
| 39 | for (int i = size() - 1; i > maxSize / 4; i--) { |
| 40 | remove(i); |
| 41 | } |
| 42 | for (Organism org: this) { |
| 43 | if (r.nextBoolean()) { |
| 44 | org.mutate(); |
| 45 | } |
| 46 | } |
| 47 | while (size() < maxSize * 4 / 5) { |
| 48 | Organism org1 = get(r.nextInt(size())); |
| 49 | Organism org2 = get(r.nextInt(size())); |
| 50 | add((Organism) org1.crossWith(org2)); |
| 51 | } |
| 52 | |
| 53 | while (size() < maxSize) { |
| 54 | Organism org1 = get(r.nextInt(size())); |
| 55 | add((Organism) org1.random()); |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | /** |
| 60 | * Runs GA for the specified number of iterations, and returns |
| 61 | * a sample of the resulting population of solutions. |
| 62 | * |
| 63 | * @param generations Number of generations to run GA for |
| 64 | * @param populationSize Population size of GA |
| 65 | * @param sample Number of solutions to ask for |
| 66 | * @param template Template GAOrganism to seed the population with |
| 67 | * @return ArrayList containing sample number of organisms |
| 68 | */ |
| 69 | List<Organism> runGA(int generations, int populationSize, int sample, Organism template) { |
| 70 | for (int i = 0; i < populationSize; i++) { |
| 71 | add((Organism) template.random()); |
| 72 | } |
| 73 | |
| 74 | for (int i = 0; i < generations; i++) { |
| 75 | step(); |
| 76 | } |
| 77 | for (int i = size() - 1; i >= sample; i--) { |
| 78 | remove(i); |
| 79 | } |
| 80 | return new ArrayList<>(this); |
| 81 | } |
| 82 | } |
| 83 | |