遗传算法及其应用 (2010 年度畅销榜NO.10925 )

本书系统全面地介绍了遗传算法的基本原理、设计方法及其并行实现，以及它在组合优化、机器学习、图像处理、过程控制、进化神经网络、模糊模式识别和人工生命等方面的应田。\r\n\r\n 本书可作为高等院校计算机、无线电电子学、自动控制、生物医学工程等有关专业高年级学生或研究生的教材和参考书，也可供从事人工智能、信息处理研究和应用的科技人员学习参考。\r\n
\r\n

第一章 绪论 \r\n\r\n 1. 1 引言 \r\n\r\n 1. 2 生物进化 \r\n\r\n 1. 3 遗传算法 \r\n\r\n 1. 3. 1 基础用语 \r\n\r\n 1. 3. 2 标准遗传算法 \r\n\r\n 1. 4 遗传算法的特点 \r\n\r\n 1. 4. 1 遗传算法和其它传统搜索方法的对比 \r\n\r\n 1. 4. 2 遗传算法和若干搜索方法的亲近关系 \r\n\r\n 1. 4. 3 遗传算法和自律分布系统的亲近关系 \r\n\r\n 1. 5 遗传算法的研究历史和现状 \r\n\r\n 1. 5. 1 遗传算法的研究概况 \r\n\r\n 1. 5. 2 遗传算法研究的新焦点 \r\n\r\n 1. 6 遗传算法今后研究的主要课题 \r\n\r\n 参考文献 \r\n\r\n 第二章 遗传算法的基本原理和方法 \r\n\r\n 2. 1 模式定理(schemate theorem) \r\n\r\n 2. 1. 1 模式 \r\n\r\n 2. 1. 2 模式定理 \r\n\r\n 2. 2 积木块假设 \r\n\r\n 2. 3 骗问题 \r\n\r\n 2. 4 隐并行性 \r\n\r\n 2. 5 性能评估 \r\n\r\n 2. 6 编码 \r\n\r\n 2. 6. 1 编码问题 \r\n\r\n 2. 6. 2 编码(译码)评估规范和编码原理 \r\n\r\n 2. 6. 3 编码技术 \r\n\r\n 2. 7 群体设定 \r\n\r\n 2. 7. 1 初始群体设定 \r\n\r\n 2. 7. 2 群体多样性 \r\n\r\n 2. 8适应度函数 \r\n\r\n 2. 8. 1 目标函数映射成适应度函数 \r\n\r\n 2. 8. 2 适应度函数定标(scaling) \r\n\r\n 2. 8. 3 适应度函数的设计对遗传算法的影响 \r\n\r\n 2. 9 遗传操作 \r\n\r\n 2. 9. 1 选择算子 \r\n\r\n 2. 9. 2 交叉算子(crossover operator) \r\n\r\n 2. 9. 3 变异算子(mutation operator) \r\n\r\n 2. 10 收敛性 \r\n\r\n 2. 10. 1 未成熟收敛 \r\n\r\n 2. 10. 2 有限马尔柯夫链 \r\n\r\n 2. 10. 3 标准遗传算法的收敛性 \r\n\r\n 参考文献 \r\n\r\n 第三章 遗传算法与组合优化 \r\n\r\n 3. 1 基于遗传算法的组合优化方法 \r\n\r\n 3. 1. 1 遗传算法的关键参数确定 \r\n\r\n 3. 1. 2 几种流行的选择机制 \r\n\r\n 3, 1. 3 适应度函数的定标 \r\n\r\n 3. 1. 4 二倍体(diploidy)与显性(dominance)技术 \r\n\r\n 3. 1. 5 物种形成(speciation)与小生境(niche)技术 \r\n\r\n 3. 2 函数优化(function optimization) \r\n\r\n 3. 2. 1 问题描述 \r\n\r\n 3. 2. 2 编码与适应度函数 \r\n\r\n 3. 2. 3 基本遗传算法(SGA)的搜索性能 \r\n\r\n 3. 2. 4 基本遗传算法的若干变体形式的搜索性能 \r\n\r\n 3. 3 背包问题(knapsack problem) \r\n\r\n 3. 3. 1 问题描述 \r\n\r\n 3. 3. 2 遗传编码 \r\n\r\n 3. 3. 3 适应度函数 \r\n\r\n 3. 3. 4 基于基本遗传算法求解背包问题 \r\n\r\n 3. 3. 5 基本遗传算法的搜索能力 \r\n\r\n 3. 3. 6 基于'与／或'交又方法求解背包问题 \r\n\r\n 3. 4 货郎担问题 \r\n\r\n 3. 4. 1 编码与适应度函数 \r\n\r\n 3. 4. 2 交又策略 \r\n\r\n 3. 4. 3 变异技术 \r\n\r\n 3. 4. 4 选择机制和群体构成 \r\n\r\n 3. 4. 5 混合GA技术 \r\n\r\n 3. 4. 6 基于遗传算法求解TSP的算法实现 \r\n\r\n 3. 5 混合搜索方法 \r\n\r\n 3. 5. 1 概述 \r\n\r\n 3. 5. 2 启发式搜索法简介 \r\n\r\n 3. 5. 3 混合遗传算法(Hybrid GA) \r\n\r\n 3. 5. 4 实验与讨论 \r\n\r\n 3. 6 图的划分问题 \r\n\r\n 3. 6. 1 问题描述 \r\n\r\n 3. 6. 2 编码与适应度函数设计 \r\n\r\n 3. 6. 3 遗传操作 \r\n\r\n 3. 6. 4 实验结果 \r\n\r\n 参考文献 \r\n\r\n 第四章 遗传算法与机2S学习 \r\n\r\n 4. 1 概述 \r\n\r\n 4. 2 分类器系统 \r\n\r\n 4. 2. 1 规则与消息 \r\n\r\n 4. 2. 2 桶队算法 \r\n\r\n 4. 2. 3 遗传算法 \r\n\r\n 4. 3 学习系统LS-1 \r\n\r\n 4. 3. 1 LS-1与CS-1的区别 \r\n\r\n 4. 3. 2 LS-1的工作原理 \r\n\r\n 4. 4 基于遗传算法的概念学习系统 \r\n\r\n 4. 4. 1 搜索空间的表示 \r\n\r\n 4. 4. 2 遗传操作 \r\n\r\n 4. 4. 3 执行过程 \r\n\r\n 4. 4. 4 非标准操作 \r\n\r\n 4. 4. 5 GABIL系统的自适应性 \r\n\r\n 4. 5 小结 \r\n\r\n 参考文献 \r\n\r\n 第五章 遗传算法与并行处理 \r\n\r\n 5. 1 遗传算法固有的并行性及其并行化的困难 \r\n\r\n 5. 1. 1 源于自然的并行性 \r\n\r\n 5. 1. 2 遗传算法理论中的并行性 \r\n\r\n 5. 1. 3 遗传算法在并行实观上的困难 \r\n\r\n 5. 2 遗传算法的并行化途径 \r\n\r\n 5. 2. 1 主从式(master-slave)并行化方法 \r\n\r\n 5. 2. 2 粗粒度模型 \r\n\r\n 5. 2. 3 细粒度模型 \r\n\r\n 5. 3 粗粒度的孤岛模型 \r\n\r\n 5. 3. 1 粗粒度模型的生物学依据 \r\n\r\n 5. 3. 2 粗粒度模型的研究现状 \r\n\r\n 5. 3. 3 孤岛模型在MIMD机器上的实现 \r\n\r\n 5. 3. 4 扩展的分布式遗传算法 \r\n\r\n 5. 4 细粒度的邻域模型 \r\n\r\n 5. 4. 1 细粒度模型的理论基础 \r\n\r\n 5. 4. 2 细粒度模型的研究现状 \r\n\r\n 5. 4. 3 MIMD上的细粒度模型的实现 \r\n\r\n 5. 4. 4 SIMD上的细粒度模型的实现 \r\n\r\n 5. 5 粗粒度模型与细粒度模型的性能比较 \r\n\r\n 5. 6 实现并行遗传算法的一个例子 \r\n\r\n 5. 6. 1 迁入式算法 \r\n\r\n 5. 6. 2 迁出式算法 \r\n\r\n 5. 6. 3 扩散式算法 \r\n\r\n 5. 7 LCS的并行实现 \r\n\r\n 5. 7. 1 执行系统 \r\n\r\n 5. 7. 2 信用系统中的分配策略 \r\n\r\n 5. 7. 3 遗传算法在LCS中的应用 \r\n\r\n 5. 7. 4 LCS的一个MIMD实观 \r\n\r\n 5. 7. 5 LCS在CM机器上的实现 \r\n\r\n 参考文献 \r\n\r\n 第六章 神经网络. 模糊集理论和进化算法 \r\n\r\n 6. 1 遗传算法与神经网络 \r\n\r\n 6. 1. 1 神经网络的发展 \r\n\r\n 6. 1. 2 神经网络连接权的进化 \r\n\r\n 6. 1. 3 神经网络结构的进化 \r\n\r\n 6. 1. 4 神经网络学习规则的进化 \r\n\r\n 6. 2 遗传算法与模糊集理论, \r\n\r\n 6. 2. 1 基于遗传算法的模糊推理规则的优化 \r\n\r\n 6. 2. 2 遗传算法在模糊模式识别中的应用 \r\n\r\n 6. 3 进化算法 \r\n\r\n 6. 3. 1 引言 \r\n\r\n 6. 3. 2 进化算法的总框架 \r\n\r\n 6. 3. 3 遗传算法 \r\n\r\n 6. 3. 4 进化规划 \r\n\r\n 6. 3. 5 进化策略 \r\n\r\n 6. 3. 6 交叉和变异的关系 \r\n\r\n 6. 3. 7 小结 \r\n\r\n 参考文献 \r\n\r\n 第七章 遗传算法与人工生命 \r\n\r\n 7. 1 人工生命的研究内容和方法 \r\n\r\n 7. 1. 1 人工生命及其特征 \r\n\r\n 7. 1. 2 人工生命研究的内容与方法 \r\n\r\n 7. 2 遗传算法与人工生命进化模型 \r\n\r\n 7. 3 L系统与形态生成模型 \r\n\r\n 7. 3. 1 L系统与植物形态 \r\n\r\n 7. 3. 2 植物的形态生成模型 \r\n\r\n 7. 3. 3 讨论 \r\n\r\n 7. 4 博弈型人工生态系统 \r\n\r\n 7. 4. 1 博弈与策略 \r\n\r\n 7. 4. 2 博弈型生态系统 \r\n\r\n 7. 4. 3 生态动力学与自组织化 \r\n\r\n 7. 5 人工生命与遗传信息处理 \r\n\r\n 7. 5. 1 人类信息世界 \r\n\r\n 7. 5. 2 监视遗传 \r\n\r\n 7. 5. 3 遗传信息处理模型 \r\n\r\n 7. 5. 4 基于遗传信息处理模型的人工生命合成 \r\n\r\n 7. 5. 5 人工生命与人工智能 \r\n\r\n 参考文献 \r\n\r\n 第八章 遗传算法应用实例 \r\n\r\n 8. 1 遗传算法在图像恢复中的应用 \r\n\r\n 8. 1. 1 引言 \r\n\r\n 8. 1. 2 图像退化模型 \r\n\r\n 8. 1. 3 遗传算法用于图像恢复 \r\n\r\n 8. 1. 4 遗传算法与贝叶斯方法相结合的图像恢复 \r\n\r\n 8. 2 遗传算法在图像识别中的应用 \r\n\r\n 8. 2. 1 引言 \r\n\r\n 8. 2. 2 数学模型 \r\n\r\n 8. 2. 3 目标函数形成 \r\n\r\n 8. 2. 4 随机全局优化方法 \r\n\r\n 8. 2. 5 实验结果 \r\n\r\n 8. 3 遗传算法在控制中的应用 \r\n\r\n 8. 3. 1 操作序列的最优化 \r\n\r\n 8. 3. 2 倒立摆控制 \r\n\r\n 8. 4 调度问题 \r\n\r\n 8. 4. 1 车间作业调度问题 \r\n\r\n 8. 4. 2 两种解法 \r\n\r\n 8. 4. 3 实验 \r\n\r\n 8. 5 硬件进化 \r\n\r\n 8. 5. 1 硬件进化的特点 \r\n\r\n 8. 5. 2 硬件进化的学习方法 \r\n\r\n 8. 5. 3 实例 \r\n\r\n 参考文献 \r\n\r\n 附录A SGA程序 \r\n\r\n 附录B TSP程序 \r\n\r\n 附录C CLS程序 \r\n
\r\n

