jenes.tutorials.problem3.TSPCityCenteredCrossover.java

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         forint 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         forint i = 0; i < size; ++i ) {
136             if( chrom.getValue(i) == city )
137                 return i;
138         }
139         return -1;
140     }
141     
142 }
Comments