一种求解单任务Agent联盟生成的贪婪算法

联盟是多Agent之间一种重要的合作方法,如何生成面向某个任务的最优联盟是一个复杂的组合优化问题.提出一种贪婪算法:逐步选择加入联盟的Agent,直到联盟的能力满足任务要求,此时完整的联盟被生成.在联盟生成过程中,任一Agent加入联盟的贪婪准则是它能否比其他Agent带来更大的能力和更小的成本.实验结果表明本算法是切实可行的.

Searching for Agent Coalition for Single Task Using Greedy Algorithm

Coalition is an important cooperative method in Multi-Agent System (MAS). It is a complicated combinatorial optimization problem to search for the optimal,task-oriented Agent coalition. A greedy algorithm was proposed to solve the problem. During the process of solution,the "best" Agent was chosen to form the optimal coalition each time according to the greedy criterion. With the increment of the number of Agents in the optimal coalition,the ability of the coalition was also improved and finally sufficient to perform the task. When it was able to fulfill the task,the optimal coalition was established completely. The greedy criterion is that the more ability and the less cost are brought to the optimal coalition by an Agent,the better the Agent is. The results of contrastive experiment show that this algorithm is effective.