【作者】 王瑜；

【导师】 王建宇； 李斌；

【作者基本信息】 中国科学技术大学 ， 电路与系统， 2011， 博士

【摘要】 作为一类新兴的计算理论与方法,进化算法(EvolutionaryAlgorithm(EA))已在许多工程与科研应用领域展现出优越的性能。相比于传统优化算法,EA只需要极少的参数设定以及少量的问题先验知识便可以实施寻优;对于工程优化问题中所存在的多个约束条件,EA无需进行复杂的归一化处理。此外,EA在多峰优化问题和多变量相关联的优化问题上也展现出了明显的性能优势。近二十年来,EA的研究已经取得了许多重要进展,但是,当应用于一些复杂的工程应用问题时,此前的EA算法版本仍然存在许多问题有待研究解决。其中,以下三个方面的不足最为业内关注:(1)EA的普适性仍然有待提高;(2)EA的延展性不足,其性能随着优化问题规模的增大(变量个数增多)而迅速降低;(3)EA在工程优化问题上的应用并不广泛。针对前两方面的不足,本文通过引入多方法融合的思想,提出更具鲁棒性的EA算法框架,以提升EA的延展性和普适性。同时,本文将所提出的算法应用于解决多项工程应用问题,取得了较好的成果。在算法设计方面,本文主要围绕着多方法融合(multi-method ensemble)思想展开研究。所取得的成果可以分为三个方面:1.针对此前各种分布估计算法(EDA)版本延展性不强的问题,本文通过引入多方法融合思想,设计一种自适应混合采样操作,并提出一种面向大规模优化应用的EDA -基于自适应混合分布采样的EDA(MUEDA)。MUEDA相对于传统EDA与经典的大规模优化EA的性能优势通过30 -1500维的函数优化实验得到全面验证。2.针对此前各种粒子群优化算法(PSO)版本普适性较差的问题,本文设计了一种自适应学习的算法框架,将多个PSO新解生成策略并列执行,提出自适应学习PSO(SLPSO)。SLPSO可以根据不同优化问题的特性,甚至是同一优化问题在不同优化阶段对优化算法要求的不同,将较多的计算资源分配给当前表现最好的策略。在这样的情况下,SLPSO的普适性得到了显著地提高。这一自适应方法的效果得到了函数优化实验和电力系统负载调配优化(ELD)实验结果的有力支持。3.在之前的研究中,以多方法融合为指导思想的EA均采用并列执行的框架。此类算法的普适性基本由框架对优化反馈的学习能力所决定。因此,并列框架在病态优化问题、带欺骗性优化问题以及极度多峰优化问题上表现仍然无法令人满意。为了改变这一现状,本文提出了基于两层串列结构的多方法融合框架(TSEA)。该框架的主体思想是根据具体问题的特性,将优化过程自适应地划分为相对独立的两个阶段:全局收敛阶段和深度搜索阶段。该算法框架的有效性在对多个复杂优化问题实施求解的过程中得到了充分验证。以两阶段串列结构的多方法融合算法框架为基础,本文设计了可应用于一般单目标优化、大规模单目标优化、多目标优化以及动态多目标优化问题求解的一系列具体算法实例。这些算法的性能除了在各类复杂函数优化问题上得到验证外,还在实际工程优化应用问题上展现出显著超越此前优化算法的性能表现。这些应用问题包括:1.大规模优化问题(变量个数在102数量级以上):MUEDA和TSEA在该类问题上取得了较大的突破。这主要表现为:在常规的问题上,本文算法的效率取得了与变量个数增加呈近似线性关系的降低趋势;在较难的问题上,对比于多种新近提出的面向大规模优化算法,我们的算法无论在搜索效率和有效性方面都表现出较大的优势。在2008年和2010年IEEE计算智能大会(WCCI)所组织的大规模优化竞赛中,MUEDA和TSEA均取得综合排名第二的好成绩。2.大规模电力系统负载调配(ELD):ELD问题是电力系统中非常重要但仍难以有效解决的优化问题。此前算法的性能随着ELD问题规模的增大衰减很快。为了改解决这一问题,本文基于TSEA算法框架、利用EDA和差分进化(DE)算法设计了一个自适应大规模ELD优化算法。对比此前最好的ELD优化算法,ED-DE以较小的代价搜索到更好的负载调配方案。特别地,ED-DE在所有已知的经典ELD问题上均刷新了最优解的记录。此外,本文也将SLPSO算法应用于大规模ELD问题求解,也取得了很好的效果3.数字IIR滤波器设计:数字IIR滤波器在数字信号处理领域有重要的作用。进化算法是求解该问题的主要算法之一。此前基于进化算法的求解方案存在两方面不足:(1)求解问题的规模(滤波器的阶数)有限;(2)取得的滤波器设计方案一般是以浮点数表示。此前算法在实际应用时会遇到两方面困难:求解问题规模的增加对算法的延展性提出了更高的要求;定点数的使用会造成求解空间的退化以及搜索信息的缺失,从而提升了对算法鲁棒性的要求。本文基于串列多方法融合框架思想,设计了新的两阶段Memetic算法(MA)TSMA,在数字IIR滤波器设计优化上取得了很好的效果。在高阶定点数数字IIR滤波器设计问题上,此前最为有效的优化算法均已失效,而TSMA仍能够获得可靠的性能表现。此外,串列多方法融合框架思想还被用于新兴的动态多目标优化问题的求解,也取得了很好的性能表现。综合本文的研究成果,基于两层串列结构的多方法融合框架在增强算法效率、有效性、鲁棒性以及普适性等各方面都表现出强大的生命力,适用于大规模复杂优化问题的求解。更多还原

