极值动力学优化算法

极值动力学优化算法(Extremal Optimization,EO)是一种新颖的、通用的、基于局部搜索的启发式智能方法,该方法是从统计物理学发展而来。通过内在的极值动力学机制及其自身具备自组织临界性完成智能优化。

极值动力学优化算法与模拟退火算法

众所周知,模拟退火算法(Simulated Annealing,SA)是模拟系统处于平衡态的一种优化方法,与SA不同的是,EO算法的理论基础建筑在Bak-Sneppen生物进化模型之上,该模型模拟处于远离平衡态的系统,具备自组织临界性(Self-Organized Criticality,SOC)。SOC是指不管系统处于何种初始状态,不需要调整任何参数,整个系统就可以演化到一个自组织临界状态,在该状态下,系统呈现出幂律分布(Power-law)。

极值动力学优化算法与遗传算法

遗传算法通过对交配池中的所有可能解实施选择、杂交和变异等遗传操作来达到寻优的目的,而EO算法总是不断地变异近似解的最差组成部分(即所谓的极值动力学机制)来达到寻优的目的。正是这种内在的极值动力学机制(Extremal dynamics),使得EO具备很强的爬山能力,尤其在求解带有相变点(Phase transitions)的组合优化问题时EO更是展现出强大的优势。

极值动力学优化算法特点

EO算法的特点是收敛速度快,局部搜索能力强,只有变异算子,无可调参数(对于基本EO算法)或只有一个可调参数τ(对于τ-EO算法)。因此,用EO算法解决优化问题设计简单,容易实现。目前EO算法已经被成功地应用于求解一些NP难的组合优化问题,如二分图,旅行商问题,图着色,旋转玻璃和动态组合优化问题。

但是,EO的发展历史尚短,理论基础还不够完善,对EO算法的收敛性缺乏理论分析和证明;其次,EO算法中适应度函数的定义对于加快收敛速度和找到全局最优解起着至关重要的作用,但是,对于不同的问题,其适应度函数的定义都有所不同。因此,研究如何针对不同的问题来定义合适的适应度函数也具有重要的理论意义。



3 Responses to “极值动力学优化算法”

  1. 淘宝  on 七月 11th, 2010

    经常观注你的博客呀,基本上天天都会过来看看的,你博客写的很不错。

  2. lsc  on 七月 9th, 2010

    应该写成论文发表啊

    • CnHUP  on 七月 9th, 2010

      好建议!过段时间结合实例来写下


发表评论

You must be logged in to post a comment.