1. 简介

-. 遗传算法 是受达尔文自然选择进化论的激发下，提出的一个 寻找最优解 的算法。该算法反映了自然选择的过程，即选择最合适的个体进行繁殖，以产生下一代的后代。

2. 自然选择的概念

自然选择的过程开始于从一个种群中寻找最优个体，他们产生的后代继承了父母的特性，并将这些特性遗传给下一代。如果他们的父母有更好的特性，他们的后代将有比他们父母更好的特性以便他们有更大的机会生存下去。这个过程会不断地迭代直至最后找到一个最适合生存地个体。

这个概念能够应用到一个寻找问题。我们考虑一个问题的一组解决方法并从中选择最好的一组解决方案。

在遗传算法中考虑了 5 个步骤：

初始化种群 （Initial population）最优函数 （Fitness function）选择 （Selection）交换 （父母的特性（基因）交换 Crossover）突变 （Mutation ）

3. 初始化种群 （Initial population）

这个过程开始于一个称为种群 Population 的一组个体的集合。其中每一个个体是对这个问题你想要的解决办法。

一个个体的特性用一组参数（变量）来表征，也就是我们所知的基因 (Genes)，基因被连成一串来组成一条染色体（Chmorosome），也就是解决方案(Solution)。

在一个遗传算法中，一个个体的基因组合使用一个字符串来表示，比方说字母表——“CGGTTAGGTTAGCAATAACATCTAAGAGAAAAA”。然而很多时候，二进制数值会被使用来表示这个字符串（0 和 1）。我们说在这个染色体中编码（encode）基因。

4. 适应度函数 （Fitness Function）

这个适应度函数（Fitness Function）决定了这个个体的适应能力（一个个体跟另外的个体比较后得出的能力高低）。它给出了每个个体的健康评估（fitness score）。个体被选择作为繁衍下一代的可能性是取决于对个体的健康评估（fitness score）。

5. 选择 （Selection）

选择阶段的概念是指选择最优的基因的个体并让他们把基因传给下一代。

一对个体（父母 parents）被选择是基于他们的健康评估（fitness score），高评估值的个体有更大的机会被选作为繁衍后代。

6. 交换 （父母的特性（基因）交换 Crossover）

Crossover 在遗传算法里是最重要的一个阶段。每一对父母都需要交配（mate），一个基因交换点（crossver point）会在基因中随机选定。

比如：考虑到 crossover point 为 3，那么如下图所示：

后代是通过交换父母(A1 A2)之间的基因产生的，直到达到 crossver point。

新的后(A5 A6)能够加进后代中：

7. 突变 （mutation）

在某些新形成的后代中，它们的一些基因会以低随机概率发生突变（mutation）。这意味着位串中的一些位可以被翻转。

突变 (mutation) 的发生是为了保持种群内的多样性并防止过早收敛 (convergence)。

8. 终止 （Termination）

如果种群已经收敛 (不会产生与上一代显著不同的后代)，算法将终止。那么，就说遗传算法为我们的问题提供了一套解决方案。

9. 解释 （Comments）

人口的规模是固定的。随着新一代的形成，最不适合的个体死亡，为新的后代提供空间。

重复这个阶段的序列，在每一代中产生比上一代更好的个体。

10. 伪代码 （Pseudocode）

START Generate the initial population Compute fitness REPEAT Selection Crossover Mutation Compute fitness UNTIL population has converged STOP

11. 一个例子的应用，使用 Java 实现

下面是一个用Java实现遗传算法的例子。您可以随意使用这些代码。给定一组5个基因，每个基因可以保存一个二进制值0和1。适应度值 (fitness value) 是根据基因组中存在的 1 的数量来计算的。如果有五个 1，那么它拥有最大的适合度 (maximum fitness)。如果没有 1，那么它的适合度最小 (minimum fitness)。该遗传算法试图最大化适应度函数 (fitness function)，以提供一个由最适个体组成的种群，比如说：个体的基因有 5 个 1。注:在本例中，在交叉 （crossover）和变异 (mutation) 之后，最不适合的个体从新的最适合的后代 (offspring) 中被取代。import java.util.Random; /** * * @author Vijini */ //Main class public 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 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 //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 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 class class Individual { int fitness = 0; int[] genes = new int[10]; int geneLength = 10; public Individual() { Random rn = new Random(); //Set genes randomly for each individual for (int i = 0; i fitness = 0; for (int i = 0; i ++fitness; } } } } //Population class class Population { int popSize = 10; Individual[] individuals = new Individual[10]; int fittest = 0; //Initialize population public void initializePopulation(int size) { for (int i = 0; i int maxFit = Integer.MIN_VALUE; int maxFitIndex = 0; for (int i = 0; i maxFit = individuals[i].fitness; maxFitIndex = i; } } fittest = individuals[maxFitIndex].fitness; return individuals[maxFitIndex]; } //Get the second most fittest individual public Individual getSecondFittest() { int maxFit1 = 0; int maxFit2 = 0; for (int i = 0; i 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 minFitVal = Integer.MAX_VALUE; int minFitIndex = 0; for (int i = 0; i minFitVal = individuals[i].fitness; minFitIndex = i; } } return minFitIndex; } //Calculate fitness of each individual public void calculateFitness() { for (int i = 0; i