文档介绍：学校代码：10406
分类号： 学号：090081002106
南昌航空大学
硕 士 学 位 论 文
（学位研究生）
混 合 元 胞 遗 传 算 法 与 多 层 元 胞 遗 传 算
法 的 研 究
硕士研究生： 揭丽琳
导 师： 黎明
申请学位级别：硕士
学科、专业： 信号与信息处理
所在单位： 信息工程学院
答辩日期：
授予学位单位：南昌航空大学
Research For Hybrid Cellular Genetic
Algorithm and Multiayer Cellular
Genetic Algorithm
A Dissertation
Submittedfor the Degreeof Master
On Signal & InformationProcessing
by Jie Lilin
Underthe Supervisionof
Prof. Li Ming
School of informationand engineering
NanchangHangkongUniversity,Nanchang, China
June ,2012
摘要
现实世界许多领域存在的问题都具有高度复杂性、多目标、多约束的要求，
采用传统的搜索方法处理十分困难，求解效果不够理想，如何找到对问题本身具
有更强求解能力的算法就成为一个迫切需要解决的问题。 遗传算法 (Genetic
Algorithms)作为进化算法中产生最早且影响最大的概率性搜索算法，它是通过模
拟自然界生物进化过程的自然选择与遗传信息规律而形成的一种高效全局寻优
方法，具有适用性强、鲁棒性好及并行计算等优势，已成功应用于求解传统搜索
技术难以解决的复杂优化问题。但是 标准遗传算法(Standard Genetic Algorithms)
不考虑空间结构环境和生物进化过程中种群局部个体间的相互作用，个体之间没
有位置关系，且遗传算子具有随机性、无方向性，因此种群多样性容易过早丢失，
导致算法陷入局部最优。元胞自动机是一种离散的数学模型，通过离散空间上大
量元胞个体简单的相互作用而形成整体上的复杂行为，特别适合于计算机模拟实
施复杂动态系统。 元胞遗传算法(Cellular GeneticAlgorithm）是一种将遗传算法
和元胞自动机原理有机地结合的算法，明显改善了遗传算法的全局收敛性能，已
成为解决复杂问题的一种有效方法。但是元胞遗传算法每次评价个体的适应度时
计算量较大，在解决非常复杂的优化问题时存在优化速度一般比较慢的缺点。同
时进一步提高元胞遗传算法的全局收敛率也还有很大的研究发展空间。
本文围绕如何解决一般元胞遗传算法在提高全局收敛率的同时一定程度降
低搜索效率的问题进行了研究，主要研究内容如下：
(A Hybrid Particle
Swarm and Multi-Population Cellular Genetic Algorithm)。该算法 首先将群体分割
成多个元胞子种群，选择合适的迁移策略，子种群之间相互通信共享进化信息，
适度降低算法的选择压力，从而更好地保持种群的多样性。算法的变异操作被粒
子群算法替代，使得局部搜索能力明显提高。元胞群体分割和粒子群变异较好地
均衡了全局探索和局部寻优之间的关系。最后分析了混