遗传算法初步探析

haitaoandroid

浏览: 27498 次
性别:
来自: 广州

最近访客更多访客>>

leoeco2000

xxq123

Slove1994

d8935

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

貌似遗传算法看起来挺神秘的，但要真正初步的了解一下它的大概思想还是挺简单的。我只想用最通俗的话和最简单的编程来讲讲遗传算法。

先来求解一个最简单的问题，求解f(x)=x*2的最大值 , x属于[0,31]；即求解x的平方在[0,31]的最大值.现在我们用遗传算法来求解这个题目。
　先解释一下生物界的一些基础知识：
1：染色体和基因，染色体可以理解为一段字符串编码，唯一的表示个体的特征的，如1001，就表示一个染色体，1，0，0，1这样的就是基因
2：选择，就是比较合适环境的个体生存下来，不合适环境的个体会被淘汰，
3：交叉，也就是繁殖，就是一个个体遗传父母的基因，有好基因，也有不好的基因，如下面
1001 1000

他们两个个体第4位交叉后变为下面的
1000 1001
4：变异，也就是这个个体的基因会产生突变，如1001变为1000就是突变
现在我们可以做上面的题目了，我们要求[0,31]中x的平方最大值，按照遗传算法的逻辑，适者生存，即要让计算机尽量选择“适者”，排除“不适者”，在这个题目“适者”就是x的平方比较大的x值。当然首先要把x变成染色体，也就是编码，编码可以有很多种方式，最简单的就是二进制编码。如31编码为1111；
确定编码规则后就可以按照下面的步骤来写代码了，总共有四步：
1：初始化

//遗传算法构造函数
public GA() {
   String s;
for(int i=0;i<4;i++){
	s = Integer.toBinaryString(r.nextInt(32));//产生随机[0,31]的随机数
					          //，并且转换为二进制表示
	while(s.length()<5){  //空位补0，补齐5位
		s = "0"+s;
		}
	chromosome[i] = s;//这是初始化种群大小，即一开始有多少个体，我这里选择4个String[] array = new String[4];
	}
	gcount = 0; //全局变量，表示当前第几代，先不用管
	// print("初始化：");
}

初始化完了，我们有4个初始个体了，为了分析，假如我们随机得到了下面四个染色体：
10010 11000 10101 00101
现在要根据这4个随机的个体找到31这个最大的x值，便有了以下的三大步骤，即遗传算法的主要步骤：
2：选择，从上面4个染色体中选择

//选择
	 void select(){
		int min = 0;
		int max = 0;
		for(int i=0;i<4;i++){ //从4个个体中把最大适应度个体代替最低适应度个体，fitArray数组表示4个染色体的适应度
			fitArray[i] = fit(chromosome[i]);//fit函数计算个体（也就是染色体）的适应度
			if(fitArray[i]<fitArray[min]){
				min = i;
			}
			if(fitArray[i]>fitArray[max]){
				max = i;
			}
		}
		if(fitArray[max]>bestFit){  //bestFit和bestChromosome是全局最优解，即我们最终的结果会在这里出现，
			bestFit = fitArray[max]; //bestFit代表至今最好的适应度
			bestChromosome = chromosome[max];//bestChromosome代表至今最好的染色体
		}
		chromosome[min] = chromosome[max];
		print("选择后：");
	}

//求染色体x的适应度函数
	double fit(String x){
		int i = Integer.parseInt(x, 2);
		return (double)i*i;
	}

我们根据染色体的适应度来选择留下来的染色体，在我们上面的4个染色体中：
10010 11000 10101 00101
根据适应度函数x的平方,(11000)的平方最大，即适应度最大，(00101)的平方最小，即适应度最小，所以00101会淘汰，被替换成11000，因此，经过选择步骤后，我们的染色体变成了
10010 11000 10101 11000