近代科学技术发展的显著特点之一是生命科学与工程科学的相互交叉. 相互渗透和相互促进. 遗传算法(GA--Genetic Algorithms)的蓬勃发展正体现了学科发展的这一特征和趋势.

遗传算法的内涵哲理乃是启迪于自然界生物从低级. 简单, 到高级. 复杂, 乃至人类这样一个漫长而绝妙的进化过程, 借鉴于达尔文的物竟天演. 优胜劣汰. 适者生存的自然选择和自然遗传的机理, 其本质是一种求解问题的高效并行全局搜索方法. 它能在搜索过程中自动获取和积累有关搜索空间的知识, 并自适应地控制搜索过程以求得最优解.

使用遗传算法求解科学研究和工程技术中各种组合搜索和优化计算问题的这一基本思想, 早在60年代初期就由美国Michigan大学的J. Holland教授提出, 其数学框架也于60年代中期形成, 并且在1975年J. Holland教授编写的名著《自然与人工系统中的自适应》中予以系统的介绍. 80年代中期, 遗传算法的研究蓬勃发展, 吸引了大批的科学研究者和工程技术人员从事该领域的研究和开发应用工作. 由于遗传算法的整体搜索策略和优化计算时不依赖于梯度信息, 所以它的应用范围非常广泛, 尤其适合于处理传统搜索方法难以解决的高度复杂的非线性问题. 它在自适应控制. 组合优化. 模式识别. 机器学习. 规划策略. 信息处理和人工生命等领域的应用中展示出优越性和魅力, 从而也确定了它在21世纪的智能计算技术中的关键地位.

