【作者】 张攀；

【导师】 贾磊；

【作者基本信息】 山东大学 ， 控制理论与控制工程， 2008， 博士

【摘要】 采用优化来描述各种问题尽管不是最佳的表述方式,但是它是一个相对简单和通用的手段——至少从原则来讲各种问题可以被表示为优化问题。本文采用优化来表征一个带求解的问题,进而以它为对象,对问题求解系统进行设计和分析。针对采用搜索机制进行对问题的求解的直接优化方法,前人曾做过大量的理论研究和实际应用。这些研究最终产生了演化计算这一领域。它通过模仿自然界或社会系统中的各式各样的自适应和学习机制来引导搜索过程的进行,从而实现优化这一目标。早期的演化计算理论不论是模式理论、马尔科夫模型和动态系统模型还是统计力学模型,它们都着力于模仿给定的计算模型的动态行为。但是这些理论在最终应用时,都面临着无法承受的计算负担。我们把其原因归结为这些理论过于一般化脱离了了待求问题的特点和实际求解要求。由于演化算法的核心机制是随机和启发式方法,因此单纯的模仿算法运行很难拿到针对特定问题求解时的准确或者说必然的结论。另一方面,在当前演化计算领域的研究中,人们都集中于直接模仿在然界和社会中存在的各类演化和学习机制,依赖于所模仿的机制的上下文,将各种仿真演化的模型设计成为特定名称的演化算法。随着这些求解模型的不断提出,名词术语上的多样性导致了研究和工程应用的障碍。很明显,现象的多样性不一定就说明内在自适应机制的多样性,相反一些新命名的仿真演化模型在本质上有相通和相似的机制。以上谈及的这两个趋势突出说明了建立一个通用的演化系统环境的必要性。这个通用的演化系统要能够应用各种演化机制来设计求解技术,进而能综合这些求解技术到某个整合的演化系统环境中定制特定系统来对特定的问题求解。其核心思想在于忽略单纯的模仿某种演化机制,而是根据待求问题的特点综合利用各类自适应机制和有效的搜索技术来设计问题求解的系统。在研究提出综合系统之前,我们首先总结并讨论了各类演化搜索算法的核心策略包括随机策略和启发式策略,以及根本指导原则包括最优性原理和评估等价性原理;进而总结并抽取出各类演化仿真系统中的本质运行机制。针对随机策略我们导论了其特点和特性,并且给出了全局搜索和局部搜索的实现机制;针对启发式策略我们阐述了其内涵和归纳了其种类和各类实现方式。我们给出了最优性原理中的基本收敛模式。我们依据文献[89,91]的讨论框架给出了评估等价性原理,通过此原理重新阐述了各类NFL定理的结论。这些理论结论为系统综合的原理和方法奠定了基本的依据。对前人工作的总结,特别是在各类演化算法中总结出根本原则和计算模型是接下来提出演化计算系统和提出相关理论和方法的基础。在理论研究和工程应用过程中人们提出了大量的演化计算模型,因此我们不是采用枚举当前演化计算领域各类模型,而是总结并抽取其三类本质的种群演化搜索模式。它们分别是基于遗传信息的演化、个体行为演化和社会行为演化。前者本质是编码空间搜索模式,另外两个分别是个体局部搜索学习和种群分布函数演化。在传统的演化计算领域里,这三类演化和学习机制被用于独立的创立各式计算模型,但是在我们将提出的综合演化环境中,他们将被利用于设计演化搜索算子,并集成在综合系统中进行合作协调搜索。接下来,我们提出了‘演化计算系统’的概念。作为系统综合环境的演化计算系统将被定制为各种实现用于具体问题的求解。变化算子集、控制算子集和能够独立维护搜索信息的演化个体是演化计算系统的根本组元。该系统之所以称为‘演化’是由于它使用演化和学习机制作为其搜索算子构建的核心机制;而要说明的是尽管称其为‘计算系统’,但是它不同于传统意义下的算法,它使能够与外部计算系统甚至专家直接交换信息,实现交互式计算。所谓的‘综合’是指系统设计依赖于求解问题的特点和求解要求,同时抛开各类描述演化机制的名词术语界限强调综合应用和协调各类求解技术,定制针对问题特点的特定求解系统。为了实现这一目标,需要建立两个根本桥梁:其一,待求问题的特点和演化搜索算子的设计的关系;其二,求解要求和组织搜索算子和演化个体的控制算子之间的关系。紧紧围绕着这两个纽带,我们提出了演化计算系统综合设计的理论。首要的工作是算子设计的理论和模型。对于变化算子,我们详细讨论了其功能性和基本构建机制。依赖使用演化个体的个数,变化算子被分为个体学习型和全局学习型;依赖其搜索的功能性,它可被分为挖掘型和探索型。构建演化搜索算子的核心机制有随机搜索,启发式搜索和问题数学结构相关的传统搜索机制。控制算子包括了变化算子选择控制,个体选择控制,种群维护和交互接口控制几大类。我们分别给出了设计机制和性能。需要特殊说明的是,演化个体独立维护变化信息的机制是多个演化搜索算子共同协作的前提。综合设计理论的核心工作是系统综合的理论和模型。系统综合的基本实现手段是通过组织和协调参与演化搜索的各个变化算子和各类控制组元。在这一部分里,我们首先给出了有关综合目标和求解条件。接下来围绕着建立这两个基本桥梁,我们分别探讨了最优性原则和综合设计模式,以及可靠性原则和实现综合系统。针对最优性原则,我们给出了两个收敛定理,并且依据这两个收敛定理提供的条件提出了两套综合模式,即综合模式Ⅰ和Ⅱ。综合模式Ⅰ本质应用穷举的策略以达到求取最优解,它的运行的低效性使得其常应用于修正一个不收敛的演化计算系统为收敛的系统。比较来讲,综合模式Ⅱ则给出了一个有效的综合方案,通过协调配和使用挖掘型演化搜索算子和探索型演化搜索算子,系统可以在保证最优性的前提下实现高效的搜索求解。求解可靠性原则更关心在给定的求解时间内求取到满意解。求解过程虽然是质量与时间的一个平衡过程,但是我们可以抽取其两个极值的情形作为综合的标准,即求解速度可靠性和求解质量的可靠性。针对系统综合,我们提供了四类总体实现方案,同时针对每种方案我们给出了相应的设计指导原则和一般性能的讨论。为了举例说明我们给出的演化计算系统和综合理论的各方面设计原理和步骤,我们给出了三个挑战性的工程优化问题。它们分别是立体旋转货架的拣选作业调度优化问题,本构方程系统的参数标定问题,以及目标形状设计优化问题。其中第一个问题属于控制优化问题类,后两个问题属于设计优化问题类。针对问题一,我们突出说明了如何依赖具体问题的信息设计高效的挖掘型演化搜索算子,以及如何使用探索型搜索算子协调搜索行为。基于综合模式Ⅱ,最优性和可靠性标准在系统综合设计中得到实现;在比较实验中得到了经验验证。针对问题二,我们强调了多个演化搜索算子共同协调进行演化搜索的工作模式。系统综合模式Ⅱ作为基本执行框架得到了实现。同时,针对挖掘型算子的特点,我们配合设计了一种探索性搜索算子。实验环节以一套29个参数的系统进行标定,我们依据问题定制的演化计算系统给出了求解该问题目前最好的结论。针对问题三,我们补充说明了除主要系统综合理论之外的附属型组元的设计和有关考虑。其中突出说明了利用交互式接口,让专家担当智能变化算子,直接参与演化搜索。同时有关解空间表达问题、评估函数的设计问题、和策略参数的初始化等问题也给出了例证。最后,我们总结了本文实现的主要工作和贡献,并给出下一步工作的两个关键研究内容。更多还原

