2.1　学习型智能优化相关理论

在本节中，首先对相关概念进行了简单界定，然后提出了学习型智能优化方法的基本框架，最后给出了学习型智能优化方法的运行机制。

2.1.1　知识

知识是对某个主题确信的认识。认知事物的能力是哲学中充满争议的中心议题之一，并且拥有它自己的分支——知识论。从更加实用的层次来看，知识通常被某些群体所共享，知识可通过不同方式来操作和管理。尽管知识是日常生活的中心组成部分，但它的确切定义仍是哲学家、社会科学家和历史学家饶有兴趣的话题。根据许多思想家的论述，知识必须具备三个特征：被证实的（justified）、真的（true）和被相信的（believed）⁽¹⁾。根据维基百科、互动百科⁽²⁾和百度百科⁽³⁾中的描述，常见的知识定义方式有以下几种。

• 知识是一种被确认的信念，通过知识持有者和接收者的信念模式和约束来创造、组织和传递。知识是从信息中变化、重构、创造而得到的，其内涵比数据、信息要更广、更深、更丰富。知识可分为显性知识（explicit knowledge）和隐性知识（tacit knowledge）。显性知识可用正规化的、系统化的语言来传输；隐性知识拥有个性化特征，很难被正规化和传播。
• 知识是存在于专业人员身上的技能财产，可分为实证知识、高级技能、系统认知和自我激励创造力等。
• 知识是资讯、文化脉络及经验的组合。
• 知识是企业的无形资产。
• 知识是用以辅助决策的事实、模式、概念、意见及直觉的集合体。
• 知识是从人类活动中所获取的真理、原则、思想及资讯。
• 知识是经验累积的记录，事实组织的系统化，对事实的理解，一种理解的行为或状态，人的已知和未知。
• 知识是与经验、上下文（context）、解释和思考（reflection）结合在一起的信息。知识是一种流动性质的综合体，包括结构化的经验和价值，经过文字化的资讯，专家独特的见解。知识是一种可随时帮助人们决策与行动的高价值信息。
• 《博弈圣经》中将知识定义为识别万物实体与性质的是与不是。
• 《中国大百科全书·教育》中将知识表述为：就内容而言，是客观事物属性与联系的反映，是客观世界在人脑中的主观映象。就反映活动形式而言，有时表现为主体对事物的感性知觉或表象（感性知识）；有时表现为关于事物的概念或规律（理性知识）。

由上述定义可知，知识是抽象的，是借由某种形式而呈现出来的、可互相传达的概念。本书更多地关注一些显性知识，即能明确表达的知识。显性知识可通过口头传授、教科书、参考资料、报纸杂志、专利文献、视听媒体、软件和数据库等方式获取，也可通过语言、书籍、文字、数据库等编码方式传播。本书中用到的显性知识，都可采用计算机语言来表示和存储；同时，其他模型可通过给定方式对这些知识进行更新和应用。

2.1.2　知识模型

知识模型是指描述某一领域产品相关专家知识的信息模型。知识模型将专家知识、产品设计过程知识和环境知识等明确地表示于产品信息模型中，支持系统中智能模块的信息表达和传递。知识模型通常基于系统功能和结构知识构建，通过符号或流程图来描述。知识模型主要研究形式化和结构化的知识。

为了更加有效地利用知识，必须采用合适的技术来完成对相关知识的表达、获取、存储和应用。在本书中，知识模型主要完成以下功能：知识表达、知识获取、知识存储和知识应用。鉴于此，本书将知识模型定义为：为完成知识表达、知识获取、知识存储和知识应用而使用的技术、方法和手段的集合体。

知识表达就是如何采用计算机语言将用于解决问题的结构化信息表示出来。本书采用一维或多维数组来表示知识。用于表示知识的数组一般都具有特定含义，即数组中的每个元素都是可解释的（具有明确含义）。

知识获取就是采用特定方法来获得一些感兴趣的知识。在学习型智能优化方法中，知识获取主要是指从智能优化方法的演化过程中挖掘（学习）有用知识。一般用到的知识获取手段包括统计方法、机器学习和数据挖掘等。本书仅采用统计方式来完成对不同类型知识的挖掘。

知识存储就是采用特定方式将一些感兴趣的知识存储起来。本书采用一维或多维数组来表示感兴趣的知识，知识存储就相对简单。只要在相关程序中将表示知识的数组以全局变量形式定义出来，任何模型在任何时段都可访问或更新这些数组。

