《遗传算法》PPT课件

《《遗传算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章遗传算法一、遗传算法概述二、遗传学相关概念三、简单遗传算法四、遗传算法应用举例五、遗传算法的理论基础英国的博物学家达尔文通过研究提出了被恩格斯赞誉为“19世纪自然科学三大发现”之一的生物进化学说。达尔文的“贝格尔号”考察路线太平洋印度洋亚洲欧洲非洲南美洲北美洲大洋州大西洋生物进化的过程和原因取食果实取食昆虫取食仙人掌取食种子取食昆虫喙凿状喙不变喙尖而长喙粗而尖加拉帕戈斯雀的进化长颈鹿的进化示意图环境实验灰色桦尺蛾黑色桦尺蛾未污染区放出只数496473重新捕捉只数6230重新捕捉百分比12.5%6.3%污染区放出只数201601重新捕捉只数32205重新捕捉百分比15.9%34.1

2、%遗传算法（GeneticAlgorithm，简称GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算机算法，它由美国Holland教授1975年提出。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。一、遗传算法概述一、遗传算法概述基本思想：基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父

3、代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。一、遗传算法概述与传统的优化算法相比，遗传算法主要有以下几个不同之处遗传算法不是直接作用在参变量集上而是利用参变量集的某种编码遗传算法不是从单个点，而是从一个点的群体开始搜索；遗传算法利用适应值信息，无须导数或其它辅助信息；遗传算法利用概率转移规则，而非确定性规则。一、遗传算法概述遗传算法的优越性主要表现在：首先，它在搜索过程中不容易陷入局部最优，即使所定义的适应函数是不连续的、非规则的或有噪声的情况下，它也能以很大的概率找到整体最优解；其

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

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

6、关概念遗传操作亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作:●选择-复制(selection-reproduction)●交叉(crossover，亦称交换、交配或杂交)●变异(mutation，亦称突变)二、遗传学相关概念遗传学遗传算法数学1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个

7、体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解二、遗传学相关概念遗传学遗传算法数学9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.9011变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值,一般