A Genetic Algorithm with Weighted Average Normally-Distributed Arithmetic Crossover and Twinkling

ABSTRACT

Genetic algorithms have been extensively used as a global optimization tool. These algorithms, however, suffer from their generally slow convergence rates. This paper proposes two approaches to address this limitation. First, a new crossover technique, the weighted average normally-distributed arithmetic crossover (NADX), is introduced to enhance the rate of convergence. Second, twinkling is incorporated within the crossover phase of the genetic algorithms. Twinkling is a controlled random deviation that allows only a subset of the design variables to undergo the decisions of an optimization algorithm while maintaining the remaining variable values. Two twinkling genetic algorithms are proposed. The proposed algorithmsare compared to simple genetic algorithms by using various mathematical and engineering design test problems. The results show that twinkling genetic algorithms have the ability to consistently reach known global minima, rather than nearby sub-optimal points, and are able to do this with competitive rates of convergence.

Genetic algorithms have been extensively used as a global optimization tool. These algorithms, however, suffer from their generally slow convergence rates. This paper proposes two approaches to address this limitation. First, a new crossover technique, the weighted average normally-distributed arithmetic crossover (NADX), is introduced to enhance the rate of convergence. Second, twinkling is incorporated within the crossover phase of the genetic algorithms. Twinkling is a controlled random deviation that allows only a subset of the design variables to undergo the decisions of an optimization algorithm while maintaining the remaining variable values. Two twinkling genetic algorithms are proposed. The proposed algorithmsare compared to simple genetic algorithms by using various mathematical and engineering design test problems. The results show that twinkling genetic algorithms have the ability to consistently reach known global minima, rather than nearby sub-optimal points, and are able to do this with competitive rates of convergence.

KEYWORDS

Genetic Algorithms; Crossover Techniques; Twinkling; Engineering Design; Global Optimization

Genetic Algorithms; Crossover Techniques; Twinkling; Engineering Design; Global Optimization

Cite this paper

G. Ladkany and M. Trabia, "A Genetic Algorithm with Weighted Average Normally-Distributed Arithmetic Crossover and Twinkling,"*Applied Mathematics*, Vol. 3 No. 10, 2012, pp. 1220-1235. doi: 10.4236/am.2012.330178.

G. Ladkany and M. Trabia, "A Genetic Algorithm with Weighted Average Normally-Distributed Arithmetic Crossover and Twinkling,"

References

[1] D. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley Reading, Boston, 1989.

[2] K. Deb and R. Agrawal, “Simulated Binary Crossover for Continuous Search Space,” Complex Systems, Vol. 9, 1995, pp. 115-148.

[3] I. Ono and S. Kobayashi, “A Real Coded Genetic Algorithm for Function Optimization Using Unimodal Normal Distribution Crossover,” Proceedings of the 7th International Conference on Genetic Algorithms, Vol. 14, No. 6, 1997, pp. 246-253.

[4] F. Herrera, M. Lozano and J. Verdegay, “Fuzzy Connectives Based Crossover Operators to Model Genetic Algorithms Population Diversity,” Fuzzy Sets and Systems, Vol. 92, No. 1, 1997, pp. 21-30. doi:10.1016/S0165-0114(96)00179-0

[5] F. Herrera, M. Lozano and A. Sanchez, “Taxonomy for the Crossover Operator for Real-Coded Genetic Algorithms: an Experimental Study,” International Journal of Intelligent Systems, Vol. 18, No. 3, 2003, pp. 309-338. doi:10.1002/int.10091

[6] H. Ishibuchi, N. Yamamoto, T. Murata and H. Tanaka, “Genetic Algorithms and Neighborhood Search Algorithms for Fuzzy Flowshop Problems,” Fuzzy Sets and Systems, Vol. 67, No. 1, 1994, pp. 81-100. doi:10.1016/0165-0114(94)90210-0

[7] D. Sotiropoulos, E. Stavropoulos and M. Vrahatis, “A New Hybrid Genetic Algorithm for Global Optimization,” Nonlinear Analysis, Vol. 30, No. 7, 1997. pp. 4529-4538. doi:10.1016/S0362-546X(96)00367-7

[8] J. Yen, J. Liao and D. Randolph, “A Hybrid Approach to Modeling Metabolic Systems Using a Genetic Algorithm and Simplex Method,” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 28, No. 2, 1998, pp. 173-191. doi:10.1109/3477.662758

[9] M. Okamoto, T., Nonaka, S. Ochiai and D. Tominaga, “Nonlinear Numerical Optimization with Use of a Hybrid Genetic Algorithm Incorporating the Modified Powell Method,” Applied Mathematics and Computation, Vol. 91, No. 1, 1998, pp. 63-72. doi:10.1016/S0096-3003(97)10007-8

