基于拟仿射变换的协同进化算法研究
发布时间：2020-09-28 15:50
随着社会的发展,优化的需求越来越多地出现在各行各业之中,由此,解决这些需求的优化算法发挥着越来越重要的作用。一般而言,优化问题的求解以设计对应模型的目标函数开始。对于此目标函数,如果其具体公式已知且是可微分的或者是二阶可微分的,则可分别通过类牛顿的方法或者牛顿的方法来求解;如果其具体公式已知却不可微分或者目标函数是黑盒函数时,牛顿类的方法失效,此时进化计算的优化算法给出了这类问题的求解。本文从进化计算领域的优化算法入手,深入分析了该领域内两种著名的分支——粒子集群优化算法和差分进化算法的研究现状及仍然存在的问题,提出了拟仿射变换的协同进化架构来克服上述两分支在进化方式中的缺陷,并对拟仿射变换的协同进化架构的提出过程及该架构下算法可能的发展方向进行了深入探讨和研究。另外,本文以外部存储的参数适应拟仿射变换协同进化算法为主体,还开发出了一个参数独立的黑盒优化工具,用以解决各类单目标实参的非线性非凸的目标函数优化问题。本文的主要研究内容及成果有以下几点:本文提出了一种解决低维度单目标实参优化的潮汐鱼算法,并在其基础上提出了解决较高维度复杂优化的模因孙悟空进化算法。潮汐鱼算法是为了解决粒子集群优化算法在低维度优化中收敛速度过慢的问题而提出的,而孙悟空算法进一步强化了潮汐鱼算法的优化能力。孙悟空算法有三个版本,第一版的孙悟空算法通过引入尺度因子增强了潮汐鱼算法的全局优化能力,但其在较高维度优化中的表现仍然较差。第二版的孙悟空算法通过引入差分向量的方式增强了第一版孙悟空算法的局部搜索能力,实现了较高维度优化问题的较好求解。但前述算法中的个体都存在两种搜索方式,这使得个体间的协同能力较差。故最终版的孙悟空算法通过把种群中所有个体都强化为最强个体的方式,实现了种群个体间的均等,同时通过引入一个协同进化矩阵,实现了种群个体间的协同搜索,并在高维度复杂优化中取得了很好的优化效果。实验结果表明,潮汐鱼算法和最终版的模因孙悟空进化算法克服了粒子集群优化算法中“走两步、退一步”缺陷所导致的在解决低维度简单优化和较高维度复杂优化中收敛过慢的问题,取得了更好的优化效果。本文提出了一种先进的参数适应学习机制的差分进化算法,该算法通过把不同控制参数分组并进行适应性学习的方式,消弭了几种先进的差分进化算法中参数之间的误导性影响;同时该算法通过在外部存储的变异策略中引入时间戳机制克服了外部存储变异策略中次等解常驻外存的缺陷,加强了变异策略中外部存储的次等解的多样性,取得了更好的优化效果。实验表明,参数适应学习机制的差分进化算法实现了在单目标的实参的高维度复杂优化问题中的又好又快收敛,其整体优化效果好于近年来在相关优化竞赛中夺魁的差分进化算法的先进变体。本文提出了一种拟仿射变换的协同进化架构——QUATRE架构及基于此架构的QUATRE算法。从个体进化的实现方式看,QUATRE算法是模因孙悟空进化算法的拓展升级,也克服了粒子集群优化算法中“走两步、退一步”缺陷所导致的收敛过慢的问题;从进化中个体的移动方式看,QUATRE算法还属于一种更少参数的差分进化算法,并克服了差分进化算法中存在的高维视角下的代表性偏见,实现了统计学及概率论角度的更合理的搜索。在该算法基础上,本文还提出了一种基于外部存储的参数适应拟仿射变换协同进化算法,该算法吸收了前文提出的参数适应学习机制的差分进化算法中控制参数的适应性学习机制和变异策略的时间戳机制,同时该算法还引入了一个协同进化矩阵的适应调整机制来更好地感知目标函数的结构,从而实现了更科学的个体移动及空间搜索。实验表明,外部存储的参数适应拟仿射变换协同进化算法在领域内的通用评测函数下取得了比其它对比算法都要好的整体优化效果。综上,本文在粒子集群优化算法的基础上提出了模因孙悟空进化算法;在几种先进的差分进化算法基础上提出了参数适应学习机制的差分进化算法;然后在上述两种算法基础之上提出了外部存储的参数适应拟仿射变换协同进化算法,由于该算法中所有参数均无需人为调节,故其为一种参数独立的优化算法。以该算法为主体的黑盒优化工具在实验中表现出了强大的处理高维度复杂优化的能力,且其优化效果均显著优于其它先进的优化算法。
【学位单位】：哈尔滨工业大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：TP18
【部分图文】：
表示 维解空间。图1-2描述了二维空间中某一连续可微分的评价函数的最小值所处位置示例。那么，对于这样一个评价函数，如何寻找其最优值呢？图1-2二维评价函数的最小值优化示例Fig. 1-2 An example of the minimum optimization of a 2-D benchmark function根据拉格朗日中值定理，如果 :R →R是连续可微分的，并且 0∈R ，则有： ( ) = ( 0) + ( 0) · ( 0+ · ( 0)), ∈ (0, 1) (1-2)假定 0是评价函数 ( )的全局最优解，那么优化算法，尤其是线性搜索策略的算法最终要实现从当前位置 到目标位置 0的移动。如果用 表示 与 0的差，则公式1-2可以改写为： ( 0+ ) = ( 0) + · ( 0+ · ), ∈ (0, 1) (1-3)一般而言，优化问题的最优解的位置是未知的，当前位置是已知的，故而，通过 5
牛顿法等优化方法，拟牛顿的方法往往是更好的选择。然而，现实世界的优化问题，存在更多更为复杂的情况，如优化问题或优化系统的评价函数不可导，亦或评价函数存在噪声，更或者评价函数未知等。图1-3给出了一个存在噪声的黑盒优化示例，其中函数 ( )是解空间中解的理想分布函数，函数 ( )是实际抽样得到的评价函数的折线。显然，对于这样的一个（可能存在噪声的）黑盒优化模型，上述所有基于导数的确定性优化算法均无法实现问题的求解，或然性的优化算法，开始显示出它的不可替代性。图1-3黑盒目标函数优化示例Fig. 1-3 An example of optimization under black-box objective function1.2.2 或然性优化算法在进化计算的或然性优化算法用以解决连续空间的黑盒优化问题中，粒子集群优化（Particle Swarm Optimization）算法和差分进化（Differential Evolution）算法是两种最为著名的算法。每届的进化计算领域的旗舰会议IEEE计算智能大会（IEEE World Congress on Computational Intelligence）都会对这两种算法的最新研究进展及研究趋势做详细讨论。IEEE计算智能大会一般由三个子会议构成，分别为：IEEE神经网络联席大会（IEEE Joint Conference on Neural Networks）
1995年提出的一种群聚智能算法，该算法通过模拟鸟类觅食飞行实现复杂优化问题的求解。图1-4给出了一张自然界中候鸟觅食飞行的图片，从中可以看出，种群中领队的候鸟会带领整个种群飞行。 受此启发，在粒子集群优化算法中，种群全局最优解和每个图1-4自然界中鸟的觅食飞行Fig. 1-4 Flying behavior of birds foraging for food in nature粒子的历史最优解如同图1-4中的领队候鸟一样，共同影响着当前粒子的下一步移动方向及移动距离。另外，粒子自身的位置信息和飞行速度信息也影响着其自身下一步的移动方向及移动距离。公式1-15给出了粒子集群优化算法中粒子迭代的具体情况，其中 , 表示第 个粒子在第 代的速度信息， , 表示第 个粒子在第 代的位置信息，
本文编号：2828968
【学位单位】：哈尔滨工业大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：TP18
【部分图文】：
表示 维解空间。图1-2描述了二维空间中某一连续可微分的评价函数的最小值所处位置示例。那么，对于这样一个评价函数，如何寻找其最优值呢？图1-2二维评价函数的最小值优化示例Fig. 1-2 An example of the minimum optimization of a 2-D benchmark function根据拉格朗日中值定理，如果 :R →R是连续可微分的，并且 0∈R ，则有： ( ) = ( 0) + ( 0) · ( 0+ · ( 0)), ∈ (0, 1) (1-2)假定 0是评价函数 ( )的全局最优解，那么优化算法，尤其是线性搜索策略的算法最终要实现从当前位置 到目标位置 0的移动。如果用 表示 与 0的差，则公式1-2可以改写为： ( 0+ ) = ( 0) + · ( 0+ · ), ∈ (0, 1) (1-3)一般而言，优化问题的最优解的位置是未知的，当前位置是已知的，故而，通过 5
牛顿法等优化方法，拟牛顿的方法往往是更好的选择。然而，现实世界的优化问题，存在更多更为复杂的情况，如优化问题或优化系统的评价函数不可导，亦或评价函数存在噪声，更或者评价函数未知等。图1-3给出了一个存在噪声的黑盒优化示例，其中函数 ( )是解空间中解的理想分布函数，函数 ( )是实际抽样得到的评价函数的折线。显然，对于这样的一个（可能存在噪声的）黑盒优化模型，上述所有基于导数的确定性优化算法均无法实现问题的求解，或然性的优化算法，开始显示出它的不可替代性。图1-3黑盒目标函数优化示例Fig. 1-3 An example of optimization under black-box objective function1.2.2 或然性优化算法在进化计算的或然性优化算法用以解决连续空间的黑盒优化问题中，粒子集群优化（Particle Swarm Optimization）算法和差分进化（Differential Evolution）算法是两种最为著名的算法。每届的进化计算领域的旗舰会议IEEE计算智能大会（IEEE World Congress on Computational Intelligence）都会对这两种算法的最新研究进展及研究趋势做详细讨论。IEEE计算智能大会一般由三个子会议构成，分别为：IEEE神经网络联席大会（IEEE Joint Conference on Neural Networks）
1995年提出的一种群聚智能算法，该算法通过模拟鸟类觅食飞行实现复杂优化问题的求解。图1-4给出了一张自然界中候鸟觅食飞行的图片，从中可以看出，种群中领队的候鸟会带领整个种群飞行。 受此启发，在粒子集群优化算法中，种群全局最优解和每个图1-4自然界中鸟的觅食飞行Fig. 1-4 Flying behavior of birds foraging for food in nature粒子的历史最优解如同图1-4中的领队候鸟一样，共同影响着当前粒子的下一步移动方向及移动距离。另外，粒子自身的位置信息和飞行速度信息也影响着其自身下一步的移动方向及移动距离。公式1-15给出了粒子集群优化算法中粒子迭代的具体情况，其中 , 表示第 个粒子在第 代的速度信息， , 表示第 个粒子在第 代的位置信息，
本文编号：2828968
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2828968.html
