概率分析的进化算法及其研究进展

概率分析的进化算法及其研究进展

一、概率分析进化算法及其研究进展(论文文献综述)

戴勇谦,张明武,祝胜林,戴勇新[1](2013)在《基于变异概率分析的改进QGA及其应用》文中研究表明标准量子遗传算法(QGA)在应用于组合优化问题时,会由于早熟收敛而陷入局部最优。为解决该问题,引入k位变异子空间概念分析Q-bit的变异概率分布,指出传统随机变异机制和QGA自有变异机制之间的冲突,提出一种基于观测状态的阶段式大尺度变异机制。将该机制的变异算子嵌入量子旋转策略表,对不同规模的0/1背包问题进行测试,结果表明,该机制能有效避免早熟收敛,跳出局部最优,全局寻优能力优于标准QGA。

戴勇谦,张明武,祝胜林,戴勇新[2](2013)在《一种新的量子遗传算法变异机制》文中研究表明针对标准的量子遗传算法(QGA)应用于数值优化时容易早熟收敛而陷入局部最优的问题,引入k位变异子空间概念对Q-bit变异概率分布进行了分析,传统随机变异机制和QGA自蕴变异机制存在冲突。为此提出一种用观测状态的阶段式大尺度变异机制(SLVMBOO),并将SLVMBOO变异算子嵌入到量子旋转策略表中,实现起来简单高效。通过典型复杂函数测试表明SLVMBOO使得QGA应用于数值优化时能有效地避免早熟收敛、跳出局部最优,而且全局寻优能力优于其它方法。

