Using ACO Metaheuristic for MWT Problem

Author

Dorzan, M.G. ; Gagliardi, E.O. ; Leguizamon, M.G. ; Penalver, G.H.

Author_Institution

Fac. de Cienc. Fis. Mat. y Naturales, Univ. Nac. de San Luis, San Luis, Argentina

fYear

2011

fDate

9-11 Nov. 2011

Firstpage

228

Lastpage

237

Abstract

Globally optimal 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) problem 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. For the experimental study we have created a set of instances for MWT problem 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 problem.

Keywords

ant colony optimisation; computational complexity; computational geometry; deterministic algorithms; set theory; ACO metaheuristic; MWT problem; NP-hard problems; ant colony optimization metaheuristic; computational geometry; deterministic methods; global optimal triangulations; minimum weight triangulation problem; no polynomial algorithm; Algorithm design and analysis; Approximation algorithms; Approximation methods; Computational geometry; Optimization; Probabilistic logic; Runtime; ACO Metaheuristic; Computational Geometry; Minimum Weight; Triangulation;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Science Society (SCCC), 2011 30th International Conference of the Chilean

Conference_Location

Curico

ISSN

1522-4902

Print_ISBN

978-1-4673-1364-3

Type

conf

DOI

10.1109/SCCC.2011.30

Filename

6363402