Auto Byte

Science AI

# 遗传算法的基本概念和实现（附 Java 实现案例）

#### 自然选择的概念

1. 初始化
2. 个体评价（计算适应度函数）
3. 选择运算
4. 交叉运算
5. 变异运算

#### 案例实现

`STARTGenerate the initial populationCompute fitnessREPEAT    Selection    Crossover    Mutation    Compute fitnessUNTIL population has convergedSTOP`

Java 中的示例实现

`import java.util.Random;/** * * @author Vijini *///Main classpublic class SimpleDemoGA {    Population population = new Population();    Individual fittest;    Individual secondFittest;    int generationCount = 0;    public static void main(String[] args) {        Random rn = new Random();                SimpleDemoGA demo = new SimpleDemoGA();                //Initialize population        demo.population.initializePopulation(10);                //Calculate fitness of each individual        demo.population.calculateFitness();                System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);        //While population gets an individual with maximum fitness        while (demo.population.fittest < 5) {            ++demo.generationCount;                        //Do selection            demo.selection();                        //Do crossover            demo.crossover();                        //Do mutation under a random probability            if (rn.nextInt()%7 < 5) {                demo.mutation();            }                        //Add fittest offspring to population            demo.addFittestOffspring();                        //Calculate new fitness value             demo.population.calculateFitness();                        System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);        }        System.out.println("\nSolution found in generation " + demo.generationCount);        System.out.println("Fitness: "+demo.population.getFittest().fitness);        System.out.print("Genes: ");        for (int i = 0; i < 5; i++) {            System.out.print(demo.population.getFittest().genes[i]);        }        System.out.println("");    }    //Selection    void selection() {                //Select the most fittest individual        fittest = population.getFittest();                //Select the second most fittest individual        secondFittest = population.getSecondFittest();    }    //Crossover    void crossover() {        Random rn = new Random();                //Select a random crossover point        int crossOverPoint = rn.nextInt(population.individuals[0].geneLength);        //Swap values among parents        for (int i = 0; i < crossOverPoint; i++) {            int temp = fittest.genes[i];            fittest.genes[i] = secondFittest.genes[i];            secondFittest.genes[i] = temp;        }    }    //Mutation    void mutation() {        Random rn = new Random();                //Select a random mutation point        int mutationPoint = rn.nextInt(population.individuals[0].geneLength);        //Flip values at the mutation point        if (fittest.genes[mutationPoint] == 0) {            fittest.genes[mutationPoint] = 1;        } else {            fittest.genes[mutationPoint] = 0;        }        mutationPoint = rn.nextInt(population.individuals[0].geneLength);        if (secondFittest.genes[mutationPoint] == 0) {            secondFittest.genes[mutationPoint] = 1;        } else {            secondFittest.genes[mutationPoint] = 0;        }    }    //Get fittest offspring    Individual getFittestOffspring() {        if (fittest.fitness > secondFittest.fitness) {            return fittest;        }        return secondFittest;    }    //Replace least fittest individual from most fittest offspring    void addFittestOffspring() {                //Update fitness values of offspring        fittest.calcFitness();        secondFittest.calcFitness();                //Get index of least fit individual        int leastFittestIndex = population.getLeastFittestIndex();                //Replace least fittest individual from most fittest offspring        population.individuals[leastFittestIndex] = getFittestOffspring();    }}//Individual classclass Individual {    int fitness = 0;    int[] genes = new int[5];    int geneLength = 5;    public Individual() {        Random rn = new Random();        //Set genes randomly for each individual        for (int i = 0; i < genes.length; i++) {            genes[i] = rn.nextInt() % 2;        }        fitness = 0;    }    //Calculate fitness    public void calcFitness() {        fitness = 0;        for (int i = 0; i < 5; i++) {            if (genes[i] == 1) {                ++fitness;            }        }    }}//Population classclass Population {    int popSize = 10;    Individual[] individuals = new Individual[10];    int fittest = 0;    //Initialize population    public void initializePopulation(int size) {        for (int i = 0; i < individuals.length; i++) {            individuals[i] = new Individual();        }    }    //Get the fittest individual    public Individual getFittest() {        int maxFit = Integer.MIN_VALUE;        for (int i = 0; i < individuals.length; i++) {            if (maxFit <= individuals[i].fitness) {                maxFit = i;            }        }        fittest = individuals[maxFit].fitness;        return individuals[maxFit];    }    //Get the second most fittest individual    public Individual getSecondFittest() {        int maxFit1 = 0;        int maxFit2 = 0;        for (int i = 0; i < individuals.length; i++) {            if (individuals[i].fitness > individuals[maxFit1].fitness) {                maxFit2 = maxFit1;                maxFit1 = i;            } else if (individuals[i].fitness > individuals[maxFit2].fitness) {                maxFit2 = i;            }        }        return individuals[maxFit2];    }    //Get index of least fittest individual    public int getLeastFittestIndex() {        int minFit = 0;        for (int i = 0; i < individuals.length; i++) {            if (minFit >= individuals[i].fitness) {                minFit = i;            }        }        return minFit;    }    //Calculate fitness of each individual    public void calculateFitness() {        for (int i = 0; i < individuals.length; i++) {            individuals[i].calcFitness();        }        getFittest();    }}`