第七讲遗传算法PPT讲稿.ppt

《第七讲遗传算法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第七讲遗传算法PPT讲稿.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七讲遗传算法第1页，共69页，编辑于2022年，星期二英国的博物学家英国的博物学家达尔文达尔文通过研究通过研究提出了被恩格斯提出了被恩格斯赞誉为赞誉为“19“19世纪世纪自然科学三大发自然科学三大发现现”之一的生物之一的生物进化学说。进化学说。第2页，共69页，编辑于2022年，星期二达尔文的达尔文的“贝格尔号贝格尔号”考察路线考察路线太平洋太平洋太平洋太平洋印度洋印度洋印度洋印度洋亚洲亚洲亚洲亚洲欧洲欧洲欧洲欧洲非洲非洲非洲非洲南美洲南美洲南美洲南美洲北美洲北美洲北美洲北美洲大洋州大洋州大洋州大洋州大西洋大西洋大西洋大西洋第3页，共69页，编辑于2022年，星期二生物进化的过程和原因生物进

2、化的过程和原因取食果实取食果实取食昆虫取食昆虫取食仙人掌取食仙人掌取食种子取食种子取食昆虫取食昆虫喙凿状喙凿状喙不变喙不变喙尖而长喙尖而长喙粗而尖喙粗而尖加拉帕戈斯雀的进化加拉帕戈斯雀的进化第4页，共69页，编辑于2022年，星期二长颈鹿的进化示意图长颈鹿的进化示意图第5页，共69页，编辑于2022年，星期二环环 境境实实 验验灰色桦尺蛾灰色桦尺蛾黑色桦尺蛾黑色桦尺蛾未污染区未污染区放出只数放出只数496496496496473473473473重新捕捉只数重新捕捉只数6262626230303030重新捕捉百分比重新捕捉百分比12.5%12.5%12.5%12.5%6.3%6.3%6.3%6

3、.3%污染区污染区放出只数放出只数201201201201601601601601重新捕捉只数重新捕捉只数32323232205205205205重新捕捉百分比重新捕捉百分比15.9%15.9%15.9%15.9%34.1%34.1%34.1%34.1%第6页，共69页，编辑于2022年，星期二n 遗传算法（遗传算法（Genetic Algorithm，简称，简称 GA），是），是模拟达尔文的遗传选择和自然淘汰的生物进化过模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算机算法，它由美国程的计算机算法，它由美国 Holland 教授教授1975年年提出。提出。q 遗传算法作为一种新的全局优化搜

4、索算法，以其简遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广等显单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为著特点，奠定了它作为21世纪关键智能计算之一的地世纪关键智能计算之一的地位。位。一、遗传算法概述一、遗传算法概述第7页，共69页，编辑于2022年，星期二一、遗传算法概述一、遗传算法概述q 基本思想：基本思想：u 基于模仿生物界遗传学的遗传过程，把问题的参数用基因来基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的解用染色体来表示代表（在计算机里用二进制表示，把问题的解用染色体来表示代表（在计算机里用二进制码表

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

6、，编辑于2022年，星期二一、遗传算法概述一、遗传算法概述q与传统的优化算法相比，遗传算法主要有以下几个不同之与传统的优化算法相比，遗传算法主要有以下几个不同之处处遗传算法不是直接作用在参变量集上而是利用参变量集的遗传算法不是直接作用在参变量集上而是利用参变量集的某种编码某种编码遗传算法不是从单个点，而是从一个点的群体开始搜索；遗传算法不是从单个点，而是从一个点的群体开始搜索；遗传算法利用适应值信息，无须导数或其它辅助信息；遗传算法利用适应值信息，无须导数或其它辅助信息；遗传算法利用概率转移规则，而非确定性规则。遗传算法利用概率转移规则，而非确定性规则。第9页，共69页，编辑于2022年，星期

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

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

