Research On Overlapping Coalition Formation Theory And Its Applications In Multi-Agent Systems

Research of coalition formation is a very important research topic in the field of multi-agent systems(MAS),how to form an efficient coalition between agents is a difficult problem in the coalition formation.In the MAS,because of the limit of a signal agent's resource and ability,agents complete the tasks in the system by means of alliance between agents.An agent is restricted in a coalition in the traditional research,which means that when a coalition is formed,even if an agent in the coalition has enough resource,it can not participate in another coalition.So,the utilization of agent resources and capacity can be wasted,thus affecting the efficiency of the whole system and not meeting the requirements of the actual application.For this reason,the research studied the structure generation,payoff distribution and application of the overlapping coalition in the dissertation,realized one agent can join multiple coalitions to take on multiple tasks simultaneously.In this way,it can increase the agent's resource utilization rate and system's efficiency of solving problems.Furthermore,it can form more intelligent complex systems and provide theoretical guidance and method basis for the research and development of the actual complex systems so as to promote the development of emulation technology in complex systems.First,the dissertation introduces the relevant algorithms of coalition structure generation and analyses their performance.In the case of non-overlapping coalition and overlapping coalition with multi tasks serial,each agent can only participate in the corresponding to solution coalition of one task at the same time,and will not generate resource conflict.In the overlapping coalition structure generation with multi tasks concurrency,resource conflicts will take place in the case of limited agent resources.It is necessary to encoding repairs in order to resolve resource conflicts.Through the analysis of the existing encoding correction algorithms,we point out their respective advantages and disadvantages of these algorithms,which provide the theoretical basis and method guidance for later research.The main research contents and innovations of this dissertation are as follows:(1)Design an algorithm of overlapping coalition structure generation based on differential evolution and encoding repairs.An agent may join in multiple solving coalitions of different tasks at the same time in the overlapping coalition.Because the resources of each agent are limited,the problem of resource conflict will be taken place with resource competition among the solving coalitions of different tasks.In order to portray the problem,the traditional differential evolution is extended to an three-dimensional integer encodings in this dissertation.Each element of the encodings represents the actual contribution amount of one type of resource of an agent to a task.In addition,the corresponding individual correction strategies will be designed to evaluate and solve the possible resource conflict of encodings.The experiment results show that the proposed algorithm can obtain the shorter time of encoding correction and the better value of coalition structure.(2)Propose a payoff distribution strategy of overlapping coalition for concurrent multiple tasks.For the existing payoff distribution is performed serially with multiple tasks,we propose a payoff distribution strategy of overlapping coalition for concurrent multiple tasks.Based on the idea of more abilities for more works,multiple concurrent tasks are dispatched in parallel by proportional allocation.Meanwhile,the payoff of overlapping coalition is distributed according to the results of task dispatch.Then,a sufficient and necessary condition that one agent satisfies the principle of non-reducing utility when it joins multiple coalitions at the same time is deduced.Finally,the effectiveness of the proposed method is proved by an example,and a comparative analysis between the proposed strategy and the serial utility allocation is carried out.The result shows that when a new agent applies to join coalition,the proposed strategy can satisfy the condition of non-reducing utility more easily and it has better timeliness.(3)Apply the research of overlapping coalition to virtual enterprise partner selection,solve virtual enterprise partner selection based on non-dominated sorting genetic algorithm-?(NSGA-?).In view of the existing research about virtual enterprise partner selection,which is serial execution of a single project,we build a model of multiple projects concurrent execution about virtual enterprise partner selection,design an algorithm of virtual enterprise partner selection with multi objective optimization based on NSGA-?,and compare with the method of single objective optimization through the experiment.The experimental results show that the multi objective optimization of virtual enterprise partner selection can obtain multiple Pareto optimal solutions,which can provide more decision alternatives for decision makers.