MAX-MIN蚁群系统：改进的优化算法

需积分: 49 115 浏览量更新于2024-07-20 2 收藏 330KB PDF 举报

最大最小蚁群系统（MAX-MIN Ant System，简称MMAS）是蚁群优化算法领域的一项重要发展，它源自于最早的蚁群算法——Ant System。最初由Thomas Stützle和Holger H. Hoos在2000年的《Future Generation Computer Systems》期刊上发表，该研究旨在解决复杂的组合优化问题，尤其是像旅行商问题（Traveling Salesman Problem，TSP）这样的传统基准问题。 Ant System以其分布式搜索和模仿生物行为的特性，在解决某些难题时展现出可行性，但它在处理大规模实例时的性能相对较低，无法与当时更为精细调优的算法相媲美。为了提升蚁群优化算法在解决硬组合优化问题上的竞争力，近年来的研究重点主要集中在开发改进版本，旨在提升算法的性能，超越Ant System本身。 MMAS作为这些改进策略之一，它在Ant System的基础上引入了若干关键改进。首先，MMAS强调了“最大化”和“最小化”的策略，这可能意味着它通过调整蚂蚁的信息素更新规则、选择路径决策或启发式信息使用，来寻找全局最优解的同时，避免陷入局部最优。其次，MMAS可能采用了动态调整参数的方法，如根据问题规模自适应地改变搜索强度或信息素衰减速度，以提高算法的适应性和效率。在论文中，作者通过实验和实证分析展示了MMAS相对于Ant System的优越性。他们可能通过对比两者的性能表现，包括解决问题的时间复杂度、收敛速度和解决方案质量，来证明MMAS在面对大型组合优化问题时，能够提供更稳定且高效的解决方案。此外，MMAS可能还展示了更好的泛化能力，即不仅在特定的测试集上表现出色，而且在不同规模和类型的优化问题中都能保持良好性能。 MAX-MIN Ant System是对蚁群优化算法的一种创新，通过优化策略和机制设计，成功地提升了在硬组合优化问题上的解决能力，为该领域的研究者提供了新的视角和方法，对于实际应用中的复杂优化问题具有重要的理论价值和实践意义。

T. Stützle, H.H. Hoos / Future Generation Computer Systems 16 (2000) 889–914 893

assignment is obtained. The pheromone update is done

as in the TSP application.

2.5. Improvements over Ant System

AS has been compared with other general purpose

heuristics on some relatively small TSP instances with

up to 75 cities. Some initial results were encourag-

ing and have shown the viability of the approach; for

example, AS could be shown to achieve better tour

qualities than other nature-inspired algorithms, such

as simulated annealing or genetic algorithms [14].

However, for larger TSP instances AS gives a very

poor solution quality compared to state-of-the-art al-

gorithms. A ﬁrst improvement over AS, called the

elitist strategy for Ant System (AS

) [8,14], gives a

strong additional reinforcement to the solution com-

ponents belonging to the best solution found since the

start of the algorithm; this solution is denoted as s

(global-best solution) in the following. This is realized

by adding a quantity e/f (s

), where e is the number

of elitist ants and f(s

) is the solution cost of s

,to

the arcs used in s

after each iteration. Some limited

results presented in [8,14] suggest that the use of the

elitist strategy with an appropriate number of elitist

ants allows AS to ﬁnd better tours and to ﬁnd them

earlier in the run. Yet, if too many elitist ants are used,

the search concentrates early around suboptimal solu-

tions leading to a premature stagnation of the search.

Search stagnation is deﬁned in [14] as the situation

where all ants follow the same path and construct the

same solution over and over again, such that better

solutions cannot be found anymore.

Other improvements over AS include Ant Colony

System (ACS) [12,18] and the rank-based version of

Ant System (AS

rank

) [5]. In ACS and MMAS, the

best solutions found during the search are exploited

by allowing only one ant to update the trails after each

iteration, while in AS

rank

a ﬁxed number of ants of the

current iteration — the better the ants are ranked in the

current iteration, the more weight they are given for

the trail update — and the global-best ant are allowed

to update the pheromone trails.

3. Search space characteristics

All improved ACO algorithms have one important

feature in common: they exploit the best solutions

found during the search much more than what is done

by AS. Also, they use local search to improve the solu-

tions constructed by the ants. The fact that additional

exploitation of the best found solutions provides the

key for an improved performance, is certainly related

to the shape of the search space of many combinato-

rial optimization problems. In this section, we report

some results on the topology of search spaces of TSP

and QAP instances which partly explain the observed

performance differences and motivates important

aspects of the algorithmic design of MMAS.

3.1. Analysis of ﬁtness landscapes

Central to the search space analysis of combinato-

rial optimization problems is the notion of ﬁtness land-

scape [39,48]. Intuitively, the ﬁtness landscape can be

imagined as a mountainous region with hills, craters,

and valleys. A local search algorithm can be pictured

as a wanderer that performs a biased walk in this land-

scape. In a minimization problem such as the TSP or

the QAP, the goal is to ﬁnd the lowest point in this

landscape. The effectiveness of a given search strat-

egy for the wanderer strongly depends on the rugged-

ness of the landscape, the distribution of the valleys

and craters in the landscape, and the overall number

of valleys and craters. Formally, the ﬁtness landscape

is deﬁned by

1. the set of all possible solutions S;

2. an objective function that assigns a ﬁtness value

f(s) to every s ∈ S;

3. a neighborhood structure N ⊆ S × S.

The ﬁtness landscape determines the shape of the

search space as encountered by a local search algo-

rithm. The neighborhood structure induces a distance

metric on the set of solutions; the distance d(s,s

)