遗传算法的两大主要特点是群体搜索策略和群体中个体之间的信息相互交换, 它实际上是模拟由个体组成的群体的整体学习过程, 其中每个个体表示给定问题搜索空间中的一个解点. 遗传算法从任一初始化的群体出发, 通过随机选择(使群体中优秀的个体有更多的机会传给下一代). 交叉(体现了自然界中群体内个体之间的信息交换)和变异(在群体中引入新的变种确保群体中信息的多样性)等遗传操作, 使群体一代一代地进化到搜索空间中越来越好的区域, 直至抵达最优解点.

遗传算法和其它的搜索方法相比, 其优越性主要表现在以下几个方面：首先, 遗传算法在搜索过程中不易陷入局部最优, 即使在所定义的适应度函数非连续. 不规则和伴有噪声的情况下也能以极大的概率找到全局最优解, 其次, 由于遗传算法固有的并行性, 使得它非常适合于大规模并行分布处理, 此外, 遗传算法易于和别的技术(如神经网络. 模糊推理. 混沌行为和人工生命等)相结合, 形成性能更优的问题求解方法.

尽管目前对遗传算法的研究还存在着一些有争议的问题, 某些截然不同的甚至形成鲜明对照的学术观点和设计原则一时尚难统一, 而且整个遗传算法的理论基础还显得较为薄弱, 但是近30年来的不断研究和大量的实例应用充分表明, 模拟自然进化的搜索过程往往可以产生非常简单. 通用和鲁棒性很强的计算算法. 我们认为, 虽然在遗传算法研究的过程中, 还存在着某些疑虑, 但是人们不得不正视大量的研究成果为此研究领域所展示出的巨大潜力. 我们相信, 利用广泛的数学方法和强大的计算机模拟工具, 必将使遗传算法的研究取得长足的进展.

