全局最优解算法

① 请大神解释一下在医学图像配准中，什么叫做局部优化算法，什么叫做全局优化算法

算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
一、遗传算法的目的
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
bi∈{0,1}L (3-84)
给定目标函数f，有f(bi)，并且
0<f(bi)<∞
同时
f(bi)≠f(bi+1)
求满足下式
max{f(bi)|bi∈{0,1}L} (3-85)
的bi。
很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
二、遗传算法的基本原理
长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
1．选择(Selection)
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproction)。
2．交叉(Crossover)
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
3．变异(Mutation)
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
遗传算法的原理可以简要给出如下：
choose an intial population
determine the fitness of each indivial
perform selection
repeat
perform crossover
perform mutation
determine the fitness of each indivial
perform selection
until some stopping criterion applies
这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
三、遗传算法的步骤和意义
1．初始化
选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
2．选择
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
给出目标函数f，则f(bi)称为个体bi的适应度。以

(3-86)
为选中bi为下一代个体的次数。
显然．从式(3—86)可知：
(1)适应度较高的个体，繁殖下一代的数目较多。
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
例如有个体
S1=100101
S2=010111
选择它们的左边3位进行交叉操作，则有
S1=010101
S2=100111
一般而言，交叉幌宰P。取值为0.25—0.75。
4．变异
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
例如有个体S＝101011。
对其的第1，4位置的基因进行变异，则有
S'=001111
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
5．全局最优收敛(Convergence to the global optimum)
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
图3—7中表示了遗传算法的执行过程。

② 线性规划(LP)基本概念和搜索算法

可以用一个符号描述一系列类似的数量值

一个方程，如果他是关于决策变量的常熟加权求和形式，则该方程式 线性方程(liner) ，佛则该方程为 非线性方程(non-linear)

目标函数 以及约束方程 中均为关于决策变量的线性方程，则该优化模型为 线性规划(linear program, LP) ，其中目标函数可以为满足约束的任意整数或者分数

目标函数 以及约束方程 中存在关于决策变量的线性方程，则该优化模型为 非线性规划(nonlinear program, LP) ，其中目标函数可以为满足约束的任意整数或者分数

一个优化模型，如果他的决策变量中存在离散变量，则该优化模型位 整数规划(integer program, IP) ，如果整数规划的所有决策变量均为离散变量，则该整数规划为 纯整数规划(pure integer program) ；否则为 混合整数规划(mixed integer program) 。

搜索算法(improving search) 通过检查邻域来寻找比当前更好地解，若有改进则替换当前解，继续迭代，直到邻域中没有更好的解为止。搜索算法又称为 局部改进(local improvement) ， 爬山算法(hillclimbing) ， 局部搜索(local search) 或 邻域搜索(neighborhood search)

倘若一组可行解周围足够小的的邻域内没有优于该解的可行点，则称为 局部最优解(local optimum) ，最小化(最大化)问题存在 局部最小(最大)解 。

如果在全局范围内不存在目标值优于某可行解的其他可行点，则称为 全局最优解(global optimum) ，最小化(最大化)问题存在 全局最小(最大)解

搜索算法沿 由当前点 向下一个搜索点 移动，其中 是当前点 处的 搜索方向(move direction) ， 是沿该方向前进的 步长 ， 。

对于所有足够小的 都有 ,则称 是当前解的一个 改进方向(improving direction) ,如果满足所有约束条件，则为 可行改进方向 。

如果优化模型的目标函数 是光滑的(所有决策变量都是可微的)，那么，当 是一个n维向量的函数，当它有一个一阶片倒数，这些导数组成的n维向量称为 梯度

导数(derivative) ，描述函数随参数的变化率，可以看做斜率。 偏导数(partial derivative) ，是保持其他变量恒定时，关于其中一个变量的导数

对于最大化目标函数 ,若 ，搜索方向 是 处的可改进方向，若 ，搜索方向 不是 处的可改进方向。

对于最小化目标函数 ,若 ，搜索方向 是 处的可改进方向，若 ，搜索方向 不是 处的可改进方向。

当目标函数梯度 ，是最大化目标 的一个改进方向， 是最小化目标函数 的一个改进方向

