离散变量多群体演化算法的研究.pdf

南京邮电大学
硕士学位论文摘要

学科、专业：工学、电磁场与微波技术
研究方向：无线通信与电磁兼容

作 者：2008 级硕士研究生 杨伟男
指导教师：薄亚明 教授



题 目：离散变量多群体演化算法的研究
英文题目： A Study on the Multi-Population Evolutionary Algorithms for
Discrete Variables



主 题 词：演化算法、全局寻优、离散变量、旅行商问题、相控阵
Key words：Evolutionary Algorithms, Global Optimization, Discrete Variables,
Traveling Salesman Problem, Phased array
摘要
遗传算法、交叉熵方法均是有效的全局随机搜索技术，但两者由于单种群优化而容易
出现早熟收敛或收敛慢的情况，为克服这种缺陷，本文引入团队进步算法的双群体分工模
型，在遵循原算法机理特性的基础上分别提出双群体遗传算法(DPGA)和双群体交叉熵方法
(DPCE)。
遗传算法的变异、交叉熵的的整个运算过程可类比于团队进步算法的探索行为，所以
在两原算法中只需引入学习和成员更新规则，便设计成与团队进步算法具有相同行为特征
的双群体算法。通过基准函数测试表明，两个新算法在收敛速度和全局寻优能力上都明显
提高。之后在 DPCE 中利用组合问题的交叉熵模型、在 DPGA 中利用 2-opt 邻域交换策略，
分别将两种双群体算法改造成离散变量优化算法，并应用于 TSP 问题。两个新算法对 30
城市以内的 TSP 问题均能给出最佳路径，而对多城市问题求得的最好解也比单种群更优。
最后将双群体算法用于相控阵天线综合，对阵元相位分别进行离散和连续两种优化，通过
对 20 元线阵和 64 元面阵的不同扫描角优化可知，离散方案可将副瓣电平压得更低。
由于双群体算法中种群出现了明显分工，使其能兼顾快速收敛和全局寻优两个对立方
面，函数优化和离散算例应用结果还表明新算法具有通用性强、计算量小、稳定度高、参
数调整容易等其他特性，可用于多类实际问题求解，所以该双群体方案将成为算法改良的
一种新途径。


关键词：演化算法；全局寻优；离散变量；旅行商问题；相控阵
I
Abstract
The genetic algorithm (GA) and cross entropy method (CE) are both effective technologies
with global random search. However, they are prone to slow or premature convergence with a
single population optimization. In this dissertation, the dual-population model in the team
progress algorithm (TPA) is introduced for GA and CE improvements. Based on the introduced
principle, the dual-population genetic algorithm and the dual population cross entropy method
are presented respectively.
The mutation of GA and the whole operation process of CE are both similar to the
exploration action of TPA. So the two dual population algorithms can be designed if only the
study action and member r