Advances in parallel heterogeneous genetic algorithms for continuous optimization

• Autorzy: Alba E. , Luna F. , Nebro A. J.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

parallel genetic algorithms; continuous optimization; premature convergence; heterogeneity

PL

algorytm genetyczny; optymalizacja ciągła; konwergencja przedwczesna

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2004
• Tom: Vol. 14, no 3
• Strony: 317--333
• Opis fizyczny: Bibliogr. 50 poz., rys., tab., wykr.

Twórcy

autor

Alba E.

• Dpto. de Lenguajes y Ciencias de la Computación, Universidad de Málaga. E.T.S.I. Informática, Campus de Teatinos, 29071 Málaga, Spain

autor

Luna F.

• Dpto. de Lenguajes y Ciencias de la Computación, Universidad de Málaga. E.T.S.I. Informática, Campus de Teatinos, 29071 Málaga, Spain

autor

Nebro A. J.

• Dpto. de Lenguajes y Ciencias de la Computación, Universidad de Málaga. E.T.S.I. Informática, Campus de Teatinos, 29071 Málaga, Spain

Bibliografia

• [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. Fernández-Villacañas and 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. 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.
• [5] Alba E., Luna F., Nebro A.J. and Troya J.M. (2004): Parallel heterogeneous genetic algorithms for continuous optimization.— Parallel Comput., (to appear).
• [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.
• [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.
• [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. Fernández-Villacañas and H.-P. Schwefel, Eds.). — Granada, Spain: Springer, pp. 665–675.
• [12] Bäck T. (1992): Self-Adaptation in Genetic Algorithms.—Proc. 1st Europ. Conf. Artificial Life, Cambridge, MA, pp. 263–271.
• [13] Bäck T. (1996): Evolutionary Algorithms in Theory and Practice.— Oxford: Oxford University Press.
• [14] Bäck T., Fogel D.B. and Michalewicz Z. (1997): Handbook of Evolutionary Computation. — Oxford: Oxford University Press.
• [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] Cantú-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.
• [21] Goldberg D.E., Kargupta H., Horn J. and Cantú-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 realcoded 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): Fine-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.
• [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] Mühlenbein 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.
• [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 Mühlenbein H. (1994): Strategy adaptation by competing subpopulations, In: Parallel Problem Solving from Nature (PPSN III) (Y. Davidor, H.-P. Schwefel and R. Männer, Eds.). — Berlin: Springer, pp. 199–208.
• [39] Schlierkamp-Voosen D. and Mühlenbein 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 Périaoux 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.
• [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] Töorn A. and Antanas Ž. (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´c 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.
• [50] Yi W., Liu Q. and He Y. (2000): Dynamic distributed genetic algorithms. — Proc. Congress Evolutionary Computation, La Jolla, USA, pp. 1132–1136.