MATLAB遗传算法工具箱及应用

　　本书系统介绍MATLAB遗传算法工具箱的功能特点、编程原理与使用方法，全书共分为10章。第一章至第四章介绍遗传算法的基础知识，包括遗传算法的基本原理（编码、选择、交叉、变异、适应度函数、控制参数的选择、 约束条件的处理），模式定理，改进的遗传算法，未成熟收敛问题及其防止，小生境技术等。第五章和第六章介绍英国谢菲尔德（Sheffield）大学的MATLAB遗传算法工具箱及其使用方法。第七章举例说明利用谢菲尔德遗传算法工具箱函数编写求解实际优化问题的MATLAB程序。第八章和第九章分别介绍MATLAB内建的遗传算法与直接搜索工具及其使用方法。第十章利用MATLAB编程实例介绍遗传算法在图像处理中的若干应用。
　　本书取材新颖，内容丰富，逻辑严谨，语言通俗，理例结合，图文并茂，注重基础，面向应用。书中包含大量的实例，便于自学和应用。本书可作为高等院校计算机、自动化、信息、管理、控制与系统工程等专业本科生或研究生的教材或参考书，也可供其他专业的师生以及科研和工程技术人员自学或参考。

第一章 遗传算法概述 1
　1.1 遗传算法的概念 1
　1.2 遗传算法的特点 3
　　1.2.1 遗传算法的优点 3
　　1.2.2 遗传算法的不足之处 4
　1.3 遗传算法与传统方法的比较 4
　1.4 遗传算法的基本用语 6
　1.5 遗传算法的研究方向 7
　1.6 基于遗传算法的应用 8

第二章 基本遗传算法及改进 11
　2.1 遗传算法的运行过程 11
　　2.1.1 完整的遗传算法运算流程 11
　　2.1.2 遗传算法的基本操作 13
　2.2 基本遗传算法 14
　　2.2.1 基本遗传算法的数学模型 14
　　2.2.2 基本遗传算法的步骤 14
　　2.2.3 遗传算法的具体例证 16
　2.3 改进的遗传算法 22
　　2.3.1 改进的遗传算法一 23
　　2.3.2 改进的遗传算法二 24
　　2.3.3 改进的遗传算法三 25
　　2.3.4 改进的遗传算法四 27
　2.4 多目标优化中的遗传算法 29
　　2.4.1 多目标优化的概念 30
　　2.4.2 多目标优化问题的遗传算法 31


第三章 遗传算法的理论基础 33
　3.1 模式定理 33
　3.2 积木块假设 35
　3.3 欺骗问题 36
　3.4 遗传算法的未成熟收敛问题及其防止 38
　　3.4.1 遗传算法的未成熟收敛问题 38
　　3.4.2 未成熟收敛的防止 39
　3.5 性能评估 40
　3.6 小生境技术和共享函数 42


第四章 遗传算法的基本原理与方法 43
　4.1 编码 43
　　4.1.1 编码方法 44
　　4.1.2 编码评估策略 46
　4.2 选择 46
　4.3 交叉 50
　4.4 变异 53
　4.5 适应度函数 55
　　4.5.1 适应度函数的作用 55
　　4.5.2 适应度函数的设计主要满足的条件 56
　　4.5.3 适应度函数的种类 56
　　4.5.4 适应度尺度的变换 57
　4.6 控制参数的选择 58
　4.7 约束条件的处理 59

第五章 遗传算法工具箱函数 60
　5.1 工具箱结构 60
　　5.1.1 种群表示和初始化 61
　　5.1.2 适应度计算 61
　　5.1.3 选择函数 61
　　5.1.4 变异算子 62
　　5.1.5 交叉算子 62
　　5.1.6 多子群支持 62
　5.2 遗传算法中的通用函数 62
　　5.2.1 函数 bs2rv 62
　　5.2.2 函数 crtbase 64
　　5.2.3 函数 crtbp 64
　　5.2.4 函数 crtrp 65
　　5.2.5 函数 migrate 66
　　5.2.6 函数 mut 67
　　5.2.7 函数 mutate 69
　　5.2.8 函数 mutbga 70
　　5.2.9 函数 ranking 72
　　5.2.10 函数 recdis 74
　　5.2.11 函数 recint 75
　　5.2.12 函数 reclin 76
　　5.2.13 函数 recmut 77
　　5.2.14 函数 recombin 79
　　5.2.15 函数 reins 80
　　5.2.16 函数 rep 82
　　5.2.17 函数 rws 82
　　5.2.18 函数 scaling 83
　　5.2.19 函数 select 84
　　5.2.20 函数 sus 86
　　5.2.21 函数 xovdp 86
　　5.2.22 函数 xovdprs 87
　　5.2.23 函数 xovmp 88
　　5.2.24 函数 xovsh 89
　　5.2.25 函数 xovshrs 90
　　5.2.26 函数 xovsp 91
　　5.2.27 函数 xovsprs 92