[10] J. Renders and S. Flasse, “Hybrid Methods Using Genetic Algorithms for Global Optimization,” IEEE Transactions on Systems, Man and Cybernetic, Vol. 26, No. 2, 1999, pp. 243-258.

[11] W. Jwo, C. Liu and C. Liu, “Large-Scale Optimal VAR Planning by Hybrid Simulated Annealing/Genetic Algorithm,” International Journal of Electrical Power & Energy Systems, Vol. 21, No. 1, 1999, pp. 39-44. doi:10.1016/S0142-0615(98)00020-9

[12] M. Musil, M. Wilmut and N. Chapman, “A Hybrid Simplex Genetic Algorithm for Estimating Geoacoustic Parameters Using Matched-Field Inversion,” IEEE Journal of Oceanic Engineering, Vol. 24, No. 3, 1999, pp. 358-369. doi:10.1109/48.775297

[13] A. Nassef, H. Hegazi and S. Metwalli, “A Hybrid Genetic Direct Search Algorithm for Global Optimization of Solid C-Frame Cross Sections,” Proceedings of the 26th Design Automation Conference, Baltimore, 11-13 September 2000.

[14] K. Hacker, J. Eddy and K. Lewis, “Tuning a Hybrid Optimization Algorithm by Determining the Modality of the Design Space,” Proceedings of the 27th Design Automation Conference, Pittsburgh, 9-12 September 2001, pp. 773-782.

[15] M. Trabia, “A Hybrid Fuzzy Simplex Genetic Algorithm,” Journal of Mechanical Design, Vol. 126, No. 6, 2004, pp. 969-974. doi:10.1115/1.1803852

[16] Y. Tenne and S. Armfield, “A Novel Evolutionary Algorithm for Efficient Minimization of Expensive Black-Box Functions with Assisted-Modelling,” IEEE Congress on Evolutionary Computation, Vancouver, 11 September 2006, pp. 3220-3226.

[17] H. Telega, “Two-Phase Stochastic Global Optimization Strategies,” Studies in Computational Intelligence, Vol. 74, 2007, pp. 153-197. doi:10.1007/978-3-540-73192-4_6

[18] M. Mekhilef, “A Twinkling Technique for Brownian Moves in Optimization,” Proceedings of the 25th Design Automation Conference, Las Vegas, 12-16 September 1999.

[19] M. Mekhilef, “Introducing the Twinkling Technique in Non-Linear Optimization,” Proceedings of the 26th Design Automation Conference, Baltimore, 10-13 September 2000.

[20] M. Mekhilef and M. Trabia, “Successive Twinkling Simplex Search Optimization Algorithms,” Proceedings of the ASME 27th Design Automation Conference, Pittsburgh, 9-12 September 2001.

[21] M. Mekhilef, “Twinkling a Random Search Algorithm for Design Optimization,” ASME 31st Design Automation Conference, Long Beach, 24-28 September 2005, pp. 321-330.

[22] Z. Michalewicz, “Genetic Algorithms/Data Structure = Evolutionary Programs,” Springer-Verlag, New York, 1994.

[23] M. Gen and R. Cheng, “Genetic Algorithms & Engineering Optimization,” Wiley Interscience, New York, 2000.

[24] R. Kasat and K. Gupta, “Multi-Objective Optimization of an Industrial Fluidized-Bed Catalytic Cracking Unit (FCCU) Using Genetic Algorithm (GA) with the Jumping Genes Operator,” Computers and Chemical Engineering, Vol. 27, No. 12, 2003, pp. 1785-1800. doi:10.1016/S0098-1354(03)00153-4

[25] M. Arakawa, T. Mayashita and H. Ishikawa, “Genetic Range Genetic Algorithms to Obtain Quasi-Optimum Solutions,” ASME 29th Design Automation Conference, Chicago, 2-6 September 2003, pp. 927-934.

[26] Z. Michalewicz, “Genetic Algorithms, Numerical Optimization, and Constraints,” Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, 15-19 July 1995, pp. 151-158.

[27] S. Rao, “Engineering Optimization: Theory and Practice,” Wiley-Interscience, New York, 1996.

[28] V. Rekalitis, A. Ravindaran and K. Ragsdell, “Engineering Optimization: Methods and Applications,” Wiley Interscience, New York, 2006.

[29] S. He, E. Prempain and Q. Wu, “An Improved Particle Swarm Optimizer for Mechanical Design Optimization Problems,” Engineering Optimization, Vol. 36, No. 5, 2004, pp. 585-605. doi:10.1080/03052150410001704854

