Graph-based Ant System and its convergence

被引：218

作者：

Gutjahr, WJ ^{[1
]}

机构：

[1] Univ Vienna, Dept Stat Operat Res & Comp Sci, A-1010 Vienna, Austria

来源：

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE | 2000年 / 16卷 / 08期

关键词：

heuristic; ant system; ant colony optimisation; combinatorial optimisation; Markov process;

D O I：

10.1016/S0167-739X(00)00044-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A general framework for solving combinatorial optimization problems heuristically by the Ant System approach is developed. The framework is based on the concept of a construction graph, a graph assigned to an instance of the optimization problem under consideration, encoding feasible solutions by walks. It is shown that under certain conditions, the solutions generated in each iteration of this Graph-based Ant System converge with a probability that can be made arbitrarily close to 1 to the optimal solution of the given problem instance. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：873 / 888

页数：16

共 19 条

[1] Aarts E., 1989, Wiley-Interscience Series in Discrete Mathematics and Optimization
[2] [Anonymous], 1992, OPTIMIZATION LEARNIN
[3] Bullnheimer B., 1999, CENTRAL EUROPEAN J O, V7, P25
[4] Bullnheimer B., 1998, HIGH PERFORMANCE ALG, V24, P87, DOI DOI 10.1007/978-1-4613-3279-4_6
[5] Dorigo M., 1997, IEEE Transactions on Evolutionary Computation, V1, P53, DOI 10.1109/4235.585892
[6] Ant algorithms for discrete optimization
Dorigo, M
Di Caro, G
Gambardella, LM
[J]. ARTIFICIAL LIFE, 1999, 5 (02) : 137 - 172
[7] Ant system: Optimization by a colony of cooperating agents
Dorigo, M
Maniezzo, V
Colorni, A
[J]. IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01): : 29 - 41
[8] Dorigo M, 1999, NEW IDEAS OPTIMIZATI, P11
[9] DORIGO M, 1991, 91016 POL MIL DEP EL
[10] GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES
FEO, TA
RESENDE, MGC
[J]. JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) : 109 - 133

← 1 2 →