《遗传算法》PPT课件.ppt

《《遗传算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《遗传算法》PPT课件.ppt（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第七章第七章 遗传算法遗传算法一、遗传算法概述一、遗传算法概述二、遗传学相关概念二、遗传学相关概念三、简单遗传算法三、简单遗传算法四、遗传算法应用举例四、遗传算法应用举例五、遗传算法的理论基础五、遗传算法的理论基础英国的博物学家英国的博物学家达尔文达尔文通过研究通过研究提出了被恩格斯提出了被恩格斯赞誉为赞誉为“19“19世纪世纪自然科学三大发自然科学三大发现现”之一的生物之一的生物进化学说。进化学说。达尔文的达尔文的“贝格尔号贝格尔号”考察路线考察路线太平洋太平洋太平洋太平洋印度洋印度洋印度洋印度洋亚洲亚洲亚洲亚洲欧洲欧洲欧洲欧洲非洲非洲非洲非洲南美洲南美洲南美洲南美洲北美洲北美洲北美洲北美洲

2、大洋州大洋州大洋州大洋州大西洋大西洋大西洋大西洋生物进化的过程和原因生物进化的过程和原因取食果实取食果实取食昆虫取食昆虫取食仙人掌取食仙人掌取食种子取食种子取食昆虫取食昆虫喙凿状喙凿状喙不变喙不变喙尖而长喙尖而长喙粗而尖喙粗而尖加拉帕戈斯雀的进化加拉帕戈斯雀的进化长颈鹿的进化示意图长颈鹿的进化示意图环环环环 境境境境实实实实 验验验验灰色桦尺蛾灰色桦尺蛾灰色桦尺蛾灰色桦尺蛾黑色桦尺蛾黑色桦尺蛾黑色桦尺蛾黑色桦尺蛾未污染区未污染区未污染区未污染区放出只数放出只数放出只数放出只数496496496496473473473473重新捕捉只数重新捕捉只数重新捕捉只数重新捕捉只数626262623030

3、3030重新捕捉百分比重新捕捉百分比重新捕捉百分比重新捕捉百分比12.5%12.5%12.5%12.5%6.3%6.3%6.3%6.3%污染区污染区污染区污染区放出只数放出只数放出只数放出只数201201201201601601601601重新捕捉只数重新捕捉只数重新捕捉只数重新捕捉只数32323232205205205205重新捕捉百分比重新捕捉百分比重新捕捉百分比重新捕捉百分比15.9%15.9%15.9%15.9%34.1%34.1%34.1%34.1%q 遗传算法（遗传算法（Genetic Algorithm，简称，简称 GA），），是模拟达尔文的遗传选择和自然淘汰的生物是模拟达尔文的

4、遗传选择和自然淘汰的生物进化过程的计算进化过程的计算机算法，它由美国机算法，它由美国 Holland 教授教授1975年提出年提出。q 遗传算法作为一种新的全局优化搜索算法，以其遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广简单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为等显著特点，奠定了它作为21世纪关键智能计算之世纪关键智能计算之一的地位一的地位。一、遗传算法概述一、遗传算法概述一、遗传算法概述一、遗传算法概述q 基本思想基本思想：u 基于模仿生物界遗传学的遗传过程，把问题的参数用基因基于模仿生物界遗传学的遗传过程，把问题的参数用

5、基因来表示，把问题的解用染色体来表示代表（在计算机里用二来表示，把问题的解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成进制码表示），从而得到一个由具有不同染色体的个体组成的群体。的群体。u 这个群体在问题特定的环境里生存竞争，适者有最好的机这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。也在生存环境的控制支配下继续这一过程。u 群体的染色体都将逐渐适应环境，不断进化，最后收敛到群体的染色体都将逐渐适应环境，不断

6、进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。一族最适应环境的类似个体，即得到问题最优解。一、遗传算法概述一、遗传算法概述q与传统的优化算法相比，遗传算法主要有以下几个与传统的优化算法相比，遗传算法主要有以下几个不同之处不同之处遗传算法不是直接作用在参变量集上而是利用参变量集遗传算法不是直接作用在参变量集上而是利用参变量集的某种编码的某种编码遗传算法不是从单个点，而是从一个点的群体开始搜索；遗传算法不是从单个点，而是从一个点的群体开始搜索；遗传算法利用适应值信息，无须导数或其它辅助信息；遗传算法利用适应值信息，无须导数或其它辅助信息；遗传算法利用概率转移规则，而非确定性规则。遗传

