Advances in parallel heterogeneous genetic algorithms for continuous optimization

Enrique Alba; Francisco Luna; Antonio Nebro

International Journal of Applied Mathematics and Computer Science (2004)

  • Volume: 14, Issue: 3, page 317-333
  • ISSN: 1641-876X

Abstract

top
In this paper we address an extension of a very efficient genetic algorithm (GA) known as Hy3, a physical parallelization of the gradual distributed real-coded GA (GD-RCGA). This search model relies on a set of eight subpopulations residing in a cube topology having two faces for promoting exploration and exploitation. The resulting technique has been shown to yield very accurate results in continuous optimization by using crossover operators tuned to explore and exploit the solutions inside each subpopulation. We introduce here a further extension of Hy3, called Hy4, that uses 16 islands arranged in a hypercube of four dimensions. Thus, two new faces with different exploration/exploitation search capabilities are added to the search performed by Hy3. We analyze the importance of running a synchronous versus an asynchronous version of the models considered. The results indicate that the proposed Hy4 model overcomes the Hy3 performance because of its improved balance between exploration and exploitation that enhances the search. Finally, we also show that the async Hy4 model scales better than the sync one.

How to cite

top

Alba, Enrique, Luna, Francisco, and Nebro, Antonio. "Advances in parallel heterogeneous genetic algorithms for continuous optimization." International Journal of Applied Mathematics and Computer Science 14.3 (2004): 317-333. <http://eudml.org/doc/207700>.

