Study On Improved Differential Fish Swarm Optimization Algorithm For Solving Quadratic Assignment Problem

In the real life and engineering,the quadratic assignment problem(QAP)has a lot of applications,such as: selection of the factory location,layout of the integrated circuit,design of the typewriter keyboard,job scheduling and so on.The quadratic assignment problem is a discrete combinatorial optimization problem with NP-hard attribute,which is difficult to be solved in polynomial time.Thus,since Koopmans and Beckmann put forward the quadratic assignment problem in 1957,many scholars have been concerned with and studied the QAP problem,and proposed effective algorithms which mainly include three categories: classical mathematical methods,heuristics algorithms and evolutionary algorithms.But the former one category only adapted to the small-scaled QAP problem,the latter two categories still have research space.How to explore high-performance solution has always been an opening project.For the artificial fish-swarm algorithm(AFSA),requirement on the initial parameters is relatively smaller.The differential evolution algorithm(DE)has relatively faster convergence speed and stronger local search ability.Work of this paper is supported by Hunan province university science and technology achievement industrialization development project fund(No.2015CY010),which is to explore a hybrid solution of the AFSA and DE for the QAP.The main innovations can be summarized as follows.1.An improved fish swarm optimization algorithm(IFSOA)is proposed to solve the QAP problem.(1)An exhaustive search foraging behavior with step size of 1 is presented to improve the foraging efficiency.(2)In the improved random behavior,the new state of individual fish inherits some of the optimal fish's state components,so as to avoid the blindness of the random behavior.(3)By randomly selecting the visual field size to maintain the diversity of the population.Experiments show that the proposed IFSOA is superior to the basic artificial fish-swarm algorithm.2.An improved differential fish swarm optimization algorithm(IDFSOA)is proposed to solve the QAP problem.The mutation,crossover and selection operators of the differential evolution are defined for QAP problem.Combined with the improved fish swarm algorithm,the local search ability and the convergence speed are improved.Numerical experiments show that the calculation efficiency and solution accuracy of the proposed IDFSOA are better than those of other existing methods.This dissertation discusses the improvement of the basic fish swarm algorithm and differential evolution algorithm for the QAP problem.And through their combination,IDFSOA is proposed and it has a stronger searching ability and higher solution precision.The example of the QAPLIB verifies the good performance of the proposed IDFSOA.I hope that the proposed algorithm can be extended to other combinatorial optimization problems.