Differential Evolution Based On Stagnation Detection And Correction And Its Application In Large Scale Packing Problem

There are many optimization problems in real life,some of which have linear objective functions,while others are non-linear optimization problems,such as combinatorial optimization problems.Some combinatorial optimization problems cannot be solved within a reasonable amount of time,and even experience the phenomenon of "combinatorial explosion".Intelligent optimization algorithms are a class of heuristic search algorithms that can effectively deal with the problem of "combinatorial explosion" and find an approximate solution to the problem within a reasonable time frame.During the continuous research and development of intelligent optimization algorithms,differential evolution has been widely researched and used in various fields due to its self-adaptation and high robustness.However,differential evolution also has its own shortcomings,such as easy early convergence and getting stuck in local optima.To address these problems,this paper proposes two improvements for differential evolution: stagnation detection and stagnation correction,and introduces a new concept of clustering degree Do A to determine the state of the population.The differential evolution based on stagnation detection and correction proposed in this paper is tested on 57 benchmark test functions in CEC2013 and CEC2017 test sets,and is compared and analyzed with 8 other algorithms.The experimental results prove that this algorithm can achieve good results in dealing with single-peak and simple multi-peak problems.In addition,the experimental results prove that the algorithm has certain advantages compared to other algorithms in dealing with complex multi-peak problems.To further validate the effectiveness of the method,this paper applies the differential evolution algorithm based on stagnation detection and correction proposed in this paper to the large-scale three-dimensional packing problem.The packing problem prototype is widely used in logistics transportation,industrial production,management and scheduling fields,among others.The three-dimensional packing problem is the most common and complex type of packing problem,and how to improve loading efficiency and reduce time consumption is the key issue in algorithm research.Among the two mainstream algorithms for studying packing problems,heuristic packing algorithms have fast execution time but low packing efficiency,while intelligent optimization algorithms have high packing efficiency but slow execution.Therefore,how to combine the advantages of the two types of algorithms,both to ensure high packing efficiency of the algorithm and to minimize the algorithm execution time,is a problem that must be solved when dealing with large-scale packing problems.In view of the characteristics of large-scale three-dimensional packing problems,this paper proposes the "pack first,unpack later" strategy,and verifies the advantages of this strategy in dealing with large-scale packing problems through experiments and complexity analysis.Based on this strategy,this paper proposes two improvements: the secondary clustering and the three-dimensional optimal fitting algorithm based on grid coverage,and combines them with the differential evolution algorithm based on stagnation detection and correction to propose a new hybrid packing algorithm.Through experiments on the Huawei packing dataset,the effectiveness of the grid coverage optimization strategy and the hybrid packing algorithm proposed in this paper are verified.Testing on 1500 packing test cases with BR,through comparative analysis with four other algorithms,it is proved that the hybrid packing algorithm proposed in this paper has significant advantages in dealing with weakly heterogeneous three-dimensional packing problems.