知识应用就是采用特定方法将知识应用到优化问题的求解中。在学习型智能优化方法中，知识应用就是如何采用知识来指导后续演化（优化）过程。在2.2节中将介绍学习型智能优化方法中用到的几类知识及其应用方式。

2.1.3　遗传算法

遗传算法和蚁群算法是两种比较典型的智能优化方法，本书基于遗传算法和蚁群算法构建了多种不同的学习型智能优化方法，因此分别对遗传算法和蚁群算法的研究现状进行了综述。遗传算法（genetic algorithm，GA）是借鉴生物界进化规律（适者生存和优胜劣汰遗传机制）而演化出来的一类随机搜索算法^[60-62]。遗传算法由美国Michigan大学的Holland教授于20世纪70年代首次提出^[63]，非常适合于处理传统优化方法难以解决的复杂的和非线性的优化问题^[64-67]。遗传算法是一类具有鲁棒性的搜索算法，主要有以下特点：以决策变量的编码作为运算对象，直接以适应度作为搜索信息，使用概率搜索技术，使用多个点的搜索信息，具有隐含并行性。遗传算法的基本运算流程如图2.1所示。

2.1.3.1　遗传算法的基本理论

遗传算法的基本理论主要以收敛性分析（群体收敛到全局最优解的概率）为主，可分为基于随机过程的收敛性研究和基于模式理论的收敛性分析^[68]。

（1）基于随机过程的收敛性研究。对于有限编码空间和有限群体，遗传算法的搜索过程可表示为离散时间的马尔可夫链模型，从而可采用随机过程理论进行严密分析。Rudolph用齐次有限马尔可夫链证明标准遗传算法收敛不到全局最优解^[69]，若采用保留最优个体的选择机制，则改进遗传算法全局收敛。Eiben等用马尔可夫链证明保留最优个体遗传算法的依概率全局收敛^[70]。Qi等用马尔可夫链证明浮点编码遗传算法是收敛的^{[68]，[71]，[72]}，但此结果是基于种群规模无穷大的假设。Fogel分析了没有变异算子的遗传算法的渐近收敛性^[73]。Suzuki用马尔可夫链状态转移矩阵的特征根分析了遗传算法的收敛行为^[74]。田军用马尔可夫链和随机摄动理论证明了遗传算法进入最小能量集的条件^[75]。张讲社等用马尔可夫链研究了基于扩展串的等价遗传算法的收敛性^[76]。

（2）基于模式理论的收敛性分析。由Holland提出的模式定理^[77]可称为遗传算法进化动力学的基本定理，积木块假设^[77]描述了遗传算法的重组功能，模式定理和积木块假设构成了遗传算法具备发现全局最优解的充分条件，也是分析遗传算法进化行为的基本理论，统称为模式理论。孙艳丰对模式定理进行了分析：模式定理揭示经过选择、交叉和变异后，模式H第k+1代的数目与第k代的数目的关系，并讨论了无交叉时的模式定理^[78]。Srinivas讨论了自适应交叉和变异概率下模式定理的表示方法^[79]。Bertoni等扩展了模式理论的研究成果^[80]。

最近，一些学者对模式定理的正确性提出了质疑。马丰宁通过测试黎曼函数和相应的理论分析，指出模式定理推导中的错误，并提出了新模式定理^[81]。张铃等也得出类似结论，并对模式定理进行了修正^[82]。Grefenstette指出模式定理不能保证适应度变换的唯一性^[83]。Muhlenbein指出了模式定理中计算模式适应度时存在的问题^[84]。Radcliffe通过对模式定理的分析，指出遗传算法并不总比随机搜索算法好^[85]。Vose也论述了模式定理中存在的一些问题^[86]。

遗传算法收敛性的研究成果，要么基于群体无穷大的假设，要么基于分析简单的或特殊的遗传算法，在实际应用中的可操作性较差。一般遗传算法的收敛性分析及如何构造一个收敛的遗传算法，仍是该领域亟待解决的重要理论问题。遗传算法的其他理论问题还包括^[87]：欺骗问题、维数分析、BGA（breeder genetic algorithm）理论、可分离函数、Walsh函数分析、傅里叶分析和二次动力系统等。

2.1.3.2　遗传算法的改进

