状态转移算法

状态转移算法状态转移算法状态转移算法状态转移算法 铁中铁中 信息科学与 程学院信息科学与 程学院 铁中玉铁中玉 信息科学与工程学院信息科学与工程学院 Outline 转 算法 Outline ¾ Part 1 状态转移算法产生的背景 ¾part 2 状态转移算法的具体介绍¾part 2 状态转移算法的具体介绍 ¾part 3 初步结果和未来研究p Part 1 状态转移算法产生的背景Part 1 状态转移算法产生的背景 思想源头: 乾 ：元，亨，利，贞。 初九：潜龙勿用初九：潜龙勿用。 九二：见龙在田，利见大人。 九三 君子终日乾乾 夕惕若 厉无咎九三：君子终日乾乾，夕惕若。厉无咎。 九四：或跃在渊，无咎。 九 龙在 利 人九五：飞龙在天，利见大人。 上九：亢龙有悔。 用九：见群龙无首，吉。 《易经·乾》 Part 1 状态转移算法产生的背景Part 1 状态转移算法产生的背景 约束优化问题描述: min ( )f X⎧⎪ . . ( ) 0( 1, , ) ( ) 0( 1 ) ist g X i m h X j l ⎪ ≤ =⎨⎪ = =⎩ " "( ) 0( 1, , )jh X j l⎪ = =⎩ " m in ( )f X无约束优化问题: Part 1 状态转移算法产生的背景Part 1 状态转移算法产生的背景 传统的基于梯度的算法: 通常采用迭代法求无约束优化问题的极小点。设xk为第k次迭代点， dk为第k次搜索方向，ak为第k次步长，则第k次迭代为 1+ = +k k k kx x a d k ， k ， 在这里，待确定的参数为ak和dk。 关于步长的选择方法有 简单算关于步长的选择方法有：（1）简单算法 （2）一维搜索算法 （3）可接受点法 Part 1 状态转移算法产生的背景Part 1 状态转移算法产生的背景 关于搜索方向的选择方法有： （1）最速下降法 （2）共轭梯度法（2）共轭梯度法 （3）牛顿法 （4）拟牛顿法 （5）坐标轮换法（ ）坐标轮换法 （6）Rosenbrock旋转方向法 （7）P ll方法（7）Powell方法 Part 1 状态转移算法产生的背景Part 1 状态转移算法产生的背景 智能优化算法: （1）遗传算法 （2）PSO算法 初始化种群 选择 1 1 2 2( 1) ( ) ( ( )) ( ( ))id id id id gd idv t wv t cr p x t c r p x t+ = + − + − ( 1) ( ) ( 1)id id idx t x t v t+ = + +选择 交叉 id id id 变异 Part 1 状态转移算法产生的背景Part 1 状态转移算法产生的背景 一方面，从传统的无约束最优化问题的各种算法可以看出，它从根本意义上， ， 是要寻找迭代时的搜索方向和搜索步长。虽然这些方法有时直接或间接地利用了 梯度信息，但梯度方向具有它本身的缺陷，一是计算上的困难；二是它仅能反映 局部信息。从全局优化意义上说，梯度方向仅是一种方向而已，它对寻找全局最局部信息。从全局优化意义上说，梯度方向仅是 种方向而已，它对寻找全局最 优并没有起到实质性的作用。如果从状态和状态转移的概念来理解传统优化方法。 则某一个迭代点xk可视为一个状态，将寻找迭代时的搜索方向和搜索步长的过程 便为一个状态转移 通过一次状态转移 则产生新的迭代点x便为 个状态转移，通过 次状态转移，则产生新的迭代点xk+1。 另一方面，也可以从一个广义的角度上来理解智能优化算法。对于遗传算法， 它的每一代种群的一个个体可视为一个状态，遗传算子包括选择，交叉以及变异 过程也即种群更新过程可视为一个状态转移过程。同样的，鸟群通过速度方程和 位置方程来更新位置的过程，也可看作是状态转移过程。， Part 2 状态转移算法的具体介绍Part 2 状态转移算法的具体介绍 借鉴状态及状态转移的概念，则可以将待优化问题的解理解为状态，优化算 法的思想描述为状态转移 求解待优化问题的过程便是 个状态转移过程法的思想描述为状态转移，求解待优化问题的过程便是一个状态转移过程。 通过上面的和讨论，可以定义如下的状态转移形式 ( 1) ( ) ( )+ +⎧x k A x k B u k( 1) ( ) ( ) ( ( 1)) + = +⎧⎨ = +⎩ k k k x k A x k B u k y f x k 其中x(k)表示一个状态，对应待优化问题的一个解；Ak、Bk为状态转移矩阵，可 解为优化算法 想的算 为状态 史状态的 数 为适应度 数理解为优化算法思想的算子；uk为状态x(k)及历史状态的函数；f为适应度函数。 Part 2 状态转移算法的具体介绍Part 2 状态转移算法的具体介绍 三种操作算子 1（1）旋转变换 2 1( 1) ( ) ( ) ( )n x k I alpha R x k n x k + = + × × ×× Part 2 状态转移算法的具体介绍Part 2 状态转移算法的具体介绍 （2）伸缩变换 ( 1) ( ) ( )sx k x k gamma R x k+ = + × × Part 2 状态转移算法的具体介绍 （3）平移变换 Part 2 状态转移算法的具体介绍 [ ( ) ( 1)]( 1) ( ) ( ) ( 1)m x k x kx k x k beta R k k − −+ = + × × 2 ( ) ( ) ( ) ( 1)m x k x k− − 4.4 4.6 4.8 5 3.4 3.6 3.8 4 4.2 4.4 14 1.6 1.8 2 2.2 2.4 2.6 2.8 3 2.5 3 3.5 4 3 3.2 1 1.2 1.4 2 Part 2 状态转移算法的具体介绍Part 2 状态转移算法的具体介绍 对于一个共同的优化问题，需要在很多“精英个体”的协作下完成。但这里有一， 个亟待解决的问题是如何既保持个性（自由发展）又保持共性（相互交流）。如 果交流很频繁，交流的信息太多，就会容易在交流不久便向当前最优个体看齐。 本着《易经·乾》的原则，在STA中，提出“间歇性交流”的概念，意思是交流是本着《易经 乾》的原则，在STA中，提出 间歇性交流 的概念，意思是交流是 间歇性的进行，而非持续地交流。另外在交流中，采用随机地两两配对的原则， 但与其他智能算法不同的是，配对的结果还是本着保持个性的原则，即两个个体 交换信息 是吸纳对自己有用的信息 如果信息对自己帮助不大 则保持个体交换信息，是吸纳对自己有用的信息，如果信息对自己帮助不大，则保持个体。 Part 3 初步结果和未来研究Part 3 初步结果和未来研究 寻优过程显示：.exe 4个Benchmark测试函数 n 2 1 1 ( ) , 100 100 n i i i f x x x = = − ≤ ≤∑ n (1) Sphere 函数 2 2 2 2 1 1 (100( ) ( 1) ), 100 100 n i i i i i f x x x x+ = = − + − − ≤ ≤∑ 2 n∑ (2) Rosenbrock函数 数 23 1 ( 10cos(2 ) 10), 5.12 5.12i i i i f x x xπ = = − + − ≤ ≤∑ 21 cos 1 600 600 nn ixf x x+ ≤ ≤∑ ∏ (3) Rastrigin函数 函数 4 1 1 cos 1, 600 600 4000 i i i i i f x x i= = = − + − ≤ ≤∑ ∏(4) Griewank函数 Part 3 初步结果和未来研究 函数 指标 PSO 基本 STA 增强 STA Part 3 初步结果和未来研究 Table 1: 实验测试结果 问题规模n=10 函数 指标 PSO 基本 STA 增强 STA 最好值 0 0 0 最差值 0 0 0 平均值 0 0 0 众数 Sphere 函数 众数 0 0 0 方差 0 0 0 最好值 0.0074 0.0106 0.4254 最差值 1.0000e+006 0.0168 0.9799 平均值 1.2024e+005 0.0133 0.7505 众数 86.4190 0.0106 0.4254 Rosenbrock 函数 方差 3.2817e+005 0.0014 0.1080 最好值 5.3404e-011 0 0 最差值 2.9849 34.8235 0 平均值 0.8557 2.4078 0 众数 0.9950 0 0 Rastrigin 函数 方差 0.9214 7.2227 0 最好值 0.0123 0 0 最差值 0.1650 0.1798 0 平均值 0.0624 0.0059 0 众数 0.0123 0 0 Griewank 函数 方差 0.0335 0.0276 0 Part 3 初步结果和未来研究Part 3 初步结果和未来研究 （1）状态转移算法的参习 （2）基于状态转移算法的约束优化（2）基于状态转移算法的约束优化 （3）基于状态转移算法的多目标优化 （4）从优化视角研究建模与控制问题（4）从优化视角研究建模与控制问题 （5）其它应用 谢谢！！谢谢！！谢谢！！谢谢！！ 敬请批评指正敬请批评指正敬请批评指正敬请批评指正