状态转移算法状态转移算法状态转移算法状态转移算法
铁中铁中
信息科学与 程学院信息科学与 程学院
铁中玉铁中玉
信息科学与工程学院信息科学与工程学院
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)其它应用
谢谢!!谢谢!!谢谢!!谢谢!!
敬请批评指正敬请批评指正敬请批评指正敬请批评指正