This paper presents a multi-thread evolutionary programming (MEP) technique that is composed of global, local, and minimal search units. An appropriate search routine is called depending on the current situation and the individuals are updated by using the selected routine. In each search routine, the individuals are updated with a normalized relative fitness function to improve the robustness of the algorithm. The proposed method is applied to the problem of backing up a truck-and-trailer system to a loading dock. A fuzzy logic controller is designed for a truck-and-trailer backer-upper system and the MEP algorithm is used to optimize the representative parameters of the fuzzy logic controller. The simulation results show that the proposed controller performs well even under a large variety of initial positions.