This paper describes a new method for three-dimensional medical image registration. In the interactive image-guided HIFU (High Intensity Focused Ultrasound) therapy system, a fast and precise localization of the tumor is very important. An automatic system is developed for registering pre-operative MR images with intra-operative ultrasound images based on the vessels visible in both of the modalities. When the MR and the ultrasound images are aligned, the centerline points of the vessels in the MR image will align with bright intensities in the ultrasound image. The method applies an optimization strategy combining the genetic algorithm with the conjugated gradients algorithm to minimize the objective function. It provides a feasible way of determining the global solution and makes the method robust to local maximum and insensitive to initial position. Two experiments were designed to evaluate the method, and the results show that our method has better registration accuracy and convergence rate than the other two classic algorithms.