A Cross-entropy Approach To The Permutation-based Combinatorial Optimization Problems

The permutation-based combinatorial optimization problems(COP's),which have attracted lots of research interests,may arise in many important applications among a vast range of domains,such as industrial manufacturing,logistics,and economic management.Among different kinds of optimization algorithms,the simulation-based ones have been the research hotspot in recent years.In order to improve the efficiency of the optimization algorithms,it is of great importance to combine the specific properties of the problems into the design of the algorithms.In this thesis,the simulation-based cross-entropy method is applied to the permutation-based COP's,whose properties are utilized to design the cross-entropy method.Two representative problems are of concern,specifically the linear ordering problem and the single row facility layout problem.For the linear ordering problem,a new algorithm is proposed to obtain a reduced solution space for the problem,which is inferred according to the properties of the local optima.Comparing to the existing algorithm,the proposed algorithm is more efficient as certain unnecessary calculations are avoided.Correspondingly,an algorithm is designed for generating feasible solutions in the reduced solution space.Meanwhile,a local search procedure,adapted from an existing one,is combined with the cross-entropy method to further improve the search efficiency.The modified local search procedure performs local searches in the reduced solution space,which is more efficient than the existing one.As for the single row facility layout problem,it is a generalization of the linear ordering problem.We first deal with a special case of the problem where the feasible solutions possess a symmetry property.A symmetry-breaking strategy is designed and utilized to improve the cross-entropy method.Besides,a local search procedure taking into account the strategy is integrated into the implementation of the cross-entropy method.In addition,the extension of the designed cross-entropy method is discussed in order to tackle other general cases of the problem.The cross-entropy based algorithms,designed for the linear ordering problem and the single row facility layout problem,are tested on the corresponding commonly used benchmark instances,respectively.Their performance is compared with several existing metaheuristics.The computational results show that the designed cross-entropy algo-rithms perform well for these two representative COP's and are competitive with the existing metaheuristics.The work in this thesis is of reference value and significance for applying the simulation-based optimization algorithms to the COP's and designing other intelligent optimization algorithms.