第1章　绪论

1.1　背景及意义

1.1.1　背景

在工业、农业、国防、工程、交通、金融、化工、能源和通信等许多领域都存在着大量的“寻优”需求。“寻优”可简要地概括为^[1]：在满足既定约束条件下，寻找一组比较合适的参数值，使待研究系统的某些性能指标达到最大或最小。优化在资源利用、结构设计、调度管理和后勤供应等许多领域已产生了巨大的经济效益和社会效益，同时在结构力学、生命科学、材料科学、环境科学、控制论等其他领域也有着非常广泛的应用。优化方法是一种以数学为基础，用于求解各种最优化问题的应用技术，优化方法理论和技术历来受到人们的广泛重视^[1]。最优化问题根据优化变量的取值类型可分为连续优化问题和离散优化问题两大类。随着科学技术的日益发展，离散优化问题与日俱增，越来越受到管理科学、运筹学、计算机科学及应用数学等诸多学科领域研究人员的高度重视。

在管理科学、计算机科学和工程学等学科及诸多应用领域中，不断涌现出许多大型复杂优化问题。面对这些问题，传统优化方法如牛顿法、共轭梯度法、模式搜索法和单纯形法等需要遍历整个搜索空间，从而产生搜索的组合爆炸，即无法在多项式时间内完成搜索。大型复杂优化问题通常都属于NP-难问题。鉴于实际工程问题的复杂性、约束性、非线性和建模困难等特点，探索高效的优化算法已成为相关学科的主要研究方向之一。

自然界中许多自适应优化现象不断地启示着人类^[2]：生物体和自然生态系统通过自身演化就能比较满意地解决许多复杂问题。计算机科学家们不断地从生物系统研究中获得灵感，并通过模仿自然世界的内在机制去获取解决复杂优化问题的新方法。20世纪80年代以来，一些智能优化方法如遗传算法（源自达尔文的自然界进化理论）、蚁群算法（模拟蚂蚁的集体觅食行为）和神经网络（模拟大脑结构和思维过程）等，通过模拟某些自然现象或过程而产生、发展并不断成熟，为解决复杂工程问题提供了新思路和新手段。智能优化方法的出现极大地丰富了最优化技术，也为那些用传统优化技术难以处理的组合优化问题提供了切实可行的解决方案。

智能优化方法模拟自然界的生物系统，依赖生物体的自身本能，通过无意识的寻优行为来优化其生存状态。智能优化方法根据所使用智能体的数量可分为基于个体的智能优化方法和基于种群的智能优化方法，其中模拟退火算法等是基于个体的智能优化方法，而遗传算法、蚁群算法和粒子群优化算法等都是基于种群的智能优化方法。基于种群的智能优化方法的主要特点可概括为^[2]：

• 是一类不确定的优化算法。不确定性体现了自然界生物的生理机制，并且在求解某些问题时优于确定性算法。
• 是一类概率型的全局搜索算法。随着搜索过程的不断推进，找到优质解的概率大于得到劣质解的概率，能以更大概率求得全局最优解。
• 在优化过程中不依赖于优化问题本身的某些数学特性。如目标函数和约束条件的精确数学描述、目标函数的连续性及可导性等。
• 是一类基于多个智能体的算法。各个智能体之间通过相互协作来更好适应环境，以获取所需性能。
• 具有潜在的并行性。搜索过程同时从多点出发，分布式并行模式极大提高了整个算法的运行效率、鲁棒性和反应能力。
• 具有学习能力。在复杂的、不确定的、时变的环境中，能通过自我学习不断提高个体的适应性。

智能优化方法的现有研究主要集中在三个方面^[1]：对现有智能优化方法进行改进并广泛应用，对其理论进行深入研究；开发新的智能优化工具，拓宽其应用领域，并对其寻求理论基础；各种现有智能优化方法的混合。算法性能（精度和速度）的提高是永无止境的，提高现有智能优化方法处理各种工程问题的性能，并对其进行理论研究已成为当前智能优化领域研究的首要任务和热点问题。

1.1.2　动机

根据搜索方法的发展历程（图1.1），可将现有的搜索方法分为以下三类：古典搜索方法、启发式搜索方法和智能优化方法。

• 古典搜索方法。如步长加速法、旋转方向法、单纯型调优法、方向加速法、枚举法和随机搜索方法等。古典搜索方法仅通过比较目标函数值的大小来移动迭代点，它的搜索策略像是“跟着感觉走”。
• 启发式搜索方法。如共轭梯度法、牛顿型方法和变尺度法等。启发式搜索方法有一套严密的理论体系，通过比较目标函数的梯度值来移动迭代点，可看作是“梯度信息启发下的简单智能搜索”。启发式搜索方法将优化问题的梯度信息引入优化过程中，采用目标函数的梯度值来引导优化方法的寻优过程。相对于古典搜索方法，启发式搜索方法能更快地搜索到优化问题的最优解。

图1.1　搜索方法的发展历程

• 智能优化方法。如模拟退火算法、遗传算法、禁忌搜索、进化规划、进化策略和蚁群算法等。智能优化方法在优化流程上均是一种“邻域搜索”结构。智能优化方法在一定程度上把优化问题的领域知识隐含地加入到算法中。如在遗传算法中，通过选择、交叉和变异操作，将优化问题的较优个体的一些部件特征（component characteristic）逐步地保留下来；在蚁群算法中，通过信息素将优化问题较优个体的一些部件特征逐步地保留下来。与启发式搜索方法相比，智能优化方法能较好地解决大规模复杂系统中出现的组合爆炸问题，不仅具有通用、稳健、简单、便于并行处理等优点，而且有望成为数值计算与语义表达、形象思维等高级智能行为之间相互联系的桥梁。智能优化方法的研究在一些采用传统方法难以解决或无法解决的应用领域中取得了重大突破。

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

本书认为在求解复杂优化问题时，可从优化过程中直接挖掘一些待求解问题的相关知识，然后应用知识来指导后续优化过程。本文更多地关注一些显性知识，即能明确表达的知识。显性知识可采用计算机语言来表示和存储，其他模型可通过给定方式对这些知识进行更新和应用。鉴于此，本书提出一类学习型智能优化方法：采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型为基础，同时突出知识模型的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。

学习型智能优化方法研究的难点主要表现在以下方面：

• 学习型智能优化方法的基本框架。构建一种比较通用的优化框架，将智能优化方法和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。
• 知识的定义。构建用于实现学习型智能优化方法的若干典型知识，这些典型知识可辅助学习型智能优化方法高效地求解复杂优化问题。
• 设计并实现若干种比较典型的学习型智能优化方法。针对一些连续优化问题、组合优化问题或实际工程问题，设计并实现若干种比较典型的学习型智能优化方法，这些方法稍加修改就可推广到其他复杂优化问题的求解中。