如果可行域内任意两点的连线都在可行域内，则称该可行域为 凸集 。

离散的可行集总是非凸集

若优化模型的可行集是凸集，那么对任意可行解始终存在指向另一个解的可行方向，意味着，只要存在最优解，可能性不会阻碍局部最优解发展为全局最优解。

线性约束的可行集又称为多面体集。

如果优化模型的所有约束都是线性的，那么该模型的可行域是凸集

两阶段法

大M法

③ 混沌优化算法可以求解全局最优解吗

非线性最优化问题的一种混合解法

摘 要：把BFGS方法与混沌优化方法相结合，基于混沌变量提出一种求解具有变量边界约束非线性最优化问题的混合优化方法。混合算法兼顾了混沌优化全局搜索能力强和BFGS方法收敛速度快的优点，成为一种求解非凸优化问题全局最优的有效方法。算例表明，当混沌搜索的次数达到一定数量时，混合优化方法可以保证算法收敛到全局最优解，且计算效率比混沌优化方法有很大提高。

关键词：混合法；BFGS方法；混沌优化方法；全局最优

1 引言
在系统工程、控制工程、统计学、反问题优化求解等领域中，很多问题是具有非凸性的。对此普通的优化技术只能求出局部最优解，因为这些确定性算法总是解得最近的一个极值点[1]，只有能够给出很好的初始点才有可能得出所需要的全局最优解。为此，实际应用中通过在多个初始点上使用传统数值优化方法来求取全局解的方法仍然被人们所采用，但是这种处理方法求得全局解的概率不高，可靠性低，建立尽可能大概率的求解全局解算法仍然是一个重要问题。近年来基于梯度法的全局最优化方法已经有所研究[2]，基于随机搜索技术的遗传算法和模拟退火算法等在全局优化问题中的应用也得到越来越大的重视[3-4]。本文则基于混沌优化和BFGS方法，提出一种求解具有简单界约束最优化问题(1)的混合算法。
混沌是存在于非线性系统中的一种较为普遍的现象。混沌运动宏观上无序无律，具有内随机性、非周期性和局部不稳定性，微观上有序有律，并不是完全的随机运动，具有无穷嵌套的自相似几何结构、存在普适性规律，并不是杂乱无章的。利用混沌变量的随机性、遍历性和规律性特点可以进行优化搜索[5]，且混沌优化方法容易跳出局部最优点。但是某些状态需要很长时间才能达到，如果最优值在这些状态时，计算时间势必很长[5]。可以说混沌优化具有全局搜索能力，其局部搜索能力稍显不足，文[5]采用二次载波技术，文[6]考虑逐渐缩小寻优变量的搜索空间都是为了弥补这一弱点。而本文则采用混沌搜索与BFGS方法进行优化求解，一方面采用混沌搜索帮助BFGS方法跳出局部最优，另一方面利用BFGS增强解附近的超线性收敛速度和搜索能力，以提高搜索最优的效率。
2 混沌－BFGS混合优化方法
2.1 BFGS方法
作为求解无约束最优化问题的拟牛顿方法类最有代表性的算法之一，BFGS方法处理凸非线性规划问题，以其完善的数学理论基础、采用不精确线性搜索时的超线性收敛性和处理实际问题有效性，受到人们的重视[7-9]。拟牛顿方法使用了二阶导数信息，但是并不直接计算函数的Hesse矩阵，而是采用一阶梯度信息来构造一系列的正定矩阵来逼近Hesse矩阵。BFGS方法求解无约束优化问题min()的主要步骤如下：
(1) 给变量赋初值x0，变量维数n和BFGS方法收敛精度ε，令B0=I（单位阵），k=0，计算在点x0的梯度g0。
(2) 取sk=-Bk-1gk，沿sk作一维搜索，确定最优步长αk，，得新点xk+1=xk+αksk，计算xk+1点的梯度gk+1。
(3) 若||gk+1||≤ε，则令，，BFGS搜索结束，转步骤3；否则执行(4)。
(4) 计算Bk+1：
(2)
(3)
(5) k=k+1，转(2)。
2.2 混沌优化方法
利用混沌搜索求解问题(1)时，先建立待求变量与混沌变量的一一对应关系，本文采用。然后,由Logistic映射式(4)产生个轨迹不同的混沌变量（）进行优化搜索，式(4)中=4。已经证明，=4是“单片”混沌，在[0,1]之间历遍。
(4)
(1)给定最大混沌变量运动次数M；给赋初值，计算和；置，。
(2) 。
(3) 。
(4) 若k<M，
若，令，；
若，和保持不变；
然后令k=k+1，，转(2)。
若k>M，则，，混沌搜索结束。
2.3 混合优化方法
混沌方法和BFGS方法混合求解连续对象的全局极小值优化问题(1)的步骤如下：
step1 设置混沌搜索的最大次数M，迭代步数iter=0，变量赋初值x0，。
step2 以为始点BFGS搜索，得当前BFGS方法最优解及=。
step3 若，取=；若，取；若，取，是相对于,较小的数。
step 4 以为始点进行混沌搜索M次，得混沌搜索后的最优解及=。
step5 若<，iter=iter+1，，转step2；否则执行step6。
step6 改变混沌搜索轨迹，再次进行混沌搜索，即给加微小扰动，执行step 4，得搜索结果和。若<，iter=iter+1，，转step2；否则计算结束，输出、。
对全局极大值问题，max ，可以转化为求解全局极小问题min 。
混合算法中混沌搜索的作用是大范围宏观搜索，使得算法具有全局寻优性能。而BFGS搜索的作用是局部地、细致地进行优化搜索，处理的是小范围搜索问题和搜索加速问题。
3 算例