@article{Alba2004,
abstract = {In this paper we address an extension of a very efficient genetic algorithm (GA) known as Hy3, a physical parallelization of the gradual distributed real-coded GA (GD-RCGA). This search model relies on a set of eight subpopulations residing in a cube topology having two faces for promoting exploration and exploitation. The resulting technique has been shown to yield very accurate results in continuous optimization by using crossover operators tuned to explore and exploit the solutions inside each subpopulation. We introduce here a further extension of Hy3, called Hy4, that uses 16 islands arranged in a hypercube of four dimensions. Thus, two new faces with different exploration/exploitation search capabilities are added to the search performed by Hy3. We analyze the importance of running a synchronous versus an asynchronous version of the models considered. The results indicate that the proposed Hy4 model overcomes the Hy3 performance because of its improved balance between exploration and exploitation that enhances the search. Finally, we also show that the async Hy4 model scales better than the sync one.},
author = {Alba, Enrique, Luna, Francisco, Nebro, Antonio},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {premature convergence; heterogeneity; parallel genetic algorithms; continuous optimization},
language = {eng},
number = {3},
pages = {317-333},
title = {Advances in parallel heterogeneous genetic algorithms for continuous optimization},
url = {http://eudml.org/doc/207700},
volume = {14},
year = {2004},
}

TY - JOUR
AU - Alba, Enrique
AU - Luna, Francisco
AU - Nebro, Antonio
TI - Advances in parallel heterogeneous genetic algorithms for continuous optimization
JO - International Journal of Applied Mathematics and Computer Science
PY - 2004
VL - 14
IS - 3
SP - 317
EP - 333
AB - In this paper we address an extension of a very efficient genetic algorithm (GA) known as Hy3, a physical parallelization of the gradual distributed real-coded GA (GD-RCGA). This search model relies on a set of eight subpopulations residing in a cube topology having two faces for promoting exploration and exploitation. The resulting technique has been shown to yield very accurate results in continuous optimization by using crossover operators tuned to explore and exploit the solutions inside each subpopulation. We introduce here a further extension of Hy3, called Hy4, that uses 16 islands arranged in a hypercube of four dimensions. Thus, two new faces with different exploration/exploitation search capabilities are added to the search performed by Hy3. We analyze the importance of running a synchronous versus an asynchronous version of the models considered. The results indicate that the proposed Hy4 model overcomes the Hy3 performance because of its improved balance between exploration and exploitation that enhances the search. Finally, we also show that the async Hy4 model scales better than the sync one.
LA - eng
KW - premature convergence; heterogeneity; parallel genetic algorithms; continuous optimization
UR - http://eudml.org/doc/207700
ER -

References

top
  1. Adamidis P. and Petridis V. (1996): Co-operating populations with different evolution behaviors. -Proc. 3rd IEEE Conf. Evolutionary Computation, New York, pp. 188-191. 
  2. Adamidis P. and Petridis V. (2002): On modelling evolutionary algorithm implementations through co-operating populations, In: Parallel Problem Solving from Nature (PPSN VII), (J.J. Merelo Guervós, P. Adamidis, H.-G. Beyer, J.-L. Fernandez-Villaca nasand H.-P. Schwefel, Eds.). - Granada, Spain: Springer, pp. 321-330. 
  3. Aickelin U. and Bull L. (2002): Partnering strategies for fitness evaluation in a pyramidal evolutionary algorithm. -Proc. Genetic and Evolutionary Comput. Conf.s GECCO'02, New York, pp. 263-270. 
  4. Alba E., Luna E. and Nebro A.J. (2003): Parallel heterogeneous genetic algorithms for continuous optimization. -Int. Parallel and Distributed Proces. Symp. (IPDPS-NIDISC'03), Nice, France, p. 147. Zbl1180.90366
  5. Alba E., Luna F., Nebro A.J. and Troya J.M. (2004): Parallel heterogeneous genetic algorithms for continuous optimization. -Parallel Comput., (to appear). Zbl1180.90366
  6. Alba E., Nebro A.J. and Troya J.M. (2002): Heterogeneous computing and parallel genetic algorithms. -J. Parall, Distrib. Comput., Vol. 62, pp. 1362-1385. Zbl1063.68104
  7. Alba E. and Tomassini M. 2002): Parallelism and evolutionary algorithms. -IEEE Trans. Evolut. Comput., Vol. 6, No. 5, pp. 443-462. 
  8. Alba E. and Troya J.M. (1999): A survey of parallel distributed genetic algorithms. -Complexity, Vol. 4, No. 4, pp. 31-52. 
  9. Alba E. and Troya J.M. (2000): Influence of the migration policy in parallel distributed GAs with structured and panmictic populations. -Appl. Intell., Vol. 12, No. 3, pp. 163-181. 
  10. Alba E. and Troya J.M. (2001): Analyzing synchronous and asynchronous parallel distributed genetic algorithms. -Future Generat. Comput. Syst., Vol. 17, No. 4, pp. 451-465. Zbl1016.68177
  11. Arenas M.G., Collet P., Eiben A.E., Jelasity M., Merelo J.J., Paechter B., Preub M. and Schoenauer M. (2002): A framework for distributed evolutionary algorithms, In: Parallel Problem Solving from Nature (PPSN VII) (J.J. Merelo Guervós, P. Adamidis, H.-G. Beyer, J.-L. Fernandez-Villacañas and H.-P. Schwefel, Eds.). - Granada, Spain: Springer, pp. 665-675. 
  12. Back T. (1992): Self-Adaptation in Genetic Algorithms. -Proc. 1st Europ. Conf. Artificial Life, Cambridge, MA, pp. 263-271. 
  13. Back T. (1996): Evolutionary Algorithms in Theory and Practice. -Oxford: Oxford University Press. Zbl0877.68060
  14. Back T., Fogel D.B. and Michalewicz Z. (1997): Handbook of Evolutionary Computation. -Oxford: Oxford University Press. Zbl0883.68001
  15. Baker J.E. (1985): Adaptive selection methods for genetic algorithms. -Proc. 1st Int. Conf. Genetic Algorithms Appl., Hillsdale, NJ, pp. 101-111. 
  16. Baker J.E. (1987): Reducing bias and inefficiency in the selection algorithm. -Proc. 2nd Int. Conf. Genetic Algorithms Appl., Hillsdale, NJ, pp. 14-21. 
  17. Cantu-Paz E. (1995): A summary of research on parallel genetic algorithms. - Tech. Rep. No. 95007, Univ. Illinois, Urbana-Champaign, Illinois GA Laboratory. 
  18. de Jong K.A. (1975): An analysis of the behavior of a class of genetic adaptive Systems. - Ph.D. thesis, Univ. Michigan, Ann Arbor. 
  19. Eshelman L.J., Mathias K.E. and Schaffer J.D. (1997): Convergence controlled variation, In: Foundations of Genetic Algorithms 4 (R. Belew and M. Vose, Eds.). - San Mateo, CA: Morgan Kaufmann, pp. 203-224. 
  20. Goldberg D.E. (1989): Genetic Algorithms in Search, Optimization and Machine Learning. - Boston: Addison-Wesley. Zbl0721.68056
  21. Goldberg D.E., Kargupta H., Horn J. and Cantu-Paz E. (1995): Critical deme size for serial and parallel genetic algorithms. - Tech. Rep. No. 95002, Univ. Illinois, Urbana-Campaign, Illinois Genetic Algorithms Laboratory. 
  22. Griewangk A.O. (1981): Generalized descent of global optimization. -J. Optim. Theory Appl., Vol. 34, No. 3, pp. 11-39. 
  23. Herrera F. and Lozano M. (1997): Heterogeneous distributed genetic algorithms based on the crossover operator. -Proc. 2nd IEE/IEEE Int. Conf. Genetic Algorithms Eng. Syst.: Innovations Appl., Glasgow, UK, pp. 203-208. 
  24. Herrera F. and Lozano M. (2000): Gradual distributed real-coded genetic algorithms. -IEEE Trans. Evolut. Comput., Vol. 4, No. 1, pp. 43-63. 
  25. Herrera F., Lozano M. and Moraga C. (1998): Hybrid distributed real-coded genetic algorithms, In: Parallel Problem Solving from Nature (PPSN V) (A.E. Eiben, T. Back, M. Schoenauer and H-P. Schwefel, Eds.). - Amsterdam: Springer, pp. 879-888. 
  26. Herrera F., Lozano M. and Verdegay J.L. (1995): Fuzzy connective based crossover operators to model genetic algorithms population diversity. - Tech. Rep. No. DECSAI-95110, University of Granada, 18071 Granada, Spain. 
  27. Hinterding R., Michalewicz Z. and Peachey T.C. (1996): Self-adaptive genetic algorithm for numeric functions, In: Parallel Problem Solving from Nature (PPSN IV) (H.-M. Voigt, W. Ebeling, I. Rechenberger and H.-P. Schwefel, Eds.). -Berlin: Springer, pp. 420-429. 
  28. Hiroyasu T., Miki M. and Negami M. (1999): Distributed genetic algorithms with randomized migration rate. -Proc. IEEE Conf. Systems, Man and Cybernetics, Tokyo, Japan, Vol. 1, pp. 689-694. 
  29. Holland J.H. (1997): Adaptation in natural and artificial systems. - Ph.D. thesis, Univ. Michigan, Ann Arbor. 
  30. Hu J.J. and Goodman E.D. (2002): The hierarchical fair competition (HFC) model for parallel evolutionary algorithms. -Proc. Congress Evolutionary Computation, CEC2002, Honolulu, USA, pp. 49-54. 
  31. Lin S.-L., Punch III W.F. and Goodman E.D. (1994): Coarse-grain parallel genetic algorithms: Categorization and new approach. -Proc. 6th IEEE Symp. Parallel and Distributed Processing, Dallas, USA, , pp. 28-37. 
  32. Manderick B. and Spiessens P. (1989): Finite-grained parallel genetic algorithms. -Proc. 3rd Int. Conf. Genetic Algorithms, Virginia, USA, pp. 428-433. 
  33. Michalewicz Z. (1992): Genetic Algorithms + Data Structures = Evolution Programs. -Berlin: Springer. Zbl0763.68054
  34. Miki M., Hiroyasu T., Kaneko M. and Hatanaka K. (1999): A parallel genetic algorithm with distributed environment scheme. -Proc. IEEE Conf. Systems, Man and Cybernetics, Tokyo, Japan, pp. 695-700. 
  35. Muhlenbein H., Schomisch M. and Born J. (1991): The parallel genetic algorithm as function optimizer. -Proc. 4th Int. Conf. Genetic Algorihtms, San Mateo, CA, pp. 271-278. Zbl0735.65040
  36. Oh S.-K, Lee C.-Y. and Lee J.-J. A new distributed evolutionary algorithm for optimization in nonstationary environments. -Proc. Congr. Evolutionary Computation, Honolulu, USA, pp. 378-383. 
  37. Potts J.C., Giddens T.D. and Yadav S.B. (1994): The development and evaluation of an improved genetic algorithm based on migration and artificial selection. -IEEE Trans. Syst. Man Cybern., Vol. 24, No. 1, pp. 73-86. 
  38. Schlierkamp-Voosen D. and Muhlenbein H. (1994): Strategy adaptation by competing subpopulations, In: Parallel Problem Solving from Nature (PPSN III) (Y. Davidor, H.-P. Schwefel and R. Manner, Eds.). -Berlin: Springer, pp. 199-208. 
  39. Schlierkamp-Voosen D. and Muhlenbein H. (1996): Adaptation of population sizes by competing subpopulations. -Proc. Int. Conf. Evolutionary Computation, Nagoya, Japan, pp. 199-208. 
  40. Schnecke V. and Vornberger O. (1996): An adaptive parallel algorithm for VLSI-layout optimization, In: Parallel Problem Solving from Nature (PPSN IV) (H.-M. Voigt, W. Ebeling, I. Rechenberger and H.-P. Schwefel, Eds.). - Berlin: Springer, pp. 22-27. 
  41. Schwefel H.-P. (1981): Numerical Optimization of Computer Models. -Chichester: Wiley. 
  42. Sefrioui M. and Periaoux J. (2000): A hierarchical genetic algorithm using multiple models for optimization, In: Parallel Problem Solving from Nature (PPSN VI) (M. Schoenauer, Kalyanmoy Deb, G. Rudolph, X. Yao, E. Lutton, J.J. Merelo and H.-P. Schwefel, Eds.). - Paris: Springer, pp. 879-888. 
  43. Storn R. and Price K. (1995): Differential evolution - A simple efficient adaptive scheme for global optimization over continuous spaces. - Tech. Rep. No. 95-012, Int. Compt. Sci. Inst., Berkeley, CA. Zbl0888.90135
  44. Tierra Home Page: www.hip.atr.co.jp/~ray/tierra/tierra.html. 
  45. Tanese R. (1989): Distributed genetic algorithms. -Proc. 3rd Int. Conf. Genetic Algorithms, Virginia, USA, pp. 434-439. 
  46. Toorn A. and Antanas Z. (1989): Global Optimization. - Berlin: Springer. 
  47. Tsutsui S. and Fujimoto Y. (1993): Forking genetic algorithm with blocking and shrinking modes (fGA). -Proc. 5th Int. Conf. Genetic Algorithms, Urbana-Champaign, USA, pp. 206-213. 
  48. Venkateswaran R., Obradović Z. and Raghavendra C.S. (1996): Cooperative genetic algorithm for optimization problems in distributed computer systems. -Proc. 2nd Online Workshop Evolutionary Computation, Nagoya, Japan, pp. 49-52 
  49. Whitley D., Beveridge R., Graves C. and Mathias K. (1995): Test driving three 1995 genetic algorithms: New test functions and geometric matching. -J. Heuristics, Vol. 1, pp. 77-104. Zbl0853.68106
  50. Yi W., Liu Q. and He Y. (2000): Dynamic distributed genetic algorithms. -Proc. Congress Evolutionary Computation, La Jolla, USA, pp. 1132-1136. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.