Research On The Maximal Successful Coalition Problem Under The Strict Goal Preferences Of Agents

Coalition structure has always been a research hotspot in the field of multi-agent systems(MAS)and artificial intelligence.It mainly studies how to construct coalitions and which coalition can form to maximize the total return of the system.However,most of the existing work does not consider the preference of the agent for the goal,that is,each agent can participate in any goal,even if the agent has no interest in these goals.In some special application scenarios,such as a multi-camera collaborative monitoring system with limited angles of view,the behavior of each smart camera has a strong goal preference,and it will only respond to the goals that can be captured in its monitoring area.Other goals are powerless;for example,in disaster emergency response,due to the high timeliness requirements of emergency response,each reserve point will first meet the needs of the nearest disaster site,and it is impossible to spend a lot of manpower and material resources to respond the needs of distant disaster sites.In view of the above background,this thesis considers the strict goal preference of the agent for the response goal based on the traditional coalition resource games,and research on the maximum successful coalitions problem under the strict goal preference.The main research work of this thesis is as follows:(1)Introduce the relevant research background,as well as the domestic and foreign research status of coalition structure,especially coalition resource games,analyze and summarize the current deficiencies in the research of the largest successful coalition generation problem,to determine the research motivation and Main research content.(2)Introduce the relevant basic theoretical knowledge,including the relevant concepts of MAS and coalition,and the relevant theory of coalition structure.Finally,several classic optimization algorithms related to this thesis are introduced,including genetic algorithm,particle swarm optimization algorithm and maximum flow algorithm.(3)According to the agent's strict preference for the goal,the traditional coalition resource games model is improved based on the "resource contribution" and "resource surplus",and the necessary and sufficient conditions for a successful coalition and the search for the largest successful coalition are theoretically analyzed The computational complexity of the problem.(4)For the largest successful coalition(LSC)problem under strict goal preference,an exponential deterministic solution algorithm(FNet EA)was designed based on the maximum flow network to obtain the LSC problem Global optimal solution.In order to improve the efficiency of problem solving,a two-dimensional hybrid search algorithm(2D-HA)was designed based on genetic algorithm,twodimensional binary coding and heuristic correction method.Comparing the experimental results,the 2D-HA algorithm shows very good effectiveness and efficiency in solving LSC problems,and it can find the same optimal as the deterministic algorithm FNet EA in a very short time on large-scale LSC problems.Solution,and the performance of the 2D-HA algorithm is not affected by the number of agents,the number of goals,and the number of resources,and is very robust.