In service-oriented computing, Web service selection is an important part of Web service composition. QoS attributes are used to distinguish Web services with same functionality. QoS-aware Web service selection and composition have attracted much attention in the past years. The Web service composition is achieved by solving the Web service concretization problem. The literature has presented two Web service concretization approaches, namely, local optimization approach and global optimization approach. There are three types of algorithmic methods in the global optimization approaches: optimal methods, sub-optimal methods, and soft constraints-based methods. The bio-inspired algorithms are sub-optimal methods. The existing studies using bio-inspired algorithms apply different strategies to solve Web service concretization problems. This paper will firstly present a hierarchical taxonomy of Web service concretization approaches. Then we present a systematic review on the current research of Web service concretization based on bio-inspired algorithms. We will describe the applications of ant colony optimization algorithm, genetic algorithm, and particle swarm optimization algorithm to Web service concretization. In addition, this paper will compare ant colony optimization algorithm and genetic algorithm in details. By analyzing and comparing different applications of bio-inspired algorithms-Web service concretization, this paper also discusses the known outcomes and areas for potential future research.