Abstract: In service-oriented environments, there are a number of service composition schemes which can satisfy the needs of service requesters.Web service composition optimization is proposed to solve the problem of selecting the optimal scheme from the schemes.Therefor, the paper presents an optimized algorithm that finds the optimal solution for service requesters without having to explore the entire solution space.Experimental results show that the algorithm efficiency has been improved.