收稿日期 :2003212215
基金项目 :国家自然科学基金项目
(
60104009
)
作者简介 :李晓磊
(
19732
)
,男 ,讲师 ,博士 ,研究方向为复杂系统智能优化、人工智能等.
文章编号 :167223961
(
2004
)
0520064204
组合优化问题的人工鱼群算法应用
李晓磊
1
,路 飞
1
,田国会
1
,钱积新
2
(
1. 山东大学 控制科学与工程学院 ,山东 济南 250061 ;
2. 浙江大学 控制系 系统工程研究所 ,浙江 杭州 310027
)
摘要 :通过模仿鱼类的行为方式 ,提出了一种基于动物自治体的优化方法 —人工鱼群算法
(
Artificial Fish
-
school Al2
gorithm
)
,并将其用于组合优化问题的求解. 介绍了该算法在此类问题求解中的距离、邻域等概念 ,给出了具体的实
现方法. 最后以 TSP 问题为例对该算法进行仿真测试. 结果表明它具有快速收敛的能力.
关键词 :人工鱼群算法 ;组合优化 ;寻优 ;TSP
中图分类号 :TP18 文献标识码 :A
Applications of artificial fish school algorithm in
combinatorial optimization problems
LI Xiao2lei
1
, LU Fei
1
, TIAN Guo2hui
1
, QIAN Ji2xin
2
(
11 School of Control Science and Engineering , Shandong Univ. , Jinan 250061 , China ;
21 Institute of Systems Engineering , Control Department , Zhejiang Univ. , Hangzhou 310027 , China
)
Abstract : An optimizing method based on autonomous animats approach , artificial fish school algorithm , is
presented. It is applied to solve the combinatorial optimization problem. The concepts of distance , neighbor2
hood , center , etc. , which are used in artificial fish school algorithm are introduced. Experiments of traveling
salesman problems are carried out. It shows that artificial fish school algorithm has rapid convergence ability.
Key words : artificial fish school algorithm; combinatorial optimizing; optimize ; TSP
0 引言
组合优化问题广泛存在于经济管理、交通运输、
通信网络等领域 ,其目的主要是寻找离散事件的最
优编排、分组、次序或筛选等 ,是运筹学中的一个经
典而重要的分支. 一些组合优化问题随着规模的扩
大 ,会造成计算规模的迅速增加 ,被称为 NP ,NP2C
和 NP2hard 复杂性问题 ,如装箱判定问题、旅行商问
题
(
TSP
)
等
【1】
. 对于此类问题 ,目前大都采用寻找近
似算法或启发式算法来寻求一个满意解或目前最好
解. 笔者给出了此类问题的人工鱼群算法描述 ,并以
TSP 问题作为对象进行仿真 ,结果表明该算法具有
快速收敛的特性.
人工鱼群算法是笔者模仿鱼类行为方式提出的
一种基于动物自治体
【2 ,3】
的优化方法 ,是集群智能
思想
【4】
的一个具体应用. 它能很好地解决非线性函数
优化等问题
【5 ,6】
. 它的主要特点是不需要了解问题的
特殊信息 ,只需要对问题进行优劣的比较 ,有着较快
的收敛速度. 仿真结果表明 ,该算法在组合优化问题
第 34 卷 第 5 期
Vol. 34 No. 5
山 东 大 学 学 报
(
工 学 版
)
JOURNAL OF SHANDONGUNIVERSITY
(
ENGINEERING SCIENCE
)
2004 年 10 月
Oct. 2004
© 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
