Abstract: A cloud federation service composition model based on Multi-Agent is proposed to compose optimal services in multi-Cloud platform.Then on the basis,a new heuristic algorithm is designed.According to the input parameters of request,the cloud service in the service library is preprocessed.And then the algorithm traverses the appropriate cloud service with heuristic function.Finally,the algorithm makes full use of service similarity and QoS to choose concrete service and program optimized in the process of regression.Compared with other similar algorithms,the simulation experiments show our algorithm can provide higher efficiency and shorter solution path for the requests.