【作者】 闫杨；

【导师】 汪定伟；

【作者基本信息】 东北大学 ， 系统工程， 2010， 博士

【摘要】 现实世界中的许多复杂优化问题多为动态的,会随时间发生随机变化,例如,接连到达的工件需要被加入到原有的调度中,机器可能会发生随机故障或逐渐磨损,原材料的性能可能会随时间发生改变,生产过程中需要考虑生产限度的影响等等。由于动态优化问题(DOPs)在现实生产和生活中具有广泛的应用背景,因而,近些年来,对于动态环境中优化问题的求解已经引起了学者的广泛关注。求解此类问题最简单直接的方法是将每次环境变化都看作是一个新问题重新求解。然而变化后新问题的最优解与旧问题的最优解可能相差不多,如果每次微小的变化都需要对问题重新进行求解是非常不经济的。进化计算方法是一类模拟生物进化过程中自然选择机制和遗传信息传递规律的优化方法,在运行过程中不断累积并利用曾经获取的信息来增强其在问题求解中的能力,属于自适应、自学习的求解方法,并已经被广泛应用于求解工业和工程领域中的各种复杂优化问题。因而进化计算自然就成为解决各种动态优化和不确定优化问题的一种选择。然而经典进化计算方法随着迭代的进行,种群会逐渐收敛,失去了对环境变化的适应能力这是进化算法在动态环境中所面临的主要挑战。鉴于动态优化问题存在的普遍性以及其在实际工业生产、经济、以及信息科学领域中存在的重要性,本文遵循综述—算法研究—算法应用的思路,对于动态环境中的进化计算方法进行了系统研究,并针对适合于不同编码机制的动态优化问题进行了探讨,具体研究工作内容如下:(1)对动态环境、动态优化问题以及动态环境中进化计算方法的相关研究进行了详细综述。首先对动态环境的概念进行了介绍,详细阐述了动态优化问题的主要特征。然后对动态环境中的编码方式和主要研究问题进行了综述。最后,对几类求解动态环境的进化计算方法的起源发展进行了介绍。(2)对适合采用0-1编码的动态优化问题进行了研究,提出了一种基于多智能体的进化搜索算法(AES)。为智能体设计了竞争行为以及两种基于统计概率的学习模型,并将两种多样性策略(随机移民策略以及自适应对偶映射方法)引入AES。通过对一组动态测试函数、震荡动态背包问题以及一类利用不同映射机制生成的新型动态背包问题的仿真实验,验证了AES算法在求解采用0-1编码的动态优化问题时能够表现出较强的鲁棒性,适合于采用0-1编码的DOPs问题的求解。(3)顺序编码方式通常被用于描述组合优化领域中的动态优化问题。动态TSP问题和调度问题都属于可以采用顺序编码的动态组合优化问题。首先,本文利用基于不同对偶映射机制的方法生成了一组DTSP问题,提出了包含复合重组算子以及局域更新规则的AES算法,通过实验证明了这两种机制有助于引导算法更好的适应不断变化的环境,具有较快的收敛能力。接下来,针对交货期可变的动态调度问题,设计了基于并行技术的多种群DE-Memetic算法,通过仿真实验说明了算法的可行性,基于并行计算的方法能够更好地利用双核处理器的运行能力,进而有效减少算法的运行时间。通过这几类具有较强实际背景的动态组合优化问题的研究,能够对系统工程以及控制领域中的实际动态优化问题有一定指导意义。(4)实数编码适合于描述多维连续实数空间中的动态优化问题。能够采用实数编码的动态多峰优化问题在动态优化领域中受到了广泛的重视,本文对该问题进行了研究,由于自组织迁移算法(SOMA)的个体迁移过程中蕴含了空间穿越机制使得算法适合于求解多维问题。提出了多Leader机制,有助于算法在环境变化后更好的追踪多个峰值,同时提出模糊迁移策略来实现对Leader的更新。通过对一组移动峰函数的仿真实验说明了MSOMA算法的有效性。(5)印刷电路板缺陷检查问题的整个检验过程是一个持续不间断变化的过程,属于实时的动态系统。由于印刷电路板组件排布的搜索属于实数空间的动态多峰函数的优化问题,将用于求解动态多峰函数的多Leader自组织迁移算法用于印刷电路板视觉检查过程的优化,可以为PCB生产工业提供一种更有效的视觉检查方法,为问题的研究提供了一个新的思路。更多还原

【Abstract】 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.更多还原