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

《演化计算系统及其综合设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学博士学位论文摘要采用优化来描述各种问题尽管不是最佳的表述方式，但是它是一个相对简单和通用的手段一一至少从原则来讲各种问题可以被表示为优化问题。本文采用优化来表征一个带求解的问题，进而以它为对象，对问题求解系统进行设计和分析。针对采用搜索机制进行对问题的求解的直接优化方法，前人曾做过大量的理论研究和实际应用。这些研究最终产生了演化计算这一领域。它通过模仿自然界或社会系统中的各式各样的自适应和学习机制来引导搜索过程的进行，从而实现优化这一目标。早期的演化计算理论不论是模式理论、马尔科夫模型和动态系统模型还是统计力学模型，

2、它们都着力于模仿给定的计算模型的动态行为。但是这些理论在最终应用时，都面临着无法承受的计算负担。我们把其原因归结为这些理论过于一般化脱离了了待求问题的特点和实际求解要求。由于演化算法的核心机制是随机和启发式方法，因此单纯的模仿算法运行很难拿到针对特定问题求解时的准确或者说必然的结论。另一方面，在当前演化计算领域的研究中，人们都集中于直接模仿在然界和社会中存在的各类演化和学习机制，依赖于所模仿的机制的上下文，将各种仿真演化的模型设计成为特定名称的演化算法。随着这些求解模型的不断提出，名词术语上的多样性导致了研究和工程应用的障碍

3、。很明显，现象的多样性不一定就说明内在自适应机制的多样性，相反一些新命名的仿真演化模型在本质上有相通和相似的机制。以上谈及的这两个趋势突出说明了建立一个通用的演化系统环境的必要性。这个通用的演化系统要能够应用各种演化机制来设计求解技术，进而能综合这些求解技术到某个整合的演化系统环境山东大学博士学位论文中定制特定系统来对特定的问题求解。其核心思想在于忽略单纯的模仿某种演化机制，而是根据待求问题的特点综合利用各类自适应机制和有效的搜索技术来设计问题求解的系统。在研究提出综合系统之前，我们首先总结并讨论了各类演化搜索算法的核心策略

4、包括随机策略和启发式策略，以及根本指导原则包括最优性原理和评估等价性原理；进而总结并抽取出各类演化仿真系统中的本质运行机制。针对随机策略我们导论了其特点和特性，并且给出了全局搜索和局部搜索的实现机制；针对启发式策略我们阐述了其内涵和归纳了其种类和各类实现方式。我们给出了最优性原理中的基本收敛模式。我们依据文献【89，9l】的讨论框架给出了评估等价性原理，通过此原理重新阐述了各类NFL定理的结论。这些理论结论为系统综合的原理和方法奠定了基本的依据。对前人工作的总结，特别是在各类演化算法中总结出根本原则和计算模型是接下来提出演化

5、计算系统和提出相关理论和方法的基础。在理论研究和工程应用过程中人们提出了大量的演化计算模型，因此我们不是采用枚举当前演化计算领域各类模型，而是总结并抽取其三类本质的种群演化搜索模式。它们分别是基于遗传信息的演化、个体行为演化和社会行为演化。前者本质是编码空间搜索模式，另外两个分别是个体局部搜索学习和种群分布函数演化。在传统的演化计算领域里，这三类演化和学习机制被用于独立的创立各式计算模型，但是在我们将提出的综合演化环境中，他们将被利用于设计演化搜索算子，并集成在综合系统中进行合作协调搜索。接下来，我们提出了‘演化计算系统’的

6、概念。作为系统综合环境的演化计算系统将被定制为各种实现用于具体问题的求解。变化算子集、控制算子集和能够独立维护搜索信息的演化个体是演化计算系统的根本组元。该系统之所以称为‘演化’是由于它使用演化和学习机制作为其搜索算子构建的核心机制；而要说明的是尽管称其为‘计算系统’，但是它不同于传统意义下的算法，它使能够与外部计算系统甚至专家直接交换信息，实现交互式计算。山东大学博士学位论文所谓的‘综合’是指系统设计依赖于求解问题的特点和求解要求，同时抛开各类描述演化机制的名词术语界限强调综合应用和协调各类求解技术，定制针对问题特点的特定

7、求解系统。为了实现这一目标，需要建立两个根本桥梁：其一，待求问题的特点和演化搜索算子的设计的关系；其二，求解要求和组织搜索算子和演化个体的控制算子之间的关系。紧紧围绕着这两个纽带，我们提出了演化计算系统综合设计的理论。首要的工作是算子设计的理论和模型。对于变化算子，我们详细讨论了其功能性和基本构建机制。依赖使用演化个体的个数，变化算子被分为个体学习型和全局学习型；依赖其搜索的功能性，它可被分为挖掘型和探索型。构建演化搜索算子的核心机制有随机搜索，启发式搜索和问题数学结构相关的传统搜索机制。控制算子包括了变化算子选择控制，个体

8、选择控制，种群维护和交互接口控制几大类。我们分别给出了设计机制和性能。需要特殊说明的是，演化个体独立维护变化信息的机制是多个演化搜索算子共同协作的前提。综合设计理论的核心工作是系统综合的理论和模型。系统综合的基本实现手段是通过组织和协调参与演化搜索的各个变化算子和各类控制组元。在这一部分里