为了维持群体的可进化性并最终搜索到全局最优解，遗传算法必须采用合适的运算形式（编码、计算流程、种群规模、种群初始化策略、GA算子和终止条件等），这就是遗传策略研究与设计的主要内容。

（1）参数设置的改进。参数确定包括静态方法和动态方法，静态方法指参数事先就确定好，算法执行过程中不变；动态方法指参数在算法执行过程中根据情况进行动态调整，以适应环境变化。由于参数设置关系到遗传算法的精度、可靠性和计算时间等诸多因素，因此许多学者通过研究参数设置来提高求解质量和系统性能。孙艳丰证明，当采用自然数编码时，从理论上可以证明遗传算法最优群体规模的存在性，并给出相应的计算方法^[88]。Srinivas等提出采用自适应交叉和变异概率来维持群体多样性，并保证遗传算法的收敛性^[79]。Fogarty研究了变异概率对整数编码的影响^[89]。Whitley采用父代个体之间的Hamming距离来设置变异概率^[90]。

（2）编码方式的改进。目前主要的编码技术有：一维染色体编码（包括二进制编码、实数编码和格雷编码等）、多参数映射编码、可变染色体长度编码、二倍体（多倍体）编码和树形编码等。Janikow等给出二进制编码和实数编码的实验比较^[71]。孟庆寿提出对称编码^[91]，并通过优良型保护、希望型成员移民和部分基因保留等措施，来加快算法的收敛速度。Fogel提出了动态变量编码，通过对DeJong的5个函数进行测试，发现动态变量编码比普通二进制编码的优化效果好很多^[92]。Goldberg等用动态背包问题进行比较研究，实验表明双倍体编码比单倍体编码的跟踪能力强^[93]。张晓缋等研究了二进制和十进制编码在搜索能力和保持群体稳定性上的差异，结果表明二进制编码比十进制编码的搜索能力强，但前者不能保持群体稳定性^[94]。Antonisse从理论上证明了Holland在推导最小字符集编码规则时存在的错误，指出大符号集编码设计可提供更多模式^[95]。

（3）选择算子的改进。常用的选择方法有：精华选择、重组选择、均分选择、适应性调整、线性排序、比例选择和自适应选择等。Potts等概括了大约20多种选择方法^[96]。为了防止算法过早收敛，Potts提出微进化结构和人工选择等来改进遗传算法。Kuo等采用分裂选择方法^[97]使新遗传算法比传统遗传算法在优化欺骗函数上具有更好的特性。Bäck在研究各种选择机制的基础上提出了扩展选择和偏置选择^[98]。

（4）交叉算子的改进。常用的交叉技术有：单点交叉、两点交叉、均匀交叉、多点交叉、启发式交叉、顺序交叉和混合交叉等。Potts概括大约20多种已有交叉技术^[96]。Qi等对遗传算法的交叉多样性进行了分析^[71]，[72]，通过建立相应的数学模型解释了在多维连续空间和大规模群体中使用均匀交叉算子是如何探索新的解空间的。

（5）变异算子的改进。常用的变异方式有：基本变异算子、逆转算子和自适应变异算子等。Potts总结了三种新的变异技术：管理变异、变化变异概率和单值运算^[96]。张良杰等人通过引入i位改进子空间的概念，采用模糊推理技术来确定选取变异概率的一般性原则^[99]。Qi等通过连续遗传算法的理论分析，提出随时间变化的变异技术^[71]，[72]，即根据群体平均适应性值来确定变异变化率。

（6）遗传算法的局部改进。由于遗传算法涉及精度、可靠性、计算时间、探索与开发等诸多问题，通过改进遗传算法本身在某种程度上可以提高遗传算法的性能。遗传算法的局部改进包括^[100]：分层遗传算法、变区域多层遗传算法、正交多目标最优化遗传算法、具有空间平滑技术的遗传算法、基于灾变的多群体遗传算法、基于共生策略的多模式进化算法和具有年龄结构的遗传算法等。

（7）混合遗传算法。混合遗传算法将遗传算法与基于领域知识的启发式搜索技术相结合来求解优化问题^[101-106]。将全局搜索能力强的遗传算法和局部搜索能力强的启发式搜索方法相结合的混合遗传算法能够产生很好的优化效果^[107-112]。设计混合遗传算法有三条指导性原则：采用原有算法中的编码技术、吸收原有算法的优点和改造遗传算子。混合遗传算法的框架如图2.2所示。常见的混合遗传算法包括^{[113]，[100]}：将模拟退火算法与遗传算法相结合；在简单遗传算法中加入局部搜索机制；用来解决模糊寻优问题的模糊遗传算法；结合可变多面体法和正交遗传算法的混合算法；将最速下降法和遗传算法相结合的混合方法等。