何小娟[3](2011)在《分布估计算法及其在生产调度问题中的应用研究》文中研究说明分布估计算法是进化计算领域新兴起的一类概率分析进化算法,它结合了智能计算和统计学习的知识,根据当前种群中若干较好个体的信息建立概率分布模型描述问题解空间的分布,并通过对概率模型随机采样产生新的种群,如此反复进行,实现种群的进化。分布估计算法通过建立概率模型描述变量之间的相关关系,能更有效地混合构造块并实现构造块重组,可以解决传统遗传算法难以解决的问题,尤其是解决非线性、高维复杂问题。分布估计算法求解问题的关键是建立一个能恰当描述问题解分布的概率模型,但是,概率模型的建立是一个非常复杂的问题,如果所建立的模型过于简单则不能正确反映问题的本质特征,影响求解效率,而模型过于复杂则会使算法学习复杂度增大。尤其对于复杂的组合优化问题,由于这类问题本身的复杂性,可行解中各变量间具有很强的相关性,建立一个能准确描述问题可行解的概率分布模型非常困难,在将分布估计算法用于求解复杂的组合优化问题时,如何建立一个能准确描述问题解分布的概率模型成为制约算法应用的瓶颈。文中结合优良模式连接的思想、Bayesian统计推断理论与离散quasi-copula理论,对概率模型的建立方式进行改进,以提高算法求解复杂组合优化问题的能力,并将算法用于求解生产调度问题和旅行商问题,主要完成了以下工作:1.根据遗传算法中的模式定理与积木块假设理论,通过概率把多个个体的相似特征结合起来考虑,发掘优势群体中个体结构的相似点,提出了基于优良模式连接的思想。在求解问题时,通过在优势群体中考虑个体相似点的信息,对以较高频率出现在后代中的多个相邻变量以概率为基础进行连接,组成一个连接块,令其为优良模式连接块,并在进化过程中以块为整体参与进化,增强那些适应度高于种群平均适应度的模式在下一代中出现的概率,相应地减少那些适应度低于种群平均适应度的模式在下一代中出现的概率。基于这种思想,使算法能有效避免构造块破坏问题,具有较好的连锁学习效果,同时为避免陷入局部最优,有条件的调整每个连接块内部各变量的排列顺序,从而有效提高分布估计算法的优化性能。2.将基于优良模式连接的分布估计算法应用于求解Job Shop调度问题、柔性Job Shop调度问题和旅行商问题中。对于Job Shop调度问题和柔性Job Shop调度问题,在建立概率模型时充分利用了相邻工序在优势群体中的信息,通过概率值对以较高频率出现在优势群体中的相邻工序进行连接,从而使建立的概率模型能较好地反应调度问题中工序排序的特点。在旅行商问题中,在建立概率模型时充分考虑相邻城市出现在优势群体中的频率信息,并通过概率的大小对其进行连接,从而使建立的概率模型能较好地反应旅行商问题中个体的结构特征。仿真结果表明,所提出的算法在求解上述问题时表现出较好的性能。3. Bayesian统计推断方法与贝叶斯网络优化方法不同,它不需要优化复杂的网络结构,而是直接利用样本提供的信息,通过建立一个后验分布对样本进行推断。因此,本文借鉴Bayesian统计推断理论中对样本的推断思想和方法,充分利用优势群体中个体的信息,建立了一种针对离散优化问题的基于Bayesian统计推理的分布估计算法。首先,针对个体结构的每一个位置,通过优势群体信息建立一种不断更新的先验分布概率模型,利用相邻变量出现在优势群体中的频率,通过计算每一个位置上的条件概率向量建立条件分布概率模型;然后,结合先验分布概率与条件分布概率,通过贝叶斯公式的转化,建立一种后验分布概率模型。这种后验概率分布模型综合了先验概率信息和样本信息,具有较好的统计推断效果,从后验概率模型中抽样产生新群体,通过对后验概率模型的不断更新,实现进化过程。4.将基于Bayesian统计推理的分布估计算法应用于求解Job Shop调度问题、柔性Job Shop调度问题和旅行商问题中。根据Job Shop问题和柔性Job Shop调度问题的特点,针对工序排序的每一个位置建立先验分布概率模型,充分利用优势群体中各台机器上工序的排列信息,通过贝叶斯公式,建立一种能较好地反映Job Shop调度问题特点的后验概率模型,并从中抽样产生新群体;对于旅行商问题,充分利用各个城市间的排列位置信息建立先验分布概率模型和条件分布概率模型,通过贝叶斯公式获得一种后验概率模型并用以指导产生新群体。针对典型算例的仿真实验结果表明,该算法具有较好的寻优能力和鲁棒性,所建立的概率模型具有较好的稳定性。5.在离散Quasi-copula理论的基础上,针对离散优化问题,提出了一种基于经验Copula的分布估计算法。对个体采用整数编码方式,采用经验分布函数求解各个变量的边缘分布函数,在估计经验Copula函数时,首先将以整数编码的个体映射到(0,1)区间上,然后对单位超立方体进行分割,等分成若干子超立方体,统计优势群体中的个体落入各个子超立方体中的个体数,构造多维经验Copula函数,得到一种针对离散变量的多变量相关的联合分布函数,并从中抽样产生新群体。由于考虑了多变量间的相关性,因而所建立的概率模型能较好地反映问题的特征。同时对算法的时间复杂性进行了分析。6.将基于经验Copula的分布估计算法应用于求解旅行商问题和柔性Job Shop调度问题中。通过估计经验Copula,建立了上述问题的多变量相关的联合分布概率模型,并从中采样。仿真实验结果表明,该算法具有较好的求解能力。

易叶青,林亚平,刘云如[4](2010)在《基于决策图贝叶斯的盲源信号分离算法》文中研究指明从混合观测数据向量中恢复不可观测的各个源信号是阵列处理和数据分析的一个典型问题。提出了一种基于决策图贝叶斯的盲源信号分离算法,该算法利用决策图贝叶斯优化算法代替JADE算法中的联合对角化操作,通过构造和学习网络来替代传统遗传算法中的交叉重组和变异等遗传算子,避免了对大量控制参数和遗传算子的人工选择和重要构造块的破坏。仿真结果表明,提出的算法比JADE算法和基于遗传算法的盲源信号分离方法均具有更高的分离精度。

