001 /*
002 * JENES
003 * A time and memory efficient Java library for genetic algorithms and more
004 * Copyright (C) 2011 Intelligentia srl
005 *
006 * This program is free software: you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation, either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * This program is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program. If not, see <http://www.gnu.org/licenses/>.
018 */
019 package jenes.tutorials.problem3;
020
021 import jenes.AlgorithmException;
022 import jenes.utils.Random;
023 import jenes.chromosome.IntegerChromosome;
024 import jenes.population.Individual;
025 import jenes.stage.operator.Crossover;
026
027 /**
028 * Tutorial showing how to implement problem specific operators.
029 * The problem faced in this example is the well known Tavel Salesman Problem (TSP)
030 *
031 * This class implements a specific crossover aimed at preserving permutations.
032 *
033 * Algorithm description:
034 * <pre>
035 * parent1 5 2 1 4 6 3 parent2 1 3 2 4 6 5
036 * child1 _ _ _ _ _ _ child2 _ _ _ _ _ _
037 *</pre>
038 * Step 1: a city is choosed randomly. We copy all the cities until the selected one from each parent to
039 * each child (parent1 in child1 and parent2 in child2)
040 * <pre>
041 * parent1 5 2 1 4 6 3 parent2 1 3 2 4 6 5
042 * child1 5 2 _ _ _ _ child2 1 3 2 _ _ _
043 * </pre>
044 * Step 2: we fill child1 getting missing elements from parent2; these ones will have the same parent2 order
045 * <pre>
046 * parent1 5 2 1 4 6 3 parent2 1 3 2 4 6 5
047 * child1 5 2 1 3 4 6 child2 1 3 2 5 4 6
048 *</pre>
049 *
050 * We repeat these steps for child2
051 *
052 * @author Luigi Troiano
053 *
054 * @version 2.0
055 * @since 1.0
056 */
057 public class TSPCityCenteredCrossover extends Crossover<IntegerChromosome>{
058
059 public TSPCityCenteredCrossover(double pCross) {
060 super(pCross);
061 }
062
063 /**
064 * Returns the number of chromosomes (i.e. 2) this operator entails.
065 */
066 @Override
067 public int spread() {
068 return 2;
069 }
070
071 private IntegerChromosome chrom_parent1 = null;
072 private IntegerChromosome chrom_parent2 = null;
073 /**
074 * This method implements the crossover operation.
075 *
076 * @param offsprings the chromosomes to be crossed.
077 */
078 protected void cross(Individual<IntegerChromosome> offsprings[]) {
079
080 IntegerChromosome chrom_child1 = offsprings[0].getChromosome();
081 IntegerChromosome chrom_child2 = offsprings[1].getChromosome();
082
083 if( chrom_parent1 == null ) {
084 chrom_parent1 = chrom_child1.clone();
085 chrom_parent2 = chrom_child2.clone();
086 } else {
087 chrom_parent1.setAs(chrom_child1);
088 chrom_parent2.setAs(chrom_child2);
089 }
090
091 final int size = chrom_child1.length();
092 if( chrom_child2.length() != size )
093 throw new AlgorithmException("Error: the two chromosomes are required to have the same length.");
094
095
096 //we choose a random city
097 int city = Random.getInstance().nextInt(0, size);
098
099 //i1, i2 are the positions of the city respectively in child1 and child2
100 int i1 = findPositionOf(city, chrom_child1);
101 int i2 = findPositionOf(city, chrom_child2);
102
103 int j1 = 0;
104 int j2 = 0;
105 for( int i = 0; i < size; ++i ) {
106 // get the city c1 in position i for parent1
107 int c1 = chrom_parent1.getValue(i);
108 // find the position of c1 in parent 2
109 int p2 = findPositionOf(c1, chrom_parent2);
110 // if the position is over the cross-point, it copies c1 in child2
111 if( p2 > i2 ) {
112 chrom_child2.setValue(i2 + (++j2), c1);
113 }
114
115 // similarly we process the other pair
116 int c2 = chrom_parent2.getValue(i);
117 int p1 = findPositionOf(c2, chrom_parent1);
118 if( p1 > i1 ) {
119 chrom_child1.setValue(i1 + (++j1), c2);
120 }
121 }
122 }
123
124 /**
125 * Finds the position of one specific city in the chromosome.
126 * <p>
127 * @param city the city to find
128 * @param chrom the chromosome to search
129 * @return the city position
130 */
131 private int findPositionOf(int city, IntegerChromosome chrom){
132 final int size = chrom.length();
133 for( int i = 0; i < size; ++i ) {
134 if( chrom.getValue(i) == city )
135 return i;
136 }
137 return -1;
138 }
139
140 }
|
|
|