2.1.3.3　遗传算法的应用

遗传算法提供了一种求解复杂优化问题的通用框架，它不依赖于问题的具体领域，从而广泛地应用于多种学科领域^[114-119]。

（1）函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，遗传算法可以方便地得到较好结果。

（2）组合优化。对于组合优化问题，应把主要精力放在寻求满意解上，遗传算法是寻求满意解的最佳工具之一。遗传算法已在求解旅行商问题、背包问题、装箱问题、布局优化问题、图形划分问题等各种NP-难问题上得到了成功应用^[120-124]。

（3）生产调度。遗传算法已成为解决复杂调度问题的有效工具，在单件（流水线）生产车间调度、生产规划和任务分配等方面^[125-130]，遗传算法都得到了有效的应用。

（4）自动控制。遗传算法在自动控制领域已得到初步应用。如采用遗传算法进行航空控制系统的优化、基于遗传算法的模糊控制器设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构设计和权值学习等。

（5）机器人学。遗传算法已被成功地用于移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面。

（6）图像处理。遗传算法可用于图像处理中的优化计算，目前已在模式识别（包括汉字识别）、图像恢复、图像边缘特征提取等方面得到了广泛应用。

（7）人工生命。遗传算法已在人工生命的进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力。

（8）遗传编程。遗传编程（genetic programming）采用树型结构来表示计算机程序，运用遗传算法的思想，通过自动生成计算机程序来解决问题。

（9）机器学习。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。如采用遗传算法学习模糊控制规则，可更好地改进模糊系统的性能。

（10）数据挖掘。现有研究表明，遗传算法是一种非常有效的数据挖掘方法。

2.1.3.4　遗传算法的发展趋势

遗传算法是多学科结合与渗透的产物，已经发展成一种自组织、自适应的综合技术，广泛应用在计算机科学、工程技术和社会科学等领域。遗传算法的发展趋势可总结为以下几个方面^[131-133]。

（1）分布并行遗传算法。对分布并行遗传算法的研究表明，只要通过保持多个群体和恰当控制群体间的相互作用来模拟并行执行过程，即使不使用并行计算机，也能提高算法的执行效率。

（2）遗传神经网络。遗传算法与神经网络相结合，已被成功地应用于多个实际的工程领域。在很多现实系统中，信号是模糊的，数据是有噪声的，一般很难正确给出每个执行的定量评价。采用遗传算法就能克服这些困难，显著提高系统性能。

（3）借鉴自然现象提出新的算法模型。从生物进化或自然界的各种现象中获得新启发，提出新方法或对现有算法进行改进，如二倍体显性技术、小生境技术等。

（4）其他发展趋势^[133]。发展一些启发式策略对遗传算法的搜索过程给予指导；补充和扩展遗传算法与其他算法的混合方法，扩展遗传算法的功能和应用；加强遗传算法的应用研究，针对具体问题深入研究遗传算法都是特别值得提倡的工作。

2.1.4　蚁群算法

蚁群算法是模拟现实世界蚁群觅食行为的一种新型仿生算法，具有本质并行性、协同工作机制、鲁棒性和易于与其他启发式算法相结合等特点。蚁群算法不需要提供任何关于环境的先验信息，通过蚁群的群体学习能力及正反馈效应来达到全局寻优目的。蚁群算法特别适合于在离散优化问题的方案空间上进行多点非确定性搜索，已成功应用于旅行商问题、二次分配问题等多个离散组合优化问题^[134-138]。蚁群算法的基本运算流程如图2.3所示。

蚁群算法是基于真实蚂蚁的群体合作行为提出的，大部分蚁群算法都包括^[139]：群体中所有个体相互交流的通信机制（信息量迹，pheromone trials）；每个个体所记录的当前遍历序列；利用当前信息进行路径选择的随机选择策略。蚁群算法中的人工蚂蚁^[140]与现实世界中的真实蚂蚁有以下不同：人工蚂蚁生活在离散空间环境下；人工蚂蚁具有记忆能力；人工蚂蚁具有视觉能力；人工蚂蚁更新信息素时不反映真实蚁群的行为；人工蚂蚁具有智能性（预测未来和局部优化等）^[141]。

