第13章　瞭望算法

13.1　瞭望算法的提出

瞭望算法（Outlook Algorithm，OA）是2006年由蔡延光、钱积新和孙优贤提出的一种求解全局优化问题的智能优化算法^[49]。由于它模拟了人类的视觉智能和根据视觉信息分析问题的推理智能，因此它是一种智能优化算法。该算法本质上是一种基于监督的并行算法。为了加快瞭望算法的收敛速度，引入瞭望算法的3层次记忆机制：基点记忆、瞭望点记忆、局部寻优记忆。在瞭望管理机制的协调下，把瞭望点产生策略和局部寻优算法有机地结合起来，能在较短的时间内求解全局优化问题。

大量的测试表明，瞭望算法具有较高的收敛率和较强的获得问题全部解的能力，对初始点几乎没有依赖，参数选择简单，能够保证在迭代过程中迭代点的质量逐步变好。

13.2　瞭望算法的基本原理

人们很早以前就有通过瞭望确定群山最高点的常识。为了寻找群山的最高点，人们一般在群山中任意选取某座山的一个点作为出发点，进行局部爬高（即向该座山的最高点攀登），达到该座山的最高点（相对于群山而言是局部最高点）后，此局部最高点作为基点进行瞭望，寻找比基点“更高的点”。以此“更高的点”所在的山的某个点作为出发点，开始下一轮的局部爬高……直至找到群山的最高点。

如何通过瞭望获得比基点“更高的点”呢？众所周知，站得越高，看得越远；观测目标离得越近，看得越清楚，可对它的局部进行精细的观察；观测目标离得越远，分辨的尺寸越大，能对其进行粗略的观察。选择基点的若干个瞭望点作为“更高的点”的候选点：在基点附近可稠密地选取一些瞭望点，在离基点远的地方瞭望点可取得稀疏一些。人们站在基点对瞭望点进行目测，瞭望点在水平视线的上方，则认为瞭望点高于基点（如果忽略观测者自身的高度），“更高的点”就是该瞭望点。

瞭望算法是利用瞭望技术确定群山最高点的常识而设计的一种求解全局优化问题的智能算法。瞭望算法由瞭望管理机制（主要负责算法进程控制与协调）、瞭望点产生策略（负责产生瞭望点）、局部问题构造与求解机制3部分组成，其求解全局优化问题的基本过程如下。

（1）由瞭望管理机制确定基点。

（2）由瞭望点产生策略产生基点的瞭望点。

（3）由瞭望管理机制按照一定的标准选择瞭望点。

（4）构造所有被选定的瞭望点的局部问题并用局部寻优算法求解这些局部问题。

（5）在获得所有被选定的局部问题的解后，瞭望管理机制确定下一个基点，进行新一轮的迭代，直至算法终止条件出现，当前最好可行解作为问题的解。

13.3　瞭望算法的数学描述

1. 全局优化问题的描述

考虑全局优化问题

记G（X）=（g₁（X），g₂（X），…，g_m（X））^T。

为了表述方便，定义以下几个基本概念。

【定义13.1】　对于全局优化问题，设R′⊆R，X^O∈R′：

（1）把minF（x）（X∈R）称为X^O处的局部优化问题，在不引起混淆时简称局部问题，求局部问题的解，称为局部寻优。

（2）如果在R′上F（x）是（下）单峰函数，则称R′为F（x）的（下）单峰区域，在不引起混淆时简称单峰区域。

【定义13.2】　对于全局优化问题：

（1）瞭望基准点（简称基点）是可行域R中的一个点。

（2）设X^B∈R是基点，基于基点X^B的瞭望点是可行域R中的一个点，在不引起混淆时把基于基点的瞭望点简称基点的瞭望点或瞭望点；按照某种标准（如欧氏距离、海明距离）把X^B的全部瞭望点分类，称X^B的第k类瞭望点为X^B的第k阶瞭望点。

【定义13.3】　局部寻优算法是一个基于迭代的优化问题的求解方法，它具有固有特性：寻优过程所产生的迭代点必须在初始点所在的单峰区域内。

2. 瞭望点产生策略

根据在基点附近可稠密地选取一些瞭望点，而在离基点远的地方瞭望点可取得稀疏一些的思想，可以设计多种瞭望点产生策略。

设为基点，下面讨论在X^B处产生第k阶瞭望点的方体瞭望点产生策略和球面瞭望点产生策略。

1）方体瞭望点产生策略

方体瞭望点产生策略是在以X^B为中心的棱长为2r_k的n维立方体表面和可行域R的交集中选取X^B的第k（k=0，1，2，…）阶瞭望点，其中r_k=H（h，k，Xⁿ，F，G），它是h、k、X^B、F、G的函数，h（＞0）为预先设定的一个常数（称为基本瞭望步长），且r₀=0＜r₁＜r₂＜…；当k=0时，X^B是唯一的瞭望点。

以n=2为例，说明由方体瞭望点产生策略所产生的第k阶瞭望点的几何意义。如图13.1所示，第k阶瞭望点取自于

关于r_k的构造主要考虑r_k是h、k函数的情形，可以用等距法、算术增距法、Fibonacci增距法、几何增距法确定r_k（具体方法参见文献［49］）。

2）球面瞭望点产生策略

球面瞭望点产生策略是在n维球面

