¡¡Chinese Journal of Computers   Full Text
  TitleOptimizing Services Composition Based on Improved Ant Colony Algorithm
  AuthorsXIA Ya-Mei1),2) CHENG Bo1) CHEN Jun-Liang1) MENG Xiang-Wu1) LIU Dong1)
  Address1)(State Key Laboratory of Networking and Switching Technology, Beijing University of Posts & Telecommunications, Beijing 100876) 2)(School of Software Engineering, Beijing University of Posts & Telecommunications, Beijing 100876)
  Year2012
  IssueNo.2(270¡ª281)
  Abstract &
  Background 		Abstract In order to optimize services composition, adapt the dynamic and instable characteristics of Web services and the limitation of multi-QoS attributes in the process of services composition, this paper puts forward an algorithm named Multi-pheromone and Dynamically Updating Ant Colony Optimization Algorithm (MPDACO), which includes one global optimizing algorithm and another local optimizing algorithm. The algorithm, which is based on the ACO and composition model that has been built, can fit for such conditions as service invalidation, QoS changing, etc. In addition, the algorithm has improved the ACO strategy on the basis of experiment to make itself be able to converge to optimal solution. In order to verify the feasibility of the above algorithms, this paper makes a simulation experiment on a prototype in tourism, and the results show that the two algorithms are more effective than ACO and the Genetic Algorithm applied to service selection. Keywords semantic; services composition; service selection; ant colony algorithm; optimization Background This paper mainly analyzes one aspect in dynamic services composition in the field of semantic web. Dynamic services composition, a focus in semantic web research, has attracted the attention of many scholars around the world. Although fruitful results have been achieved, there are still some problems to be solved. As an important research power, State Key Laboratory of Networking and Switching Technology of Beijing University of Posts & Telecommunications has a 10-year research experience in this field, and published many influential papers. It also provides this paper with ¡°fertile soil¡±. This paper is supported by National Basic Research Program of China under Grant No.2011CB302704 and the National Natural Science Foundation of China under Grant No.61001118. In the research of ¡°The Providing Mechanism and Methods of the Internet of Things Service¡±¡ªthe sub project of 973 (2011CB302704), the performance of service selection is an emergent problem to solve. With some inherent features, the ant colony algorithm is fit for solving this problem. This paper builds a services composition model, and changes services composition graph to a simple one-direction connected graph. For the instability of services state, the change of service state is simulated by dynamically adjusting the connected graph and changing the weight of the edge. In addition, as in many services, the Value of QoS is known only after the services are selected and implemented, the author makes improvement of the ACO, and makes the optimized algorithm being implemented without knowing the value of QoS. As the ACO matures early and tends to stagnate, which makes the optimal solution always a local one, this paper makes improvement of the ACO strategy, and profoundly enhances the convergence of the algorithm, and decreases the probability of converging to local optimal solution. To prove its effectiveness, the algorithm is used in ¡°Pingu District Tourism Information System¡± to make service recommendation. The simulation experiment result shows that the algorithm has a better performance than ACO and the Genetic Algorithm used in service selection.