遗传算法使用Java实现

最近需要学习神经网络，对于神经网络问题的求解其中需要用到遗传算法，所以今天学习了一下遗传算法，主要参看了 http://blog.csdn.net/emiyasstar__/article/details/6938608这篇博客的文章，同时将其使用C++实现的程序用Java再次实现了一遍，不足之处还请指出多包涵

 

遗传算法：也称进化算法 。 遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识

 

遗传算法教科书上的步骤：
      1.评估每条染色体所对应个体的适应度。
      2.遵照适应度越高，选择概率越大的原则，从种群中选择两个个体作为父方和母方。
      3.抽取父母双方的染色体，进行交叉，产生子代。
      4.对子代的染色体进行变异。
      5.重复2，3，4步骤，直到新种群的产生。

 

 

我下面说下我所理解的遗传算法，我所理解的遗传算法其实就是“广撒网多捞鱼”,怎么讲？遗传算法一般是先确定初始的群体，群体的每个个体都有两部分组成：1，染色体，也就是基因序列，2，适应性函数 也就是进化能力 ，其中基因序列指的是在实际问题中的一些起主要决定作用的一些特征的编码，主要分为两种：二进制编码和浮点数编码，这种所谓的编码其实就是对应着该“个体”的特征值，而确定了特征编码之后，因为遗传算法还需要进行进化，那么就需要对个体的“适应环[size=medium]境的能力”进行考量，在实际问题中其实也就是距离真正最优解的度量。我理解这个部分的内容为“广撒网阶段”
      在确定初始群体之后，就需要进行选择和进化，其实是选择其中的优胜者得到下一代，选择是依据进化论的“物竞天择”理论，也就是适应度越好的个体越容易被选出来，在算法的实现过程中这一部分一般使用“转盘赌”算法实现，所谓“转盘赌”算法，比如现在有四个个体，适应度分别是3,6,9,12 ，那么选择下一代就相当于在一个四个区域的转盘上转指针，其中3的区域占3/(3+6+9+12)=10%，以此类推，当指针停在哪个区域上表示选中哪个个体，显然，适应度越高的个体越容易被选中，在编程中，一般使用这样的算法：
    第一步：选择一个介于0（本文讨论的内容适应度大多为正，因为为负的话这种转盘赌方法不适用）和总适应度的适应度，也就是可以描述为：rand(0,1)乘以总的适应度，
   第二步骤:将种群的所有个体的适应度进行累加，如果当加到某个个体的时候累加的适应度大于了第一步所得到的适应度，那么就将这个个体取出来
    其实有人会质疑，这种算法实现的转盘赌是不是真的是有效的，我不太清除如何使用使用数学概率推导说明，但是这种方法实现的转盘赌还是有一定道理的，直观的理解就是，假设在前N-1步到了比步骤一的数字小的累加和，那么第N步能够超越步骤一的累加和的数字肯定是偏向适应度大的 那个个体(没有数学上的证明，只是直观想像)
    好了，选择出杂交的后代接下来就是进行产生后代了，产生后代的过程过程其实是染色体交换和基因变异的过程，对于二进制编码而言，染色体交换是交换父母的一部分序列，基因变异是其中几个序列由1变成0或者0变为1的过程；对于浮点数编码的话，那么染色体交换是一样的（在下文的例子中间因为基因只有一个浮点数的编码，所以没有用到染色体交换），基因突变是指在原有的浮点数基础上加一点随机噪音（加一点变化步长）

交叉重组的过程可以用下图表示

 
                                       
 
   这样再循环就算是遗传算法了。

 

结合一个例子：求解 f=x*sin(10PI*x)+2在[0,4]之间的最大值


 
这个例子来源于这个博客：http://blog.csdn.net/emiyasstar__/article/details/6938608，题目的背景和步骤都在原博客里面交代的很清楚，这里我主要给出一个Java版本的实现过程：（本人对C++面向对象部分的编程不是很熟悉，所以使用Java实现）

 

阶梯思路是先随机在0-4之间选择一个种群，以横坐标作为其基因序列，以函数值作为其适应度，然后不断的选择-交叉重组-变异，去除适应度（函数值）低的留下适应度高的，然后不断迭代找到最优解

个体类：

package com.luchi.genetic;

import java.util.ArrayList;
import java.util.List;

/*
 * 基因载体类
 * */
public class Genome {
	
	
	private List<Double> genomeList=new ArrayList<Double>();  //存放基因序列
	private double fitness;  //适应度函数值
	public List<Double> getGenomeList() {
		return genomeList;
	}
	public void setGenomeList(List<Double> genomeList) {
		this.genomeList = genomeList;
	}
	public double getFitness() {
		return fitness;
	}
	public void setFitness(double fitness) {
		this.fitness = fitness;
	}
	public Genome(){
		super();
	}
	public Genome(List<Double> genomeList, double fitness) {
		super();
		this.genomeList = genomeList;
		this.fitness = fitness;
	}
	
}

 主要算法类：

package com.luchi.genetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

