论坛首页 Java企业应用论坛

关于遗传算法

浏览 3263 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-08-26  

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

一.进化论知识  

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

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

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

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

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

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

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

 

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

 

 

二.遗传算法思想  

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

 

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

 

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

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

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

      代码如下:

package com.algorithm.hash;

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;
	}

}
 

 

   发表时间:2011-08-26  
例子不错!遗传算法有什么实用的例子吗?
0 请登录后投票
   发表时间:2011-11-17  
不错!看了楼主的例子收获很多。但是在此我想提几个问题:

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

最后一个问题就是:你的split方法内的染色体分裂逻辑73-85行是怎么来得?还是简单的根据智商算出的呢?
0 请登录后投票
   发表时间:2011-11-17  
实际中的应用:
客服排班,教学安排等。。。要考虑很多因素,突发情况,这种问题就可以用遗传算法模型来处理
0 请登录后投票
   发表时间:2011-11-17  
http://www.azumi.cc/thread-667728-1-1.html 楼主你一天到晚抄人家的累不累?
0 请登录后投票
   发表时间:2011-11-17  
iminto 写道
实际中的应用:
客服排班,教学安排等。。。要考虑很多因素,突发情况,这种问题就可以用遗传算法模型来处理


通常用于解决优化问题,这些问题往往没有最优解或者很难求出。
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics