Abstract: Web service selection is a critical procedure for performance-enhancing in composite service. To find the best services from the candidate services, both the Quality of Service (QoS) requirements and functional requirements should be considered. However, most Web service selection methods are based on the assumption of the independence among candidate services, and ignore the dependency relationship and compatible relationship among candidate services. In practice, composite services emphasize the coordination among these component services. The function of a candidate service in a composite service usually depends on the other optional service. To solve this problem, a multi-constraint service selection method is proposed based on local approximate filter. This method filters out part of the unsatisfied constrain services based on local approximate filter, and estimates the local fitness of each of the rest candidate services, then defines a suitable particle swarm algorithm to search the optimal solutions in the light of the calculated local fitness. Experimental results demonstrate the effectiveness of this method.