Ant Colony Optimization with Parallel Subsolutions Heuristic

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F08%3A00147052" target="_blank" >RIV/68407700:21230/08:00147052 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Ant Colony Optimization with Parallel Subsolutions Heuristic

Popis výsledku v původním jazyce

For solving N-complete Travelling Salesman Problem (TSP) by combining solutions of its subproblems, we designed algorithm inspired by Ant Colony Optimization (ACO) modified by adding parallel subsolutions heuristic. ACO can be parallelized simply by simultaneous execution of the algorithm with eventual exchange of the best solutions between all computational units. This approach requires access to a whole state matrix (which is of size O(n^2)) for each of them. It can limit the size of solvable problemson special architectures with different available memory capacities such as Cell Broadband Engine Architecture (CBEA). The presented algorithm keeps only one pheromone matrix in the memory of a main unit. The matrix is updated by subsolutions computed by ACO on other units in parallel. We show that this approach performs significantly better than greedy algorithm, even though it generates the whole solution from solutions of subproblems.

Název v anglickém jazyce

Ant Colony Optimization with Parallel Subsolutions Heuristic

Popis výsledku anglicky

For solving N-complete Travelling Salesman Problem (TSP) by combining solutions of its subproblems, we designed algorithm inspired by Ant Colony Optimization (ACO) modified by adding parallel subsolutions heuristic. ACO can be parallelized simply by simultaneous execution of the algorithm with eventual exchange of the best solutions between all computational units. This approach requires access to a whole state matrix (which is of size O(n^2)) for each of them. It can limit the size of solvable problemson special architectures with different available memory capacities such as Cell Broadband Engine Architecture (CBEA). The presented algorithm keeps only one pheromone matrix in the memory of a main unit. The matrix is updated by subsolutions computed by ACO on other units in parallel. We show that this approach performs significantly better than greedy algorithm, even though it generates the whole solution from solutions of subproblems.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

European Simulation and Modelling Conference 2008

ISBN

978-90-77381-44-1

ISSN

—

e-ISSN

—

Počet stran výsledku

5

Strana od-do

—

Název nakladatele

EUROSIS - ETI

Místo vydání

Ghent

Místo konání akce

Le Havre

Datum konání akce

27. 10. 2008

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000264749400036