Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 2012

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: ACO Metaheuristic

Sortuj według:

Ogranicz wyniki do:

Shortest path problem solving based on ant colony optimization metaheuristic

Głąbowski M., Musznicki B, Nowak P., Zwierzykowski P.

Image Processing & Communications

2012

Vol. 17, no. 1-2

7--17

The Ant Colony Optimization (ACO) metaheuristic is a versatile algorithmic optimization approach based on the observation of the behaviour of ants. As a result of numerous analyses, ACO has been applied to solving various combinatorial problems. The ant colony metaheuristic proves itsel I' to be efficient in solving NP-hard problems, often generating the best solution in the shortest amount of time. However, not enough attention has been paid to ACO as a means of solving problems that have optimal solutions which can be found using other methods. The shortest path problem is undoubtedly one of the aspects of great significance to navigation and telecommunications. It is used, amongst others, for determining the shortest route between two geographical locations, for routing in packet networks, and to balance and optimize network utilization. Thus, this article introduces ShortestPathACO, an Ant Colony Optimization based algorithm designed to find the shortest path in a graph. The algorithm consists of several subproblems that are presented successively. Each subproblem is discussed from many points of view to enable researchers to find the most suitable solutions to the problems they investigate.

Approximations on Minimum Weight Triangulations and Minimum Weight Pseudo-Triangulations Using Ant Colony Optimization Metaheuristic

Dorzan M. G., Gagliardi E. O., Leguizamón M. G., Pe�nalver G. H.

Fundamenta Informaticae

2012

Vol. 119, nr 1

1-27

Globally optimal triangulations and pseudo-triangulations are difficult to be found by deterministic methods as, for most type of criteria, no polynomial algorithm is known. In this work, we consider the Minimum Weight Triangulation (MWT) and Minimum Weight Pseudo- Triangulation (MWPT) problems of a given set of n points in the plane. This paper shows how the Ant Colony Optimization (ACO) metaheuristic can be used to find high quality triangulations and pseudo-triangulations of minimum weight. For the experimental study presented here we have created a set of instances for MWT and MWPT problems since no reference to benchmarks for these problems were found in the literature. Through the experimental evaluation, we assess the applicability of the ACO metaheuristic for MWT and MWPT problems considering greedy and Simulated Annealing algorithms.