演化计算系统及其综合设计

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 1 Introduction
• 1.1 Motivations
• 1.2 Objectives
• 1.3 Main Contributions
• 1.4 Organization
• 2 Reviews of Theories and Models
• 2.1 Evolutionary Computation
• 2.1.1 An example
• 2.2 Review of Computational Models
• 2.3 Engineering Applications
• 2.4 The Theories
• 2.4.1 Schema
• 2.4.2 Markov models and dynamical systems
• 2.4.3 Statistical mechanics
• 2.4.4 Alternative prospective
• 3 The Optimization Problem
• 3.1 Definiticns and Relationship
• 3.2 Uniform Set of the Problems
• 3.3 Global Optimization
• 3.3.1 Local minimum in discrete domains
• 3.3.2 Local minimum in continuous domains
• 3.4 Optimization Problems
• 3.4.1 Classification
• 3.4.2 Solvability
• 3.5 Engineering Requirements
• 4 Search Strategies
• 4.1 Search and Individual-Oriented Paradigm
• 4.2 Stochastic Strategies
• 4.2.1Realization
• 4.2.1.1 Random variation
• 4.2.1.2 Random transit
• 4.2.1.3 Elitism
• 4.2.2 Taxonomy and performance
• 4.2.2.1 Taxonomy
• 4.2.2.2 Performance
• 4.3 Heuristic Strategy
• 4.4 NFL Perspective
• 5 Evolution Framework
• 5.1 Population Scheme
• 5.1.1 Characteristics
• 5.1.2 Information from population
• 5.1.2.1 Reference solution
• 5.1.2.2 Reference strategy
• 5.1.2.3 Benefits
• 5.2 Evolution and Learning Systems
• 5.2.1 Evolution
• 5.2.2 Learning
• 5.3 Simulated Evolution Systems
• 5.3.0.1 Taxonomy
• 5.4 Computational System for Synthesis
• 6 System Synthesis
• 6.1 Evolutionary Computational Systems
• 6.1.1 Definition and notation
• 6.1.2 Models for variation operators
• 6.1.2.1 Individual-Learning Type（?）i
• 6.1.2.2 Global-Learning Type（?）g
• 6.1.3 Operators for population control
• 6.1.4 Interactive control interfaces
• 6.2 System Synthesis
• 6.2.1 Definition and objectives
• 6.2.2 Optimality principle and synthesis patterns
• 6.2.2.1 Convergence condition Ⅰ and pattern Ⅰ
• 6.2.2.2 Convergence condition Ⅱ and pattern Ⅱ
• 6.2.2.3 Summary of patterns for optimality
• 6.2.3 Solution reliability principle and realization
• 6.3 Summary of Synthesis Procedure
• 6.3.1 Collecting the components
• 6.3.2 Synthesis of the system
• 6.3.3 Summary of the procedure
• 7 Case Studies for Synthesis of the ECS System
• 7.1 Pick Sequencing Optimization
• 7.1.1 Introduction
• 7.1.1.1 The rotary rack S/R system
• 7.1.1.2 Problem definition and model
• 7.1.2 Synthesis of the ECS system
• 7.1.2.1 Knowledge and effective technique
• 7.1.2.2 Synthesis
• 7.1.3 Experimental Results
• 7.1.3.1 Setup of the experiments
• 7.1.3.2 Computational results
• 7.1.4 Conclusion
• 7.2 Calibration of the Descriptive System Model
• 7.2.1 Introduction
• 7.2.1.1 Constitutive equations
• 7.2.1.2 Objective function for optimization
• 7.2.2 Synthesis of the ECS system
• 7.2.2.1 Design of the components
• 7.2.2.2 Synthesis of the system
• 7.2.3 Experimental Results
• 7.2.4 Conclusion
• 7.3 TargetShape Design Optimization
• 7.3.1 Introduction
• 7.3.2 Synthesis of the ECS system
• 7.3.2.1 Representation
• 7.3.2.2 Fitness function
• 7.3.2.3 Variation and strategy parameters
• 7.3.2.4 Interactive interface
• 7.3.3 Experimental Results
• 7.3.4 Conclusion
• 8 Conclusions
• 8.1 Main Contributious
• 8.2 Future Work
• References
• Acknowledgements
• 攻读学位期间发表的学术论文
• 学位论文评阅及答辩情况表