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.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 * @author Pierpaolo Lombardi
044 *
045 * @version 1.0
046 * @since 1.0
047 */
048 public class TSPScrambleMutator extends Mutator<IntegerChromosome> {
049
050 public TSPScrambleMutator(double pMut) {
051 super(pMut);
052 }
053
054 @Override
055 protected void mutate(Individual<IntegerChromosome> t) {
056 int size = t.getChromosomeLength();
057 int index1,index2;
058 do{
059 index1 = Random.getInstance().nextInt(0,size);
060 index2 = Random.getInstance().nextInt(0,size);
061 }while(index2==index1);
062
063 int min,max;
064 if(index1<index2){
065 min=index1;
066 max=index2;
067 }else{
068 min=index2;
069 max=index1;
070 }
071
072 randomize(t.getChromosome(),min, max);
073 }
074
075 /**
076 * Randomizes the elements chromosome within the range [min,max]
077 * <p>
078 * @param chrom the individual to mutate
079 * @param min the lower bound
080 * @param max the upper bound
081 */
082 public void randomize(IntegerChromosome chrom, int min, int max) {
083
084 //we create a temporany array
085 int len = max-min+1;
086 int[] base = new int[len];
087
088 //we fill it with the elements within [min,max]
089 for(int i=0;i<len;i++)
090 base[i]= chrom.getValue(min+i);
091
092 //the loop ends when the temporany array is empty
093 for( int i = 0; len > 0; --len, ++i) {
094 //we choose a random position pos in the array and copy the element at pos in the chromosome
095 int pos = Random.getInstance().nextInt(0,len);
096 chrom.setValue(min+i,base[pos]);
097 //we removes the chosen element from the temporany array
098 for(int j=pos;j<(len-1);j++){
099 base[j]=base[j+1];
100 }
101 }
102 }
103 }
|
|
|
