第七讲遗传算法课件

《第七讲遗传算法课件》由会员分享，可在线阅读，更多相关《第七讲遗传算法课件（69页珍藏版）》请在金锄头文库上搜索。

1、第七章 遗传算法,一、遗传算法概述 二、遗传学相关概念 三、简单遗传算法 四、遗传算法应用举例 五、遗传算法的理论基础,英国的博物学家达尔文通过研究提出了被恩格斯赞誉为“19世纪自然科学三大发现”之一的生物进化学说。,达尔文的“贝格尔号”考察路线,太平洋,印度洋,亚洲,欧洲,非洲,南美洲,北美洲,大洋州,大西洋,生物进化的过程和原因,取食果实,取食昆虫,取食仙人掌,取食种子,取食昆虫,喙凿状,喙不变,喙尖而长,喙粗而尖,加拉帕戈斯雀的进化,长颈鹿的进化示意图,遗传算法（Genetic Algorithm，简称 GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算机算法，它由美国 Hol

2、land 教授1975年提出。,遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。,一、遗传算法概述,一、遗传算法概述,基本思想：,基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。 这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。 群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似

3、个体，即得到问题最优解。,一、遗传算法概述,与传统的优化算法相比，遗传算法主要有以下几个不同之处,遗传算法不是直接作用在参变量集上而是利用参变量集的某种编码 遗传算法不是从单个点，而是从一个点的群体开始搜索； 遗传算法利用适应值信息，无须导数或其它辅助信息； 遗传算法利用概率转移规则，而非确定性规则。,一、遗传算法概述,遗传算法的优越性主要表现在：首先，它在搜索过程中不容易陷入局部最优，即使所定义的适应函数是不连续的、非规则的或有噪声的情况下，它也能以很大的概率找到整体最优解；其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算机。,一、遗传算法概述,应用,遗传算法在自然科学、工程技术、

4、商业、医学、社会科学等领域 都有应用,复杂数学函数的优化；半导体器件、飞行器、通信网络、天然气管道系统、汽轮机的设计；神经网络的设计与训练；生产的规划与排序；机器人的运动轨迹生成与运动学解；机器多故障诊断；自动装配系统的优化设计等。,尤其适合于寻求多参数、多设计变量或多选择的复杂工程问题的最优数值解。,二、遗传学相关概念,个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。,二、遗传学相关概念,适应度与适应度函数 适

5、应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。,二、遗传学相关概念,染色体与基因 染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如： 个体 染色体 9 - 1001 （2，5，6）- 010 101 110,二、遗传学相关概念,遗传操作 亦称遗传算子(genetic operator)，就是关于染色体

6、的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉(crossover，亦称交换、交配或杂交) 变异(mutation，亦称突变),二、遗传学相关概念,二、遗传学相关概念,三、简单遗传算法,选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。,这里的选择概率P(xi)的计算公式为,三、简单遗传算法,s4 0.309,s2 0.492,s1 0.144,s30.055,指针轮盘法,三、简单遗传算法,交叉：就是互换两个染色体某些位上的基因。,s1=0

7、1000101, s2=10011011 可以看做是原染色体s1和s2的子代染色体。,例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即,三、简单遗传算法,变异：就是改变染色体某个(些)位上的基因。 例如, 设染色体 s=11001101，将其第三位上的0变为1, 即 s=11001101 11101101= s。 s也可以看做是原染色体s的子代染色体。,三、简单遗传算法,遗传算法基本步骤：,把这些可行解置于问题的 “环境” 中，按适者生存的原则，选取较适应环境的“染色体”进行复制，并通过交叉、变异过程产生更适应环境的新一代 “染色体” 群,把问题的解

8、表示成 “染色体”，在算法中就是以二进制编码的串，给出一群 “染色体”，也就是假设的可行解,经过这样的一代一代地进化，最后就会收敛到最适应环境的一个 “染色体” 上，它就是问题的最优解,三、简单遗传算法,遗传算法具体步骤,选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 定义适应度函数，便于计算适应值； 确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数； 随机产生初始化群体；,三、简单遗传算法,计算群体中的个体或染色体解码后的适应值； 按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体； 判断群体性能是否满足某一指标，或者已完成预

9、定的迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步,遗传算法具体步骤,是否满足终止条件,得到结果,是,结束程序,否,计算每个个体的适应值,以概率选择遗传算子,选择一个个体复制到新群体,选择两个个体进行交叉插入到新群体,选择一个个体进行变异插入到新群体,得到新群体,四、遗传算法应用举例 1,例1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。,分析 原问题可转化为在区间0, 31中搜索能使y取最大值的点a的问题。那么，0, 31 中的点x就是个体, 函数值f(x)恰好就可以作为x的适应度，区间0, 31就是一个(解)空间 。这样, 只要能给出个体x的适当染色体编码, 该问

10、题就可以用遗传算法来解决。,四、遗传算法应用举例 1,(1) 设定种群规模,编码染色体，产生初始种群。 将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定义适应度函数, 取适应度函数：f (x)=x2,四、遗传算法应用举例 1,(3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。 ,四、遗传算法应用举例 1,首先计算种群S1中各个体 s1= 13(01101), s2=

11、 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,再计算种群S1中各个体的选择概率。,选择概率的计算公式为,由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31,四、遗传算法应

12、用举例 1,赌轮选择示意,四、遗传算法应用举例 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=0.001。 这样，群体S1中共有 540.001=0.

13、02 位基因可以变异。 0.02位显然不足1位，所以本轮遗传操作不做变异。,四、遗传算法应用举例 1,于是，得到第二代种群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）,四、遗传算法应用举例 1,第二代种群S2中各染色体的情况,四、遗传算法应用举例 1,假设这一轮选择-复制操作中，种群S2中的 4个染色体都被选中，则得到群体：,s1=11001（25）, s2= 01100（12） s3=11011（27）, s4= 10000（16）,做交叉运算，让s1与s2，s3与s4 分别交换后三位基因，得,s1 =11100（28）,

14、 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中各染色体的情况,四、遗传算法应用举例 1,设这一轮的选择-复制结果为： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19）,做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得,s1=11111（31）, s2=1110

15、0（28） s3=11000（24）, s4=10000（16）,这一轮仍然不会发生变异。,四、遗传算法应用举例 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。,四、遗传算法应用举例 1,Y,例 4.2 用遗传算

16、法求解TSP。 分析 由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。,四、遗传算法应用举例 2,（1）定义适应度函数 我们将一个合法的城市序列s=（c1, c2, , cn, cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是,四、遗传算法应用举例 2,（2）对个体s=（c1, c2, , cn, cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列