图 1 函数-特性示意图 图 2 函数特性示意图
采用如下两个非常复杂的、常用于测试遗传算法性能的函数测试本文算法：

函数称为Camel 函数，该函数有6个局部极小点(1.607105, 0.568651)、(-1.607105, -0.568651)、(1.703607, -0.796084)、(-1.703607, 0.796084)、(-0.0898,0.7126)和(0.0898,-0.7126)，其中(-0.0898,0.7126)和(0.0898,-0.7126)为两个全局最小点，最小值为-1.031628。函数称为 Schaffer's函数，该函数有无数个极大值，其中只有（0，0）为全局最大点，最大值为1。此函数的最大峰值周围有一圈脊，它们的取值均为0.990283，因此很容易停留在此局部极大点。文献[10]采用该函数对该文提出的基于移动和人工选择的改进遗传算法（GAMAS）其性能进行了考察，运行50次，40％的情况下该函数的唯一全局最优点能够找到。而采用本文混合算法，由计算机内部随机函数自动随机生产100个不同的初始点，由这些初始点出发，一般混合算法迭代2－4次即能够收敛。M取不同数值时对函数、的计算结果分别如表1和表2所示，表中计算时间是指在奔腾133微机上计算时间。
由表2可见，当M=1500时，本文方法搜索到最优解的概率即达到40％，而此时计算量比文献[10]小。同样由混合算法的100个起始点，采用文献[5]的算法对函数优化计算100次，以作为收敛标准，混沌搜索50000次，计算结果为67次搜索到最优解，概率为67%，平均计算时间为1.2369s。而即使保证混合算法100次全收敛到最优解所花费的平均计算时间也只为0.2142s（表1），可见混合算法优于文献[5]的方法。
表1 M取不同数值时函数的计算结果
_____________________________________________________________________
M 搜索到全局最优点的次数 搜索到最优的概率 平均计算时间
(-0.0898,0.7126) (0.0898,-0.7126)
_____________________________________________________________________________________________
1000 44 39 83% 0.1214s
3000 53 45 98% 0.1955s
5000 53 47 100% 0.2142s
________________________________________________________________________________________________

表2 M取不同数值时函数的计算结果
___________________________________________________________
M 搜索到全局最优点的次数 搜索到最优的概率 平均计算时间
____________________________________________________________________________________
1500 40 40% 0.1406s
5000 73 73% 0.2505s
10000 88 88% 0.4197s
50000 100 100% 1.6856s
____________________________________________________________________________________