和可行域R的交集中选取X^B的第k（k=0，1，2，…）阶瞭望点，其中r_k与方体瞭望点产生策略的意义及确定方法完全相同。因为r₀=0＜r₁＜r₂＜…，所以在球面瞭望点产生策略下，同阶的瞭望点与X^B的距离相等，较高阶瞭望点距离X^B较远。

以n=2为例，说明由球面瞭望点产生策略所产生的第k阶瞭望点的几何意义。如果希望至多取q个第k阶瞭望点，则不妨在X^B出发的q条射线（q条射线一般是均匀分布的）与圆周的交点中选取可行点作为瞭望点，如图13.2所示，这里q=q（h，k，X^B，F，G）。类似于算法2（见13.4节），可获得球面瞭望点产生策略产生瞭望点的算法。

3. 局部问题的构造与局部寻优算法

瞭望算法的提出也是为了求解目标函数是多峰函数的全局优化问题，首先把R划分为数量尽量少的两两互不相交的单峰区域（或把R划分为两两互不相交的单峰区域，并使每个单峰区域尽量大），每个单峰区域对应一个局部问题，这样把全局优化问题分解为一系列目标函数是单峰函数的子问题（即局部问题）；其次用目标函数是单峰函数的优化问题的求解方法获得局部问题的解；最后通过简单地比较各局部问题的解就可获得全局优化问题的解。但是，以上设想直接实现起来非常困难。

瞭望算法充分地利用局部寻优算法的固有特性构造并求解局部问题。根据局部寻优算法的固有特性，显然只要给出局部寻优的初始点（为了节约计算时间，通常把瞭望点作为初始点），就可以获得局部问题的解，只要给出局部寻优的初始点，局部问题也就随之确定了。

局部寻优算法可以通过对求解目标函数是单峰函数的优化问题的方法（如一维无约束优化的黄金分割法、成功-失败法、牛顿法、多维无约束优化的拟牛顿法、共轭梯度法、DFP法，以及有约束优化问题的罚函数法、SWIFT法、可行方向法、线性逼近法等）做一些必要的改造得到，使其最大限度地满足局部寻优算法的固有特性。按照这个思路，可以对以上提到的一些算法进行改造。例如，局部牛顿法是在牛顿法的基础上增加了对边界和拐点等的特别处理而获得的局部寻优算法，局部DFP法是在DFP法的基础上增加了对边界等的特别处理而获得的局部寻优算法（限于篇幅，改造过程从略）。

4. 瞭望算法的记忆机制

为了避免在搜索过的区域进行重复搜索，提高算法的收敛速度，引入瞭望算法的3层次记忆机制：第一层的基点记忆；第二层的瞭望点记忆；第三层的局部寻优记忆。

1）基点记忆

基点记忆（MB）记忆全部基点。初始的MB=∅；如果X^B为基点，则MB=MB∪｛X^B｝。如果实行基点记忆，则将算法1（见13.4节）的片段3所对应的条件改为：如果F（LocalX^min）≤F（X^min）且LocalX^min∉MB。这样，可以避免在迭代过程中重复地把一个点作为基点。

2）瞭望点记忆

瞭望点记忆（MO）记忆全体构造过局部问题并实施过局部寻优的瞭望点。初始的MO=∅；如果X^O是某个基点的瞭望点，且求解过X^O处的局部问题，则MO=MO∪｛X^O｝。如果实施瞭望点记忆，则将算法1（见13.4节）的片段1所对应的条件改为：如果F（X^O）≤F（X^B）且不存在X′∈MO使‖X′-X^O‖≤ε（ε≥0为预设的精度）。这样，对任意点及其附近的点至多只能构造一次局部问题。

3）局部寻优记忆

局部寻优记忆（ML）记忆局部寻优过程所经历的部分迭代点。初始的ML=∅；如果X^L是局部寻优过程所获得的一个迭代点，且不存在X′∈ML满足‖X′-X^L‖≤ε（ε≥0为预设的精度），则ML=ML∪｛X^L｝；否则终止此局部寻优，因为如果F（X）是平滑的、不具有突变性，若继续进行局部寻优，则所得到的迭代点的质量一般不会比以前有实质性更好。此外，当有局部寻优记忆时，算法1的片段1所对应的条件也可改为：F（X^O）≤F（X^B）且不存在X′∈ML使‖X′-X^O‖≤ε（ε≥0为预设的精度）。

MB、MO、ML体现了瞭望算法3个层次的记忆，显然有MB⊆ML、MO⊆ML，根据需要选择其中一个或多个记忆。为了实现对MB、MO、ML中的元素进行快速查找（如二分查找），在迭代过程中应该同时对它们的元素进行排序（如二分插入排序）。

13.4　求解全局优化问题的瞭望算法的实现

算法1是瞭望算法的一种实现形式，用于求解全局优化问题，其核心包括以下3个部分。

（1）外层循环：控制瞭望算法的进程、选择基点X^B。当基点数超过预先设定的最大值或允许瞭望标志等于False时，算法终止运行，输出最优解。

（2）第二层循环：通过调用算法2，产生基于基点X^B的各阶瞭望点。

（3）内层循环：选择瞭望点进行局部寻优、设置允许瞭望标志的值。

算法1　求解全局优化问题（式（13.1））的瞭望算法（C语言编程）。

算法2　用方体瞭望点产生策略产生瞭望点（C语言编程）。