2.1.4.1　蚂蚁系统

1991年，Dorigo博士等首次提出蚂蚁系统（ant system）^[142]。蚂蚁系统有三种基本模型：蚁周模型（ant-cycle system）、蚁密模型（ant-density system）、蚁量模型（ant-quantity system）。在求解旅行商问题（traveling salesman problem，TSP）时，蚁周模型是三种模型中性能最好的，因此主要从蚁周模型的角度来讨论蚂蚁系统。

蚂蚁系统的基本步骤是：

（1）初始化各条边上的信息素强度及各个蚂蚁的禁忌表；

（2）每只蚂蚁按照概率规则，在禁忌表的制约下选择下一个要到达的结点，直到最终形成一条可行路径；

（3）更新各条边上的信息素，先进行信息素挥发操作，再根据各蚂蚁产生的路径长度获取蚂蚁所释放的信息素；

（4）所有蚂蚁都完成信息素更新操作后，记录当前最短路径，对禁忌表及信息素增加值进行重新计算，并转到第（2）步。

依次循环下去，直到满足算法的终止准则为止。

在初始化阶段，每条边上的信息素被初始化为一个较小数值τ₀；每只蚂蚁的禁忌表被初始化为该蚂蚁所在的结点（禁忌表长度为1）；每只蚂蚁在各条边上释放信息素的量被初始化为0。在蚂蚁系统中，每只蚂蚁均按照以下概率

来确定下一步要到达的城市。其中，p_ij（t）表示蚂蚁在t时刻由城市i选择城市j的概率，τ_ij（t）表示在t时刻边（i，j）上的信息素，α是信息素的权重，η_ij表示边（i，j）的启发因子（在TSP问题中常被设置为边（i，j）距离的倒数），β是启发因子的权重，A是不在蚂蚁禁忌表中的城市集合。当所有蚂蚁都找到一条可行路径后，蚂蚁系统就按照以下方式

开始执行信息素的更新。其中，ρ表示信息素的挥发因子，Δτ_ij（t，t+1）表示所有蚂蚁在边（i，j）上所释放的信息素总和。蚂蚁k在t到t+1时间内在边（i，j）上所释放的信息素为

这里，Q表示一个常量，L_k表示蚂蚁k构建的可行路径Tour_k的长度，（i，j）∈Tour_k表示蚂蚁k构建的可行路径Tour_k中包含边（i，j）。

2.1.4.2　蚁群系统

1996年，Dorigo博士在蚂蚁系统的基础上提出了蚁群系统（ant colony system，ACS）^[140]。蚁群系统的基本思想是：将m只蚂蚁按规则放置于n个节点，每只蚂蚁通过状态转移规则创建一条可行路径；每只蚂蚁通过局部更新规则对自己所建路径上的边进行信息素局部更新；当所有蚂蚁都完成路径构造之后，再对最佳路径上的边进行信息素全局更新。蚁群系统较蚂蚁系统的改进之处主要体现在以下三个方面。

（1）蚁群系统全局更新仅针对当前最好路径上的边

其中，Δτ_G为当前最好路径Tour_B长度的倒数，（i，j）∈Tour_B表示边（i，j）包含于当前最好路径Tour_B中。

（2）蚁群系统在蚂蚁创建路径时所使用的状态转移规则不同于蚂蚁系统

S表示按照公式（2.1）从集合A中随机选取下一步要到达的城市，q∈（0，1）是随机数，q₀∈（0，1）是常量，它在算法的求解效率与运行效率之间起着平衡作用。

（3）蚁群系统在对信息素进行更新时，除了进行全局更新外，还要进行信息素的局部更新。信息素局部更新规则如下：

这里，Δτ_L通常被设置为τ₀。

2.1.4.3　最大-最小蚂蚁系统

1997年，Stutzle等人提出了最大-最小蚂蚁系统（max-min ant system，MMAS）^[143]。MMAS的基本思路：将各边上信息素的浓度控制在[τ_min，τ_max]范围之内，这里τ_min和τ_max是算法中信息素所能取到的下限和上限。在初始化时，将各边信息素的数值初始化为τ_max；最大-最小蚂蚁系统会增强当前循环中最优路径上的信息素强度，其他边上的信息素由于挥发作用而进一步减少；这样就加剧了各边信息素的差异，提高了算法的运行效率。与蚂蚁系统相比，MMAS的改进之处主要体现在以下方面：

