有关遗传算法的一个简单入门的例子（java语言实现）

遗传算法的java语言实现

摘要：本报告提出了一个能体现遗传算法原理的例子，并侧重于java语言的编程实现，结果较好地完成了算法的要求。基因遗传算法是一种灵感源于达尔文自然进化理论的启发式搜索算法。算法反映了自然选择的过程，即最适者被选定繁殖，并产生下一代。

引言：遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则。遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉、变异等运算对个体进行筛选，使得适应值大的个体被保留，适应值小的个体被淘汰。新的群体继承上一代的信息，又优于上一代，如此反复循环，直到满足结束条件，最后留下来的个体集中分布在最优解的周围，选择出最优个体作为问题的解。

算法设计背景：

给定一组五个基因，每一个基因可以保存一个二进制值 0 或 1。这里的适应度是基因组中 1 的数量。如果基因组内共有五个 1，则该个体适应度达到最大值。如果基因组内没有 1，那么个体的适应度达到最小值。该遗传算法希望最大化适应度，并提供适应度达到最大的个体所组成的群体。本例中，在交叉运算与突变运算之后，适应度最低的个体被新的，适应度最高的后代所替代。

算法原理：

自然选择的过程从选择群体中最适应环境的个体开始。后代继承了父母的特性，并且这些特性将添加到下一代中。如果父母具有更好的适应性，那么它们的后代将更易于存活。迭代地进行该自然选择的过程，最终，我们将得到由最适应环境的个体组成的一代。

遗传算法含以下五步：

1、初始化

2、计算适应度函数（个体评价）

3、选择运算

4、交叉运算

5、变异运算

初始化

该过程从种群的一组个体开始，且每一个体都是待解决问题的一个候选解。

个体以一组参数（变量）为特征，这些特征被称为基因，串联这些基因就可以组成染色体（问题的解）。

在遗传算法中，单个个体的基因组以字符串的方式呈现，通常我们可以使用二进制（1 和 0 的字符串）编码，即一个二进制串代表一条染色体串。因此可以说我们将基因串或候选解的特征编码在染色体中。

种群、染色体（个体）、基因的关系

计算适应度函数（个体评价）

个体评价利用适应度函数评估了该个体对环境的适应度（与其它个体竞争的能力）。每一个体都有适应度评分，个体被选中进行繁殖的可能性取决于其适应度评分。适应度函数值越大，解的质量就越高。适应度函数是遗传算法进化的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。

选择运算

选择运算的目的是选出适应性最好的个体，并使它们将基因传到下一代中。基于其适应度评分，我们选择多对较优个体（父母）。适应度高的个体更易被选中繁殖，即将较优父母的基因传递到下一代。

交叉运算

交叉运算是遗传算法中最重要的阶段。对每一对配对的父母，基因都存在随机选中的交叉点。

例如：

首先随机产生交叉点

父母间在交叉点之前互换产生子代

父母间交换基因，产生后代被添加到新种群中

变异运算

在某些形成的新后代中，它们的某些基因可能受到低概率变异因子的作用。这意味着二进制位串中的某些位可能会翻转。

变异运算可用于保持种群内的多样性，并防止过早收敛。

终止

在群体收敛的情况下（群体内不产生与前一代差异较大的后代）该算法终止。也就是说遗传算法提供了一组问题的解。

种群的规模恒定。新一代形成时，适应度最差的个体凋亡，为后代留出空间。这些阶段的序列被不断重复，以产生优于先前的新一代。

这一迭代过程的伪代码：

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

算法仿真结果：

Generation: 0 Fittest: 4

Generation: 1 Fittest: 5

Solution found in generation 1

Fitness: 5

Genes: 11111

从算法的仿真结果中可以看出，第0代（父母那一代），最大适应度为4，迭代到第1代得到结果，最大适应度为5，满足算法的终止条件，染色体中的基因为11111。