9、、遗传学相关概念二、遗传学相关概念个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个（一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。体也就是搜索空间中的一个点。种群种群(population)(population)就是模拟生物种群而由若就是模拟生物种群而由若 干个体组成的群体干个体组成的群体,它一般是整个搜索空间它一般是整个搜索空间 的一个很小的子集。的一个很小的子集。第12页，共69页，编辑于2022年，星期二二、遗传学相关概念二、遗传学相关概念适应度与适应度函数适应度与适应度函数 适应

10、度适应度(fitness)(fitness)就是借鉴生物个体对环境的就是借鉴生物个体对环境的 适应程度适应程度,而对问题中的个体对象所设计的而对问题中的个体对象所设计的 表征其优劣的一种测度。表征其优劣的一种测度。适应度函数适应度函数(fitness function)(fitness function)就是问题中的就是问题中的 全体个体与其适应度之间的一个对应关系。全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。法中指导搜索的评价函数。第13页，共69页，编辑于2022年，星期二二、遗传学相关概念二、

11、遗传学相关概念染色体与基因染色体与基因染染色色体体（chromosomechromosome）就就是是问问题题中中个个体体的的某某种种字字符符串串形形式式的的编编码码表表示示。字字符符串串中中的的字字符符也也就就称称为为基基因因（genegene）。例如：例如：个体 染色体 9 -1001 （2，5，6）-010 101 110第14页，共69页，编辑于2022年，星期二二、遗传学相关概念二、遗传学相关概念遗传操作遗传操作亦称遗传算子亦称遗传算子(genetic operator)(genetic operator)，就是关于染，就是关于染色体的运算。遗传算法中有三种遗传操作色体的运算。遗传算

