作者：陈英武,向尚,邢立宁
出版社：清华大学出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
学习型智能优化算法及其应用试读：
前言
最优化技术在科学和工程等领域都有非常广泛的应用，理论界和工程界都对其进行了热切关注和深入研究。优化理论与算法的研究已成为一个具有理论意义和应用价值的热点课题。智能优化方法模仿自然现象的运行机制而产生，为解决复杂工程问题提供了新思路和新手段。最优化理论领域的“无免费午餐”定理说明算法混合是有效提高优化性能的一种手段，将各种算法有效地集成起来构成新的高效的优化方法是一个非常有价值的研究方向。
在现有智能优化方法的基础上，本书建立了学习型智能优化方法的基本框架。该框架采用智能优化模型和知识模型相结合的集成建模思路：智能优化模型按照“邻域搜索”策略对优化问题的可行空间进行搜索；知识模型从前期优化过程中挖掘有用知识，然后采用知识来指导智能优化模型的后续优化过程。构建学习型智能优化的基本框架，可以将智能优化模型和知识模型有效地结合起来，极大地提高了学习型智能优化方法的优化效果。学习型智能优化方法的基本框架为现有优化方法的改进提供了一种有益的借鉴。
本书提出了精英个体知识、构件知识、算子知识和参数知识4种知识形式，为学习型智能优化方法嵌入知识奠定了重要基础；构建了用于实现学习型智能优化方法的8类典型知识，可辅助学习型智能优化方法高效地求解复杂优化问题。
针对连续优化问题，本书设计并实现了一种求解函数优化问题的学习型遗传算法。采用21个标准测试函数进行实验，结果表明学习型遗传算法在优化性能方面优于近期公开发表的3种方法。
针对离散优化问题，本书设计并实现了求解3类典型离散优化问题的5种学习型智能优化算法。基于标准测试实例的实验结果表明，学习型智能优化算法在优化性能方面优于已经公开发表的多种方法。
针对实际工程问题，本书将学习型遗传算法和学习型蚁群算法分别应用于体系仿真优化问题、卫星地面站系统任务调度问题和多星任务规划问题，获得了非常满意的实验结果。
本书主要面向在运筹学领域研究智能优化方法的企业、高校与科研院所的研究人员，帮助读者了解学习型智能优化算法的基本原理与框架流程，提高读者对学习型智能优化算法的实践与应用能力，促进学习型智能优化算法的发展与完善。作 者2018年10月第1章 绪论1.1 背景及意义1.1.1 背景
在工业、农业、国防、工程、交通、金融、化工、能源和通信等[1]许多领域都存在着大量的“寻优”需求。“寻优”可简要地概括为：在满足既定约束条件下，寻找一组比较合适的参数值，使待研究系统的某些性能指标达到最大或最小。优化在资源利用、结构设计、调度管理和后勤供应等许多领域已产生了巨大的经济效益和社会效益，同时在结构力学、生命科学、材料科学、环境科学、控制论等其他领域也有着非常广泛的应用。优化方法是一种以数学为基础，用于求解各种最优化问题的应用技术，优化方法理论和技术历来受到人们的广泛
[1]重视。最优化问题根据优化变量的取值类型可分为连续优化问题和离散优化问题两大类。随着科学技术的日益发展，离散优化问题与日俱增，越来越受到管理科学、运筹学、计算机科学及应用数学等诸多学科领域研究人员的高度重视。
在管理科学、计算机科学和工程学等学科及诸多应用领域中，不断涌现出许多大型复杂优化问题。面对这些问题，传统优化方法如牛顿法、共轭梯度法、模式搜索法和单纯形法等需要遍历整个搜索空间，从而产生搜索的组合爆炸，即无法在多项式时间内完成搜索。大型复杂优化问题通常都属于NP-难问题。鉴于实际工程问题的复杂性、约束性、非线性和建模困难等特点，探索高效的优化算法已成为相关学科的主要研究方向之一。[2]
自然界中许多自适应优化现象不断地启示着人类：生物体和自然生态系统通过自身演化就能比较满意地解决许多复杂问题。计算机科学家们不断地从生物系统研究中获得灵感，并通过模仿自然世界的内在机制去获取解决复杂优化问题的新方法。20世纪80年代以来，一些智能优化方法如遗传算法（源自达尔文的自然界进化理论）、蚁群算法（模拟蚂蚁的集体觅食行为）和神经网络（模拟大脑结构和思维过程）等，通过模拟某些自然现象或过程而产生、发展并不断成熟，为解决复杂工程问题提供了新思路和新手段。智能优化方法的出现极大地丰富了最优化技术，也为那些用传统优化技术难以处理的组合优化问题提供了切实可行的解决方案。
智能优化方法模拟自然界的生物系统，依赖生物体的自身本能，通过无意识的寻优行为来优化其生存状态。智能优化方法根据所使用智能体的数量可分为基于个体的智能优化方法和基于种群的智能优化方法，其中模拟退火算法等是基于个体的智能优化方法，而遗传算法、蚁群算法和粒子群优化算法等都是基于种群的智能优化方法。基于种[2]群的智能优化方法的主要特点可概括为：● 是一类不确定的优化算法。不确定性体现了自然界生物的生理机制，并且在求解某些问题时优于确定性算法。● 是一类概率型的全局搜索算法。随着搜索过程的不断推进，找到优质解的概率大于得到劣质解的概率，能以更大概率求得全局最优解。● 在优化过程中不依赖于优化问题本身的某些数学特性。如目标函数和约束条件的精确数学描述、目标函数的连续性及可导性等。● 是一类基于多个智能体的算法。各个智能体之间通过相互协作来更好适应环境，以获取所需性能。● 具有潜在的并行性。搜索过程同时从多点出发，分布式并行模式极大提高了整个算法的运行效率、鲁棒性和反应能力。● 具有学习能力。在复杂的、不确定的、时变的环境中，能通过自我学习不断提高个体的适应性。[1]
智能优化方法的现有研究主要集中在三个方面：对现有智能优化方法进行改进并广泛应用，对其理论进行深入研究；开发新的智能优化工具，拓宽其应用领域，并对其寻求理论基础；各种现有智能优化方法的混合。算法性能（精度和速度）的提高是永无止境的，提高现有智能优化方法处理各种工程问题的性能，并对其进行理论研究已成为当前智能优化领域研究的首要任务和热点问题。1.1.2 动机
根据搜索方法的发展历程（图1.1），可将现有的搜索方法分为以下三类：古典搜索方法、启发式搜索方法和智能优化方法。● 古典搜索方法。如步长加速法、旋转方向法、单纯型调优法、方向加速法、枚举法和随机搜索方法等。古典搜索方法仅通过比较目标函数值的大小来移动迭代点，它的搜索策略像是“跟着感觉走”。● 启发式搜索方法。如共轭梯度法、牛顿型方法和变尺度法等。启发式搜索方法有一套严密的理论体系，通过比较目标函数的梯度值来移动迭代点，可看作是“梯度信息启发下的简单智能搜索”。启发式搜索方法将优化问题的梯度信息引入优化过程中，采用目标函数的梯度值来引导优化方法的寻优过程。相对于古典搜索方法，启发式搜索方法能更快地搜索到优化问题的最优解。图1.1 搜索方法的发展历程● 智能优化方法。如模拟退火算法、遗传算法、禁忌搜索、进化规划、进化策略和蚁群算法等。智能优化方法在优化流程上均是一种“邻域搜索”结构。智能优化方法在一定程度上把优化问题的领域知识隐含地加入到算法中。如在遗传算法中，通过选择、交叉和变异操作，将优化问题的较优个体的一些部件特征（component characteristic）逐步地保留下来；在蚁群算法中，通过信息素将优化问题较优个体的一些部件特征逐步地保留下来。与启发式搜索方法相比，智能优化方法能较好地解决大规模复杂系统中出现的组合爆炸问题，不仅具有通用、稳健、简单、便于并行处理等优点，而且有望成为数值计算与语义表达、形象思维等高级智能行为之间相互联系的桥梁。智能优化方法的研究在一些采用传统方法难以解决或无法解决的应用领域中取得了重大突破。
在现有智能优化方法中，还没有大量直接地挖掘、存储和应用待求解问题的相关领域知识，还不能最有效地得到最优解。在现实生活中，实际系统的规模越来越大，约束条件越来越多，系统结构越来越复杂，多准则、非线性、不可微、不确定已成为这些复杂系统的基本特征。探寻适合大规模计算且具有智能特征的问题求解方法已成为相关学科的研究热点和重要研究方向。
本书认为在求解复杂优化问题时，可从优化过程中直接挖掘一些待求解问题的相关知识，然后应用知识来指导后续优化过程。本文更多地关注一些显性知识，即能明确表达的知识。显性知识可采用计算机语言来表示和存储，其他模型可通过给定方式对这些知识进行更新和应用。鉴于此，本书提出一类学习型智能优化方法：采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型为基础，同时突出知识模型的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。
学习型智能优化方法研究的难点主要表现在以下方面：● 学习型智能优化方法的基本框架。构建一种比较通用的优化框架，将智能优化方法和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。● 知识的定义。构建用于实现学习型智能优化方法的若干典型知识，这些典型知识可辅助学习型智能优化方法高效地求解复杂优化问题。● 设计并实现若干种比较典型的学习型智能优化方法。针对一些连续优化问题、组合优化问题或实际工程问题，设计并实现若干种比较典型的学习型智能优化方法，这些方法稍加修改就可推广到其他复杂优化问题的求解中。1.2 智能优化方法
智能优化方法的主要思想来源于人类对物理、生物和社会等自然现象的长期观察和深刻理解。智能优化方法的特点就是仿自然，如仿人类思维（神经网络、禁忌搜索等）、仿生物行为（粒子群优化、蚁群优化等）和仿物理原理（模拟退火、微正则退火等）。这些方法从随机的可行初始解出发，采用优胜劣汰策略，在可接受的计算成本内去搜寻满意解。虽然不能保证最终一定能求得最优解，但智能优化方法能在搜索精度和算法复杂度之间达到某种平衡。智能优化方法已成为解决优化问题特别是NP-难问题的一种有力工具，在优化领域得到了非常广泛的应用。
常用的智能优化方法有以下几种：（1）模拟退火（simulate anneal）。模拟退火是基于Monte Carlo迭代求解策略的随机寻优算法，其出发点是固体物质退火过程与组合优化问题的相似性；从某一初温开始，随着温度的降低，结合概率突跳特性在解空间中搜索最优解，即在局部解时能概率性地跳出并最终趋于全局最优。（2）遗传算法（genetic algorithm）。遗传算法是一种通过模拟自然进化过程搜索最优解的方法。它将问题求解表示成染色体适者生存过程，通过染色体的逐步迭代，最终收敛到最适应环境的个体（优化问题的最优解或满意解）。（3）禁忌搜索（tabu search）。禁忌搜索是一种全局逐步优化算法，它模拟人类的智力过程，通过引入一种灵活的存储结构和相应的禁忌规则来避免迂回搜索，并通过藐视原则来赦免一些被禁忌的优良状态，以实现全局优化。（4）进化规划（evolution programming）。进化规划过程可理解为从所有可能的计算机程序中，搜索具有高适应度的计算机程序个体。进化规划最初由随机产生的计算机程序群体开始，计算机程序由适合问题空间领域的函数组成，函数可以是算术运算函数、编程操作、逻辑函数或领域函数。群体中每个计算机程序个体都是用适应度来评价的，该适应度的取值与特定问题领域有关。（5）进化策略（evolution strategy）。进化策略通过模仿自然进化原理来求解参数优化问题。进化策略和遗传算法的区别包括：表示个体的方式不同，进化策略在浮点矢量上运行，而遗传算法一般运行在二进制矢量上；选择过程不同；复制参数不同，遗传算法的复制参数（交叉和变异的可能性）在进化过程中保持恒定，而进化策略动态地改变它们。随着技术的发展，进化策略和遗传算法的差别越来越不明显。（6）蚁群算法（ant colony optimization）。蚁群算法是受自然界中蚂蚁搜索食物行为的启发而提出的一种随机优化算法。蚂蚁间借助于信息素这种化学物质进行信息的交流和传递，并表现出正反馈现象：某段路径上经过的蚂蚁越多，该路径被重复选择的概率就越高。正反馈机制和通信机制是蚁群算法的两个重要基础。（7）人工神经网络（neural network）。人工神经网络是一种模仿动物神经网络行为特征，进行分布式并行信息处理的数学模型。人工神经网络具有自学习和自适应能力，可通过预先提供的相互对应的输入数据和输出数据，分析掌握两者之间的潜在规律，最终根据这些规律，用新输入数据来推算输出结果。1.3 知识导向的智能优化算法
智能优化算法是当前研究的热点问题，其主要缺点是容易出现早熟收敛和收敛速度慢。导致这些缺点的一个重要原因就是智能优化算法中缺乏明确的导向因子。国内外学者一方面通过传统人工智能手段和特定知识模型来实现对智能优化算法的进化引导，同时也采用具有双层进化机制的文化算法对智能优化算法进行引导。1.3.1 传统人工智能引导的智能优化算法
采用传统人工智能手段对智能优化算法进行引导，如采用禁忌搜[3][4][5][6]索、文化算法和机器学习来控制进化等。在具体实施时，必须首先抽取一些进化过程中尽可能一般和重要的规则，利用禁忌搜索、文化算法和机器学习等算法进行学习，然后根据学习得到的规则控制个体进化。这些工作的缺点在于很难找到尽可能一般和重要的规则，而且这些规则缺乏全局性，没有考虑到随着个体的进化，个体所处的[6]环境也在不断变化，因而相应的规则也应该变化。
为了平衡进化过程中选择操作正向作用和交叉（变异）操作破坏[7]性影响，范磊等采用归纳学习方法来引导进化过程：采用归纳学习方法从进化历史进程中抽取出能反映过去进化的错误和成功的规则，进而用它们来引导后续进化过程，保证在避免重复错误的同时加速进化。基于函数优化和布局求解的实验验证了其有效性。
曹先彬等借鉴个体进化的生命周期性，提出了一种基于生命期引[8]导的生态进化模型。基于此模型的算法在个体生命期的各个阶段设置了相应的引导算子，使个体在整个生命期都基于其生态特征而被引导进化。实验结果验证了其优越性。
为了提高粒子群算法中粒子搜索全局最优解的准确度，岑宇森等[9]提出了基于知识空间的分组式粒子群算法。该算法使用k-means算法对粒子群进行分组，利用较小的最大飞行速度加强粒子在组内的局部搜索能力，并将“知识空间”的概念引入到分组中，由知识空间中的粒子来引导群中粒子前往更好的解空间搜索。
李亚男等在遗传算法中采用专家知识辅助寻优，并将该改进遗传[10]算法应用到无功规划优化中。依据专家知识对少数被选中的个体动态形成本厂、站的就地无功／电压控制的有效变量集进行人工调整，可改善遗传算法的局部寻优能力。对某实际系统的计算表明，结合专家知识的遗传算法能够更有效地找到全局最优。
柴啸龙将领域知识通过禁忌连接集的形式加入蚁群规划算法中[11]，相邻动作层的很多互斥信息通过禁忌连接集只需计算一次，不进入主循环计算中，这样可以较好地提升算法的执行效率。实例分析表明这一策略是有效的。1.3.2 特定知识模型引导的智能优化算法
采用特定知识模型对智能优化算法进行引导时，在智能优化算法运行之初就已确定了知识的基本形式，相关知识按照固定规则随着算法演化而不断调整，然后采用已获得知识来指导后续个体的进化。采用特定知识模型对智能优化算法进行引导也可理解为演化与学习之间[12-17]的交互（interaction between evolution and learning）。
根据现有文献，研究人员一般通过以下两种途径来实现演化和学[18]习之间的交互：学习已获得个体的一些优良特征，采用这些优良特征来改进后续产生的个体；学习已获得个体的一些不良特征，采取措施防止这些不良特征出现在后续个体中。现有研究表明：演化和学习之间的交互是可能的，可采用多种途径来实现演化和学习之间的交[19][20]互，例如版本空间（version space）、基于案例的记忆单元、Q-[21]，[22]学习系统（Q-learning system）和AQ-学习系统（AQ-learning [23]system）等。通过演化和学习之间的交互可有效提高智能优化方法[18]的优化效率。1.3.2.1 采用记忆单元对智能优化算法进行引导
很多学者尝试采用记忆单元（memory cell）来实现演化和学习之间的交互。Chung和Reynolds将个体优良特征看作是信念（beliefs），将这些信念保存到记忆单元中，采用这些信念来改进后续
[24]个体。Branke将一些已获得的较优个体保存到记忆单元中，采用这[25]些较优个体来改进后续个体。
Gantovnik等采用记忆单元在遗传算法中实现演化和学习之间的
[26]，[27]交互，并使用这种改进遗传算法来解决混合变量优化设计问题。[28]Louis和Li采用带有记忆单元的遗传算法来求解旅行商问题。Yang采用基于记忆单元的移民方式在遗传算法中实现演化和学习之间的交[29]，[30]互，并使用这种改进遗传算法求解动态优化问题。
苏淼等采用免疫记忆方式在蚁群算法中实现演化和学习之间的交[31]互，并使用这种改进蚁群算法来求解武器目标分配问题。Acan使用外部记忆单元（external memory）在蚁群算法中实现演化和学习[32]之间的交互。在此基础上，Acan在外部存储器中加入了局部置换[33]（partial permutations）功能，进一步提高了改进蚁群算法的效率。Shamsipur使用外部记忆单元在蚁群算法中实现演化和学习之间的交[34]互。1.3.2.2 基于案例对智能优化算法进行引导
很多学者也采用案例（case）在智能优化方法中实现演化和学习[20]，[35]，[36]之间的交互。Louis和McDonnell采用案例推理（case-based reasoning）方法从案例记忆单元（case-based memory cell）中选择[20]特征来改进后续个体。Louis和Li在遗传算法中采用案例注入方式来[35]实现演化和学习之间的交互，并使用这种改进遗传算法来求解旅行商问题。Rasheed和Hirsh采用案例学习方式在遗传算法中实现演化和[36]学习之间的交互。Babbar-Sebens和Minsker提出了一种基于案例的宏观交互式遗传算法（case-based micro interactive genetic [37]algorithm），主要通过案例记忆单元和案例推理来实现演化和学习之间的交互。1.3.2.3 采用学习演化模型对智能优化算法进行引导
不同于基于达尔文进化论的演化计算方法，学习演化模型（learnable evolution model，LEM）主要采用机器学习方法来指导整[38]个演化进程。Coletti对学习演化模型进行了初步研究，Wojtusiak研[39]究了学习演化模型中的约束优化问题，Kaufman和Michalski采用学[40]习演化模型来解决热交换器设计问题，Jourdan等使用学习演化模[41]型来解决多目标水系统设计问题，Domanski等采用学习演化模型[42]来求解优化设计问题。目前，学习演化模型的最新版本为LEM3。[43]Wojtusiak和Michalski应用LEM3来解决复杂函数优化问题。
近年来，越来越多的学者开始使用学习演化模型在智能优化方法[18]，[23]中实现演化和学习之间的交互。Michalski等在总结学习演化模[44]型最新进展的基础上，在智能优化方法中采用学习模型来实现演化[45]和学习之间的交互。在Michalski构建的学习演化模型中，主要采用[23]机器学习方法来实现演化和学习之间的交互。Ho等采用学习型遗传框架（learnable genetic architecture，LEGA）来实现演化和学习之[18]间的交互。Wojtusiak设计了一种可用于多种智能优化方法的LEM3
[46]系统。1.3.2.4 采用神经网络对智能优化算法进行引导
针对遗传算法个体进化缺乏明确导向的缺点，顾慧等提出了一种[6]基于知识模型的改进遗传算法：利用神经网络的学习功能，从当前两代个体的信息中获取一定知识，用于控制下一代某些个体的进化。该算法既保留了遗传操作算子，同时利用神经网络构造相应的知识模型，用于引导个体进化，使得改进遗传算法既保留了遗传算法强大的全局随机搜索能力，又具有神经网络的自学习能力和强鲁棒性。1.3.3 具有双层进化机制的文化算法
文化算法模拟人类社会的文化进化过程，由实现个体进化的种群空间和实现知识更新的信度空间构成。文化算法通过信度空间实现对进化信息的有效提取和管理，并利用进化信息指导种群空间的进化过程。文化算法可实现隐含进化信息的显性归纳和描述，在种群空间之上扩展信度空间，以独立实施知识管理，实现知识进化过程。目前文化算法已被成功用于解决农业进化、概念学习、实值函数优化和制造装配过程的重新设计等问题。已经证明，在文化加速进化作用下的进[47]化远优于单纯依靠基因遗传的生物进化。
在传统进化算法的基础上，文化算法通过构建信度空间来提取隐含在进化过程中的各类信息，并以知识形式加以存储，最终用于指导[48]进化过程，其基本结构如图1.2所示。文化算法由种群空间、信度空间和接口函数构成一种双层进化结构。上层信度空间中的知识进化是以底层种群空间中的个体进化为基础，且知识是个体经验的高度概括。该双层进化结构体现为个体微观进化和知识宏观进化两个不同粒[48]度的进化层面。图1.2 文化算法的基本结构● 种群空间用于实现基于种群的进化算法。一方面对个体进行评价，并面向种群实施进化操作；另一方面将优良个体作为样本提供给信度空间。● 信度空间通过接受函数从已评价种群中选取样本个体，在知识更新函数的作用下，提取样本个体所携带的隐含信息，并以知识形式加以概括、描述和储存。各类知识通过影响函数作用于种群空间，从而实现对进化操作的引导。● 接受函数和影响函数为上层知识模型和下层进化过程提供了作用通道，称为接口函数。1.3.3.1 种群空间
随着智能计算研究的不断深入，遗传算法、进化规划、遗传规划、粒子群优化算法及微分进化算法等诸多智能优化方法被引入种群空间。● 遗传算法最早被引入种群空间。Reynolds等针对概念学习问题，采用基于遗传算法的种群空间，讨论了信度空间的知识构成[49]。采用遗传算法的优点在于，知识对进化过程的引导作用可体现在不同进化算子上。● 进化规划仅采用变异算子，知识对进化过程的影响程度易于观察和分析。Jin使用基于进化规划的文化算法解决非线性约束[50]优化问题，将信度元的概念引入到信度空间。● 遗传规划采用遗传操作来动态改变程序所描述的问题模型，采用遗传规划作为种群空间的文化算法，在软件工程、基于代理[51]模型的策略优化问题中得到较好应用。● 有学者采用粒子群优化算法作为种群空间，分析了在信度空间[52]，[53]各类知识进行交流的情况下个体间的信息传播。● 微分进化本质上是一类基于概率分析的进化算法，研究人员将微分进化引入文化算法的种群空间，用于解决非线性约束优化[54]，[55]和多目标优化等问题。● 交互式进化计算是一类由人参与个体评价的算法。研究人员将该算法引入种群空间，通过提取人的认知和偏好等知识来缩小[56]搜索空间，加速进化收敛。1.3.3.2 信度空间
信度空间的核心在于知识如何描述和更新。种群空间采用的进化策略不同和应用领域不同，相应的知识形式也有所不同。一般而言，信度空间知识被划分为5类：状况知识、规范知识、拓扑知识、领域[50]，[56-58]知识和历史知识。这5类知识本质上都是进化过程中隐含信息的显性描述，但在某些需要人参与的实际优化问题中，反映人类经验的常识知识也对进化过程具有重要引导作用。
根据底层种群进化层提供的信息来源及其特征，也有学者将知识划分为常识知识、进化知识和评价知识三部分，分别用来存储以对象形式描述的显性常识知识、以特征向量形式描述的进化过程隐含知识[59]和以代理模型形式描述的用户评价隐含知识，从而拓展了知识描述形式，丰富了知识内容。1.3.3.3 接受函数
接受函数从种群空间选取较优个体提交给信度空间用于知识更新，其研究核心在于选取较优个体数目。目前，已有的接受函数有3[48]类：固定比率接受函数、动态接受函数和模糊接受函数。这3类接受函数各有特点，在实际应用中应根据具体优化问题进行选择。1.3.3.4 影响函数
影响函数的主要作用是使用信度空间中各类知识引导种群进化。进化初期，种群探索整个搜索空间，此时规范知识及拓扑知识处于控制地位，一方面限定探索区域，另一方面引导搜索趋于具有高属性值的单元。进化中期，更新状况知识和规范知识，进一步缩小搜索范围，并重新划分拓扑知识，引导种群在更小粒度单元上进行搜索。进化后期，搜索集中在某一局部区域，容易导致早熟收敛，于是引入历史知识，帮助种群跳出局部较优点。在整个进化过程中，领域知识一直为种群进化提供进化方向的指引。从知识对进化过程的引导作用可以看出，影响函数的关键问题在于各类知识何时作用于种群及其所引导的种群比例。在各类知识的引导作用下，文化算法显示出了优于以往进化算法的收敛性、搜索能力及对环境的适应能力。1.4 章节结构
本书的结构框架如图1.3所示。本书主要有10章，各章的主要内容可概括如下。
第1章是绪论，阐述了研究背景及意义、国内外研究综述和主要研究工作。
第2章详细介绍了学习型智能优化方法，主要内容包括：学习型智能优化方法概述、学习型智能优化方法中用到的4类知识和9种典型的学习型智能优化方法。
第3章主要研究了求解函数优化问题的学习型智能优化方法，将学习型遗传算法应用到函数优化问题中。采用21个标准测试函数进行实验，结果表明学习型遗传算法在优化性能方面优于已公开发表的3种方法。
第4章主要研究了求解非对称旅行商问题的学习型智能优化方法，通过对旅行商问题的描述与特点分析，设计并实现了求解该问题的学习型遗传算法，该算法在求解实例时优于已公开发表的4种典型方法。
第5章主要研究了求解双层CARP优化问题的学习型智能优化方法，通过对双层CARP优化问题的描述与特点分析，探讨了求解双层CARP优化问题的基本框架，设计并实现了求解该问题的学习型遗传算法和学习型蚁群算法，这种算法在求解测试实例时均优于其他改进方法。
第6章主要研究了求解柔性作业车间调度问题的学习型智能优化方法，设计并实现了求解该问题的学习型蚁群算法和学习型协同进化算法，这种方法在求解15个标准实例时优于已经公开发表的几种典型方法。
第7章主要研究了求解体系仿真优化问题的学习型智能优化方法，通过对体系仿真优化问题的描述与特点分析，设计并实现了求解体系仿真优化问题的学习型遗传算法。实验结果表明，在求解体系仿真优化问题时，学习型遗传算法的效率都比其他方法高，应用本方法求解体系优化问题是可行的、正确的、有效的。图1.3 本书的结构框架图
第8章主要研究了求解卫星地面站系统任务调度的学习型智能优化方法，首先对卫星地面站系统任务调度问题进行描述，设计并实现了求解卫星地面站系统任务调度的学习型蚁群算法。实验结果表明学习型蚁群算法能快速有效地求解卫星地面站系统任务调度问题。
第9章主要研究了求解多星任务规划问题的学习型智能优化方法，首先对多星任务规划问题进行描述，然后建立了多星任务规划模型，接着设计并实现了求解多星任务规划问题的学习型蚁群算法。实验结果表明学习型蚁群算法在优化性能方面优于其他两种方法。
第10章是总结和展望，在总结研究结论的同时，提出了未来的研究方向。
在现有研究中，国内外学者围绕特定领域与问题对智能优化方法进行了大量研究。近年来，有学者开始研究通过知识对智能优化算法进行引导，但将其作为一个方法体系进行研究的较少。在传统智能优化方法的基础上，本书构建了一类学习型智能优化方法：从学习型智能优化的角度，构建了4类典型知识形式；从优化过程中挖掘一些有用知识，然后采用知识来指导后续优化过程；针对连续优化、离散优化和实际工程优化问题提出了一系列学习型智能优化方法，获得了较为满意的结果。本书的主要创新点可概括为以下3个方面。（1）建立了学习型智能优化方法的基本框架。采用智能优化模型和知识模型相结合的集成建模思路，智能优化模型按照“邻域搜索”策略对优化问题的可行空间进行搜索；知识模型从前期的优化过程中挖掘出有用知识，然后采用知识来指导智能优化模型的后续优化过程。演化学习型智能优化方法的基本框架为现有优化方法改进提供了一种有益的借鉴。（2）提出了精英个体知识、构件知识、算子知识和参数知识这4种典型的知识形式，为学习型智能优化方法嵌入知识奠定了重要基础；构建了用于实现学习型智能优化方法的8类知识，可辅助学习型智能优化方法高效地求解复杂优化问题。（3）针对连续优化、离散优化和实际工程优化问题，设计并实现了9种学习型智能优化方法，获得了较为满意的结果。这些方法稍加修改就可以推广到其他复杂优化问题的求解过程中。第2章 学习型智能优化方法
本章将详细介绍学习型智能优化方法，主要内容包括：学习型智能优化方法概述，学习型智能优化方法中用到的知识和几种典型的演化学习型智能优化方法。2.1 学习型智能优化相关理论
在本节中，首先对相关概念进行了简单界定，然后提出了学习型智能优化方法的基本框架，最后给出了学习型智能优化方法的运行机制。2.1.1 知识
知识是对某个主题确信的认识。认知事物的能力是哲学中充满争议的中心议题之一，并且拥有它自己的分支——知识论。从更加实用的层次来看，知识通常被某些群体所共享，知识可通过不同方式来操作和管理。尽管知识是日常生活的中心组成部分，但它的确切定义仍是哲学家、社会科学家和历史学家饶有兴趣的话题。根据许多思想家的论述，知识必须具备三个特征：被证实的（justified）、真的(1)(2)（true）和被相信的（believed）。根据维基百科、互动百科和百(3)度百科中的描述，常见的知识定义方式有以下几种。● 知识是一种被确认的信念，通过知识持有者和接收者的信念模式和约束来创造、组织和传递。知识是从信息中变化、重构、创造而得到的，其内涵比数据、信息要更广、更深、更丰富。知识可分为显性知识（explicit knowledge）和隐性知识（tacit knowledge）。显性知识可用正规化的、系统化的语言来传输；隐性知识拥有个性化特征，很难被正规化和传播。● 知识是存在于专业人员身上的技能财产，可分为实证知识、高级技能、系统认知和自我激励创造力等。● 知识是资讯、文化脉络及经验的组合。● 知识是企业的无形资产。● 知识是用以辅助决策的事实、模式、概念、意见及直觉的集合体。● 知识是从人类活动中所获取的真理、原则、思想及资讯。● 知识是经验累积的记录，事实组织的系统化，对事实的理解，一种理解的行为或状态，人的已知和未知。● 知识是与经验、上下文（context）、解释和思考（reflection）结合在一起的信息。知识是一种流动性质的综合体，包括结构化的经验和价值，经过文字化的资讯，专家独特的见解。知识是一种可随时帮助人们决策与行动的高价值信息。●《 博弈圣经》中将知识定义为识别万物实体与性质的是与不是。●《 中国大百科全书·教育》中将知识表述为：就内容而言，是客观事物属性与联系的反映，是客观世界在人脑中的主观映象。就反映活动形式而言，有时表现为主体对事物的感性知觉或表象（感性知识）；有时表现为关于事物的概念或规律（理性知识）。
由上述定义可知，知识是抽象的，是借由某种形式而呈现出来的、可互相传达的概念。本书更多地关注一些显性知识，即能明确表达的知识。显性知识可通过口头传授、教科书、参考资料、报纸杂志、专利文献、视听媒体、软件和数据库等方式获取，也可通过语言、书籍、文字、数据库等编码方式传播。本书中用到的显性知识，都可采用计算机语言来表示和存储；同时，其他模型可通过给定方式对这些知识进行更新和应用。2.1.2 知识模型
知识模型是指描述某一领域产品相关专家知识的信息模型。知识模型将专家知识、产品设计过程知识和环境知识等明确地表示于产品信息模型中，支持系统中智能模块的信息表达和传递。知识模型通常基于系统功能和结构知识构建，通过符号或流程图来描述。知识模型主要研究形式化和结构化的知识。
为了更加有效地利用知识，必须采用合适的技术来完成对相关知识的表达、获取、存储和应用。在本书中，知识模型主要完成以下功能：知识表达、知识获取、知识存储和知识应用。鉴于此，本书将知识模型定义为：为完成知识表达、知识获取、知识存储和知识应用而使用的技术、方法和手段的集合体。
知识表达就是如何采用计算机语言将用于解决问题的结构化信息表示出来。本书采用一维或多维数组来表示知识。用于表示知识的数组一般都具有特定含义，即数组中的每个元素都是可解释的（具有明确含义）。
知识获取就是采用特定方法来获得一些感兴趣的知识。在学习型智能优化方法中，知识获取主要是指从智能优化方法的演化过程中挖掘（学习）有用知识。一般用到的知识获取手段包括统计方法、机器学习和数据挖掘等。本书仅采用统计方式来完成对不同类型知识的挖掘。
知识存储就是采用特定方式将一些感兴趣的知识存储起来。本书采用一维或多维数组来表示感兴趣的知识，知识存储就相对简单。只要在相关程序中将表示知识的数组以全局变量形式定义出来，任何模型在任何时段都可访问或更新这些数组。
知识应用就是采用特定方法将知识应用到优化问题的求解中。在学习型智能优化方法中，知识应用就是如何采用知识来指导后续演化（优化）过程。在2.2节中将介绍学习型智能优化方法中用到的几类知识及其应用方式。2.1.3 遗传算法
遗传算法和蚁群算法是两种比较典型的智能优化方法，本书基于遗传算法和蚁群算法构建了多种不同的学习型智能优化方法，因此分别对遗传算法和蚁群算法的研究现状进行了综述。遗传算法（genetic algorithm，GA）是借鉴生物界进化规律（适者生存和优胜[60-62]劣汰遗传机制）而演化出来的一类随机搜索算法。遗传算法由美[63]国Michigan大学的Holland教授于20世纪70年代首次提出，非常适[64-67]合于处理传统优化方法难以解决的复杂的和非线性的优化问题。遗传算法是一类具有鲁棒性的搜索算法，主要有以下特点：以决策变量的编码作为运算对象，直接以适应度作为搜索信息，使用概率搜索技术，使用多个点的搜索信息，具有隐含并行性。遗传算法的基本运算流程如图2.1所示。2.1.3.1 遗传算法的基本理论
遗传算法的基本理论主要以收敛性分析（群体收敛到全局最优解的概率）为主，可分为基于随机过程的收敛性研究和基于模式理论的[68]收敛性分析。（1）基于随机过程的收敛性研究。对于有限编码空间和有限群体，遗传算法的搜索过程可表示为离散时间的马尔可夫链模型，从而可采用随机过程理论进行严密分析。Rudolph用齐次有限马尔可夫链[69]证明标准遗传算法收敛不到全局最优解，若采用保留最优个体的选择机制，则改进遗传算法全局收敛。Eiben等用马尔可夫链证明保留[70]最优个体遗传算法的依概率全局收敛。Qi等用马尔可夫链证明浮点[68]，[71]，[72]编码遗传算法是收敛的，但此结果是基于种群规模无穷大[73]的假设。Fogel分析了没有变异算子的遗传算法的渐近收敛性。Suzuki用马尔可夫链状态转移矩阵的特征根分析了遗传算法的收敛行[74]为。田军用马尔可夫链和随机摄动理论证明了遗传算法进入最小能[75]量集的条件。张讲社等用马尔可夫链研究了基于扩展串的等价遗传[76]算法的收敛性。图2.1 遗传算法的基本运算流程[77]（2）基于模式理论的收敛性分析。由Holland提出的模式定理[77]可称为遗传算法进化动力学的基本定理，积木块假设描述了遗传算法的重组功能，模式定理和积木块假设构成了遗传算法具备发现全局最优解的充分条件，也是分析遗传算法进化行为的基本理论，统称为模式理论。孙艳丰对模式定理进行了分析：模式定理揭示经过选择、交叉和变异后，模式H第k+1代的数目与第k代的数目的关系，并讨论[78]了无交叉时的模式定理。Srinivas讨论了自适应交叉和变异概率下[79][80]模式定理的表示方法。Bertoni等扩展了模式理论的研究成果。
最近，一些学者对模式定理的正确性提出了质疑。马丰宁通过测试黎曼函数和相应的理论分析，指出模式定理推导中的错误，并提出[81]了新模式定理。张铃等也得出类似结论，并对模式定理进行了修正[82][83]。Grefenstette指出模式定理不能保证适应度变换的唯一性。[84]Muhlenbein指出了模式定理中计算模式适应度时存在的问题。Radcliffe通过对模式定理的分析，指出遗传算法并不总比随机搜索算
[85][86]法好。Vose也论述了模式定理中存在的一些问题。
遗传算法收敛性的研究成果，要么基于群体无穷大的假设，要么基于分析简单的或特殊的遗传算法，在实际应用中的可操作性较差。一般遗传算法的收敛性分析及如何构造一个收敛的遗传算法，仍是该[87]领域亟待解决的重要理论问题。遗传算法的其他理论问题还包括：欺骗问题、维数分析、BGA（breeder genetic algorithm）理论、可分离函数、Walsh函数分析、傅里叶分析和二次动力系统等。2.1.3.2 遗传算法的改进
为了维持群体的可进化性并最终搜索到全局最优解，遗传算法必须采用合适的运算形式（编码、计算流程、种群规模、种群初始化策略、GA算子和终止条件等），这就是遗传策略研究与设计的主要内容。（1）参数设置的改进。参数确定包括静态方法和动态方法，静态方法指参数事先就确定好，算法执行过程中不变；动态方法指参数在算法执行过程中根据情况进行动态调整，以适应环境变化。由于参数设置关系到遗传算法的精度、可靠性和计算时间等诸多因素，因此许多学者通过研究参数设置来提高求解质量和系统性能。孙艳丰证明，当采用自然数编码时，从理论上可以证明遗传算法最优群体规模的存[88]在性，并给出相应的计算方法。Srinivas等提出采用自适应交叉和[79]变异概率来维持群体多样性，并保证遗传算法的收敛性。Fogarty[89]研究了变异概率对整数编码的影响。Whitley采用父代个体之间的[90]Hamming距离来设置变异概率。（2）编码方式的改进。目前主要的编码技术有：一维染色体编码（包括二进制编码、实数编码和格雷编码等）、多参数映射编码、可变染色体长度编码、二倍体（多倍体）编码和树形编码等。[71]Janikow等给出二进制编码和实数编码的实验比较。孟庆寿提出对[91]称编码，并通过优良型保护、希望型成员移民和部分基因保留等措施，来加快算法的收敛速度。Fogel提出了动态变量编码，通过对DeJong的5个函数进行测试，发现动态变量编码比普通二进制编码的[92]优化效果好很多。Goldberg等用动态背包问题进行比较研究，实验[93]表明双倍体编码比单倍体编码的跟踪能力强。张晓缋等研究了二进制和十进制编码在搜索能力和保持群体稳定性上的差异，结果表明二进制编码比十进制编码的搜索能力强，但前者不能保持群体稳定性[94]。Antonisse从理论上证明了Holland在推导最小字符集编码规则时[95]存在的错误，指出大符号集编码设计可提供更多模式。（3）选择算子的改进。常用的选择方法有：精华选择、重组选择、均分选择、适应性调整、线性排序、比例选择和自适应选择等。[96]Potts等概括了大约20多种选择方法。为了防止算法过早收敛，Potts提出微进化结构和人工选择等来改进遗传算法。Kuo等采用分裂[97]选择方法使新遗传算法比传统遗传算法在优化欺骗函数上具有更好的特性。Bäck在研究各种选择机制的基础上提出了扩展选择和偏置
[98]选择。（4）交叉算子的改进。常用的交叉技术有：单点交叉、两点交叉、均匀交叉、多点交叉、启发式交叉、顺序交叉和混合交叉等。[96]Potts概括大约20多种已有交叉技术。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.2 混合遗传算法构成示意图（2）组合优化。对于组合优化问题，应把主要精力放在寻求满意解上，遗传算法是寻求满意解的最佳工具之一。遗传算法已在求解旅行商问题、背包问题、装箱问题、布局优化问题、图形划分问题等[120-124]各种NP-难问题上得到了成功应用。（3）生产调度。遗传算法已成为解决复杂调度问题的有效工具，在单件（流水线）生产车间调度、生产规划和任务分配等方面[125-130]，遗传算法都得到了有效的应用。（4）自动控制。遗传算法在自动控制领域已得到初步应用。如采用遗传算法进行航空控制系统的优化、基于遗传算法的模糊控制器设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构设计和权值学习等。（5）机器人学。遗传算法已被成功地用于移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面。（6）图像处理。遗传算法可用于图像处理中的优化计算，目前已在模式识别（包括汉字识别）、图像恢复、图像边缘特征提取等方面得到了广泛应用。（7）人工生命。遗传算法已在人工生命的进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力。（8）遗传编程。遗传编程（genetic programming）采用树型结构来表示计算机程序，运用遗传算法的思想，通过自动生成计算机程序来解决问题。（9）机器学习。基于遗传算法的机器学习，特别是分类器系
试读结束[说明：试读内容隐藏了图片]