主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
吕 强,柏战华,夏晓燕.一种求解最大团问题的并行交叉熵算法.软件学报,2008,19(11):2899-2907
一种求解最大团问题的并行交叉熵算法
Leader-Based Parallel Cross Entropy Algorithm for Maximum Clique Problem
投稿时间:2007-08-02  修订日期:2007-10-09
DOI:
中文关键词:  交叉熵方法  最大团问题  并行计算
英文关键词:Cross Entropy method  maximum clique problem  parallel implementation
基金项目:Supported by the National Research Foundation for the Doctoral Program of Ministry of Education of China (国家教育部博士点基金); the Natural Science Foundation of Jiangsu Province of China under Grant No.BK2003030 (江苏省自然科学基金)
作者单位
吕 强 苏州大学 计算机科学与技术学院,江苏 苏州 215006
江苏省计算机信息处理重点实验室,江苏 苏州 215006 
柏战华 苏州大学 计算机科学与技术学院,江苏 苏州 215006 
夏晓燕 江苏省计算机信息处理重点实验室,江苏 苏州 215006 
摘要点击次数: 3290
全文下载次数: 3426
中文摘要:
      为了提高交叉熵算法求解最大团问题(maximum clique problem,MCP)的性能,提出一种领导者-跟随者协作求解的并行策略来实现交叉熵算法,从而达到减少计算时间和保障解的质量这两方面的平衡.算法中领导者活跃在并行处理器之间采集数据,并根据当前获得信息对跟随者作出决策;受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间,完成各自的集团产生任务.采用了OpenMPI在MIMD平台上实现了该算法,并应用到MCP基准测试问题上.加速比和效率分析结果表明,算法具有很好的加速比和效率.而与其它几种当前最好的启发式算法相比,结果表明算法相对于基于种群的启发式算法有一定的性能改善.
英文摘要:
      The Cross Entropy method is a new search strategy for combinatorial optimization problems. However, it usually needs considerable computational time to achieve good solution quality. This paper introduces a Cross Entropy algorithm for solving maximum clique problem (MCP). To make the Cross Entropy algorithm faster, this paper proposes a leader-based cooperative parallel strategy. Unlike the widely used coarse-grained parallel strategy, our method has a leader, who can move around the parallel processors and collect data actively, and several followers whose main job are simply to sample the cliques guided by the leader via transition matrix. To evaluate the performance of the algorithm, this paper implements the algorithm using OpenMPI on MIMD architecture, and applies it on the MCP benchmark problems. The speedup and efficiency are analyzed, and the results are compared with those obtained by four other best heuristic algorithms. The results show that the presented method has achieved good performance among those best population-based heuristics.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利