《遗传算法及其应用》PPT课件

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

1、第7章遗传算法及其应用第7章遗传算法及其应用7.1遗传算法的产生与发展7.2遗传算法的基本算法7.3遗传算法的改进算法7.4基于遗传算法的生产调度方法2第7章遗传算法及其应用7.1遗传算法的产生与发展7.2遗传算法的基本算法7.3遗传算法的改进算法7.4基于遗传算法的生产调度方法37.1遗传算法的产生与发展遗传算法（geneticalgorithms，GA）：一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计

2、和人工生命等领域。47.1遗传算法的产生与发展7.1.1遗传算法的生物背景7.1.2遗产算法的基本思想7.1.3遗产算法的发展历史7.1.4设计遗产算法的基本原则与内容57.1.1遗传算法的生物学背景适者生存：最适合自然环境的群体往往产生了更大的后代群体。生物进化的基本过程：染色体(chromosome)：生物的遗传物质的主要载体。基因(gene)：扩展生物性状的遗传物质的功能单元和结构单位。基因座（locus）：染色体中基因的位置。等位基因（alleles）：基因所取的值。67.1.2遗传算法的基本思想生物遗传概念遗产算法中

3、的应用适者生存目标值比较大的解被选择的可能性大个体（Individual）解染色体（Chromosome）解的编码（字符串、向量等）基因（Gene）解中每一分量的特征适应性（Fitness）适应函数值群体（Population）根据适应函数值选定的一组解（解的个数为群体的规模）婚配（Marry）交叉（Crossover）选择两个染色体进行交叉产生一组新的染色体的过程变异（Mutation）编码的某一分量发生变化的过程77.1.2遗传算法的基本思想遗传算法的基本思想：在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生

4、新的解。87.1.3遗传算法的发展历史1962年，Fraser提出了自然遗传算法。1965年，Holland首次提出了人工遗传操作的重要性。1967年，Bagley首次提出了遗传算法这一术语。1970年，Cavicchio把遗传算法应用于模式识别中。1971年，Hollstien在论文《计算机控制系统中人工遗传自适应方法》中阐述了遗传算法用于数字反馈控制的方法。1975年，美国J.Holland出版了《自然系统和人工系统的适配》；DeJong完成了重要论文《遗传自适应系统的行为分析》。20世纪80年代以后，遗传算法进入兴盛发展

5、时期。97.1.4设计遗传算法的基本原则与内容设计的基本原则：适用性：算法所能适用的问题种类。可靠性：算法对于所设计的问题，以适当的精度求解其中大多数问题的能力。收敛性：算法能否收敛到全局最优。稳定性：算法对其控制参数及问题数据的敏感度。生物类比：通过类比的方法引入在生物界被认为是有效的方法及操作。10设计的基本内容：7.1.4设计遗传算法的基本原则与内容编码方案：编码表示方式。适应度函数：目标函数。选择策略：优胜劣汰。控制参数：种群的规模、算法执行的最大代数、执行不同遗传操作的概率等。遗传算子：选择(selection)；交

6、叉(crossover)；变异(mutation)。算法的终止准则：规定一个最大的演化代数，或算法在连续多少代以后解的适应值没有改进。11第7章遗传算法及其应用7.1遗传算法的产生与发展7.2遗传算法的基本算法7.3遗传算法的改进算法7.4基于遗传算法的生产调度方法127.2遗传算法的基本算法遗传算法的五个基本要素：参数编码初始群体的设定适应度函数的设计遗传操作设计控制参数设定137.2遗传算法的基本算法7.2.1编码7.2.2群体设定7.2.3适应度函数7.2.4选择7.2.5交叉7.2.6变异7.2.7遗传算法的一般步骤1

7、47.2.1编码位串编码一维染色体编码方法：将问题空间的参数编码为一维排列的染色体的方法。二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间B={0，1}上，然后在位串空间上进行遗传操作。（1）二进制编码157.2.1编码(1)二进制编码（续）优点：类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。缺点：①相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。15：0111116：10000②要先给出求解的精度。③求解高维优化问

8、题的二进制编码串长，算法的搜索效率低。167.2.1编码位串编码（2）Gray编码Gray编码:将二进制编码通过一个变换进行转换得到的编码。二进制串Gray二进制编码Gray编码Gray编码二进制编码177.2.1编码2.实数编码采用实数表达法不必进行数制转换，可直接在解