本书根据我们近期有关遗传算法的研究和教学实践, 并在综合大量有关文献资料的基础上, 进行归纳. 总结编著而成. 全书共分8章, 分别介绍了遗传算法的一般概念, 遗传算法的基本原理和方法, 遗传算法与组合优化, 遗传算法与机器学习, 遗传算法与并行处理, 神经网络. 模糊集理论和进化算法, 遗传算法与人工生命以及遗传算法的应用实例. 在附录中给出了SGA(标准遗传算法). TSP(货郎担问题)和CLS(概念学习系统)3个典型的遗传算法程序范例.

本书系集体编写, 从开始拟定章节目录到分工撰写, 大家相互讨论, 并几经修改, 最后由陈国良教授统一定稿. 参与此书有关章节编写工作的还有黄俊斌(2. 1～2.4和2. 10). 陈先富(第三章). 陈恩红(第四章). 张群(第五章). 曹先斌(6. 1和6. 3). 曹磊(7. 3)和孙启斌(8. 1和8. 2)等同志, 对于他们的辛勤劳动和贡献, 作者表示诚挚的谢意.

由于作者水平有限, 加之时间仓促, 书中不妥之处在所难免, 恳请读者批评指正.

本书的出版得到了国家攀登计划认识科学(神经网络)重大关键项目和国家自然科学基金的资助.

作者

1995年4月于中国科技大学

无封面