An ant system for the maximum independent set problem

Early applications of Ant Colony Optimization (ACO) have been mainly concerned with solving ordering problems (e.g., the Traveling Salesperson Problem). More recently, promising results were obtained for solving the Multiple Knapsack Problem by introducing a modification of the standard Ant System a...

Descripción completa

Detalles Bibliográficos
Autores principales: Leguizamón, Guillermo, Michalewicz, Zbigniew, Schutz, Martín
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2001
Materias:
Ciencias Informáticas
Hormigas
Optimization
Heuristic methods
ARTIFICIAL INTELLIGENCE
ant colony optimization
maximum independent set problem
combinatorial optimization
metaheuristics
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/23384
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-23384
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Hormigas
Optimization
Heuristic methods
ARTIFICIAL INTELLIGENCE
ant colony optimization
maximum independent set problem
combinatorial optimization
metaheuristics
spellingShingle Ciencias Informáticas
Hormigas
Optimization
Heuristic methods
ARTIFICIAL INTELLIGENCE
ant colony optimization
maximum independent set problem
combinatorial optimization
metaheuristics
Leguizamón, Guillermo
Michalewicz, Zbigniew
Schutz, Martín
An ant system for the maximum independent set problem
topic_facet Ciencias Informáticas
Hormigas
Optimization
Heuristic methods
ARTIFICIAL INTELLIGENCE
ant colony optimization
maximum independent set problem
combinatorial optimization
metaheuristics
description Early applications of Ant Colony Optimization (ACO) have been mainly concerned with solving ordering problems (e.g., the Traveling Salesperson Problem). More recently, promising results were obtained for solving the Multiple Knapsack Problem by introducing a modification of the standard Ant System algorithm. In this paper we extend our study on the applicability of the ACO approach to subset problems. The computational study involves its applicability for solving the Maximum Independent Set Problem (MISP). The set of instances tested were either randomly generated by specific methods or taken from the so-called DIMACS benchmark graphs. The reported results which are comparable with different state-of-the-art algorithms show the potential of the ACO approach for solving the MISP.
format Objeto de conferencia
Objeto de conferencia
author Leguizamón, Guillermo
Michalewicz, Zbigniew
Schutz, Martín
author_facet Leguizamón, Guillermo
Michalewicz, Zbigniew
Schutz, Martín
author_sort Leguizamón, Guillermo
title An ant system for the maximum independent set problem
title_short An ant system for the maximum independent set problem
title_full An ant system for the maximum independent set problem
title_fullStr An ant system for the maximum independent set problem
title_full_unstemmed An ant system for the maximum independent set problem
title_sort ant system for the maximum independent set problem
publishDate 2001
url http://sedici.unlp.edu.ar/handle/10915/23384
work_keys_str_mv AT leguizamonguillermo anantsystemforthemaximumindependentsetproblem
AT michalewiczzbigniew anantsystemforthemaximumindependentsetproblem
AT schutzmartin anantsystemforthemaximumindependentsetproblem
AT leguizamonguillermo antsystemforthemaximumindependentsetproblem
AT michalewiczzbigniew antsystemforthemaximumindependentsetproblem
AT schutzmartin antsystemforthemaximumindependentsetproblem
bdutipo_str Repositorios
_version_ 1764820465781571586

Ejemplares similares