Development of Heterogeneous Parallel Genetic Simulated Annealing Using Multi-Niche Crowding
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).
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:54219", author = "Z. G. Wang and M. Rahman and Y. S. Wong and K. S. Neo", title = "Development of Heterogeneous Parallel Genetic Simulated Annealing Using Multi-Niche Crowding", 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.", volume = "1", number = "10", pages = "3052-8", }
