狀態(tài)轉(zhuǎn)移算法一種連續(xù)狀態(tài)轉(zhuǎn)移算法

在連續(xù)狀態(tài)轉(zhuǎn)移算法中，

狀態(tài)轉(zhuǎn)移算法狀態(tài)轉(zhuǎn)換算子

(1) 旋轉(zhuǎn)變換（Rotation Transformation, RT）

這里

(2)平移變換（Translation Transformation, TT）

這里

(3)伸縮變換（Expansion Transformation, ET）

這里

(4)坐標(biāo)搜索（Axesion Transformation, AT）

這里

狀態(tài)轉(zhuǎn)移算法鄰域和采樣

對于一個給定的當(dāng)前狀態(tài)

對于給定的

狀態(tài)轉(zhuǎn)移算法更新策略

在給定當(dāng)前最好解

狀態(tài)轉(zhuǎn)移算法基本連續(xù)狀態(tài)轉(zhuǎn)移算法的流程

基本連續(xù)狀態(tài)轉(zhuǎn)移算法由上面介紹的狀態(tài)變換算子，采樣機(jī)制與更新策略融合而成，其算法的流程如下：

Step 1：隨機(jī)產(chǎn)生一個初始解

Step 2: 基于當(dāng)前最好解

Step 3: 基于當(dāng)前最好解

Step 4: 基于當(dāng)前最好解

Step 5: 置

狀態(tài)轉(zhuǎn)移算法基本連續(xù)狀態(tài)轉(zhuǎn)移算法背后的原理

• 伸縮變換算子具有在整個空間進(jìn)行搜索的能力，使其滿足全局性；

• 旋轉(zhuǎn)變換算子中，當(dāng)旋轉(zhuǎn)因子充分小時，當(dāng)前的最好解將變成一個局部最優(yōu)解，即；

• 更新策略可以保證狀態(tài)轉(zhuǎn)移算法的收斂性，因為

且假定

• 采樣機(jī)制(它有效地避免了窮舉)和各種狀態(tài)轉(zhuǎn)變算子的交替使用可以很好的節(jié)省搜索時間;

• 狀態(tài)轉(zhuǎn)移中對變換因子的調(diào)整可以控制搜索空間的幾何形態(tài)。

狀態(tài)轉(zhuǎn)移算法用狀態(tài)空間表達(dá)式來統(tǒng)一描述產(chǎn)生候選解的統(tǒng)一框架：

其中，

作為一種全局優(yōu)化算法，在設(shè)計狀態(tài)轉(zhuǎn)移算法時，使其具備以下性質(zhì)：

• 全局性，狀態(tài)轉(zhuǎn)移算法具有在整個空間進(jìn)行搜索的能力；

• 最優(yōu)性，狀態(tài)轉(zhuǎn)移算法可以保證找到一個最優(yōu)解；

• 收斂性，通過狀態(tài)轉(zhuǎn)移算法產(chǎn)生的解序列是收斂的；

• 快速性，狀態(tài)轉(zhuǎn)移算法盡可能地節(jié)省搜索時間；

• 可控性，狀態(tài)轉(zhuǎn)移算法可以控制搜索空間的幾何形態(tài)。

狀態(tài)轉(zhuǎn)移算法的MATLAB程序 2100433B

狀態(tài)轉(zhuǎn)移矩陣是俄國數(shù)學(xué)家馬爾科夫提出的控制理論中的矩陣，是時間和初始時間的函數(shù)，可以將時間的狀態(tài)向量和此矩陣相乘，得到時間時的狀態(tài)向量。

他在20世紀(jì)初發(fā)現(xiàn)：一個系統(tǒng)的某些因素在轉(zhuǎn)移過程中，第n次結(jié)果只受第n-1的結(jié)果影響，即只與上一時刻所處狀態(tài)有關(guān)，而與過去狀態(tài)無關(guān)。 在馬爾科夫分析中，引入狀態(tài)轉(zhuǎn)移這個概念。所謂狀態(tài)是指客觀事物可能出現(xiàn)或存在的狀態(tài)；狀態(tài)轉(zhuǎn)移是指客觀事物由一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)。2100433B

關(guān)于狀態(tài)機(jī)的一個極度確切的描述是：它是一個有向圖形，由一組節(jié)點(diǎn)和一組相應(yīng)的轉(zhuǎn)移函數(shù)組成。狀態(tài)機(jī)通過響應(yīng)一系列事件而“運(yùn)行”。每個事件都在屬于“當(dāng)前” 節(jié)點(diǎn)的轉(zhuǎn)移函數(shù)的控制范圍內(nèi)，其中函數(shù)的范圍是節(jié)點(diǎn)的一個子集。函數(shù)返回“下一個”（也許是同一個）節(jié)點(diǎn)。這些節(jié)點(diǎn)中至少有一個必須是終態(tài)。當(dāng)?shù)竭_(dá)終態(tài)， 狀態(tài)機(jī)停止。

