Research On Solving Uncapacitated Facility Location Problem Based On Evolutionary Algorithms

With the rapid growth of the world economy and the overall progress of modern science and technology,industries such as industry,transportation and computers have developed rapidly.The profits of many industries depend to a large extent on their geographical location.One of the most important strategic decisions is facility location.The uncapacitated facility location problem(UFLP)is a basic location problem,but it is difficult to solve at present,and with the increase of the scale of the problem,the difficulty of solving the problem increases exponentially.Evolutionary algorithms(EAs)has polynomial time complexity and can quickly obtain the optimal solution or approximate optimal solution of the problem.Therefore,EAs has gradually become one of the important methods for solving UFLP.At present,most of the evolutionary algorithms are based on real number operations and can not be directly used to solve UFLP.In order to overcome this defect,scholars at home and abroad have proposed many methods to transform continuous evolutionary algorithms into discrete evolutionary algorithms,in which the conversion method using transfer functions is not only simple to operate,but also more universal.Transfer functions has become a hot research topic.In this paper,we choose a novel discrete evolution algorithm: optimization algorithm based on group theory and a classical continuous evolution algorithm: differential evolution algorithm to solve the UFLP problem.The following is an overview of the research content of this paper:First of all,the group theory-based optimization algorithm(GTOA)is used to study how to solve the UFLP problem quickly and efficiently.According to the inherent characteristics of UFLP,a new local search operator,one direction mutation operator(ODMO),is proposed.Then,a redundancy check strategy(RCS)for further optimization of feasible solutions is given.On this basis,an enhanced group theory-based optimization algorithm(EGTOA)is proposed to solve UFLP rapidly.For 15 UFLP benchmark instances,compared with the existing algorithms,the results show that the performance of EGTOA is better.Secondly,in order to effectively use differential evolution to solve the UFLP problem,on the basis of the existing S-shaped transfer function and V-shaped transfer function,this paper proposes a new class of coding transfer function: Taper-shaped transfer functions,and gives a novel binarydifferential evolution algorithm based on taper-shaped transfer functions(denoted as NBDE).On the basis of keeping the original evolution mode of DE,NBDE uses the taper-shaped transfer functions to transform the real vector encoded by the individual into 0-1 vector.In order to test the performance of NBDE and the effectiveness of the new transfer function,NBDE is compared with the binary differential evolution algorithm based on S-shaped transfer function(S-NBDE)and the binary differential evolution algorithm based on V-shaped transfer function(V-NBDE),and the superiority of taper-shaped transfer functions are illustrated.The comparison with the existing algorithms for solving UFLP shows that T-NBDE is very competitive.