最优化问题求解之：遗传算法
遗传算法的手工模拟计算示例
为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各
个主要执行步骤。
例：求下述二元函数的最大值：
(1) 个体编码
&&&&&&&&&&
遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种
符号串。本题中，用无符号二进制整数来表示。
&&&&&&&&&&
因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它
们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可
&&&&&&&&&&
例如，基因型 X＝101110 所对应的表现型是：x＝[ 5，6 ]。
&&&&&&&&&&
个体的表现型x和基因型X之间可通过编码和解码程序相互转换。
(2) 初始群体的产生
遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始
群体数据。
本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机
方法产生。
如：，111001
&(3) 适应度汁算
遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传
机会的大小。
本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接
利用目标函数值作为个体的适应度。
选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代
群体中。&&&&&&&&&&&&&&&&&&&
本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中
的数量。其具体操作过程是：
&& 先计算出群体中所有个体的适应度的总和&
fi& ( i=1.2,…,M );
&& 其次计算出每个个体的相对适应度的大小 fi / fi ，它即为每个个体被遗传
&&&&&&&&&&&&
到下一代群体中的概率，
&& 每个概率值组成一个区域，全部概率值之和为1；
&& 最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区
&&&&&&&&&&&&
域内来确定各个个体被选中的次数。
交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某
两个个体之间的部分染色体。
本例采用单点交叉的方法，其具体操作过程是：
& 先对群体进行随机配对；
& 其次随机设置交叉点位置；
& 最后再相互交换配对染色体之间的部分基因。
变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进
行改变，它也是产生新个体的一种操作方法。
本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：
& 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，
其中的数字表示变异点设置在该基因座处；
& 然后依照某一概率将变异点的原有基因值取反。
对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。
从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得
到了明显的改进。事实上，这里已经找到了最佳个体“111111”。&&&&&&&
[注意]&&&&&&
需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，
我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中
&& 有可能需要一定的循环次数才能达到这个最优结果。
----------------------------------------------------------------------------
遗传算法属于进化算法( Evolutionary
Algorithms) 的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解.
遗传算法有三个基本算子:选择、交叉和变异.
。数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。
生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法（GA）。算法中称遗传的生物体为个体（individual），个体对环境的适应程度用适应值（fitness）表示。适应值取决于个体的染色体（chromosome），在算法中染色体常用一串数字表示，数字串中的一位对应一个基因（gene）。一定数量的个体组成一个群体（population）。对所有个体进行选择、交叉和变异等操作，生成新的群体，称为新一代（new
generation）。
遗传算法计算程序的流程可以表示如下[3]：
第一步 准备工作
（1）选择合适的编码方案，将变量（特征）转换为染色体（数字串，串长为m）。通常用二进制编码。
（2）选择合适的参数，包括群体大小（个体数M）、交叉概率PC和变异概率Pm。
（3）确定适应值函数f（x）。f（x）应为正值。
形成一个初始群体（含M个个体）。在边坡滑裂面搜索问题中，取已分析的可能滑裂面组作为初始群体。
第三步 对每一染色体（串）计算其适应值fi，同时计算群体的总适应值
第四步 选择
计算每一串的选择概率Pi=fi/F及累计概率。选择一般通过模拟旋转滚花轮（roulette，其上按Pi大小分成大小不等的扇形区）的算法进行。旋转M次即可选出M个串来。在计算机上实现的步骤是：产生[0，1]间随机数r，若r
第五步 交叉
（1）对每串产生[0，1]间随机数，若r&pc，则该串参加交叉操作，如此选出参加交叉的一组后，随机配对。
对每一对，产生[1，m]间的随机数以确定交叉的位置。
第六步 变异
如变异概率为Pm，则可能变异的位数的期望值为Pm
&m&M，每一位以等概率变异。具体为对每一串中的每一位产生[0，1]间的随机数r，若r
如新个体数达到M个，则已形成一个新群体，转向第三步；否则转向第四步继续遗传操作。直到找到使适应值最大的个体或达到最大进化代数为止。
由于选择概率是由适应值决定的，即适应值大的染色体入选概率也较大，使选择起到"择优汰劣"的作用。交叉使染色体交换信息，结合选择规则，使优秀信息得以保存，不良信息被遗弃。变异是基因中得某一位发生突变，以达到产生确实有实质性差异的新品种。遗传算法虽是一种随机算法，但它是有导向的，它所使用的"按概率随机选择"方法是在有方向的搜索方法中的一种工具。正是这种独特的搜索方法，使遗传算法自然地避开了其它最优化算法常遇到的局部最小陷阱。
遗传算法与传统的优化方法（枚举，启发式等）相比较，以生物进化为原型，具有很好的收敛性，在计算精度要求时，计算时间少，鲁棒性高等都是它的优点。
遗传算法的优点：
1. 与问题领域无关切快速随机的搜索能力。
搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较，robust.
3. 搜索使用评价函数启发，过程简单
4. 使用概率机制进行迭代，具有随机性。
5. 具有可扩展性，容易与其他算法结合。
遗传算法的缺点：&
&1、遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,
&2、另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.
3、没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢，要得要较精确的解需要较多的训练时间。
4、算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进。
5、算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的一个研究热点方向。
在现在的工作中，遗传算法（1972年提出）已经不能很好的解决大规模计算量问题，它很容易陷入“早熟”。常用混合遗传算法，合作型协同进化算法等来替代，这些算法都是GA的衍生算法。
遗传算法具有良好的全局搜索能力，可以快速地将解空间中的全体解搜索出，而不会陷入局部最优解的快速下降陷阱；并且利用它的内在并行性，可以方便地进行分布式计算，加快求解速度。但是遗传算法的局部搜索能力较差，导致单纯的遗传算法比较费时，在进化后期搜索效率较低。在实际应用中，遗传算法容易产生早熟收敛的问题。采用何种选择方法既要使优良个体得以保留，又要维持群体的多样性，一直是遗传算法中较难解决的问题。
模拟退火算法虽具有摆脱局部最优解的能力，能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。但是，由于模拟退火算法对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，使得模拟退火算法的运算效率不高。模拟退火算法对参数（如初始温度）的依赖性较强，且进化速度慢。
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
遗传算法c语言程序.doc 11页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：200 &&
遗传算法c语言程序
你可能关注的文档：
··········
··········
一 需求分析
1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数
2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。
3．测试数据
输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048&=x1,x2&=2.048作适应度函数求最大适应度即为函数的最大值
二 概要设计
1．程序流程图
2．类型定义
//种群大小
//最大世代数
struct individual
chrom[chromlength+1];
int worst_
struct indiv
//最佳个体
struct indivi //最差个体
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() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。
void calculateobjectvalue();计算适应度函数值 。
根据给定的变量用适应度函数计算然后返回适度值。
（3）选择函数selectoperator()
在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在
能被选中，以便增加下一代群体的多样性。
（4）染色体交叉函数crossoveroperator()
这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色体的交叉位的后面部分交叉即可；若大于交叉概率，则进行简单的染色体复制即可。
（5）染色体变异函数mutation()
变异是针对染色体字符变异的，而不是对个体而言，即个体变异的概率是一样。随机产生比较概率，若小于变异概率，则1变为0，0变为1，同时变异次数加1。
（6）long decodechromosome(char *,int,int)
本函数是染色体解码函数，它将以数组形式存储的二进制数转成十进制数，然后才能用适应度函数计算。
（7）void findbestandworstindividual()本函数是求最大适应度个体的，每一代的所有个体都要和初始的最佳比较，如果大于就赋给最佳。
（8）void out
正在加载中，请稍后...322494人阅读
遗传算法的手工模拟计算示例
为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各&&& 个主要执行步骤。&&&&&& 例：求下述二元函数的最大值：
&&& (1) 个体编码&&&&&&&&&& 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种&&&&&& 符号串。本题中，用无符号二进制整数来表示。&&&&&&&&&& 因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它&&&&&& 们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可&&&&&& 行解。&&&&&&&&&& 例如，基因型 X＝101110 所对应的表现型是：x＝[ 5，6 ]。&&&&&&&&&& 个体的表现型x和基因型X之间可通过编码和解码程序相互转换。
(2) 初始群体的产生&&&&&&&&& 遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始&&&&& 群体数据。&&&&&&&& 本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机&&&& 方法产生。&&&&&&&&& 如：，111001&&&&&&&&&&(3) 适应度汁算&&&&&&&&& 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传&&&&&& 机会的大小。&&&&&&&&& 本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接&&&&&& 利用目标函数值作为个体的适应度。
&(4)& 选择运算&&&&&&&&& 选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代&&&&& 群体中。&&&&&&&&&&&&&&&&&&&本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中&&&& 的数量。其具体操作过程是：&&&&&&&& && 先计算出群体中所有个体的适应度的总和& ?fi& ( i=1.2,&,M );&&&&&&&& && 其次计算出每个个体的相对适应度的大小 fi / ?fi ，它即为每个个体被遗传&&&&&&&&&&&& 到下一代群体中的概率，&&&&&&&& && 每个概率值组成一个区域，全部概率值之和为1；&&&&&&&& && 最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区&&&&&&&&&&&& 域内来确定各个个体被选中的次数。
(5)& 交叉运算&&&&&&& 交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某&&& 两个个体之间的部分染色体。&&&&&& 本例采用单点交叉的方法，其具体操作过程是：&&&&&& & 先对群体进行随机配对；&&&&&& & 其次随机设置交叉点位置；&&&&&& & 最后再相互交换配对染色体之间的部分基因。
(6)& 变异运算&&&&&&&& 变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进&&&& 行改变，它也是产生新个体的一种操作方法。&&&&&&& 本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：&&&&&&& & 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，&&&&&&&&& 其中的数字表示变异点设置在该基因座处；&&&&&&& & 然后依照某一概率将变异点的原有基因值取反。
对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。
从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得&&& 到了明显的改进。事实上，这里已经找到了最佳个体&111111&。&&&&&&&[注意]&&&&&&&&&&&&& 需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，&& 我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中&& 有可能需要一定的循环次数才能达到这个最优结果。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1251201次
积分：10129
积分：10129
排名：第1745名
原创：64篇
转载：197篇
评论：947条
(1)(1)(1)(3)(2)(4)(1)(2)(4)(2)(5)(5)(3)(2)(2)(3)(2)(5)(4)(25)(22)(10)(16)(17)(9)(26)(56)(28)(1)(2)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'基于遗传算法的高校排课系统算法改进的研究
遗传算法自上世纪诞生以来，迅速运用到复杂科学计算、工程计算、资源调度、业务优化、时间表等复杂问题的求解上。这些传统难题的症结在于构建的数学模型非常复杂，需要用到积分、微分、概率论、矩阵方面的高深数学知识并进行推导，这对于很多程序员来讲很难完成。遗传算法模拟了自然界的“物竞天择、优胜劣汰”的思想，其只需要明确问题的目标，而不需要复杂的数学推导，通过类似“进化”的程序演化过程，就可以得到理想的答案，尤其在多目标任务求解与优化上，效果更加突出。时间表问题就是一个多目标优化问题。对于规模稍微大的时间表问题，如果采用传统的穷举法，则...展开
遗传算法自上世纪诞生以来，迅速运用到复杂科学计算、工程计算、资源调度、业务优化、时间表等复杂问题的求解上。这些传统难题的症结在于构建的数学模型非常复杂，需要用到积分、微分、概率论、矩阵方面的高深数学知识并进行推导，这对于很多程序员来讲很难完成。遗传算法模拟了自然界的“物竞天择、优胜劣汰”的思想，其只需要明确问题的目标，而不需要复杂的数学推导，通过类似“进化”的程序演化过程，就可以得到理想的答案，尤其在多目标任务求解与优化上，效果更加突出。时间表问题就是一个多目标优化问题。对于规模稍微大的时间表问题，如果采用传统的穷举法，则会因为计算时间过长而失去实际意义。遗传算法为求解时间表问题提出了新的思路。排课是时间表问题中的一个特例，几乎每所学校都会涉及到，但是各个学校对于课表的要求差异性较大，需要针对性的优化。　　本文对于遗传算法在高校排课中的应用进行了研究，重点研究了基因和染色体的表示方法、三个子算子的优化、适应度的构成等方面的问题。基因采用结构体的方式，包含了更加丰富的信息，表示的概念和含义更加明确，而且也可以根据需要嵌入辅助信息;染色体采用二维数组结构，横纵坐标分别是时间和教室信息，从结构上避免了时间和教室分配方面可能引起的冲突问题，空间利用率也在可以承受的范围内。选择算子采用了灵活的方式，针对交叉和变异采用了不同的改进方案。交叉运算时，高的交叉率使得每一条染色体都有很大机率被选中，保证种群的多样性，同时又给予适应度高的染色体以更多的选择机会;变异算法时，较低的变异率保证了算法的稳定。交叉算予以1-5班的课程作为基因交换量，占染色体基因总量的2％至10％，即保证了染色体的稳定，又可以保证算法的较快收敛。变异算子采用了“定向”变异的方式，给予适应度最低的基因较高的变异机率，以期求得更好的基因;适应度高的基因也拥有一定的变异机率，以便在更广的空间上进行搜索。适应度采用了综合评价的方法，染色体的适应度由基因的适应度之和确定，引入的标志位可以给予“不合理”的基因以较高的“惩罚值”，从而对进化方向产生直接影响。收起
学位授予单位
机标分类号
本文读者也读过
加载中，请稍候
．客服电话
&&8:00-11:30,13:00-17:00(工作日)经典算法研究系列：七、深入浅出遗传算法&&&&&&&&&&&&&作者:July&&&&二零一一年一月十二日。本文参考：维基百科&&华南理工大学电子讲义&&互联网-------------------------------------------------------------------------------&一、初探遗传算法Ok，先看维基百科对遗传算法所给的解释：遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。&遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即和的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。&光看定义，可能思路并不清晰，咱们来几个清晰的图解、步骤、公式：基本遗传算法的框图：&&所以，遗传算法基本步骤是：1）&&初始化&&&←进化代数计数器；是最大进化代数；随机生成个个体作为初始群体&&&&（）；2）&&个体评价&计算（）中各个个体的适应度值；3）&&选择运算&将选择算子作用于群体；4）&&交叉运算&将交叉算子作用于群体；5）&&变异运算&将变异算子作用于群体，并通过以上运算得到下一代群体（）6）&&终止条件判断&&≦：←&转到步骤；&&&&&&&&&&&&&&&t&T：终止&输出解。&&好的，看下遗传算法的伪代码实现：▲：&&&伪代码begin&&&&&&&initialize&P(0);&&&&&&&t&=&0;&&&&&&&&&&&&&//t是进化的代数，一代、二代、三代...&&&&&&&while(t&&=&T)&do&&&&&&&&&&&&&&for&i&=&1&to&M&&do&&&& //M是初始种群的个体数&&&&&&&&&&&&&&&&&&&&&Evaluate&fitness&of&P(t);&&//计算（）中各个个体的适应度&&&&&&&&&&&&&&end&for&&&&&&&&&&&&&&for&i&=&1&to&M&&do&&&&&&&&&&&&&&&&&&&&&Select&operation&to&P(t);&&//将选择算子作用于群体&&&&&&&&&&&&&&end&for&&&&&&&&&&&&&&for&i&=&1&to&M/2&&do&&&&&&&&&&&&&&&&&&&&&Crossover&operation&to&P(t);&//将交叉算子作用于群体&&&&&&&&&&&&&&end&for&&&&&&&&&&&&&&for&i&=&1&to&M&&do&&&&&&&&&&&&&&&&&&&&&Mutation&operation&to&P(t);&&//将变异算子作用于群体&&&&&&&&&&&&&&end&for&&&&&&&&&&&&&&for&i&=&1&to&M&&do&&&&&&&&&&&&&&&&&&&&&P(t+1)&=&P(t);&&&&&&//得到下一代群体（）&&&&&&&&&&&&&&end&for&&&&&&&&&&&&&&t&=&t&+&1;&&&&&&//终止条件判断&&≦：←&转到步骤&&&&&&&end&whileend&二、深入遗传算法1、智能优化算法概述智能优化算法又称现代启发式算法，是一种具有全局优化性能、通用性强且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。&遗传算法属于智能优化算法之一。&&常用的智能优化算法有：遗传算法&、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。（本经典算法研究系列，日后将陆续阐述模拟退火算法、粒子群算法、蚁群算法。）&2、遗传算法概述遗传算法是由美国的教授于年在他的专著《自然界和人工系统的适应性》中首先提出的。借鉴生物界自然选择和自然遗传机制的随机化搜索算法。&模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象。&在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子选择、交叉和变异对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。&&基本遗传算法（，又称简单遗传算法或标准遗传算法），是由总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。&3、基本遗传算法的组成（）编码（产生初始种群）（）适应度函数（）遗传算子（选择、交叉、变异）（）运行参数&接下来，咱们分门别类，分别阐述着基本遗传算法的五个组成部分：1、编码遗传算法（）通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。基本遗传算法（）使用二进制串进行编码。&&初始种群：基本遗传算法（）采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。&2、适应度函数&遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。&&3.1、选择算子遗传算法使用选择运算对个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是从父代群体中选取一些个体，遗传到下一代群体。&基本遗传算法（）中选择算子采用轮盘赌选择方法。&Ok，下面就来看下这个轮盘赌的例子，这个例子通俗易懂，对理解选择算子帮助很大。轮盘赌选择方法轮盘赌选择又称比例选择算子，其基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为N，个体xi 的适应度为 f(xi)，则个体xi的选择概率为：&&轮盘赌选择法可用如下过程模拟来实现：(1)在［0, 1］内产生一个均匀分布的随机数r。(2)若r≤q1,则染色体x1被选中。?(3)若qk-1&r≤qk(2≤k≤N), 则染色体xk被选中。 其中的qi称为染色体xi (i=1, 2, …, n)的积累概率, 其计算公式为：&积累概率实例：&&轮盘赌选择方法的实现步骤:（1）计算群体中所有个体的适应度值；（2）计算每个个体的选择概率；（3）计算积累概率；（4）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。例如，有染色体s1= 13 (01101)s2= 24 (11000) s3= 8&& (01000)s4= 19 (10011)假定适应度为f(s)=s^2 ，则f (s1) = f(13) = 13^2 = 169f (s2) = f(24) = 24^2 = 576f (s3) = f(8) = 8^2 = 64f (s4) = f(19) = 19^2 = 361染色体的选择概率为：&染色体的累计概率为：&&根据上面的式子，可得到：&&例如设从区间［］中产生个随机数&&&&r1&=&0.450126,&&&&r2&=&0.110347&&&&r3&=&0.572496,&&&&r4&=&0.98503&&&&3.2、交叉算子交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。基本遗传算法（SGA）中交叉算子采用单点交叉算子。 单点交叉运算 3.3、变异算子&变异运算，是指改变个体编码串中的某些基因值，从而形成新的个体。变异运算是产生新个体的辅助方法，决定遗传算法的局部搜索能力，保持种群多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。基本遗传算法（SGA）中变异算子采用基本位变异算子。 基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则将其变为1；反之，若原有基因值为1，则将其变为0 。 基本位变异算子的执行过程：4、运行参数（1）M& ：种群规模 （2）T& ： 遗传运算的终止进化代数 （3）Pc& ：交叉概率 （4）Pm ：变异概率 &三、浅出遗传算法遗传算法的本质遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。遗传算法的主要有以下八方面的应用：（1）组合优化&&&&& （2）函数优化 （3）自动控制&&&&& （4）生产调度 （5）图像处理&&&&& （6）机器学习 （7）人工生命&&&&& （8）数据挖掘 &四、遗传算法的应用遗传算法的应用举例、透析本质（这个例子简明、但很重要）已知为整数，利用遗传算法求解区间［］上的二次函数的最大值。&[分析]原问题可转化为在区间［0, 31］中搜索能使 y 取最大值的点 a 的问题。个体：［0, 31］ 中的任意点x适应度：函数值f(x)=x2 解空间：区间［0, 31］这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。[解]?(1)&设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1s1= 13 (01101),& s2= 24 (11000)s3= 8 (01000),&&& s4= 19 (10011）&(2) 定义适应度函数, 取适应度函数f (x)=x^2(3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体，即31（11111）出现为止。首先计算种群S1中各个体：s1= 13(01101),&&& s2= 24(11000)s3= 8(01000),&&&&& s4= 19(10011)的适应度f (si), 容易求得：f (s1) = f(13) = 13^2 = 169f (s2) = f(24) = 24^2 = 576f (s3) = f(8) = 8^2 = 64f (s4) = f(19) = 19^2 = 361再计算种群S1中各个体的选择概率：由此可求得P(s1) = P(13) = 0.14P(s2) = P(24) = 0.49P(s3) = P(8) = 0.06P(s4) = P(19) = 0.31再计算种群中各个体的积累概率：&&选择复制&设从区间［0, 1］中产生4个随机数如下:r1 = 0.450126,&&&& r2 = 0.110347 r3 = 0.572496,&&&& r4 = 0.98503 &于是，经复制得群体：s1’ =11000（24）,& s2’ =01101（13） s3’ =11000（24）（24被选中俩次）,& s4’ =10011（19）&&&交叉设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s3’与s4’配对。s1’ =11000（24）,& s2’ =01101（13）s3’ =11000（24）,& s4’ =10011（19）分别交换后两位基因，得新染色体：s1’’=11001（25）,& s2’’=01100（12）s3’’=11011（27）,& s4’’=10000（16）&变异 &设变异率pm=0.001。这样，群体S1中共有5×4×0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。于是，得到第二代种群S2：s1=11001（25）,&& s2=01100（12）s3=11011（27）,&& s4=10000（16）第二代种群S2中各染色体的情况：&假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：&s1’=11001（25）,& s2’= 01100（12）&s3’=11011（27）,& s4’= 10000（16）做交叉运算，让s1’与s2’，s3’与s4’ 分别交换后三位基因，得 & s1’’=11100（28）,&&& s2’’ = 01001（9）& s3’’ =11000（24）,&& s4’’ = 10011（19）这一轮仍然不会发生变异。于是，得第三代种群S3：&s1=11100（28）,& s2=01001（9）&s3=11000（24）,& s4=10011（19） 第三代种群S3中各染色体的情况：设这一轮的选择复制结果为：s1’（）’（）s3’（）’（）&做交叉运算，让’与’，’与’&分别交换后两位基因，得&&s1’’（）’’（）&&s3’’（）’’（）&这一轮仍然不会发生变异。&&于是，得第四代种群：&s1=11111（）出现最优解（）s3=11000（）（）&显然，在这一代种群中已经出现了适应度最高的染色体。&于是，遗传操作终止，将染色体（）作为最终结果输出。然后，将染色体“”解码为表现型，即得所求的最优解：。将代入函数中，即得原问题的解，即函数的最大值为。&&所以，综合以上各代群的情况，如下：ok，完。文章有误之处，一经发现，立马修正。同时，也望各位不吝指正。-------------------------------------------&&本人July对本博客所有文章和资料享有版权，转载或引用任何文章、资料请注明出处。向您的厚道致敬。谢谢。 July、二零一一年一月十二日。
阅读(...) 评论()}