3:交叉

	//交叉
	void cross(){
		if(Math.random()<0.25){//交叉的概率，为了好讲解，这个可以先不管，后面还会说到，先假设一定会交叉
			return;
		}
		char[] cr[] = new char[4][5];
		//随机产生4个染色体中哪两个需要交叉
		int a = r.nextInt(4);
		int b = r.nextInt(4);
		for(int i=0;i<4;i++){
			cr[i] = chromosome[i].toCharArray();
		}
		//随机产生交叉的位置j和l，因为染色体为5位，所以值要小于5
		int j = r.nextInt(5); 
		int l = r.nextInt(5);
		if(l<j){  //在a和b染色体中l到j位中产生交叉操作
			for(int k=l;k<j;k++){
				char u = cr[a][k];
				cr[a][k] = cr[b][k];
				cr[b][k] = u;
			}
		}else{ //在a和b染色体中j到l位中产生交叉操作
			for(int k=j;k<l;k++){
				char u = cr[a][k];
				cr[a][k] = cr[b][k];
				cr[b][k] = u;
			}
		}
		//交叉后重新赋值给染色体
		for(int i=0;i<4;i++){
			chromosome[i] = new String(cr[i]);
		}
		print("交叉后：");
	}

假设还是上面的经过选择的染色体：
10010 11000 10101 11000
如果是第一个和第三个染色体的第2位到第4位进行交叉，即上面代码中（a=0,b=2,j=1,l=3）,交叉后得到
10100 11000 10011 11000
这是我们经过交叉后得到的结果，当然交叉不是每一次迭代都需要，还需要一定的概率，后面会说到。

4：变异

//变异
	void variation(){
		if(Math.random()>0.1)return;//变异的概率是0.1
		int i = r.nextInt(4);//哪一个个体变异
		int j = r.nextInt(5);//个体的哪一位变异
		char[] c = chromosome[i].toCharArray();
		if(c[j]=='0'){
			c[j] = '1';
		}else{
			c[j] = '0';
		}
		chromosome[i] = new String(c);
		print("变异后：");
	}

以常识来讲，变异的操作概率更低，但假如我们这次发生了变异，还是用上面的数据：
10100 11000 10011 11000
如果是第四个染色体的第三位发生了变异，即会变为：
10100 11000 10011 11100
以上是所以一次迭代的操作，即一次生物繁殖的过程，当然，我们会经过很多次的迭代来最终得到31（即11111）这个最大值，如下

5：迭代求最终结果

public static void main(String[] args) {
		GA ga = new GA();
		for(int i=0;i<1000;i++){
			ga.select();
			ga.cross();
			ga.variation();
			ga.gcount++;
			System.out.println("第几代.."+ga.gcount);
		}
		
		System.out.println("最好的适应度："+bestFit+" 最好的值；"+bestChromosome);
	}

以下给出迭代开始和迭代结束的一些结果，仅供参考：

初始化：
01100
11000
01010
00110
选择后：
01100
11000
01010
11000
交叉后：
01100
11000
01010
11000
第几代..1
选择后：
01100
11000
11000
11000
交叉后：
01000
11000
11000
11100
第几代..2
选择后：
11100
11000
11000
11100
交叉后：
11000
11000
11100
11100
变异后：
11000
11000
10100
11100
................................
选择后：
11111
11111
11111
11111
交叉后：
11111
11111
11111
11111
第几代..998
选择后：
11111
11111
11111
11111
第几代..999
选择后：
11111
11111
11111
11111
交叉后：
11111
11111
11111
11111
第几代..1000
最好的适应度：961.0 最好的值；11111

这样我们就得到我们想要的值11111（即31）
有些人可能会疑惑，经过这些操作，为什么能够得到这个31最大值呢？理一下思路，一开始，计算机是随机得到4个[0，31]的值，然后选择操作会把x的值越来越推进最优解，但是这个是临时的最优解，重新选择四个个体：
10010 11000 10001 01001
这里的最优解是11000，想象一下，如果一直只进行选择操作，而不进行交叉和变异操作，最后的结果会是：
11000 11000 11000 11000
因为111000是这里的最优，最后所有的不合适的解都会被11000给替换。交叉又起了什么作用呢？假如在上面的四个个体中在进行选择的同时也进行交叉操作，最后的结果会是：
11011 11011 11011 11011
还是得不到我们想要的值11111，为什么会这样呢？大家可以想象一下，因为在我们的染色体中，第三位都是0，第三位无论怎么进行选择和交叉操作，都不会变，这样我们还是得不到我们想要的值，接下来是变异发挥作用的时候。相信大家都已经很明白了，因为变异也是随机的，只要变异的次数够多，总会把其中一个染色体的第三位变成1，这样再进行选择，交叉操作的时候就能够得到11111了。至于最后有关选择，交叉，变异的范围以及它怎么影响到最后的结果我会在“模式和遗传算法的搜索机制”中讲到，其中牵涉到模式和遗传算法的搜索域问题。

分享到：