伊藤算法的框架及关键算子的设计

4.2.2　伊藤算法的框架及关键算子的设计

1．算法框架

伊藤过程主要是针对一个粒子的运动规律而言的，为了将伊藤过程映射为能求解优化问题的算法，模仿其他的群智能算法，比如遗传算法、蚁群算法、粒子群算法、免疫算法等，设计的伊藤算法同样是基于种群的算法，其框架如下。

Step1:初始化，采用某种策略初始化N₀个粒子的种群，并设置算法的相关参数。

Step2:评估种群中的粒子，并采用有关策略选取种群中若干个个体作为漂移算子的吸引点(或者叫吸引元、吸引子)。

Step3:每个粒子按照设定漂移算子和波动算子运动到新的位置，即计算每个粒子的漂移增量和波动增量，两者共同决定更新粒子的运动，从而更新粒子的位置;假设波动的增量为w(t)、漂移增量为m(t)，粒子当前位置为x(t)，则粒子下一刻的位置为

其中γ₁，γ₂为漂移和波动的权向量因子。

Step4:是否满足停机条件，若是则退出，否则转Step2。

2．漂移算子的设计

漂移算子由两部分构成:一个是漂移的方向a;一个是漂移的距离，即漂移的系数(或增量)α。下面针对n维空间Rⁿ中极小化问题详细讨论二者的确定方法。

下面的定义主要考虑如下的函数优化模型:

minf(x)

s.t.x∈Rⁿ

定义4.3　映射M:Rⁿ×Rⁿ×R₊→Rⁿ，Ax₁，x₀，其中x₁称为原始空间点、x₀称为吸引子，假设x₁按照上述的方法确定的半径为r₁，参数T∈R₊，满足以下条件:

(5)如果r₁=0，则α=0;

(6)如果T=0，则α=0。

则映射M被称为漂移算子，α被称为漂移增量(或漂移系数)。

一旦定义了漂移方向和漂移增量，粒子的漂移的新位置由下式计算:

其中，x'为粒子漂移之后的新位置，x为粒子漂移之前的位置。

根据定义4.3，对于n维空间中的连续系统优化问题，漂移的方向比较容易确定，是该粒子指向吸引子的方向，即

其中，x代表当前粒子的位置，x₀代表吸引子的位置，如图4.1所示。

图4.1　粒子的漂移过程

3．波动算子的设计

波动函数的设计应该遵循的原则如下:

(1)波动算子是在粒子的邻域内局部的扰动，代表粒子局部的“探索”能力;

(2)由于是基于伊藤过程的随机算法，波动算子应该遵循伊藤过程中波动率的定义;

(3)波动的方向可以随机选定，取决于抽样路径;

(4)波动算子的设计应该遵循物理学原理，和漂移算子一样，应该体现出环境温度和粒子半径的影响。

伊藤算法的提出者董文勇教授指出，上述这些条件可以部分满足，但第一条一定要满足。波动算子的几何意义如下:对于给定的一个解x，波动后会移动到一个新的位置从而得到一个新的解x';在x附近的所有解中，距离x越近，被选取的可能性越大，反之，则越小。

从粒子的位置更新函数可以看出，对于当前最好的那个粒子，其漂移增量为0。因为它无须朝着当前最优解靠拢，它没有任何漂移的趋势，但其波动增量不为0。因为即使是当前最优解，也有必要在它周围进行小范围搜索，于是有可能找到更为精确的最优解。对于距离当前最优解很远的粒子，它会以一种相对较快的速度向当前最优解漂移，体现了快速优化的特性。如果粒子距离当前最优解很近或是评估值与最优解接近，那么其漂移的速度就会非常慢，这样有利于精细化搜索。