第14章　视觉认知优化算法

14.1　视觉认知优化算法的提出

视觉认知优化算法（Visual Cognitive Optimization Algorithm，VCOA）是2010年由孙雅芳等人提出的一种基于视觉认知的全局优化算法^[50]，[51]，本书简称为视觉认知优化算法。该算法是针对瞭望算法在解决全局优化问题时，会产生漏点现象或只是达到局部最优的问题，从而提出的基于视觉认知的全局优化算法，以确保在产生瞭望点时，不存在漏点的现象，且用数学的方法证明了由该算法产生的序列依概率收敛于全局最小值。

14.2　视觉认知优化算法的原理

视觉是一种极为复杂和重要的感觉，人所感受的外界信息80%以上来自视觉。视觉为多功能名称，常说的视力仅为其功能之一，广义的视功能应由视觉-感觉、量子吸收、特定的空间-时间构图及心理神经一致性4个连续阶段组成。视网膜中的特殊感受器便是视功能的主要物质基础。目前视觉科学已经成为一门独立的科学。

认知科学是当代世界科学的前沿学科，原因在于认知科学是探究人脑的尖端学科。认知科学定义为智能实体与其环境相互作用的原理的研究，向两个方向展开，是研究人类的认知和智力的本质和规律的科学。

视觉认知方法是视觉科学与认知科学的交叉结合，从视觉的角度收集信息，用认知科学来分析和鉴别信息。人们获得的信息是人类通过不同的手段获得的初始资料。所谓结构数据，是指能够用数据或统一的结构加以表示。非结构化数据是指无法用数据或统一的结构加以表示。通过视网膜获得的原始信息是非结构化的，通过大脑的分析，即可以获得现实世界的真实内容。大脑还有自动优化的功能，比如在已有的经验分析下，人们能够很快分辨出同种两个物体的大小。现在所面临的巨大挑战是如何使得计算机能够像人那样看懂图、能够从复杂环境中辨识目标及能够准确感知环境，换句话说，就是怎样完成由非结构化到结构化的信息编码。

神经生理学和认知科学最好的结合方法之一，就是视觉认知方法。用视觉认知方法来解决非结构化信息是一个非常有效的手段。信息处理就是一个优化的过程，从纷杂的非结构化信息中整理出想要的部分，视觉认知方法的引入能很好地降低这个过程的计算量，使信息处理的时间能够缩短。

目前研究视觉认知是从两个方面展开的：一方面研究视觉系统的具体机制；另一方面研究视觉环境及视觉系统对视觉环境的总体反应。视觉认知研究的最新成果是“脑视觉”。近年来，美国脑神经科学者和心理学者发现神经细胞会根据人们所看到东西的线的倾斜度，做出不同的反应。日本的研究者发现：根据线的倾斜被分解后的视觉信息到达视觉野，这些信号群被传递到一个个图形构造中。神秘的脑宇宙中壮大的网络开始运转，这些图形所具有的特异功能再次组合，从而认识全体的图像。视觉认知研究还发现两个重要的现象：一是，画不同的图像时，人的“一次视觉野”的位置不同；二是，看不同色彩、形状及静态或动态的事物时，大脑中相应区域中神经细胞的反应有所不同。

14.3　视觉认知优化算法的描述与步骤

视觉认知优化算法是为了避免瞭望算法存在漏点的现象而提出的一种全局优化算法。

考虑如下形式的全局优化问题

假设：（1）f：Rⁿ→R连续有下界。（2）存在一个实数c₀，使得水平集非空有界。

1. 视觉认知优化算法的步骤

（1）取ε＞0充分小，样本点数N∈Z⁺，令k=0，c₀=f（x₀）。

（2）取样，令k=k+1，产生样本点集，其中g_k（x）为取样密度函数。

（3）产生瞭望记忆机制

计算函数值，记，将，从小到大排列得到次序瞭望样本集

若为空，转步骤（2）。

（4）计算当前瞭望水平值。

（5）计算。

（6）给出终止条件，如果，循环停止，则c^∗=c_k为近似总极值，否则更新取样密度，转步骤（2）。

2. 取样与更新

在算法中，起始密度选取为g₀（x）=U（D），D∈Rⁿ为足够大的超立方体，其他步骤的取样密度选取以下核密度函数，即令

为了简化计算，利用相对熵方法来更新取样密度函数g_k+1（x），选取的核函数为

其中，x_j为向量x=（x₁，x₂，…，x_n）的第j个分量。

选取这样的核函数给取样和密度函数的更新带来方便，结合式（14.2）与式（14.3），可以得到取样核密度函数为

其中，为第k次重点样本中的第i个样本点的第j个分量。

14.4　算法的收敛性证明

【定理14.1】　设｛c_k｝是由算法产生的序列，存在c使

证明：由算法可知，因此｛c_k｝为单调下降序列。又因为由假设（1）可知c_k有界，则。

【引理14.1】　若c_k→c，（k=1，2，…），且，则，k=1，2，…使得。

证明：当k→∞时，通过上述所构造的取样密度函数g_k（x）所选取重点样本集的方法，可知对∀ε＞0，。即，k=1，2，…，使得。

