GCLIQUE: An Open Source Genetic Algorithm for the Maximum Clique Problem

Shalin Shah

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.

Cite this code:

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

Usage:

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

Instance	Vertices	Edges	Best Known	Found	Duration (seconds)
brock200_1	200	14834	21	21	9
brock200_2	200	9876	12	12	30
brock200_3	200	12048	15	15	10
brock200_4	200	13089	17	16	2
brock400_1	400	59723	27	25	5
brock400_2	400	59786	29	25	14
brock400_3	400	59681	31	25	10
brock800_1	800	207505	23	20	2
C125.9	125	6963	34	34	0
C250.9	250	27984	44	43	30
C500.9	500	112332	57	55	5
C1000.9	1000	450079	67	65	3
C2000.5	2000	999836	16	15	5
C2000.9	2000	1799532	75	73	9
C4000.5	4000	4000268	18	16	28
c-fat200-1	200	1534	12	12	0
c-fat200-2	200	3235	24	24	0
c-fat200-5	200	8473	58	58	0
c-fat500-1	500	4459	14	14	0
c-fat500-2	500	9139	26	26	0
c-fat500-5	500	23191	64	64	0
c-fat500-10	500	46627	126	126	1
DSJC500.5	500	125248	13	13	3
DSJC1000.5	1000	499652	15	14	5
gen200_p0.9_44	200	17910	44	40	5
gen400_p0.9_55	400	71820	55	51	2
hamming6-2	64	1824	32	32	0
hamming6-4	64	704	4	4	0
hamming8-2	256	31616	128	128	1
hamming8-4	256	20864	16	16	0
hamming10-2	1024	518656	512	512	1
hamming10-4	1024	434176	40	40	10
johnson32-2-4	496	107880	16	16	0
keller4	171	9435	11	11	0
keller5	776	225990	27	27	10
MANN_a27	378	70551	126	125	1
MANN_a45	1035	533115	345	342	2
MANN_a81	3321	5506380	>=1100	1096	25
p_hat300-1	300	10933	8	8	0
p_hat300-2	300	21928	25	25	0
p_hat300-3	300	33390	36	36	30
p_hat500-1	500	31569	9	9	0
p_hat500-2	500	62946	36	36	0
p_hat500-3	500	93800	>=50	49	0
p_hat700-1	700	60999	11	11	9
p_hat700-2	700	121728	>=44	44	0
p_hat700-3	700	183010	>=62	62	3
p_hat1000-1	1000	122253	>=10	10	2
p_hat1000-2	1000	244799	>=46	46	5
p_hat1000-3	1000	371746	>=68	65	11
p_hat1500-1	1500	284923	>=12	11	2
p_hat1500-2	1500	568960	>=65	65	2
p_hat1500-3	1500	847244	>=94	93	8
san200_0.7_1	200	13930	30	30	0
san200_0.7_2	200	13930	18	18	2
san200_0.9_1	200	17910	70	70	16
san200_0.9_2	200	17910	60	60	28
san200_0.9_3	200	17910	44	37	5
san400_0.5_1	400	39900	13	13	1
san400_0.7_1	400	55860	40	40	5
san400_0.7_2	400	55860	30	30	2
san400_0.7_3	400	55860	22	18	20
san400_0.9_1	400	71820	100	100	1
sanr200_0.7	200	13868	18	18	1
sanr200_0.9	200	17863	42	41	1
sanr400_0.5	400	39984	13	13	3
sanr400_0.7	400	55869	21	21	5
san1000	1000	250500	15	10	1