第 22 卷 第 10 期
Vol. 22 No. 10
控 制 与 决 策
Control and Decision
2007 年 10 月
Oct. 2007
收稿日期 : 2006208203 ; 修回日期 : 2006210218.
基金项目 : 国家自然科学基金项目
(
70701009 ,70431003
)
.
作者简介 : 齐洁
(
1978 —
)
,女 ,云南大理人 ,博士 ,从事建模与优化、智能优化方法等研究 ; 汪定伟
(
1948 —
)
,男 ,
江西彭泽人 ,教授 ,博士生导师 ,从事制造系统建模与优化、智能计算与软计算等研究.
文章编号 : 100120920
(
2007
)
1021081205
极 值 优 化 算 法 综 述
齐 洁
1
, 汪定伟
2
(
1. 东华大学 信息科学与技术学院 , 上海 200051 ; 2. 东北大学 信息科学与工程学院 , 沈阳 110004
)
摘 要 : 极值优化
(
EO
)
算法是新开发的一种启发式算法 ,其基本思想是更新适值最差的变量 ,提高目标函数的适
值. 首先介绍了自组织临界的思想和模型 ;然后阐述了算法的具体实现 ,讨论了算法的改进、特点和算法的理论分析 ;
最后介绍了算法的应用 ,并展望了算法未来可能的改进和研究方向.
关键词 : 极值优化算法 ; 自组织临界 ; 准平衡性 ; 演化计算
中图分类号 : TP301. 6 文献标识码 : A
Overview of extremal optimization algorithm
QI J ie
1
, W A N G Ding2wei
2
(
1. College of Information Science and Technology , Donghua University , Shanghai 200051 , China ; 2. College of
Information Science and Engineering , Northeastern University , Shenyang 110004 , China. Correspondent : QI Jie ,
E2mail : jieqi @dhu. edu. cn
)
Abstract : Extremal optimization
(
EO
)
algorithm is a new heuristic method , whose principle is to select and update the
worst variable , and improve the fitness of the whole problem. The relative theory and model of self2organized
criticality in complex system are reviewed. Then , the implementing process of EO is described. Some improved
schemes ,properties and theoretical analysis results for EO are presented and discussed. Finally , applications of EO are
introduced , and the further possible improvements for EO and research directions are suggested.
Key words: Extremal optimization algorithm ; Self2organized criticality ; Punctuated equilibrium ; Evolutionary
computation
1
引 言
极值优化
(
EO
)
算法由 Boettcher
[1 ]
在国际遗传
与进化计算会议上首次提出. 算法的思想源于自组
织临界理论 ,其突出的特点为非平衡性
(
准平衡性
)
.
它不同于以往提出的智能优化方法
(
如遗传算法
(
GA
)
,模拟退火算法
(
SA
)
,蚁群算法 , PSO 算法
等
)
,EO 算法不会收敛到一个平衡态 ,而出现断续
平衡 ,产生的波动性使算法具有更好的持续搜索和
跳出局优解的能力. EO 算法易于实现 ,计算量小 ,
算法效果好 ,因此得到了广泛的应用. EO 算法规则
简单 ,可追踪算法的运行过程 ,建立算法过程模型 ,
进行理论分析. 目前 , 一些学者对此作了初步研
究
[224 ]
.
本文首先介绍与 EO 算法相关的复杂系统理
论 ;然后给出基本的 EO 算法 ,并以 TSP 问题为例
介绍算法的具体实现 ;再后讨论算法的改进 ,分析算
法的特点 ,并与其他算法进行比较 ;最后介绍建模分
析方面的成果以及算法的实际应用.
2 极值优化算法的由来
EO 算法是受复杂系统自组织临界进化模型的
启发 ,发展形成的一种启发式智能算法. 自然界和人
类社会中存在许多复杂系统 ,它们在无外界驱动的
情况下 ,能够自发地演化形成复杂的结构 ,这样的结
构能以一种精妙的方式优化资源的使用
[5 ]
. 例如生
态系统进化形成了一种强大相互依赖连接的网络 ,
能高效地使用有限的资源 ;网络系统如果工作在临
界状态下 ,就能获得最高的数据传输效率
[6 ]
. 为了描
述这种突现的复杂性 ,Bak
[729 ]
提出了自组织临界
(
SOC
)
的概念.
SOC 普遍存在于复杂系统 ,如地貌的形成、地
震、森林火灾、网络交通流、城市演化、收入和财富的
分布、经济破产、技术创新和股市波动
[4 ]
等. 为了研
资源评论