谭乐怡,王守觉[5](2009)在《一种按基因重要度收敛的进化算法》文中研究表明提出基因重要度的概念,通过实验证明基因重要度对于单变量边缘分布算法(Unvaried Marginal Distribution Algo-rithm,UMDA)收敛的重要性.由此提出一种基于基因重要度的进化算法.该算法首先对组成染色体的各基因进行重要度排序,随后对重要度大的基因先进行收敛操作,每次收敛当前重要度最大的基因,直到所有基因全部收敛.实验数据表明,本算法的收敛速度更快,而且更容易求出满意解.

姚金涛,杨波,孔宇彦[6](2009)在《一种自适应模型构造的层次决策图贝叶斯优化算法》文中研究表明描述和分析零星模型构造(SMB)方法中固定模型构造周期参数对层次决策图贝叶斯优化算法性能的影响,提出了一种基于自适应模型构造(AMB)的层次决策图贝叶斯优化算法,通过计算群体平均信息熵密度而确定相邻两代群体所对应网络模型的相似度,仅当相似度小于给定阈值时自适应重构贝叶斯网络模型,从而在保证贝叶斯网络模型精确性的前提下减少贝叶斯网络模型的构造次数,进而降低算法计算复杂度,加速收敛.实验结果表明,AMB方法有效可行.

魏懿[7](2008)在《基于概率粒子群算法的背包问题的研究》文中研究表明背包问题属于NP难问题,解决背包问题是解决组合优化所面临的问题之一,在现实中有着广泛的应用背景,开展对解决复杂组合优化问题的算法研究具有一定的理论意义和实用价值。本文在对背包问题进行研究分析的基础上,分析和比较了各类方法,提出了一种用于求解0-1背包问题的基于概率模型的粒子群算法。该算法利用对概率向量的操作实现群体的进化,来提高算法性能。然后利用本文构造的算法分别针对不同规模的背包问题进行了求解。实验结果表明本文提出的概率粒子群优化算法可以有效的改进算法收敛能力和寻优效果。

姚金涛,刘财兴,孔宇彦[8](2008)在《基于决策图贝叶斯网络的混沌优化算法》文中提出提出一种基于决策图贝叶斯网络的混沌优化算法,该算法把贝叶斯概率模型结合到混沌遗传算法中,通过构造和学习网络来替代传统遗传算法中的交叉重组和变异等遗传算子,避免了对大量控制参数和遗传算子的人工选择和重要构造块的破坏。同时,通过在决策图贝叶斯网络中引入混沌操作,对部分个体进行启发式变异,能有效提高群体多样性,避免早熟或局部收敛。仿真结果表明,提出的算法比改进前的决策图贝叶斯优化算法和混沌遗传算法均有更快的收敛速度,较强的鲁棒性。

刘娟[9](2008)在《基于BOA的受限延时QoS路由算法》文中指出无线adhoc网络中受限延时的QoS路由问题是NP-complete问题,针对其特点,将贝叶斯优化算法引入其中,用贝叶斯网络对QoS参数进行模拟、采样和优化。实验结果表明,贝叶斯优化算法对于受限延时的QoS路由问题有着很好的解决能力,同时与其他算法比较,能够搜索到较低代价的路由,满足QoS路由要求。

刘振,史建国,赵峰,孙永芹[10](2007)在《概率模型进化算法与仿真研究》文中认为针对传统遗传算法,指出了遗传算法的新的发展方向及概率模型进化算法。介绍了几种基于概率的模型进化算法(UMDA、BMDA、CGA以及BOA),用仿真的方式验证了概率模型进化算法能提高遗传算法的性能,最后指出图型模型在进化计算中的重要作用。

二、概率分析进化算法及其研究进展(论文开题报告)

(1)论文研究背景及目的

此处内容要求:

首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。

写法范例:

本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。

(2)本文研究方法

调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。

实证研究法:依据现有的科学理论和实践的需要提出设计。

定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。

定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。

跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。

模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

三、概率分析进化算法及其研究进展(论文提纲范文)

(2)一种新的量子遗传算法变异机制(论文提纲范文)

