一种具有确定偏好和随机权重的改进蚂蚁系统(2013年)

工程技术

论文

需积分: 5 131 浏览量 2021-06-14 15:55:32 上传评论 1 收藏 492KB PDF 举报

资源推荐

资源详情

资源评论

苛

抖

胡

言

唱

电

Vol.17

No.3

第

卷第

期

2013

年

月

电机与控制学报

ELECTRIC

MACHINES

AND

CONTROL

Mar. 2013

一种具有确定偏好和随机权重的改进蚂蚁系统

张杰，

徐志宇，

曾正洋，

许维胜

(同济大学电子与信息工程学院，上海

201804

)

摘

要:提出一种多阶段，多偏好的改进蚁群算法

(MP

AS)

，包括

种蚁型，对信息索、能见度与节

约值有不同的重视程度。常态时，所有蚂蚁遵循同一转移规则，同时更新公共和私有信息素;一旦

陷入局部最优，

种蚁型将根据各自确定的偏好类型，运用随机的偏好权重，计算特移概卒，并只更

新其私有信息素。偏好类型的王异性使蚁群得以沿不同方向独立进化;而偏好权重的随机性进一

步提高了改善当前最优解的概率。为避免某种蚁型因长期孤立进化而积累病态，定期用全局最优

解更新公共及私有信息素，增强蚁型间的交流，指导蚁群的进化方向。车辆路径问题标准算例的数

值实验结果说明该算法具有很强的全局搜索和局部开发能力。

关键词:蚁群优化;蚁型;多阶段-多偏好;确定的偏好类型;随机的偏好权重;公共/私有信息索

中图分类号

:TP

;TP

273

文献标志码

文章编号:

l007-449X(2013)03-

∞

98-07

proved

ant

system with deterministic preference

and

stochastic weights

ZHANG

Jie

Zhi-yu

ZENG

Zheng-yang

Wei-sheng

(School

Electronics

and

Information

Engineering

Tongji

University

皿

ghai

，

201804

China)

Abstract:

This paper proposes an improved ant system with multiple phases and preferences (MP2

) .

The ant colony is composed of four ant groups , which attaches different significance to pheromone , visi-

bility and savings. Normally all ants conduct state transitions with the same rule and simultaneously up-

date the public/private pheromones. Once trapped in local optima, each ant group will calculate the tran-

sition probability according

its

own

preference type and stochastic weights , and update its own private

pheromone. The discrepancy of preference type realizes the concurrent search along different directions

while the random preference weights increase the probability of finding superior solutions.

e global op-

timal solution is periodically utilized

update the public and private pheromones to enhance the commu-

nication among ant groups and provide guidance for the evolution of the whole ant colony. Numeric exper-

iments are performed on various vehicle routing benchmark problems and computational results indicate

that the proposed algorithm is with strong capability of global exploration as well as local exploitation.

Key

words:

ant colony optimization; ant group; multi-phase multi-preference; deterministic preference

type; stochastic preference weight;

public/

private pheromone

收稿日期:

2012

-20

基金项目:国家自然科学基金

(91024023

，

71090404);

上海市基础研究重点项目(lO

JCI415300)

;上海市科委项目(1

0dz

份

作者简介:张

杰(

1968

一)

，女，博士，高级工程师，研究方向为智能算法及应用;

徐志宇(

1982

一)

，男，博士，讲师，研究方向为启发式算法优化在电气系统中的应用;

曾正洋(1

987

一)

，男，博士研究生，研究方向为启发式算法优化在调度问题中的应用;

许维胜

(1966

一)

，男，教授，博士生导师，研究方向为智能控制理论及应用。

通讯作者:徐志宇

;

第

期

张

杰等:一种具有确定偏好和随机权重的改进蚂蚁系统

。

自然界中，蚁群总是可以迅速发现巢穴与食物

之间的最短路径，尽管单个蚂蚁行为单一，但大量蚂

蚁通过分工协作，构成高度结构化的社会组织，表现

出强大的搜索能力

[1]

。受这种群体智能

(swarm

in-

telligence)

行为的启发，上世纪

年代，

Dorigo

等

提出蚁群优化(

ant colony optimization ,

ACO)

的算法

体系

[2]

并成功应用于各种非线性优化问题[川]。

为克服其易早熟停滞(

stagnation)

的缺陷，相关改进

工作主要围绕以下

个方面展开。

)参数选择。

信息素权重

，能见度权重

，挥发率

，

一般通过大

量数值实验确定

[8]

文献

[9]

给出一种设定参数的

均匀设计法。文献

[10

]重点研究

的自适应调节，

改善全局搜索能力。

转移规则。状态转移时一

般考虑候选弧段上的信息素

，

能见度

，节约值

，

采用轮盘赌或伪随机策略。大规模问题中对所有可

行状态均计算转移概率是低效和不必要的，文献

[11

]通过多态蚁群中侦察蚁的初始局部搜索，文献

[12

]利用最优解的区域特征，精简候选状态集，压

缩问题规模，提高了寻优效率。

信息素更新。其

核心是"用什么值来强化哪些解

"[13]

。

ant-densi

/ quantity /

cycle

系统分别利用固定数值，弧段长

