Generational PipeLined Genetic Algorithm (PLGA)using Stochastic Selection

Authors: Malay K. Pakhira, Rajat K. De

Abstract:

In this paper, a pipelined version of genetic algorithm, called PLGA, and a corresponding hardware platform are described. The basic operations of conventional GA (CGA) are made pipelined using an appropriate selection scheme. The selection operator, used here, is stochastic in nature and is called SA-selection. This helps maintaining the basic generational nature of the proposed pipelined GA (PLGA). A number of benchmark problems are used to compare the performances of conventional roulette-wheel selection and the SA-selection. These include unimodal and multimodal functions with dimensionality varying from very small to very large. It is seen that the SA-selection scheme is giving comparable performances with respect to the classical roulette-wheel selection scheme, for all the instances, when quality of solutions and rate of convergence are considered. The speedups obtained by PLGA for different benchmarks are found to be significant. It is shown that a complete hardware pipeline can be developed using the proposed scheme, if parallel evaluation of the fitness expression is possible. In this connection a low-cost but very fast hardware evaluation unit is described. Results of simulation experiments show that in a pipelined hardware environment, PLGA will be much faster than CGA. In terms of efficiency, PLGA is found to outperform parallel GA (PGA) also.

Keywords: Hardware evaluation, Hardware pipeline, Optimization, Pipelined genetic algorithm, SA-selection.

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

References:

[1] J. Holland, Adaptation in Neural and Artificial Systems. Ann. Arbor, MI: University of Michigan, 1975.
[2] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. New York: Addison-Wesley, 1989.
[3] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. New York: Springer-Verlag, 1992.
[4] T. Bach, F. Hoffmeister, and H. P. Schwefel, "A survey of evolution strategies," in Proc of Fourth international conference on genetic algorithms, pp. 2-9, San Mateo, CA: Morgan Kaufmann, 1991.
[5] J. J. Grefenstette, "Optimization of control parameters for genetic algorithms," IEEE Trans. on Syst., Man and Cybern., vol. 16, pp. 122-128, 1986.
[6] H. M¨uhlenbein, M. Scomisch, and J. Born, "The parallel genetic algorithm as function optimizer," in Proc. of Fourth Intl. Conf. on Genetic Algorithms, pp. 271-278, San Mateo, Calif: Morgan Kaufmann, 1991.
[7] V. S. Gordon and D. Whitley, "Serial and parallel genetic algorithms as function optimizers," in Proc. of the Fifth International Conference on Genetic Algorithms, (Morgan Kaufmann, San Mateo, CA), pp. 177-183, 1993.
[8] S. Baluja, "Structure and performance of fi ne-grain parallelism in genetic search," in Proc. of the Fifth International Conference on Genetic Algorithms, (Morgan Kaufmann, San Mateo, CA), pp. 155-162, 1993.
[9] R. Shonkwiler, "Parallel genetic algorithms," in Proc. of 5th Intl. Conf. on Genetic Algorithms, pp. 199-205, San Mateo, CA: Morgan Kaufmann, 1993.
[10] E. Cant'u-Paz, "A survey of parallel genetic algorithms," tech. rep., University of Illinois, Illinois GA Laboratory, Urbana Champaign, Urbana, IL, 1997.
[11] E. Cant'u-Paz, "On scalability of parallel genetic algorithms," Evolutionary Computation, vol. 7, no. 4, pp. 429-449, 1999.
[12] E. Cant'u-Paz, Effective and Accurate Parallel Genetic Algorithms. Kluwer Academic Publishers, 2000.
[13] S. Kirkpatrik, C. Gellat, and M.P.Vecchi, "Optimization by simulated annealing," Science, vol. 220, pp. 671-680, 1983. Upper Saddle River, NJ: Prentice Hall PTR, 1999.
[14] L. Yong, K. Lishan, and D. J. Evans, "The annealing evolution algorithm as function optimizer," Parallel Computing, vol. 21, pp. 389-400, 1995.
[15] A. Pr¨ugel-Bennett and J. L. Shapiro, "Analysis of genetic algorithms using statistical mechanics," Physical Review Letters, vol. 72, no. 9, pp. 1305-1309, 1994.
[16] D. E. Goldberg, "A note on boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing," Complex Systems, vol. 4, pp. 445-460, 1990.
[17] B. T. Zhang and J. J. Kim, "Comparison of selection methods for evolutionary optimization," Evolutionary Optimization, vol. 2, no. 1, pp. 55-70, 2000.
[18] P. Martin, "A pipelined hardware implementation of Genetic Programming using FPGAs and Handle-C," tech. rep., University of Essex, Department of Computer Science, Colchester, UK, 2002.
[19] M. Tommiska and J. Vuori, "Implementation of genetic algorithms with programmable logic devices," in Proc. of the 2NWGA, pp. 71-78, 1996.
[20] S. D. Scott, A. Samal and S. Seth, "HGA: A Hardware-Based Genetic Algorithm", in Intl. Symposium on Field-Programmable Gate Array, pp. 53-59, 1995.
[21] I. M. Bland and G. M. Megson, "Effi cient operator pipelining in a bit serial genetic algorithm engine," Electronic Letters, vol. 33, pp. 1026- 1028, 1997.
[22] M. K. Pakhira and R. K. De, "A hardware pipeline for function optimization using genetic algorithms," in Proc. of Genetic and Evolutionary Computation Conference (GECCO - 05), (Washington DC, USA), pp. 949-956, 2005.
[23] M. K. Pakhira, "Postfi x hardware evaluation unit for genetic algorithms: Application in fuzzy clustering," in Proc. of Intl.conf. on Advanced Computing and Communications (ADCOM - 06), (Mangalore, INDIA), pp. 357-360, 2006.
[24] M. K. Pakhira, "Genetic evaluation in hardware: Application in fuzzy clustering," accepted in Foundations of Computing and Decision Sciences, 2007 (to appear).
[25] J. L. R. Filho, P. C. Treleaven, and C. Alippi, "Genetic algorithm programming environments," IEEE Computer, pp. 28-43, June, 1994.
[26] M. D. Vose, The simple Genetic Algorithms: Foundations and Theory (Complex Adaptive Systems). New York: The MIT Press, 1999.
[27] D. D. Cox and S. John, "SDO: A statistical method for global optimization," in Multidisciplinary Design Optimization (Hampton, VA), 1995, pp. 315-329, Philadelphia, PA: SIMA, 1997.