Abstract: To tackle the QoSbased service selection problem， a novel efficient hybrid ant colony optimization algorithm was proposed. In this algorithm， a skyline query process was used to filter the candidates related with each service class， by which the search space could be greatly shrunk and the solving efficiency was improved in the case of not losing good candidates. Then， varying dynamic construct graph was designed to guide the ant search directions based on a clustering process and some promising search areas could be found after the ACO search process. In order to make a further exploitation for these areas， a heuristic strategy was introduced and used to make a deeper local search. The proposed approach was evaluated experimentally by using standard real datasets and synthetically generated datasets， and compared with the recently proposed related service selection algorithms. The experiments indicated very encouraging results in terms of the quality of solution， and the processing time required.

Key words: ACO (ant colony optimization), service selection, clustering, heuristic information, pheromone