Affiliations: Department of Information Systems, Faculty of Computer Science and Management, Wroclaw University of Technology, Wrocław, Poland
Correspondence:
[*]
Corresponding author. Andrzej Siemiński, Department of Information Systems, Faculty of Computer Science and Management, Wroclaw University of Technology, Wybrzeże, Wyspiańskiego 27, 50-370 Wrocław, Poland. Tel.: +48 71 320 3799; Fax: +48 71 320 3884; E-mail: [email protected].
Abstract: The paper presents a study on the efficiency of Ant Colony Communities (ACC) used to solve the Travelling Salesman Problem. The ACC is an approach to parallelize the Ant Colony Optimization algorithm (ACO). An ACC is made up of a Community Server that coordinates the work of a set ant colony clients. Each client implements a classical ACO algorithm. The individual colonies process cargos of data obtained from the server and send them back the as partial results. The paper presents a general description of the ACC concept and describes in details two ways of implementing it. The first one uses an inhomogeneous environment of traditional computers working in an asynchronous mode. The second one uses the homogenous Hadoop environment and the processing is done in a synchronized mode. The performance of the Communities is estimated by low level measures: their power and scalability. The high level measure deals with the length of obtained routes. The paper presents also the taxonomy of parallel implementations of the Ant Colony Optimization.
Keywords: Ant Colony Optimization, Travelling Salesman Problem, ACO parallel implementations, sockets, Hadoop, MapReduce, scalability, computational power
