You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by br...@apache.org on 2008/03/31 17:37:23 UTC
svn commit: r643027 -
/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/
Author: brentworden
Date: Mon Mar 31 08:37:16 2008
New Revision: 643027
URL: http://svn.apache.org/viewvc?rev=643027&view=rev
Log:
added beginning of genetics framework.
Added:
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java
commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java?rev=643027&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Chromosome.java Mon Mar 31 08:37:16 2008
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.apache.commons.math.genetics;
+
+/**
+ * Individual in a population. Chromosomes are compared based on their fitness.
+ */
+public interface Chromosome {
+ /**
+ * Access the fitness of this chromosome.
+ *
+ * @return the fitness.
+ */
+ Fitness getFitness();
+}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java?rev=643027&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/ChromosomePair.java Mon Mar 31 08:37:16 2008
@@ -0,0 +1,58 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.apache.commons.math.genetics;
+
+/**
+ * A pair of {@link Chromosome} objects.
+ */
+public class ChromosomePair {
+ /** the first chromosome in the pair. */
+ private Chromosome first;
+
+ /** the second chromosome in the pair. */
+ private Chromosome second;
+
+ /**
+ * Create a chromosome pair.
+ *
+ * @param c1 the first chromosome.
+ * @param c2 the second chromosome.
+ */
+ public ChromosomePair(Chromosome c1, Chromosome c2) {
+ super();
+ first = c1;
+ second = c2;
+ }
+
+ /**
+ * Access the first chromosome.
+ *
+ * @return the first chromosome.
+ */
+ public Chromosome getFirst() {
+ return first;
+ }
+
+ /**
+ * Access the second chromosome.
+ *
+ * @return the second chromosome.
+ */
+ public Chromosome getSecond() {
+ return second;
+ }
+}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java?rev=643027&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/CrossoverPolicy.java Mon Mar 31 08:37:16 2008
@@ -0,0 +1,32 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.apache.commons.math.genetics;
+
+/**
+ * Policy used to create a pair of new chromosomes by performing a crossover
+ * operation on a source pair of chromosomes.
+ */
+public interface CrossoverPolicy {
+ /**
+ * Perform a crossover operation on the given chromosomes.
+ *
+ * @param first the first chromosome.
+ * @param second the second chromosome.
+ * @return the pair of new chromosomes that resulted from the crossover.
+ */
+ ChromosomePair crossover(Chromosome first, Chromosome second);
+}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java?rev=643027&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Fitness.java Mon Mar 31 08:37:16 2008
@@ -0,0 +1,20 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.apache.commons.math.genetics;
+
+public interface Fitness extends Comparable {
+}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java?rev=643027&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/GeneticAlgorithm.java Mon Mar 31 08:37:16 2008
@@ -0,0 +1,181 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.apache.commons.math.genetics;
+
+/**
+ * Implementation of a genetic algorithm. All factors that govern the operation
+ * of the algorithm can be configured for a specific problem.
+ */
+public class GeneticAlgorithm {
+ /** the crossover policy used by the algorithm. */
+ private CrossoverPolicy crossoverPolicy;
+
+ /** the rate of crossover for the algorithm. */
+ private double crossoverRate;
+
+ /** the mutation policy used by the algorithm. */
+ private MutationPolicy mutationPolicy;
+
+ /** the rate of mutation for the algorithm. */
+ private double mutationRate;
+
+ /** the selection policy used by the algorithm. */
+ private SelectionPolicy selectionPolicy;
+
+ /**
+ * Evolve the given population. Evolution stops when the stopping condition
+ * is satisfied.
+ *
+ * @param initial the initial, seed population.
+ * @param condition the stopping condition used to stop evolution.
+ * @return the population that satisfies the stopping condition.
+ */
+ public Population evolve(Population initial, StoppingCondition condition) {
+ Population current = initial;
+ while (!condition.isSatisfied(current)) {
+ current = nextGeneration(current);
+ }
+ return current;
+ }
+
+ /**
+ * Access the crossover policy.
+ *
+ * @return the crossover policy.
+ */
+ private CrossoverPolicy getCrossoverPolicy() {
+ return crossoverPolicy;
+ }
+
+ /**
+ * Access the crossover rate.
+ *
+ * @return the crossover rate.
+ */
+ private double getCrossoverRate() {
+ return crossoverRate;
+ }
+
+ /**
+ * Access the mutation policy.
+ *
+ * @return the mutation policy.
+ */
+ private MutationPolicy getMutationPolicy() {
+ return mutationPolicy;
+ }
+
+ /**
+ * Access the mutation rate.
+ *
+ * @return the mutation rate.
+ */
+ private double getMutationRate() {
+ return mutationRate;
+ }
+
+ /**
+ * Access the selection policy.
+ *
+ * @return the selection policy.
+ */
+ private SelectionPolicy getSelectionPolicy() {
+ return selectionPolicy;
+ }
+
+ /**
+ * Evolve the given population into the next generation.
+ *
+ * @param current the current population.
+ * @return the population for the next generation.
+ */
+ private Population nextGeneration(Population current) {
+ Population nextGeneration = current.nextGeneration();
+
+ while (nextGeneration.getPopulationSize() < nextGeneration
+ .getPopulationLimit()) {
+ // select parent chromosomes
+ ChromosomePair pair = getSelectionPolicy().select(current);
+
+ // apply crossover policy to create two offspring
+ if (Math.random() < getCrossoverRate()) {
+ pair = getCrossoverPolicy().crossover(pair.getFirst(),
+ pair.getSecond());
+ }
+
+ // apply mutation policy to first offspring
+ if (Math.random() < getMutationRate()) {
+ nextGeneration.addChromosome(getMutationPolicy().mutate(
+ pair.getFirst()));
+
+ if (nextGeneration.getPopulationSize() < nextGeneration
+ .getPopulationLimit()) {
+ // apply mutation policy to second offspring
+ nextGeneration.addChromosome(getMutationPolicy().mutate(
+ pair.getSecond()));
+ }
+ }
+ }
+
+ return nextGeneration;
+ }
+
+ /**
+ * Modify the crossover policy.
+ *
+ * @param value the new crossover policy.
+ */
+ public void setCrossoverPolicy(CrossoverPolicy value) {
+ this.crossoverPolicy = value;
+ }
+
+ /**
+ * Modify the crossover rate.
+ *
+ * @param value the new crossover rate.
+ */
+ public void setCrossoverRate(double value) {
+ this.crossoverRate = value;
+ }
+
+ /**
+ * Modify the mutation policy.
+ *
+ * @param value the new mutation policy.
+ */
+ public void setMutationPolicy(MutationPolicy value) {
+ this.mutationPolicy = value;
+ }
+
+ /**
+ * Modify the mutation rate.
+ *
+ * @param value the new mutation rate.
+ */
+ public void setMutationRate(double value) {
+ this.mutationRate = value;
+ }
+
+ /**
+ * Modify the selection policy.
+ *
+ * @param value the new selection policy.
+ */
+ public void setSelectionPolicy(SelectionPolicy value) {
+ this.selectionPolicy = value;
+ }
+}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java?rev=643027&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/MutationPolicy.java Mon Mar 31 08:37:16 2008
@@ -0,0 +1,30 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.apache.commons.math.genetics;
+
+/**
+ * Algorithm used to mutate a chrommosome.
+ */
+public interface MutationPolicy {
+
+ /**
+ * Mutate the given chromosome.
+ * @param original the original chromosome.
+ * @return the mutated chromomsome.
+ */
+ Chromosome mutate(Chromosome original);
+}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java?rev=643027&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/Population.java Mon Mar 31 08:37:16 2008
@@ -0,0 +1,52 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.apache.commons.math.genetics;
+
+/**
+ * A collection of chromosomes that facilitates generational evolution.
+ */
+public interface Population {
+ /**
+ * Access the current population size.
+ * @return the current population size.
+ */
+ int getPopulationSize();
+
+ /**
+ * Access the maximum population size.
+ * @return the maximum population size.
+ */
+ int getPopulationLimit();
+
+ /**
+ * Start the population for the next generation.
+ * @return the beginnings of the next generation.
+ */
+ Population nextGeneration();
+
+ /**
+ * Add the given chromosome to the population.
+ * @param chromosome the chromosome to add.
+ */
+ void addChromosome(Chromosome chromosome);
+
+ /**
+ * Access the fittest chromosome in this population.
+ * @return the fittest chromosome.
+ */
+ Chromosome getFittestChromosome();
+}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java?rev=643027&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/SelectionPolicy.java Mon Mar 31 08:37:16 2008
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.apache.commons.math.genetics;
+
+/**
+ * Algorithm used to select a chromosome pair from a population.
+ */
+public interface SelectionPolicy {
+ /**
+ * Select two chromosomes from the population.
+ * @param population the population from which the chromosomes are choosen.
+ * @return the selected chromosomes.
+ */
+ ChromosomePair select(Population population);
+}
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java?rev=643027&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/genetics/StoppingCondition.java Mon Mar 31 08:37:16 2008
@@ -0,0 +1,32 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.apache.commons.math.genetics;
+
+/**
+ * Algorithm used to determine when to stop evolution.
+ */
+public interface StoppingCondition {
+ /**
+ * Determine whether or not the given population satisfies the stopping
+ * condition.
+ *
+ * @param population the population to test.
+ * @return <code>true</code> if this stopping condition is met by the
+ * given population. <code>false</code> otherwise.
+ */
+ boolean isSatisfied(Population population);
+}