求解旅行商问题的改进果蝇算法

被引：10

作者：

王克甫 ^{[1
]}

薛鹏 ^{[1
]}

黄全振 ^{[1
,2
]}

李恒宇 ^{[2
]}

机构：

[1] 河南工程学院电气信息工程学院

[2] 上海大学机电工程与自动化学院

来源：

计算机工程与设计 | 2014年 / 35卷 / 08期

基金：

中国博士后科学基金;

关键词：

果蝇算法; 局部最优半径; 变异算子; 自适应步长; 旅行商问题;

D O I：

10.16208/j.issn1000-7024.2014.08.064

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

为了有效解决经典的NP难问题-旅行商问题(traveling salesman problem,TSP),提出了一种改进的果蝇算法。针对果蝇算法存在易陷入局部最优及收敛速度慢的缺点,引入了局部最优半径的概念,以此为依据判断果蝇是否处于局部最优区域;设计了带启发式规则的变异算子,对局部最优半径中选中的果蝇个体进行启发式变异,在保护最优个体的同时,也改善了种群多样性,抑制了早熟现象的产生;采用自适应步长策略,显著提高了搜索效率。对其全局收敛性进行了验证,以TSPLIB为基准与标准果蝇算法、粒子群算法进行了实验对比,对比结果验证了该算法的有效性。

引用

页码：2789 / 2792+2821 +2821

页数：5

共 7 条

[1] 基于人工蜂群算法的TSP仿真 [J].

胡中华 ;

赵敏 .

北京理工大学学报, 2009, 29 (11) :978-982

[2] 基于k-中心点法的改进粒子群算法在旅行商问题中的应用 [J].

张旭梅 ;

邱晗光 .

计算机集成制造系统, 2007, (01) :99-104

[3] 基于MapReduce的蚁群算法 [J].

吴昊 ;

倪志伟 ;

王会颖 .

计算机集成制造系统, 2012, 18 (07) :1503-1509

[4]

Hongze Li,Sen Guo,Huiru Zhao.Annual Electric Load Forecasting by a Least Squares Support Vector Machine with a Fruit Fly Optimization Algorithm. ENERGIES . 2012

[5] 基于人工蜂群算法的TSP仿真 [J].