Research On The Application Of Swarm Intelligence Algorithms For Quadratic Assignment Problem

The main contents of this dissertation are the application of swarmintelligence computation on quadratic assignment problem. The algorithmsthis dissertation involved are Ant Colony Algorithm and Particle SwarmOptimization.Swarm intelligence algorithm is a simulated evolutionary method thatsimulating the behaviors of social insects searching for food and building ofnest. It produced the best suitable individual by adapting to the change ofthe environment. The course of searching and optimizing is used to simulatethe course of the individual evolution or searching for food, and it usesthose dots existed in the searching space to analog the individual in thenature;It uses the goal function to measure the individual's adaptivecapacity to the environment;the course of survival of the fittest individualor searching for food is used to simulate the iterative course that using thefeasible solution to replace the bad solution in the searching and optimizingcourse. Thus an iterative searching algorithm are formed, which has thecharacteristic of "create+measure ", it is a self-adaptive and self-organizingartificial intelligence technology and it is main in solving the extreme valuequestion.Swarm intelligence algorithm uses Reynolds model to simulate thesport of the whole colony so as to the iterative searching course of thealgorithm turns into one course that utilize constantly individual extremevalue and colony extreme value to revise the itself ,and it have realized themutual and cooperation about individual information and colonyinformation. The individual extreme value has certain randomcity, andkeeps the variety of searching direction in a way so as to avoid getting intothe local optimum too early;the colony extreme value holds the excellentsearching direction on the whole, so as to guarantee the convergenceproperty of the algorithm. Due to having these advantages, swarmintelligence algorithm is still at primary researching stage and has a lot ofdifficulty, but we can prophesy that it is an important direction of computerresearch and development.Ant colony algorithm is a new simulation evolution algorithm. At thefoundation of studying on collective behavior of the true ant colony in thenature, it is put forward by Dorigo .etc, scholar of Italian. Ant colonyalgorithm simulates the cooperation course of the true ant colony, and thealgorithm is executed together by a lot of ants. Each ant independentlysearches for solution in the candidate solution space, and at the same timeleaves certain amount of pheromone on the fined solution. The performanceof the solution is better, and more pheromone will be stayed. If the solutionhas much more pheromone, it is more possibility chose. Amount ofpheromone of all solutions are same in the primary stage, but thepheromone of the better solution will increase with promotion of algorithmand the algorithm will converge gradually.Particle Swarm Optimization is a new developed algorithm in recentyears. Particle Swarm Optimization was firstly proposed by Kennedy andEberhart in 1995, and it is an evolutionary algorithm based on iterations.Particle swarm optimization mainly considered the two domains: artificiallife, PSO was inspired by the process of searching food of bird flock andfish school, especially Swarm Theory, on the other hand, evolutionarycomputation, especially has ties to genetic algorithm and evolutionaryprogramming. In the description of PSO, the Swarm is made up of a certainnumber of particles, at each iteration;all the particles search the globaloptima in the n-dimensional space. The position and velocity of eachparticle are updated by certain formulas. In the searching process, eachparticle is influenced by the three factors: the current velocity of the particle,the best history experience of the particle and the global best experience ofall the particles.The Quadratic assignment problem is a classic combinationaloptimization problem, which is NP-hard 。It can be described as follows:Given a set of n facilities and n locations;, a flow matrix A=(fij),whereeach element fij denotes a flow const between the facility i and facility j;adistance matrix B=(dij),where dij denotes a distance between location i andj. Our aim is to find the permutation p=(p(1),p(2),…,p(n)) that minimizes( ) ( )1 1( )n nij L i L ji jC p f d= == ∑∑Here L(i) denotes the location that facility i is assigned, p∈π (n).Ant colony algorithm has succeeded in many discrete problems. Butwhen solve the combinational problems, the basic ant colony algorithm hasthese disadvantages , such as slow convergence speed,tend to get into thelocal optimum. By way of increasing the global searching capacity and thespeed, in this dissertation we use a dynamic and adaptive ant algorithm tosolve the quadratic assignment problem, and presents 3-opt algorithm to theproblem (QAP). The results from the experiments on different QAPinstances show that this algorithm is able to find good solutions quickly.Especially, the algorithm is able to solve the large QAP instance preferably,but the ancient algorithm is only able to solve the small QAP instances.Particle Swarm Optimization, as a novel evolutionary computingtechnique, has succeeded in many continuous problems, but research ondiscrete problems especially quadratic assignment problem has been donelittle. In this dissertation, a Particle Swarm Optimization (PSO) algorithmwas proposed to solve QAP, which is a well-known NP-hard problem. Thealgorithm searched in the Cartesian continuous space, constructed amapping from continuous space to discrete permutation space of QAP, thusto implement the space transformation. Then the algorithm was tested withconcrete examples in QAPLIB, and compared with GH and GAHRR,experiment shows that the algorithm can achieve good results.