在连续状态转移算法中, 是一个连续变量,设计了四个特殊的状态转换算子来产生新的候选解。
状态转移算法状态转换算子
(1) 旋转变换(Rotation Transformation, RT)
这里 是一个正常数,称作旋转因子, 是一个随机矩阵,它里面的每个元素服从[-1,1]的均匀分布, 表示向量的二范数。旋转变换具有在半径为 的超球体内搜索的功能。
(2)平移变换(Translation Transformation, TT)
这里 是一个正常数,称作平移因子, 是一个服从[0,1]均匀分布的随机变量。平移变换具有沿着从点 到点 直线上并以 为起点最大长度为 进行线搜索的功能。
(3)伸缩变换(Expansion Transformation, ET)
这里 是一个正常数,称作伸缩因子, 是一个随机对角矩阵,它里面的每个元素服从高斯分布。伸缩变换具有使 中的每个元素伸缩变换到 的功能,从而实现在整个空间进行搜索。
(4)坐标搜索(Axesion Transformation, AT)
这里 是一个正常数,称作坐标因子, 是一个随机对角稀疏矩阵,它只在某个随机位置有非零元素,且该元素服从高斯分布。坐标搜索具有沿着坐标轴方向搜索的功能,它的目的是为了增强单维搜索能力。
状态转移算法邻域和采样
对于一个给定的当前状态 ,下一个状态 是通过上面介绍的状态变换算子产生的。考虑到状态转移矩阵的随机性,可知产生的候选解不是唯一的。不难想象,对于给定的 ,当利用某种状态变换算子时,产生的所有候选解将自动形成一个邻域。
对于给定的 ,考虑到状态转移矩阵中的元素服从某种随机分布,产生的候选解是一个随机向量,它对应的特定值可以看成一个样本。此外,对于某种状态变换算子和给定当前状态,考虑到其对应的状态转移矩阵的产生是独立的,当独立运行多次后,比如独立运行SE次后,将会产生SE个样本。
状态转移算法更新策略
在给定当前最好解 的基础上,对于某种状态变换算子,利用上面阐述的采样策略,将会产生SE个候选解。记SE个候选解中的最好解为 ,则通过如下的策略来更新当前最好解
, if
, otherwise
状态转移算法基本连续状态转移算法的流程
基本连续状态转移算法由上面介绍的状态变换算子,采样机制与更新策略融合而成,其算法的流程如下:
Step 1:随机产生一个初始解 ,设置算法参数 1e-4,
Step 2: 基于当前最好解 ,利用伸缩变换操作产生SE个样本,并利用更新策略更新当前最好解,如果当前最好解有变动,执行平移变换操作并以同样的机制更新当前最好解 。
Step 3: 基于当前最好解 ,利用旋转变换操作产生SE个样本,并利用更新策略更新当前最好解,如果当前最好解有变动,执行平移变换操作并以同样的机制更新当前最好解 。
Step 4: 基于当前最好解 ,利用坐标搜索操作产生SE个样本,并利用更新策略更新当前最好解,如果当前最好解有变动,执行平移变换操作并以同样的机制更新当前最好解 。
Step 5: 置 ,如果 ,置 ,否则置 ,然后重返Step2直到终止条件满足。
状态转移算法基本连续状态转移算法背后的原理
;
且假定 存在,根据单调收敛定理可知序列 是收敛的;