The characteristic that nodes can enlist into the network topology freely and independently makes mobile Ad hoc networks (MANET) widely used in various environments such as disaster rescue, battlefield and so on. In MANET, the routing mechanism should adapt rapidly to the frequently changed network topology and in the mean time economize valuable network resources with its best. The Optimized Link State Routing Protocol (OLSR) is an important MANET routing protocol in which the key technique is MultiPoint Relays (MPR). After introducing the OLSR protocol and its MPR technique, the shortcoming of presently used heuristic algorithm in finding the minimum MPR sets is revealed. Then the new algorithm based on genetic algorithm (GA) is presented, and the convergence of the algorithm is proved. A series of 4 genetic algorithms are further developed by adopting different GA strategies and simulated in many topologies that are created randomly. Analysis on simulating results shows that the genetic algorithms are feasible and applicable and the choice of heuristic strategies is advisable and appropriate.