包含一組狀態(tài)集（states）、一個起始狀態(tài)（start state）、一組輸入符號集（alphabet）、一個映射輸入符號和當(dāng)前狀態(tài)到下一狀態(tài)的轉(zhuǎn)換函數(shù)（transition function）的計算模型。當(dāng)輸入符號串，模型隨即進(jìn)入起始狀態(tài)。它要改變到新的狀態(tài)，依賴于轉(zhuǎn)換函數(shù)。在有限狀態(tài)機(jī)中，會有有許多變量，例如，狀態(tài) 機(jī)有很多與動作（actions）轉(zhuǎn)換(Mealy機(jī))或狀態(tài)（摩爾機(jī)）關(guān)聯(lián)的動作，多重起始狀態(tài)，基于沒有輸入符號的轉(zhuǎn)換，或者指定符號和狀態(tài)（非定有 限狀態(tài)機(jī)）的多個轉(zhuǎn)換，指派給接收狀態(tài)（識別者）的一個或多個狀態(tài)，等等。

傳統(tǒng)應(yīng)用程序的控制流程基本是順序的：遵循事先設(shè)定的邏輯，從頭到尾地執(zhí)行。很少有事件能改變標(biāo)準(zhǔn)執(zhí)行流程；而且這些事件主要涉及異常情況?！懊钚袑嵱贸绦颉笔沁@種傳統(tǒng)應(yīng)用程序的典型例子。

另一類應(yīng)用程序由外部發(fā)生的事件來驅(qū)動——換言之，事件在應(yīng)用程序之外生成，無法由應(yīng)用程序或程序員來控制。具體需要執(zhí)行的代碼取決于接收到的事件，或者它相對于其他事件的抵達(dá)時間。所以，控制流程既不能是順序的，也不能是事先設(shè)定好的，因為它要依賴于外部事件。事件驅(qū)動的GUI應(yīng)用程序是這種應(yīng)用程序的典 型例子，它們由命令和選擇（也就是用戶造成的事件）來驅(qū)動。

Web應(yīng)用程序由提交的表單和用戶請求的網(wǎng)頁來驅(qū)動，它們也可劃歸到上述類別。但是，GUI應(yīng)用程序?qū)τ诮邮盏降氖录杂幸欢ǔ潭鹊目刂?，因為這些事件要依賴于向用戶顯示的窗口和控件，而窗口和控件是由程序員控制的。Web應(yīng)用 程序則不然，因為一旦用戶采取不在預(yù)料之中的操作（比如使用瀏覽器的歷史記錄、手工輸入鏈接以及模擬一次表單提交等等），就很容易打亂設(shè)計好的應(yīng)用程序邏輯。

顯然，必須采取不同的技術(shù)來處理這些情況。它能處理任何順序的事件，并能提供有意義的響應(yīng)——即使這些事件發(fā)生的順序和預(yù)計的不同。有限狀態(tài)機(jī)正是為了滿足這方面的要求而設(shè)計的。

有限狀態(tài)機(jī)是一種概念性機(jī)器，它能采取某種操作來響應(yīng)一個外部事件。具體采取的操作不僅能取決于接收到的事件，還能取決于各個事件的相對發(fā)生順序。之所以能 做到這一點(diǎn)，是因為機(jī)器能跟蹤一個內(nèi)部狀態(tài)，它會在收到事件后進(jìn)行更新。為一個事件而響應(yīng)的行動不僅取決于事件本身，還取決于機(jī)器的內(nèi)部狀態(tài)。另外，采取 的行動還會決定并更新機(jī)器的狀態(tài)。這樣一來，任何邏輯都可建模成一系列事件/狀態(tài)組合。

狀態(tài)機(jī)可歸納為4個要素，即現(xiàn)態(tài)、條件、動作、次態(tài)。這樣的歸納，主要是出于對狀態(tài)機(jī)的內(nèi)在因果關(guān)系的考慮?！艾F(xiàn)態(tài)”和“條件”是因，“動作”和“次態(tài)”是果。詳解如下：

①現(xiàn)態(tài)：是指當(dāng)前所處的狀態(tài)。

②條件：又稱為“事件”，當(dāng)一個條件被滿足，將會觸發(fā)一個動作，或者執(zhí)行一次狀態(tài)的遷移。

③動作：條件滿足后執(zhí)行的動作。動作執(zhí)行完畢后，可以遷移到新的狀態(tài)，也可以仍舊保持原狀態(tài)。動作不是必需的，當(dāng)條件滿足后，也可以不執(zhí)行任何動作，直接遷移到新狀態(tài)。

④次態(tài)：條件滿足后要遷往的新狀態(tài)。“次態(tài)”是相對于“現(xiàn)態(tài)”而言的，“次態(tài)”一旦被激活，就轉(zhuǎn)變成新的“現(xiàn)態(tài)”了。