状态转移算法

在连续状态转移算法中，

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

(1) 旋转变换（Rotation Transformation, RT）

这里

(2)平移变换（Translation Transformation, TT）

这里

(3)伸缩变换（Expansion Transformation, ET）

这里

(4)坐标搜索（Axesion Transformation, AT）

这里

状态转移算法邻域和采样

对于一个给定的当前状态

对于给定的

状态转移算法更新策略

在给定当前最好解

状态转移算法基本连续状态转移算法的流程

基本连续状态转移算法由上面介绍的状态变换算子，采样机制与更新策略融合而成，其算法的流程如下：

Step 1：随机产生一个初始解

Step 2: 基于当前最好解

Step 3: 基于当前最好解

Step 4: 基于当前最好解

Step 5: 置

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

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

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

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

且假定

• 采样机制(它有效地避免了穷举)和各种状态转变算子的交替使用可以很好的节省搜索时间;

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

状态转移算法的MATLAB程序 2100433B

状态转移算法用状态空间表达式来统一描述产生候选解的统一框架：

其中，

作为一种全局优化算法，在设计状态转移算法时，使其具备以下性质：

• 全局性，状态转移算法具有在整个空间进行搜索的能力；

• 最优性，状态转移算法可以保证找到一个最优解；

• 收敛性，通过状态转移算法产生的解序列是收敛的；

• 快速性，状态转移算法尽可能地节省搜索时间；

• 可控性，状态转移算法可以控制搜索空间的几何形态。

状态转移矩阵是俄国数学家马尔科夫提出的控制理论中的矩阵，是时间和初始时间的函数，可以将时间的状态向量和此矩阵相乘，得到时间时的状态向量。

他在20世纪初发现：一个系统的某些因素在转移过程中，第n次结果只受第n-1的结果影响，即只与上一时刻所处状态有关，而与过去状态无关。 在马尔科夫分析中，引入状态转移这个概念。所谓状态是指客观事物可能出现或存在的状态；状态转移是指客观事物由一种状态转移到另一种状态。2100433B

关于状态机的一个极度确切的描述是：它是一个有向图形，由一组节点和一组相应的转移函数组成。状态机通过响应一系列事件而“运行”。每个事件都在属于“当前” 节点的转移函数的控制范围内，其中函数的范围是节点的一个子集。函数返回“下一个”（也许是同一个）节点。这些节点中至少有一个必须是终态。当到达终态， 状态机停止。

包含一组状态集（states）、一个起始状态（start state）、一组输入符号集（alphabet）、一个映射输入符号和当前状态到下一状态的转换函数（transition function）的计算模型。当输入符号串，模型随即进入起始状态。它要改变到新的状态，依赖于转换函数。在有限状态机中，会有有许多变量，例如，状态 机有很多与动作（actions）转换(Mealy机)或状态（摩尔机）关联的动作，多重起始状态，基于没有输入符号的转换，或者指定符号和状态（非定有 限状态机）的多个转换，指派给接收状态（识别者）的一个或多个状态，等等。

传统应用程序的控制流程基本是顺序的：遵循事先设定的逻辑，从头到尾地执行。很少有事件能改变标准执行流程；而且这些事件主要涉及异常情况。“命令行实用程序”是这种传统应用程序的典型例子。

另一类应用程序由外部发生的事件来驱动——换言之，事件在应用程序之外生成，无法由应用程序或程序员来控制。具体需要执行的代码取决于接收到的事件，或者它相对于其他事件的抵达时间。所以，控制流程既不能是顺序的，也不能是事先设定好的，因为它要依赖于外部事件。事件驱动的GUI应用程序是这种应用程序的典 型例子，它们由命令和选择（也就是用户造成的事件）来驱动。

Web应用程序由提交的表单和用户请求的网页来驱动，它们也可划归到上述类别。但是，GUI应用程序对于接收到的事件仍有一定程度的控制，因为这些事件要依赖于向用户显示的窗口和控件，而窗口和控件是由程序员控制的。Web应用 程序则不然，因为一旦用户采取不在预料之中的操作（比如使用浏览器的历史记录、手工输入链接以及模拟一次表单提交等等），就很容易打乱设计好的应用程序逻辑。

显然，必须采取不同的技术来处理这些情况。它能处理任何顺序的事件，并能提供有意义的响应——即使这些事件发生的顺序和预计的不同。有限状态机正是为了满足这方面的要求而设计的。

有限状态机是一种概念性机器，它能采取某种操作来响应一个外部事件。具体采取的操作不仅能取决于接收到的事件，还能取决于各个事件的相对发生顺序。之所以能 做到这一点，是因为机器能跟踪一个内部状态，它会在收到事件后进行更新。为一个事件而响应的行动不仅取决于事件本身，还取决于机器的内部状态。另外，采取 的行动还会决定并更新机器的状态。这样一来，任何逻辑都可建模成一系列事件/状态组合。

状态机可归纳为4个要素，即现态、条件、动作、次态。这样的归纳，主要是出于对状态机的内在因果关系的考虑。“现态”和“条件”是因，“动作”和“次态”是果。详解如下：

①现态：是指当前所处的状态。

②条件：又称为“事件”，当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。

③动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。

④次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。