协同进化算法及其应用研究

进化计算已在各个领域得到了广泛的成功应用，但其理论和应用都还存在一些瓶颈问题。本文对其前沿方向之一——协同进化计算模型进行了深入地分析。针对海量数据分类问题、SAT问题、有约束和无约束数值优化、多目标优化、超大规模集成电路布图规划等五个具有挑战性的问题进行了系统深入地研究。针对不同问题提出了多种新的算法和实现策略，主要工作概括如下： (1) 针对海量数据的分类问题，提出了组织协同进化分类算法。它与现有进化分类方法的不同之处在于采用了一种自下而上的搜索机制，即先使若干样本的集合得到进化，再从进化结果中提取规则。这样有利于避免在进化过程中产生无意义的规则。实验中首先用12个UCI标准数据集测试了算法性能，然后用上千万的海量数据对算法的扩展性进行了分析和验证。最后，将算法应用于两个实际问题——雷达一维像识别和遥感舰船目标识别，获得了良好的效果。 (2) 针对SAT问题，提出了求解SAT问题的组织进化算法。它将原问题分解成若干子问题，用每个子问题形成一个组织。逐个解决子问题后再通过一定方式协调不同子问题间相冲突的变量，以达到求解原问题的目的。实验中用3700个不同规模的标准SAT问题对算法性能作了全面测试，验证了其有效性和通用性。 (3) 针对数值优化问题，提出了组织进化数值优化算法。该算法与传统遗传算法、进化规划、进化策略求解数值优化问题的运行机制不同。它先由个体构成组织，再由组织构成种群。进化操作不直接作用于个体上，而作用于组织上。从理论上证明了其具有全局收敛性。用15个无约束标准优化问题和13个有约束标准优化问题验证了算法性能。并对算法中的各个参数变化机理进行了分析，确定了其取值范围，便于读者应用。 (4) 提出了一种新的、适用于进化算法求解VLSI布图规划问题的布图表示方法——移动模式序列。设计了移动模式序列到布局的转换算法，对其正确性和复杂度进行了理论分析。移动模式序列能表示多种类型的模块，解决了其它表示方法不易设计进化算法中交叉算子的问题。因此，它有利于进化算法在布图规划领域中的进一步应用。 (5) 基于移动模式序列，提出了求解布图规划问题的组织进化算法。它能同时处理多种类型模块混合的布图问题。对300个硬矩形模块问题、100个软矩形模块问题、100个软矩形模块和非矩形模块的混合问题均求得了高质量的解，表明这一 摘要 方法适于求解大规模布图规划问题，具有很高的实用价值。 (6)提出了协同进化多目标优化算法，并根据其框架提出了求解布图规划问题 的多目标优化方法。它一次运行就可求出各种不同的线长和面积组合，便于用户 根据实际中面积和线长不同耗材比例进行选择。避免了调整权值，不用多次运行， 既节省了计算量，又便于用户进行决策。 关键词:进化算法协同进化算法组织数据挖掘分类雷达一维像识别 遥感图像识别SAT问题数值优化无约束优化有约束优化多目 标优化超大规模集成电路布图规划布图表示方法移动模式序列 西安电子科技大学博士学位论文