Study On The Solving Of Optimal Assignment Problem Based On Intelligent Computation And Its Application

Optimal Assignment Problem(OAP) is one of classical problems in Operation Research,which applies in many fields widely,such as production dispatching,transportation planning,material flow management,decision support system and so on.With the purpose of solving the OAP and its expanded problems,Genetic Algorithm(GA) and Particle Swarm Optimization(PSO) are introduced,and some new algorithms based on Intelligent Computation are proposed,which are well applied to solve some key problems in the designment of robot soccer decision-making system.Firstly,the definition and mathematic model of standard OAP is discussed.According to the actual issues,some general OAP are deduced, and their transformations to standard model are explored.After analyzing the principle and algorithmic process of Hungary Algorithm(HA),its drawbacks are discussed.Secondly,a new algorithm for OAP based on improved GA is designed. In the algorithm,a strategy of crossing over with the best individual is introduced,and a new adaptive method for the probabilities of crossover and mutation is proposed,which possesses a nice global guidance and enhances rapidity of convergence.The algorithm is tested in a general OAP,an OAP which is not convergent with Hungary Algorithm,and compared with Adaptive Genetic Algorithm(AGA) in OAPs with different dimensions. Experiments show the algorithm is effective,well adaptive,and better than AGA at convergency.Thirdly,PSO's principle and model are introduced systematically,and its important developments are reviewed.After discussing the OAP model based on permutation and combination,an algorithm for OAP based on PSO is proposed.In the algorithm,the model of velocity-displacement is reserved; with a view to the discreteness and particularity of OAP,the particle's velocity,displacement and their update mechanisms are redefined;an improved strategy for population diversity is introduced.Experiments show that,the algorithm is not only well effective and adaptive in general OAPs, but also good at large-dimension OAPs.And improved PSO is better than improved GA at solving the OAP.Fourthly,for dealing with the existing problem in formation selection and role assignment,the methods of formation compound in formation determining layer and role assignment aiming to global optimum in formation implementing layer are purposed;and the algorithm for OAP based on PSO is applied in;consequently,the formation continuity problem and formation stability problem are solved.Finally,the decision-making system is designed and implemented for Federation of International Robot-soccer Association's(FIRA) Large League SimuroSot(LLS),in which the research results above are applied.The system is served for Wuhan Institute of Technology in many domestic and international competitions,and has best rewards.Practice proves that the system meet the demand of FIRA LLS excellently.