Implementation of a genetic algorithm for the maximum clique problem in C++. A clique of a graph is a set of vertices in which each pair in the set have an edge between them i.e. it is a complete subgraph. A clique of maximum size is called the maximum clique. The algorithm uses new types of crossovers to achieve good results on several public graph datasets.

@misc{shah2020gclique,
  title={GCLIQUE: An Open Source Genetic Algorithm for the Maximum Clique Problem},
  author={Shah, Shalin},
  year={2020},
  doi={10.5281/zenodo.3829645}
}

- Compile the code using g++
- e.g. g++ gaClique.cpp
- Run ./a.out filename generations
- e.g. ./a.out instances/C500.9.CLQ 100
- Typical value for generations is 100

(If you are looking for a simpler algorithm in Java, please see clique2)

(The intersection crossover was borrowed from a similar idea in this algorithm)

Results on some DIMACS instances are show in the following table. The algorithm is allowed to run for a maximum duration of 30 seconds. 

• The best performance is on the hamming, p_hat and c-fat instances.
• The worst performance is on the san1000 and brock instances.
• Please remove all comments and other extraneous text from the graph text instance file.