第5章 智能优化算法 第4章介绍了搜索的概念，通过搜索方法的应用，从理论上讲能够找到所有优化问题的全局最优解。 实际上并非如此，如某些问题的规模很大，状态空间极为复杂，即使采用目前最快的巨型计算机，也要花费很长时间 (数天、数年甚至更长时间)才能得到结果，这在现实生活中是无法接受的。于是， 考虑这样一类优化方法，能在可接受的时间内 给出较优化的用户满意解(次优解) 而非全局最优解。本章介绍的智能优化算法就是这样的方法。本章 首先介绍邻域的概念、基于局部搜索算法的思路，在此基础上介绍几种常用的智能优化方法。 5.1智能优化算法概述 5.1.1优化问题的复杂度 在电子、通信、计算机、自动化、机器人、经济学和管理学等众多学科中不断出现了许多复杂的组合优化问题。 例5.101背包问题。 给定n种物品和1个背包，物品i的重量是Wi、价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 在该问题中，任一物品只有放入背包或不放入背包 两种选择，对应可用1或0分别表示，所以称为01背包问题，其本质上属于组合优化问题，即通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。在此类问题中 往往需要在庞大的搜索空间中寻找最优解或者准最优解。若采用传统优化方法(如 搜索方法)需要遍历整个搜索空间， 问题规模较大时会出现“组合爆炸”现象，算法难以在有效时间内完成搜索。鉴于实际工程问题的复杂性、非线性、约束性以及建模困难等特点，寻求高效的智能优化算法已成为热门研究内容之一。 优化问题按照其求解的复杂程度可以分为以下四类。 (1) P类问题： 所有可以在多项式时间内求解的判定问题构成P类问题。 (2) 非确定性多项式(Nondeterministic Polynomial，NP)类问题： 复杂问题不能确定是否在多项式时间内找到答案，但可以在多项式时间内验证答案是否正确。显然，P类问题是NP类问题的子集。 长期以来，研究人员一直试图搞清楚 NP类问题是否等于P类问题，即那些能在多项式时间内验证得出正确解的问题，是否都是具有多项式时间求解算法的问题呢？如果解决了这个问题，所有的NP问题都可以通过计算机解决，因为它们都存在多项式时间求解算法。 (3) NP完全(NPComplete，NPC)问题： 为了论证“NP类问题是否等于P类问题” ，研究人员想了很多办法，其中之一 是问题约化。 问题约化： 如果用问题B的算法 可以解决问题A，那么问题A可以简化成问题B。 如果存在这样一个NP问题，所有的NP问题都可以约化成它，则该问题称为NP完全问题。换句话说，只要找到某个NP完全问题的多项式时间求解算法，那么所有的NP问题都解决。 (4) NP难(NPHard)问题： NP完全问题需要满足 它是一个NP问题，以及 所有的NP问题都可以约化到它。 NP难问题是 满足NP完全问题定义的第二条但不一定 满足第一条，即所有的NP问题都能约化到它，但 它本身不一定是NP问题。显然，NP难问题 比NP完全问题的范围大，因为NP难问题没有限定属于NP类问题，即NP完全问题是NP难问题的子集。 目前尚未找到任何一个NP完全问题或NP难问题的多项式时间求解算法，只能用穷举法逐个检验，计算时间随问题的复杂程度通常呈指数增长。 在实际中，针对NP难问题，为了在有效时间内给出求解结果，通常 是降低对NP难问题解的最优化要求，即不一定寻找最优解，而是寻找接近最优解的次优解(用户满意解)。本章要介绍的智能优化算法采用了这样的求解思路，是NP难问题最有效的求解方法之一。 5.1.2典型智能优化算法 针对典型的NP难问题，传统优化算法搜索空间巨大，甚至可能搜索不到最优解。受到人类智能、生物群体社会性或自然现象规律的启发，研究人员提出很多智能优化算法来解决复杂优化问题，此类方法都是通过模拟或揭示某些自然界的现象和过程或生物群体的智能行为而得到发展。此类方法具有简单、通用、便于并行处理等特点，并可寻找到全局最优解或是接近全局最优的结果，在优化领域称它们为智能优化算法。 智能优化算法在解决大空间、非线性、全局寻优、组合优化等复杂优化问题方面所具有的独特优势,得到了国内外学者的广泛关注，目前已发展出许多有效的智能优化算法， 比较典型的有依据固体物质退火过程和组合优化问题之间相似性提出的模拟退火算法、模仿自然界生物进化机制的遗传算法、模仿蚁群觅食路径选择的蚁群优化算法以及鱼群或鸟群运动行为的粒子群算法等。 本章将针对上述智能优化算法分别进行介绍。在介绍具体智能优化算法之前，首先引入邻域的概念，并介绍基于邻域的局部搜索算法。 5.1.3邻域的概念 邻域是智能优化算法中一个非常重要的概念，也是众多智能优化算法完成求解的基础。对于函数优化问题，邻域可定义为 在距离空间中以一点为中心的一个超球体。对于组合优化问题，邻域可定义为 N:x∈D→N(x)∈2D，且x∈N(x)，称为一个邻域映射。其中，2D表示D的所有子集组成的集合，N(x)称为x的邻域。如果y∈N(x)，则称y为x的一个邻居。 邻域的构造依赖问题决策变量的表示，邻域的结构在现代智能化优化算法中起重要作用。 下面通过例子说明邻域的构造方式和应用方法。 例5.2旅行商问题的邻域。 旅行商问题(Traveling Salesman Problem，TSP)是典型的NPC问题，其可描述为假设有一个旅行商人要访问N个城市，他必须选择所要走的路径，路径的限制是每个城市只能访问一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径中的最小值。 TSP解的一种表示方法为 D={x=(i1,i2,…,in)|i1,i2,…,in是城市序号的排列}。可定义它的邻域映射为2opt，即x中的两个元素进行对换，即N(x)中共包含x的C2n=n(n-1)/2个邻居和x本身。 以4个城市的TSP为例，当x=(1,2,3,4)时，表示旅行商从1号城市出发，以此经过2、3、4号城市，最终回到1号城市。此时，C24=6，则x的邻域N(x)={(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3),(1,2,3,4)}。 类似可定义kopt(k≥2)，即对k个元素按一定规则互换。k的取值不同，邻域的结构也将完全不同。 5.1.4局部搜索算法 基于邻域的概念可设计局部搜索算法求解TSP。方法如下。 Step1： 选定一个初始可行解x0，记录当前最优解xbest∶=x0,设T=N(xbest)。 Step2： 当T＼{xbest}=，或满足其他停止运算准则时，输出计算结果，停止运算； 否则，从T中选一集合S，得到S中的最好解xnow； 若f(xnow) 43，则xbest=(ACBDE)，不变。 上述步骤可继续进行，直到算法退出。 一步搜索算法又称为随机爬山算法。随机爬山算法通过在邻域中随机选择解的方式探索更优化解，但其只能接受比当前找到的最好解xbest更好的解，否则，保持xnow=xbest不变。显然，这个特性容易使局部搜索算法陷入局部最优解，如图5.2 所示。 图5.2局部最优解与全局最优解示意图 由此可见，局部搜索算法有如下特点： （1） 简单易行，但无法保证全局最优性； （2） 局部搜索主要依赖起点的选取和邻域的结构； （3） 为了得到好的解，可以比较不同的邻域结构和不同的初始点； （4） 如果初始点的选择足够多，总可以计算出全局最优解。 显然，局部搜索算法的“智能性”还不够强，但其对于邻域的构造和利用是现代智能优化算法的思想基础。下面介绍几种典型的智能优化算法。 5.2模拟退火算法 5.2.1模拟退火算法的原理 模拟退火算法 思想最早由Metropolis等于1953年提出，1983年Kirkpatrick等将其应用于组合优化，用于解决NPHard问题。 与局部搜索算法相比，该方法 克服初值依赖性，而且改善优化过程，避免陷入局部极值。 顾名思义，该算法是对现实生活中物理退火过程的模拟。在物理退火过程中，首先 把固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，达到某种稳定固体状态。这一过程可概括为以下三个核心流程。 （1） 加温过程： 增强粒子的热运动，消除系统原先可能存在的非均匀态。 （2） 等温过程： 对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。 （3） 冷却过程： 使粒子热运动减弱并渐趋有序，系统能量逐渐下降，得到低能的晶体结构。 图5.3 (a)到图5.3(b)是加温过程，图5.3(b)到图5.3(c)是冷却过程，而等温过程发生在图5.3(b)中。 图5.3物理退火三个过程 模拟退火算法主要对其中的等温过程进行模拟。在该过程中，系统状态总体趋势是自由能由高到低变化，但也有随机的分子从低向高变化。对该过程进行理论描述，物理学的研究表明，在温度T时，分子停留在状态r的概率服从玻耳兹曼分布，即 P{=E(r)}=1Z(T)exp -E(r)kBT(51) 式中： 为分子能量的一个随机变量； E(r)为状态r的能量； kB为玻耳兹曼常数，kB>0； Z(T)为概率标准化因子(常数)，且有 Z(T)=∑s∈Dexp-E(s)kBT(52) 式中： D为状态空间。 假设同一个温度T，有两个能量状态E1和E2，且E10 可知 P{=E1}-P{=E2}>0 可见，在同一温度下分子停留在 低能量状态的概率大于停留在高能量状态的概率。由式(53)可进一步推断出，随着温度的降低，分子停留在最低能量状态的概率加大。值得注意的是，这里存在一定随机性，即分子停留在低能量状态的概率会更大一些，并不代表分子一定只向能量低的状态变化。 为了模拟上述固体在恒定温度下达到热平衡的过程，可以用蒙特卡洛方法(计算机随机模拟方法)进行模拟； 该方法虽然思路简单，但必须大量采样才能得到比较精确的结果，计算量很大。 为使模拟固体等温过程更加快速可行，Metropolis于1953年提出以概率接受新状态的准则，也称为Metropolis准则。其核心思想为对于温度T，由当前状态i转移到新状态j， 若Ej≤Ei，则直接接受状态 j 为当前状态； 若概率P=exp-Ej-EikBT大于［0,1)区间内的随机数，则接受状态j 为当前状态，否则维持状态i不变。 Metropolis准则表明： 若新状态的能量变小，则必定接受； 若新状态能量变大，则以一定概率接受。在相同温度下，状态之间的能量差值越大，由低能量态向高能量态转换成功的概率就越小。若温度很高，则系统以较大概率接受一切状态。若温度接近0，则系统不接受任何更高能量的状态。可见，温度越高，接受从低能量状态到高能量状态转换的概率就越大。在高温下 可接受与当前状态能量差较大的新状态，在低温下只接受与当前状态能量差较小的新状态。 将组合优化问题与物理退火过程相对比，各种状态或参数的对应相似性如表5.1 所示。 表5.1组合优化与物理退火相似性 组合优化问题物 理 退 火组合优化问题物 理 退 火 解粒子状态Metropolis抽样过程等温过程 最优解能量最低状态控制参数的下降冷却 设定初温熔解过程目标函数能量 因此，Metropolis抽样准则为计算机模拟物理退火过程提供了可能。由表5.1列出 的关联关系，可以通过计算机模拟物理退火过程求解复杂的优化问题，这就是模拟退火算法的核心思想。模拟退火算法流程如图5.4 所示。 图5.4模拟退火算法流程 5.2.2模拟退火算法的描述 算法5.1模拟退火算法。 给定初温t=t0，随机产生初始状态s=s0，令k=0； Repeat//外循环 Repeat//内循环 产生新状态sj=Genete(s)； if min1,exp-C(sj)-C(s)/tk >=random［0,1］ s=sj； Until 抽样稳定准则满足； 退温tk+1=update(tk)，并令k=k+1； Until算法终止准则满足； 输出算法搜索结果。 由算法5.1的描述可知，模拟退火算法的关键要素可以概括为“三函数两准则一初温”。 1. 三函数 1) 状态产生函数 sj=Genete(s) 原则： 设计状态产生函数(邻域函数)的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。 方法： 在当前状态下的邻域结构内以一定的概率方式(均匀分布、正态分布、指数分布等)产生。 2) 状态接受函数 min1,exp-C(sj)-C(s)/tk>=random［0,1］, s=sj 式中： C(sj)为当前解sj的目标函数值。 状态接受函数一般以概率的方式给出，不同的状态接受函数的差别主要是接受概率的形式不同。设计状态接受概率，应该遵循以下原则。 （1） 在固定温度下，接受使目标函数下降的候选解的概率大于使目标函数上升的候选解的概率； （2） 随温度的下降，接受目标函数上升的解的概率要逐渐减少； （3） 当温度趋于零时，只能接受目标函数下降的解。 方法： 状态接受函数的引入是模拟退火算法实现全局搜索的关键因素。一般而言，状态接受函数只要满足上述三个原则即可，其具体形式对算法影响不大，通常用min 1,exp-C(sj)-C(s)/tk作为模拟退火算法的状态接受函数。 3) 退温函数 tk+1=update(tk) 即温度的下降方式，用于在外循环中修改温度值。降温方式对算法性能影响很大。降温过快 可能丢失最优值点，降温过慢可能导致算法收敛速度极大降低。为保证全局收敛性，一般要求温度下降趋于0。 常用的退温函数如下。 （1） 比例退火方式： tk+1=α·tk，其中，0<α<1。α越接近1，温度下降越慢。α的大小可以不断变化。如果α大小不变，则比例退火方式的降温过程在高温区速度较快，低温区速度逐渐减慢。 （2） 衰减退火方式： tk+1=t0(K-k)/K。其中K为温度下降的总次数(预先设定的常数)。 2. 两准则 1) 内循环终止准则 内循环终止准则分为以下两种算法。 (1) 非时齐算法： 每个温度下只产生一个或少量候选解。 (2) 时齐算法： 常采用Metropolis抽样稳定准则，需要等温过程中晶体分子的状态转移达到稳定状态后再进行降温过程。 确定在等温状态下系统稳定有如下三种方法。 ① 检验目标函数的均值是否稳定(如均值变化小于某一个阈值)。 ② 连续若干步的目标值变化较小(如目标值变化小于某一个阈值)。 ③ 按一定步数抽样(抽样步数通常较多)。 2) 外循环终止准则 外循环终止，代表算法计算结束。常用的外循环终止准则如下。 （1） 设置终止温度的阈值(通常要求这个阈值应接近于0)。 （2） 设置外循环迭代次数(迭代达到一定步数，算法自动退出)。 （3） 算法搜索到的最优值连续若干步保持不变。 3. 初温 原则上通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的初温参数。实际应用中往往需要将初温设置得充分大，实验表明，初温越大，获得高质量解的概率越大，但也会花费较多的计算时间。常用的初温设置方法如下。 （1） 均匀抽样一组状态，以各状态目标值的方差为初温。 （2） 随机产生一组状态，确定两两状态间的最大目标差值，根据差值，利用一定的函数确定初温。 （3） 其他一些经验公式。 5.2.3模拟退火算法的应用 模拟退火算法的应用很广泛,可以有效求解NPHard问题。本节将介绍如何用模拟退火算法求解实际问题。 例5.4 如图5.5所示， 假设某小区内有30个安保巡逻打卡点，其在平面图上对应的坐标如下： 41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50 图5.5巡逻打卡问题 安保人员需要从第一个打卡点出发巡逻所有打卡点，最终返回第一个打卡点。如何设计保安的巡逻路线，使得巡逻路线总长度最小？ 该问题可以抽象为TSP，其已经被证明是一典型的NP难问题。目前尚未发现多项式时间求解方法。 尝试用模拟退火算法求解。 1. 问题编码 采用与例5.3相同的编码方式，即采用访问打卡点的序号进行问题编码。后续的各种处理都基于该问题编码方式进行。 2. 设计状态产生函数 状态产生函数基于邻域的概念进行设计，设计了三种邻域结构操作，以生成多样化的新状态。具体如下所示。 (1) 互换操作，即随机选定两个打卡点的序号，直接将其交换，如图5.6所示。 图5.6状态产生函数互换操作示意图 (2) 逆序操作，即随机选定连续若干打卡点，并将访问顺序逆转，如图5.7所示。 图5.7状态产生函数逆序操作示意图 (3) 插入操作，随机选择某个城市序号插入某随机位置，如图5.8所示。 图5.8状态产生函数插入操作示意图 3. 设置初始温度 随机地选择一些打卡点，并计算这些点之间的距离，然后用其中的最大值减去最小值，再除以经验值log0.9，作为初始温度。 4. 其他参数设定 截止温度tf=0.01； 退温函数采用比例退火方式，退温系数α=0.9； 内循环次数L=200×PointNum，其中PointNum为打卡点的数量。 采用上述设置后，使用模拟退火算法进行计算，运行结果如图5.9 所示。 图5.9模拟退火算法求解巡逻打卡路径问题的计算结果 5.2.4模拟退火算法的改进 模拟退火算法具有质量高、初值鲁棒性强、简单、通用、易实现等优点，其不足主要是 较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长，耗时较多。针对效率问题，常用的改进方法如下。 (1) 设计合适的状态产生函数。针对问题的特点，设计更加合理高效的状态产生函数，在更有可能包含最优解的区域产生解。 (2) 避免状态的迂回搜索。采用一定的记忆方式，使算法记住已经产生过的解，避免对局部空间反复搜索。 (3) 采用并行搜索结构。利用并行计算方式，将搜索空间划分为多个子空间，进行并行搜索，然后汇总处理各子空间的搜索结果。 (4) 避免陷入局部极小，改进对温度的控制方式。主要通过引入随机状态，使搜索具有跳出局部空间的能力。 (5) 选择合适的初始状态。比如可引入先验信息或其他约束条件，通过控制搜索的起始位置减少搜索空间。 (6) 设计合适的算法终止准则。除了以找到目标状态为终止条件外，也可合理设定内循环、外循环的次数，从而控制总的搜索计算量。 (7) 增加升温或重升温过程，避免陷入局部极小。从模拟退火算法的原理可知，升温能够使系统处于不稳定状态，从而有利于跳出局部极值。 (8) 结合其他智能优化算法或搜索机制的算法。比如将模拟退火算法的结果作为其他搜索算法的初始解。 (9) 上述各方法的综合。 5.3遗传算法 5.3.1遗传算法的原理 1. 遗传算法的产生及发展历程 在达尔文(Darwin)的进化论和孟德尔(Mendel)的遗传变异理论的基础上，产生了一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术，称为演化计算，遗传算法是其最初形成的一种具有普遍影响的模拟进化优化算法。 20世纪50年代，一些生物学家开始研究使用数字计算机模拟生物的自然遗传与自然进化过程。1963年，德国柏林技术大学的雷肯伯格(I.Rechenberg)和施韦费尔(H.P.Schwefel)，在做风洞实验时产生了进化策略的初步思想。 60年代，福格尔(L.J.Fogel)在设计有限态自动机时提出进化规划的思想。1966年 福格尔等出版了《基于模拟进化的人工智能》，系统阐述了进化规划的思想。60年代中期，美国密西根大学的霍兰德(J.H.Holland)教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术。1967年， 巴格利(J.D.Bagley)首次提出“遗传算法 ”一词。1975年，Holland出版了著名的《自然与人工系统中的适应》，标志遗传算法诞生。70年代初，Holland提出了“模式定理”，一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础。1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(International Society of Genetic Algorithms，ISGA)。至今，以遗传算法为代表的演化计算仍然是国际上的研究热点。 2. 遗传算法的思想来源 遗传算法思想源自生物进化理论和遗传学，在计算机处理中借鉴了以下基本知识。 (1) 达尔文自然选择学说。 ① 遗传： 子代和父代具有相同或相似的性状，保证物种的稳定性。 ② 变异： 子代与父代，子代不同个体之间总有差异，是生命多样性的根源。 ③ 自然选择： 自然界中，适应性强的变异个体被保留，适应性弱的变异个体被淘汰，表现出生存斗争和适者生存的现象，称为自然选择。注意，自然选择是长期的、缓慢的、连续的过程。 (2) 遗传学基本概念与术语。 染色体： 遗传物质的载体。 脱氧核糖核酸（DNA）： 大分子有机聚合物，双螺旋结构。 遗传因子： DNA或RNA长链结构中占有一定位置的基本遗传单位。 基因型： 遗传因子组合的模型。 表现型： 由染色体决定性状的外部表现。 图5.10表现型基因对大象外貌的影响 基因型和表现型的例子如图5.10 所示。假设大象的基因型表示为一串数字，白象的基因型为“1111111”，黑象的基因型为“1110111”。 因为其基因型不同，个体的表现型不同，表现出白象与黑象两种特性。 基因座： 遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因。 个体： 染色体带有特征的实体。 种群： 个体的集合，该集合内个体数量称为种群的大小。 进化： 生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化或演化。 适应度： 度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝。 选择： 决定以一定的概率从种群中选择若干个体的操作。 复制： 细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。 交叉： 在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”。 变异： 在细胞进行复制时可能以很小的概率产生某些复制差错，使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。 编码： 表现型到基因型的映射。 解码： 从基因型到表现型的映射。 1930—1947年，达尔文进化论与遗传学走向融合， 多布然斯基 （Th.Dobzhansky）于1937年发表的《遗传学与物种起源》成为融合进化论与遗传学的代表作。 生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是生物在进化过程中体现的一种智能，也是人工系统梦寐以求的功能。 我们 考虑这样一个场景。 一片山地包含若干山峰，一群兔子立志找到最高峰。它们采用的方法是，首先随机选择一个地点，然后兔子之间交配生下子代兔子，子代兔子的位置为其父代的两个个体的中间。接下来，兔子可随机往某个方向随机移动一段距离。我们规定，位置海拔更高的兔子对环境的适应能力更强，其有更多的觅食和繁殖机会，被天敌吃掉的概率也更低。于是兔子在繁衍若干代之后，大量的兔子会集中在海拔更高的位置，直到找到最高峰。遗传算法正是用计算机模拟这个过程找到问题优化解。 5.3.2遗传算法的实现 遗传算法是模拟自然界生物进化过程与机制的问题求解技术，基本遗传算法的流程（图5.11）如下： Step1： 选择合适的编码形式，对待考查的个体进行编码； Step2： 初始化种群，设置算法运行参数； Step3： 评估种群中个体的适应度； Step4： 以适应度为依据，从种群中选择两个个体作为待交叉的父代个体； Step5： 将两个父代个体的染色体进行交叉，产生两个子代个体； Step6： 对子代的染色体进行变异； Step7： 转Step4，直到子代种群产生； Step8： 如果满足算法结束条件，则算法退出，输出解； Step9： 转Step3。 图5.11基本遗传算法流程 按照图5.11 中基本遗传算法的流程，算法具有编码、选择、交叉、变异等关键操作。 1. 编码 由设计空间向编码空间的映射，对应表现型到基因型的映射。编码的选择是影响算法性能和效率的重要因素。 常用的一种编码方式是二进制编码，如数据对“(1,2)”的二进制编码可表示为“00010010”，其中编码的前半部分“0001”是十进制数字“1”的二进制编码， 后半部分“0010”是十进制数字“2”的二进制编码。与编码对应的是解码，即由编码空间向设计空间的映射，对应基因型到表现型的映射。其可看作编码操作的逆映射。 在遗传算法操作中，种群中个体都以编码方式存在，后续的遗传操作都作用在编码后的个体上。 1) 编码原则。 健壮的编码通常符合如下原则。 (1) 完备性： 问题空间的所有解都能表示为所设计的基因型。 (2) 健全性： 任何一个基因型都对应于一个可能解。 (3) 非冗余性： 问题空间和表达空间一一对应。 2) 多种编码方式。 编码的方式多种多样，但通常有如下编码方式。 （1） 二进制编码： 用一串“0”或“1”组成的二进制数进行编码，其编码、解码操作简单易行，交叉、变异等遗传操作便于实现。 因为其变异后可能导致表现型变化很大，不连续，所以可能会远离最优解，达不到稳定。二进制编码也容易出现海明悬崖问题。 （2） 浮点数编码： 又称为实数编码，其基于多个浮点数进行问题编码。 （3） 格雷码编码： 两个相邻的数用格雷码表示，其对应的码位只有一个不同,可以提高算法的局部搜索能力。这是格雷码相比二进制码而言所具备的优势。 （4） 符号编码： 染色体编码串中的基因值取自一个无数值含义而只有代码含义的符号集。这些符号可以是字符，也可以是数字。例如，对于旅行商问题，城市编号的排列可构成一个表示旅行路线的个体。 （5） 复数编码： 与实数编码相对，其用复数对个体进行编码。 2. 适应度函数 个体的适应度是个体在种群生存的优势程度度量，用于区分个体的“好与坏”，其具体数值使用适应度函数 进行量化计算，也称为评价函数。适应度函数的设计原则如下： (1) 单值,连续,非负,最大化； (2) 合理,一致性； (3) 计算量小； (4) 通用性强。 适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。适应度函数设计不当有可能出现欺骗问题。比如，在进化初期个别超常个体可能会控制选择过程，在进化末期个体适应度差异太小， 导致算法陷入局部极值。 一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的尺度变换 。常用的三种适应度函数的构造方式如下： 1) 直接转换法 目标函数为最大化问题： Fitf(x)=f(x)(54) 目标函数为最小化问题： Fitf(x)=-f(x)(55) 2) 截断式界限构造法 目标函数为最大化问题： Fitf(x)= f(x)-cmin,f(x)>cmin 0,其他(56) 式中： cmin为f(x)的最小估计值。 目标函数为最小化问题： Fitf(x)= cmax-f(x),f(x) Xmax=1.8506 f(Xmax)=3.8503 值得注意的是，使用遗传算法求解函数优化问题不需要函数可导，甚至不要求函数连续。这是基于求导的数学方法所不具备的优势。 2. 组合优化 在有限个可行解的集合中找出最优解的一类优化问题称为组合优化问题。实践证明，遗传算法对于组合优化中的NPHard问题非常有效，在01背包问题、旅行商问题、装箱问题及图形划分等问题上已经成功应用了遗传算法。典型的组合优化问题可分为无约束组合优化问题和带约束组合优化问题。下面将分别介绍使用遗传算法对其求解的方法。 1) 无约束组合优化问题求解 典型的无约束组合优化问题是旅行商问题，其只有最小化(或最大化)优化目标的要求，而对解本身没有约束。 本节使用遗传算法求解例5.4的30个巡逻点的巡逻打卡问题。前面已经分析，30个巡逻点的巡逻打卡问题是典型的旅行商问题。 Step1： 编码。直接采用解的表示形式，30位(30个打卡点)长，每位代表所经过的打卡点序号(无重复)。 Step2： 生成初始种群。 依然采用随机方式，生成整个种群。生成每个个体时，访问打卡点的顺序随机确定。 Step3： 设计适应度函数。 由于旅行商问题的优化目标是最小化路径距离，可以选择路径距离的倒数作为个体的适应度。 Step4： 设计选择算子。采用轮盘赌方法。 Step5： 交叉算子。交叉算子设计为随机有序交换，具体操作： 随机选取两个交叉点； 两个父个体交换中间部分； 替换交换后重复的打卡点序号。 Step6： 设计变异算子。随机选择同一个个体的两个点进行交换。 算法超参数设置： 种群规模100； 交叉概率0.8； 变异概率0.2； 终止代数2000。 采用上述设置后，使用遗传算法进行计算，运行结果如图5.22所示。 图5.22遗传算法求解巡逻打卡路径问题 这里通过遗传算法找到最优解为425.649，比例5.4中用模拟退火算法找到的最优解423.7406差一些。需要说明的是，智能优化算法不一定能找到最优解，其目标是寻找足够好的次优解或用户满意解，且两次运行同一遗传算法所得到的结果也不一定相同。 2) 带约束的组合优化问题求解 带约束的组合优化问题又称为约束最优化问题，其一般形式如下： minimize f(x) s.t.gi(x)≤0(i=1,2,…，p) hj(x)=0(i=1,2,…，q) (516) 式中： f(x)是优化目标，不等式gi(x)和等式hj(x)均为约束。 从式(516)可知，约束最优化问题不仅要求目标函数达到最小，而且解x需要满足不等式gi(x)和等式hj(x)的约束。 直接按无约束问题求解的方式来处理约束最优化问题是行不通的，主要有两个原因： 一是随机生成的初始种群中可能有大量不可行解； 二是交叉、变异等遗传算子作用于可行解后也可能产生不可行解。 使用遗传算法解决约束最优化问题的关键是对约束的有效处理，主要包括 以下两种方法。 (1) 罚函数法。 罚函数法的核心思想是将有约束问题转化为无约束问题。其构造惩罚项，并包含到适应度评价中，通常有 加法和乘法两种形式。 罚函数法的加法形式： fitness(x)=f(x)+rP(x), P(x)=0,x∈X P(x)>0,xX,r<0(517) 式中： x为遗传算法中个体； X为可行解域； fitness(x)为个体x的适应度评价函数； P(x)为罚函数； r为惩罚系数。 在式(517)中，rP(x)就是惩罚项。如果个体没有违反任何约束(x∈X)，则惩罚项为0； 否则， 惩罚项的存在会导致个体x的适应度降低。 罚函数法的乘法形式： fitness(x)=f(x)·P(x), P(x)=1,x∈X P(x)<1,xX(518) 式中： x为遗传算法中个体； X为可行解域； fitness(x)为个体x的适应度评价函数； P(x)为罚函数。当个体x违反约束 时，P(x)<1，也会导致个体x的适应度降低。 对简单约束问题采用定量惩罚，如只要违反约束， 就适应度降低相同的数量； 对复杂约束问题 可采用变量惩罚。变量惩罚的罚函数由 可变惩罚率和违反约束的惩罚量组成。 可变惩罚率是指个体违反约束程度不同或算法进化迭代次数的不同。调整罚函数的惩罚系数r有如下的处理方式。 ① 基于解违反约束程度： 随着违反约束程度变得严重而增加惩罚压力，称为静态惩罚。 ② 基于算法的进化迭代次数： 随着进化过程的进展而增加惩罚压力，称为动态惩罚。 违反约束的惩罚量是指在惩罚系数不变的情况下，合理设计罚函数P(x)，使个体违反约束的程度越大，则P(x)越大。 图5.23可行解域与不可行解域 示意图及最优解分布位置 问题的解空间可以 划分为可行解域和不可行解域，如图5.23 所示。 罚函数法的优势在于能够在可行解域和不可行解域 搜索最优解。 大量研究表明，最优解总是出现在可行解域与不可行解域的边界上。在遗传算法的进化过程中，一个不可行解( 图5.23 中A点)包含的染色体片段信息可能比可行解(图5.23 中B点)中的染色体片段信息更接近最优解。 注意，使用罚函数法需要谨慎地在过轻或过重惩罚之间找到平衡。惩罚力度过大可能造成搜索只停留在可行解域内，且容易早熟收敛； 惩罚力度过小可能造成种群中存在大量毫无意义的不可行解，搜索过程在无意义区域浪费大量时间，也难以找到最优解。 (2) 解修正法。 解修正方法的思想是将不可行解转化为可行解，需要按照相关领域知识设计解修正算法，并且解修正算法的效果和效率对问题求解效果影响较大。在约束修正算法设计合理、修正算法运行代价较小的情况下， 解修正方法相较于罚函数方法通常能取得更好的结果。 例如，使用遗传算法求解例5.1中的01背包问题。采用罚函数法，可设计个体的适应度函数等于装入物品价值减去超重部分物品价值乘以惩罚系数； 采用解修正法，可按照性价比(或重量、价值、随机等)原则去除超重的背包内物品，直至背包不再超重。 5.3.4遗传算法的改进 遗传算法的改进方法一直是研究的热点，目前已有大量成果。这里介绍 精英解保持、自适应遗传算法和基于小生境技术的遗传算法三种常用的改进方法。 1. 精英解保持 遗传算法中的基因并不一定真实地反映待求解问题的本质，因此各个基因之间未必就相互独立。如果只是简单地进行杂交，很可能破坏了较好的基因片段，这样就没有达到通过进化过程累积优良基因的目的。精英保留策略可以避免 杂交操作破坏最优个体。此外，轮盘赌等选择算子也可能以较小概率丢失种群中最优解。为了防止当前群体的最优个体在下一代发生丢失，导致遗传算法不能收敛到全局最优解，De Jong 提出了“精英选择”策略，也称为“精英保留” 策略。该策略的思想是把群体在进化过程中迄今出现的最好个体(称为精英个体Elitist)不进行配对交叉而直接复制到下一代中。 精英个体是种群进化到当前为止遗传算法搜索到的适应度最高的个体，它具有最好的基因结构和优良特性。采用精英保留的优点是 遗传算法在进化过程中出现的最优个体不会被选择、交叉和变异操作丢失和破坏。精英保留策略对改进标准遗传算法的全局收敛能力产生了重大作用，学者们已经从理论上证明了具有精英保留的标准遗传算法依概率1收敛到全局最优解。 2. 自适应遗传算法 交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键，直接关系到算法的收敛性。Pc越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏； Pc过小，搜索过程缓慢，以至停滞不前。Pm过大，变成纯粹的随机搜索； Pm过小，不易产生新个体结构。 显然，当种群中各个体适应度趋于一致或趋于局部最优时，应使Pc和Pm增加； 而当种群中个体适应度比较分散时，应使Pc和Pm减少。同时，适应度较高的个体，应设定较低的Pc和Pm； 适应度较低的个体，应设定较高的Pc和Pm。 因此，可以按照一定的规则在遗传算法运行过程中动态地调整Pc和Pm，使得算法具有自适应能力。 3. 基于小生境技术的遗传算法 小生境(niche)是生物学中的概念，表示特定环境中的一种组织功能； 在自然界中，往往特征、性状相似的物种相聚在一起，并在同类中繁衍后代。在标准遗传算法中，容易“近亲繁殖”，即两个有类似基因的个体交叉产生的子代个体与双亲极为接近，破坏了种群中的潜在多样性。于是，学者提出了小生境遗传算法(Niche Generic Algorithm，NGA)，将种群中个体划分为若干类，这些类内个体的基因相似度相对较高，类间个体的基因相似度相对较低。选择操作时，从每类选出优秀个体进行交叉、变异操作，或组成新的种群。 基于小生境技术的遗传算法能够保持解的多样性，提高全局搜索能力，比较适合复杂多峰函数的优化。 5.4其他典型智能优化算法简介 除了前面介绍的模拟退火算法和遗传算法之外，还有很多其他的智能优化算法。在自然界中各种生物群体显现出来的智能近几十年来得到了广泛关注，学者通过对简单生物体的群体行为进行模拟 提出了群智能算法。其中，模拟蚁群觅食过程的蚁群优化算法 (Ant Colony Optimization，ACO)和模拟鸟群运动方式的粒子群算法(Particle Swarm Optimization，PSO)是两种主要的群智能算法，本节将分别进行介绍。 5.4.1蚁群优化算法 蚁群优化算法是一种源于大自然生物世界的新的仿生进化算法，是由意大利学者多里戈(M.Dorigo)和马聂佐(V.Maniezzo)等于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法。蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短路径，并且能随环境的变化，适应性地搜索新的路径，产生新的选择。目前，蚁群优化算法已被广泛应用于求解优化问题。 1. 算法原理 蚁群优化算法又称为人工蚁群优化算法，是模拟真实蚂蚁群行为而设计的求解优化问题的一种仿生算法。 通过对蚁群觅食行为的观察发现了如下现象。 （1） 蚁群觅食是群体行为，单只蚂蚁的觅食路径(从巢穴到达食物源的路径)并不一定是最优的，但通过群体协作总可找到最优路径。 （2） 蚁群觅食开始选择路径是随机的，但随着蚂蚁搬运食物来回于巢穴与食物源之间，路径的选择会越来越趋于有组织，当然也有少数蚂蚁有随机行走的现象。 进一步研究发现，蚂蚁会在其经过的路径上释放 “信息素”，蚁群内的蚂蚁对“信息素”具有感知能力，它们会倾向于沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源。 受到真实蚁群觅食的启发，学者们设想了人工蚁群系统。人工蚁群系统具有如下特点。 (1) 每一只人工蚂蚁(简称蚂蚁)在行动路径上均释放信息素。 (2) 当“蚂蚁”碰到还没走过的路口，就随机挑选一条路走。“信息素”随时间挥发， 对于某一条路径而言，“信息素”浓度与路径长度成反比。 (3) 其他觅食的蚂蚁根据不同路径上的“信息素”的浓度来选择路径，浓度越大，越有可能沿着其方向行进。 (4) 当更多的蚂蚁选择某条路径时，这条路径因为聚集了越来越多的“信息素”而变得更有吸引力，进而吸引更多的蚂蚁走这条路。 (5) 这种作用形成一种正反馈机制，使最优觅食路径被越来越多的蚂蚁选择，最优路径上的“信息素”浓度越来越大。 (6) 最终蚁群找到最优寻食路径。 在蚁群觅食过程中有以下两个重要的机制相互作用推进了这种最优行为。 （1） 蚂蚁在行进路径上不断累积信息素，使得不同路径变得不一样。 （2） 路径上信息素的不断累积改变了蚂蚁选择路径的概率。 从而形成一种蚂蚁行为不断改变所选路径，路径不断对蚂蚁行为产生影响的双向作用，直到绝大多数蚂蚁选择了最优路径。 2. 算法描述 这里以例5.2中的旅行商问题为例介绍基本蚁群优化算法及其流程。基本蚁群优化算法可以表述如下： 在算法的初始时刻，将m只蚂蚁随机地放到n座城市，同时为每只蚂蚁保存一个禁忌表tabuk(k=1,2,…,m)，用来记录蚂蚁k已经走过的城市。初始化禁忌表tabuk时，将其第一个元素设置为蚂蚁k当前所在的城市。设τij(t)表示在t时刻，城市i到城市j的 “信息素”浓度。初始化τij(t)=c(c是较小的常数)，表示刚开始时，各路径上的信息素量相等，且接近于0。 算法运行过程中，每只蚂蚁根据路上残留的“信息素”量和启发式信息(两城市间的距离)独立地选择下一座城市，在时刻 t，蚂蚁 k 从城市 i 转移到城市 j 的概率可表示为 p(k)ij(t)= ［τij(t)］α·［ηij］β ∑s∈Jk(i) ［τis(t)］α· ［ηis］β,j∈Jk(i) 0,其他(519) 式中： Jk(i)={1,2,…,n}-tabuk,表示蚂蚁k下一步允许选择的城市集合。禁忌表 tabuk记录了蚂蚁k已经走过的城市。当所有n座城市都加入 禁忌表tabuk中时，蚂蚁k便完成了一次周游，此时蚂蚁k所走过的路径便是TSP的一个可行解。式(519)中的ηij是一个启发式因子，表示蚂蚁从城市i转移到城市j的期望程度。在蚁群优化算法中，ηij通常取城市i与城市j之间距离的倒数。α、β分别表示信息素和期望启发式因子的相对重要程度。当所有蚂蚁完成一次周游后，各路径上的信息素根据 下式更新： τij(t+1)=(1-ρ)·τij(t)+Δτij(520) 式中： ρ为路径上“信息素”的蒸发系数(0<ρ<1)， 则1-ρ为“信息素”的持久性系数； Δτij为本次选代中边i→j上信息素的增量，即 Δτij=∑mk=1Δτ(k)ij(521) 式中： Δτ(k)ij为第k只蚂蚁在本次选代中留在边(i,j)上的 “信息素”量，如果蚂蚁k没有经过边(i,j)，则Δτ(k)ij的值为零。Δτ(k)ij可表示为 Δτ(k)ij= QLk,蚂蚁k在本次周游中经过边(i,j) 0,其他(522) 式中： Q为正常数； Lk为第 k 只蚂蚁在本次周游中所走过路径的长度。 实际上，M.Dorigo一共提出了三种群算法的模型，式(522)称为 antcycle 模型，另外两个模型分别称为 antquantity 模型和 antdensity 模型，其差别主要在 于Δτij的表达方式。 在antquantity模型中，Δτij表示为 Δτ(k)ij= Qdij,蚂蚁k在本次周游中经过边(i,j) 0,其他(523) 式中： Q为正常数； dij为城市i到城市j的距离。 在antdensity模型中，Δτij表示为 Δτ(k)ij= Q,蚂蚁k在本次周游中经过边(i,j) 0,其他(524) 式中： Q为正常数。 实际上， 蚁群优化算法是正反馈原理和启发式算法相结合的一种算法。在选择路径时，蚂蚁不仅利用了路径上的 “信息素”，而且用到了城市间距离的倒数作为启发式信息。实验结果表明，通常情况下，antcycle模型比antquantity和antdensity模型有更好的性能。这是因为antcycle模型利用全局信息更新路径上的信息素量，而antquantity和antdensity模型使用的是局部信息。 求解TSP的基本蚁群优化算法的步骤如下。 Step1： 参数初始化。令时间t=0和循环次数Nc=0，设置最大循环次数 G，将m个蚂蚁随机置于 n 个元素(城市) 上，令有向图上每条边(i,j)的初始化“信息素”量τij(t)=c，其中c为常数，且初始时刻Δτij=0； Step2： 设置蚂蚁的索引号k=1； Step3： 设置当前蚂蚁k已访问的城市数量numcity=1； Step4： 蚂蚁个体k根据式(519)计算的概率选择城市j并前进，j∈Jk(i)； Step5： 将城市j加入禁忌表tabuk中，numcity=numcity+1； Step6： 如果numcity