Some Study On Optimization Problem Solving Based On Multi-Agent

The concept of agent roots in people's recognition to artificial intelligence: the final goal of artificial intelligence is to realize the agent which has intelligence and could handle affairs instead of people. This is why people devoted a lot of energy to the research on mental state of agent in the early stages. Then a great deal of models and theories were engendered one after the other, for example, the DBI model by Cohen-levesque, the DBI model by Rao-Georgeff and so on. But along with the deep research on agent, the cognition of agent has been extensive. Agent has become a method of describing intricate phenomenon, researching intricate system, and realizing intricate self-adaptive calculation. Presently, the research on theoretical study of mental state of agent and the agent based construction of application model are emphasized, but the research on the complex system itself and the role of agent in complex system are ignored in our country.At the same time, along with the development of communications infrastructure, computing technology and applications of computer network, a passel of difficult requirements of new applications have occurred in the fields of scientific calculation, business activities and so on. Distributed constraint optimization problem (DCOP) is a typical problem in them. DCOP is an optimization problem in large-scale, open and dynamic network environment. Besides the traditional optimization problem's characteristics of nonlinearity, binding and difficulty to model, it also has the characteristics of stochastic, dynamic evolution, territorial information, local control, asynchronously updating the state of network, which makes DCOP is more difficult to solve. Task scheduling and resource allocation in computing grid, QoS Multicast routing in multimedia network, performance optimization of agent based e-commerce system and logistics management in ERP, they all can be modeled as DCOP. Because of the high computational complexity and the difficulty to obtain global optimal solution, it's very difficult to be solved by centralized method. So, it's a challenging research topic in computer science to search for a problem solving mechanism which is large-scale, parallel and has the intelligent characteristic to solve DCOP, which is drawing more and more concerns to researchers.There is no centralized global control in the solving mechanism of DCOP, it adopts the distributed strategy of multi-solver. In the problem solving process, the solvers are asynchronous and independent, which have only local knowledge instead of global knowledge to solve this problem. Because the agent technology matches most characters of the solving mechanism of DCOP, it's believed as a very promising method. But the DCOP's characters of random and dynamic evolutionary require the problem solving system have strong self-adaptive ability, the characteristic of territorial information, local control and asynchronously updating the state of network require the problem solving system have flexible self-organizing capacity, the problem solving mechanisms which were supplied by current agent technology couldn't satisfy the above two requires very well. So, aiming at the characteristics of DCOP, we apply the features of self-adaptability and self-organization to agent technology, and research the general methods for solving DCOP. Not only they could provide new ideas to solve large-scale and complex DCOP, they also have very important sense to push the research on theory and application of the agent technology.So, optimization problem solving by a multi-agent system represents a promising approach to solve complex computational problems, and it's very valuable to research. Based on multi-agent system, this paper dose some research on optimization problem solving from three sides of solving global optimization problem , distributed constraint optimization problem and data clustering problem.First, when solving the global optimization problem, immune algorithm is usually a little poor in local search and evolutionary diffusion optimization is usually a little poor in global search. To this point, an immune evolutionary diffusion optimization based on immune algorithm and evolutionary diffusion optimization is proposed. This algorithm combines the advantages of immune algorithm and evolutionary diffusion optimization, on the one hand it maintains the diversity of colony through importing the niche algorithm, on the other hand it improves the efficiency of the algorithm through proposing a strategy of dynamically adjusting the parameter of step size. Experimental results show that this algorithm is better than Tisui's evolutionary diffusion optimization and Ingber's adaptive simulated annealing algorithm on efficiency and stability for a given precision. The strategy of dynamically adjusting the parameter of step size is analyzed at last.Second, distributed constraint optimization problem (DCOP) is the optimization problem emerging in large-scale, dynamic and distributed networks. Compared with traditional optimization problems, it has stochastic, dynamic, decentralized and asynchronous properties, which make it much more difficult to address. So far, there have been a lot of methods for solving DCOP. However, most of them are not completely decentralized and require global network structures as their inputs. In most cases, the assumption that we can obtain the global view of networks beforehand is not true due to their huge sizes, geographical distributions or decentralized controls. To solve this problem, in this paper, we present a self-organized behavior based divide and conquer algorithm, in which multiple autonomous agents work together to solve the DCOP through a proposed self-organization mechanism. Compared with existing methods, our algorithm is completely decentralized and demonstrates good performance in both efficiency and effectiveness.Third, aiming at the problem that most clustering algorithm must rely on the similarity, and clustering results are greatly influenced by the selection of the similarity function, a concept of k-nearest-neighbor (kNN) network is introduced, and this paper does some researches on spectral clustering from two sides based on kNN network. On the one hand, we convert the clustering data set to a kNN network, and then give its clustering result using G-N algorithm which was proposed by M.Girvan in 2002. Experimental results show that this method is better than standard c-Means algorithm on accuracy. On the other hand, we cluster the kNN network of clustering data set using the distributed network community mining (DNCM) algorithm which was proposed by Bo Yang in 2007, and compare it with the affinity propagation (AP) algorithm which was proposed by Frey in the same year. Experimental results show that this method is a little worse than AP algorithm on the value of objective function, but it is better than this algorithm on accuracy and iteration numbers. In addition, as a completely distributed algorithm, DNCM is more suitable for distributed clustering.This paper enriches the idea of multi-agent based optimization problem solving through the research on three sides of solving global optimization problem, distributed constraint optimization problem and data clustering problem using multi-agent based methods.