evolver.java

来自「This program is using Genetic Algorithm 」· Java 代码 · 共 803 行 · 第 1/2 页

                    }
                }
                
                if (!inChild)
                    temp.addElement(g);
            }
            
            Gene[] childend = new Gene[temp.size()];
            for (int k = 0; k < temp.size(); k++)
            {
                childend[k] = (Gene) temp.elementAt(k);
            }
            
            return childend;
    }
    
    /** Mutates this chromosome by randomly selecting two genes and swapping them.
        Uses the default mutation rate of 0.05. */
    public void mutate() {  mutate(Chromosome.DEFAULT_MUTATION_RATE); }
    
    /** 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 = GAUtils.getRandomDouble(1.0);
        
        if (random < i_mutationRate)	 
        {
            int size = this.getSize();
            
            int r1 = GAUtils.getRandomInt(0, size - 1);
            int r2 = GAUtils.getRandomInt(0, size - 1);
            
            //r1, r2 are index of gene in chrmosome
            Gene g1 = (Gene) this.getGene(r1);
            Gene g2 = (Gene) this.getGene(r2);
            
            //put gene in r1 to r2, put gene in r2 to r1
            m_genes.set(r2, g1);
            m_genes.set(r1, g2);
        }
    }
    
    /** 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++)  
        {
            Gene g1 = (Gene) m_genes.get(i);
            Gene g2 = null;
            if (i == (m_genes.size() - 1))		//if reach the end of the chromosome
                g2 = (Gene) m_genes.get(0);
            else
                g2 = (Gene) m_genes.get(i+1);
            
            i_fitness += calcDistance(g1.getX(), g1.getY(), g2.getX(), g2.getY());
        }
        
        m_fitness = i_fitness;
        
        return m_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);
    }
    
    /** Returns the number of genes in this chromosome */
    public int getSize() { return m_genes.size(); }	 
    
    /** Sets the gene at the specified index to i_gene */
    public void setGene(int i_index, Gene i_gene) { m_genes.set(i_index, i_gene); }
    
    /** Sets the genes for this chromosome to i_genes */
    public void setGenes(ArrayList i_genes) { m_genes = i_genes; } 
    
    /** Sets the genes for this chromosome to those contained in i_genes */
    public void setGenes(Gene[] i_genes)			 
    {
        for (int i = 0; i < i_genes.length; i++)
        {
            m_genes.add(i_genes[i]);
        }
    }
    
    /** Sets the genes for this chromosome to those contained in i_beingGenes and i_endGenes */
    public void setGenes(Gene[] i_beginGenes, Gene[] i_endGenes)  
    {
        for (int i = 0; i < i_beginGenes.length; i ++)
        {
            m_genes.add(i_beginGenes[i]);
        }
        
        for (int j = 0; j < i_endGenes.length; j ++)
        {
            m_genes.add(i_endGenes[j]);
        }
    }
    
    /** Returns the gene at the specified index */
    public Gene getGene(int i_index) { return ((Gene) m_genes.get(i_index)).copy(); }
    
    /** Returns an array of all genes of this chromosome */
    public Gene[] getGenes() { return getGenes(0, m_genes.size() - 1); }
    
    /** Returns the genes between and including the specified indices */
    public Gene[] getGenes(int i_beginIndex, int i_endIndex) 
    {
    	Gene[] i_genes = new Gene[i_endIndex - i_beginIndex + 1];
        
        for (int i = 0; i < (i_endIndex - i_beginIndex + 1); i++)
        {
            i_genes[i] = ((Gene) m_genes.get(i_beginIndex + i)).copy();
        }
        
        return i_genes;
    }
    
    /** Replaces existing genes beginning at index */
    public void replaceGenes(Gene[] i_genes, int i_index)
    {
        for (int i = i_index; i < (i_genes.length + i_index); i++)
        {
            m_genes.set(i, i_genes[i - i_index]);	
        }
    }
    
    
    /** Returns a copy of this chromosome */
    public Chromosome copy() { return new Chromosome(getGenes()); }
    
    /**
     * Examines a chromosome one gene at a time, in order, to determine if they are equal.
     * If so, returns true.  Otherwise, returns false.
     */
    public boolean equals(Chromosome c)
    {
        for (int i = 0; i < m_genes.size(); i++)
        {
        	Gene myGene = (Gene) m_genes.get(i);
        	Gene yourGene = c.getGene(i);
            
            if (myGene.equals(yourGene))
                continue;
            else
                return false;
        }
        
        return true;
    }
    
    /** Returns a String representation of this chromosome */
    public String toString()
    {
        StringBuffer sb = new StringBuffer();
        
        sb.append("Fitness = " + this.m_fitness + "\n");
        
        for (int i = 0; i < m_genes.size(); i++)
        {
            sb.append("\n");
            sb.append(m_genes.get(i));
        }
        
        return sb.toString();
    }
}


