检索结果-内蒙古大学图书馆

模式识别与人工智能 2011年第2期24卷 185-193页

作者：何小娟曾建潮兰州理工大学电气工程与信息工程学院兰州730050 太原科技大学复杂系统与计算智能实验室太原030024

提出一种基于优良模式连接的分布估计算法求解TSP问题.首先构造两两相邻的模式矩阵,然后结合优良个体信息建立多个相邻模式的连接块.以块为整体调整排列顺序,避免重复搜索,改善优良模式构造块的破坏问题,提高搜索速度.同时对每个块内部... 详细信息

提出一种基于优良模式连接的分布估计算法求解TSP问题.首先构造两两相邻的模式矩阵,然后结合优良个体信息建立多个相邻模式的连接块.以块为整体调整排列顺序,避免重复搜索,改善优良模式构造块的破坏问题,提高搜索速度.同时对每个块内部的模式有条件地进行局部调整,进一步加强算法的局部搜索能力.仿真结果表明,本文算法在求解TSP问题时表现出较好的性能.

关键词：分布估计算法优良模式连接模式矩阵 TSP问题

来源：评论

学校读者我要写书评

暂无评论

分布估计算法及其在生产调度问题中的应用研究

分布估计算法及其在生产调度问题中的应用研究

引用

作者：何小娟兰州理工大学

学位级别：博士

分布估计算法是进化计算领域新兴起的一类概率分析进化算法,它结合了智能计算和统计学习的知识,根据当前种群中若干较好个体的信息建立概率分布模型描述问题解空间的分布,并通过对概率模型随机采样产生新的种群,如此反复进行,实现种群... 详细信息

分布估计算法是进化计算领域新兴起的一类概率分析进化算法,它结合了智能计算和统计学习的知识,根据当前种群中若干较好个体的信息建立概率分布模型描述问题解空间的分布,并通过对概率模型随机采样产生新的种群,如此反复进行,实现种群的进化。分布估计算法通过建立概率模型描述变量之间的相关关系,能更有效地混合构造块并实现构造块重组,可以解决传统遗传算法难以解决的问题,尤其是解决非线性、高维复杂问题。分布估计算法求解问题的关键是建立一个能恰当描述问题解分布的概率模型,但是,概率模型的建立是一个非常复杂的问题,如果所建立的模型过于简单则不能正确反映问题的本质特征,影响求解效率,而模型过于复杂则会使算法学习复杂度增大。尤其对于复杂的组合优化问题,由于这类问题本身的复杂性,可行解中各变量间具有很强的相关性,建立一个能准确描述问题可行解的概率分布模型非常困难,在将分布估计算法用于求解复杂的组合优化问题时,如何建立一个能准确描述问题解分布的概率模型成为制约算法应用的瓶颈。文中结合优良模式连接的思想、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)区间上,然后对单位超立方体进行分割,等分成若干子

关键词： Job Shop调度问题柔性Job Shop调度问题关键词分布估计算法优良模式连接 Bayesian统计推理经验Copula

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：