1 引言
2 QGA的自蕴变异机制分析
    2.1 传统的进化算法变异机制缺陷
    2.2 QGA的自蕴变异机制分析
3 SLVMBOO的提出
4 SLVMBOO的设计与实现
    4.1 设计SLVMBOO需解决的两个问题
    4.2 SLVMBOO设计思想
    4.3 SLVMBOO的嵌入式变异算子SymbolQCp的设计
5 实验结果及分析
    5.1 参数设置与测试函数
    5.2 仿真结果
6 结论

(3)分布估计算法及其在生产调度问题中的应用研究(论文提纲范文)

摘要
Abstract
插图索引
附表索引
第1章 绪论
    1.1 生产调度问题研究背景和意义
    1.2 车间生产调度问题研究现状
    1.3 车间生产调度问题概述
        1.3.1 车间生产调度问题的特点及分类
        1.3.2 车间生产调度问题的方法
    1.4 本文的主要工作
    1.5 本文的组织结构
第2章 分布估计算法
    2.1 遗传算法
    2.2 分布估计算法研究背景
    2.3 分布估计算法研究现状
    2.4 分布估计算法
        2.4.1 分布估计算法基本框架
        2.4.2 分布估计算法特点及分类
        2.4.3 算法收敛性与复杂性分析
第3章 基于优良模式连接的分布估计算法及其应用
    3.1 优良模式连接的基本思想
    3.2 模式矩阵的建立方法
    3.3 分块优化思想及过程
    3.4 基于优良模式连接的EDA 算法基本流程
    3.5 仿真实验及结果分析
    3.6 小结
第4章 基于优良模式连接的分布估计算法求解车间生产调度问题
    4.1 基于优良模式连接的EDA 算法求解JSP 问题
        4.1.1 JSP 问题描述
        4.1.2 算法基本流程
        4.1.3 仿真实验及结果分析
    4.2 基于优良模式连接的EDA 算法求解FJSP 问题
        4.2.1 FJSP 问题描述
        4.2.2 算法基本流程
        4.2.3 仿真实验及结果分析
    4.3 小结
第5章 基于Bayesian 统计推理的分布估计算法
    5.1 Bayesian 统计推断理论
    5.2 概率模型的建立
        5.2.1 先验分布概率模型的建立
        5.2.2 条件分布概率模型的建立
        5.2.3 后验分布概率模型的建立
    5.3 概率模型的更新
        5.3.1 先验分布概率模型的更新
        5.3.2 条件分布概率模型的更新
        5.3.3 后验分布概率模型的更新
    5.4 算法基本流程
    5.5 仿真实验及结果分析
    5.6 小结
第6章 基于Bayesian 统计推理的分布估计算法求解车间生产调度问题
    6.1 基于Bayesian 统计推理的EDA 算法求解JSP 问题
        6.1.1 算法基本流程
        6.1.2 仿真实验及结果分析
    6.2 基于Bayesian 统计推理的EDA 算法求解FJSP 问题
        6.2.1 算法基本流程
        6.2.2 仿真实验及结果分析
    6.3 小结
第7章 基于经验Copula 的分布估计算法及其在离散优化问题中的应用
    7.1 离散Quasi-copula 基本概念
    7.2 基于经验Copula 的分布估计算法
        7.2.1 基于经验copula EDA 算法流程
        7.2.2 基于经验copula 的EDA 算法复杂性分析
    7.3 基于经验Copula 的EDA 算法求解TSP 问题
        7.3.1 求解TSP 问题的算法流程
        7.3.2 仿真实验及结果分析
    7.4 基于经验Copula 的EDA 算法求解FJSP 问题
        7.4.1 求解FJSP 问题的算法流程
        7.4.2 仿真实验及结果分析
    7.5 小结
结论与展望
参考文献
致谢
附录 A 攻读博士期间发表的学术论文

(4)基于决策图贝叶斯的盲源信号分离算法(论文提纲范文)