class Population{
    private int m_offspringPerGeneration;
    private int m_populationSize;
    private int m_initialPopulationSize;
    private int m_elitism;
    private int m_tournamentSize;
    private int m_chromosomeSize;
    private double m_crossoverRate;
    private double m_mutationRate;
       
    static final int DEFAULT_OFFSPRINGPERGENERATION=90;
    static final int DEFAULT_POPULATIONSIZE=100;
    static final int DEFAULT_INITIALPOPULATIONSIZE=1000;
    static final int DEFAULT_ELITISM=10;
    static final int DEFAULT_TOURNAMENT_SIZE=6;
    //static final int DEFAULT_CHROMOSOMESIZE=30;								//shoule get dynamically
    static final double DEFAULT_CROSSOVER_RATE = 0.90;
    static final double DEFAULT_MUTATION_RATE = 0.10;
    
    
    private ArrayList m_population;
    private Comparator m_comparator = new MoreFitChromosomeHasSmallerFitness();
    
    // Constructor
    public Population(int m_chromosomeSize, int m_populationSize, double m_crossoverRate, double m_mutationRate,GenePool i_genePool) { 
    	init(m_chromosomeSize, m_populationSize, m_crossoverRate, m_mutationRate, i_genePool); }
    public Population(int geneNbr, GenePool i_genePool) { init(geneNbr, i_genePool); }
    
    /** Method to initialize a population from a properties file */
    public void init(int chromosomeSize, int populationSize, double crossoverRate, double mutationRate, GenePool i_genePool)				//从config中读参数& initial chromosomes
    {
        m_offspringPerGeneration = DEFAULT_OFFSPRINGPERGENERATION;
        m_populationSize = populationSize;
        m_initialPopulationSize = DEFAULT_INITIALPOPULATIONSIZE;
        m_elitism = DEFAULT_ELITISM;
        m_crossoverRate = crossoverRate;
        m_mutationRate = mutationRate;
        m_tournamentSize = DEFAULT_TOURNAMENT_SIZE;
        m_chromosomeSize = chromosomeSize;
        
        // create initial population									//choose best pops from initial pops
        ArrayList m_initialPopulation = new ArrayList(m_initialPopulationSize); //arr_initialPop
        for (int i = 0; i < m_initialPopulationSize; i++)				//population randoms chromosomes here!!!!!!!!
            m_initialPopulation.add(i, i_genePool.createRandomChromosome(m_chromosomeSize));
        
        // sort initial population
        sort(m_initialPopulation);										//use java.util.Collections.sort(List list), ascending order
        
        // keep the best
        m_population = new ArrayList(m_populationSize);						//arr_pop <- arr_initialPop
        for (int i = 0; i < m_populationSize; i++)
            m_population.add(i, m_initialPopulation.get(i));
        
        // mix em up													//use java.util.Collections.shuffle(List list) 
        java.util.Collections.shuffle(m_population);
    }
    
    public void init(int geneNbr, GenePool i_genePool)				//read config & initial chromosomes
    {
        m_offspringPerGeneration = DEFAULT_OFFSPRINGPERGENERATION;
        m_populationSize = DEFAULT_POPULATIONSIZE;
        m_initialPopulationSize = DEFAULT_INITIALPOPULATIONSIZE;
        m_elitism = DEFAULT_ELITISM;
        m_crossoverRate = DEFAULT_CROSSOVER_RATE;
        m_mutationRate = DEFAULT_MUTATION_RATE;
        m_tournamentSize = DEFAULT_TOURNAMENT_SIZE;
        m_chromosomeSize = geneNbr;
        
        // create initial population									//choose best pops from initial pops
        ArrayList m_initialPopulation = new ArrayList(m_initialPopulationSize); //arr_initialPop
        for (int i = 0; i < m_initialPopulationSize; i++)				//population randoms chromosomes here!!!!!!!!
            m_initialPopulation.add(i, i_genePool.createRandomChromosome(m_chromosomeSize));  
        
        // sort initial population
        sort(m_initialPopulation);										//use java.util.Collections.sort(List list), ascending order
        
        // keep the best
        m_population = new ArrayList(m_populationSize);						//arr_pop <- arr_initialPop
        for (int i = 0; i < m_populationSize; i++)
            m_population.add(i, m_initialPopulation.get(i));								 
        
        // mix em up													//use java.util.Collections.shuffle(List list) 
        java.util.Collections.shuffle(m_population);
    }
    
