一种求解最大团问题的并行交叉熵算法

• 作者: 吕强 夏晓燕 柏战华
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 交叉熵方法 最大团问题 并行计算
• 年，卷（期）: 2008,（11）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 2899-2907
• 页数: 9页
• 分类号: TP301
• 语种: 中文

摘要

为了提高交叉熵算法求解最大团问题(maximum clique problem,MCP)的性能,提出一种领导者.跟随者协作求解的并行策略来实现交又熵算法,从而达到减少计算时间和保障解的质量这两方面的平衡.算法中领导者活跃在并行处理器之间采集数据,并根据当前获得信息对跟随者作出决策;受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间,完成各自的集团产生任务.采用了OpenMPI在MIMD平台上实现了该算法,并应用到MCP 基准测试问题上.加速比和效率分析结果表明,算法具有很好的加速比和效率.而与其它几种当前最好的启发式算法相比,结果表明算法相对于基于种群的启发式算法有一定的性能改善.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吕强	苏州大学计算机科学与技术学院	134	1011	15.0	26.0
5	柏战华	苏州大学计算机科学与技术学院	2	19	2.0	2.0
6	夏晓燕		2	11	2.0	2.0