Generational PipeLined Genetic Algorithm (PLGA)using Stochastic Selection

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.

Authors:

• Malay K. Pakhira
• Rajat K. De

Keywords:

• Hardware evaluation
• Hardware pipeline
• Optimization
• Pipelined genetic algorithm
• SA-selection.

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.