001 /*
002 * JENES
003 * A time asnd 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.old.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 * @author Pierpaolo Lombardi
054 *
055 * @version 1.4
056 * @since 1.0
057 */
058 public class TSPCityCenteredCrossover extends Crossover<IntegerChromosome>{
059
060 public TSPCityCenteredCrossover(double pCross) {
061 super(pCross);
062 }
063
064 /**
065 * Returns the number of chromosomes (i.e. 2) this operator entails.
066 */
067 @Override
068 public int spread() {
069 return 2;
070 }
071
072 private IntegerChromosome chrom_parent1 = null;
073 private IntegerChromosome chrom_parent2 = null;
074 /**
075 * This method implements the crossover operation.
076 *
077 * @param offsprings the chromosomes to be crossed.
078 */
079 protected void cross(Individual<IntegerChromosome> offsprings[]) {
080
081 IntegerChromosome chrom_child1 = offsprings[0].getChromosome();
082 IntegerChromosome chrom_child2 = offsprings[1].getChromosome();
083
084 if( chrom_parent1 == null ) {
085 chrom_parent1 = chrom_child1.clone();
086 chrom_parent2 = chrom_child2.clone();
087 } else {
088 chrom_parent1.setAs(chrom_child1);
089 chrom_parent2.setAs(chrom_child2);
090 }
091
092 final int size = chrom_child1.length();
093 if( chrom_child2.length() != size )
094 throw new AlgorithmException("Error: the two chromosomes are required to have the same length.");
095
096
097 //we choose a random city
098 int city = Random.getInstance().nextInt(0, size);
099
100 //i1, i2 are the positions of the city respectively in child1 and child2
101 int i1 = findPositionOf(city, chrom_child1);
102 int i2 = findPositionOf(city, chrom_child2);
103
104 int j1 = 0;
105 int j2 = 0;
106 for( int i = 0; i < size; ++i ) {
107 // get the city c1 in position i for parent1
108 int c1 = chrom_parent1.getValue(i);
109 // find the position of c1 in parent 2
110 int p2 = findPositionOf(c1, chrom_parent2);
111 // if the position is over the cross-point, it copies c1 in child2
112 if( p2 > i2 ) {
113 chrom_child2.setValue(i2 + (++j2), c1);
114 }
115
116 // similarly we process the other pair
117 int c2 = chrom_parent2.getValue(i);
118 int p1 = findPositionOf(c2, chrom_parent1);
119 if( p1 > i1 ) {
120 chrom_child1.setValue(i1 + (++j1), c2);
121 }
122 }
123 }
124
125 /**
126 * Finds the position of one specific city in the chromosome.
127 * <p>
128 * @param city the city to find
129 * @param chrom the chromosome to search
130 * @return the city position
131 */
132 private int findPositionOf(int city, IntegerChromosome chrom){
133 final int size = chrom.length();
134 for( int i = 0; i < size; ++i ) {
135 if( chrom.getValue(i) == city )
136 return i;
137 }
138 return -1;
139 }
140
141 }
|
|
|