【Abstract】 As the performance rising, Evolutionary algorithm (EA) has become more andmore important in optimization domain. Compared with classical optimization meth-ods, EAs require less parameter settings and less pre-knowledge. For the engineeringapplications with many constrains, EAs can work without complicated uniformizationprocedure. Besides, EAshaveshownespeciallybetterperformanceonmulti-modalandlinked problems.Although EAs have achieved significant performance previously, several aspectsof EAs still need to be improved. Generally speaking, there are three demerits of EAsas follows: (1) their universality, which means the ability of solving diverse kinds prob-lems, is still relatively poor; (2) their scalability, which is mainly the capability of solv-ing high dimensional problems, needs to be improved; (3) their application in engineer-ing optimization problems is still limited. For the first two drawbacks, we design amore robust and effective EA framework by using multi-method ensemble idea. Fur-thermore, the proposed EAs are applied to solve real world engineering applicationsand scientific problems, and the performance mostly surpass those of the classical EAs.This dissertation focuses on designing more effective and efficient multi-methodensemble based EAs, and then applying them to difficult engineering and scientificoptimization problems. The important findings are as follows:1. InordertoimprovethescalabilityofEstimationofDistributionAlgorithm(EDA),we design a new self-adaptive mixed distribution based sampling operator andthen,proposeaself-adaptiveMixeddistributionbasedUni-variateEDA(MUEDA).The advantages of MUEDA compared with the classical EDAs and state-of-the-art EAs are verified on the function optimization experiment scaling from 30 to1500 dimension.2. In order to improve the universality of Particle Swarm Optimization (PSO), wepropose a self-adaptive learning framework to extract strengthes from differentPSO new offspring creation strategies, which results in a new PSO variant self-adaptive learning PSO (SLPSO). Generally, SLPSO can assign more computa-tionalbudgettosuitablestrategiesbasedonthefeedbackofpreviousoptimizationprocedure. In this case, the universality of SLPSO can be remarkably improvedcompared with the other PSOs. This viewpoint is confirmed by function opti- mization and economic load dispatch of power system experimental results.3. In the previous research, the parallel execution of multiple new offspring cre-ation strategies is the usual form of multi-method ensemble algorithms. In thiskind of algorithmic framework, the learning mechanism is crucial to extend theapplication area. Therefore, it is difficult to handle ill-conditional and deceiv-able problems. In order to solve this, we propose a new Two-Stage based serialmulti-method ensemble EA (TSEA) framework, whose main idea is to dividethe optimization procedure into two stages, global convergence and exhaustivesearch.Based on TSEA framework, we propose a series of algorithmic versions to han-dle general function optimization problems, large scale optimization problems, multi-objective optimization problems and dynamic multi-objective optimization problems.Besides the function optimization experiments, TSEA shows significant advantages onreal world engineering and scientific optimization applications:1. Large scale global optimization: (with more than 102 variables) MUEDA andTSEA provide much better performance than the current state-of-the-art largescaleglobaloptimizationalgorithms. Asthedifficultylevelarises,theadvantagesof our proposed algorithms in effectiveness and efficiency become more clear. InIEEE CEC2008and2010largescaleglobal optimization competitions, MUEDAand TSEA are among the best candidates.2. Large scale ELD optimization: As an important and difficult optimization taskin power system, ELD has attracted public attention from research community.However,theperformanceofpreviousalgorithmsisstilllimited. Inordertosolvethis, weapplySLPSOandaTSEAversion, ED-DE,tolargescaleELDproblems.ComparedwiththecurrentbestELDoptimizationalgorithms,ED-DEcanallbestsolution records within lower computational cost.3. Digital IIR filter design: In the previous research, many methods have been ap-plied to this optimization task. However, they have similar demerits: (1) theycan only be applied to low-quality filter design; (2) the filter is represented byfloating-point numbers. These two aspects require more effective design meth-ods. This dissertation adopts Two-Stage based multi-method ensemble memeticAlgorithm (TSMA) to solve this problem and achieve remarkable progresses. It is worth noting that TSMA shows especially reliable performance on the hardtasks, on which the other algorithms all fail.Besides, the TSEA based algorithm is applied to dynamic multi-objective optimizationdomain, which attracts little attention previously, and gain significant progresses. Insummary, TSEA framework shows promising performance in terms of effectiveness,efficiency, robustness and universality, and is especially suitable for hard optimizationtasks.更多还原