Abstract: With the development of Web service theories and technologies, Web service has been spreading rapidly. In order to meet the requirements of different users, multiple services need to be composed. Therefore, how to dynamically and efficiently select appropriate Web services from existing services to build newly value-added and complex services has been a popular research focus. In this paper, a discrete particle swarm optimization (DPSO) algorithm is designed to facilitate the dynamic Web service selection, and combined with the specific meaning of service selection, three kinds of velocity operator and one position evolution equation are proposed. Aimed at the common limitation that evolutionary algorithms are prone to fall into the local optimal solution, no-hope/re-hope criterion is introduced to guarantee the diversity of particle swarm and improve the global search ability. Theoretical analysis and experimental results show that the proposed algorithm not only owns a good globally convergent performance but also has a faster convergent rate. Specially, the service selection method is independent of the candidate services number, which means that the efficiency of service selection will not decrease with the increase of available services. Furthermore, compared with other two velocity operators, the Max operator has best comprehensive properties in the process of service selection.