[30] J. Wang and Z. Yin, “A Ranking Selection-Based Particle Swarm Optimizer for Engineering Design Optimization Problems,” Structural Multidisclinary Optimization, Vol. 37, No. 2, 2008, pp. 131-147. doi:10.1007/s00158-007-0222-3

[31] C. Coello, “Use of a Self-Adaptive Penalty Approach for Engineering Optimization Problems,” Computers in Industry, Vol. 41, No. 2, 2000, pp. 113-127.

[32] S. Kitayama, M. Arakawa and K. Yamazaki, “Penalty Function Approach for the Mixed Discrete Nonlinear Problems by Particle Swarm Optimization,” Structural Multidisclinary Optimization, Vol. 32, No. 3, 2006, pp. 191-202. doi:10.1007/s00158-006-0021-2

[33] Q. He and L. Wang, “A Hybrid Particle Swarm Optimization with a Feasibility-Based Rule for Constrained Optimization,” Applied Mathematics and Computation, Vol. 86, No. 2, 2007, pp. 1407-1422. doi:10.1016/j.amc.2006.07.134

[1] D. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley Reading, Boston, 1989.

[2] K. Deb and R. Agrawal, “Simulated Binary Crossover for Continuous Search Space,” Complex Systems, Vol. 9, 1995, pp. 115-148.

[3] I. Ono and S. Kobayashi, “A Real Coded Genetic Algorithm for Function Optimization Using Unimodal Normal Distribution Crossover,” Proceedings of the 7th International Conference on Genetic Algorithms, Vol. 14, No. 6, 1997, pp. 246-253.

[4] F. Herrera, M. Lozano and J. Verdegay, “Fuzzy Connectives Based Crossover Operators to Model Genetic Algorithms Population Diversity,” Fuzzy Sets and Systems, Vol. 92, No. 1, 1997, pp. 21-30. doi:10.1016/S0165-0114(96)00179-0

[5] F. Herrera, M. Lozano and A. Sanchez, “Taxonomy for the Crossover Operator for Real-Coded Genetic Algorithms: an Experimental Study,” International Journal of Intelligent Systems, Vol. 18, No. 3, 2003, pp. 309-338. doi:10.1002/int.10091

[6] H. Ishibuchi, N. Yamamoto, T. Murata and H. Tanaka, “Genetic Algorithms and Neighborhood Search Algorithms for Fuzzy Flowshop Problems,” Fuzzy Sets and Systems, Vol. 67, No. 1, 1994, pp. 81-100. doi:10.1016/0165-0114(94)90210-0

[7] D. Sotiropoulos, E. Stavropoulos and M. Vrahatis, “A New Hybrid Genetic Algorithm for Global Optimization,” Nonlinear Analysis, Vol. 30, No. 7, 1997. pp. 4529-4538. doi:10.1016/S0362-546X(96)00367-7

[8] J. Yen, J. Liao and D. Randolph, “A Hybrid Approach to Modeling Metabolic Systems Using a Genetic Algorithm and Simplex Method,” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 28, No. 2, 1998, pp. 173-191. doi:10.1109/3477.662758

[9] M. Okamoto, T., Nonaka, S. Ochiai and D. Tominaga, “Nonlinear Numerical Optimization with Use of a Hybrid Genetic Algorithm Incorporating the Modified Powell Method,” Applied Mathematics and Computation, Vol. 91, No. 1, 1998, pp. 63-72. doi:10.1016/S0096-3003(97)10007-8

[10] J. Renders and S. Flasse, “Hybrid Methods Using Genetic Algorithms for Global Optimization,” IEEE Transactions on Systems, Man and Cybernetic, Vol. 26, No. 2, 1999, pp. 243-258.

[11] W. Jwo, C. Liu and C. Liu, “Large-Scale Optimal VAR Planning by Hybrid Simulated Annealing/Genetic Algorithm,” International Journal of Electrical Power & Energy Systems, Vol. 21, No. 1, 1999, pp. 39-44. doi:10.1016/S0142-0615(98)00020-9

[12] M. Musil, M. Wilmut and N. Chapman, “A Hybrid Simplex Genetic Algorithm for Estimating Geoacoustic Parameters Using Matched-Field Inversion,” IEEE Journal of Oceanic Engineering, Vol. 24, No. 3, 1999, pp. 358-369. doi:10.1109/48.775297

[13] A. Nassef, H. Hegazi and S. Metwalli, “A Hybrid Genetic Direct Search Algorithm for Global Optimization of Solid C-Frame Cross Sections,” Proceedings of the 26th Design Automation Conference, Baltimore, 11-13 September 2000.