1 引言
2 盲源信号分离问题
3 决策图贝叶斯优化算法
4 基于决策图贝叶斯优化的盲源分离算法
    4.1 参数编码及初始群体的设定
    4.2 适应度函数的选取
    4.3 约束条件的保持
    4.4 算法描述
5 仿真实验
6 结论

(5)一种按基因重要度收敛的进化算法(论文提纲范文)

1 引 言
2 基于基因重要度的进化算法 (GIEA)
    2.1 基因重要度 (GI)
    2.2 基因重要度的排序
    2.3 设立优秀基因池
    2.4 基因收敛的算法流程
    2.5 GIEA的算法流程
3 收敛性分析
    3.1 遗传算法的收敛性定理
    3.2 GIEA的收敛性分析
4 测试函数和实验结果
    4.1 测试函数
    4.2 实验结果
5 结 论

(6)一种自适应模型构造的层次决策图贝叶斯优化算法(论文提纲范文)

1 引 言
2 层次贝叶斯优化算法及SMB增强方法
    2.1 决策图贝叶斯网络
    2.2 层次贝叶斯优化算法与SMB增强方法
3 自适应模型构造的层次决策图贝叶斯优化算法
    3.1 自适应模型构造 (AMB) 方法
    3.2 算法描述
4 实验结果及分析
    4.1 测试问题
        (1) 三阶欺骗函数:
        (2) 五阶陷阱函数:
        (3) 三阶层次陷阱函数[8]:
    4.2 实验结果
5 结束语

(7)基于概率粒子群算法的背包问题的研究(论文提纲范文)

中文摘要
英文摘要
第一章 绪论
    1.1 选题的背景和意义
        1.1.1 组合优化问题
        1.1.2 背包问题
        1.1.3 粒子群优化算法
    1.2 国内外研究现状
        1.2.1 背包问题的研究现状
        1.2.2 粒子群算法的研究现状
    1.3 本文的组织
第二章 背包问题
    2.1 背包问题简介
    2.2 背包问题的数学模型
    2.3 背包问题的算法简介
        2.3.1 背包问题的精确算法简介
        2.3.2 背包问题的近似算法简介
    2.4 小结
第三章 粒子群优化算法
    3.1 粒子群算法的三种典型模型
        3.1.1 基本PSO 模型
        3.1.2 引入惯性权重的PSO 模型
        3.1.3 带收缩因子的PSO 模型
    3.2 粒子群算法的特点
    3.3 PSO 算法的其他改进方法
        3.3.1 离散PSO
        3.3.2 自适应PSO
        3.3.3 混合PSO
        3.3.4 免疫PSO
    3.4 PSO 与其它进化算法的比较
    3.5 粒子群优化算法的应用
    3.6 小结
第四章 概率粒子群优化算法
    4.1 粒子群算法改进策略
        4.1.1 粒子群算法存在的问题及其改进思路
        4.1.2 PSO 的粒子速度更新项分析
        4.1.3 PSO 的收敛性能分析
        4.1.4 改进后的PSO 流程
        4.1.5 典型测试函数分析
    4.2 概率分析进化算法
        4.2.1 概率分析进化算法概述
        4.2.2 概率分析进化算法的基本原理
        4.2.3 概率分析进化算法的分类
    4.3 引入概率分析进化算法的粒子群算法
        4.3.1 概率粒子群算法描述
        4.3.2 改善搜索速度的策略
        4.3.3 概率粒子群算法流程
    4.4 小结
第五章 概率粒子群算法求解背包问题
    5.1 应用概率粒子群算法求解背包问题
        5.1.1 粒子的构造方式
    5.2 仿真试验
    5.3 小结
第六章 结论
参考文献
致谢
在学期间发表的学术论文和参加科研情况

(8)基于决策图贝叶斯网络的混沌优化算法(论文提纲范文)

