HomeDigital EditionSys-Con RadioSearch Java Cd
Advanced Java AWT Book Reviews/Excerpts Client Server Corba Editorials Embedded Java Enterprise Java IDE's Industry Watch Integration Interviews Java Applet Java & Databases Java & Web Services Java Fundamentals Java Native Interface Java Servlets Java Beans J2ME Libraries .NET Object Orientation Observations/IMHO Product Reviews Scalability & Performance Security Server Side Source Code Straight Talking Swing Threads Using Java with others Wireless XML
 

"An Introduction To Genetic Algorithms"
Vol. 6, Issue 3, p. 62

	





Listing 1: TSPGene.java

package com.lacy.genetic.tsp;
import java.util.Properties;
import com.lacy.genetic.*;
public class TSPGene implements IGene
{
    private String m_description;
    private double m_x;
    private double m_y;


// Constructors
    public TSPGene() {}
    public TSPGene(Properties i_properties, int i_index) { 
        init(i_properties, i_index); }
    public TSPGene(String i_description, double i_x, double i_y)
    {
     this.m_description = i_description;
     this.m_x = i_x;
     this.m_y = i_y;
    }


// Method to initialize a gene from a properties file
    public void init(Properties i_props, int i_index)
    {
    setDescription(i_props.getProperty("gene." + i_index + 
        ".description"));
           setX((Double.valueOf(i_props.getProperty("gene." + i_index +".x")).doubleValue()));
    setY((Double.valueOf(i_props.getProperty("gene." + i_index + 
        ".y")).doubleValue()));
                                }


// Accessor/Settor methods
    public String getDescription() { return m_description; }
    public void setDescription(String i_description)
                                                { m_description = i_description; }
    public double getX() { return m_x; }
    public void setX(double i_x) { m_x = i_x; }
    public double getY() { return m_y; }
    public void setY(double i_y) { m_y = i_y; }


// Utility methods
    public IGene copy() { return new TSPGene(getDescription(),getX(), getY()); }
    public boolean equals(IGene i_gene)
    {
    return (i_gene.getDescription().equals(m_description));
    }
    public String toString() { return m_description; }
                                }



Listing 2: TSP Fitness Evaluation

// Returns the total distance traveled for the order of cities  //              
specified by this chromosome.


    public double getFitness()
    {
        if (m_fitness > 0.0)
            return m_fitness;


        double i_fitness = 0.0;


        for (int i = 0; i < m_genes.size(); i++)
        {
            TSPGene g1 = (TSPGene) m_genes.at(i);
            TSPGene g2 = null;
            if (i == (m_genes.size() - 1))
                        g2 = (TSPGene) m_genes.at(0);
            else
                        g2 = (TSPGene) m_genes.at(i+1);


            i_fitness += calcDistance(g1.getX(), g1.getY(), 
        g2.getX(), g2.getY());
        }


        m_fitness = i_fitness;


// Calculates the cartesian distance between two points specified
//              by points (x1, y1) and (x2, y2) using the Pythagorean Theorem.


    private static double calcDistance(double x1, double y1,
                                double x2, double y2)
    {
        double deltaXSquared = (x2 - x1) * (x2 - x1);
        double deltaYSquared = (y2 - y1) * (y2 - y1);


        return Math.pow(deltaXSquared + deltaYSquared , 0.5);
    }



Listing 3: Parent Tournament Selection

// Returns 2 IChromosome objects using tournament selection
    protected IChromosome[] selectParents(int i_tournamentSize)
    {
        IChromosome[] parents = new IChromosome[2];
        Array gladiators = new Array(i_tournamentSize);


// pick a random spot within the population
        int startIndex = GeneticAlgorithmUtils.getRandomInt(0, 
        m_population.size() - i_tournamentSize);


// get as many chromosomes as specified by tournament size
        for (int i = startIndex; i < (startIndex + 
        i_tournamentSize); i++)
        {
          gladiators.put(i - startIndex, m_population.at(i));
        }


// sort the sub-population by fitness
        sort(gladiators);


// return the best two
        parents[0] = (IChromosome) gladiators.at(0);
        parents[1] = (IChromosome) gladiators.at(1);


        return parents;
                                    }



Listing 4: Crossover

/** Performs a crossover with this chromosome and the one specified in the argument. 
Returns two children chromosomes while preserving the uniqueness of genes in the chromosomes, 
meaning that all genes will be represented once and only once in the chromosome. */


public IChromosome[] crossover(IChromosome i_chromosome, double i_crossoverRate


   {
   int size = this.getSize();
   IChromosome mom = this.copy();
   IChromosome dad = i_chromosome.copy();
   IChromosome[] children = new IChromosome[2];
   double random=GeneticAlgorithmUtils.getRandomDouble(1.0);


   if (random < i_crossoverRate)
   {
   int crossoverPoint=GeneticAlgorithmUtils.getRandomInt(1,size-1);


   IGene[] child1begin=mom.getGenes(0, crossoverPoint-1);
   IGene[] child1end=getEndGenes(child1begin,
        dad.getGenes(0,size-1));
   IGene[] child2begin = dad.getGenes(0, crossoverPoint - 1);
   IGene[] child2end = getEndGenes(child2begin, mom.getGenes(0, 
                        size -1));
   children[0] = new TSPChromosome(child1begin, child1end);
   children[1] = new TSPChromosome(child2begin, child2end);


   return children;
        }


// if no crossover, children are same as parents
        children[0] = mom;
        children[1] = dad;


        return children;
    }



Listing 5: Mutation

/** Mutates this chromosome by randomly selecting two genes and swapping them 
Uses the mutation rate specified by i_mutationRate */
    public void mutate(double i_mutationRate)
    {
    double random = GeneticAlgorithmUtils.getRandomDouble(1.0);


    if (random < i_mutationRate)
     {
     int size = this.getSize();


     int r1 = GeneticAlgorithmUtils.getRandomInt(0, size - 1);
     int r2 = GeneticAlgorithmUtils.getRandomInt(0, size - 1);


     IGene g1 = (IGene) this.getGene(r1);
     IGene g2 = (IGene) this.getGene(r2);


        m_genes.put(r2, g1);
     m_genes.put(r1, g2);
        }
    }



Listing 6: Insertion

/** Method to insert children into the population, preserving the m_elitism best from the previous generation */


protected void insert(IChromosome[] i_children, int i_elitism)
    {
        sort(m_population);


        for (int i = i_elitism; i < m_population.size(); i++)
            m_population.put(i, i_children[i - i_elitism]);


    }


  
 
 

All Rights Reserved
Copyright ©  2004 SYS-CON Media, Inc.
  E-mail: [email protected]

Java and Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. SYS-CON Publications, Inc. is independent of Sun Microsystems, Inc.