7、算法利用概率转移规则，而非确定性规则。一、遗传算法概述一、遗传算法概述n遗传算法的优越性主要表现在：首先，它在搜遗传算法的优越性主要表现在：首先，它在搜索过程中不容易陷入局部最优，即使所定义的索过程中不容易陷入局部最优，即使所定义的适应函数是不连续的、非规则的或有噪声的情适应函数是不连续的、非规则的或有噪声的情况下，它也能以很大的概率找到整体最优解；况下，它也能以很大的概率找到整体最优解；其次，由于它固有的并行性，遗传算法非常适其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算机。用于大规模并行计算机。一、遗传算法概述一、遗传算法概述n应用应用 遗传算法在自然科学、工程技术、商业、医学

8、、社会科学等领域遗传算法在自然科学、工程技术、商业、医学、社会科学等领域 都有应用都有应用复杂数学函数的优化；半导体器件、飞行器、通信网络、天然气管道系统、汽轮机复杂数学函数的优化；半导体器件、飞行器、通信网络、天然气管道系统、汽轮机的设计；神经网络的设计与训练；生产的规划与排序；机器人的运动轨迹生成与运的设计；神经网络的设计与训练；生产的规划与排序；机器人的运动轨迹生成与运动学解；机器多故障诊断；自动装配系统的优化设计等。动学解；机器多故障诊断；自动装配系统的优化设计等。尤其适合于寻求多参数、多设计变量或多选择的复杂工程问题的最优数值解。二、遗传学相关概念二、遗传学相关概念个体与种群个体与种

9、群 个体就是模拟生物个体而对问题中的对象个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个（一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。体也就是搜索空间中的一个点。种群种群(population)(population)就是模拟生物种群而由若就是模拟生物种群而由若 干个体组成的群体干个体组成的群体,它一般是整个搜索空间它一般是整个搜索空间 的一个很小的子集。的一个很小的子集。二、遗传学相关概念二、遗传学相关概念适应度与适应度函数适应度与适应度函数 适应度适应度(fitness)(fitness)就是借鉴生物个体对环境的就是借鉴生物个体对环境的 适

10、应程度适应程度,而对问题中的个体对象所设计的而对问题中的个体对象所设计的 表征其优劣的一种测度。表征其优劣的一种测度。适应度函数适应度函数(fitness function)(fitness function)就是问题中的就是问题中的 全体个体与其适应度之间的一个对应关系。全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。法中指导搜索的评价函数。二、遗传学相关概念二、遗传学相关概念染色体与基因染色体与基因染染色色体体（chromosomechromosome）就就是是问问题题中中个个体体的的某某种种字字符

