List of Contents
– 1. The background of the research
– 2. Research purpose
– 3. Research methods
– 4. Research process
– 4.1 Establishment of basic model
– 4.2 Basic Model Implementation
– 4.3 Integration of genetic algorithm and establishment of optimal solution algorithm
– 4.4 Result analysis
– 5. Conclusion
– 6. Annexes
1. The background of the research
Genetic algorithm is actually a computer algorithm. It is a computational model simulating the natural selection and genetic mechanism of Darwin’s biological evolution theory, and a method of searching the optimal solution by simulating the natural evolution process. When solving more complex combinatorial optimization problems, compared with some conventional optimization algorithms, better optimization results can be obtained quickly.
Nowadays, genetic algorithms have been widely used in combination optimization, machine learning, signal processing, adaptive control, artificial life and other fields. As a student in the information school, I will inevitably rely on algorithms to process information data and carry out automatic control in my future study. Therefore, understanding genetic algorithms will advance the subsequent study.
2. Research purpose
Genetic algorithm has been applied in function optimization since its appearance. Genetic algorithm only needs the information of function value, and does not need the continuity of design space or function, so it is suitable for solving various function optimization problems. Genetic algorithm can search optimization in a large range of design space, so it is more likely to obtain global optimization solution. At present, genetic algorithms have been used to solve continuous variable optimization problems, mixed discrete variable optimization problems, combinatorial optimization problems, etc. I expect to use genetic algorithm to solve the programming problem of obtaining the optimal value.
3. Research methods
I will complete the research on genetic algorithm based on the application of actual genetic algorithm, that is, genetic algorithm is referenced to programming to solve the optimal solution of practical problems.
4. Research process
4.1 Establishment of basic model
A long time ago, a group of TinyYellows lived happily in a two-dimensional world with
10 * 10, a total of100spaces to move, and the world was surrounded by a layer of walls…
We want them to explore the world and pick up as many cans as possible in a limited number of steps. It should be noted that their sights are very narrow. So,they can only see five grids–the grid which they are in and the grids around themselves in four directions. There are only three possible states for each grid: jar, blank and wall.
As the left graph shown above, the ! represents the TinyYellow, the @ represents the jars, and the # represents the wall.
The right one is the actual map stalled in program.
4.2 Basic Model Implementation
This is the most basic model, that is, the model from God’s(player’s) perspective and the operations that players can perform.
In fact, the jars on the chessboard cannot be seen by TinyYellows(because of their eyesight), so an algorithm is needed to optimize the solution. We need to find the best strategy for TinyYellow. The strategy table of each strategy is 243, which corresponds to 3 ^ 5 situations that can be seen by the strategy. The value of each strategy is an integer from 0 to 6, which refers to 7 possible actions.
That is to say, with the strategy table like above, TinyYellow can make a unique choice according to the situation that can be seen by the strategy. For each step, TinyYellow will check the five grids it can see, and calculate the situation id. Then it will refer to the strategy table and take corresponding actions.
4.3 Integration of genetic algorithm and establishment of optimal solution algorithm
We hope TinyYellow can find more jars, so if TinyYellow finds jars, we will reward it with points. If TinyYellow picks up a jar, it’ll get ten points. At the same time, we don’t want TinyYellow to do something worthless, so if TinyYellow choose to take the ‘pick up’ action in a grid without a jar, two points will be deducted. If he goes to hit the wall, five points will be deducted. It’s easy to realize that the more clever and intelligent a TinyYellow is, the higher score it should obtain, according to this scoring system. So with this system, we can assess whether TinyYellow is clever or not.
If a batch of TinyYellow were randomly generated at this time, their scores would be quite low. We expect that the clever TinyYellow can make fewer mistakes and pick up enough cans at the same time to get a higher score.
At this time, we need to use genetic algorithms to get a higher score for the next generation of TinyYellow. The so called “genetic algorithm”, simply explained, is a win-win co-operation.
In fact, mating is to take half of the strategy table of two parents and then mix their strategy tables. For each new generation, half of their behavior patterns will follow parent A, while the other half will follow parent B.
In order to improve the scores of the next generation, the two selected parents should rank higher. In practice, the program we designed uses different coefficients to make TinyYellow with higher ranking more likely to be selected. If the score is very low, it is almost impossible for them to be selected for mating, and their genes will be eliminated. This simulates the process of natural elimination.
In fact, simply superimposing two TinyYellow’s strategy tables does not necessarily improve TinyYellow’s score, at least not significantly. Therefore, in the process of copying the strategy table, we will also introduce a concept called mutation, that is, part of TinyYellow’s strategies will be a random value.
If this mutation can make it get higher scores, it will be ranked higher in the next round. This mutated gene will be more likely to be retained. Through mating, we get a new generation of TinyYellows. In order to ensure that the best genes can be retained, we will directly add the top ten of the previous generation to the new generation to ensure that the highest score will only increase. After that, let the new generation of TinyYellow walk on the chessboard for another 200 steps. According to the new round of data, we get a new ranking. According to this round of data, TinyYellows will mate again to generate the next generation of TinyYellow. After repeated iterations, finally, it was obvious that TinyYellow’s average score had improved significantly. This proves that the genetic algorithm is indeed effective.
4.4 Result analysis
We set 200 TinyYellows and let them act on 100 random maps for 200 steps, and then repeat the iterations for 1000 times, during which we collect the scores. Just one set of result is far from enough, we repeat the experiment with different MUs(mutation). We visualized the result to get the graph below.
We can safelty come to the conclution that the genetic algorithm works and it train TinyYellows to get an ideal score.
Since there’re
50jars on average, it’s quiet perfect that the highest score can reach400.
5. Conclusion
Through genetic algorithm, we use iteration to solve the programming problem of the combination of the probability of the optimal solution and the algorithm. On the one hand, it is consistent with our research purpose and expectations, on the other hand, it illustrates the universality and practical significance of the application of genetic algorithm in practical problems. In addition to the above programming problems, we actually involve genetic algorithms in bioengineering, such as radiation protection, motor scheduling in engineering, mixed model assembly line balance in logistics, and stock selection based on BP neural network in commercial economy. I believe that although genetic algorithm is inspired by the Darwin era, it will shine for a long time in all neighborhoods of the world now and in the future.
6. Annexes
The code has posted on GitHub, feel free to check it out.
PJ2_2.c: the main code that trains the TinyYellows and output the best strategy table and the scorces data.Display.c: read thestrategy.txtand show you how it works.strategy.txt: the strategy table of the best TinyYellow I’ve trained.Scores.xlsx: the data of score with different MUs.