结束语：遗传算法只是放生类算法中的一种，本例使用java语言仿真了一类简单的遗传算法，遗传算法的应用十分广泛，之后又很多问题值得我们去学习研究。之后的学习过程中，希望能用MATLAB语言对更多的遗传算法进行仿真。

附件：（算法程序）

/*

* 给定一组五个基因，每一个基因可以保存一个二进制值 0 或 1。

* 这里的适应度是基因组中 1 的数量。

* 如果基因组内共有五个 1，则该个体适应度达到最大值。如果基因组内没有 1，那么个体的适应度达到最小值。

* 该遗传算法希望最大化适应度，并提供适应度达到最大的个体所组成的群体。

* 注意：本例中，在交叉运算与突变运算之后，适应度最低的个体被新的，适应度最高的后代所替代。

* */

/*

* 伪代码

* START

*Generate the initial population

*Compute fitness

*REPEAT

* Selection

* Crossover

* Mutation

* Compute fitness

*UNTIL population has converged

*STOP

* */

import java.util.Random;

//main class

public class SimpleGA

{

Population population = new Population();

Individual fittest = new Individual();

Individual secondFittest = new Individual();

int generationCount = 0;

//main method

public static void main(String[] args)

{

//Generate the initial population

Random rn = new Random();

SimpleGA ga = new SimpleGA(); //主类的实例化,对象为ga

// Initialize population

ga.population.initializePopulation(10); //种群中个体数量为10个

//Calculate fitness of each individual

ga.population.calculateFitness();

//Display the generation count and the fittest（显示种群代数并输出最大适应度为多少）

System.out.println("Generation: "+ ga.generationCount +" Fittest: "+ ga.population.fittest);

//While population gets an individual with maximum fitness(当某代种群获得最大适应度时终止循环)

while(ga.population.fittest < 5)

{

++ga.generationCount;

//Do selection

ga.selection();

//Do crossover

ga.crossOver();

//Do mutation under a random probability

if(rn.nextInt(5) < 3) //0.6的概率变异

{

ga.mutation();

}

//Add fittest offspring to population

ga.addFittestOffspring();

//Calculate the new fitness value

ga.population.calculateFitness();

System.out.println("Generation: "+ ga.generationCount+" "+"Fittest: "+ga.population.fittest);

}

//循环结束后，代表找到了最大适应度的种群

System.out.println("\nSolution found in generation "+ga.generationCount);

System.out.println("Fitness: "+ ga.population.getFittest().fitness);

System.out.print("Genes: ");

for(int i = 0; i < 5; i ++)

{

System.out.print(ga.population.getFittest().genes[i]);

}

System.out.println("\n");

}

//Selection

void selection()

{

//select the most fittest individual

fittest = population.getFittest();

}

//Crossover

void crossOver()

{

Random rn = new Random();

//Select a random crossover point

int crossOverPoint = rn.nextInt(population.individuals[0].genes.length);

//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].genes.length);

//Flip values at the mutation point

if(fittest.genes[mutationPoint] == 0)

{

fittest.genes[mutationPoint] = 1;

}

else

{

fittest.genes[mutationPoint] = 0;

}

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;

}

else

{

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 fittest 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[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); //产生【0 1】的随机数，也即【0 2）

}

fitness = 0;

}

//Calculate fitness

public void calcFitness()

{

fitness = 0;

for(int i = 0;i < 5; i ++)

{

if(genes[i] == 1)

{

fitness ++;

}

}

}

}

//Population class

class Population

{

Individual individuals[] = new Individual[10]; //个体数组的实例化

int fittest = 0;

//Initialize population

public void initializePopulation(int size)

{

for(int i = 0; i < individuals.length; i ++) //i < individuals.length?

{

individuals[i] = new Individual(); //匿名对象的使用

}

}

//Get the fittest individual

public Individual getFittest() //返回值是一个个体

{

//int maxFit = Integer.MIN_VALUE;

int maxFit = 0;

for(int i = 0; i < individuals.length; i ++)

{

if(individuals[maxFit].fitness <= 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(individuals[minFit].fitness >= 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(); //寻找最适应的个体

}

}