Range image registration is a popular problem in pattern recognition and computer vision, and it has a wide range of applications in real life. The objective of registration is to match two models as close as possible. In this area, the best known iterative closest point (ICP) method is sensitive to the initial position of two models and it is easy stuck in local minima. In recent years, heuristic algorithms have been used for registration with good ability for global searching. However, the features of models are ignored generally in the iterative evolution process, so the tailored methods are lack of versatility for different models registration. In this paper, normal angle histogram is added into the fruit fly optimization algorithm for registration. The searching step of each individual is relative to the initial position of two models. The versatility and effectiveness of proposed algorithm are illustrated by a series of experiments.