（1）MMAS只对当前循环中所产生的最短路径进行信息素的更新操作，这样做使得算法在最短路径附近搜索，从而逐步找出全局最优解。

（2）为了避免算法过快地收敛于局部最优解，MMAS将各边上的信息素浓度控制在比较固定的范围之内，这是该算法的主要特点。

（3）MMAS将各边上的信息素初始化为上限τ_max。根据实验结果^[143]，将各边上的信息素浓度初始化为τ_max可以提高算法的效率。

（4）为了扩展蚁群的搜索空间，MMAS还引入了平滑机制（smoothing）。平滑机制就是尽可能缩小各边上的信息素差异。平滑机制可表述为

这里，δ∈[0，1]表示平滑强度，和τ_ij（t）分别表示平滑之后与平滑之前边（i，j）上的信息素数值。

2.1.4.4　蚁群优化算法

1999年，Dorigo博士等提出了蚁群优化算法（ant colony optimization，ACO）^[144]，该算法给出了蚁群算法的一个标准框架。ACO对蚁群算法的实现进行了高度概括，将蚁群算法概括为蚂蚁行为、信息素挥发和守护操作（daemon actions）。

蚂蚁行为可描述为一群蚂蚁同时异步地在问题空间上移动。移动依赖于启发信息和信息素所决定的选择策略及问题本身的限制条件。蚂蚁在构造解的过程中或完成解的构造后，会对当前构造的解进行评估，然后依据解的好坏来释放一定数量的信息素到当前构造的路径上。这些信息素将进一步指导后续蚂蚁的路径构造。

信息素挥发可描述为图中各边上的信息素随着时间而逐渐消失。信息素挥发可避免算法过快地收敛于局部最优解，同时也有利于蚂蚁对新空间进行搜索，进而找出更好的解。

守护操作可描述为实现蚂蚁不能完成的集中控制任务。如局部搜索策略、仅对最短路径再次进行信息素的全局更新等。

2.1.4.5　蚁群算法的改进

蚁群算法的改进可概括为4个方面^[145]：信息素更新方式的改进、路径选择策略的改进、与其他算法的结合和多重蚁群算法。

（1）信息素更新方式的改进。采用锦标赛竞争策略更新信息素可取得很好效果^[146]；通过精英策略来改进信息素更新方式，能极大地提高算法性能^[147]；基于排序思想按比例在经过的路径上释放信息素，能显著地提高解的精度^[148]。一些学者对蚁群算法的信息素更新方式进行了大幅修改，取得了非常满意的结果^{[140]，[143]}。

（2）路径选择策略的改进。主要体现在：通过减小算法陷入局部最优解的概率来提高算法的优化性能，如采用伪随机比例规则（pseudo-random proportional rule）来构建路径^{[140]，[149]}。在伪随机比例规则的作用下，使用状态转移规则来指导蚂蚁的寻优过程，可较快地找到可接受的解；以一定概率接受当前系统的累积状态（选择当前转移概率最大的城市），可有效地提高算法的收敛速度。

（3）与其他算法的结合。利用蚁群算法良好的耦合能力，将蚁群算法和遗传算法结合起来，采用遗传算法生成信息素初始分布，利用蚁群算法来获得精确解，能够实现两种算法的优势互补^[150-153]。吴庆洪等提出了具有变异特征的蚁群算法^[154]，采用逆转变异方式，随机进行变异，增大进化时所需的信息素，克服了蚁群算法收敛较慢的问题。陈烨基于交叉算子提出了改进算法^[155]，进一步提高了算法性能。Dorigo等通过研究多个蚂蚁的协同效应，提出了蚁群算法与Q学习机制结合而成的Ant-Q算法^[156]，有效地解决了进化速度慢及陷入局部最优解的问题。Gambardella等提出了ACS-3-Opt算法^[157]，将蚁群算法与3-Opt局部搜索算法进行耦合，有效地提高了蚁群算法的求解精度和计算效率。蚁群算法的另一种改进是将蚁群算法和神经网络相结合^[158]，使得神经网络的广泛映射能力和蚁群算法的快速全局收敛性能相互补充，呈现出单一算法所不具有的特性。