【定理14.2】　充要条件为：当c_k→c时，对于∀x∈H_c，有f（x）=c。

证明：先证必要性，由已知，H_c=｛x|f（x）≤c｝。所以∀x∈H_c，只能有f（x）=c。

再证充分性，由已知对∀x∈H_c，且c_k→c，有f（x）=c，则∀x∈Rⁿ，有f（x）≥c。采用反正法证明如下。

假设：（1）存在k，使得且f（x₀）＜c。

根据算法，所以，即可知c_k≤f（x₀），又因为c_k→c，再由定理14.1知c≤c_k≤f（x₀）与假设矛盾。

（2），，使得。

由引理14.1可知，k=1，2，…，使得，根据算法，所以，即可知，又因为c_k→c，再由定理14.1可知与假设矛盾。

综上，对∀x∈Rⁿ，有。

【定理14.3】　若c_k→c（k→∞），则当k→∞时，。

证明：由于，i=1，2，…，N′，又有c_k→c（k→∞），所以可得，定理得证。

14.5　视觉认知优化算法的实现举例

对上述算法使用MATLAB编程实现，计算条件：CPU P4-1.0 GHz，256MB RAM，MATLAB 7.0。

【例14.1】　Rosenbroek测试函数：

最优解是［1，1］^T，minF₂（x₁，x₂）=0。

根据视觉认知算法，投点数为N=2000，迭代次数取k=4，得到最优解为［1，1］^T，minF₂（x₁，x₂）=0。

【例14.2】　Easom（ES）测试函数：

ES（x₁，x₂）=-cosx₁cosx₂exp（-（（x₁-π）²+（x₂-π）²））

搜索范围：-100＜x_i＜100，i=1，2。

全局最优解：x^∗=（π，π），ES（x^∗）=-1。

通过视觉认知算法，当N=4000，k=3时，最优解为（3.1423，3.1489）^T，最优值为-0.999 959。

【例14.3】　Sphere Model测试函数：

取n=3最优解x_i=0（i=1，2，3），minF₄（x₁，x₂，x₃）=0，根据视觉认知算法，当N=3000，k=9时，得到最优解（0.0020，0.0019，0.0021）^T，minF₄（x₁，x₂，…，x₈）=0.000 012 02。

14.6　基于视觉认知的可视化算法

受图像处理中图像分割与特征提取思想的启发，与水平值下降算法思想相结合，基于函数局部最大Lipschitz常数与水平值下降距离的关系，文献［52］提出了一种新的求解一维约束全局优化问题的可视化算法。该算法采用先删除区间再加细取点的原则以减少计算量，并通过目标函数可视化处理动态调整目标函数局部最大Lipschitz常数，以提高算法收敛速度。其优点在于对目标函数没有过高要求，不仅适用于求解连续可微的光滑函数，也同样适用于求解非光滑函数。

考虑一维约束全局最优化问题：

其中，f（x）：［a，b］→R，是［a，b］上的多峰函数，x^∗为f（x）在［a，b］上的最优解。

假设：（1）目标函数f（x）有下界，即存在常数M∈R，使得f（x）≥M，∀x∈［a，b］。

（2）目标函数f（x）在［a，b］上是Lipschitz连续，存在L＞0，使得∀x₁，x₂∈［a，b］，有|f（x₁）-f（x₂）|≤L|x₁-x₂|。

为估计目标函数Lipschitz常数，对一类函数给出一种求其Lpschitz常数L的方法如下。

若f（x）在［a，b］上一阶可微，则L=max|f′（x）|，x∈［a，b］；若c点为函数f（x）在［a，b］内唯一不可导点，则L=max｛|f′（x）|，x∈［a，c］；|f′（x）|，x∈［c，b］｝。

可视化算法包括以下两个基本阶段。

阶段1：区域划分及估计函数Lipschitz常数。

将目标函数在给定区域内以较大间隔取点绘制函数粗略曲线，通过对目标函数粗略曲线的观察，将目标函数按照坡度陡缓差异分成不同区域。在不同的区域中分别按照上述方法求解函数Lipschitz常数。

阶段2：区间删除策略（注意，为提高算法收敛速度，算法中L_k指不同区间Lipschitz常数，但l^k为当前全局极小点）。

以区间［α，β］为例，［α，β］⊆［c，b］，函数f（x）在区间［α，β］连续可微。可视化算法的实现步骤如下。

（1）k=1，计算精度为ε＞0，在［α，β］上间隔h_k取值，记此点集为

其中，；，…；；。

（2）计算n^k+1自变量的函数值，设，i=0，1，…，n^k。

（3）记

（4）若h_k≤ε/L_k，算法终止，C^k为近似最优解集合，否则，转步骤（5）。

（5）在中所有相邻点对之间（以h_k为间隔的两个点之间，也就是说，间隔距离为h_k的两点）加细取点，间隔变为h_k+1=h_k/10，令d_k+1=d_k/10。

（6）将加细取点后的所有点组成的集合记为，若，算法终止，C^k为近似最优解集合，否则，k=k+1，转步骤（2）。