算法设计与分析课件 第7讲(遗传算法).pdfVIP

遗传算法的提出  遗传算法是根据自然界 “物竞天择、适者生存”的现象而提出的 一种随机有哪些信誉好的足球投注网站算法；  20世纪70年代由美国密执根大学的霍兰德（Holland）首先提 出的；  遗传算法把优化问题看作是自然界中的生物进化过程，通过模拟 大自然中生物进化过程的遗传规律，来达到寻优的目的。  生物进化圈示意图 群体 变异 选择 遭淘汰 子群 种群 的群体 婚配 人类进化图 生物进化的特性 进化过程发生在染色体上，而不是发生在他们所编码的 生物体上；  自然选择把染色体以及由他们所译成的结构的表现联系 在一起，适应性好的个体染色体比差的染色体有更多的 繁殖机会； 繁殖过程发生在进化那一刻。变异可以使生物体子代的 染色体不同于他们的父代染色体；通过结合两个父代染 色体中的物质，重组过程可以产生在子代中有很大差异 的染色体； 生物进化没有记忆。 遗传算法的基本思想 遗传算法通过自然选择中 “优胜劣汰”的策略在每次搜 索中利用各种随机的遗传算子生成问题一些新的解，淘 汰较差的解，保留较好的以及有希望的解，从而不断对 有哪些信誉好的足球投注网站空间中新的未知区域进行探索。它有效地利用了许 多历史信息，使得有哪些信誉好的足球投注网站每次都向着最好的方向前进。 对优化问题的解进行编码，编码后的一个解称为染色体， 组成染色体的元素称为基因； 一个群体由若干染色体组成，染色体的个数称为群体的 规模； 用适应度函数表示环境，它是已编码的解的函数，是一 个解适应环境程度的评价；适应函数的构造一般与优化 问题的指标函数相关； 遗传算法的基本思想 适应函数值大表示所对应的染色体适应环境的能力强， 自然选择规律将以适应函数值的大小来决定染色体是否 继续生存下去的概率； 生存下来的染色体称为种群，他们中的部分或全部以一 定的概率进行交配、繁衍，从而得到下一代群体； 交配是一个生殖过程，发生在两个染色体之间，作为双 亲的染色体，交换部分基因后，生殖出两个新的染色体， 即问题的新解； 在进化过程中，染色体的某些基因可能会发生变异，即 染色体的编码发生了某些变化。一个群体的进化需要染 色体的多样性，变异对于保持群体的多样性具有一定的 作用。 生物进化与遗传算法之间的对应关系 生物进化中的概念 遗传算法中的作用 环境 适应函数 适应性 适应函数值 适者生存 适应值大的解被保留的概率大 个体 问题的一个解 染色体 解的编码 基因 编码的元素 群体 被选定的一组解 种群 按适应函数选择的一组解（编码表示） 交配 以一定的方式由双亲产生后代的过程 变异 编码的某些分量发生变化的过程 遗传算法的基本模型 （1）遗传算法可以形式化地描述如下： GA (P(0), N ,l,s,g ,p ,f ,t) P(0) (y (0), y (0),..., y (0)) I N （2） 1 2 N 表示初始群体； （3）I