aboutsummaryrefslogtreecommitdiffstats
path: root/src/jcgp/backend/modules/es
diff options
context:
space:
mode:
Diffstat (limited to 'src/jcgp/backend/modules/es')
-rw-r--r--src/jcgp/backend/modules/es/MuPlusLambda.java66
1 files changed, 61 insertions, 5 deletions
diff --git a/src/jcgp/backend/modules/es/MuPlusLambda.java b/src/jcgp/backend/modules/es/MuPlusLambda.java
index 3743ee6..6a6870f 100644
--- a/src/jcgp/backend/modules/es/MuPlusLambda.java
+++ b/src/jcgp/backend/modules/es/MuPlusLambda.java
@@ -77,21 +77,77 @@ public class MuPlusLambda extends EvolutionaryStrategy {
@Override
public void evolve(Population population, Mutator mutator) {
- // sort the population in order of best fitness
- population.sort();
+ // sort the population neutrally
+ sort(population);
- // population is now sorted in ascending order of fitness, the last chromosomes are the fittest
+ // population is now sorted such that the new parents are in the last mu positions
for (int i = 0; i < getResources().populationSize() - mu.get(); i++) {
- // select a random parent out of the lambda offspring individuals
+ // select a random parent out of the mu population parents
int randomParent = getResources().populationSize() - 1 - getResources().getRandomInt(mu.get());
if (report.get()) getResources().reportln("[ES] Copying Chr " + randomParent + " to population position " + i);
+
+ // copy it into the offspring position
population.copyChromosome(randomParent, i);
- // mutate selected chromosome
+ // mutate the new offspring chromosome
if (report.get()) getResources().reportln("[ES] Mutating copied chromosome");
mutator.mutate(population.get(i));
}
if (report.get()) getResources().reportln("[ES] Generation is complete");
}
+
+ /**
+ * Neutrally sorts the specified population.
+ * <br><br>
+ * Optimised sorting methods tend to be stable, meaning
+ * the order of elements which are already ordered is not
+ * changed. While performing faster, such sorting algorithms
+ * do not promote neutral drift, an important aspect of CGP.
+ * <br><br>
+ * This sort iterates through the population offspring (first lambda
+ * elements) and compares each with each of the parents (last mu
+ * elements), overwriting the parent if the offspring's fitness
+ * is greater than or equal to the parent's.
+ * It is biased towards offspring: parents are replaced with
+ * equally fit offspring as often as possible.
+ *
+ * @param population the population to sort.
+ */
+ private void sort(Population population) {
+ /* Create an array with the index of each of the current parents.
+ * This is done to speed up the sort. No deep chromosome copies are
+ * made until the algorithm is finished; instead, only indices are copied.
+ */
+ int[] parents = new int[mu.get()];
+ for (int i = 0; i < parents.length; i++) {
+ parents[i] = lambda.get() + i;
+ }
+
+ // cycle through the offspring, i.e. the first lambda elements of the population
+ for (int o = 0; o < getResources().populationSize() - mu.get(); o++) {
+ // compare each offspring with each parent, as stored in parents
+ for (int p = 0; p < parents.length; p++) {
+ /* replace parent if the offspring fitness and greater than or equal to its own
+ * if it is equal to, only replace if it is an old parent, if it is greater than,
+ * replace regardless
+ */
+ if ((population.get(o).getFitness() == population.get(parents[p]).getFitness() && parents[p] >= lambda.get())
+ || population.get(o).getFitness() >= population.get(parents[p]).getFitness()) {
+ parents[p] = o;
+ // offspring has been selected, check the next one
+ break;
+ }
+ }
+ }
+
+ /* selection is complete, parents now contains the indices of each selected offspring
+ * time to perform the deep copies
+ */
+ for (int c = 0; c < parents.length; c++) {
+ // copy each selected index in parent to each parent position in the population
+ population.copyChromosome(parents[c], lambda.get() + c);
+ }
+
+ }
}