• Article
  • | |
  • Metrics
  • |
  • Reference [21]
  • |
  • Related [20]
  • |
  • Cited by [1]
  • | |
  • Comments
    Abstract:

    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.

    Reference
    [1] Rubinstein RY. The cross-entropy method for combinatorial and continous optimization. Methodolgy and Computing in Applied Probality, 1999,2:127-190.
    [2] Rubinstein RY, Kroses DP. The cross-entropy method, a unified approach to combinatorial optimization. Monte-Carlo Simulation and Machine Learning. Springer-Verlag, 2004.
    [3] Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, eds. Complexity of Computer Computations. Plenum Press, 1972.
    [4] Bomze IM, Budinich M, Pardalos PM, Pelilo M. The maximum clique problem. In: Du DZ, ed. Handbook of Combinatorial Optimization. 1999. 1-74.
    [5] Pevzner PA, Sze SH. Combinatorial approaches to finding subtle signals in dna sequences. In: Proc. of the Int’l Conf. on Intelligent Systems for Molecular Biology. AAAI Press, 2000. 269-278.
    [6] Ji YM, Xu X, Stormo GD. A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics, 2004,20(10):1591-1602.
    [7] Website. http://dimacs.rutgers.edu/challenges/
    [8] Battiti R, Protasi M. Reactive local search for the maximum clique problem. Algorithmica, 2001,29(4):610-637.
    [9] Busygin S. A new trust region technique for the maximum weight clique problem. Discrete Mathematics, 2006,154(15):2080-2096.
    [10] Grosso A, Locatelli M, Croce FD. Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem. Journal of Heuristics, 2004,10(2):135-152.
    [11] Katayama K, Hamamoto A, Narihisa H. An effective local search for the maximum clique problem. Information Processing Letters, 2005,95(5):503-511.
    [12] Solnon C, Fenet S. A study of ACO capabilities for solving the maximum clique problem. Journal of Heuristics, 2006,12(3): 155-180.
    [13] Pullan W, Hoos HH. Dynamic local search for the maximum clique problem. Journal of Artificial Intelligence Research, 2006,25: 159-185.
    [14] Marchiori E. Genetic, iterated and multistart local search for the maximum clique problem. In: Cagnoni S, ed. Proc. of the Applications of Evolutionary Computing. LNCS 2279, 2002. 112-121.
    [15] Zhang QF, Sun JY, Tsang E. An evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Trans. on Evolutionary Computation, 2005,9(2):192-200.
    [16] Holland JH. Adaption in Natural and Artificial Systems. Ann Harbor, MI: The University of Michigan Press, 1975.
    [17] Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperating agents. IEEE Trans. on Systems, Man, and Cybernetics Part B: Cybernetics, 1996,26(1):29-41.
    [18] Cantu-Paz E. A survey of parallel genetic algorithms. Calculateurs Paralleles, 1998,10(2):141-171.
    [19] Ram DJ, Sreenivas TH, Subramaniam KG. Parallel simulated annealing algorithms. Journal Of Parallel and Distributed Computing, 1996,37:207-212
    [20] BullnHeimer B, Kotsis G, Strauss C. Parallelization strategies for the ant system. High Performance and Algorithms and Software in Nonlinear Optimization, Applied Optimization, 1998,24:87-100.
    [21] OpenMPI. Open source high performance computing. http://www.open-mpi.org/
    Comments
    Comments
    分享到微博
    Submit
Get Citation

吕 强,柏战华,夏晓燕.一种求解最大团问题的并行交叉熵算法.软件学报,2008,19(11):2899-2907

Copy
Share
Article Metrics
  • Abstract:4646
  • PDF: 5952
  • HTML: 0
  • Cited by: 0
History
  • Received:August 02,2007
  • Revised:October 09,2007
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063