import javax.swing.plaf.synth.SynthSeparatorUI;

/*
 * 遗传算法
 * @author：luchi
 * @date:2015/12/9
 * @description：使用遗传算法求解最值问题
 * */
public class GeneticAlgorithm {
	
	//放置所有的种群基因信息
	private List<Genome> population=new ArrayList<Genome>();
	//种群数量信息
	private int popSize;
	//每条染色体总数目
	private int chromoLength;
	//种群总的适应度数值
	private double totalFitness;
	//种群最好的适应度
	private double bestFitness;
	//种群最坏的适应度
	private double worstFitness;
	//种群平均的适应度
	private double averageFitness;
	//最好的适应度的对应的染色体
	private Genome bestGenome;
	//基因突变概率
	private double mutationRate;
	//基因交叉概率
	private double crossoverRate;
	//遗传的代数(第几代)
	private int generation;
	//最大变异步长
	private double maxPerturbation;
	//种群适应度的范围,left为左，right为右边	
	private double leftPoint;
	private double rightPoint;
	//遗传最大的迭代次数
	private int iterNum;
	
	public int getIterNum() {
		return iterNum;
	}
	public void setIterNum(int iterNum) {
		this.iterNum = iterNum;
	}

	private Random random=new Random();
	private MathCalc mathCalc=new MathCalc();
	public List<Genome> getPopulation() {
		return population;
	}
	public void setPopulation(List<Genome> population) {
		this.population = population;
	}
	public int getPopSize() {
		return popSize;
	}
	public void setPopSize(int popSize) {
		this.popSize = popSize;
	}
	public int getChromoLength() {
		return chromoLength;
	}
	public void setChromoLength(int chromoLength) {
		this.chromoLength = chromoLength;
	}
	public double getTotalFitness() {
		return totalFitness;
	}
	public void setTotalFitness(double totalFitness) {
		this.totalFitness = totalFitness;
	}
	public double getBestFitness() {
		return bestFitness;
	}
	public void setBestFitness(double bestFitness) {
		this.bestFitness = bestFitness;
	}
	public double getWorstFitness() {
		return worstFitness;
	}
	public void setWorstFitness(double worstFitness) {
		this.worstFitness = worstFitness;
	}
	public double getAverageFitness() {
		return averageFitness;
	}
	public void setAverageFitness(double averageFitness) {
		this.averageFitness = averageFitness;
	}
	public Genome getBestGenome() {
		return bestGenome;
	}
	public void setBestGenome(Genome bestGenome) {
		this.bestGenome = bestGenome;
	}
	public double getMutationRate() {
		return mutationRate;
	}
	public void setMutationRate(double mutationRate) {
		this.mutationRate = mutationRate;
	}
	public double getCrossoverRate() {
		return crossoverRate;
	}
	public void setCrossoverRate(double crossoverRate) {
		this.crossoverRate = crossoverRate;
	}
	public int getGeneration() {
		return generation;
	}
	public void setGeneration(int generation) {
		this.generation = generation;
	}
	public double getMaxPerturbation() {
		return maxPerturbation;
	}
	public void setMaxPerturbation(double maxPerturbation) {
		this.maxPerturbation = maxPerturbation;
	}
	public double getLeftPoint() {
		return leftPoint;
	}
	public void setLeftPoint(double leftPoint) {
		this.leftPoint = leftPoint;
	}
	public double getRightPoint() {
		return rightPoint;
	}
	public void setRightPoint(double rightPoint) {

		this.rightPoint = rightPoint;
	}
	
	//构造函数初始化参数值
	public GeneticAlgorithm(int popSize, int chromoLength, double totalFitness, double bestFitness, double worstFitness,
			double averageFitness, double mutationRate, double crossoverRate, int generation, double maxPerturbation,
			double leftPoint, double rightPoint,int iterNum) {
		super();
		this.popSize = popSize;
		this.chromoLength = chromoLength;
		this.totalFitness = totalFitness;
		this.bestFitness = bestFitness;
		this.worstFitness = worstFitness;
		this.averageFitness = averageFitness;
		this.mutationRate = mutationRate;
		this.crossoverRate = crossoverRate;
		this.generation = generation;
		this.maxPerturbation = maxPerturbation;
		this.leftPoint = leftPoint;
		this.rightPoint = rightPoint;
		this.iterNum=iterNum;
	}
	
	/*转盘赌函数
	 *注意：这里的转盘赌方法仅适用于适应度的值大于0的染色体序列
	 * 
	 * 
	 * */
	
	//初始化种群信息
	public void init(){
		//清空
		population.clear();
		List list;
		double sum=0.0;
		//赋予种群最初的信息
		for(int i=0;i<popSize;i++){
			double gene=random.nextDouble()*(rightPoint-leftPoint)+leftPoint;
			list=new ArrayList<Double>();
			list.add(gene);
			double fitness=mathCalc.calcFunction(list);
			sum+=fitness;
			Genome genome=new Genome(list, fitness);
			population.add(genome);
		}
		setGenInfo();
		printGenInfo();
	}
	
