Ant Colony Optimization with Parallel Subsolutions Heuristic

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Ant Colony Optimization with Parallel Subsolutions Heuristic
Original language description
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.
Czech name
—
Czech description
—

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

Article name in the collection
European Simulation and Modelling Conference 2008
ISBN
978-90-77381-44-1
ISSN
—
e-ISSN
—
Number of pages
5
Pages from-to
—
Publisher name
EUROSIS - ETI
Place of publication
Ghent
Event location
Le Havre
Event date
Oct 27, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000264749400036

Similar results(10)