引言
1 决策图贝叶斯优化算法
2 基于决策图贝叶斯网络的混沌优化算法
    2.1 随机扰动的确定
    2.2 算法描述
        (1)
        (2)选用(7)式所示的Logistic映射
        (3)按(8)式将选定的r个混沌变量βi(u+1)分别代入到式(4)的r个优化变量中,得到混沌变量ix',使混沌变量的变化范围分别变换到相应的优化变量的取值范围:
        (4)将式(8)代入式(4)计算个体适应度,并对其进行降序排列,为保证fk'(X')非负,并避免fk'(X')对某一代群体相对变化范围不大而减慢算法的收敛速度,必须对fk'(X')按下式作适当调整:
        (5)对个体进行二进制编码,并执行锦标赛竞争选择,从tP中选择N个体,根据选定的网络评价标准和约束条件构造相应的贝叶斯网络B;根据对B编码后的联合分布信息,对网络进行采样,从而产生N个新个体,用来替换父代个体,构成群体,描述如下:
        (6)若t≥T,算法终止。否则按式(9)调整个体适应度,计算平均适应度并与最大值按式(10)比较,如果成立,则算法终止,否则转(7)。
        (7)
        (8)
    2.3 算法分析
3 实验结果
    (1)为了验证所提出算法的有效性,用BCOA算法对文献[11]中的一组测试函数(如式(11))进行30次优化计算,并在相同的仿真环境设置下与文献[5]算法的平均测试结果进行比较,所得结果见表1,可以看出,BCOA算法能够比CGA算法更快收敛于全局最优解,这主要是由于贝叶斯网络模型的引入能够有效导引算法对解空间的搜索,减少了搜索过程的盲目性,提高了搜索效率。
    (2)另外,在选取相同的参数条件下,分别用BCOA算法和DBOA算法对文献[10]中的一组GA难函数(如式12)进行了30次测试,并对平均测试结果进行比较,所得结果如图3-6所示。
4 结论

(9)基于BOA的受限延时QoS路由算法(论文提纲范文)

1贝叶斯优化算法 (BOA)
2无线adhoc网络中基于BOA的受限延时QoS路由算法
    2.1受限延时QoS路由网络模型
    2.2问题编码
    2.3适应度函数
    2.4算法描述
3实验结果及分析
    3.1平均消息数
    3.2平均路由代价
4结论

(10)概率模型进化算法与仿真研究(论文提纲范文)

1 概率模型进化算法
    1.1 低阶概率模型进化算法
    1.2 高阶概率模型进化算法
2 概率模型进化算法的执行过程与仿真分析
3 结束语

四、概率分析进化算法及其研究进展(论文参考文献)

  • [1]基于变异概率分析的改进QGA及其应用[J]. 戴勇谦,张明武,祝胜林,戴勇新. 计算机工程, 2013(07)
  • [2]一种新的量子遗传算法变异机制[J]. 戴勇谦,张明武,祝胜林,戴勇新. 计算机仿真, 2013(02)
  • [3]分布估计算法及其在生产调度问题中的应用研究[D]. 何小娟. 兰州理工大学, 2011(12)
  • [4]基于决策图贝叶斯的盲源信号分离算法[J]. 易叶青,林亚平,刘云如. 计算机工程与应用, 2010(23)
  • [5]一种按基因重要度收敛的进化算法[J]. 谭乐怡,王守觉. 小型微型计算机系统, 2009(09)
  • [6]一种自适应模型构造的层次决策图贝叶斯优化算法[J]. 姚金涛,杨波,孔宇彦. 小型微型计算机系统, 2009(08)
  • [7]基于概率粒子群算法的背包问题的研究[D]. 魏懿. 华北电力大学(河北), 2008(11)
  • [8]基于决策图贝叶斯网络的混沌优化算法[J]. 姚金涛,刘财兴,孔宇彦. 系统仿真学报, 2008(12)
  • [9]基于BOA的受限延时QoS路由算法[J]. 刘娟. 科学技术与工程, 2008(12)
  • [10]概率模型进化算法与仿真研究[J]. 刘振,史建国,赵峰,孙永芹. 海军航空工程学院学报, 2007(05)

标签:;  ;  ;  ;  ;  

概率分析的进化算法及其研究进展
下载Doc文档

猜你喜欢