Efficiency of parallel metaheuristics for solving combinatorial problems

ABSTRACT

The paper investigates the speedup and quality of solution of parallel metaheuristics on multicomputer platform for the case studies of parallel genetic computation for solving the TSP and solving the room assignment problem by parallel simulated annealing. Parallel computational models have been suggested for solving the TSP by genetic approach with chromosome migration (SPMD paradigm) and for solving the room assignment problem by simulated annealing (manager/workers paradigm). The experimental study is based on flat (MPI-based) parallel program implementations on multicomputer platform. Performance and scalability analysis have been made in respect to the application size and multicomputer size. The impact of various factors on the quality of solutions have been investigated and presented.

REFERENCES

• 1: Aarts E., J. Korst, P. van Laarhoven, Simulated Annealing, in Aarts E., J. Lenstra, eds., Local Search in Combinatorial Optimization, John Wiley and Sons, 1997.
• 2: Abdennadher S., M. Marte, University course timetabling using constraint handling rules. Journal of Applied Artifficial Intelligence, Vol.14, no.4, pp.311÷326, 2000.
• 3: Borovska P., S. Bahudaila, Impact of the Mutation Strategy on the Solution Quality of Parallel Genetic Algorithm with Circular Migration, in Proceedings of International Scientific Conference Computer Science'2006, 12--15 October, Istanbul, 2006.
• 4: Der-Rong Din , Shian-Shyong Tseng, A Simulated Annealing Algorithm for Extended Cell Assignment Problem in a Wireless ATM Network, Proceedings of the EvoWorkshops on Applications of Evolutionary Computing, p.150-160, April 18-20, 2001
• 5: David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning, Operations Research, v.39 n.3, p.378-406, May-June 1991 [doi>10.1287/opre.39.3.378]
• 6: Martinez-Alfaro H., J. Minero, G. Alanis, N. Leal, I. Avila, Using Simulated Annealing to Solve the Classroom Assignment Problem, Proc. of ISAI/IFIS Int. Conference on Intelligent Systems Technologies, pp.370÷377, 1996.
• 7: Osman I., Heuristics for the Generalized Assignment Problem: Simulated Annealing and Tabu Search Approaches, Journal Operational Research Spectrum, Vol.17, No.4, pp.211÷225, 1995.
• 8: Wang L., A. Maciejewski, H. Siegel, V. Roychowdhury, B. Eldridge, A Study of Five Parallel Approaches to a Genetic Algorithm for the TSP, in Intelligent Automation and Soft Computing, Vol.11, No.4, pp.217--234, 2005.
• 9: Albert Y. Zomaya , Michael Wright, Observations on Using Genetic-Algorithms for Channel Allocation in Mobile Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.9, p.948-962, September 2002 [doi>10.1109/TPDS.2002.1036068]

INDEX TERMS

Keywords:
combinatorial problems, evolutionary computing, optimization, parallel computing, parallel metaheuristics, simulated annealing