Research On The Artificial School Algorithm For Quadratic Assignment Problem

The factory workshop location, hospital layout, the design of computerkeyboards, the task matching and scheduling can be transformed into thequadratic assignment problem solved. Theoretically speaking, the quadraticassignment problem belongs to the combinatorial optimization problem, wherecombinatorial explosion phenomenon exists. Due to the NP-hard property, it isvery difficult to obtain the optimal solution i n the polynomial time. Up to now,many scholars have conducted in-depth exploration, and obtained a lot of resultson it. The effective algorithms can be divided into the following two types:(i)exact algorithms, for example, branch and bound algorithm, d ynamicprogramming algorithm, etc;(ii) the random search algorithms, such as, geneticalgorithm, simulated annealing algorithm, ant colony algorithm, particle swarmalgorithm, tabu search algorithm and artificial fish school algorithm, etc.The artificial fish school algorithm (AFSA) is an intelligent algorithm forsolving optimization problems based on the model of the autonomous bodies ofanimals. Its mechanism and framework are different from the previousintelligent optimization algorithms. Meri ts of AFSA include that the initialpopulation requires low quality, both setting of parameters and its evaluationfunction are simple, and it possesses global optimization capability andpotential parallelism. Currently, some scholars combined AFSA with sometraditional methods for solving other optimization problems, such as, theoptimization problem of pump parameters of gain flattened Raman fiberamplifiers, the coverage optimization problem of the WSN network, TSP and thestock index prediction.This research is supported by National Natural Science Foundation andResearch Foundation of Education Bureau of Hunan Province. The project groupfocus on discussion of the heuristic strategies of quadratic assignment problem.By using fish school algorithm for quadr atic assignment problem, we haveobtained a number of results. The main works and innovations are as follows:1. A heuristic strategy is put forward for the quadratic assignment problem.Related knowledge is obtained from the information of the known matrices andthis knowledge is used to calculate the heuristic factor of probability of eachfactory location. Following by roulette wheel selection to get the location ofeach factory and calculate the evaluation value of location scheme. Its heuristicsearch algorithm is that the heuristic strategy used in constructing location scheme with n locations, the best location scheme is obtained through severaliterations. The proposed experimental results show the feasibility andeffectiveness of this heuristic strategy.2. In view of the quadratic assignment problem, a hybrid artificial fishschool optimization algorithm for the quadratic assignment problem is putforward. Firstly, the initial population is constructed by heuristic strategy. Thenthree improved behaviours are proposed, which are preying, clustering andfollowing, and different visual distances are selected, a reasonable movingmethod is proposed for artificial fish individuals. Finally, in order to strengthenthe local search ability, the differential evolution operator is proposed.Experimental results show that the proposed algorithm is superior to existingalgorithms in performance.Quadratic assignment problem has wide application background. In thisresearch, the initial solutions are constructed by heuristic strategy, further theimproved hybrid optimization algorithm is used for this problem. The resultsshow better stability and faster convergence. Finally, the author hopes thisalgorithm can be extended to other combinatorial optimization problems whichcan contribute to solve these problems.