狀態轉移算法

周曉君最最佳化問題狀態空間表達式狀態轉移矩陣

基本介紹

• 中文名：
• 外文名：
• 提出者：
• 提出時間：

統一框架

狀態空間表達式

最最佳化問題

狀態轉移矩陣

一種連續狀態轉移算法

狀態轉移矩陣

對於給定的 ，考慮到狀態轉移矩陣中的元素服從某種隨機分布，產生的候選解是一個隨機向量，它對應的特定值可以看成一個樣本。此外，對於某種狀態變換運算元和給定當前狀態，考慮到其對應的狀態轉移矩陣的產生是獨立的，當獨立運行多次後，比如獨立運行SE次後，將會產生SE個樣本。

更新策略

在給定當前最好解 的基礎上，對於某種狀態變換運算元，利用上面闡述的採樣策略，將會產生SE個候選解。記SE個候選解中的最好解為 ，則通過如下的策略來更新當前最好解

, if

, otherwise

基本連續狀態轉移算法的流程

基本連續狀態轉移算法由上面介紹的狀態變換運算元，採樣機制與更新策略融合而成，其算法的流程如下：

Step 1：隨機產生一個初始解 ，設定算法參數 1e-4,

Step 2: 基於當前最好解 ，利用伸縮變換操作產生SE個樣本，並利用更新策略更新當前最好解，如果當前最好解有變動，執行平移變換操作並以同樣的機制更新當前最好解 。

Step 3: 基於當前最好解 ，利用旋轉變換操作產生SE個樣本，並利用更新策略更新當前最好解，如果當前最好解有變動，執行平移變換操作並以同樣的機制更新當前最好解 。

Step 4: 基於當前最好解 ，利用坐標搜尋操作產生SE個樣本，並利用更新策略更新當前最好解，如果當前最好解有變動，執行平移變換操作並以同樣的機制更新當前最好解 。

Step 5: 置 ，如果 ，置 ，否則置 ，然後重返Step2直到終止條件滿足。

基本連續狀態轉移算法背後的原理

• 伸縮變換運算元具有在整個空間進行搜尋的能力，使其滿足全局性；
• 旋轉變換運算元中，當旋轉因子充分小時，當前的最好解將變成一個局部最優解，即；

；

• 更新策略可以保證狀態轉移算法的收斂性，因為

且假定 存在，根據單調收斂定理可知序列 是收斂的；

• 採樣機制(它有效地避免了窮舉)和各種狀態轉變運算元的交替使用可以很好的節省搜尋時間;
• 狀態轉移中對變換因子的調整可以控制搜尋空間的幾何形態。

其它相關連結

狀態轉移算法的MATLAB程式