Research On Evolutionary Algorithms With Different Encoding Schemes For Various Dynamic Optimization Problems With Applications

Many optimization problems in real-world are dynamic. They may stochastically change over time. 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, etc.Problem optimization in dynamic environments has attracted a growing interest from the evolutionary computation community in recent years due to its importance in real world optimization problems. A standard approach to deal with these uncertainty and dynamics in optimization problems is to regard each change as the arrival of a new optimization problem instance that has to be solved from scratch. However, it is not economically sensible to adapt the solution after every small change because the solution of the new problem might not differ too much from the solution of the old problem.Evolutionary algorithms (EAs) are a class of optimization techniques which make use of principles of natural selection and population genetics. EAs are adaptive and self-learning algorithms in the sense that they accumulate and use information to progressively improve their ability to solve some problem of interest. Therefore, EAs seem to be particularly suitable for dynamic and stochastic optimization problems since the principles of nature evolution is a stochastic and dynamic process as well.Nevertheless EAs eventually converge to an optimum and thereby loose their diversity necessary for efficiently and adaptively exploring the search space. Due to the universality of DOPs and their importance in practical industry, economics and information science research fields, in this paper a comprehensive research of EAs with different encoding methods in dynamic environments is carried out following the process from survey to the algorithm study, to algorithm application research. Research contents in details are shown as followings:(1) This dissertation surveys the related researches on dynamic environment, dynamic optimization problems and EAs in dynamic environment. Firstly we describe the idea of dynamic environment and emphasize the main features of dynamic optimization problems (DOPs). Then the encoding method and the main research problems in dynamic environments are surveyed. At last, the origin and development of a series of evolutionary algorithms in dynamic environment are presented.(2) An Agent based Evolutionary Search algorithm (AES) is proposed in this dissertation for dynamic optimization problems in which 0-1 coded are adopted. A competitive behavior and two statistics based learning behavior is introduced. For the purpose of maintaining the diversity of the population, random immigrants and adaptive primal dual mapping schemes are incorporated. The experimental study over a series of dynamic testing fuctions, a shifting dynamic knapsack problem and a dynamic knapsack problem generated by mapping based DOPs generator, AES is proved to be robust and adaptive in solving 0-1 coded DOPs.(3) Sequence coding method is often applied to describe the DOPs in combinatorial optimization. Dynamic TSP (DTSP) problem and dynamic scheduling problems belogs to the sequence coded DOPs research field. The Mapping based DOP generator is used to generate a series of DTSP problems, and an AES algorithm is presented to solve the DTSP problems. At the same time, a Recombination Operator and a Local Updating Rule are introduced into AES. Experimental results demonstrate that the proposed AES method can adapt to new environment and converge fast the dynamic environment.In recent year, Differential Evolutionary (DE) Algorithm and Memetic Algorithm (MA) have caught extensive attention. A DE based MA is put forward to address the sequence coding DOPs in this dissertation. In order to solve the dynamic scheduling problem with variable due dates, a parallel multi-population DE-Memetic algorithm is presented. According to the simulation, the proposed parallel DE-Memetic algorithm is proved to be feasible and time-consuming due to the fact that the processing ability of dual-core processor is better utilized. According to the experimental study on the dynamic scheduling problems which are practical, the proposed algorithm has an important guide significance for real world DOPs in systems engineering and control theory.(4) Real-coded encoding method utilized to describe multidimension real number space. Real-coded multimodal optimization problems in non-stationary environments have been paid much attention. In this dissertation the real coded motimodal dynamic optimization problems has been studied. Due to the ability to pass through the search space embedded in SOMA, SOMA is used to solve the dynamic motimodal optimization problems. A multi Leader scheme is designed to track multiple optima in non-stationary environments. In order to adapt to the dynamic environment, a fuzzy migration scheme is introduced to accomplish the updating process of the Leader. Experimental studies on the Moving peaks function demonstrate that the proposed algorithm is effective in solving the real-coded dynamic multimodal problems.(5) The entire defect detection process in printed circuit board industry which is the major research problem in quality control procedure is a continuously changing process. The multiple components with multi-direction location problem are transformed to a multimodal function optimization problem. In fact, the PCB inspection problem is a real-coded dynamic multimodal optimization problem, and the multi-leader SOMA is applied to optimize the PCB inspection process. Therefore it improves the inspection efficiency of PCB industry and provides a new idea for the inspection problem.