第六章 遗传算法工具箱的介绍 93
　6.1 安装 93
　6.2 种群的表示和初始化 93
　6.3 目标函数和适应度函数 94
　6.4 选择 95
　6.5 交叉 97
　6.6 变异 98
　6.7 重插入 99
　6.8 遗传算法的终止 100
　6.9 数据结构 100
　6.10 多种群支持 101
　6.11 示范脚本 103

第七章 遗传算法应用举例 104
　7.1 简单一元函数优化实例 104
　7.2 多元单峰函数的优化实例 108
　7.3 多元多峰函数的优化实例 112
　7.4 收获系统最优控制 115
　7.5 装载系统的最优问题 119
　7.6 离散二次线性系统最优控制问题 122
　7.7 目标分配问题 125
　7.8 双积分的优化问题 127
　7.9 雷达目标识别问题 128
　7.10 图像增强问题 131
　7.11 一些测试函数对应的优化问题 133
　　7.11.1 轴并行超球体的最小值问题 133
　　7.11.2 旋转超球体的最小值问题 134
　　7.11.3 Rosenbrock′s Valley最小值问题 135
　　7.11.4 Rastrigin函数的最小值问题 136
　　7.11.5 Schwefel函数的最小值问题 137
　　7.11.6 Griewangk函数的最小值问题 138
　　7.11.7 不同权的总和最小值问题 139
　7.12 多目标优化问题 139

第八章 使用MATLAB遗传算法工具 143
　8.1 遗传算法与直接搜索工具箱概述 143
　　8.1.1 工具箱的特点 143
　　8.1.2 编写待优化函数的M文件 145
　8.2 使用遗传算法工具初步 146
　　8.2.1 遗传算法使用规则 147
　　8.2.2 遗传算法使用方式 147
　　8.2.3 举例：Rastrigin函数 149
　　8.2.4 遗传算法的一些术语 154
　　8.2.5 遗传算法如何工作 155
　8.3 使用遗传算法工具求解问题 158
　　8.3.1 使用遗传算法工具GUI 158
　　8.3.2 从命令行使用遗传算法 170
　　8.3.3 遗传算法举例 177
　　8.3.4 混合整数优化 196
　　8.3.5 用遗传算法求解混合整数工程设计问题 201
　8.4 遗传算法参数和函数 207
　　8.4.1 遗传算法参数 207
　　8.4.2 遗传算法函数 217
　　8.4.3 标准算法选项 223

第九章 使用MATLAB直接搜索工具 224
　9.1 直接搜索工具概述 224
　9.2 直接搜索算法 225
　　9.2.1 直接搜索 225
　　9.2.2 执行模式搜索 225
　　9.2.3 寻找函数最小值 227
　　9.2.4 模式搜索术语 229
　　9.2.5 模式搜索如何工作 230
　9.3 使用直接搜索工具 235
　　9.3.1 浏览模式搜索工具 235
　　9.3.2 从命令行运行模式搜索 245
　　9.3.3 模式搜索算法举例 248
　　9.3.4 参数化函数 267
　　9.3.5 用户绘图函数 269
　　9.3.6 向量化目标函数和约束函数 272
　　9.3.7 并行优化ODE问题 274
　9.4 模式搜索参数和函数 281
　　9.4.1 模式搜索参数 282
　　9.4.2 模式搜索函数 294
　9.5 搜索和表决 300
　　9.5.1 搜索的定义 300
　　9.5.2 搜索方法 301
　　9.5.3 搜索类型 301
　　9.5.4 搜索时机 301
　9.6 非线性约束求解算法 302

第十章 遗传算法在图像处理中的应用 303
　10.1 基于GA的图像分割方法 303
　　10.1.1 基于简单GA的图像分割阈值法 303
　　10.1.2 基于改进GA的图像分割方法 309
　10.2 最大类间方差法与GA相结合的图像分割方法 317
　10.3 最佳直方图熵法与GA相结合的图像分割方法 319
　10.4 最佳直方图熵法与改进GA相结合的图像分割方法 322
　10.5 二维最佳直方图熵法及改进GA分割图像方法 325
　10.6 基于GA的植物病害叶片中的病斑提取方法 332
　10.7 基于遗传神经网络的图像分割方法 333
　10.8 基于GA的文字提取方法 336

参考文献 340

