Machine Coded Compact Genetic Algorithms for Real Parameter Optimization Problems

Abstract

In this paper, we extend the Compact Genetic Algorithm (CGA) for real-valued optimization problems by dividing the total search process into three stages. In the first stage, an initial vector of probabilities is generated. The initial vector contains the probabilities of bits having 1 depending on the bit locations as defined in the IEEE-754 standard. In the second stage, a CGA search is applied on the objective function using the same encoding scheme. In the last stage, a local search is applied using the result obtained by the previous stage as the starting point. A simulation study is performed on a set of well-known test functions to measure the performance differences. Simulation results show that the improvement in search capabilities is significant for many test functions in many dimensions and different levels of difficulty.

Keywords

• Optimization
• genetic algorithms
• evolutionary optimization
• simulations

References

1. Aporntewan C. and Chongstitvatana P. (2001) A hardware implementation of the compact genetic algorithm. In Evolutionary Computation, 2001. Proceedings of the 2001 Congress on, volume 1, pages 624–629. IEEE, 2001.
2. Arakaki, R. K and Usberti, F. L. (2018) Hybrid genetic algorithm for the open capacitated arc routing problem. Computers & Operations Research, 90:221–231.
3. Budin, L., Golub, M., & Budin, A. (2010). Traditional techniques of genetic algorithms applied to floating-point chromosome representations. Sign, 1(11), 52.
4. Chen, J., Xin, B., Peng, Z. Dou, L. and Zhang, J. (2009) Optimal contraction theorem for exploration–exploitation tradeoff in search and optimization. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 39(3), 680–691.
5. Goldberg, D. E. (1991) Real-coded genetic algorithms, virtual alphabets, and blocking. Complex systems, 5(2). 139–167.
6. Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning.
7. Goldberg. D. E (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition.
8. Gonçalves, J. F. And Mendes, J. J. M and Resende, M. GC. (2005) A hybrid genetic algorithm for the job shop scheduling problem. European journal of operational research, 167(1), 77–95.

9. Harik, G. R., Lobo, F. G. and Goldberg, D. E. (1999) The compact genetic algorithm. IEEE transactions on evolutionary computation, 3(4). 287–297.
10. Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.
11. Hooke, R. and Jeeves, T. A. (1961) “direct search” solution of numerical and statistical problems. Journal of the ACM (JACM), 8(2), 212–229.
12. Ieee standard for floating-point arithmetic. IEEE Std 754-2008, pages 1–70, Aug 2008.
13. Kang, F., Li, J., Ma, Z., & Li, H. (2011). Artificial bee colony algorithm with local search for numerical optimization. Journal of Software, 6(3), 490-497.
14. Kim, D. H., Abraham, A. and Cho, J. H. (2007) A hybrid genetic algorithm and bacterial foraging approach for global optimization. Information Sciences, 177(18), 3918–3937.
15. Liu, D., Liu, C., Zhang, C., Xu, C., Du, Z. and Wan, Z. (2018), "Efficient hybrid algorithms to solve mixed discrete-continuous optimization problems: A comparative study", Engineering Computations, 35(2), 979-1002.
16. Long, Q., & Wu, C. (2014). A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of industrial and management optimization, 10(4), 1279-1296.
17. Mininno, E., Cupertino, F., & Naso, D. (2008). Real-valued compact genetic algorithms for embedded microcontroller optimization. IEEE Transactions on Evolutionary Computation, 12(2), 203-219.
18. Mishra, S. K. (2006) Some new test functions for global optimization and performance of repulsive particle swarm method. Available at SSRN 926132.
19. Moser, I. (2009) Hooke-jeeves revisited. In Evolutionary Computation, 2009. CEC’09. IEEE Congress on, pages 2670–2676.
20. Ojha, V. K., Dutta, P., Saha, H., & Ghosh, S. (2012). Application of real valued neuro genetic algorithm in detection of components present in manhole gas mixture. In Advances in Computer Science, Engineering & Applications, 333-340. Springer, Berlin, Heidelberg.
21. Pelikan, M., Hauschild, M. W., & Lobo, F. G. (2015). Estimation of distribution algorithms. In Springer Handbook of Computational Intelligence (pp. 899-928). Springer, Berlin,
22. Heidelberg. Baluja, S. (1994). Population-based incremental learning. a method for integrating genetic search based function optimization and competitive learning. Carnegie-Mellon Univ Pittsburgh Pa Dept Of Computer Science.
23. Sastry, K., Goldberg, D. E and Kendall, G. (2014). Genetic algorithms. In Search methodologies, Springer, 93–117.
24. Satman, M. H. (2013), Machine coded genetic algorithms for real parameter optimization problems. Gazi University Journal of Science, 26(1), 85–95.
25. Satman, M. H. (2015) Hybridization of floating-point genetic algorithms using hooke-jeeves algorithm as an intelligent mutation operator. Journal of Mathematical and Computational Science, 5(3), 320-332.
26. Satman, M. H. and Akadal, E. (2016) Arima forecasting as a genetic inheritance operator in floating-point genetic algorithms. Journal of Mathematical and Computational Science, 6(3), 360.
27. Satman, M. H. and Akadal, E. (2017) Machine-coded genetic operators and their performances in floating-point genetic algorithms. International Journal of Advanced Mathematical Sciences, 5(1), 8–19.
28. Sebag, M. And Ducoulombier, A (1998). Extending population-based incremental learning to continuous search spaces. In International Conference on Parallel Problem Solving from Nature, pages 418–427. Springer,
29. Umbarkar, A. J., Joshi, M. S., & Sheth, P. D. (2015). Dual population genetic algorithm for solving constrained optimization problems. International Journal of Intelligent Systems and Applications, 7(2), 34.
30. Usberti, F. L., França, P. M. and França, A. L. M. (2013) Grasp with evolutionary path-relinking for the capacitated arc routing problem. Computers & Operations Research, 40(12), 3206–3217.