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