一种求解加权约束满足问题的RCGA算法

摘要：

针对遗传算法在求解WCSP时收敛速度慢、搜索能力差等问题,提出一种新的WCSP求解算法RCGA.利用图分割技术将WCSP的约束图分割为若干最小相关的子图,重新确定变量序进行编码,采用WCSP的代价函数设计适应度函数,利用轮盘赌选择法对种群进行筛选.实验结果表明,RCGA算法能够使父代的优点更好地遗传给下一代,提高了向最优解收敛的速度,并增强了对最优解的搜索能力,整体性能明显优于单纯GA算法.

关键词：图分割、最小相关、WCSP、遗传算法

所属期刊栏目：35

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金61262030,61100025

在线出版日期：2015-05-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：54-58