4 计算结果分析
由表1和表2可见，混合算法全局寻优能力随M的增加而增大，当M达到某一足够大的数值Mu后，搜索到全局最优的概率可以达到100％。
从理论上说，Mu趋向无穷大时，才能使混沌变量遍历所有状态，才能真正以概率1搜索到最优点。但是，本文混沌运动M次的作用是帮助BFGS方法跳出局部最优点，达到比当前局部最优函数值更小的另一局部最优附近的某一点处，并不是要混沌变量遍历所有状态。由混沌运动遍历特性可知，对于某一具体问题，Mu达到某一具体有限数值时，混沌变量的遍历性可以得到较好模拟，这一点是可以满足的，实际算例也证实了这一点。
由于函数性态、复杂性不同，对于不同函数，如这里的测试函数、，数值Mu的大小是有差别的。对于同一函数，搜索区间增大，在相同混沌运动次数下，即使始点相同，总体而言会降低其搜索到全局最优的概率,要保证算法仍然以概率1收敛到全局最优，必然引起Mu 增大。跟踪计算中间结果证实，当M足够大时，混合算法的确具有跳出局部最优点，继续向全局最优进行搜索的能力；并且混合算法的计算时间主要花费在为使混合算法具有全局搜索能力而进行混沌搜索上。
5 结语
利用混沌变量的运动特点进行优化，具有非常强的跳出局部最优解的能力，该方法与BFGS方法结合使用，在可以接受的计算量下能够计算得到问题的最优解。实际上，混沌优化可以和一般的下降类算法结合使用，并非局限于本文采用的BFGS方法。采用的Logistic映射产生混沌变量序列，只是产生混沌变量的有效方式之一。
混沌运动与随机运动是不同的。混沌是确定性系统中由于内禀随机性而产生的一种复杂的、貌似无规的运动。混沌并不是无序和紊乱，更像是没有周期的秩序。与随机运动相比较，混沌运动可以在各态历经的假设下，应用统计的数字特征来描述。并且，混沌运动不重复地经过同一状态，采用混沌变量进行优化比采用随机变量进行优化具有优势。
混沌优化与下降类方法结合使用是有潜力的一种全局优化途径，是求解具有变量界约束优化问题的可靠方法。如何进一步提高搜索效率，以及如何把混沌优化有效应用于复杂约束优化问题是值得进一步研究的课题。
本文算法全局收敛性的严格数学证明正在进行之中。
参考文献
[1]胡山鹰，陈丙珍，何小荣，沈静珠．非线性规划问题全局优化的模拟退火法[J]．清华大学学报，37(6)，1997，5-9．
[2]C A Floudas, A Aggarwal, A R Ciric． Global optimum search for nonconvex NLP and MINLP problems[J]. Comput Chem Engng． 1989， 13(10)， 1117~1132．
[3]康立山，谢云，尤矢勇等．非数值并行算法（第一册）――模拟退火算法[M]．北京：科学出版社，1998．
[4]刘勇，康立山，陈琉屏．非数值并行算法（第二册）――遗传算法[M]．北京：科学出版社，1998．
[5]李兵，蒋慰孙．混沌优化方法及其应用[J]．控制理论与应用，14(4)，1997，613-615．
[6]张彤，王宏伟，王子才．变尺度混沌优化方法及其应用[J]．控制与决策，14(3)，1999，285-287．
[7]席少霖．非线性最优化方法[M]．北京：高等教育出版社，1992．
[8]席少霖，赵凤志．最优化计算方法[M]．上海：上海科学技术出版社，1983．
[9]Press W H, Tenkolsky S A, Vetterling W T, Flannery B P．Numerical Recipes in C, The Art of Scientific Computing[M]． Second edition， Cambridge University Press， 1992．
[10]J C Ports．The development and evaluation of an improved genetic algorithm based on migration and artificial selection[J]．IEEE Trans. Syst. Man and Cybern.．1994, 24(1)，73-85．
A Hybrid Approach for Nonlinear Optimization
Abstract：Combined BFGS method with chaos optimization method, a hybrid approach was proposed to solve nonlinear optimization problems with boundary restraints of variables. The hybrid method is an effective approach to solve nonconvex optimization problems, as it given both attentions to the inherent virtue to locate global optimum of chaos optimization method and the advantage of high convergence speed of BFGS method. Numerical examples illustrate that the present method possesses both good capability to search global optima and far higher convergence speed than that of chaos optimization method.