In this paper, we apply GAs, SA and postpone search to approximately solve reachability problems and those performance are compared. This approach can not determine exact solutions, however, does not directly face state space explosion problems. First, supposed to be 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 state space and the number of firing sequences which affect hardness of problems. By using those random reachability problems, we compare GAs performance with performance of SA or postpone search with experiments. Furthermore we discussed an efficient crossover for reachability problems and effect of population size. Finally, harder reachability problems are discussed with empirical results of GAs.