1. Introduction
Game is a competitive activity involving skill, chance, or endurance on the part of two or more persons who play according to a set of rules, usually for their own amusement or for that of spectators Most of the design problems in the nature can be considered as optimization problems which request some proper optimization techniques and algorithms to be dealt with. In these days, the design problems have become extremely complex in which the classical optimization algorithms based on the mathematical principles are incapable of providing some satisfactory results in a reasonable period of time.
Chaos theory is a branch of mathematics concentrating on the specific characteristics of dynamical systems which are extremely sensitive to initial conditions [1]. Considering the randomness of these dynamical systems, chaos theory denotes on the existence of some primary patterns such as similar loops, repeated templates [2], fractals and multiple sub-systems in the behavior of these systems which represent them as self-similar and self-organized dynamical systems [3].
2. The Choas game
The “chaos game” method plots points in random order all over the attractor. This is in contrast to other methods of drawing fractals, which test each pixel on the screen to see whether it belongs to the fractal. The general shape of a fractal can be plotted quickly with the “chaos game” method, but it may be difficult to plot some areas of the fractal in detail. The chaos theory demonstrates that some small changes in the initial conditions of a dynamical system will result in some extreme differences in the upcoming conditions of these systems due to the dependence of them to the initial conditions. Based on this theory, the present state of a system could determine the later state of this system while the approximate present state of a system does not approximately determine the later state of this system.
In mathematics, the chaos game is the methodology of creating fractals utilizing an initial polygon shape and a randomly selected initial point. The main purpose is to create a sequence of points in an iterative manner in order to achieve a sketch which has similar shape in different scales. In this regard, the vertices of a polygon which is considered as the main shape of the fractal should be firstly positioned properly. Then, an initial random point is selected as the starting point for creating fractal. Based on this initial point, the next point in the sequence is determined as a fraction of the distance between the initial point and one of the vertices of the polygon which is selected randomly in each iteration. By repeating this process continuously with consideration of the random initial point and the random vertex selection in each iteration, a fractal is created
3. Inspiration of Choas Game Algorithm (CGO)
The main concept of the CGO algorithm is based on some principles of chaos theory in which the configuration of fractals [7] by chaos game concept and the fractals self-similarity issues are in perspective [8]. In mathematics, the term chaos game originally referred to a method of creating a fractal, using a polygon and an initial point selected at random inside it. The fractal is created by iteratively creating a sequence of points, starting with the initial random point, in which each point in the sequence is a given fraction of the distance between the previous point and one of the vertices of the polygon; the vertex is chosen at random in each iteration. Repeating this iterative process a large number of times, selecting the vertex at random on each iteration, and throwing out the first few points in the sequence, will often produce a fractal shape. Using a regular triangle and the factor will result in the Sierpinski triangle, while creating the proper arrangement with four points and a factor will create a display of a “Sierpinski Tetrahedron”, the three-dimensional analogue of the Sierpinski triangle.
With the aid of the “chaos game” a new fractal can be made and while making the new fractal some parameters can be obtained. These parameters are useful for applications of fractal theory such as classification and identification. The new fractal is self-similar to the original in some important features such as fractal dimension. If in the “chaos game” you start at each vertex and go through all possible paths that the game can take, you will get the same image as with only taking one random path. However, taking more than one path is rarely done since the overhead for keeping track of every path makes it far slower to calculate. This method does have the advantages of illustrating how the fractal is formed more clearly than the standard method as well as being deterministic.
4. Why does the Sierpinski triangle arise from the chaos game?
The Sierpinski triangle also called the Sierpinski gasket or Sierpinski sieve [9] is a fractal attractive fixed set with the overall shape of an equilateral triangle, subdivided recursively into smaller equilateral triangles [10].
The step by step creation of a Sierpinski triangle by the methodology of chaos game is presented. At first, three vertices are selected in order to create the main shape of the fractal which results in a triangle shape in this case. Each of the selected vertices is marked by one of the red, blue and green colors. A dice is taken which has two red faces, two blue faces and two green faces. An initial random point is selected as the starting point of the fractal which is considered as a seed in this example. As the dice is rolled, based on which color comes up, the seed in the initial point is moved toward the related vertex half the distance between the seed and the vertex. The new position of the seed is utilized in the next iteration as the starting point in which the dice is rolled again and the seed is moved to the intended vertex accordingly. By rolling the dice many times, the Sierpinski triangle is achieved as the final shape
5. Mathematical model of CGO
In this section, an optimization algorithm is proposed based on the presented principles of the chaos theory. The basic concepts of the fractals and chaos game are utilized in order to formulate a mathematical model for the CGO algorithm. Because of the fact that many of the natural evolution algorithms maintain a population of solutions which are evolved through random alterations and selection. The CGO algorithm considers a number of solution candidates (S) in this purpose which represent some eligible seeds inside a Sierpinski triangle [11]. The Sierpinski triangle is considered as the search space for solution candidates in the optimization algorithm. The mathematical presentation of these aspects is as follows:
7. Application of CGA
Reference
[1]S. Talatahari and M. Azizi, “Chaos Game Optimization: a novel metaheuristic algorithm”, Artificial Intelligence Review, 2020. Available: 10.1007/s10462-020-09867-w.
[2]B. Alatas, “Chaotic harmony search algorithms”, Applied Mathematics and Computation, vol. 216, no. 9, pp. 2687-2699, 2010. Available: 10.1016/j.amc.2010.03.114.
[3]B. Alatas, “ACROA: Artificial Chemical Reaction Optimization Algorithm for global optimization”, Expert Systems with Applications, vol. 38, no. 10, pp. 13170-13180, 2011. Available: 10.1016/j.eswa.2011.04.126.
[4]B. Alatas, E. Akin and A. Over, “Chaos embedded particle swarm optimization algorithms”, Chaos, Solitons & Fractals, vol. 40, no. 4, pp. 1715-1734, 2009. Available: 10.1016/j.chaos.2007.09.063.
[5]E. Low, P. Ng, C. Hui and L. Cai, “Teaching as a Career Choice: Triggers and Drivers”, Australian Journal of Teacher Education, pp. 28-46, 2017. Available: 10.14221/ajte.2017v42n2.3.
[6]M. Azizi, R. Ejlali, S. Mousavi Ghasemi and S. Talatahari, “Upgraded Whale Optimization Algorithm for fuzzy logic based vibration control of nonlinear steel structure”, Engineering Structures, vol. 192, pp. 53-70, 2019. Available: 10.1016/j.engstruct.2019.05.007 [Accessed 2 October 2020].
[7]D. Karaboga and B. Basturk, “A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm”, Journal of Global Optimization, vol. 39, no. 3, pp. 459-471, 2007. Available: 10.1007/s10898-007-9149-x.
[8]M. Cheng and D. Prayogo, “Symbiotic Organisms Search: A new metaheuristic optimization algorithm”, Computers & Structures, vol. 139, pp. 98-112, 2014. Available: 10.1016/j.compstruc.2014.03.007.
[9]M. Dorigo, V. Maniezzo and A. Colorni, “Ant system: optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29-41, 1996. Available: 10.1109/3477.484436.
[10]S. Pasandideh and S. Niaki, “Multi-response simulation optimization using genetic algorithm within desirability function framework”, Applied Mathematics and Computation, vol. 175, no. 1, pp. 366-382, 2006. Available: 10.1016/j.amc.2005.07.023.
[11]D. Zaldívar, B. Morales, A. Rodríguez, A. Valdivia-G, E. Cuevas and M. Pérez-Cisneros, “A novel bio-inspired optimization model based on Yellow Saddle Goatfish behavior”, Biosystems, vol. 174, pp. 1-21, 2018. Available: 10.1016/j.biosystems.2018.09.007.
[12]Z. Gao, J. Zhao, Y. Yang and X. Tian, “The hybrid grey wolf optimization-slime mould algorithm”, Journal of Physics: Conference Series, vol. 1617, p. 012034, 2020. Available: 10.1088/1742-6596/1617/1/012034.
[13]D. S and A. Ravikumar, “A Study from the Perspective of Nature-Inspired Metaheuristic Optimization Algorithms”, International Journal of Computer Applications, vol. 113, no. 9, pp. 53-56, 2015. Available: 10.5120/19858-1810.