An efficient genetic algorithm for reachability problems

We apply GAs, SA and postpone search to approximately solve reachability problems and compare their performance. This approach cannot determine exact solutions, however, it does not directly face state space explosion problems. Supposing the existence of a nonnegative parickh vector which satisfies the necessary reachability condition, we show how to present reachability problems on GAs and SA as optimization problems. Next, we present random reachability problems which are capable of handling the state space and the number of firing sequences which affect the hardness of problems. By using those random reachability problems, we compare GA performance with the performance of SA or postpone search with experiments. Furthermore, we discuss an efficient crossover for reachability problems and the effect of population size. Finally, harder reachability problems are discussed with empirical results of GAs