	//转盘赌算法
	public Genome getChromoRoulette(){
		
		
		double slice=random.nextDouble()*totalFitness;
		Genome choseGenome=null;
		double sum=0.0;
		for(int i=0;i<population.size();i++){
			choseGenome=population.get(i);
			sum+=choseGenome.getFitness();
			if(sum>=slice && choseGenome.getFitness()>this.averageFitness){
				break;
			}
		}
		return choseGenome;
		
	}
	
	//基因突变
	public void Mutate(List<Double> genomList){
		
		for(int i=0;i<genomList.size();i++){
			
			//根据指定的突变率选择突变与否
			double randomRate=random.nextDouble();
			if(randomRate<this.getMutationRate()){
				double raw=(double) genomList.get(i);
				raw+=(random.nextDouble()-0.5)*this.getMaxPerturbation();
				if(raw<leftPoint){
					raw=leftPoint;
				}else if(raw>rightPoint){
					raw=rightPoint;
				}
				genomList.set(i, raw);
			}
			
		}
	}
	
    //进化核心方法,每个双亲生成两个子女
	public void Epoch(final List<Genome> popList){
		
		//选择父母，产生后代，注意这里需要size是双数，其实在选择父母的过程中就已经包含了淘汰的过程
		List <Genome>newPopList=new ArrayList<Genome>();
		while(newPopList.size()<this.getPopSize()){
			
			Genome mum=this.getChromoRoulette();
			Genome dad=this.getChromoRoulette();
			//生成新的基因序列
			List<Double> baby1=mum.getGenomeList();
			List<Double> baby2=dad.getGenomeList();
			this.Mutate(baby1);
			this.Mutate(baby2);
			Genome newBabyGenome1=new Genome(baby1,mathCalc.calcFunction(baby1));
			Genome newBabyGenome2=new Genome(baby2,mathCalc.calcFunction(baby1));
			newPopList.add(newBabyGenome1);
			newPopList.add(newBabyGenome2);
			
		}
		popList.clear();
		//产生新的一代
		for(int i=0;i<newPopList.size();i++){
			popList.add(newPopList.get(i));
		}
		newPopList=null;
		
	}
	public void setGenInfo(){
		
		Genome bestGenome=population.get(0);
		Genome worstGenome=population.get(0);
		double totalFit=0.0;
		for(int i=0;i<population.size();i++){
			Genome genom=population.get(i);
			totalFit+=genom.getFitness();
			if(genom.getFitness()>bestGenome.getFitness()){
				bestGenome=genom;
			}
			if(genom.getFitness()<worstGenome.getFitness()){
				worstGenome=genom;
			}
			
			
		}
		
		double averageFit=totalFit/population.size();
		this.setTotalFitness(totalFit);
		this.setBestFitness(bestGenome.getFitness());
		this.setWorstFitness(worstGenome.getFitness());
		this.setAverageFitness(averageFit);
		this.setGeneration(this.getGeneration()+1);
		
	}
	public void printGenInfo(){
		System.out.print("the generation is:\t");
		System.out.println(this.generation);
		System.out.print("the best fitness is:\t");
		System.out.println(this.getBestFitness());
		System.out.print("the worst fitness is:\t");
		System.out.println(this.getWorstFitness());
		System.out.print("the average fitness is:\t");
		System.out.println(this.getAverageFitness());
		System.out.print("the total fitness is:\t");
		System.out.println(this.getTotalFitness());
	}
	//遗传算法具体操作步骤
	public void geneticAlgorithmPorcess(){
		
		int iterNum=this.iterNum;
		this.init();
		for (int gen=0;gen<this.iterNum;gen++){
			this.Epoch(this.population);
			setGenInfo();
			printGenInfo();
		}

		
	}
	
	
	
	
	

}

 测试类：

package com.luchi.genetic;

public class MainTestClass {
	
	public static void main(String[]args){
		
		GeneticAlgorithm genAL=new GeneticAlgorithm(50, 1, 0.0,
				0.0, 99999999, 0.0, 0.8,
				0.8, 0, 0.004, 0, 4, 100);
	
		genAL.geneticAlgorithmPorcess();
	}
}

 结果如下：

the generation is:	101
the best fitness is:	5.648238442785841
the worst fitness is:	5.277698361050879
the average fitness is:	5.460200891763737
the total fitness is:	273.0100445881869

 迭代次数为101次（多了一次是因为迭代从0开始的）

 

      需要说明的是：遗传算法对初始群体的选取还有遗传父母的个体还是很敏感的，每次运行会有不同的结         果，这里使用（0,4）区间并不是最好的选择，因为其适应值函数包含了负数，这会影响到转盘赌方法的       准确性，因此如果需要遗传算法得到一个很好的效果，还是需要对初始群体和遗传交叉过程进行优化

      今天就写到这儿，有问题再议，源代码见附件

 

 

       参考文献

       1，http://blog.csdn.net/emiyasstar__/article/details/6938608

        2， http://blog.csdn.net/b2b160/article/details/4680853/