CFP last date
22 April 2024
Call for Paper
May Edition
IJCA solicits high quality original research papers for the upcoming May edition of the journal. The last date of research paper submission is 22 April 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A Binary Harmony Search Algorithm for Solving the Maximum Clique Problem

by Sepideh Afkhami, Omid R. Ma’rouzi, Ali Soleimani
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 69 - Number 12
Year of Publication: 2013
Authors: Sepideh Afkhami, Omid R. Ma’rouzi, Ali Soleimani
10.5120/11897-7956

Sepideh Afkhami, Omid R. Ma’rouzi, Ali Soleimani . A Binary Harmony Search Algorithm for Solving the Maximum Clique Problem. International Journal of Computer Applications. 69, 12 ( May 2013), 38-43. DOI=10.5120/11897-7956

@article{ 10.5120/11897-7956,
author = { Sepideh Afkhami, Omid R. Ma’rouzi, Ali Soleimani },
title = { A Binary Harmony Search Algorithm for Solving the Maximum Clique Problem },
journal = { International Journal of Computer Applications },
issue_date = { May 2013 },
volume = { 69 },
number = { 12 },
month = { May },
year = { 2013 },
issn = { 0975-8887 },
pages = { 38-43 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume69/number12/11897-7956/ },
doi = { 10.5120/11897-7956 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:30:05.994809+05:30
%A Sepideh Afkhami
%A Omid R. Ma’rouzi
%A Ali Soleimani
%T A Binary Harmony Search Algorithm for Solving the Maximum Clique Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 69
%N 12
%P 38-43
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The maximum clique problem (MCP) has long been concentrating the interest of many researchers in the field of combinatorial optimization. The goal inthe MCP is to find the largest complete subgraph (clique) in a given graph. Early methods developed to solve the MCP, suffer from exponential time complexity that limits their application to relatively small graph sizes. In order to overcome this limitation, a binary representation ofthe MCP is consideredand solved using a novel binary implementation of Harmony Search (HS) algorithm. The standard HS mimics music improvisation process to solve optimization problems. However, it is not suitable for binary representations. This is due to the pitch adjusting operator not being able to perform the local search in the binary space. Therefore the improvisation process in the proposed Binary Harmony Search (BHS) is modified to fit binary formulation of the MCP. The algorithm is tested on DIMACS benchmark graphs with up to 1024 nodes and 500000 edges, consisting of randomly generated graphs with known maximum cliques and of graphs derived from various practical applications. Results provide empirical evidence of the effectiveness the BHS for solving maximum clique problem, in a timely manner.

References
  1. B. Huang, "Finding maximum clique with a genetic algorithm," Penn. State Harrisburg Master's Thesis in Computer Science, 2002.
  2. P. Pevzner and S. Sze, "Combinatorial approaches to finding subtle signals in DNA sequences," Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, pp. 269–278, 2000.
  3. C. Solnon and S. Fenet, "A study of ACO capabilities for solving the maximum clique problem," Journal of Heuristics, pp. 1–31, 2006.
  4. R. Carraghan and P. Pardalos, "An exact algorithm for the maximum clique problem," Operations Research Letters, vol. 9, no. November, pp. 375–382, 1990.
  5. E. Marchiori, "A Simple Heuristic Based Genetic Algorithm for the Maximum Clique Problem," Proc. ACM Symp. Appl. Comput, pp. 366-373,1998.
  6. Q. Zhang, J. Sun, and E. Tsang, "An Evolutionary Algorithm With Guided Mutation for the Maximum Clique Problem," IEEE Transactions on Evolutionary Computation, vol. 9, no. 2, pp. 192–200, Apr. 2005.
  7. I. Bomze, M. Budinich, and P. M. Pardalos, "The maximum clique problem," In Handbook of Combinatorial Optimization, vol. 4, pp. 1–74, 1999.
  8. P. Östergård, "A fast algorithm for the maximum clique problem," Discrete Applied Mathematics, vol. 120, pp. 197–207, 2002.
  9. P. Pardalos and G. Rodgers, "A branch and bound algorithm for the maximum clique problem," Computers & operations research,vol. 19, pp. 363-375, 1992.
  10. E. Marchiori, "Genetic, iterated and multistart local search for the maximum clique problem," Applications of Evolutionary Computing, pp. 112–121, 2002.
  11. D. S. Johnson and M. A. Trick, "Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge," AMS, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, 1996.
  12. R. Battiti and M. Protasi, "Reactive local search for the maximum clique problem," Algorithmica, vol. 1198, no. 510, 2001.
  13. I. Bomze, M. Budinich, M. Pelillo, and C. Rossi, "Annealed replication: a new heuristic for the maximum clique problem," Discrete Applied Mathematics, vol. 121, pp. 27–49, 2002.
  14. Z. W. Geem, J. Kim, and G. Loganathan, "A new heuristic optimization algorithm: harmony search," Simulation 76, pp. 60-68, 2001.
  15. Z. W. Geem, C. Tseng, and Y. Park, "Harmony search for generalized orienteering problem: best touring in China," Advances in natural computation, pp. 741–750, 2005.
  16. Z. W. Geem, "Optimal cost design of water distribution networks using harmony search,"Engineering Optimization, pp. 1–49, 2010.
  17. Z. W. Geem, K. S. Lee, and Y. Park, "Application of Harmony Search to Vehicle Routing," American Journal of Applied Sciences, vol. 2, no. 12, pp. 1552–1557, Dec. 2005.
  18. F. Glover and M. Laguna, "Tabu search,"Kluwer Academic Publishers, Norwell, MA1998.
  19. E. Marchiori, "A simple heuristic based genetic algorithm for the maximum clique problem," Proceedings of the 1998 ACM symposium on Applied Computing - SAC '98, pp. 366–373, 1998.
  20. D. Johnson and M. Trick, "Cliques, Coloring, and Satisfiability: Second Dimacs Implementation Challenge. 1996," USA: American Mathematical Society.
  21. N. Sloane, "Unsolved problems in graph theory arising from the study of codes," Graph Theory Notes of New York, vol. 18, pp. 11–20, 1989.
  22. J. Lagarias and P. Shor, "Keller's cube-tiling conjecture is false in high dimensions," Manuscript, Bell Laboratories, vol. 27, no. 2, pp. 279–283, 1992.
  23. D. R. Wood, "An algorithm for nding a maximum clique in a graph," vol. 21, no. August 1995, pp. 211–217, 1997.
  24. C. Zhang and H. Hu, "Using PSO algorithm to evolve an optimum input subset for a SVM in time series forecasting," IEEE International Conference on Systems, Man, and Cybernetics, 2005.
Index Terms

Computer Science
Information Sciences

Keywords

Maximum clique problem Harmony search algorithm Graph theory Evolutionary computing

Powered by PhDFocusTM