Machine-coded genetic operators and their performances in floating-point genetic algorithms

  • Authors

    • Mehmet Hakan Satman Istanbul University
    • Emre Akadal Istanbul University
    2017-01-25
    https://doi.org/10.14419/ijams.v5i1.7128
  • Genetic algorithms, Optimization, Simulations

  • Abstract

    Machine-coded genetic algorithms (MCGAs) use the byte representation of floating-point numbers which are encoded in the computer memory. Use of the byte alphabet makes classical crossover operators directly applicable in the floating-point genetic algorithms. Since effect of the byte-based mutation operator depends on the location of the mutated byte, the byte-based mutation operator mimics the functionality of its binary counterpart. In this paper, we extend the MCGA by developing new type of byte-based genetic operators including a random mutation and a random dynamic mutation operator. We perform a simulation study to compare the performances of the byte-based operators with the classical FPGA operators using a set of test functions. The prepared software package, which is freely available for downloading, is used for the simulations. It is shown that the byte-based genetic search obtains precise results by carrying out the both exploration and exploitation tasks by discovering new fields of the search space and performing a local fine-tuning. It is also shown that the introduced byte-based operators improve the search capabilities of FPGAs by means of convergence rate and precision even if the decision variables are in larger domains.

  • References

    1. [1] Ernesto P Adorio and U Diliman. Mvf-multivariate test functions library in c for unconstrained global optimization. Quezon City, Metro Manila, Philippines, 2005.

      [2] M Montaz Ali, Charoenchai Khompatraporn, and Zelda B Zabinsky. A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. Journal of Global Optimization, 31(4):635–672, 2005.

      [3] Rachid Chelouah and Patrick Siarry. Tabu search applied to global optimization. European journal of operational research, 123(2):256–270, 2000.

      [4] Sung-Bae Cho and Joo-Young Lee. A human-oriented image retrieval system using interactive genetic algorithm. Systems, Man and Cybernetics, Part A: systems and humans, IEEE Transactions on, 32(3):452–458, 2002.

      [5] Kalyanmoy Deb. Multi-objective optimization using evolutionary algorithms, volume 16. John Wiley & Sons, 2001.

      [6] Kalyanmoy Deb and Ram Bhushan Agrawal. Simulated binary crossover for continuous search space. Complex systems, 9(2):115–148, 1995.

      [7] Kalyanmoy Deb and A Kumar. Real-coded genetic algorithms with simulated-binary crossover: Studies on multi-modal and multiobjective problems. Complex systems, 9(6):431–454, 1995.

      [8] Larry J Eshelman. chapter real-coded genetic algorithms and interval schemata. Foundations of genetic algorithms, 2:187–202, 1993.

      [9] David Goldberg. What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys (CSUR), 23(1):5–48, 1991.

      [10] David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1989.

      [11] John J Grefenstette. Optimization of control parameters for genetic algorithms. Systems, Man and Cybernetics, IEEE Transactions on, 16(1):122–128, 1986.

      [12] Nikolaus Hansen and Stefan Kern. Evaluating the cma evolution strategy on multimodal test functions. In Parallel problem solving from nature-PPSN VIII, pages 282–291. Springer, 2004.

      [13] Francisco Herrera and Manuel Lozano. Gradual distributed real-coded genetic algorithms. Evolutionary Computation, IEEE Transactions on, 4(1):43–63, 2000.

      [14] Francisco Herrera, Manuel Lozano, and Ana M Sánchez. A taxonomy for the crossover operator for real-coded genetic algorithms: An experimental study. International Journal of Intelligent Systems, 18(3):309–338, 2003.

      [15] Francisco Herrera, Manuel Lozano, and Jose L. Verdegay. Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis. Artificial intelligence review, 12(4):265–319, 1998.

      [16] John H Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. U Michigan Press, 1975.

      [17] Hee-Su Kim and Sung-Bae Cho. Application of interactive genetic algorithm to fashion design. Engineering applications of artificial intelligence, 13(6):635–644, 2000.

      [18] Alex Kosorukoff. Human based genetic algorithm. In Systems, Man, and Cybernetics, 2001 IEEE International Conference on, volume 5, pages 3464–3469. IEEE, 2001.

      [19] Fernando G Lobo and David E Goldberg. The parameter-less genetic algorithm in practice. Information Sciences, 167(1):217–232, 2004.

      [20] Zbigniew Michalewicz. Genetic algorithms+ data structures= evolution programs. Springer Science & Business Media, 2013.

      [21] Tatsuya Nomura and Tsutomu Miyoshi. Numerical coding and unfair average crossover in ga for fuzzy rule extraction in dynamic environments. In Fuzzy Logic, Neural Networks, and Evolutionary Computation, pages 55–72. Springer, 1995.

      [22] Anne L Olsen. Penalty functions and the knapsack problem. In Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on, pages 554–558. IEEE, 1994.

      [23] Petr Pospichal, Josef Schwarz, and Jiri Jaros. Parallel genetic algorithm solving 0/1 knapsack problem running on the gpu. In 16th International Conference on Soft Computing MENDEL, volume 2010, pages 64–70, 2010.

      [24] R Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2016.

      [25] Nicholas J Radcliffe. Equivalence class analysis of genetic algorithms. Complex systems, 5(2):183–205, 1991.

      [26] Shahryar Rahnamayan, Hamid R Tizhoosh, and Magdy Salama. Opposition-based differential evolution. Evolutionary Computation, IEEE Transactions on, 12(1):64–79, 2008.

      [27] Shahryar Rahnamayan, Hamid R Tizhoosh, and Magdy MA Salama. A novel population initialization method for accelerating evolutionary algorithms. Computers & Mathematics with Applications, 53(10):1605– 1614, 2007.

      [28] Mehmet Hakan Satman. Machine coded genetic algorithms for real parameter optimization problems. Gazi University Journal of Science, 26(1):85–95, 2013.

      [29] Mehmet Hakan Satman and Emre Akadal. Arima forecasting as a genetic inheritance operator in floating-point genetic algorithms. Journal of Mathematical and Computational Science, 6(3):360, 2016.

      [30] Luca Scrucca. Ga: A package for genetic algorithms in r. Journal of Statistical Software, 53(1):1–37, 2013.

      [31] D. Stevenson. A proposed standard for binary floating-point arithmetic. Computer, 14(3):51–62, March 1981.

      [32] Rainer Storn and Kenneth Price. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11(4):341–359, 1997.

      [33] Aram Ter-Sarkisov and Stephen Marsland. K-bit-swap: a new operator for real-coded evolutionary algorithms. Soft Computing, pages 1–10, 2016.

      [34] Jakob Vesterstrøm and Rene Thomsen. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems. In Evolutionary Computation, 2004. CEC2004. Congress on, volume 2, pages 1980–1987. IEEE, 2004.

      [35] Alden H Wright. Genetic algorithms for real parameter optimization. Foundations of genetic algorithms, 1:205–218, 1991.

  • Downloads

    Additional Files

  • How to Cite

    Satman, M. H., & 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. https://doi.org/10.14419/ijams.v5i1.7128