（4）多重蚁群算法。随着蚁群算法的不断改进、逐步发展完善及工程应用对算法要求的不断提高，研究重点必然转向使用几个蚁群协同解决问题的多重蚁群算法。传统蚁群算法中只有一个蚁群，没有充分挖掘蚁群算法的本质并行性及分布式计算等优良特性；多重蚁群算法通过使用正、负两种信息素效应，利用蚁群群体层的交互作用，使得蚁群能够更好地交换问题解决过程的规划信息，同时保持蚁群在搜索过程中的多样性。

2.1.4.6　蚁群算法的应用

蚁群算法已在许多组合优化问题中获得了成功应用^{[151]，[152]，[159-166]}，这些问题可分为两类：静态组合优化问题，参数特性在求解过程中不发生变化，如TSP（traveling salesman problem），QAP（quadratic assignment problem），SOP（sequential ordering problem），VRP（vehicle routing problem），JSSP（job-shop scheduling problem）等；动态组合优化问题，参数特性在求解过程中发生变化，如网络路由问题等。

（1）在TSP中的应用。TSP是蚁群算法应用最早、最多的一类组合优化问题。Colorni等首先将蚁群算法应用于TSP中^[142]。Gambardella等基于蚁群算法和Q学习算法^[157]设计了Ant-Q算法^[156]，并用来求解TSP问题。Dorigo等对Ant-Q算法进行了简化，并采用2-Opt和3-Opt局部搜索算法对蚂蚁构造的解进行改进，在求解TSP问题时得到了很好的求解效果^[140]。Bullnheimer等基于排序思想提出了一种求解TSP问题的改进蚁群算法（AS）^[148]。Stutzle等基于蚁群算法设计了求解TSP问题的MMAS算法，并采用2-Opt等局部搜索算法来改进由蚂蚁构造的解^[168]。陈烨将交叉算子引入蚁群算法中，并采用改进算法来求解TSP问题^[155]。吴庆洪等在蚁群算法中引入变异机制，并采用2-Opt来改进由蚂蚁构造的解，使得该方法在求解TSP问题时具有较快的收敛速度^[154]。吴斌等将相遇算法与分段算法相结合，提出一种求解TSP问题的改进蚁群算法^[169]。王颖等通过自适应调整蚁群算法中的相关参数，在保证收敛速度的前提下极大地提高了求解质量^[170]。马良等将ACS应用推广到多目标TSP问题中^[171]。

（2）在QAP中的应用。QAP是蚁群算法在组合优化领域的另一个典型应用。鉴于QAP和TSP的相似性，很多学者将求解TSP的蚁群算法进行调整和改进后再来求解QAP问题。Maniezzo等提出了一种求解QAP问题的改进蚁群算法，采用禁忌搜索方法对蚂蚁构造的解进行局部优化^[172]，针对QAP设计了Ants-QAP算法^[173]。Stutzle等研究了MMAS在QAP中的应用^[168]。Tailland等针对QAP设计了FANT算法，算法中仅使用一只蚂蚁，在算法执行过程中对信息素更新的学习步长作自适应调整^[174]。Gambardella等针对QAP设计了HAS-QAP算法，该方法没有将信息素浓度用在解的构造过程中，而是用在了对解的改进过程中^[175]。Talbi等设计的Ant-Tabu算法与HAS-QAP具有相似结构^[176]，但采用并行机制实现。

（3）在网络路由问题中的应用。蚁群算法在动态组合优化问题中的应用主要集中在网络通信方面，特别是网络路由选择问题上。网络路由选择问题可简单描述为在一个代表通信网络的全连接图中求解任何两个节点的最短路径问题。虽然在静态环境下该问题可通过多项式算法求解^[177]，但在节点间流量随时间变化情况下，该问题的求解变得非常困难。Caro等针对网络路由问题设计了算法Ant-Net^[178]，取得了比较满意的结果。

2.1.4.7　蚁群算法的发展趋势

蚁群算法在解决离散优化问题上的卓越性能，以及在解决连续优化问题上的初露锋芒，吸引了众多研究者的关注，并提出了许多有效的改进方法，使得蚁群算法发展很快，但还有很多方面有待完善，需要进行深入研究^{[145]，[159]}。

