A Cellular Automata-Based Crossover Operator for Binary Chromosome Population Genetic Algorithms
Source abstract
Abstract
In this paper, we propose a crossover operator for genetic algorithms with binary chromosomes populations based on the cellular automata (CGACell). After presenting the fundamental elements regarding cellular automata with specific examples for one- and two- dimensional cases, the the most widely used crossover operators in applications with genetic algorithms are described, and the crossover operator based on cellular automata is defined. Specific forms of the crossover operator based on the ECA and 2D CA cases are described and exemplified. The CGACell crossover operator is used in the genetic structure to improved the KNN algorithm in terms of the parameter represented by the number of nearest neighbors selected by the data classification method. Validity and practical performance testing are performed on image data classification problems by optimizing the nearest-neighbors-based algorithm. The experimental study on the proposed crossover operator, by comparing a GA algorithm based on CGACell with GA algorithms based on other crossover methods, including classical GAs and permutation-based, heuristic, and hybrid methods, attests to good qualitative performance in terms of correctness percentages in the recognition of new images, as well as in classification and recognition applications of facial image classes corresponding to several persons.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Cellular Automata and Applications · DNA and Biological Computing · Algorithms and Data Compression
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Mathematics-Informatics, The National University of Science and Technology POLITEHNICA Bucharest, Pitești University Centre, 110040 Pitești, Romania
References (56)
Show source-provided references
1. Burke, E.K., and Kendall, G. (2005). Search Methodologies Introductory Tutorials in Optimization and Decision Support Techniques, Springer Science Business Media.
2. Muhlenbein, H. (1989, January 24–28). Parallel genetic algorithms, population genetics and combinatorial optimization. Proceedings of the Workshop on Parallel Processing: Logic, Organization and Technology, Wildbad Kreuth, Germany.
3. A comparative review between Genetic Algorithm use in composite optimisation and the state-of-the-art in evolutionary computation10.1016/j.compstruct.2019.111739 ↗
4. Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley.
5. A review on genetic algorithm: Past, present, and future10.1007/s11042-020-10139-6 ↗
6. Sengoku, H., and Yoshihara, I. (1993, January 9–11). A Fast TSP Solution using Genetic Algorithm. Proceedings of the 46th National Convention of Information Processing Society of Japan, Kanagawa, Japan.
7. Sushil, J., Louis, J., Gregory, E., and Rawlins, E. (1991, January 13–16). Designer Genetic Algorithms: Genetic Algorithms in Structure Design. Proceedings of the 4th International Conference on Genetic Algorithms, San Diego, CA, USA.
8. Whitley, L.D., and Vose, M.D. (1985). Foundations of Genetic Algorithms, Morgan Kaufmann.
9. Burkowski, F.J. (1999, January 6–9). Shuffle Crossover and Mutual Information. Proceedings of the Congress on Evolutionary Computation, Washington, DC, USA.
10. Crossover and mutation operators of genetic algorithms10.18178/ijmlc.2017.7.1.611 ↗
11. Geometric Crossovers for Multiway Graph Partitioning10.1162/evco.2007.15.4.445 ↗
12. Tsutsui, S., Yamamura, M., and Higuchi, T. (1999, January 13–17). Multi-parent recombination with simplex crossover in real coded genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, Florida.
13. Crossover operators in genetic algorithms: A review
14. Tafehi, E., Ahmadnia, S., and Yousefi, M. (2016, January 9–11). Improved Genetic Algorithm using Chaotic Cellular Automata-CCAGA. Proceedings of the 1st Conference on Swarm Intelligence and Evolutionary Computation (CSIEC2016), Higher Education Complex of Bam, Bam, Iran.10.1109/CSIEC.2016.7482112 ↗
15. Adamatzky, A. (1994). Identification of Cellular Automata, Taylor and Francis.
16. Injective linear cellular automata and sofic groups10.1007/s11856-007-0069-8 ↗
17. Farmer, J.D., Toffoli, T., and Wolfram, S. (1984, January 7–11). Cellular Automata. Proceedings of the an Interdisciplinary Workshop at Los Alamos, Los Alamos, NM, USA.
18. Davis, M. (1965). On computable numbers, with an application to the Entscheidungsproblem. The Undecidable, Raven Press. Available online: http://www.abelard.org/turpap2/tp2-ie.asp.
19. A symbiosis between cellular automata and genetic algorithms10.1016/j.chaos.2020.109719 ↗
20. A Hybrid Cellular Genetic Algorithm for the Traveling Salesman Problem10.1155/2021/6697598 ↗
21. Mitchell, M., Crutchfield, J.P., and Das, R. (1996, January 24–27). Evolving cellular automata with genetic algorithms: A review of recent work. Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA), Moscow, Russia.
22. Louis, S.J., and Raines, G.L. (2003, January 5). Genetic Algorithm Calibration of Probabilistic Cellular Automata for Modeling Mining Permit Activity. Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), Sacramento, CA, USA.
23. An Improved k-Nearest Neighbor Classification Using Genetic Algorithm
24. Classification of Heart Disease Using K-Nearest Neighbor and Genetic Algorithm10.1016/j.protcy.2013.12.340 ↗
25. Theory of cellular automata: A survey10.1016/j.tcs.2004.11.021 ↗
26. Wolfram, S. (1986). Theory and Applications of Cellular Automata, World Scientific.
27. Toffoli, T., and Margolus, N. (1987). Cellular Automata Machines: A New Environment for Modeling, MIT Press.10.7551/mitpress/1763.001.0001 ↗
28. Gutowitz, H. (1991). Cellular Automata: Theory and Experiment, MIT. Published as Physica D45, 1-3.10.1016/0167-2789(90)90204-3 ↗
29. The fantastic combinations of John Conway’s new solitaire game ‘life’
30. Burks, A.W. (1970). Von Neumann’s self-reproducing automata. Essays on Cellular Automata, University of Illinois Press.10.21236/AD0688840 ↗
31. The Garden of Eden theorem for linear cellular automata10.1017/S0143385705000520 ↗
32. Ceccherini-Silberstein, T., and Coornaert, M. (2010). Cellular Automata and Groups, Springer. Springer Monographs in Mathematics.10.1007/978-3-642-14034-1 ↗
33. Wolfram, S. (2002). A New Kind of Science, Wolfram Media.
34. Wuensche, A., and Lesser, M. (1992). The Global Dynamics of Cellular Automata, Addison-Wesley. Ref. Vol. 1 of Santa Fe Institute Studies in the Sciences of Complexity.
35. Cellular automata over algebraic structures
36. Cellular Automata and their Applications: A Review
37. Weimar, J.R. (1998). Simulation with Cellular Automata, Logos Verlag.
38. Delorme, M. (1998). An Introduction to Cellular Automata, Ecole Normale Superieur de Lyon. Research Rep. No. 98–37.
39. Two-dimensional cellular automata10.1007/BF01010423 ↗
40. Foundations of Genetic Algorithms (1991). Genetic Operators for Sequencing Problems, Morgan Kaufmann Publishers.
41. Selection methods for genetic algorithms
42. Schaffer, J.D. (1989, January 4–7). Uniform crossover in genetic algorithms. Proceedings of the Third International Conference on Genetic Algorithms, Fairfax, VA, USA.
43. Goldberg, D.E., and Lingle, R. (1985, January 24–26). Alleles, loci and the traveling salesman problem. Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications, Los Angeles, CA, USA.
44. Ray, S.S., Bandyopadhyay, S., and Pal, S.K. (2004, January 26). New operators of genetic algorithms for traveling salesman problem. Proceedings of the 17th International Conference on Pattern Recognition, Cambridge, UK.10.1109/ICPR.2004.1334276 ↗
45. Mudaliar, D.N., and Modi, N.K. (2013, January 7–8). Unraveling travelling salesman problem by genetic algorithm using mcrossover operator. Proceedings of the International Conference on Signal Processing, Image Processing & Pattern Recognition, Coimbatore, India.10.1109/ICSIPR.2013.6497974 ↗
46. Criteria for designing crossovers for TSP
47. Takuya, I., Hitoshi, I., and Satoshi, S. (1998, January 4–9). Depth-Dependent Crossover for Genetic Programming. Proceedings of the IEEE World Congress on Computational Intelligence Evolutionary Computation, Anchorage, AK, USA.
48. Tsutsui, S. (2006). Multi-Parent Recombination in Genetic Algorithms with Search Space Boundary Extension by Mirroring, Springer. Parallel Problem Solving from Nature, Lecture Notes in Computer Science.
49. Tsutsui, S., and Ghosh, A. (1998, January 4–9). A study on the effect of multiparent recombination in real coded genetic algorithms. Proceedings of the IEEE World Congress on Computational Intelligence, Anchorage, AK, USA.
50. Zhang, M., Gao, X., and Lou, W. (2006, January 16-21). Looseness Controlled Crossover in GP for Object Recognition. Proceedings of the IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada.
51. Aggarwal, C., and Reddy, C. (2013). Data Clustering: Algorithms and Applications, CRC Press.10.1201/b15410 ↗
52. Bishop, C. (2007). Pattern Recognition and Machine Learning, Springer.
53. Discriminant adaptive nearest neighbor classification10.1109/34.506411 ↗
54. Decision Fusion of Symmetrically Trained CNN Clas-Sifiers For Diagnosis of Chest CT Images
55. Universality in Elementary Cellular Automata10.25088/ComplexSystems.15.1.1 ↗
56. Computation theory of cellular automata10.1007/BF01217347 ↗