分布估计算法种群进化机制研究.pdf

学校代码:10406
分类号: 学号:090081002011


南昌航空大学

硕士学位论文
(学位研究生)


分布估计算法种群进化机制的研究





硕士研究生: 黄情操
导师: 余达祥副教授
申请学位级别: 硕士
学科、专业: 信号与信息处理
所在单位: 信息工程学院
答辩日期: 2012-06
授予学位单位: 南昌航空大学
1
Study on population evolutionary
mechanism of estimation of
distribution algorithms





A Dissertation
Submitted for the Degree of Master
On signal and information processing




by Huang Qingcao




Under the Supervision of
Vice Prof. Yu Daxiang





College of Information and Enginnering
Nanchang Hangkong University, Nanchang, China
June, 2012
2
摘要
分布估计算法(EDAs)从提出到现在虽然取得了不少进展,但是还有不少问
题需要深入研究。例如对算法的种群进化机制研究,算法的设计与应用研究等。
分布估计算法种群进化机制主要包括算法的模式定理和变量之间的联结关系,算
法的种群多样性保持和算法的收敛性。分布估计算法的变量之间的联结关系是算
法的本质属性,决定了算法求解问题的难度。算法的种群多样性保持对于分布估
计算法避免陷入局部最优有着极其重要的意义,决定了算法的搜索结果是否全局
意义上的最优解,是分布估计算法理论中一个非常重要的问题。收敛性是分布估
计算法最重要的指标之一,决定了算法能否正确有效的进行搜索,能否正确有效
的解决过去不能解决或者不能有效解决的问题,提高其工作效率。
本文以分布估计算法为基础,结合其他智能算法,对于算法的收敛性和和多
样性进行了研究。本文的研究内容如下:
(1) 首先介绍了分布估计算法及其研究背景,并且由一个例子简单的介绍了分
布估计算法的求解过程;接着对分布估计算法进行了概要性的描述,引出了分布
估计算法种群进化机制的研究成果与不足,最后提出了本文的研究方向和方法。
(2) 着重介绍了分布估计算法的基本框架结构,变量离散型和变量连续型的分
布估计算法的研究和发展,以及分布估计算法种群进化机制的一些基础理论,重
点介绍了算法的收敛性分析和多样性保持的数学工具和方法,为后面的研究打下
基础。
(3) 对一类分布估计算法中的种群进化机制进行了研究,重点研究了分布估
计算法的收敛性对于算法性能的影响,在简要的分析蚁群算法的基础上,提出了
蚁群算法与分布估计算法融合的算法,并且运用随机过程理论中的马尔科夫链对
该算法的收敛性进行了证明,最后通过实验仿真,表明在该模型下,在文中所述
的算法有效的改善了分布估计算法的收敛性。
(4) 通过分析分布估计算法中种群进化机制中的种群多样性,引入了均匀变异
算子,并与单变量边缘分布算法相结合提出了一种保持种群多样性的单变量边缘
分布算法的算法,通过实验比较,结果表明新算法在维持种群的多样性方面确有
成效。
关键词:分布估计算法,单变量边缘分布算法,种群,收敛性,均匀变异算
子,多样性,蚁群算法

I
3
Abstract
Although some progress has been made since the birth of estimation of
distribution algorithms,there are many issues to be studied such as algorithm theoretical
analysis on the mechanism of evolution and population, algorithm design and
application and so on. Population evolutionary of estimation of distribution algorithms
mechanisms mainly includes algorit