Markov chain analysis of genetic algorithms for 3-SAT problem
Qinglian Ma, Yuan Zhang, Kunihito Yamamori, Makoto Sakamoto, Hiroshi Furutani · 2011
There are many works to solve NP-complete problems by using Genetic Algorithms(GAs). The satisfiability (SAT) problem is the first proposed NP-complete problem, and plays a central role in computer science. However, the application of GAs to SAT problems may require the high performance computing, and it is necessary to obtain runtime properties of the problem. To solve this problem, we investigated the distribution of the first hitting time T for 3-SAT problems within the framework of Markov chain model. We define T as the first time of finding a solution instance in a population. We also explored the success probability S, first hitting time T̃ in the stationary distribution and survival time a in the GA on 3-SAT problem. We focused on the relations between these quantities, and got the result of T̃ = a/S. Furthermore, we give the functional form for the distributions of T and T̃, and compared them with numerical experiments.