度，路径总长度，更新所有蚂蚁走过的路径，而

ant

则利用全局最短路径总长，只强化蚁群发现的最

短路径。为了避免蚁群被强势路径引人局部最优，

Stützle

提出最大最小蚂蚁系统

(MMAS)

[叫，限定

信息素范围。文献[

]从优解池中选取更新信息

素。文献口

基于

ant

density

模型，利用信息素的

扩散反映较优解的吸引作用。文献

[17

]将信息素

划分为有限个等级，使更新量独立于目标函数值，文

献

[18]

设计了

层更新模式。文献[

19]

在实时性

方面做了改进。

文献

[20]

从一个全新的视角，提出了混合行为

蚁群算法

(HBACA)

，蚁群中的不同个体根据各自的

行为准则完成状态转移。然而大量数值仿真的结果

显示，当蚁群已获得较优解时，单纯根据启发因子

(先验知识)或信息素(后验知识)都不利于发现更

优解，而在大规模问题中依靠完全盲目的随机转移，

正巧碰到更优解的概率更是微乎其微，因此我们认

为，在借鉴"混合行为"思想的同时，有必要对不同

蚁型的行为展开深入分析和精致设计，结合仿真实

验，确定行之有效的转移规则，真正使每种蚁型都能

为发现新优解发挥作用，从而提高整个蚁群的全局

搜索能力。

基本蚁群算法

以车辆路径问题

(vehicle

routing problem ,

VRP)

为例，平面分布

个节点，

为车场(

depω)

-n

为客户

(customer)

。车辆从车场满载出发，服

务所有客户，若剩余载量不足则返回车场重新装载。

每个客户只能由一辆车服务一次。寻求车辆数最少

和总行程最短的配送方案。

研究表明，影响蚂蚁状态转移的因素包括信息

素

，

能见度

和节约值

μ[

川，其中

Cij

为

，

两节点

间的转移成本，

今

，

JLij

表明由节点

直接转移至到

节

点点]:获获得的收益越高。

为后验知识，

，

均为先验的启发函数。

用蚁群算法求解

VRP

时，每只蚂蚁映射为一台

虚拟车辆。当蚂蚁

位于节点

时，服务过的节点

构成其禁忌表矶，未服务且满足容量约束的节点构

成其可行集鸣，即

k =

{sls

øθ

knd

，

~C}

，

(1)

式中

，

为节点

的需求量，

为蚂蚁

的当前剩余

容量。蚂蚁

根据

(3)

移到节点]，直至遍历所有节

点，即生成一个解，对应于车辆完成一次配送。

:~μ;

巧=

~亏

，

if j E

otherwise

。

if r <

(吨

弩刊

μ:

，

式(

otherwise

。

(2)

(3)

式中

:α

，

分别为

，

的权重

，

为一个

，

间均匀分布的随机数，

为预设阔值

。

只蚂蚁全部生成各自的配送路径后，蚁群按照

Tij

•

-p

ij+åTij'

(4)

更新信息素，并进人下一轮迭代。式中

为信息素

挥发率，

<ρ<1

。不同蚂蚁系统中

åT

的具体形式

不同，例如

ant

- density/ quantity/

cycle

模型中

åTij = L

åTt

)

所有解均参与更新信息素

(

åTt

的计算方法有所区

别)

;ant

模型中仅用最优解更新信息、素

豆

åTij =

~lb

，

鸟，

otherwise

。

(6)

式中

:Sb

为本轮迭代最优解

Sib

或全局最优解

Sgb'λ

为相应的最优值儿或

。

剩余6页未读，继续阅读

评论收藏

内容反馈

weixin_38504170

粉丝: 3
资源: 937

一种具有确定偏好和随机权重的改进蚂蚁系统 (2013年)

最新资源

一种具有确定偏好和随机权重的改进蚂蚁系统 (2013年)

一种改进的偏好融合组推荐方法.pdf

TSP-EAS(精华蚂蚁系统)_精华蚂蚁系统_

论文研究-考虑不同心理行为偏好的混合随机多属性决策.pdf

一种不确定语言偏好排序的多目标粒子群算法.pdf

一种基于专家权重的方案排序方法

7种确定评估指标权重方法的比较.pdf

企业管理权重确定方法.doc

论文研究-求解VRPTW问题的不确定性目标偏好蚁群算法.pdf

电信设备-一种信用卡偏好分析系统和方法.zip

反S型权重风险偏好对一类两级供应链的影响.pdf 知网论文

基于蚁群优化算法的TSP商旅优化问题，输出动态路线规划过程和收敛过程。对比了传统蚁群，精英蚂蚁系统，基于排序的蚂蚁系统

熵权法_熵权法权重确定_目标函数权重_

一种模糊偏好排序的多目标粒子群算法.pdf

基于Vikor的具有不确定偏好序数和不完全权重信息的群体决策方法

基于作者偏好和异构信息网络的科技文献推荐方法研究.docx

一种缓解推荐偏好的协同过滤TopN算法.docx

具有无差异区间偏好结构的权重稳定区间 (2005年)

偏好逻辑资料，一篇有用的资料

电信设备-一种基于用户偏好的信息推送方法和装置.zip

最新资源