关于遗传算法

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

一.进化论知识  

　　作为遗传算法生物背景的介绍，下面内容了解即可：

　　种群 (Population) ： 生物的进化以群体的形式进行，这样的一个群体称为种群。

　　个体 ：组成种群的单个生物。

　　基因 ( Gene ) ： 一个遗传因子。 

　　染色体 ( Chromosome ) ：包含一组的基因。

　　生存竞争，适者生存 ：对环境适应度高的、牛B的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少。

　　遗传与变异 ：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。

 

　　简单说来就是：繁殖过程，会发生基因交叉( Crossover ) ，基因突变 ( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高 的那个个体。

 

 

二.遗传算法思想  

　　借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应。

 

        下面是一个根据遗传算法的思想写出来的简单例子。

 

        人类种群分为，男人和女人，男人是奇数，女人是偶数，每个人都有一个智商值（代码里为num）。男人会分裂成两个染色体X （奇数）和Y（偶数），女人也会分裂成两个染色体X（偶数）和X（偶数）。在染色体分裂的过程中会有一定几率（这里几率为0.25）基因突变（这里是值加2）。然后男人的一个染色体和女人的一个染色体结合产生后代。

       产生的后代也有智商值，那些智商值低的个体将不会生存下来（适者生存），这里有一个适应度函数来模拟适者生存。

       最后看产生的后代是否智商达到100，达到了100就结束繁殖。

      代码如下：

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

//遗传算法
public class GA {
	//男人是奇数，女人是偶数
	List<human>  manPop = new ArrayList<human>();
	List<human>  womanPop = new ArrayList<human>();
	double Pm = 0.25; //变异发生的概率
	int score = 100;
	public GA(human man ,human woman){
		manPop.add(man);
		womanPop.add(woman);
	}

	//种群（Population）
	public Boolean Population(){

		int num = manPop.size()<womanPop.size()?manPop.size():womanPop.size();

		for(int i = 0; i < num;i++){
			
			boby(manPop.get(i),womanPop.get(i));
		}
		//适者生存，淘汰最差的
		manPop = Fitness(manPop);
		womanPop = Fitness(womanPop);
		//得到需要的后代后停止
		if(check(manPop)||check(womanPop)){
			return true;
		}else{
			return false;
		}
	}
	
	private void boby(human m,human w){
		//染色体分裂
		split(m);
		split(w);

		//组合
		human newhuman = new human(m.getA() + w.getA());
		if( newhuman.getNum() % 2 != 0){//产生的是男人，放到男人种群
			manPop.add(newhuman);
		}else{                         //产生的是女人，放到女人种群
			womanPop.add(newhuman);
		}
		newhuman = new human(m.getA() + w.getB());
		if( newhuman.getNum() % 2 != 0){//产生的是男人，放到男人种群
			manPop.add(newhuman);
		}else{                         //产生的是女人，放到女人种群
			womanPop.add(newhuman);
		}
		newhuman = new human(m.getB() + w.getA());
		if( newhuman.getNum() % 2 != 0){//产生的是男人，放到男人种群
			manPop.add(newhuman);
		}else{                         //产生的是女人，放到女人种群
			womanPop.add(newhuman);
		}
		newhuman = new human(m.getB() + w.getB());
		if( newhuman.getNum() % 2 == 0){//产生的是男人，放到男人种群
			manPop.add(newhuman);
		}else{                         //产生的是女人，放到女人种群
			womanPop.add(newhuman);
		}

	}
	
	//染色体分裂,男人分裂为X Y，女人分裂为 X1 X2
	private human split(human h){
		//男人
		if(h.getNum() % 2 != 0){
			h.setA(h.getNum()/2);
			h.setB(h.getNum() - (h.getNum()/2));
		}else{//女人
			int temp = h.getNum()/2;
			if(temp % 2 != 0){
				temp = temp + 1;
			}
			h.setA(temp);
			h.setB(h.getNum() - temp);
		}
		//染色体变异(基因突变)
		h.setA(Mutation(h.getA()));
		h.setB(Mutation(h.getB()));
		h.setDeadStatus(1);
		return h;
	}
	
	//变异(Mutation)：在繁殖过程，新产生的染色体中的基因会以一定的概率出错，称为变异。变异发生的概率记为Pm
	private int Mutation(int a){
		if(Math.random()<Pm){ //变异有一定概率发生
			return a = a + 2;
		}else{
			return a;
		}
	}
	
	//适应度函数 ( Fitness Function ) 适者生存，将不适应的个体淘汰掉
	private List<human> Fitness(List<human> pop){
		//新的种群
		List<human> newPop = new ArrayList<human>();
		pop = StayMax(pop);
		for(human h:pop){
			if(h.getDeadStatus() == 0){
				newPop.add(h);
			}
		}
		return newPop;
	}
	
	//淘汰算法(只要num最大的)
	private List<human> StayMax(List<human> pop){
		//只要最大num的
		int max = pop.get(0).getNum();
		int maxId = 0;
		for(int i = 0; i < pop.size();i++){
			human h = pop.get(i);
			if(h.getDeadStatus() == 0&&h.getNum() > max){
				max = h.getNum();
				maxId = i;
			}
			pop.get(i).setDeadStatus(1);
		}
		pop.get(maxId).setDeadStatus(0);  //最大的留下
		return pop;
	}
	
	//去掉最小的，其他留下。
	private List<human> RemoveMin(List<human> pop){
		//去掉
		int min = pop.get(0).getNum();
		int minId = 0;
		for(int i = 0; i < pop.size();i++){
			human h = pop.get(i);
			if(h.getDeadStatus() == 0&&h.getNum() < min){
				min = h.getNum();
				minId = i;
			}
		}
		pop.get(minId).setDeadStatus(1);  //最小的被淘汰
		return pop;
	}
	
	//
	public Boolean  check(List<human> pop){
		for(human h:pop){
			if(h.getNum() >= score){
				return true;
			}
			
		}
		return false;
	}
	
	public void Print(){
		for(human h:manPop){
			if(h.getDeadStatus() == 0){
				System.out.println(h.getNum());
			}
		}
		for(human h:womanPop){
			if(h.getDeadStatus() == 0){
				System.out.println(h.getNum());
			}
		}
	}
	
	public static void main(String[] args) {
		GA ga = new GA(new human(1),new human(2));
		for(int i = 1;i < 1000000;i++){
			if(ga.Population()){
				System.out.println("第"+i+"代满足条件");
				ga.Print();
				break;
			}
				
		}	
	}
}

//一个人有两条性染色体,X Y 或者 X X
class human{
	private int num;
	private int a;
	private int b;
	private int deadStatus = 0; //当为0时，表示个体死亡，被淘汰.
	public int getDeadStatus() {
		return deadStatus;
	}

	public void setDeadStatus(int deadStatus) {
		this.deadStatus = deadStatus;
	}

	public human(int num){
		this.num = num;
	}

	public int getNum() {
		return num;
	}
	public void setNum(int num) {
		this.num = num;
	}
	public int getA() {
		return a;
	}
	public void setA(int a) {
		this.a = a;
	}
	public int getB() {
		return b;
	}
	public void setB(int b) {
		this.b = b;
	}

}

 

 

评论

3 楼 LANGRENBULE 2013-01-30  

发现Lz没有调用RemoveMin函数！即没有进行淘汰，看来LZ是个怜悯类型造物主

2 楼 liulanghan110 2011-11-21  

1.第一个应该是注释写错了。
2.很多生物都是繁殖完就死亡的，比如蜉蝣，哈哈。
3.分裂的时候进行基因突变，然后染色体交叉成为后代。
分裂 的逻辑只是根据奇数（男人）分成一个奇数+一个偶数，偶数（女人）分成两个偶数的简单算法。具体的问题要有具体的分裂逻辑。智商相当于适应度函数，也是具体的情况会有不同的适应度函数。

1 楼 beitongmoming 2011-11-17  

不错！看了楼主的例子收获很多。但是在此我想提几个问题：

1.我读你的代码发现应该是deadStatus = 1表示死亡。但是你注释写的是0
2.88行没必要赋值1了。分裂完就死亡是不是悲剧了点 - -！
3.我觉得是不是可以把变异方法Mutation从分裂里面移到boby内的组合后面，也就是68行。因为基因突变应该是在交叉后面吧？而不是在分裂的时候突变。

最后一个问题就是：你的split方法内的染色体分裂逻辑73-85行是怎么来得？还是简单的根据智商算出的呢？