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