Home |  ENGLISH |  Kontakt |  Impressum |  Datenschutz |  Anmelden |  KIT


Aus Aifbportal

Wechseln zu: Navigation, Suche

On Enforced Convergence of ACO and its Implementation on the Reconfigurable Mesh Architecture Using Size Reduction Tasks

Veröffentlicht: 2003 November

Journal: Journal on Supercomputing
Nummer: 3
Seiten: 221-238
Verlag: ACM
Volume: 26

Referierte Veröffentlichung


In this paper we show that size reduction tasks can be used for executing iterative randomized metaheuristics on runtime reconfigurable architectures so that an improved throughput and better solution qualities are obtained compared to conventional architectures that do not allow runtime reconfiguration. In particular, the problem of executing ant colony optimization (ACO) algorithms on a dynamically reconfigurable mesh architecture is studied. It is shown how ACO can be implemented such that the convergence behavior of the algorithm can be used to dynamically reduce the size of the submesh that is needed for execution. Furthermore we propose a method to enforce the convergence of ACO leading to a faster reduction process. This increases the throughput of ACO algorithms on runtime reconfigurable meshes. The increased throughput is used for repeated runs of ACO algorithms on a given set of problem instances which significantly improves the obtained solution quality.




Effiziente Algorithmen