2.1 优化研究基础

优化是科学研究、工程技术和经济管理等领域的重要研究工具。它所研究的问题是讨论在众多的方案中寻找最优方案。例如，工程设计中怎样选择设计参数，使设计方案既满足设计要求，又能降低成本；资源分配时怎样分配有限资源，使分配方案既能满足各方面的基本要求，又能获得好的经济效益。在人类活动的各个领域中，诸如此类，不胜枚举。最优化理论和技术是为很多问题的解决提供理论基础和求解方法，它是一门应用广泛、实用性很强的科学。

随着科学技术，尤其是计算机技术的不断发展，以及随着数学理论与方法向各门学科和各个应用领域更广泛、更深入的渗透，最优化理论和技术必将在二十一世纪的信息社会中起越来越重要的作用。为解决最优化问题，人们提出过许多技术和方法，但工业和科学领域大量实际问题的困难程度正在日益增长，这些问题大多是无法在可接受的时间内找到解的问题。鉴于这类优化问题的复杂性、约束性、非线性、多极小和建模困难等特点，寻求一种适合于大规模并行且具有智能特征的优化算法已成为相关学科的一个主要研究目标和方向。

最优化问题涉及的应用领域很广，问题种类与性质繁多。归纳起来，可分为函数优化问题和组合优化问题两大类，其中，函数优化的对象是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态。

2.1.1 函数优化

对许多实际问题进行数学建模后，可将其抽象为一个数值函数的优化问题。由于问题的种类繁多，影响因素复杂，这些数学函数会呈现出多种数学特征。如有些函数是连续的，而有些函数是离散的；有些函数是凸函数，而有些函数不是凸函数；有些函数是单峰值的，而有些函数却是多峰值的。而实际中遇到的函数是这些不同数学特征的组合。因此，寻找高效、通用的函数优化方法是值得研究的问题。

一般函数优化问题可以描述为：

其中，D⊆Rⁿ称为搜索空间，f∶D→R称为目标函数。通常，x=（x₁，x₂，…，x_n）∈Rⁿ，，i=1，2，…，n。

定义2.1 对于函数优化问题，参见式（2-1），设x^*∈D，若∀x∈D，有

则称x^*为该问题的一个全局最优解。

定义2.2 对于函数优化问题，参见式（2-1），设x^*∈D，若存在x^*的邻域，使得当x∈D∩N_ε（x*）时，有

则称x^*为该问题的一个局部最优解。

鉴于许多实际问题存在约束条件，受约束函数的优化问题也一直是优化领域关注的主要对象。由于约束条件增加了寻优难度，所以，许多场合将受约束问题转化为无约束问题来处理，常用的途径有：

（1）把问题的约束在状态的表达形式中体现出来，并设计专门的算子，使状态所表示的解在搜索过程中始终保持可行性。这种方法最直接，但适用领域有限，算子的设计也比较困难。

（2）在编码过程中不考虑约束，而在搜索过程中通过检验解的可行性来决定对解的弃用。这种方法一般只适用于简单的约束问题。

（3）采用惩罚的方法来处理约束越界问题。这种方法比较通用，适当选择惩罚函数的形式可得到较好的结果。比如采用罚函数，可描述为：

传统的优化方法一般要求目标函数连续、可微，根据目标函数的局部展开性质确定下一步的搜索方向，缺乏简单性和通用性。在问题规模比较大时，需要的搜索时间及空间也急剧扩大。近年来，进化计算等基于自然法则的随机搜索算法，在优化领域取得的成功引起了人们的普遍关注，其原因在于它们摆脱了对函数导数的依赖性，具有自适应、全局寻优及内在并行的特点。

2.1.2 组合优化

组合优化是指在离散的、有限的数学结构上，寻找满足给定约束条件且目标函数值最大或最小的解。在管理科学、分子生物学及图像处理、VLSI设计等领域中，存在着大量组合优化问题，典型的组合优化问题有旅行商问题（Traveling Salesman Problem，TSP），许多具体问题可以归结为该问题，而且它已经成为评测算法效率的标杆问题；0/1背包问题（Knapsack Problem）是另一个组合优化问题；而将0/1背包问题与TSP问题组合起来则是一个更复杂的组合优化问题：VRP（Vehicle Routing Problem）。除此之外，还有加工调度问题（Scheduling Problem，如Flow-shop，Job-shop）、装箱问题（Bin Packing Problem）、图着色问题（Graph Coloring Problem）和聚类问题（Clustering Problem）等，这些问题至今没有找到有效的多项式时间算法。

组合优化问题一般可以描述为：

其中，f（i）为目标函数，g（i）为约束函数，i为决策变量，D一般为有限集或可数无限集。集合F={i|i∈D，g（i）≥0}称为可行域。

定义2.3 对于组合优化问题，见式（2-5），D上的一个映射

称为一个领域映射，其中，ρ（D）表示D的所有子集组成的集合，N（S）称为S的领域。

定义2.4 若i^*∈F满足

则称i^*为该问题的一个全局最优解。

定义2.5 若i^*∈F满足∀i∈N（i^*）∩F，且

则称i^*为该问题的一个局部最优解。

大规模的组合优化问题是NP-hard问题，采用传统优化方法难以取得满意解，其中主要原因之一就是所谓的组合爆炸。例如，聚类问题的可能划分方式有kⁿ/k！个，Job-shop的可能排列方式有（n！）^m个，基于置换排列描述的n城市TSP问题有n！种可行排列，即便对无方向性和循环性的平面问题仍有（n-1）！/2种不同排列，显然，状态数量随问题规模增长呈超指数增长。若计算机每秒能处理1亿种排列，则穷举20个城市问题的20！种排列约需几百年，如此巨大的计算量是人们无法承受的，更不用谈更大规模问题的求解。因此，解决这些问题的关键在于寻求有效的优化算法，也正是这些问题的代表性和复杂性激起了人们使用智能算法对组合优化理论进行研究的热情。虽然一种算法能不能找到优化解很重要，但花费多少时间、消耗多少资源、能得到何种准确程度的优化解，也是算法面临的更实际的问题。因此，针对组合优化，人们也构造了大量测试算法的Benchmark寻优问题，来测试算法的效率、精度等性能。