between two solutions s and s

can be deﬁned as the

minimum number of moves that have to be performed

to transform s into s

The distribution of local minima and their relative

location with respect to global optima is an important

criterion for the effectiveness of adaptive multi-start

algorithms like ACO algorithms. For analyzing this

aspect of the ﬁtness landscape, the correlation be-

tween solution ﬁtness and the distance to optimal so-

lutions has been studied [3,23,31]; in the literature on

genetic algorithms this correlation is also called the

ﬁtness–distance correlation (FDC) [23]. This corre-

894 T. Stützle, H.H. Hoos / Future Generation Computer Systems 16 (2000) 889–914

lation can be captured by the correlation coefﬁcient,

which is deﬁned as:

ρ(F,D) =

Cov(F, D)

√

Var (F )

√

Var (D)

, (5)

where Cov(F, D) is the covariance between the ran-

dom variables F and D which probabilistically de-

scribe the ﬁtness and the distance of local optima to a

global optimum, while Var denotes the variance. This

correlation coefﬁcient can be empirically estimated by

substituting the covariance and the variance values by

the respective empirically measured ones. The FDC

analysis has shown to be very useful in the context of

studying the effectiveness of adaptive algorithms and

their design [3,4,31]. Note that for minimization prob-

lems, a high, positive correlation between the solution

cost and the distance to the global optimum indicates

that the smaller the solution cost, the closer are the so-

lutions — on average — to a global optimum. Hence,

if a problem shows a high FDC, algorithms combin-

ing adaptive solution generation and local search may

be expected to perform well. For ACO algorithms,

this is the case because the most important guidance

mechanism of ACO algorithms is the solution quality

of the solutions constructed by the ants — the better

a solution, the more its solution components will be

reinforced. Yet, if no such correlation exists, or even

worse, if cost and distance are negatively correlated,

the ﬁtness gives only little or no guidance towards

better solutions and on such problems ACO algorithm

may perform poorly.

3.2. FDC analysis for the TSP

The symmetric TSP is one of the most widely

studied problems in terms of search space analysis

[3,4,24,34]. A good distance measure between two

tours s and s

is given by the number of different arcs,

that is, d(s,s

) = n−|{(i, j) : (i, j) ∈ s ∧(i, j ) ∈ s

(n is the number of cities). A ﬁrst study of the corre-

lation between the solution quality and the distance

to the global optimum has been done in [3]. Addi-

tionally, plots of the solution cost versus the distance

to the closest global optimum have shown to be a

very illustrative tool for the graphical presentation of

the ﬁtness–distance relationship [3,23,31]. Here, we

exemplify results on the FDC analysis using some in-

stances which are larger than previously studied ones.

For our investigation we use a 3-opt local

search algorithm [25]. This local search algorithm

proceeds by systematically testing whether the cur-

rent tour can be improved by replacing at most

three arcs. Straightforward 3-opt implementations

require O(n

) exchanges to be examined. Since

this is too time-consuming in practice, we use a

number of standard speed-up techniques [1,22,29]

which achieve a subquadratical growth of the lo-

cal search time with instance size. In particular, we

restrict the set of examined moves to a candidate

list of a ﬁxed number of nearest neighbors; here,

as a default we set this number to 40. Addition-

ally, we apply a ﬁxed radius nearest neighbor search

[1,22].

For some instances several globally optimal solu-

tions exist. To partially address this issue, for each

of these problems we generated a number of glob-

ally optimal solutions, then eliminated doubles and

in our FDC analysis we use the distance to the clos-

est of these global optima. (Note that the number in

the instance name gives the number of cities.) Fig.

2 gives plots of the percentage deviation from the

optimum versus the distance to the closest global

optimum. All plots show a strong positive corre-

lation between solution cost and the distance from

the closest optimal solution — better local min-

ima tend to be closer to the global optimum. Some

summary results for the FDC analysis are given in

Table 1, in particular, the average distance between

local minima and the average distance to global op-

tima, the respective ratios to the maximum possible

distance, and the correlation coefﬁcients are given.

Interestingly, the ratio between the average distance

of tours and the distance size (column avg

d-ls

/n in

Table 1) is very small; this fact indicates that locally

optimal tours in the TSP are concentrated around a

small region of the whole search space (this partic-

ularity has also been observed before [3,4,24,34]).

Also, the correlation coefﬁcients are all statistically

signiﬁcant. Note that the generality of these results

does not depend on the particular 3-opt algorithm

used. When using 2-opt or the more powerful

Lin–Kernighan heuristic (LK) for the local search,

again a strongly signiﬁcant FDC, which was slightly

weaker when using 2-opt and stronger when using

LK, has been observed for the instances examined in

[3].

剩余25页未读，继续阅读

stevendick

粉丝: 0
资源: 1

MAX-MIN蚁群系统：改进的优化算法

蚁群算法代码及模型.rar

基于蚁群系统的Hopfield神经网络

MMAS_最大最小蚂蚁系统_蚁群信息素_蚁群算法_mmas_改进蚁群算法_

最大最小蚁群算法是什么

基于蚁群算法求解TSP问题的国内外现状

蚁群算法的基本介绍及使用的语言环境介绍 蚁群算法的运行实例以及性能比较 蚁群算法的改进，变种及其具体解决了什么问题

蚁群算法解决0-1背包问题

蚁群算法k-means

蚁群算法求解多目标多旅行商

0-1背包 蚁群算法

最新资源

蚁群算法的基本介绍及使用的语言环境介绍蚁群算法的运行实例以及性能比较蚁群算法的改进，变种及其具体解决了什么问题

0-1背包蚁群算法