11、符串串形形式式的的编编码码表表示示。字字符符串串中中的的字字符符也也就就称称为为基基因因（genegene）。例如：）。例如：个体 染色体 9 -1001 （2，5，6）-010 101 110二、遗传学相关概念二、遗传学相关概念遗传操作遗传操作亦称遗传算子亦称遗传算子(genetic operator)(genetic operator)，就是关于，就是关于染色体的运算。遗传算法中有三种遗传操作染色体的运算。遗传算法中有三种遗传操作:选择选择-复制复制(selection-reproduction)(selection-reproduction)交叉交叉(crossover(crossove

12、r，亦称交换、交配或杂交，亦称交换、交配或杂交)变异变异(mutation(mutation，亦称突变，亦称突变)二、遗传学相关概念二、遗传学相关概念遗传学遗传算法数学1个体个体要处理的基本对象、结构要处理的基本对象、结构也就是可行解也就是可行解2群体群体个体的集合个体的集合被选定的一组可行解被选定的一组可行解3染色体染色体个体的表现形式个体的表现形式可行解的编码可行解的编码4基因基因染色体中的元素染色体中的元素编码中的元素编码中的元素5基因位基因位某一基因在染色体中的位置某一基因在染色体中的位置元素在编码中的位置元素在编码中的位置6适应值适应值个体对于环境的适应程度，或在环个体对于环境的适应

13、程度，或在环境压力下的生存能力境压力下的生存能力可行解所对应的适应函数可行解所对应的适应函数值值7种群种群被选定的一组染色体或个体被选定的一组染色体或个体根据入选概率定出的一组根据入选概率定出的一组可行解可行解8选择选择从群体中选择优胜的个体，淘汰劣从群体中选择优胜的个体，淘汰劣质个体的操作质个体的操作保留或复制适应值大的可保留或复制适应值大的可行解，去掉小的可行解行解，去掉小的可行解二、遗传学相关概念二、遗传学相关概念遗传学遗传算法数学9交叉交叉一组染色体上对应基因段一组染色体上对应基因段的交换的交换根据交叉原则产生的根据交叉原则产生的一组新解一组新解10交叉概率交叉概率染色体对应基因段交换

14、的染色体对应基因段交换的概率（可能性大小）概率（可能性大小）闭区间闭区间0,1上的一个上的一个值，一般为值，一般为0.650.9011变异变异染色体水平上基因变化染色体水平上基因变化编码的某些元素被改编码的某些元素被改变变12变异概率变异概率染色体上基因变化的概率染色体上基因变化的概率（可能性大小）（可能性大小）开区间开区间(0,1)内的一个内的一个值值,一般为一般为0.0010.0113进化、进化、适者生存适者生存个体进行个体进行优胜劣汰的进化，优胜劣汰的进化，一代又一代地优化一代又一代地优化目标函数取到最大值，目标函数取到最大值，最优的最优的可行解可行解三、简单遗传算法三、简单遗传算法选选

15、择择-复复制制通通常常做做法法是是：对对于于一一个个规规模模为为N N的的种种群群S S,按按每每个个染染色色体体x xi iS S的的选选择择概概率率P P(x xi i)所所决决定定的的选选中中机机会会,分分N N次次从从S S中中随随机机选选定定N N个个染染色色体体,并进行复制。并进行复制。这里的选择概率这里的选择概率P P(x xi i)的计算公式为的计算公式为三、简单遗传算法三、简单遗传算法s4s2s1s355指针轮盘法指针轮盘法三、简单遗传算法三、简单遗传算法交叉：交叉：就是互换两个染色体某些位上的基因。就是互换两个染色体某些位上的基因。s1=01000101,s2=100110

16、11 s1=01000101,s2=10011011可以看做是原染色体可以看做是原染色体s1s1和和s2s2的子代染色体。的子代染色体。例如例如,设染色体设染色体 s1=01001011,s2=10010101,s1=01001011,s2=10010101,交换其后交换其后4 4位基因位基因,即即三、简单遗传算法三、简单遗传算法变异：变异：就是改变染色体某个就是改变染色体某个(些些)位上的基因。位上的基因。例如例如,设染色体设染色体 s=11001101 s=11001101，将其第三位上的，将其第三位上的0 0变变为为1,1,即即 s=11001101 s=11001101 1110110

17、1=s11101101=s。s s也可以看做是原染色体也可以看做是原染色体s s的子代染色体。的子代染色体。三、简单遗传算法三、简单遗传算法q 遗传算法基本步骤：遗传算法基本步骤：u 把这些可行解置于问题的把这些可行解置于问题的“环境环境”中，按适者生存的原中，按适者生存的原则，选取较适应环境的则，选取较适应环境的“染色体染色体”进行复制，并通过交叉、进行复制，并通过交叉、变异过程产生更适应环境的新一代变异过程产生更适应环境的新一代“染色体染色体”群群u 把问题的解表示成把问题的解表示成“染色体染色体”，在算法中就是以二进，在算法中就是以二进制编码的串，给出一群制编码的串，给出一群“染色体染色

18、体”，也就是假设的可行，也就是假设的可行解解u 经过这样的一代一代地进化，最后就会收敛到最适应环经过这样的一代一代地进化，最后就会收敛到最适应环境的一个境的一个“染色体染色体”上，它就是问题的最优解上，它就是问题的最优解三、简单遗传算法三、简单遗传算法n遗传算法具体步骤遗传算法具体步骤选择编码策略，把参数集合（可行解集合）转换染色体结构选择编码策略，把参数集合（可行解集合）转换染色体结构空间；空间；定义适应度函数，便于计算适应值；定义适应度函数，便于计算适应值；确定遗传策略，包括选择群体大小，选择、交叉、变异方法确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗

19、传参数；以及确定交叉概率、变异概率等遗传参数；随机产生初始化群体；随机产生初始化群体；三、简单遗传算法三、简单遗传算法计算群体中的个体或染色体解码后的适应值；计算群体中的个体或染色体解码后的适应值；按照遗传策略，运用选择、交叉和变异算子作用于群按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；体，形成下一代群体；判断群体性能是否满足某一指标，或者已完成预定的判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回第五步，或者修改遗传策略迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步再返回第六步遗传算法具体步骤 产生初始群体是否满足终止条件得到结果是结束程

20、序否计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进行交叉插入到新群体选择一个个体进行变异插入到新群体得到新群体四、遗传算法应用举例四、遗传算法应用举例 1例例1 利利用用遗遗传传算算法法求求解解区区间间0,31上上的的二二次次函函数数y=x2的最大值。的最大值。y=x2 31 XY 分析分析 原问题可转化为在区间原问题可转化为在区间0,31中搜索能使中搜索能使y取最取最大值的点大值的点a的问题。那么，的问题。那么，0,31 中的点中的点x就是个体就是个体,函数值函数值f(x)恰好就可以作为恰好就可以作为x的适应度，区间的适应度，区间0,31就是一个就是一个(解解)

21、空间空间。这样。这样,只要能给出个体只要能给出个体x的适当染的适当染色体编码色体编码,该问题就可以用遗传算法来解决。该问题就可以用遗传算法来解决。四、遗传算法应用举例四、遗传算法应用举例 1(1)设定种群规模设定种群规模,编码染色体，产生初始种群。编码染色体，产生初始种群。将将种种群群规规模模设设定定为为4；用用5位位二二进进制制数数编编码码染染色色体体；取取下列个体组成初始种群下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数定义适应度函数,取适应度函数：取适应度函数：f(x)=x2 四、遗传算法应

22、用举例四、遗传算法应用举例 1(3)计计算算各各代代种种群群中中的的各各个个体体的的适适应应度度,并并对对其其染染色色 体体 进进 行行 遗遗 传传 操操 作作,直直 到到 适适 应应 度度 最最 高高 的的 个个 体体(即即31（11111）)出现为止。出现为止。四、遗传算法应用举例四、遗传算法应用举例 1 首先计算种群首先计算种群S1中各个体中各个体 s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度的适应度f(si)。容易求得容易求得 f(s1)=f(13)=132=169 f(s2)=f(24)=242=576 f(s3)=f(8

23、)=82=64 f(s4)=f(19)=192=361四、遗传算法应用举例四、遗传算法应用举例 1再计算种群再计算种群S1中各个体的选择概率。中各个体的选择概率。选择概率的计算公式为选择概率的计算公式为 由此可求得由此可求得 P(s1)=P P(s2)=P(24)=0.49 P(s3)=P P(s4)=P四、遗传算法应用举例四、遗传算法应用举例 1 赌轮选择示意s40.31s20.49s10.14s30.06四、遗传算法应用举例四、遗传算法应用举例 1选择-复制 染色体 适应度选择概率选中次数s1=01101 169 0.14 1s2=11000 576 0.49 2s3=01000 64 0

24、.06 0s4=10011 361 0.31 1四、遗传算法应用举例四、遗传算法应用举例 1于是，经复制得群体：于是，经复制得群体：s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）四、遗传算法应用举例四、遗传算法应用举例 1交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）四、遗传算法应用举例四、遗传算法应用举例 1变异 设变异率pm。这样，群体S1中共有 54位

25、基因可以变异。位显然不足1位，所以本轮遗传操作不做变异。四、遗传算法应用举例四、遗传算法应用举例 1 于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）四、遗传算法应用举例四、遗传算法应用举例 1 第二代种群第二代种群S2中各染色体的情况中各染色体的情况 染色体 适应度选择概率 估计的选中次数s1=11001 625 0.36 1s2=01100 144 0.08 0s3=11011 729 0.41 2s4=10000 256 0.15 1四、遗传算法应用举例四、遗传算法应用举例 1 假设这一轮选择-复制操作中，种群

26、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）这一轮仍然不会发生变异。四、遗传算法应用举例四、遗传算法应用举例 1于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）四、遗传算法应用举例四、遗传算法应用举例 1 第三代种群第三代种群S3中各染色体的情况中各染色

27、体的情况 染色体 适应度选择概率 估计的选中次数s1=11100 784 0.44 2s2=01001 81 0.04 0s3=11000 576 0.32 1s4=10011 361 0.20 1四、遗传算法应用举例四、遗传算法应用举例 1 设这一轮的选择-复制结果为：s1=11100（28）,s2=11100（28）s3=11000（24）,s4=10011（19）做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得 s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）这一轮仍然不会发生变异。四、遗传算法应用举例四、遗传算法应用举例

28、1 于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）四、遗传算法应用举例四、遗传算法应用举例 1 显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。四、遗传算法应用举例四、遗传算法应用举例 1YYy=x2 8 13 19 24 X第一代种群及其适应度y=x2 12 16 25 27 XY第二代种群及其适应度

29、y=x2 9 19 24 28 XY第三代种群及其适应度y=x2 16 24 28 31 X第四代种群及其适应度例 用遗传算法求解TSP。分析 由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。四、遗传算法应用举例四、遗传算法应用举例 2（1）定义适应度函数 我们将一个合法的城市序列s=（c1,c2,cn,cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是 四、遗传算法应用举例四、遗传算法应用举例 2

30、（2）对个体s=（c1,c2,cn,cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。四、遗传算法应用举例四、遗传算法应用举例 2然后进行遗传操作。设 s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）实施常规的交叉或变异操作，如交换后三位，得 s1=（A,C,B,C,B,A），s2=（A,E,D,E,D,A）或者将染色体s1第二位的C变为E，得 s1=（A,E,B,E,D,A）可

31、以看出，上面得到的s1，s2和s1都是非法的城市序列。四、遗传算法应用举例四、遗传算法应用举例 2 为此，对TSP必须设计合适的染色体和相应的遗传运算。事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。四、遗传算法应用举例四、遗传算法应用举例 2为四个连锁饭店寻找最好的经营决策，其中一个经营饭店的决策包括要做出以下三项决定：

32、（1）价格 汉堡包的价格应该定在50美分还是1美元？（2）饮料 和汉堡包一起供应的应该是酒还是可乐？（3）服务速度 饭店应该提供慢的还是快的服务？目的：找到这三个决定的组合以产生最高的利润。上述问题的表示方案：共有8种表示方案用遗传算法解这个问题的第一步就是选取一个适当的表示方案。四、遗传算法应用举例四、遗传算法应用举例 3 饭店编号饭店编号 价价 格格 饮饮 料料 速速 度度二进制表示二进制表示 1 高 可乐 快 011 2 高 酒 快 001 3 低 可乐 慢 110 4 高 可乐 慢 010表表1 饭店问题的表示方案（其中的饭店问题的表示方案（其中的4个）个）群体规模N4四、遗传算法应用

33、举例四、遗传算法应用举例 3 第0代 i 串xi 适应值f（xi）1 011 3 2 001 1 3 110 6 4 010 2 总和 12 最小值 1 平均值 3.00 最大值 6表表2 初始群体中经营决策的适应值初始群体中经营决策的适应值一个简单的遗传算法由复制、杂交、变异三个算子组成四、遗传算法应用举例四、遗传算法应用举例 3 第0代 复制 i 串xi适应值f（xi）f（xi）/f（xi）串 f（xi）1 011 3 0.25 011 3 2 001 1 0.08 110 6 3 110 6 0.50 110 6 4 010 2 0.17 010 2 总和 12 17 最小值 1 2 平

34、均值 3.00 4.25 最大值 6 6表表3 使用使用复制算子复制算子后产生的交叉后产生的交叉1.复制算子：采用赌盘选择复制算子：采用赌盘选择2.杂交算子：采用一点交叉杂交算子：采用一点交叉从交配池中选择编号为1和2的串进行配对，且杂交点选在2（用分隔符|表示），杂交算子作用的结果为：01|1 010 11|0 111对交配池中指定百分比的个体应用杂交算子，假设交叉概率pc50，交配池中余下的50个体仅进行复制运算，即复制概率pr50。第 0 代 复制 第 1 代 i 串xi适应值f(xi)f（xi）/f(xi)串 f（xi）交叉点 xif（xi）1 011 3 0.25011 3 2010

35、 2 2 001 1 0.08110 6 2111 7 3 110 6 0.50110 6 110 6 4 010 2 0.17010 2 010 2 总和 12 17 17最小值 1 2 2 平均值 3.00 4.25 4.25最大值 6 6 7表表4 使用使用复制和杂交算子复制和杂交算子的作用结果的作用结果遗传算法利用复制和杂交算子可以产生具有更高平均适应值和更好个体的群体课堂练习n设有6个个体，分别具有满足度值5，10，15，25，50，100.试用指针轮盘法计算每个个体的复制次数。五、遗传算法的理论基础五、遗传算法的理论基础设满足度函数为f(x),在遗传算法中每一次迭代时，每一代个体的

36、总数为m，每个个体的编码长度为n，第g次迭代中的个体j的编码为：遗传算法的数学描述遗传算法的数学描述Xg,j=(x1g,j,x2g,j,xng,j),j=1,2,m,g=0,1,复制复制基因交换基因交换基因突变基因突变1、纲是一个相同的构形，它描述的是一个串的子集，这个集合中串之间在某些位上相同。例如，添加符号*表示不确定字母，即0或1，考虑串长为7的模式H*11*0*，则串A0111000是模式H的一个表示，对于基数为k的字母表，每一个串有（k1）l 个模式。2、纲的阶数出现在模式中确定位置的数目。在二进制中，一个模式的阶就是所有的1或0的数目。例如，模式H*11*0*的阶为33、纲的定义长

37、度模式中第一个确定位置与最后一个确定位置之间的距离例如，模式H*11*0*的定义长度r523五、遗传算法的理论基础五、遗传算法的理论基础五、遗传算法的理论基础五、遗传算法的理论基础n若用二进制字母表进行编码，一个长度为n的个体表达了2n个纲。对于有m个个体的人口，纲的总数为2nNSm2n五、遗传算法的理论基础五、遗传算法的理论基础n复制 假设一个纲S在t时刻人口中有n(S,t)个代表个体。S的一个代表个体被复制到下一代的概率和期望次数分别为f(Si)/F和f(Si)f(P),纲在t+1时刻人口中有n(s,t+1)个代表个体n(S,t+1)=n(S,t)f(S)/f(P)=n(S,0)(1+k)

38、n+1f(Si)为纲S的一个代表个体的满足度函数值；F为人口中个体满足度函数值的总和；F(S)为纲S在人口中所有代表个体的满足度函数值的平均值；f(P)为人口中所有个体的满足度函数值的平均值；五、遗传算法的理论基础五、遗传算法的理论基础n交叉S101，S2=0 1A0 1 0 0 0 1 0 1，B=1 0 1 0 1 0 0 0A0 1 0 0 1 0 0 0，B=1 0 1 0 0 1 0 1值得注意的是，S1没有代表个体，而S2有一个代表个体一个纲S由于随机交叉而丢失一个代表的概率为pL=(S)/(L-1)(S)为纲的定义长度；L为纲的长度。五、遗传算法的理论基础五、遗传算法的理论基础纲

39、S保持一个代表的概率为pr=1-(S)/(L-1)一对个体进行交叉的概率为pc，那么pr=1-pc(S)/(L-1)由此可得，纲S在下一代中的代表数目为n(S,t+1)n(S,t)f(S)/f(P)1-pc(S)/(L-1)五、遗传算法的理论基础五、遗传算法的理论基础n突变由于pm很小，该个体在突变后仍代表纲的概率可写为设pm为一个基因突变的概率，不突变的概率为1-pm；如果一个个体代表一个有o(S)个确定基因的纲，那么，该个体在突变后仍代表纲的概率为 (1-pm)o(S)1-o(S)pm五、遗传算法的理论基础五、遗传算法的理论基础n遗传算法的基本定理纲定理n(S,t+1)n(S,t)f(S)/f(P)1-pc(S)/(L-1)-o(S)pm 作业：n某个人口为4的遗传搜索过程中第i代有如下的个体和满足度值#个体 满足度110001 20211100 10300011 5401110 155 设个体交叉概率为（1与3，2与4交叉）,突变概率为，试计算确定第i1代的个体。