Research On Multi-task Parallel Coalition Generation Based On Modified Discrete Particle Swarm Optimization Algorithm

The coordination and cooperation among agents in large-scale complicated system is very important. Coalition as one of important cooperation ways is useful as it may increase the ability of agents to accomplish tasks and achieve their goals. And coalition generation is the primary issue for coalition mechanism to resolve.Coalition generation mainly focus on how to generate task-oriented optimal coalition in a dynamic manner. This paper analyses the multi-task parallel coalition generation based on coalition structure and finds out there exists surplus ability in coalitions, then a method is presented to construct multi-task coalition model from smaller granularity of participants. Finally, a modified discrete particle swarm optimization algorithm (DPSO) is adopted to solve collation generation problem. The result of experiment proves the superiority of modified DPSO as well as the rationality of the improved coalition generation model. The main research contents and innovations in this dissertation are as follows:First, the qualification that any agent only can participate in one coalition leads to task coalition ability demand conflict and can not optimize ability distribution of agents, which brings ability surplus of coalitions. A strategy of decomposing ability according to ability category is presented, and subagent is introduced to construct coalition generation model from small granularity of participants.Second, discrete particle swarm algorithm is adopted to solve coalition generation problem. Search divergence of particles is found during the evolution through analyzing the movement trajectory of particles. It causes particles search blindly, resulting in DPSO performance worse. Then, this paper introduces a modified DPSO through revising the movement equation of particles including the velocity equation and location transfer equation. On the basis of the modified DPSO (MDPSO), an algorithm for multi-task coalition generation is given including coding rules of particle and the strategies of particles' initialization and renewal. Finally, a group of experiments are given, the results of which show that MDPSO reduces the search divergence of particles effectively, and improves the performance of coalition, comparing with other algorithms. Besides, the improved coalition generation is superior to the tradition model in decreasing the waste of coalition ability as well as improving the profit of coalitions.