（1）加强蚁群算法各种改进方法的综合研究。现有研究工作主要针对蚁群算法的不同部分进行修改，蚁群算法各个参数的相互作用及最优配置、各种方法的综合使用及各种改进方法的相互作用等都是未来研究的重点。

（2）加强蚁群算法与其他算法的耦合。蚁群算法具有很强的耦合性，易与其他进化算法或局部搜索算法相结合，将蚁群算法与神经网络、遗传算法、模拟退火算法等相融合，必将成为今后蚁群算法新的研究热点。

（3）加强蚁群算法与应用的结合。尽管蚁群算法在众多领域得到了推广，但大多数研究仅局限于仿真试验，应当充分挖掘蚁群算法在实际应用中的潜力，对现有应用领域进行深化研究，进一步扩大其应用范围。

（4）采用Multi-Agent技术来改进蚁群算法。在蚁群系统中，可赋予人工蚂蚁更多的智能性和学习能力。可考虑对蚂蚁进行分工，不同蚂蚁具有不同能力并完成不同任务。在具体实现方面，可将每只蚂蚁看作一个Agent，然后再设法寻求所有蚂蚁之间的彼此协调，最终共同实现系统整体目标。如何设计程序框架使得基于Multi-Agent的蚁群框架具有广泛的适用性也需要深入研究。

2.1.5　学习型智能优化的基本框架

在现有智能优化方法中，还没有大量直接地挖掘、存储和应用待求解问题的相关领域知识，因此还不能更加有效地得到优化问题的最优解。在现实生活中，实际系统的规模越来越大，约束条件越来越多，系统结构越来越复杂，多准则、非线性、不可微、不确定已成为这些复杂系统的基本特征。探寻适合大规模计算且具有智能特征的问题求解方法已成为相关学科的研究热点和重要研究方向。

本书认为在求解复杂优化问题时，可从优化过程中直接挖掘一些待求解问题的相关知识，然后应用知识来指导后续优化过程。本书更多地关注一些显性知识，即能明确表达的知识。本书中用到的显性知识，都可采用计算机语言来表示和存储；其他模型也可通过给定方式对这些知识进行更新和应用。

本书把学习型智能优化方法定义为：将智能优化模型和知识模型有效结合起来的混合智能优化方法。在学习型智能优化方法中，智能优化模型按照“邻域搜索”策略对优化问题的可行空间进行搜索；知识模型从前期的优化过程中挖掘出有用知识，然后采用知识来指导智能优化方法的后续优化过程。将智能优化模型和知识模型有效地结合起来，极大地提高了学习型智能优化方法的优化绩效。

鉴于此，本书提出一类学习型智能优化方法，该方法采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型为基础，同时突出知识模型的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。学习型智能优化方法的基本框架如图2.4所示。

在求解一些实际复杂工程问题（如军事、交通、工程和网络等领域的优化问题）时，应考虑将人机交互功能引入学习型智能优化方法中。由于本书内容所限，暂时还没有考虑把人机互动（人在回路）功能加入到学习型智能优化方法中。在后续著作中，可考虑将人机交互功能引入学习型智能优化方法。

2.1.6　学习型智能优化的运行机制

学习型智能优化方法的运行机制如图2.5所示。图2.5的顶部刻画了智能优化方法的优化进程。智能优化方法按照“邻域搜索”机制对优化问题的可行空间进行搜索；经过逐步迭代，智能优化方法最终收敛到最适应环境的个体。图2.5的底部刻画了知识模型的作用。知识模型从前期优化过程中挖掘或抽取有用知识，然后应用知识来指导后续优化过程。

在学习型智能优化方法的运行过程中，由于初始阶段可供学习的样本太少，挖掘出来的知识可信度不高，对后续优化过程的指导作用也不明显；随着迭代的逐步推进，挖掘出来的知识可信度越来越高，对后续优化过程的指导作用也越来越明显。与智能优化方法相比，在知识模型的辅助下，学习型智能优化方法要么能更加快速地收敛到一个满意解；要么能收敛于一个质量更高的满意解。

在学习型智能优化方法的优化过程中，知识模型和智能优化模型都起着非常重要的作用。智能优化模型是基础，按照“邻域搜索”机制对优化问题的可行空间进行搜索；知识模型是核心，从前期优化过程中挖掘有用知识，应用知识来指导后续优化过程。将智能优化模型和知识模型有效地集成起来，极大地提高了学习型智能优化方法的优化绩效。