In this paper we present an efficient method to solve reachability problems for Petri nets based on genetic algorithms and a kind of random search which is called postpone search. Genetic algorithm is one of algorithms developed for solving several problems of optimization. We apply GAs and postpone search to approximately solving reachability problems. This approach can not determine exact solutions, however, from applicability points of view, does not directly face state space explosion problems and can extend class of Petri nets to deal with very large state space in reasonable time. First we describe how to represent reachability problems on each of GAs and postpone search. We suppose the existence of a nonnegative parickh vector which satisfies the necessary reachability condition. Possible firing sequences of transitions induced by the parickh vector is encoded on GAs. We also define fitness function to solve reachability problems. Reachability problems can be interpreted as an optimization ones on GAs. Next we introduce random reachability problems which are capable of handling state space and the number of firing sequences which enable to reach a target marking from an initial marking. State space and the number of firing sequences are considered as factors which effect on the hardness of reachability problems to solve with stochastic methods. Furthermore, by using those random reachability problems and well known dining philosophers problems as benchmark problems, we compare GAs' performance with the performance of postpone search. Finally we present empirical results that GAa is more useful method than postpone search for solving more harder reachability problems from the both points of view; reliability and efficiency.