Development of Heterogeneous Parallel Genetic Simulated Annealing Using Multi-Niche Crowding

Authors: Z. G. Wang, M. Rahman, Y. S. Wong, K. S. Neo

Abstract:

In this paper, a new hybrid of genetic algorithm (GA) and simulated annealing (SA), referred to as GSA, is presented. In this algorithm, SA is incorporated into GA to escape from local optima. The concept of hierarchical parallel GA is employed to parallelize GSA for the optimization of multimodal functions. In addition, multi-niche crowding is used to maintain the diversity in the population of the parallel GSA (PGSA). The performance of the proposed algorithms is evaluated against a standard set of multimodal benchmark functions. The multi-niche crowding PGSA and normal PGSA show some remarkable improvement in comparison with the conventional parallel genetic algorithm and the breeder genetic algorithm (BGA).

Keywords: Crowding, genetic algorithm, parallel geneticalgorithm, simulated annealing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060467

References:

[1] J.H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press, 1975, ch.1.
[2] J.P. Li, M.E. Balazs, G.T. Parks, and P.J. Clarkson, "A species conserving genetic algorithm for multimodal function optimization," Evolutionary Computation, vol. 10, no. 3, pp. 207-234, Fall 2002.
[3] H. Chen, and N. Flann, "Parallel Simulated Annealing and Genetic Algorithms: A Space of Hybrid Methods," In Proc. Int-l Conf. Evolutionary computation − PPSN III, Lecture Notes in Computer Science, vol. 866, Berlin: Springer-Verlag, 1994, pp. 428-438.
[4] S.W. Mahfoud, and D.E. Goldberg, "Parallel recombinative simulated annealing: A genetic algorithm," Parallel Computing, vol. 21, no. 1, pp. 1-28, Jan. 1995.
[5] J.V. Varanelli, and J.C. Cohoon, "Population-Oriented Simulated Annealing: A Genetic/Thermodynamic Hybrid Approach to Optimization," in Proc. 6th Int-l Conf. Genetic Algorithms, M. Kaufman, San Francisco, Calif., 1995, pp. 174-181.
[6] H. Chen, N.S. Flann, and D.W. Watson, "Parallel genetic simulated annealing: a massively parallel SIMD algorithm," IEEE Transactions on Parallel and Distributed Systems, vol. 9, pp. 126-136, 1998.
[7] T. Hiroyasu, M. Miki, and M. Ogura, "Parallel Simulated Annealing using Genetic Crossover," in Proc. IASTED Int-l Conf. on Parallel and Distributed Computing Systems, Las Vegas, 2000, pp. 145-150.
[8] C. Baydar, "A hybrid parallel simulated annealing algorithm to optimize store performance," in Workshop on GECCO 2002, New York, 2002.
[9] K.A. De Jong, "An Analysis of the Behavior of a Class of Genetic Adaptive Systems," Ph.D. Thesis, University of Michigan, MI, 1975.
[10] D.E. Goldberg, Genetic algorithms in search, optimization and machine learning, Reading, Massachusetts: Addison -Wesley, 1989, pp. 1-145.
[11] W. Cedeno, and V.R. Vemuri, "Analysis of speciation and niching in the multi-niche crowding GA," Theoretical Computer Science, vol. 229, no. 1-2, pp. 177-197, 1999.
[12] J. Hesser, and R. Männer, "Towards an optimal mutation probability for genetic algorithms," in Proc. Parallel problem solving from nature: 1st workshop, PPSN I, Lecture Notes in Computer Science, vol. 496, Berlin: Springer-Verlag, 1991, pp. 23-32.
[13] E. Cant├║-Paz, Efficient and accurate parallel genetic algorithms, Boston: Kluwer Academic Publishers, 2000, pp. 1-119.
[14] E. Alba, and J.M. Troya, "A survey of parallel distributed genetic algorithms," Complexity, vol. 4, no. 4, pp. 31-52, 1999.
[15] D. Dumitrescu, B. Lazzerini, L.C. Jain, and A. Dumitrescu, Evolutionary computation. Boca Raton: CRC Press, 2000, pp. 187-211.
[16] H. M├╝hlenbein, and D. Schlierkamp-Voosen, "Predictive models for the breeder genetic algorithm I. Continuous parameter optimization," Evolutionary Computation, vol. 1, no. 1, pp. 25-49, 1993.
[17] Th. Bäck, F. Hoffmeister, and H.-P. Schwefel, "A Survey of evolution strategies," in Proc. Fourth Int-l Conf. Genetic Algorithms. M. Kaufmann, San Mateo, Calif., 1991, pp. 2-9.
[18] T.B. Trafalis, and S. Kasap, "A novel metaheuristics approach for continuous global optimization," Journal of Global Optimization, vol. 23, no. 2, pp. 171-190, 2002.
[19] Z.G. Wang, Y.S. Wong and M. Rahman, "Development of a parallel optimization method based on genetic simulated annealing algorithm," Parallel Computing, vol. 31, no. 8-9, pp. 839-857, 2005.
[20] A.O. Griewank, "Generalized descent for global optimization," Journal of Optimization Theory and Applications, vol. 34, pp. 11-39, 1981.
[21] H. M├╝hlenbein, M. Schomisch, and J. Born, "The parallel genetic algorithm as function optimizer," Parallel Computing, vol. 17, pp. 619- 632, 1991.