This paper presents a framework for automatic service composition which combines a composition graph model with an Ant Colony Optimization metaheuristic to find the optimal composition solution. The composition graph model encodes all the possible composition solutions that satisfy a user request. The graph will be further used as the search space for the ant-inspired selection method targeting the identification of the optimal composition solution. To identify the optimal composition solution we define a fitness function which uses the QoS attributes and the semantic quality as selection criteria. The proposed composition framework has been tested and evaluated on an extended version of the SAWSDL-TC benchmark.