    /** Method that performs the reproduction cycle for a single generation */
    public void reproduce()
    {
    	java.util.Collections.shuffle(m_population);								//use java.util.Collections.shuffle(List list) 
                
        Chromosome[] children = new Chromosome[m_offspringPerGeneration]; //wrong here? = new Chromosome()
        																	//here m_offspringPerGeneration == 90
        
        // iterate i_offspring/2 times because there are 2 offspring per crossover
        for (int i = 0; i < m_offspringPerGeneration/2 ; i++)				 
        {
        	Chromosome[] parents = selectParents(m_tournamentSize);		//here m_tournamentSize == 6
            																 
        	Chromosome[] offspring = parents[0].crossover(parents[1], m_crossoverRate);
            
            // mutate the children Chromosomes and insert into population, should always be 2
            for (int j = 0; j < offspring.length; j++)
            {
                offspring[j].mutate(m_mutationRate);
                children[(i*2)+j] = offspring[j];
            }            
        }
        
        insert(children);
    }
    
    /** Returns 2 IChromosome objects using tournament selection */
    protected Chromosome[] selectParents(int i_tournamentSize)
    {
    	Chromosome[] parents = new Chromosome[2];
        ArrayList gladiators = new ArrayList(i_tournamentSize);
        
        // pick a random spot within the population
        int startIndex = GAUtils.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.add(i - startIndex, m_population.get(i));			 
        }																	 
        
        // sort the sub-population by fitness
        sort(gladiators);												 
        
        // return the best two
        parents[0] = (Chromosome) gladiators.get(0);
        parents[1] = (Chromosome) gladiators.get(1);
        
        return parents;
    } 
    
    // Methods to insert children into the population, perserving the m_elitism best from the previous generation
    protected void insert(Chromosome[] i_children) { insert(i_children, m_elitism); }
    protected void insert(Chromosome[] i_children, int i_elitism)			//here i_elitism == 10
    {
        sort(m_population);
        
        for (int i = i_elitism; i < m_population.size(); i++)
            m_population.set(i, i_children[i - i_elitism]);
        
    }
    
    // Methods to sort a (sub) population
    protected void sort() { sort(m_population); } 
    protected void sort(ArrayList i_population) { java.util.Collections.sort(i_population, m_comparator); }
    
    /** Returns a String representation of the population parameters */
    public String toString()
    {
        StringBuffer sb = new StringBuffer();
        
        sb.append("Initial Population Size = " + this.m_initialPopulationSize + "\n");
        sb.append("Population Size = " + this.m_populationSize + "\n");
        sb.append("Offspring/Generation = " + this.m_offspringPerGeneration + "\n");
        sb.append("Crossover Rate = " + this.m_crossoverRate + "\n");
        sb.append("Mutation Rate = " + this.m_mutationRate + "\n");
        sb.append("Elitism Factor = " + this.m_elitism + "\n");
        sb.append("Selection Tournament Size = " + this.m_tournamentSize + "\n");
        sb.append("Initial Population Size = " + this.m_initialPopulationSize + "\n");
        
        return sb.toString();
    }
    
    /** Returns the most fit chromosome in the population */
    public Chromosome getBestChromosome()
    {
        sort();
        return (Chromosome) m_population.get(0);
    }
    
    /** Inner class used by the JGL Sorting class to compare chromosomes */
    private final class MoreFitChromosomeHasSmallerFitness implements Comparator  
    {
        public int compare(Object first, Object second)
        {
        	Chromosome c1 = (Chromosome) first;
        	Chromosome c2 = (Chromosome) second;
        
            if (c1.getFitness() < c2.getFitness())
                return -1;
            if (c1.getFitness() == c2.getFitness())
            	return 0;
            else
                return 1;
        }
    };
}
 

class GAUtils{
    private static Random m_random = new Random();
            
    /** 
     * Returns a random double between 0 and i_high
     */
    public static double getRandomDouble(double i_high) {
        return m_random.nextDouble() * i_high;
    } 
    
    /**
     * Returns a random double between i_low and i_high
     */
    public static double getRandomDouble(double i_low, double i_high){
        return getRandomDouble(i_high - i_low) + i_low;
    } 
    
    /**
     * Returns a random int between (and including i_lo and i_hi)
     */
    public static int getRandomInt(int i_lo, int i_hi){        
        return (int) Math.floor(m_random.nextDouble() * (i_hi - i_lo + 1)) + i_lo;
    }
    
}