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
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.