Research And Application Of A Memetic Algorithm For Dynamic Optimization Problems

Dynamic optimization problems have been gained a lot of attentions from evolutionary computation community in recent years because many real-world problems are usually time-varying. For example, new jobs are arriving continuously and have to be added to the schedule, machines may break down or wear out slowly, raw material is of changing quality, production tolerances have to be taken into account, and so on.In this paper, a new evolutionary algorithm, called memetic algorithm (MA), is investigated for DOPs. MA usually hybridizes both population-based global exploration and individual-based local exploitation together within the same algorithm framework, which causes that it becomes a very good way for solving many optimization problems. However, it is a major problem that the population will gradually converge when a MA is used to solve DOPs considering that the converging population cannot adapt well to a changing environment. In order to address this problem, a primal-dual immigrant strategy, where a number of immigrants are generated using a primal-dual operation and then injected into the population every generation, is proposed in this paper. In addition, an adaptive local search (LS) method, which employees multiple different LS methods in an adaptive cooperation fashion, is also introduced to make MA execute a more efficient local refinement.This paper gives a comprehensive study about the Memetic algorithm in dynamic environments concluding the survey, algorithm, and application of it. And the main work presented in this paper focuses on three aspects as follows:(1) This dissertation surveys the related research on genetic algorithm, memetic algorithms and the approaches in dynamic environments.(2) A memetic algorithm for dynamic optimization problem is proposed in this thies, including local search and the strategy to maintain population diversity.(3) We build a dynamic TSP problem to test the performance of the algorithm.(4) We construct a dynamic single machine scheduling problem, and then test the algorithm presented in this paper to prove its feasibility.