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.utils.Random;
022 import jenes.chromosome.IntegerChromosome;
023 import jenes.population.Individual;
024 import jenes.stage.operator.Mutator;
025
026 /**
027 * Tutorial showing how to implement problem specific operators.
028 * The problem faced in this example is the well known Tavel Salesman Problem (TSP)
029 *
030 * This class implements a specific mutations aimed at preserving permutations.
031 *
032 * Algorithm description:
033 * Two random indexes, i1 and i2, are choosed; the order of the elements within the
034 * range [i1,i2] changes randomly. For example:
035 * <pre>
036 * i1=0; i2=3
037 * position: 0 1 2 3 4 5
038 * start_chrom: 5 2 1 4 6 3
039 * end_chrom: 2 5 4 1 6 3
040 * </pre>
041 *
042 * @author Luigi Troiano
043 *
044 * @version 1.0
045 * @since 1.0
046 */
047 public class TSPScrambleMutator extends Mutator<IntegerChromosome> {
048
049 public TSPScrambleMutator(double pMut) {
050 super(pMut);
051 }
052
053 @Override
054 protected void mutate(Individual<IntegerChromosome> t) {
055 int size = t.getChromosomeLength();
056 int index1,index2;
057 do{
058 index1 = Random.getInstance().nextInt(0,size);
059 index2 = Random.getInstance().nextInt(0,size);
060 }while(index2==index1);
061
062 int min,max;
063 if(index1<index2){
064 min=index1;
065 max=index2;
066 }else{
067 min=index2;
068 max=index1;
069 }
070
071 randomize(t.getChromosome(),min, max);
072 }
073
074 /**
075 * Randomizes the elements chromosome within the range [min,max]
076 * <p>
077 * @param chrom the individual to mutate
078 * @param min the lower bound
079 * @param max the upper bound
080 */
081 public void randomize(IntegerChromosome chrom, int min, int max) {
082
083 //we create a temporany array
084 int len = max-min+1;
085 int[] base = new int[len];
086
087 //we fill it with the elements within [min,max]
088 for(int i=0;i<len;i++)
089 base[i]= chrom.getValue(min+i);
090
091 //the loop ends when the temporany array is empty
092 for( int i = 0; len > 0; --len, ++i) {
093 //we choose a random position pos in the array and copy the element at pos in the chromosome
094 int pos = Random.getInstance().nextInt(0,len);
095 chrom.setValue(min+i,base[pos]);
096 //we removes the chosen element from the temporany array
097 for(int j=pos;j<(len-1);j++){
098 base[j]=base[j+1];
099 }
100 }
101 }
102 }
|
|
|