12、法中有三种遗传操作:选择选择-复制复制(selection-reproduction)(selection-reproduction)交叉交叉(crossover(crossover，亦称交换、交配或杂交，亦称交换、交配或杂交)变异变异(mutation(mutation，亦称突变，亦称突变)第15页，共69页，编辑于2022年，星期二二、遗传学相关概念二、遗传学相关概念遗传学遗传算法数学1个体个体要处理的基本对象、结构要处理的基本对象、结构也就是可行解也就是可行解2群体群体个体的集合个体的集合被选定的一组可行解被选定的一组可行解3染色体染色体个体的表现形式个体的表现形式可行解的编码可行解的编

13、码4基因基因染色体中的元素染色体中的元素编码中的元素编码中的元素5基因位基因位某一基因在染色体中的位置某一基因在染色体中的位置元素在编码中的位置元素在编码中的位置6适应值适应值个体对于环境的适应程度，或在环个体对于环境的适应程度，或在环境压力下的生存能力境压力下的生存能力可行解所对应的适应函数值可行解所对应的适应函数值7种群种群被选定的一组染色体或个体被选定的一组染色体或个体根据入选概率定出的一组可根据入选概率定出的一组可行解行解8选择选择从群体中选择优胜的个体，淘汰劣从群体中选择优胜的个体，淘汰劣质个体的操作质个体的操作保留或复制适应值大的可行保留或复制适应值大的可行解，去掉小的可行解解，去

14、掉小的可行解第16页，共69页，编辑于2022年，星期二二、遗传学相关概念二、遗传学相关概念遗传学遗传算法数学9交叉交叉一组染色体上对应基因段的一组染色体上对应基因段的交换交换根据交叉原则产生的一根据交叉原则产生的一组新解组新解10交叉概率交叉概率染色体对应基因段交换的概染色体对应基因段交换的概率（可能性大小）率（可能性大小）闭区间闭区间0,1上的一个值，上的一个值，一般为一般为0.650.9011变异变异染色体水平上基因变化染色体水平上基因变化编码的某些元素被改变编码的某些元素被改变12变异概率变异概率染色体上基因变化的概率染色体上基因变化的概率（可能性大小）（可能性大小）开区间开区间(0,

15、1)内的一个值内的一个值,一般为一般为0.0010.0113进化、进化、适者生存适者生存个体进行优胜劣汰的进化，个体进行优胜劣汰的进化，一代又一代地优化一代又一代地优化目标函数取到最大值，目标函数取到最大值，最优的可行解最优的可行解第17页，共69页，编辑于2022年，星期二三、简单遗传算法三、简单遗传算法选选择择-复复制制通通常常做做法法是是：对对于于一一个个规规模模为为N N的的种种群群S S,按按每每个个染染色色体体x xi iS S的的选选择择概概率率P P(x xi i)所所决决定定的的选选中中机会机会,分分N N次从次从S S中随机选定中随机选定N N个染色体个染色体,并进行复制。

16、并进行复制。这里的选择概率这里的选择概率P P(x xi i)的计算公式为的计算公式为第18页，共69页，编辑于2022年，星期二三、简单遗传算法三、简单遗传算法s40.309s20.492s10.144s30.055指针轮盘法指针轮盘法第19页，共69页，编辑于2022年，星期二三、简单遗传算法三、简单遗传算法交叉：交叉：就是互换两个染色体某些位上的基因。就是互换两个染色体某些位上的基因。s1=01000101,s2=10011011 s1=01000101,s2=10011011可以看做是原染色体可以看做是原染色体s1s1和和s2s2的子代染色体。的子代染色体。例如例如,设染色体设染色体

17、s1=01001011,s2=10010101,s1=01001011,s2=10010101,交换交换其后其后4 4位基因位基因,即即第20页，共69页，编辑于2022年，星期二三、简单遗传算法三、简单遗传算法变异：变异：就是改变染色体某个就是改变染色体某个(些些)位上的基因。位上的基因。例如例如,设染色体设染色体 s=11001101 s=11001101，将其第三位上的，将其第三位上的0 0变为变为1,1,即即 s=11001101 11101101=s s=11001101 11101101=s。s s也可以看做是原染色体也可以看做是原染色体s s的子代染色体。的子代染色体。第21页，

18、共69页，编辑于2022年，星期二三、简单遗传算法三、简单遗传算法q 遗传算法基本步骤：遗传算法基本步骤：u 把这些可行解置于问题的把这些可行解置于问题的“环境环境”中，按适者生存的原则，中，按适者生存的原则，选取较适应环境的选取较适应环境的“染色体染色体”进行复制，并通过交叉、变异过进行复制，并通过交叉、变异过程产生更适应环境的新一代程产生更适应环境的新一代“染色体染色体”群群u 把问题的解表示成把问题的解表示成“染色体染色体”，在算法中就是以二进制编，在算法中就是以二进制编码的串，给出一群码的串，给出一群“染色体染色体”，也就是假设的可行解，也就是假设的可行解u 经过这样的一代一代地进化，

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

20、概率等遗传参数；随机产生初始化群体；随机产生初始化群体；第23页，共69页，编辑于2022年，星期二三、简单遗传算法三、简单遗传算法计算群体中的个体或染色体解码后的适应值；计算群体中的个体或染色体解码后的适应值；按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；一代群体；判断群体性能是否满足某一指标，或者已完成预定的迭代次判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步数，不满足则返回第五步，或者修改遗传策略再返回第六步第24页，共69页，编辑于2022年，星期二遗传

21、算法具体步骤 产生初始群体是否满足终止条件得到结果是结束程序否计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进行交叉插入到新群体选择一个个体进行变异插入到新群体得到新群体第25页，共69页，编辑于2022年，星期二四、遗传算法应用举例四、遗传算法应用举例 1例例1 利利用用遗遗传传算算法法求求解解区区间间0,31上上的的二二次次函函数数y=x2的的最大值。最大值。y=x2 31 XY第26页，共69页，编辑于2022年，星期二 分析分析 原问题可转化为在区间原问题可转化为在区间0,31中搜索能使中搜索能使y取最大取最大值的点值的点a的问题。那么，的问题。那么，0,3

22、1 中的点中的点x就是个体就是个体,函数值函数值f(x)恰好就可以作为恰好就可以作为x的适应度，区间的适应度，区间0,31就是一个就是一个(解解)空空间间。这样。这样,只要能给出个体只要能给出个体x的适当染色体编码的适当染色体编码,该问题就可该问题就可以用遗传算法来解决。以用遗传算法来解决。四、遗传算法应用举例四、遗传算法应用举例 1第27页，共69页，编辑于2022年，星期二(1)设定种群规模设定种群规模,编码染色体，产生初始种群。编码染色体，产生初始种群。将将种种群群规规模模设设定定为为4；用用5位位二二进进制制数数编编码码染染色色体体；取取下下列列个体组成初始种群个体组成初始种群S1:s

23、1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数定义适应度函数,取适应度函数：取适应度函数：f(x)=x2 四、遗传算法应用举例四、遗传算法应用举例 1第28页，共69页，编辑于2022年，星期二(3)计计算算各各代代种种群群中中的的各各个个体体的的适适应应度度,并并对对其其染染色色体体进进行行遗遗传传操操作作,直直到到适适应应度度最最高高的的个个体体(即即31（11111）)出出现现为止。为止。四、遗传算法应用举例四、遗传算法应用举例 1第29页，共69页，编辑于2022年，星期二 首先计算种群首先计算种群S1中各个体中各个

24、体 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)=82=64 f(s4)=f(19)=192=361四、遗传算法应用举例四、遗传算法应用举例 1第30页，共69页，编辑于2022年，星期二再计算种群再计算种群S1中各个体的选择概率。中各个体的选择概率。选择概率的计算公式为选择概率的计算公式为 由此可求得由此可求得 P(s1)=P(13)=0.14 P(s2)=P(24)=0.49 P(s3)=P(

25、8)=0.06 P(s4)=P(19)=0.31四、遗传算法应用举例四、遗传算法应用举例 1第31页，共69页，编辑于2022年，星期二 赌轮选择示意s40.31s20.49s10.14s30.06四、遗传算法应用举例四、遗传算法应用举例 1第32页，共69页，编辑于2022年，星期二选择-复制 染色体 适应度选择概率选中次数s1=01101 169 0.14 1s2=11000 576 0.49 2s3=01000 64 0.06 0s4=10011 361 0.31 1四、遗传算法应用举例四、遗传算法应用举例 1第33页，共69页，编辑于2022年，星期二于是，经复制得群体：于是，经复制得

26、群体：s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）四、遗传算法应用举例四、遗传算法应用举例 1第34页，共69页，编辑于2022年，星期二交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）四、遗传算法应用举例四、遗传算法应用举例 1第35页，共69页，编辑于2022年，星期二变异 设变异率pm=0.001。这样，群体S1中共有 540.001=0.02位基因可

27、以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。四、遗传算法应用举例四、遗传算法应用举例 1第36页，共69页，编辑于2022年，星期二 于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）四、遗传算法应用举例四、遗传算法应用举例 1第37页，共69页，编辑于2022年，星期二 第二代种群第二代种群S2中各染色体的情况中各染色体的情况 染色体 适应度选择概率 估计的选中次数s1=11001 625 0.36 1s2=01100 144 0.08 0s3=11011 729 0.41 2s4=10000 256

28、0.15 1四、遗传算法应用举例四、遗传算法应用举例 1第38页，共69页，编辑于2022年，星期二 假设这一轮选择-复制操作中，种群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第39页，共69页，编辑于2022年，星期二于是，得第三代种群S3：s1=1110

29、0（28）,s2=01001（9）s3=11000（24）,s4=10011（19）四、遗传算法应用举例四、遗传算法应用举例 1第40页，共69页，编辑于2022年，星期二 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体 适应度选择概率 估计的选中次数s1=11100 784 0.44 2s2=01001 81 0.04 0s3=11000 576 0.32 1s4=10011 361 0.20 1四、遗传算法应用举例四、遗传算法应用举例 1第41页，共69页，编辑于2022年，星期二 设这一轮的选择-复制结果为：s1=11100（28）,s2=11100（28）s3=110

30、00（24）,s4=10011（19）做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得 s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）这一轮仍然不会发生变异。四、遗传算法应用举例四、遗传算法应用举例 1第42页，共69页，编辑于2022年，星期二 于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）四、遗传算法应用举例四、遗传算法应用举例 1第43页，共69页，编辑于2022年，星期二 显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，

31、遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。四、遗传算法应用举例四、遗传算法应用举例 1第44页，共69页，编辑于2022年，星期二YYy=x2 8 13 19 24 X第一代种群及其适应度y=x2 12 16 25 27 XY第二代种群及其适应度y=x2 9 19 24 28 XY第三代种群及其适应度y=x2 16 24 28 31 X第四代种群及其适应度第45页，共69页，编辑于2022年，星期二例 4.2 用遗传算法求解TSP。分析 由于其

32、任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。四、遗传算法应用举例四、遗传算法应用举例 2第46页，共69页，编辑于2022年，星期二（1）定义适应度函数 我们将一个合法的城市序列s=（c1,c2,cn,cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是 四、遗传算法应用举例四、遗传算法应用举例 2第47页，共69页，编辑于2022年，星期二（2）对个体s=（c1,c2,cn,cn+1）进行编码。但对于

33、这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。四、遗传算法应用举例四、遗传算法应用举例 2第48页，共69页，编辑于2022年，星期二然后进行遗传操作。设 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）可以看出，上面得到的

34、s1，s2和s1都是非法的城市序列。四、遗传算法应用举例四、遗传算法应用举例 2第49页，共69页，编辑于2022年，星期二 为此，对TSP必须设计合适的染色体和相应的遗传运算。事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺顺序编码或整数编码、随机键编码、部分映射交序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。四、遗传算法应用举例四、遗传算法应用举例 2第50页，共69页，编辑于2022年，星期二为四个连锁

35、饭店寻找最好的经营决策，其中一个经营饭店的决策包括要做出以下三项决定：（1）价格 汉堡包的价格应该定在50美分还是1美元？（2）饮料 和汉堡包一起供应的应该是酒还是可乐？（3）服务速度 饭店应该提供慢的还是快的服务？目的：找到这三个决定的组合以产生最高的利润。上述问题的表示方案：共有8种表示方案用遗传算法解这个问题的第一步就是选取一个适当的表示方案。四、遗传算法应用举例四、遗传算法应用举例 3第51页，共69页，编辑于2022年，星期二 饭店编号饭店编号 价价 格格 饮饮 料料 速速 度度二进制表示二进制表示 1 高 可乐 快 011 2 高 酒 快 001 3 低 可乐 慢 110 4 高

36、可乐 慢 010表表1 饭店问题的表示方案（其中的饭店问题的表示方案（其中的4个）个）群体规模N4四、遗传算法应用举例四、遗传算法应用举例 3第52页，共69页，编辑于2022年，星期二 第0代 i 串xi 适应值f（xi）1 011 3 2 001 1 3 110 6 4 010 2 总和 12 最小值 1 平均值 3.00 最大值 6表表2 初始群体中经营决策的适应值初始群体中经营决策的适应值一个简单的遗传算法由复制、杂交、变异三个算子组成四、遗传算法应用举例四、遗传算法应用举例 3第53页，共69页，编辑于2022年，星期二 第0代 复制 i 串xi适应值f（xi）f（xi）/f（xi）

37、串 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 平均值 3.00 4.25 最大值 6 6表表3 使用使用复制算子复制算子后产生的交叉后产生的交叉1.复制算子：采用赌盘选择复制算子：采用赌盘选择第54页，共69页，编辑于2022年，星期二2.杂交算子：采用一点交叉杂交算子：采用一点交叉从交配池中选择编号为1和2的串进行配对，且杂交点选在2（用分隔符|表示），杂交算子作用的结果为：01|1 010 11|0 111对交配池中指定百分比的个体应用杂

38、交算子，假设交叉概率pc50，交配池中余下的50个体仅进行复制运算，即复制概率pr50。第55页，共69页，编辑于2022年，星期二 第 0 代 复制 第 1 代 i 串xi适应值f(xi)f（xi）/f(xi)串 f（xi）交叉点 xif（xi）1 011 3 0.25011 3 2010 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 使用使用复制和杂交算子复制和杂交算子的作用结果的作用

39、结果遗传算法利用复制和杂交算子可以产生具有更高平均适应值和更好个体的群体第56页，共69页，编辑于2022年，星期二课堂练习n设有6个个体，分别具有满足度值5，10，15，25，50，100.试用指针轮盘法计算每个个体的复制次数。第57页，共69页，编辑于2022年，星期二五、遗传算法的理论基础五、遗传算法的理论基础设满足度函数为f(x),在遗传算法中每一次迭代时，每一代个体的总数为m，每个个体的编码长度为n，第g次迭代中的个体j的编码为：遗传算法的数学描述遗传算法的数学描述Xg,j=(x1g,j,x2g,j,xng,j),j=1,2,m,g=0,1,第58页，共69页，编辑于2022年，星期

40、二复制复制第59页，共69页，编辑于2022年，星期二基因交换基因交换第60页，共69页，编辑于2022年，星期二基因突变基因突变第61页，共69页，编辑于2022年，星期二1、纲是一个相同的构形，它描述的是一个串的子集，这个集合中串之间在某些位上相同。例如，添加符号*表示不确定字母，即0或1，考虑串长为7的模式H*11*0*，则串A0111000是模式H的一个表示，对于基数为k的字母表，每一个串有（k1）l 个模式。2、纲的阶数出现在模式中确定位置的数目。在二进制中，一个模式的阶就是所有的1或0的数目。例如，模式H*11*0*的阶为33、纲的定义长度模式中第一个确定位置与最后一个确定位置之间

41、的距离例如，模式H*11*0*的定义长度r523五、遗传算法的理论基础五、遗传算法的理论基础第62页，共69页，编辑于2022年，星期二五、遗传算法的理论基础五、遗传算法的理论基础n若用二进制字母表进行编码，一个长度为n的个体表达了2n个纲。对于有m个个体的人口，纲的总数为2nNSm2n第63页，共69页，编辑于2022年，星期二五、遗传算法的理论基础五、遗传算法的理论基础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

42、)f(S)/f(P)=n(S,0)(1+k)n+1f(Si)为纲S的一个代表个体的满足度函数值；F为人口中个体满足度函数值的总和；F(S)为纲S在人口中所有代表个体的满足度函数值的平均值；f(P)为人口中所有个体的满足度函数值的平均值；第64页，共69页，编辑于2022年，星期二五、遗传算法的理论基础五、遗传算法的理论基础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

43、-1)(S)为纲的定义长度；L为纲的长度。第65页，共69页，编辑于2022年，星期二五、遗传算法的理论基础五、遗传算法的理论基础纲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)第66页，共69页，编辑于2022年，星期二五、遗传算法的理论基础五、遗传算法的理论基础n突变由于pm很小，该个体在突变后仍代表纲的概率可写为设pm为一个基因突变的概率，不突变的概率为1-pm；如果一个个体代表一个有o(S)个确定基因的纲，那么

44、，该个体在突变后仍代表纲的概率为 (1-pm)o(S)1-o(S)pm第67页，共69页，编辑于2022年，星期二五、遗传算法的理论基础五、遗传算法的理论基础n遗传算法的基本定理纲定理n(S,t+1)n(S,t)f(S)/f(P)1-pc(S)/(L-1)-o(S)pm 第68页，共69页，编辑于2022年，星期二作业：n某个人口为4的遗传搜索过程中第i代有如下的个体和满足度值#个体 满足度110001 20211100 10300011 5401110 15 设个体交叉概率为1.0（1与3，2与4交叉）,突变概率为0.001，试计算确定第i1代的个体。第69页，共69页，编辑于2022年，星期二