Research On Theory And Algorithm Of Agents Coalition Formation In Multi-agent System Based On PSO

The coalition of agents is an important collaboration way and a research hotspot inmulti-agent system (MAS). Due to its simple implementation, strong global search ability andgood robustness and distribution, the PSO algorithm is suitable for solving the problem aboutcoalition formation in complex systems. But the current coalition formation algorithm basedon PSO usually may trap into local optima easily and has a low convergence accuracy, thusinfluence the search efficiency to optimal coalition.After the intensively study on the theories of multi-agent coalition formation and thePSO algorithm, this dissertation systematically researches the theory and algorithm of theagents’ coalition problem based on PSO. The main work includes:(1) Proposed an improved BPSO algorithm with the experience factor. The newalgorithm exploited the experience factor, which could reflect the historical information ofparticle’s position, to influence the speed update of particles and therefore improving theoptimization process. In order to avoid the excessive dependence of particles’ historicalexperience information, the algorithm regulated the historical information through the rewardand punishment mechanism and a history forgotten coefficiency, in the end, combinedempirical weights to determine the final effect of the experience factor. The experimentsshowed that the new algorithm could achieve better results both in convergence speed andglobal search ability.(2) Used the experience factor with BPSO algorithm for solving multi-agent coalitiongeneration problem, and analyzed disadvantages algorithms to solve this problem. Then,proposed a BPSO algorithm based on experience propelled to solve the problem of coalitiongeneration. The novel algorithm takes advantage of the particle’s previous worst location andits group’s previous worst to update particles’ velocity. The results of the experiments showedthat the novel algorithm can achieve better results not only in the speed of searching optimalcoalition value, but also the ability for global searching, compared with the BPSO algorithmwith experience factor.(3) Proposed a coalition formation strategy based on loyalty. New strategy introduced theconception of agent’s loyalty, based on if one agent leave the coalition before finish the taskor not during agent taking part in a coalition every time, the agent’s loyalty would get relevantupdate. At the same time, new strategy decided the coalition utility allocation by means ofcombining each agent’s loyalty and their ability to finish the task. Theory analysis and theresults of the experiments show that the novel strategy can improve the justice of allocationfor utility and achieve a global optimal solution, which is stable, speedy and simple.