博主前言：此文章来自一份网络资料，原作者不明，是我看过的最好的一份遗传算法教程，如果你能耐心看完他，相信你一定能基本掌握遗传算法。
遗传算法的有趣应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制，找圆心问题（这是一个国外网友的建议：在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心。），TSP问题（在以后的章节里面将做详细介绍。），生产调度问题，人工生命模拟等。直到最后看到一个非常有趣的比喻，觉得由此引出的袋鼠跳问题（暂且这么叫它吧），既有趣直观又直达遗传算法的本质，确实非常适合作为初学者入门的例子。
问题的提出与解决方案
让我们先来考虑考虑下面这个问题的解决办法。
已知一元函数：
现在要求在既定的区间内找出函数的最大值
极大值、最大值、局部最优解、全局最优解
在解决上面提出的问题之前我们有必要先澄清几个以后将常常会碰到的概念：极大值、最大值、局部最优解、全局最优解。学过高中数学的人都知道极大值在一个小邻域里面左边的函数值递增，右边的函数值递减，在图2.1里面的表现就是一个“山峰”。当然，在图上有很多个“山峰”，所以这个函数有很多个极大值。而对于一个函数来说，最大值就是在所有极大值当中，最大的那个。所以极大值具有局部性，而最大值则具有全局性。
因为遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基
因组到其解的适应度形成一个映射。所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。在这个多维曲面里面也有数不清的“山峰”，而这些最优解所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遗传算法不一定要找“最高的山峰”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的，遗传算法所要找的就是“最深的谷底”）如果至今你还不太理解的话，那么你先往下看。本章的示例程序将会非常形象的表现出这个情景。
“袋鼠跳”问题
既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰（尽管袋鼠本身不见得愿意那么做）。所以求最大值的过程就转化成一个“袋鼠跳”的过程。下面介绍介绍“袋鼠跳”的几种方式。
爬山法、模拟退火和遗传算法
解决寻找最大值问题的几种常见的算法：
1. 爬山法（最速上升爬山法）：
从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断重复上述过程。因为只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。（在爬山法中，袋鼠最有希望到达最靠近它出发点的山顶，但不能保证该山顶是珠穆朗玛峰，或者是一个非常高的山峰。因为一路上它只顾上坡，没有下坡。）
2. 模拟退火：
这个方法来自金属热加工过程的启发。在金属热加工过程中，当金属的温度超过它的熔点（Melting Point）时，原子就会激烈地随机运动。与所有的其它的物理系统相类似，原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变迁过程中，开始时。温度非常高，使得原子具有很高的能量。随着温度不断降低，金属逐渐冷却，金属中的原子的能量就越来越小，最后达到所有可能的
最低点。利用模拟退火的时候，让算法从较大的跳跃开始，使到它有足够的“能量”逃离可能“路过”的局部最优解而不至于限制在其中，当它停在全局最优解附近的时候，逐渐的减小跳跃量，以便使其“落脚”到全局最优解上。（在模拟退火中，袋鼠喝醉了，而且随机地大跳跃了很长时间。运气好的话，它从一个山峰跳过山谷，到了另外一个更高的山峰上。但最后，它渐渐清醒了并朝着它所在的峰顶跳去。）
3. 遗传算法：
模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换。以面为单位的搜索，比以点为单位的搜索，更能发现全局最优解。（在遗传算法中，有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠，并希望存活下来的袋鼠是多产的，在它们所处的地方生儿育女。）（后来，一个叫天行健的网游给我想了一个更恰切的故事：从前，有一大群袋鼠，它们被莫名其妙的零散地遗弃于喜马拉雅山脉。于是只好在那里艰苦的生活。海拔低的地方弥漫着一种无色无味的毒气，海拔越高毒气越稀薄。可是可怜的袋鼠们对此全然不觉，还是习惯于活蹦乱跳。于是，不断有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。）
下面主要介绍介绍遗传算法实现的过程。
遗传算法的实现过程
遗传算法的实现过程实际上就像自然界的进化过程那样。首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系。）然后用随机数初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上。），种群里面的个体就是这些数字化的编码。接下来，通过适当的解码过程之后，（得到袋鼠的位置坐标。）用适应性函数对每一个基因个体作一次适应度评估。（袋鼠爬得越高，越是受我们的喜爱，所以适应度相应越高。）用选择函数按照某种规定择优选择。（我们要每隔一段时间，在山上射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平。）让个体基因交叉变异。（让袋鼠随机地跳一跳）然后产生子代。（希望存活下来的袋鼠是多产的，并在那里生儿育女。）遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去
了解和操心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀。）以后你会慢慢理解这句话，这是遗传算法的精粹！
所以我们总结出遗传算法的一般步骤：
开始循环直至找到满意的解。
1.评估每条染色体所对应个体的适应度。
2.遵照适应度越高，选择概率越大的原则，从种群中选择两个个体作为父方和母方。
3.抽取父母双方的染色体，进行交叉，产生子代。
4.对子代的染色体进行变异。
5.重复2，3，4步骤，直到新种群的产生。
结束循环。
接下来，我们将详细地剖析遗传算法过程的每一个细节。
编制袋鼠的染色体----基因的编码方式
通过前一章的学习，读者已经了解到人类染色体的编码符号集，由4种碱基的两种配合组成。共有4种情况，相当于2 bit的信息量。这是人类基因的编码方式，那么我们使用遗传算法的时候编码又该如何处理呢？
受到人类染色体结构的启发，我们可以设想一下，假设目前只有“0”，“1”两种碱基，我们也用一条链条把他们有序的串连在一起，因为每一个单位都能表现出1 bit的信息量，所以一条足够长的染色体就能为我们勾勒出一个个体的所有特征。这就是二进制编码法，染色体大致如下：
010010011011011110111110
上面的编码方式虽然简单直观，但明显地，当个体特征比较复杂的时候，需要大量的编码才能精确地描述，相应的解码过程（类似于生物学中的DNA翻译过程，就是把基因型映射到表现型的过程。）将过份繁复，为改善遗传算法的计算复杂性、提高运算效率，提出了浮点数编码。染色体大致如下：
1.2 – 3.3 –
2.0 –5.4 – 2.7 – 4.3
那么我们如何利用这两种编码方式来为袋鼠的染色体编码呢？因为编码的目的是建立表现型到基因型的映射关系，而表现型一般就被理解为个体的特征。比如人的基因型是46条染色体所描述的（总长度两米的纸条？），却能解码成一个个眼，耳，口，鼻等特征各不相同的活生生的人。所以我们要想为“袋鼠”的染色体编码，我们必须先来考虑“袋鼠”的“个体特征”是什么。也许有的人会说，袋鼠的特征很多，比如性别，身长，体重，也许它喜欢吃什么也能算作其中一个特征。但具体在解决这个问题的情况下，我们应该进一步思考：无论这只袋鼠是长短，肥瘦，只要它在低海拔就会被射杀，同时也没有规定身长的袋鼠能跳得远一些，身短的袋鼠跳得近一些。当然它爱吃什么就更不相关了。我们由始至终都只关心一件事情：袋鼠在哪里。因为只要我们知道袋鼠在那里，我们就能做两件必须去做的事情：
（1）通过查阅喜玛拉雅山脉的地图来得知袋鼠所在的海拔高度（通过自变量求函数值。）以判断我们有没必要把它射杀。
（2）知道袋鼠跳一跳后去到哪个新位置。
如果我们一时无法准确的判断哪些“个体特征”是必要的，哪些是非必要的，我们常常可以用到这样一种思维方式：比如你认为袋鼠的爱吃什么东西非常必要，那么你就想一想，有两只袋鼠，它们其它的个体特征完全同等的情况下，一只爱吃草，另外一只爱吃果。你会马上发现，这不会对它们的命运有丝毫的影响，它们应该有同等的概率被射杀！只因它们处于同一个地方。（值得一提的是，如果你的基因编码设计中包含了袋鼠爱吃什么的信息，这其实不会影响到袋鼠的进化的过程，而那只攀到珠穆朗玛峰的袋鼠吃什么也完全是随机的，但是它所在的位置却是非常确定的。）
以上是对遗传算法编码过程中经常经历的思维过程，必须把具体问题抽象成数学模型，突出主要矛盾，舍弃次要矛盾。只有这样才能简洁而有效的解决问题。希望初学者仔细琢磨。
既然确定了袋鼠的位置作为个体特征，具体来说位置就是横坐标。那么接下来，我们就要建立表现型到基因型的映射关系。就是说如何用编码来表现出袋鼠所在的横坐标。由于横坐标是一个实数，所以说透了我们就是要对这个实数编码。回顾我们上面所介绍的两种编码方式，读者最先想到的应该就是，对于二进制编码方式来说，编码会比较复杂，而对于浮点数编码方式来说，则会比较简洁。恩，正如你所想的，用浮点数编码，仅仅需要一个浮点数而已。而下面则介绍如何建立二进制编码到一个实数的映射。
明显地，一定长度的二进制编码序列，只能表示一定精度的浮点数。譬如我们要求解精确到六位小数，由于区间长度为2 – (-1) = 3 ,为了保证精度要求，至少把区间[-1,2]分为3 × 106等份。又因为
所以编码的二进制串至少需要22位。
把一个二进制串（b0,b1,....bn)转化位区间里面对应的实数值通过下面两个步骤。
（1）将一个二进制串代表的二进制数转化为10进制数：
（2）对应区间内的实数：
例如一个二进制串<1000101110110101000111>表示实数值0.637197。
二进制串<0000000000000000000000>和<1111111111111111111111>则分别表示区间的两个端点值-1和2。
由于往下章节的示例程序几乎都只用到浮点数编码，所以这个“袋鼠跳”问题的解决方案也是采用浮点数编码的。往下的程序示例（包括装载基因的类，突变函数）都是针对浮点数编码的。（对于二进制编码这里只作简单的介绍，不过这个“袋鼠跳”完全可以用二进制编码来解决的，而且更有效一些。所以读者可以自己尝试用二进制编码来解决。）
我们定义一个类作为袋鼠基因的载体。（细心的人会提出这样的疑问：为什么我用浮点数的容器来储藏袋鼠的基因呢？袋鼠的基因不是只用一个浮点数来表示就行吗？恩，没错，事实上对于这个实例，我们只需要用上一个浮点数就行了。我们这里用上容器是为了方便以后利用这些代码处理那些编码需要一串浮点数的问题。）
[cpp]view plaincopy
1.class Genome
2.{
3.public:
4.
5.friend class GenAlg;
6.friend class GenEngine;
7.
8. Genome():fitness(0){}
9.
10. Genome(vector
), fitness(f){} //类的带参数初始化参数。
11.private:
12. vector
13.
14.double fitness; //适应度
15.
16.};
好了，目前为止我们把袋鼠的染色体给研究透了，让我们继续跟进袋鼠的进化旅程。
物竞天择－－适应性评分与及选择函数。
1.物竞――适应度函数（fitness function）
自然界生物竞争过程往往包含两个方面：生物相互间的搏斗与及生物与客观环境的搏斗过程。但在我们这个实例里面，你可以想象到，袋鼠相互之间是非常友好的，它们并不需要互相搏斗以争取生存的权利。它们的生死存亡更多是取决于你的判断。因为你要衡量哪只袋鼠该杀，哪只袋鼠不该杀，所以你必须制定一个衡量的标准。而对于这个问题，这个衡量的标准比较容易制定：袋鼠所在的海拔高度。（因为你单纯地希望袋鼠爬得越高越好。）所以我们直接用袋鼠的海拔高度作为它们的适应性评分。即适应度函数直接返回函数值就行了。
2.天择――选择函数（selection）
自然界中，越适应的个体就越有可能繁殖后代。但是也不能说适应度越高的就肯定后代越多，只能是从概率上来说更多。（毕竟有些所处海拔高度较低的袋鼠很幸运，逃过了你的眼睛。）那么我们怎么来建立这种概率关系呢？下面我们介绍一种常用的选择方法――轮盘赌（Roulette Wheel Selection）选择法。假设种群数目,某个个体其适应度为,则其被选中的概率为：
比如我们有5条染色体，他们所对应的适应度评分分别为：5，7，10，13，15。
所以累计总适应度为：
所以各个个体被选中的概率分别为：
呵呵，有人会问为什么我们把它叫成轮盘赌选择法啊？其实你只要看看图2-2的轮盘就会明白了。这个轮盘是按照各个个体的适应度比例进行分块的。你可以想象一下，我们转动轮盘，轮盘停下来的时候，指针会随机地指向某一个个体所代表的区域，那么非常幸运地，这个个体被选中了。（很明显，适应度评分越高的个体被选中的概率越大。）
那么接下来我们看看如何用代码去实现轮盘赌。
[cpp]view plaincopy
1.Genome GenAlg:: GetChromoRoulette()
2.
3.{
4.
5.//产生一个0到人口总适应性评分总和之间的随机数.
6.
7.//中m_dTotalFitness记录了整个种群的适应性分数总和)
8.
9.double Slice = (random()) * totalFitness;
10.
11.//这个基因将承载转盘所选出来的那个个体.
12.
13. Genome TheChosenOne;
14.
15.//累计适应性分数的和.
16.
17.double FitnessSoFar = 0;
18.
19.//遍历总人口里面的每一条染色体。
20.
21.for (int i=0; i 22. 23. { 24. 25.//累计适应性分数. 26. 27. FitnessSoFar += vecPop[i].fitness; 28. 29.//如果累计分数大于随机数,就选择此时的基因. 30. 31.if (FitnessSoFar >= Slice) 32. 33. { 34. 35. TheChosenOne = vecPop[i]; 36. 37.break; 38. 39. } 40. 41. } 42. 43.//返回转盘选出来的个体基因 44. 45.return TheChosenOne; 46. 47.} 遗传变异――基因重组（交叉）与基因突变。 应该说这两个步骤就是使到子代不同于父代的根本原因（注意，我没有说是子代优于父代的原因，只有经过自然的选择后，才会出现子代优于父代的倾向。）。对于这两种遗传操作，二进制编码和浮点型编码在处理上有很大的差异，其中二进制编码的遗传操作过程，比较类似于自然界里面的过程，下面将分开讲述。 1.基因重组/交叉(recombination/crossover) （1）二进制编码 回顾上一章介绍的基因交叉过程：同源染色体联会的过程中，非姐妹染色单体（分别来自父母双方）之间常常发生交叉，并且相互交换一部分染色体，如图2-3。事实上，二进制编码的基因交换过程也非常类似这个过程――随机把其中几个位于同一位置的编码进行交换，产生新的个体，如图2-4所示。 （2）浮点数编码 如果一条基因中含有多个浮点数编码，那么也可以用跟上面类似的方法进行基因交叉，不同的是进行交叉的基本单位不是二进制码，而是浮点数。而如果对于单个浮点数的基因交叉，就有其它不同的重组方式了，比如中间重组： 这样只要随机产生就能得到介于父代基因编码值和母代基因编码值之间的值作为子代基因编码的值。 考虑到“袋鼠跳”问题的具体情况――袋鼠的个体特征仅仅表现为它所处的位置。可以想象，同一个位置的袋鼠的基因是完全相同的，而两条相同的基因进 行交叉后，相当于什么都没有做，所以我们不打算在这个例子里面使用交叉这一个遗传操作步骤。（当然硬要这个操作步骤也不是不行的，你可以把两只异地的袋鼠捉到一起，让它们交配，然后产生子代，再把它们送到它们应该到的地方。） 2.基因突变(Mutation) （1）二进制编码 同样回顾一下上一章所介绍的基因突变过程：基因突变是染色体的某一个位点上基因的改变。基因突变使一个基因变成它的等位基因，并且通常会引起一定的表现型变化。恩，正如上面所说，二进制编码的遗传操作过程和生物学中的过程非常相类似，基因串上的“ 0”或“ 1”有一定几率变成与之相反的“ 1”或“ 0”。例如下面这串二进制编码： 101101001011001 经过基因突变后，可能变成以下这串新的编码： 001101011011001 （2）浮点型编码 浮点型编码的基因突变过程一般是对原来的浮点数增加或者减少一个小随机数。比如原来的浮点数串如下： 1.2,3.4, 5.1, 6.0, 4.5 变异后，可能得到如下的浮点数串： 1.3,3.1, 4.9, 6.3, 4.4 当然，这个小随机数也有大小之分，我们一般管它叫“步长”。（想想“袋鼠跳”问题，袋鼠跳的长短就是这个步长。）一般来说步长越大，开始时进化的速度会比较快，但是后来比较难收敛到精确的点上。而小步长却能较精确的收敛到一个点上。所以很多时候为了加快遗传算法的进化速度，而又能保证后期能够比较精确地收敛到最优解上面，会采取动态改变步长的方法。其实这个过程与前面介绍的模拟退火过程比较相类似，读者可以做简单的回顾。 下面是针对浮点型编码的基因突变函数的写法： [cpp]view plaincopy 1.void GenAlg::Mutate(vector 2.{ 3. 4.//遵循预定的突变概率,对基因进行突变 5. 6.for (int i=0; i 7. 8. { 9. 10.//如果发生突变的话 11. 12.if (random() < mutationRate) 13. 14. { 15. 16.//使该权值增加或者减少一个很小的随机数值 17. 18. chromo[i] += ((random()-0.5) * maxPerturbatio n); 19. 20.//保证袋鼠不至于跳出自然保护区. 21. 22.if(chromo[i] < leftPoint) 23. 24. { 25. 26. chromo[i] = rightPoint; 27. 28. } 29. 30.else if(chromo[i] > rightPoint) 31. 32. { 33. 34. chromo[i] = leftPoint; 35. 36. } 37. 38.//以上代码非基因变异的一般性代码只是用来保证基因 编码的可行性。 39. 40. } 41. 42. 43. } 44.} 值得一提的是遗传算法中基因突变的特点和上一章提到的生物学中的基因突变的特点非常相类似，这里回顾一下： 1.基因突变是随机发生的，且突变频率很低。（不过某些应用中需要高概率的变异） 2.大多数基因变异对生物本身是有害的。 3.基因突变是不定向的。 好了，到此为止，基因编码，基因适应度评估，基因选择，基因变异都一一实现了，剩下来的就是把这些遗传过程的“零件”装配起来了。 遗传算法引擎――GenAlg [cpp]view plaincopy 1./遗传算法 2.class GenAlg 3. { 4. 5.public: 6. 7.//这个容器将储存每一个个体的染色体 8. 9. vector 10. 11.//人口(种群)数量 12. 13.int popSize; 14. 15.//每一条染色体的基因的总数目 16. 17.int chromoLength; 18. 19.//所有个体对应的适应性评分的总和 20. 21.double totalFitness; 22. 23.//在所有个体当中最适应的个体的适应性评分 24. 25.double bestFitness; 26. 27.//所有个体的适应性评分的平均值 28. 29.double averageFitness; 30. 31.//在所有个体当中最不适应的个体的适应性评分 32. 33.double worstFitness; 34. 35.//最适应的个体在m_vecPop容器里面的索引号 36. 37. Genome fittestGenome; 38. 39.//基因突变的概率,一般介于0.05和0.3之间 40. 41.double mutationRate; 42. 43.//基因交叉的概率一般设为0.7 44. 45.double crossoverRate; 46. 47.//代数的记数器 48. 49.int generation; 50. 51.//最大变异步长 52. 53.double maxPerturbation; 54. 55.double leftPoint; 56. 57.double rightPoint; 58. 59.//构造函数 60. 61. GenAlg(); 62. 63.//初始化变量 64. 65.void Reset(); 66. 67.//初始化函数 68. 69.void init(int popsize, double MutRate, double CrossRa te, int GenLenght,double LeftPoint,double RightPoint); 70. 71.//计算 TotalFitness, BestFitness, WorstFitness, AverageFitness等变量 72. 73.void CalculateBestWorstAvTot(); 74. 75.//轮盘赌选择函数 76. 77. Genome GetChromoRoulette(); 78. 79. 80.//基因变异函数 81. 82.void Mutate(vector 83. 84.//这函数产生新一代基因 85. 86.void Epoch(vector 87. 88. Genome GetBestFitness(); 89. 90.double GetAverageFitness(); 91. }; 其中Reset()函数，init()函数和CalculateBestWorstAvTot()函数都比较简单，读者查看示例程序的代码就能明白了。而下面分别介绍init函数和Epoch 函数。 类的初始化函数――init函数 init函数主要充当CGenAlg类的初始化工作，把一些成员变量都变成可供重新开始遗传算法的状态。（为什么我不在构造函数里面做这些工作呢？因为我 的程序里面CGenAlg类是View类的成员变量，只会构造一次，所以需要另外的初始化函数。）下面是init函数的代码： [cpp]view plaincopy 1.void GenAlg::init(int popsize, double MutRate, double Cro ssRate, int GenLenght,double LeftPoint,double RightPoint) 2. 3.{ 4. 5. popSize = popsize; 6. 7. mutationRate = MutRate; 8. 9. crossoverRate = CrossRate; 10. 11. chromoLength = GenLenght; 12. 13. totalFitness = 0; 14. 15. generation = 0; 16. 17.//fittestGenome = 0; 18. 19. bestFitness = 0.0; 20. 21. worstFitness = 99999999; 22. 23. averageFitness = 0; 24. 25. maxPerturbation=0.004; 26. 27. leftPoint=LeftPoint; 28. 29. rightPoint=RightPoint; 30. 31.//清空种群容器，以初始化 32. 33. vecPop.clear(); 34. 35.for (int i=0; i 37. { 38. 39.//类的构造函数已经把适应性评分初始化为0 40. 41. vecPop.push_back(Genome()); 42. 43.//把所有的基因编码初始化为函数区间内的随机数。 44. 45.for (int j=0; j 46. 47. { 48. 49. vecPop[i].vecGenome.push_back(random() * 50. 51. (rightPoint - leftPoint) + leftPoint); 52. 53. } 54. 55. } 56. 57.} 恩，正如我之前说的，我们这个程序不但要应付基因编码只有一个浮点数的“袋鼠跳”问题的情况，还希望以后在处理一串浮点数编码的时候也一样适用，所以从这里开始我们就把基因当成串来对待。 开创新的纪元――Epoch函数 现在万事具备了，只差把所有现成的“零件”装配起来而已。而Epoch函数就正好充当这个职能。下面是这个函数的实现： [cpp]view plaincopy 1.void GenEngine:: OnStartGenAlg() 2. 3.{ 4. 5. 6.//产生随机数 7. 8. srand( (unsigned)time( NULL ) ); 10.//初始化遗传算法引擎 11. 12. genAlg.init(g_popsize, g_dMutationRate, g_dCrossoverR ate, g_numGen,g_LeftPoint,g_RightPoint); 13. 14.//清空种群容器 15. 16. m_population.clear(); 17. 18.//种群容器装进经过随机初始化的种群 19. 20. m_population = genAlg.vecPop; 21. 22.//定义两个容器，以装进函数的输入与及输出（我们这个函数是单 输入单输出的，但是以后往往不会那么简单，所以我们这里先做好这样的准备。） 23. 24. vector 25.double output; 26. 27. input.push_back(0); 28. 29.for(int Generation = 0;Generation <= g_Generation;Gen eration++) 30. 31. { 32. 33.//里面是对每一条染色体进行操作 34. 35.for(int i=0;i 36. 37. { 38. 39. input = m_population[i].vecGenome; 40. 41.//为每一个个体做适应性评价，如之前说的，评价分数就 是函数值。其 42. 43.//Function函数的作用是输入自变量返回函数值，读者 可以参考其代码。 44. 45. output = (double)curve.function(input); 46. 47. m_population[i].fitness = output; 48. 49. } 50. 51.//由父代种群进化出子代种群（长江后浪退前浪。） 52. 53. genAlg.Epoch(m_population); 54. 55. 56.//if(genAlg.GetBestFitness().fitness>=bestFitness ) 57. bestSearch=genAlg.GetBestFitness().vecGenome[0]; 58. bestFitness=genAlg.GetBestFitness().fitness; 59. averageFitness=genAlg.GetAverageFitness(); 60.//cout< 61. report(Generation+1); 62. } 63. 64.//return bestSearch; 65. 66.} 恩，到这里“袋鼠跳”的主要代码就完成了。(其它一些代码，比如图形曲线的显示，和MFC的相关代码在这就不作介绍了，建议初学者不必理会那些代码，只要读懂算法引擎部分就可以了。)下面就只等着我们下达命令了！ 让袋鼠在你的电脑里进化――程序的运行 我想没有什么别的方法比自己亲手写一个程序然后通过修改相关参数不断调试程序，更能理解并且掌握一种算法了。不知道你还记不记得你初学程序的日子，我想你上机动手写程序比坐在那里看一本厚厚的程序开发指南效率不知高上多少倍，兴趣也特命浓厚，激情也特别高涨。恩，你就是需要那样的感觉，学遗传算法也是一样的。你需要把自己的代码运行起来，然后看看程序是否按照你所想象的去运行，如果没有，你就要思考原因，按照你的想法去改善代码，试着去弄清其中的内在联系。这是一个思维激活的过程，你大脑中的神经网络正在剧烈抖动（呵呵，或许学到后面你就知道你大脑的神经网络是如何“抖动”的。），试图去接受这新鲜而有趣的知识。遗传算法（包括以后要学到的人工神经网络）包含大量的可控参数，比如进化代数、人口数目、选择概率、交叉概率、变异概率、变异的步长还有以后学到的很多。这些参数之间的搭配关系，不能指望别人 用“灌输”的方式让你被动接受，这需要你自己在不断的尝试，不断的调整中去形成一种“感觉”的。很多时候一个参数的量变在整个算法中会表现出质的变化。而算法的效果又能从宏观上反映参数的设置。 现在就让我们来对这个程序做简单的说明。 参数的设置： 这个程序有很多的需要预先设置好的参数，为了方便修改，我把它们都定义为全局变量，定义和初始化都放在Parameter.h的头文件里面。下面对几个主要参数的说明： 1.//目标函数的左右区间，目前的设置是[-1,2] 2. 3.double g_LeftPoint = -1; 4. 5.double g_RightPoint = 2; 6. 7.////遗传算法相关参数//// 8. 9.int g_numGen = 1; //每条染色体的编码个数，这里是1个 10. 11.int g_Generation = 1000; //进化的代数 12. 13.int g_popsize = 50; //种群的人口数目（就是说你要放多少只袋鼠到山 上） 14. 15.double g_dMutationRate = 0.8; //基因变异的概率 16. 17.double g_dMaxPerturbation = 0.005; //基因变异的步长（袋鼠跳的最大 距离） 当然，一些主要的参数在程序运行后可以通过参数设置选项进行设置。（其中缓冲时间是每进化一代之后，暂停的时间，单位为毫秒）如图2-6。 一需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1．程序流程图 2．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual { char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在； 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。 （4）染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色 遗传算法在图像处理中的应用 束道胜 P201002117 1引言 遗传算法( genetic algorithm, GA)是一种自适应启发式群体型概率性迭代式的全局收敛搜索算法,其基本思想来源于生物进化论和群体遗传学,体现了适者生存、优胜劣汰的进化原则。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan大学的Holland教授提出,其数学框架也于20世纪60年代中期形成。由于GA的整体搜索策略和优化计算不依赖于梯度信息,所以它的应用范围非常广泛,尤其适合于处理传统方法难以解决的高度复杂的非线性问题。它在自适应控制、组合优化、模式识别、机器学习、规划策略、信息处理和人工生命等领域的应用中越来越展示出优越性。 图像处理是计算机视觉中的一个重要研究领域,在图像处理过程中,如扫描、特征提取、图像分割等不可避免地会存在一些误差,从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求, GA 在这些图像处理中的优化计算方面找到了用武之地,目前已在图像分割、图像恢复、图像重建、图像检索和图像匹配等方面得到了广泛的应用。 2 遗传算法的原理、基本性质和改进 GA把问题的解表示成染色体(也称串) , GA的求解步骤如下: (1) 编码定义问题的解空间到染色体编码空间的映射,一个候选解(个体)用一串符号表示。 (2) 初始化种群在一定的限制条件下初始化种群,该种群是解空间的一个子空间。 (3) 设计适应度函数将种群中的每个染色体解码成适于计算机适应度函数的 形式,计算其数值。 (4) 选择根据适应度大小选择优秀个体繁殖下一代,适应度越高,则选择概率越大。 (5) 交叉随机选择两个用于繁殖下一代的个体的相同位置,在选中的位置实行交换。 (6) 变异对某个串中的基因按突变概率进行翻转。 (7) 从步骤4开始重复进行,直到满足某一性能指标或规定的遗传代数。 步骤1、2和3是实际应用中的关键,步骤4～步骤6进行3种基本基因操作,选择实现 硕士生考查课程考试试卷 考试科目： 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：年月日午时至时 《MATLAB 教程》试题： A 、利用MATLA B 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。要求设计遗传算法对该问题求解。 a e h k B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。 以上四题任选一题进行实验，并写出实验报告。 选择题目： B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 一、问题分析（10分） 这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。 在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。 二、实验原理与数学模型（20分） （1）试验原理： 用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。 遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。 （2）数学模型 对于求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件； 1、简述可拓思想及其拓展工具 可拓思想是利用物元理论、事元理论和可拓集合理论，结合各应用理论和方法去处理该领域中的矛盾问题，以化不可行为可行，不可知为可知，化不属于为属于、化对立为共存。 可拓拓展工具定性工具物元和事元是可拓学的基本概念，可拓变换是解决矛盾问题的基本工具，可拓分析方法是寻求可拓变换的依据。利用它们可以从定性的角度分析事物开拓的可能性。 定量工具可拓集合是描述事物具有某种性质的程度和量变与质变的定量化工具。 2、什么是云计算？云计算为什么备受关注？为什么要实现云计算？ 云计算的基本原理是通过使计算分布在大量的分布式计算机上，而非本地计算机或远程服务中，企业数据中心的运行将更与互联网相似。这使得企业能够将资源切换到需要的应用上，根据需求访问计算机和存储系统 云计算是一种革命性的举措，打个比方，这就好比是从古老的单台发电机模式转向了电厂集中供电的模式。它意味着计算能力也可以作为一种商品进行流通。它最大的不同在于它是通过互联网进行传输的。 在未来只需一台笔记本或者手机，就可以通过网络服务来满足人们一切甚至包括超级计算这样的任务。最终用户才是云计算的真正拥有者。云计算的思想：把力量联合起来，给其中的每一个成员使用。 3、简述粗集理论. ①利用抽象代数来研究粗糙集代数空间这种特殊的代数结构。②利用拓扑学描述粗糙空间。 ③还有就是研究粗糙集理论和其他软计算方法或者人工智能的方法相接合，例如和模糊理论、神经网络、支持向量机、遗传算法等。④针对经典粗糙集理论框架的局限性，拓宽粗糙集理论的框架，将建立在等价关系的经典粗糙集理论拓展到相似关系甚至一般关系上的粗糙集理论 4、比较协同进化遗传算法与普通遗传算法。 遗传算法虽然实现简单，操作方便，但是存在很多的缺陷：①很容易导致“早熟”，陷入局部最优；②随着问题规模的增大，其计算复杂度明显增加，收敛性显著降低，搜索问题空间能力也下降；③依靠简单的交叉、变异操作，很容易产生不可行解；④交叉产生的子代可能一个适应度很高，另一个很低，低的个体虽然含有较好的基因，但是会被淘汰。 两种算法的比较结果很明显就可以看出两种算法的优劣：CGA、要明显优于GA，计算是时间短，收敛速度快，而且收敛精度也比较高。在求解分类神经网络训练问题计算工作量大大减少，同样达到90%的分类精度，CGA的遗传代数只有GA的1/3.在求解Manipulator Path Planning问题CGA占用CPU的时间只有GA的1/9 5、比较免疫算法与遗传算法。 (1)免疫算法与遗传算法起源于抗原与抗体之间的内部竞争，其相互作用的环境既包括外部也包括内部的环境；而遗传算法起源于个体与自私基因之间的外部竞争。(2)免疫算假设免疫元素互相作用，即每一个免疫细胞等个体可以相互作用，而遗传算法不考虑个体之间的作用。(3)免疫算法中，基因可以由个体自己选择，而在遗传算法中基因有环境选择。(4)免疫算法中，基因组合是为了获得多样性，一般不用交叉算子，因为免疫算法中基因是在同一代个体进行进化，这种情况下设交叉概率为0；而遗传算法后代个体基因通常是由父代交叉的结果，交叉用于混合基因(5)免疫算法选择个变异阶段明显不同，而遗传算法中它们是交替进行的。 6、请描述遗传算法特点。 (1)遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传 function youhuafun D=code; N=50;%Tunable maxgen=50;%Tunable crossrate=0.5;%Tunable muterate=0.08;%Tunable generation=1; num=length(D); fatherrand=randint(num,N,3); score=zeros(maxgen,N); while generation<=maxgen ind=randperm(N-2)+2;%随机配对交叉 A=fatherrand(:,ind(1:(N-2)/2)); B=fatherrand(:,ind((N-2)/2+1:end)); %多点交叉 rnd=rand(num,(N-2)/2); ind=rnd tmp=A(ind); A(ind)=B(ind); B(ind)=tmp; %%两点交叉 %for kk=1:(N-2)/2 %rndtmp=randint(1,1,num)+1; %tmp=A(1:rndtmp,kk); %A(1:rndtmp,kk)=B(1:rndtmp,kk); %B(1:rndtmp,kk)=tmp; %end fatherrand=[fatherrand(:,1:2),A,B]; %变异 rnd=rand(num,N); ind=rnd[m,n]=size(ind); tmp=randint(m,n,2)+1; tmp(:,1:2)=0; fatherrand=tmp+fatherrand; fatherrand=mod(fatherrand,3); %fatherrand(ind)=tmp; %评价、选择 scoreN=scorefun(fatherrand,D);%求得N个个体的评价函数 score(generation,:)=scoreN; [scoreSort,scoreind]=sort(scoreN); sumscore=cumsum(scoreSort); sumscore=sumscore./sumscore(end); childind(1:2)=scoreind(end-1:end); for k=3:N tmprnd=rand; tmpind=tmprnd difind=[0,diff(t mpind)]; if~any(difind) difind(1)=1; end childind(k)=scoreind(logical(difind)); end fatherrand=fatherrand(:,childind); generation=generation+1; end %score maxV=max(score,[],2); minV=11*300-maxV; plot(minV,'*');title('各代的目标函数值'); F4=D(:,4); FF4=F4-fatherrand(:,1); FF4=max(FF4,1); D(:,5)=FF4; save DData D function D=code load youhua.mat %properties F2and F3 F1=A(:,1); F2=A(:,2); F3=A(:,3); if(max(F2)>1450)||(min(F2)<=900) error('DATA property F2exceed it''s range (900,1450]') end %get group property F1of data,according to F2value F4=zeros(size(F1)); for ite=11:-1:1 index=find(F2<=900+ite*50); F4(index)=ite; end D=[F1,F2,F3,F4]; function ScoreN=scorefun(fatherrand,D) F3=D(:,3); F4=D(:,4); N=size(fatherrand,2); FF4=F4*ones(1,N); FF4rnd=FF4-fatherrand; FF4rnd=max(FF4rnd,1); ScoreN=ones(1,N)*300*11; %这里有待优化 人工智能实验—智能算法 实验一蚂蚁算法 一、实验目的： 理解蚂蚁算法的本质，会编写蚂蚁算法来求解TSP问题。 二、实验原理： 蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物——信息素(随着时间的推移该物质会逐渐挥发), 后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。 而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制, 通过这种正反馈机制，蚂蚁最终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。 三、实验内容： #include 课程：新技术讲座 题目：遗传算法在图像处理中的应用XX： 学号： 目录 摘要2 1.引言3 2.遗传算法的基本原理和基本性质4 3.遗传算法在图像处理中的应用6 3.1在图像增强中的应用6 3.2在图像恢复中的应用7 3.3在图像分割中的应用8 3.4在图像压缩中的应用10 3.5在图像匹配中的应用11 4.遗传算法在图像处理中的问题及发展方向12 参考文献12 遗传算法在图像处理中的应用 摘要 遗传算法是一种模拟生命进化机制，基于生物自然选择与遗传机理的随机搜索与优化方法。近几年来，遗传算法广泛应用在生物信息学、系统发生学、计算科学、工程学、经济学、化学、制造、数学、物理、药物测量学和其他领域之中，这种算法得到快速发展，尤其是在计算机科学人工智能领域中。本文将在系统并且深入的介绍遗传算法基本理论的基础上，重点综述遗传算法在数字图像处理中的主要应用，深入研究目前遗传算法在图像处理领域中存在的问题，并对这些问题作出了一些个人的见解，阐述了遗传算法在图像处理应用的发展方向。 关键词：遗传算法，数字图像处理 Abstract Genetic Algorithm is a simulation of the life evolution mechanism,random search and optimization method which is based on the natural selection and genetic mechanism.In recent years,due to the enormous potential of solving plex optimization problems and the successful applications in the industrial field,the Genetic Algorithm developed rapidly,Especially in the field of artificial intelligence in puter science.This article not only describes the basic theoretical foundation of genetic algorithms,but also focus on 一个简单实用的遗传算 法c程序 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 一个简单实用的遗传算法c程序（转载） 2009-07-28 23:09:03 阅读418 评论0 字号：大中小 这是一个非常简单的遗传算法源代码，是由Denis Cormier (North Carolina State University)开发的，Sita (University of North Carolina at Charlotte)修正。代码保证尽可能少，实际上也不必查错。对一特定的应用修正此代码，用户只需改变常数的定义并且定义“评价函数”即可。注意代码的设计是求最大值，其中的目标函数只能取正值；且函数值和个体的适应值之间没有区别。该系统使用比率选择、精华模型、单点杂交和均匀变异。如果用Gaussian变异替换均匀变异，可能得到更好的效果。代码没有任何图形，甚至也没有屏幕输出，主要是保证在平台之间的高可移植性。读者可以从,目录 coe/evol中的文件中获得。要求输入的文件应该命名为‘’；系统产生的输出文件为‘’。输入的文件由几行组成：数目对应于变量数。且每一行提供次序——对应于变量的上下界。如第一行为第一个变量提供上下界，第二行为第二个变量提供上下界，等等。 /**************************************************************************/ /* This is a simple genetic algorithm implementation where the */ /* evaluation function takes positive values only and the */ /* fitness of an individual is the same as the value of the */ /* objective function */ /**************************************************************************/ #include <> #include <> #include <> /* Change any of these parameters to match your needs */ #define POPSIZE 50 /* population size */ 自适应PID控制 摘要：自适应PID控制是一门发展得十分活跃控制理论与技术,是自适应控制理论的一个重要组成部分,本文简要回顾PID控制器的发展历程,对自适应PID控制的主要分支进行归类,介绍和评述了一些有代表性的算法。 关键词：PID控制，自适应，模糊控制，遗传算法。 Abstract: The adaptive PID control is a very active developed control theory and technology and is an important part of adaptive control theory.This paper briefly reviews the development process PID controller.For adaptive PID control of the main branches, the paper classifies,introduces and reviews some representative algorithms. Keywords: PID control, adaptive, fuzzy control, genetic algorithm 1 引言 从问世至今已历经半个世纪的PID控制器广泛地应用于冶金、机械、化工、热工、轻工、电化等工业过程控制之中，PID控制也是迄今为止最通用的控制方法， PID控制是最早发展起来的控制策略之一，因为他所涉及的设计算法和控制结构都很简单，并且十分适用于工程应用背景，所以工业界实际应用中PID 控制器是应用最广泛的一种控制策略(至今在全世界过程控制中用的80% 以上仍是纯PID调节器，若改进型包含在内则超过90%)。由于实际工业生产过程往往具有非线性和时变不确定性，应用常规PID控制器不能达到理想控制效果，长期以来人们一直寻求PID控制器参数的自动整定技术，以适应复杂的工况和高指标的控制要求。随着微机处理技术和现代控制理论诸如自适应控制、最优控制、预测控制、鲁棒控制、智能控制等控制策略引入到PID控制中，出现了许多新型PID控制器。人们把专家系统、模糊控制、神经网络等理论整合到PID控制器中，这样既保持了PID控制器的结构简单、适用性强和整定方便等优点，又通过先进控制技术在线调整PID控制器的参数，以适应被控对象特性的变化。 2 自适应PID控制概念及发展 2.1 PID控制器 常规PID控制系统原理框图如下图所示，系统由模拟PID控制器和被控对象组成。 . . 课程：新技术讲座 题目：遗传算法在图像处理中的应用姓名： 学号： 目录 摘要 (2) 1.引言 (3) 2.遗传算法的基本原理和基本性质 (3) 3.遗传算法在图像处理中的应用 (5) 3.1在图像增强中的应用 (5) 3.2在图像恢复中的应用 (6) 3.3在图像分割中的应用 (7) 3.4在图像压缩中的应用 (8) 3.5在图像匹配中的应用 (9) 4.遗传算法在图像处理中的问题及发展方向 (10) 参考文献 (10) 遗传算法在图像处理中的应用 摘要 遗传算法是一种模拟生命进化机制，基于生物自然选择与遗传机理的随机搜索与优化方法。近几年来，遗传算法广泛应用在生物信息学、系统发生学、计算科学、工程学、经济学、化学、制造、数学、物理、药物测量学和其他领域之中，这种算法得到快速发展，尤其是在计算机科学人工智能领域中。本文将在系统并且深入的介绍遗传算法基本理论的基础上，重点综述遗传算法在数字图像处理中的主要应用，深入研究目前遗传算法在图像处理领域中存在的问题，并对这些问题作出了一些个人的见解，阐述了遗传算法在图像处理应用的发展方向。 关键词：遗传算法，数字图像处理 Abstract Genetic Algorithm is a simulation of the life evolution mechanism, random search and optimization method which is based on the natural selection and genetic mechanism.In recent years,due to the enormous potential of solving complex optimization problems and the successful applications in the industrial field,the Genetic Algorithm developed rapidly,Especially in the field of artificial intelligence in computer science.This article not only describes the basic theoretical foundation of genetic algorithms,but also focus on Genetic Algorithm in digital image processing.Moreover,it studies the problems of the Genetic Algorithm in the field of image processing and the direction of development in the future，Moreover,the author elaborates the personal opinion in the end. keyword ：Genetic Algorithm,Digital image processing C语言遗传算法代码 以下为遗传算法的源代码，计算一元代函数的代码和二元函数的代码以+++++++++++++++++++++++++++++++++++++为分割线分割开来，请自行选择适合的代码，使用时请略看完代码的注释，在需要更改的地方更改为自己需要的代码。 +++++++++++++++++++++++++++++++一元函数代码++++++++++++++++++++++++++++ #include 遗传算法的C语言程序案例 一、说明 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．举个例子，输入初始变量后，用y= (x1*x1)+(x2*x2)，其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 4．程序流程图 5．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual { char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 6．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个 遗传算法经典学习Matlab代码 遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法 % % 求下列函数的最大值 % % f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] % % 将 x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为 (10-0)/(2^10-1)≈0.01 。 % % 将变量域 [0,10] 离散化为二值域 [0,1023], x=0+10*b/1023, 其 中 b 是 [0,1023] 中的一个二值数。 % % % %--------------------------------------------------------------------------------------------------------------% %--------------------------------------------------------------------------------------------------------------% % 编程 %----------------------------------------------- % 2.1初始化(编码) % initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)， % 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元 为 {0,1} 行数为popsize，列数为chromlength的矩阵， 简单对比遗传算法与蚁群算法求解旅行商问题 简单对比遗传算法与蚁群算法求解旅行商问题 1、旅行商 1.1 旅行商问题简介 旅行商问题（Traveling Saleman Problem）又称作旅行推销员问题、货郎担问题等，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出，规则虽然简单，但在地点数目增多后求解却极为复杂。 TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）！。有研究者形象地把解空间比喻为一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。 1.2 求解TSP方法简介 旅行推销员的问题属于NP-Complete的问题，所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种： 1.2.1 途程建构法（Tour Construction Procedures） 从距离矩阵中产生一个近似最佳解的途径，有以下几种解法： （1）最近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。 （2）节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。 （3）插入法（Insertion procedures）：如最近插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。 1.2.2 途程改善法（Tour Improvement Procedure） 先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法： （1）K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代目前路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。 （2）Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止。 1.2.3 合成启发法（Composite Procedure） 先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（two phase method）。有以下几种解法： （1）起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。 30维线性方程求解 摘要：非线性方程组的求解是数值计算领域中最困难的问题，大多数的数值求解算法例如牛顿法的收敛性和性能特征在很大程度上依赖于初始点。但是对于很多高维的非线性方程组，选择好的初始点是一件非常困难的事情。本文采用了遗传算法的思想，提出了一种用于求解非线性方程组的混合遗传算法。该混合算法充分发挥了遗传算法的群体搜索和全局收敛性。选择了几个典型非线性方程组，考察它们的最适宜解。 关键词：非线性方程组；混合遗传算法；优化 1. 引言遗传算法是一种通用搜索算法，它基于自然选择机制和自然遗传规律来模拟自然界的进化过程，从而演化出解决问题的最优方法。它将适者生存、结构化但同时又是 随机的信息交换以及算法设计人的创造才能结合起来，形成一种独特的搜索算法，把一些解决方案用一定的方式来表示，放在一起成为群体。每一个方案的优劣程度即为适应性，根据自然界进化“优胜劣汰”的原则，逐步产生它们的后代，使后代具有更强的适应性，这样不断演化下去，就能得到更优解决方案。 随着现代自然科学和技术的发展，以及新学科、新领域的出现，非线性科学在工农业、经济政治、科学研究方面逐渐占有极其重要的位置。在理论研究和应用实践中，几乎绝大多数的问题都最终能化为方程或方程组，或者说，都离不开方程和方程组的求解。因此，在非线性问题中尤以非线性方程和非线性方程组的求解最为基本和重要。传统的解决方法，如简单迭代法、牛顿法、割线法、延拓法、搜索法、梯度法、共轭方向法、变尺度法，无论从算法的选择还是算法本身的构造都与所要解决的问题的特性有很大的关系。很多情况下,算法中算子的构造及其有效性成为我们解决问题的巨大障碍。而遗传算法无需过多地考虑问题的具体形式，因为它是一种灵活的自适应算法，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效。而且，遗传算法是一种高度并行的算法，且算法结构简单，非常便于在计算机上实现。本文所研究的正是将遗传算法应用于求解非线性方程组的问题。 2. 遗传算法解非线性方程组为了直观地观察用遗传算法求解非线性方程组的效果，我们这里用代数非线性方程组作为求解的对象问题描述：非线性方程组指的是有n 个变量（为了简化讨论，这里只讨论实变量方程组）的方程组 中含有非线性方程。其求解是指在其定义域内找出一组数能满足方程组中的每 个方程。这里，我们将方程组转化为一个函数则求解方程组就转化为求一组值使得成立。即求使函数取得最小值0 的一组数，于是方程组求解问题就转变为函数优化问题 3. 遗传算子 遗传算子设计包括交叉算子、变异算子和选择算子的设计。 用遗传算法优化BP神经网络的Matlab编程实例 由于BP网络的权值优化是一个无约束优化问题，而且权值要采用实数编码，所以直接利用Matlab遗传算法工具箱。以下贴出的代码是为一个19输入变量，1个输出变量情况下的非线性回归而设计的，如果要应用于其它情况，只需改动编解码函数即可。 程序一：GA训练BP权值的主函数 function net=GABPNET(XX,YY) %-------------------------------------------------------------------------- % GABPNET.m % 使用遗传算法对BP网络权值阈值进行优化，再用BP算法训练网络 %-------------------------------------------------------------------------- %数据归一化预处理 nntwarn off XX=premn mx(XX); YY=premn mx(YY); %创建网络 net=newff(minmax(XX),[19,25,1],{'tansig','tansig','purelin'},'trainlm'); %下面使用遗传算法对网络进行优化 P=XX; T=YY; R=size(P,1); S2=size(T,1); S1=25;%隐含层节点数 S=R*S1+S1*S2+S1+S2;%遗传算法编码长度 aa=ones(S,1)*[-1,1]; popu=50;%种群规模 initPpp=initializega(popu,aa,'gabpEval');%初始化种群 gen=100;%遗传代数 %下面调用gaot工具箱，其中目标函数定义为gabpEval [x,endPop,bPop,trace]=ga(aa,'gabpEval',[],initPpp,[1e-6 1 1],'maxGenTerm',gen,... 'normGeomSelect',[0.09],['arithXover'],[2],'nonUnifMutation',[2 gen 3]); %绘收敛曲线图 figure(1) plot(trace(:,1),1./trace(:,3),'r-'); hold on plot(trace(:,1),1./trace(:,2),'b-');遗传算法的c语言程序
遗传算法在图像处理中的应用
MATLAB课程遗传算法实验报告及源代码
智能信息处理导论简答题
基于遗传算法的matlab源代码
智能算法实验报告
遗传算法在图像处理中应用
一个简单实用的遗传算法c程序完整版
自适应PID控制综述(完整版)
遗传算法在图像处理中的应用
遗传算法C语言源代码(一元函数和二元函数)
遗传算法的C语言程序案例
遗传算法典范MATLAB代码
简单对比遗传算法与蚁群算法求解旅行商问题
人工智能之遗传算法论文含源代码
遗传算法 (2)
相关主题
文本预览