Multi-solution Optimization Algorithms And The Application To Itinerary Planning

There are a large number of optimization problems in the fields of traffic dispatch,network transportation and economic management.The optimization problem that has multiple optimal solutions is named multi-solution optimization problem.The multi-solution optimization problem requires algorithms to find all the optimal solutions in the feasible solution space.Providing multiple optimal solutions for researchers,decision makers and executors demonstrates both significance in scientific research and practical value in engineering.Evolutionary computation is a paradigm of optimization method utilizing population-based heuristic search.With good adaptability and self-organization capabilities,the algorithms can solve optimization problems efficiently and flexibly.However,the traditional evolutionary algorithms will form global convergence and cannot be used to solve multi-solution optimization problems.Researchers introduce the concept of niching into the evolutionary algorithms to specify the resource competition area and maintain population diversity,and hence achieve multiple convergence of search.Therefore,the niching evolutionary algorithm can effectively solve the multi-solution optimization problems.According to the classification of decision variables,the problems can be divided into continuous and discrete multi-solution optimization problems.Researchers have proposed a large number of improved niching evolutionary algorithms for the continuous multi-solution optimization problems.However,these algorithms suffers from low utilization of historical information and low search efficiency.On the other hand,discrete optimization research is still in the infancy stage that there is lack of efficient solution methods and there is no comprehensive performance test framework.In addition,most multi-solution optimization methods are tested on the benchmark test suite only.Therefore,their performance has not been verified in real-world application scenarios.To tackle the above problems,this article studies from three aspects: continuous multisolution optimization research,discrete multi-solution optimization research and practical application of multi-solution optimization.Based on these three aspects,a series of researches are carried out around niching evolutionary algorithms.The main contributions of the work are summarized as follows:(1)For continuous multi-solution optimization,we propose a probabilistic niching evolutionary computation framework based on binary space partition tree,in order to make full use of historical information and improve the niches' search efficiency.The continuous multi-solution optimization algorithms generate the population of the next generation based on the current population and specific evolution strategies,but they ignore information of the solution space visited by the population.Niches are subsets of the population.The niches are more likely to converge locally and lead to stagnation of evolution.Sometimes,the niches conduct repeated searches that cause low search efficiency.To solve these two problems,this paper first designs an enhanced binary space partition tree for structured storage of historical information in the search process of the algorithm,providing efficient information retrieval and data access capabilities.Based on the structurally stored information,a probabilistic niching evolution framework is proposed.The framework can mine the feasible search space,resample the convergent and redundant niches and further improve the search ability of niches.The framework is so generic that it can be used to instantiate various niching evolutionary algorithms.The experiments verify the validity and superiority of the proposed framework.(2)For discrete multi-solution optimization,in view of that the current studies lack of efficient algorithm design and comprehensive test framework,we propose a niching memetic algorithm and a multi-solution traveling salesman problem test framework.In this paper,the classic NP-hard discrete optimization problem—traveling salesman problem is used as the research example of discrete multi-solution optimization problems.First,the paper proposes a niching memetic algorithm,which provides an idea of an optimization method design for multi-solution traveling salesman problem.The algorithm designs an adaptive neighborhood strategy,which can adjust the niching parameters adaptively according to the niches' state.The critical edge-aware method is designed to identify the promising edge set in the candidate solution set and maintain the critical edge in the evolutionary operator.The selective local search strategy is utilized to avoid inefficient fitness evaluations and improve search efficiency.The elite selection strategy is adopted to eliminate redundant and inferior solutions in the final output set and provide representative solutions for decision makers.The lack of uniform test framework makes it impossible to make fair performance comparison on different discrete multi-solution optimization methods,which hinders the research and improvement of algorithms.This paper designs test framework of multi-solution traveling salesman problems,including 25 test instances and 2 evaluation indicators,which provides a unified and comprehensive test platform for discrete multi-solution optimization research work.Experiments validate that the niching memetic algorithm is superior to the existing discrete multi-solution optimization algorithm in terms of the quality and diversity of the final solution set.This work provides a design paradigm of discrete multi-solution optimization algorithms.To test the performance of the algorithms,we innovatively design the performance test framework for the discrete multi-solution optimization methods.The proposed algorithm and framework expand the research boundary of multi-solution optimization and fill the gap of the field of discrete multi-solution optimization to some extent.Furthermore,the work lays the foundation for future research of discrete multi-solution optimization.(3)For practical applications,the paper applies a niching evolutionary computation to the multiple-itinerary planning problem,in order to verify the effectiveness of multi-solution optimization in real world.Based on the consideration of the practical requirements of users,this paper designs a mathematical model of multiple-itinerary planning by considering optimization goals,need of multi-day travel and requirement of multiple travel itineraries.To solve the model,the paper proposes a niching evolutionary computation to automatically complete the task of itinerary planning.Particularly,we design a solution encoding scheme for multi-tourism itineraries and tailor evolutionary operators that can promise visit constraint implicitly.Also,a greedy repair operation is adopted to repair infeasible solutions according to different optimization goals to meet time constraint.The algorithm performance is tested on the real city data set.The experiments prove that the proposed method can effectively obtain multiple qualified solution sets.The successful attempt of niching evolutionary computation to multiple-itinerary planning promotes the application of multi-solution optimization to more practical application scenarios.In this work,we explore new means of the application of multi-solution optimization research to the fields of intelligent scheduling and smart transportation.To sum up,this article focuses on the research of multi-solution optimization and dives into the algorithm design.First,we study the continuous multi-solution optimization algorithm.Specifically,we put forward an efficient data structure and strengthen the search ability of niches.Next,we look into discrete multi-solution optimization algorithm.To be specific,we propose an efficient optimization algorithm and a comprehensive performance test framework.That enables the development of multi-solution optimization to reach a new level.Finally,the studied method is verified on the application of itinerary planning to promote the real-world application of multi-solution optimization algorithms.