[14] K. Hacker, J. Eddy and K. Lewis, “Tuning a Hybrid Optimization Algorithm by Determining the Modality of the Design Space,” Proceedings of the 27th Design Automation Conference, Pittsburgh, 9-12 September 2001, pp. 773-782.

[15] M. Trabia, “A Hybrid Fuzzy Simplex Genetic Algorithm,” Journal of Mechanical Design, Vol. 126, No. 6, 2004, pp. 969-974. doi:10.1115/1.1803852

[16] Y. Tenne and S. Armfield, “A Novel Evolutionary Algorithm for Efficient Minimization of Expensive Black-Box Functions with Assisted-Modelling,” IEEE Congress on Evolutionary Computation, Vancouver, 11 September 2006, pp. 3220-3226.

[17] H. Telega, “Two-Phase Stochastic Global Optimization Strategies,” Studies in Computational Intelligence, Vol. 74, 2007, pp. 153-197. doi:10.1007/978-3-540-73192-4_6

[18] M. Mekhilef, “A Twinkling Technique for Brownian Moves in Optimization,” Proceedings of the 25th Design Automation Conference, Las Vegas, 12-16 September 1999.

[19] M. Mekhilef, “Introducing the Twinkling Technique in Non-Linear Optimization,” Proceedings of the 26th Design Automation Conference, Baltimore, 10-13 September 2000.

[20] M. Mekhilef and M. Trabia, “Successive Twinkling Simplex Search Optimization Algorithms,” Proceedings of the ASME 27th Design Automation Conference, Pittsburgh, 9-12 September 2001.

[21] M. Mekhilef, “Twinkling a Random Search Algorithm for Design Optimization,” ASME 31st Design Automation Conference, Long Beach, 24-28 September 2005, pp. 321-330.

[22] Z. Michalewicz, “Genetic Algorithms/Data Structure = Evolutionary Programs,” Springer-Verlag, New York, 1994.

[23] M. Gen and R. Cheng, “Genetic Algorithms & Engineering Optimization,” Wiley Interscience, New York, 2000.

[24] R. Kasat and K. Gupta, “Multi-Objective Optimization of an Industrial Fluidized-Bed Catalytic Cracking Unit (FCCU) Using Genetic Algorithm (GA) with the Jumping Genes Operator,” Computers and Chemical Engineering, Vol. 27, No. 12, 2003, pp. 1785-1800. doi:10.1016/S0098-1354(03)00153-4

[25] M. Arakawa, T. Mayashita and H. Ishikawa, “Genetic Range Genetic Algorithms to Obtain Quasi-Optimum Solutions,” ASME 29th Design Automation Conference, Chicago, 2-6 September 2003, pp. 927-934.

[26] Z. Michalewicz, “Genetic Algorithms, Numerical Optimization, and Constraints,” Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, 15-19 July 1995, pp. 151-158.

[27] S. Rao, “Engineering Optimization: Theory and Practice,” Wiley-Interscience, New York, 1996.

[28] V. Rekalitis, A. Ravindaran and K. Ragsdell, “Engineering Optimization: Methods and Applications,” Wiley Interscience, New York, 2006.

[29] S. He, E. Prempain and Q. Wu, “An Improved Particle Swarm Optimizer for Mechanical Design Optimization Problems,” Engineering Optimization, Vol. 36, No. 5, 2004, pp. 585-605. doi:10.1080/03052150410001704854

[30] J. Wang and Z. Yin, “A Ranking Selection-Based Particle Swarm Optimizer for Engineering Design Optimization Problems,” Structural Multidisclinary Optimization, Vol. 37, No. 2, 2008, pp. 131-147. doi:10.1007/s00158-007-0222-3

[31] C. Coello, “Use of a Self-Adaptive Penalty Approach for Engineering Optimization Problems,” Computers in Industry, Vol. 41, No. 2, 2000, pp. 113-127.

[32] S. Kitayama, M. Arakawa and K. Yamazaki, “Penalty Function Approach for the Mixed Discrete Nonlinear Problems by Particle Swarm Optimization,” Structural Multidisclinary Optimization, Vol. 32, No. 3, 2006, pp. 191-202. doi:10.1007/s00158-006-0021-2

[33] Q. He and L. Wang, “A Hybrid Particle Swarm Optimization with a Feasibility-Based Rule for Constrained Optimization,” Applied Mathematics and Computation, Vol. 86, No. 2, 2007, pp. 1407-1422. doi:10.1016/j.amc.2006.07.134