论文部分内容阅读
Abstract： According to traditional card problem solving which is based on the idea of genetic algorithm（GA）， a set of algorithms is designed to find final solution. For each process in genetic algorithm， including choices of fitness function， parameters determination and coding scheme selection，classic algorithm is used to realize the various steps， and ultimately to find solution of problems.
Key words： genetic algorithm； card problem； fitness function； parameters determination； coding scheme selection
中图分类号：TP393.06 文献标识码：A 文章编号：1009-3044（2016）05-0025-02
1 Introduction
Genetic algorithm has been wildly used in several parts of our modern society. It is popular to solve problems by using the mind of genetic algorithm （GA）. In this article， a classical card problem is going to be solved by GA， which is a simple example to show the procedure.
1.1 Card problem
Card problem is a famous mathematic problem in western country. If there are ten cards from A to 10， it is possible that the number of five chosen cards can add to 36 and the number of rest five cards can multiply to 360. So the problem is how to find out what the five cards that we choose are.
1.2 Genetic algorithm （GA）
Genetic Algorithm （GA） is an iterative algorithm for global optimization. This Algorithm， based on Darwin’s theory of evolution， is a stochastic search algorithm by simulating the process of natural selection.
Genetic algorithm describes the biological evolution in an abstract way. Copy， crossover and mutation are three most important parameters in evolution and will be set as three operators of the algorithm. These operators in each iteration have a set of answers， which are originally randomly generated. After each iteration， a new set of answers are generated by genetic manipulation simulated evolution. The new answers are evaluated by an objective function. This process is repeated until it reaches some form of convergence.
A new set of answers not only can selectively retain some old answers with high value of objective function， but also includes some new answers obtained by combining other answers. Therefore， the genetic algorithm can remain the potential gene in each iteration during evolutionary process， which means that the results of genetic algorithms are always looking for the best value for the evaluation function. Generally， the Genetic algorithm is kind of optimization process which is reliable and can be proved mathematically. The key issues of GA are the choice of fitness function， parameters determination and coding scheme selection. 2 Algorithm Design
2.1 Coding scheme selection
As there are 10 cards used in card problem， the length of chromosome is set as 10. So a two-dimension array with 10 columns is designed. Then， the original population is generated by random function. Meanwhile， the capacity of population should also be set to reach the need of reproduction.
2.3 Crossover function
At the beginning， the crossover rate should be set. The method that determine whether it is going to crossover is roulette wheel. The lower environmental adaption would be instead of by the function below：
2.5 Reproduction upper limit calculation
As the original data come from random function， the algorithm may not get the final answers after a long time calculation. So it is necessary to set an upper limit for reproduction， when reach the limitation， the program would stop.
3 Results and Discussion
Based on the GA， the program was designed and the parameters were set as follows：
The population was 30， the crossover rate was 0.6， the mutation rate was 0.01 and the reproduction upper limit was 1000. The output results are displayed on figure 1， figure 2 and figure 3.
In summary， the program got the results of card problem by using the genetic algorithm. It is clear that GA is a reliable and effective algorithm methods in many area. However， GA still has its disadvantages， like it may not be able to get answers after a long time. In the future， the GA would solve more and more realistic problems and have more applications with the development of itself.
References：
[1] S.G. Ficici and J.B. Pollack.A game-theoretic approach to the simple coevolutionary algorithm[C].Proc. of the Sixth International Conference on Parallel Problem Solving from Nature，Paris， France， 2000： 467-476.
[2] Ren Xienan.Study on optimization of BP neural network based on genetic algorithm and Matlab simulation[D].Tianjin：Tianjin Normal University.
[3] Xi Yugeng，Chai Tianyou，Yun Weimin.Survey on genetic algorithm [J].Control Theory and Applications，1996（6）：697-708.
Key words： genetic algorithm； card problem； fitness function； parameters determination； coding scheme selection
中图分类号：TP393.06 文献标识码：A 文章编号：1009-3044（2016）05-0025-02
1 Introduction
Genetic algorithm has been wildly used in several parts of our modern society. It is popular to solve problems by using the mind of genetic algorithm （GA）. In this article， a classical card problem is going to be solved by GA， which is a simple example to show the procedure.
1.1 Card problem
Card problem is a famous mathematic problem in western country. If there are ten cards from A to 10， it is possible that the number of five chosen cards can add to 36 and the number of rest five cards can multiply to 360. So the problem is how to find out what the five cards that we choose are.
1.2 Genetic algorithm （GA）
Genetic Algorithm （GA） is an iterative algorithm for global optimization. This Algorithm， based on Darwin’s theory of evolution， is a stochastic search algorithm by simulating the process of natural selection.
Genetic algorithm describes the biological evolution in an abstract way. Copy， crossover and mutation are three most important parameters in evolution and will be set as three operators of the algorithm. These operators in each iteration have a set of answers， which are originally randomly generated. After each iteration， a new set of answers are generated by genetic manipulation simulated evolution. The new answers are evaluated by an objective function. This process is repeated until it reaches some form of convergence.
A new set of answers not only can selectively retain some old answers with high value of objective function， but also includes some new answers obtained by combining other answers. Therefore， the genetic algorithm can remain the potential gene in each iteration during evolutionary process， which means that the results of genetic algorithms are always looking for the best value for the evaluation function. Generally， the Genetic algorithm is kind of optimization process which is reliable and can be proved mathematically. The key issues of GA are the choice of fitness function， parameters determination and coding scheme selection. 2 Algorithm Design
2.1 Coding scheme selection
As there are 10 cards used in card problem， the length of chromosome is set as 10. So a two-dimension array with 10 columns is designed. Then， the original population is generated by random function. Meanwhile， the capacity of population should also be set to reach the need of reproduction.
2.3 Crossover function
At the beginning， the crossover rate should be set. The method that determine whether it is going to crossover is roulette wheel. The lower environmental adaption would be instead of by the function below：
2.5 Reproduction upper limit calculation
As the original data come from random function， the algorithm may not get the final answers after a long time calculation. So it is necessary to set an upper limit for reproduction， when reach the limitation， the program would stop.
3 Results and Discussion
Based on the GA， the program was designed and the parameters were set as follows：
The population was 30， the crossover rate was 0.6， the mutation rate was 0.01 and the reproduction upper limit was 1000. The output results are displayed on figure 1， figure 2 and figure 3.
In summary， the program got the results of card problem by using the genetic algorithm. It is clear that GA is a reliable and effective algorithm methods in many area. However， GA still has its disadvantages， like it may not be able to get answers after a long time. In the future， the GA would solve more and more realistic problems and have more applications with the development of itself.
References：
[1] S.G. Ficici and J.B. Pollack.A game-theoretic approach to the simple coevolutionary algorithm[C].Proc. of the Sixth International Conference on Parallel Problem Solving from Nature，Paris， France， 2000： 467-476.
[2] Ren Xienan.Study on optimization of BP neural network based on genetic algorithm and Matlab simulation[D].Tianjin：Tianjin Normal University.
[3] Xi Yugeng，Chai Tianyou，Yun Weimin.Survey on genetic algorithm [J].Control Theory and Applications，1996（6）：697-708.