Research On Representations And Evolutionary Optimization Algorithms For Combinational Optimization Problems

As a type of important optimization problem,the combinatorial optimization covers a wide range of fields,such as information technology,industrial engineering,transportation and economic management.Therefore,the study of combinatorial optimization is of great practical significance.With the development of artificial intelligence,since the 1980s,the evolutionary algorithm has gradually become an important technology to solve combinatorial optimization problems,and has been widely used in many fields.In the study of solving combinatorial optimization problems using intelligent optimization algorithms such as evolutionary algorithm,the representation of problems determines the size and toplogy of the searching space,and therefore,determines the difficulty of problems and affects the performance of optimization algorithms to a large extent.Therefore,this paper takes solving combinatorial optimization problems as the core purpose,focusing on designing the representations and single-objective,multitasking and multi-objective evolutionary optimization algorithms for combinatorial optimization problems.The main work can be summarized as follows:1.To solve constraint satisfaction problems,the hybrid representation that combines the direct and indirect representatopn is designed,and the corresponding multi-agent evolutionary algorithm is designed based on the hybrid representation.The hybrid representation combines the advantage of simplicity and easy evaluation of the direct representation with the advantage of the indirect representation that can generate high-quality solutions via heuristic decoding.In addition,several behaviors of agents in the multi-agent evolutionary algorithm are designed according to the characteristics of the problems and the hybrid representation,including neighborhood crossover operator,mutation operator,and self-learning operator.The proposed hybrid representation-based multi-agent evolutionary algorithm is validated on 250 binary constraint satisfaction problem sets and 79 graph coloring problem sets.The experimental results show that the multi-agent evolutionary algorithm based on hybrid representation has better performance than those based on either direct or indirect representations.2.To solve the resource-constrained project scheduling problems,a new representation,namely,moving block sequence,is designed.The moving block sequence consists of two parts:block sequence and moving modes.A block represents an activity in a project.The duration of each activity can be considered as the width of the block,while the resource demand can be considered as the height of the block.Four initial positions and corresponding moving modes are designed for blocks.The decoding procedure is to move each block from its initial position to an appropriate position according to its moving mode.Based on the moving block sequence representation,the multi-agent evolutionary algorithm for solving the resource-constrainted project scheduling problems is designed.In addition,several behaviors of agents in the multi-agent evolutionary algorithm are designed according to the characteristics of the problems and the new representation,including neighborhood crossover operator,mutation operator,forward-backward improvement operator.and self-learning operator.The performance of the designed moving block sequence-based multi-agent evolutionary algorithm is verified on the benchmarks of-resource-constrained project scheduling test sets J30,J60,J90,and J120.The experimental results show that the designed multi-agent evolutionary algorithm has good performance,especially in solving large-scale test sets.3.A new hyper-heuristic framework,namely,the evolutionary multitasking graph-based hyper-heuristic,is designed,and the performance of the framework is verified on the examination timetabling problems and graph coloring problems.As a kind of algoritluns to select or generate heuristics,hyper-heuristics are of good generality;however,the current research is limited to the single-task optimization.The characteristic of evolutionary multitasking optimization is that multiple tasks can be optimized simultaneously,and there is no special requirement on the relationship among tasks.In the evolutionary multitasking optimization,the solutions of diff-erent tasks are mapped to the same search space through the unified representation at first,then after optimized in that search space by general solvers,it will be decoded back to the original search space of each task for the purpose of evaluation.Multitasking optimization not only has the ability of cross-domain searching,but also the ability of knowledge-transfer.This framework introduces the concept of multitasking into the hyper-heuristics for the first time,which endows hyper-heuristics the ability of knowledge-transfer.and further improves their generality.Meanwhile,the framework extends the unified representation in evolutionary multitasking optimization to the heuristic search space at a higher level,which also inproves the generality of the evolutionary multitasking optimization.The experimental results on multifactorial optimization problems including 2,3,4 and 5 tasks show that the designed hyper-heuristic framework is of high efficiency,good asynchronous optimization,cross-domain search ability,and robustness.4.A new problem model for Chinese high school timetabling problems under the new curriculum innovation is proposed,which fills the gap in the problem model of optional class timetabling in China.The main feature of this model is the introduction of timetabling of optional classes,based on which,the representation of the solution including timetables of administrative and optional classes is designed,and a two-phase simulated annealing algorithm is used to solve the proposed problem model.Firstly,the effectiveness of the the designed representation and two-phase simulated annealing is verified on 45 synthetic test sets of different sizes,and the convergence of the algorithm is analyzed as well.Then,the applicability of the proposed model and the effectiveness of the designed representation and two-phase simulated annealing algorithm are further verified on the timetabling for 10 real high schools.5.Firstly,the performance of the decomposition-based multi-objective evolutionary algorithm(MOEA/D)with the global replacement strategy is verified,and the influence of different reference points on the algorithm is analyzed in solving many-objective knapsack problems.Then,an improved global replacement strategy is designed to handle the problem of the failure of global replacement strategy when the utopia point is used as the reference point.The experimental results on a set of many-objective knapsack problems with up to 8 objectives show that the improved global replacement strategy can update the solutions of boundary subproblems more efficiently,thus to maintain a better diversity of the population.