We have previously proposed a modified back-propagation (BP) algorithm for the development of behavior-based autonomous robots. Although the method was proved applicable to a real mobile robot Khepera, there existed some problems such as the convergence to the local minimum and the variability among trials. In order to improve the performance, we have introduced a new criterion for selecting the training data set. Coefficients of a multi-layered neural network (NN), that determined the sensor-motor reflex of the robot, were first set randomly, and the robot was allowed to behave in environment for some time. Sets of the sensor-motor values were continuously sampled during the free-moving period, and each set was evaluated by the behavior that occurred after the sampling by using an evaluation function. The behavior was evaluated by both immediate response to near-by obstacles and long-range navigation capability, and the evaluation function was composed with these scores. The set obtained the highest score was selected for each sensor pattern, and used to train the NN with BP. By repeating the above procedures, the robot obtained the adaptive behavior for the given environment in accordance with the evaluation function. The new criterion provided a much faster and stable convergence than the previous one, and far better than the conventional genetic algorithm.