Abstract | ||
---|---|---|
Mutation plays an important role in the computing of Genetic Algorithms (GAs). In this paper, we use the success probability as a measure of the performance of GAs, and apply a method for calculating the success probability by means of Markov chain theory. We define the success probability as there is at least one optimum solution in a population. In this analysis, we assume that the population is in linkage equilibrium, and obtain the distribution of the first order schema. We calculate the number of copies of the optimum solution in the population by using the distribution of the first order schema. As an application of the method, we study the GA on the multiplicative landscape, and demonstrate the process to calculate the success probability for this example. Many researchers may consider that the success probability decreases exponentially as a function of the string length L. However, if mutation is included in the GA, it is shown that the success probability decreases almost linearly as L increases. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-4-431-53868-4_43 | NATURAL COMPUTING |
Keywords | Field | DocType |
first order,markov chain,genetic algorithm | Population,Mathematical optimization,Multiplicative function,Meta-optimization,Markov chain,Schema (psychology),Genetic algorithm,Mathematics,Exponential growth,Mutation | Conference |
Volume | ISSN | Citations |
2.0 | 1867-2914 | 1 |
PageRank | References | Authors |
0.39 | 4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yu-an Zhang | 1 | 23 | 8.97 |
Qinglian Ma | 2 | 7 | 2.63 |
Makoto Sakamoto | 3 | 25 | 16.45 |
Hiroshi Furutani | 4 | 54 | 22.85 |