第1章

引言

“优化问题无所不在，优化理论无所不能”，或许人们不会觉得这句话过于夸张或者引起非议，现实世界中的很多问题都可以被抽象为优化问题，都可以设计相应的优化方法得到相应的答案。每个人每天都会遇到各种优化问题，如排课系统、电梯调度、公交车调度和路径规划等，我们都在享受优化技术带来的便利。优化技术应该是类似于人工智能技术那样接地气、妇孺皆知。

无论从理论研究的角度还是从实际应用的角度来看，组合优化问题的是非常具有代表性的优化问题，在工业、航空、航天、电力系统等各个领域都发挥着重要的作用，如流水线调度问题、无人机任务规划与协同问题、对地观测卫星任务规划问题、智能电网能源调度问题等。研究这些问题的解空间特性，从而设计更为适用和实用的求解方法是各个领域都迫切关注的研究热点，也是促进相关领域发展的一项支撑性技术。

适应度地形理论研究优化问题的解空间特征，为了解现实问题的特性提供了一种技术途径，近年来得到了学者们的广泛关注。本章从组合优化问题出发，引出适应度地形的基本定义，为后续章节提供基础。

1.1

优化问题

一般来说，优化问题P定义为

P∈（S，Ω，f）

式中，S是定义在决策变量X

i

（i=1，2，…，n）的有限集合基础上的搜索空间；Ω是决策变量的约束条件集；f是需要进行优化的目标空间。

决策变量（Decision Variable）、约束条件（Constraints）和目标函数（Objective func-tion）是优化问题的三要素。优化问题的一般描述是要选择一组参数（变量），在满足相关限制条件（约束）下，使设计指标（目标）达到最优值，一般采用数学规划的形式加以描述。

X=[x

1

,x

2

,…，x

n

]

T

s.t.g

i

(X)≤0(i=0,1…,n)

h

j

(X)=0(i=0,1,…,n)

maxf(X)or min f(X)

最优化模型分类方法有很多，可按变量、约束条件、目标函数个数、目标函数和约束条件的是否线性、是否依赖时间等进行分类，如连续优化问题和组合优化问题、无约束优化问题和约束优化问题、线性优化问题和非线性优化问题、单目标优化问题和多目标优化问题，静态规划问题和动态规划问题等。本书主要探讨组合优化问题，其决策变量在解空间中具有离散状态，约束条件一般情况下也具有离散状态。

1.2

组合优化问题

1.2.1

组合优化问题的定义

组合优化问题是最优化问题的一类。最优化问题可以自然地分成两类：一类是连续变量的问题，另一类是离散变量的问题。其中，具有离散变量的问题称为组合问题。在连续变量的问题里，一般是求一组实数或者一个函数；在组合问题里，是从一个无限集或者可数无限集里寻找一个较优对象，如一个整数，一个集合，一个排列或者一个图。一般地，这两类问题具有不同的特点与不同的求解方式。

组合优化问题通常可描述为：Ω={s

1

，s

2

，…，s

n

}为所有状态构成的解空间，C（s

i

）为状态s

i

对应的目标函数值，要求寻找最优解s

∗

，使得

∀s

i

∈Ω，C（s

∗

）=minC（s

i

）

组合优化往往涉及排序、分类、筛选等问题。

min f（x）

s.t.x∈S，S∈X（S，X：拥有有限个或可数无限个解的离散集合）

式中，f（x）是目标函数；x是问题的解；X是解空间；S是可行解空间（可行域），X包含S。

如果S是有限集合，从理论上讲，只要遍历所有的组合，就能找到最优解，然而随着问题规模的增大，S中解的个数会迅速增大，实际上要想遍历所有的解，几乎是不可能的。

所谓组合优化，是指在离散的、有限的数学结构上，寻找一个（或一组）满足给定约束条件并使其目标函数值达到最小的解，即在离散状态下求极值的问题。把某种离散对象按某个确定的约束条件进行安排，当已知合乎这种约束条件的特定安排存在时，寻求这种特定安排在某个优化准则下的极大解或极小解。组合优化的理论基础包括线性规划、非线性规划、整数规划、动态规划、网络分析等，组合优化技术提供了一个快速寻求极大解或极小解的方法。