自本书2005年第一次出版以来， 许多读者借助于本书学习遗传算法，或者尝试利用书中介绍的MATLAB遗传算法工具箱的知识来求解、研究相关领域的科学问题，使得本书成为了从事该领域研究的读者们相互推荐和引用较多的一本书。 目前，MATLAB这个在研究领域不可或缺的强大工具已经从第7版（2004年6月，Release 14）发展到了第8版（2012年9月，Release 2012b），MATLAB 7.x所包含的“遗传算法与直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox，GADS）”已经发展演变为MATLAB 8.x的“全局优化工具箱（Global Optimization Toolbox，GOT）”。
　　MATLAB第8版内置的新的“全局优化工具箱”不但完整包含了第7版的“遗传算法与直接搜索工具箱”的全部内容，而且对遗传算法和直接搜索这两种优化工具的内容进行了较大的功能扩充，新增加了一部分函数和参数，使之更加易用，功能更加强大。此外，“全局优化工具箱”还包括模拟退火工具箱（Simulated Annealing），以及优化问题设置、全局或多起始点搜索、多目标优化等内容。
　　针对这些新的变化，为了使读者更好地了解和使用MATLAB新版的遗传算法和直接搜索工具，本书在此次修订时，对于第八章中涉及遗传算法工具的内容和第九章涉及直接搜索工具的内容，都按照MATLAB最新版本的内容进行了增补，包括一些新增的函数、参数等。对于MATLAB第7版和第8版在遗传算法和直接搜索工具使用界面、参数格式、函数格式等方面的差异，也尽量予以兼顾。另外增补的第十章介绍了在MATLAB环境下用纯粹编程的方法实现遗传算法的典型应用实例。
　　在本书修订过程中，雷阳博士、孟飞翔博士、余晓东博士、刘健博士、王亚男博士等参加了相关修订工作，并对第八章、第九章新增补的内容进行了仔细整理和校核，新增补的第十章由张善文博士和王献锋博士编写，雷阳博士对全部书稿及其中的例子进行了仔细的校核，在此感谢他们的辛勤工作。
　　本书的再版，得益于众多读者的长期支持、帮助和鼓励，读者们提出的宝贵意见和真知灼见是本书汲取不尽的源泉，也感谢西安电子科技大学出版社的大力支持， 正是由于这众多的帮助和支持才使本书得以再次呈献给读者。虽然作者充分考虑到读者的需要，竭尽所能，精心编排内容，仔细测试实例，尽可能简明而准确地进行阐述， 但限于水平和时间，书中的不足之处在所难免，恳请读者不吝指正。

　 作　 者　
2013年11月



第一版前言
　MATLAB是MathWorks公司推出的一套高性能的数值计算和可视化软件。它集数值分析、矩阵运算、信号处理和图形显示于一体，构成一个方便的、界面友好的用户环境。MATLAB强大的扩展功能和影响力吸引各个领域的专家相继推出了许多基于MATLAB的专用工具箱。MATLAB强大的科学运算、灵活的程序设计流程、高质量的图形可视化与界面设计、便捷的与其他程序和语言的接口等功能，使之成为当今世界最有活力和最具影响力的可视化软件。
　遗传算法（Genetic Algorithm，简称GA）是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的高效全局寻优搜索算法。GA摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机优化搜索。它将问题域中的可能解看做是群体的一个个体或染色体，并将每一个个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传、交叉和变异）。根据预定的目标适应度函数对每个个体进行评价，依据适者生存、优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，以求得满足要求的最优解。　
　自从1975年John H．Holland教授出版关于GA的经典之作《Adaptation in Natural and Artificial Systems》以来，GA已获得广泛应用。从遗传算法的整个发展来看，20世纪70年代是兴起阶段，20世纪80年代是发展阶段，20世纪90年代是高潮阶段。遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起国内外学者的高度重视。遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域，已经广泛应用于函数优化、组合优化、自动控制、机器人学、图像处理、人工生命、遗传编码、机器学习等科技领域，并且在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面的应用已经取得了成功。
　由于GA在大量问题求解过程中独特的优点和广泛的应用，许多基于MATLAB的遗传算法工具箱相继出现，其中出现较早、影响较大、较为完备者当属英国谢菲尔德大学（The University of Sheffield）推出的基于MATLAB的遗传算法工具箱。另外，还有美国北卡罗来纳州立大学推出的可与MATLAB一起使用的遗传算法优化工具箱GAOT（Genetic Algorithm Optimization Toolbox）。考虑到前者在内容上已经覆盖到后者，因此本书将着重介绍英国谢菲尔德大学的基于MATLAB的遗传算法工具箱。值得注意的是，MathWorks公司最新发布了一个专门设计的MATLAB遗传算法与直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox），本书同时也详细介绍了这个遗传算法与直接搜索工具箱及其使用方法。 书中通过大量实例，介绍了如何利用提供的遗传算法工具箱函数来编写MATLAB程序，解决实际问题。
　在此，作者非常感谢西安电子科技大学王宝树教授、周利华教授、李荣才教授等的指导和鼓励，以及空军工程大学计算机系吕辉教授等的支持和帮助，真诚感谢西安电子科技大学出版社的大力支持。需要特别指出，虽然作者竭尽所能，精心策划章节结构和内容编排，详细测试书中的每一个实例，尽可能简明而准确地表述其意，但限于水平和资料，书中的错误和不足之处在所难免，恳请读者不吝指正。

作　 者　　
2004年10月