At present, although genetic algorithm (GA) is widely used in best polarity searching of MPRM logic circuit, there are few literatures pay attention to the polarity conversion sequence of the polarity set waiting for evaluation. An improved best polarity searching approach (IBPSA) based on GA is presented to optimize the polarity conversion sequence of polarity set and speed up the best polarity searching of MPRM logic circuits. In addition, we present an improved nearest neighbor (INN) to obtain the best polarity conversion sequence of the polarity set waiting for evaluation in each generation of GA and apply elitism strategy to IBPSA to guarantee its global convergence. Our proposed IBPSA is implemented in C and a comparative analysis has been presented for MCNC benchmark circuits. The experimental results show that the IBPSA can greatly reduce the time of best polarity searching of MPRM logic circuits compared to the approaches neglecting polarity conversion sequence.