Research On Teaching-learning-based Algorithm And Application For Several Kinds Of Complex Combinatorial Optimization Problems

Combinatorial optimization is a class of optimization problems.Many optimization problems in real life can be abstracted as combinatorial optimization problems.The combinatorial optimization problem is an NP-hard problem so that many researchers use evolutionary algorithms to find approximate optimal solutions.The teaching-learning-based algorithm is a new intelligence evolutionary algorithm that simulates the process of teacher teaching students and students learning from each other.The teaching-learning-based algorithm has the advantages of simple model and high computational efficiency.This paper studies the teaching algorithm and its application in several complex combinatorial optimization problems.The main contents are as follows:(1)Presenting a novel teaching-learning-based optimization algorithm with group collaboration(GC-TLBO)for job shop scheduling problem(JSSP).First,a collaborative learning strategy between groups is introduced to avoid being trapped into local optimum when solving JSSP with high complexity.After learning within the group,individuals would communicate and collaborate with individuals of other groups so that they can jump out of the limitation of the current learning process.Second,in order to balance the local and global searching ability,a depth or width searching strategy is introduced,which enables individuals to learn in different ways according to their learning ability.For individuals with stronger learning ability,the depth learning will be adopted and for individuals with weaker learning ability,the width learning will be adopted so that different individuals can play different roles in the learning process.Experimental results on benchmark instances of OR-Library show that the search ability and convergence accuracy have been effectively improved in solving job shop scheduling problem.(2)Using a heuristically initialized GC-TLBO to solve a class of Traveling Salesman Problem(TSP)with clustering properties.Order ordering optimization problem in intelligent storage system is abstracted as a class of TSP problems with constraints and clustering properties.The simulation experiments verify the effectiveness of the heuristically initialized GC-TLBO algorithm in solving such problems.(3)For the MTSP problem involving the assignment and optimization of multiple tasks,ateaching algorithm based on a novel crossover operator(NC-TLBO)is proposed based on the GC-TLBO.A novel crossover operator is used on the teacher phase and student phase,and three novel self-learning operators are used in the student self-learning phase.Depending on the research and analysis of the ordering problem upon the quadruped robots,it can be summarized as a Multiple Traveling Salesman Problem(MTSP)with constraints.The effectiveness of the proposed NC-TLBO algorithm in solving this type of MTSP is verified by simulation experiments.(4)Proposing a improved teaching-learning-based algorithm based on the combination of variable-step strategy and the critical path(CP-TLBO)for solving FJSP with reentrant property.Designing a novel coding method combining with sequence coding method and process coding method.Individuals with stronger learning ability perform local search with variable steps,and individuals with weaker learning ability perform global search based on the critical path.Depending on the research of the scheduling problem of the immunodetection device,summarizing it as a FJSP with complex constraints and reentrant properties.Verifying the effectiveness of the proposed CP-TLBO algorithm in solving this type of FJSP by simulation experiments.