人工智能第三章遗传算法、蚁群算法、粒子群算法

《人工智能第三章遗传算法、蚁群算法、粒子群算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章遗传算法、蚁群算法与粒子群算法8/22/202113.1遗传算法8/22/20212生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法(GeneticAlgorithm，简称GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。8/22/20213虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机制，也不完全清

2、楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的以下几个特点却为人们所共识：(1)生物的所有遗传信息都包含在其染色休中，染色体决定了生物的性状。(2)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上。(3)生物的繁殖过程是由其基因的复制过程来完成的：(4)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。(5)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。8/22/20214遗传算法是模拟生物在自然环境力的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holl

3、and教授提出，起源于60年代对自然和人工自适应系统的研究。70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在—系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。8/22/20215一、遗传算法概要式中，为决策变量，f(X)为目标函数，后两个式子为约束条件，U是基本空间，R是U的一个子集。对于一个求函数最大值的优化问题(求函数最小值也类同)，—般可描述为下述数学规划模型：满足约束条件的解X称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。它们之间的关系如图所示。8/22/20216U基本空

4、间R可行解集合X可行解8/22/20217对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之—。8/22/20218求最优解或近似最优解的方法(1)枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的

5、计算工具上都无法求解。(2)启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每—个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性，不适合于其他问题。8/22/20219(3)搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到—种较好的平衡。而遗传算法为解决这类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。8/22/202110遗传算

6、法中，将n维决策向量用n个记号Xi(n＝l，2，，n)所组成的符号串X来表示：把每一个Xi看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。—般情况下，染色体的长度n是固定的，但对一些问题n也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由0和l这两个整数组成的。相应的染色体就可表示为一个二进制符号串。8/22/202111这种编码所形成的排列形式X是个体的基因型，与它对应的x值是个体的表现型。通常个体的表现型和其基因型是一一对应的，但有时也允许基因型和表现

7、型是多对一的关系。染色休X也称为个体X。对于每一个个体X，要按照一定的规则确定出其适应度；个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。8/22/202112生物的进化是以集团为主体的。与此相对应，遗传算法的运算对