造价通

反馈
取消

热门搜词

造价通

取消 发送 反馈意见

状态转移算法一种连续状态转移算法

2022/07/16234 作者:佚名
导读:在连续状态转移算法中, 是一个连续变量,设计了四个特殊的状态转换算子来产生新的候选解。 状态转移算法状态转换算子 (1) 旋转变换(Rotation Transformation, RT) 这里 是一个正常数,称作旋转因子, 是一个随机矩阵,它里面的每个元素服从[-1,1]的均匀分布, 表示向量的二范数。旋转变换具有在半径为 的超球体内搜索的功能。 (2)平移变换(Translation Tran

在连续状态转移算法中,

是一个连续变量,设计了四个特殊的状态转换算子来产生新的候选解。

状态转移算法状态转换算子

(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直到终止条件满足。

状态转移算法基本连续状态转移算法背后的原理

  • 伸缩变换算子具有在整个空间进行搜索的能力,使其满足全局性;

  • 旋转变换算子中,当旋转因子充分小时,当前的最好解将变成一个局部最优解,即;

  • 更新策略可以保证状态转移算法的收敛性,因为

且假定

存在,根据单调收敛定理可知序列
是收敛的;
  • 采样机制(它有效地避免了穷举)和各种状态转变算子的交替使用可以很好的节省搜索时间;

  • 状态转移中对变换因子的调整可以控制搜索空间的几何形态。

*文章为作者独立观点,不代表造价通立场,除来源是“造价通”外。
关注微信公众号造价通(zjtcn_Largedata),获取建设行业第一手资讯

热门推荐

相关阅读