【Abstract】 Optimization may not be the best language for expressing a problem, but it is relatively simple and quite general - all problem can, at least in principle, be expressed as optimization problems. Herein optimization terminology is employed to describe a problem to be solved and furthermore used to design and analyze the problem-solving system.In history, a series of fundamental work has been done for direct optimization by means of the trail-and-error mode and the fruitful outcome was the emergence of the field of evolutionary computation, which utilize various adaptive and learning mechanisms inspired from nature or social systems.In earlier, theories on evolutionary computation were interested in simulating the dynamical behavior for a fixed computational model to explain the behavior after implemented. All the theories face the unsolvable computing bounden for real application. It can be learned that the reason is partly because that they all ignored the characteristics of the problem to be solved and the practical requirements of the solution performance. As a result, these theories are all too general to be used in real analysis and algorithmic design.Currently, many concerns has been put into introducing various evolution and learning mechanisms from natural world or social systems to invent various evolutionary algorithms with the plenty of names. With the growth of the applicable solution techniques, the terminology barrier has also been formed with the complicated names and terminologies. Obviously the diversity of the phenomena do not definitely represent the diversity of the adaptive mechanisms, instead many mechanisms of these newly termed algorithms overlaps in essence. Both of the addressed trends essentially appeal the formulation of an uniform framework 1) to design or develop new solution techniques that are learned from nature or society, and 2) to synthesize the involved solution techniques into a comprehensive environment for realization of a specific problem solving system for the particular problem under the required solution reliability. The philosophy on the uniform framework is to DIY the evolvable system for solving the specific problem, instead of negatively simulating a single adaptive mechanism. With synthesis of a evolutionary system in the specific application context, the resultant system is expected to behave as we designed.Before the proposal of the comprehensive evolution environment, the essential strategies including the stochastic strategy and heuristic strategy, principles including the optimality and the equivalence in evaluation and computational models for producing simulated evolutionary search are summarized and subtracted. The corresponding theoretical results are also studied. Firstly, the stochastic strategy is indispensable in building the variation and transit mechanisms for an evolutionary search scheme, due to its versatility, simplicity, robustness and flexibility. Realization for global scope search and localized search are exemplified and a range of optimality results are discussed. Furthermore the other essential mechanism of the heuristic strategy is addressed from the aspect of the implications and the exemplified implementation. Secondly, the fundamental principle of NFL theorem for design of the problem solving system has been emphasized. We follow the framework in [89, 91] and generalize it to the theorem of equivalence in evaluation. These theoretical results support the philosophy and methodology on system synthesis.Summary of the previous work, especially on essential principles and various models of evolutionary computation is critical for proposal of the evolutionary computational system and development of the theories and methodologies to realize a synthesized system in specific solution context. Since numerous simulated evolution models have been developed in line of the theoretical research and engineering application, thus instead of enumerating the variety of simulated evolution models in current EC field, we subtract three essential population based search schemes by investigating the core mechanisms of various models. These three schemes are named as genetic information based evolution, individual behavioral evolution, and the social behavioral evolution. Along with the emphasizing the merits from population based search, the three schemes prominently exemplify three basic population search patterns: encoded solution space variation, individual learning, and the multiple sampling learning. In traditional EC field, the three types of evolution and learning mechanisms have been independently utilized to form the simulated evolution models respectively. However, in the proposed comprehensive evolution environment, these schemes will be employed to devise a variety of ready-to-use variation operators, which are used as components to synthesize the problem solving system.Then, we put forward the evolutionary computational system (ECS) as the comprehensive environment to devise the various solution models, where variation operators, control operators, self-maintained hyper-individuals are essential elements. Two fundamental characteristics distinguish the ECS from others including 1) this comprehensive environment is capable to employ both the evolution or learning mechanisms and the traditional effective techniques simultaneously to design the operators and devise the coordination rules; 2) this environment is beyond the traditional meanings of computation, which is allowed to open the interactive interfaces to interact with outer computing systems or even human being as variation operators or control operators. Although it is referred to as the computational system, it is not the computer algorithm in traditional sense.The so-called synthesis focus on the solution context including the problem characteristics and solution requirements. It leaves the original terminology aside and emphasizes the comprehensive application and coordination of various solution techniques within the ECS framework. To perform the synthesis in practical meaning, the core work concentrates on building two bridges across 1) the problem characteristics with the design of operators and 2) the solution requirements with the organization of operators.With considerations of the two connections, we propose the synthesis theories for the ECS system. The first contribution is the theory and models on the operator design. Variation operators are divided into individual learning type and global learning type according to the number of operands (hyper-individuals); the functionality is devised into localized intensive search and global information involved search; and the realization mechanisms are based on random featured operators, heuristic featured operators and mathematical structure based operators. The related realization diagrams are exemplified and discussed in depth. Moveover, the control operators including the individual selection control, variation operator control, population maintenance control and interactive interfaces are studied. The design rules and mechanisms are presented and the related functionalities are discussed.The second is the theory and patterns on system synthesis, that is the organization of the involving operators and other components. Firstly, the synthesis objective and solution conditions are specified in details. Establishment of the bridge between solution requirements on optimality, and the bridge between reliability of speed and quality are studied respectively.The optimality principles are proposed with the presentation of convergence condition I and II, and correspondingly the synthesis patterns are formulated with respect to the two convergence conditions. The synthesis pattern I provides a foundation to modify a nonconver-gent evolutionary search process to a convergent one. In comparison, the synthesis pattern II outlines an effective synthesis scheme for organization of both exploitive variation operators and explorative operators to perform the search in collaboration. The synthesis pattern II is naturally employed as the default pattern to organize the variation and control operators only if some effective exploitation variation operator can be devised.The solution reliability concerns achieving the satisfying quality solutions within the allowed solution time slot. This is a balance of quality and time in practice, while separately they can be two criteria in the course of system synthesis process. Four types of combinatorial realization schemes are discussed; the performances are studied respectively; and the application principles are also provided.We illustrate the range of principles and methodologies with three engineering optimization problems which are all derived from our finished projects. The first application is a scheduling problem (a typical combinatorial optimization problem) for picking sequencing scheduling for an automated stereotype warehousing system. The second application is a target shape design optimization problem. The third application is parameter decision for materials modeling.To demonstrate the utilization of the theories and models of synthesizing the evolutionary computational system for solving the specific problem under the specific solution requirements. Three real engineering problems are selected including the order-pickup sequencing problem in the multi-carousal warehousing system, the calibration problem for the mechanism-based unified viscoplastic damage constitutive equations and the target shape design optimization problem.The case of the order-pickup sequencing problem belongs to the class of online problems, which requires the high speed solution and without the strict optimality but expected the best. In this case, we emphasize the employment of heuristic information on the characteristics of the problem to build the expletive variation operators and based on the synthesis pattern II to organize the control operators.For the last two problems, they are the cases of the off-line problems. In the study of the calibration of the descriptive system consisting of a set of mechanism-based unified viscoplastic damage constitutive equations, we mainly study the collaboration of multiple variation operators in the synthesized ECS system. At first we devise an effective exploitive variation operator and then to coordinate the exploitive search operator, we propose a new global learning variation operator, which has three adjustable items. To emphasize the explorative performance, we realize this variation operator in the explorative form, which satisfies the global reachable condition. Based on the synthesis pattern II, we devised the evolutionary computational system under the requirements of both solution optimality and solution reliability. The convergent result was proved and the reliability performance was demonstrated by the experimental comparisons. In comparison, in the study of the target shape design optimization problem, we ma-jorally demonstrate some secondary aspects on synthesizing an evolutionary computational system, addition to the forgoing two cases. We emphasize the influences of different evaluation mechanisms on the search process, a variable representation scheme on strategy parameter updating and introduction of the direct human expert as a non-computing variation operator. The influence of these secondary concerns are studied by a series of experiments and the general principles in practice are presented.更多还原