The Maximum Clique Problem (MCP) has been studied for decades and is well known in graph theory as a problem that is difficult as it as it is known to be NP-complete. The MCP has a vast domain of application such as finance, biochemistry, bioinformatics, and many more. Many niching methods have been successfully applied in Genetic Algorithms (GA) to diversify the population and avoid getting trapped within local optima. In this paper, we propose an approach using the Sharing method and a Hybrid Genetic Algorithm (HGA) for the maximum clique problem. We also propose a non-evolutionary approach using a migration mechanism to boost the current HGA.
Over the last few years, the size of networks has increased rapidly and the amount of information from massive data sets has become a highly researched computational challenge.
Some examples of fast growing networks exist in social networks and bioinformatics. The use of traditional methods for analyzing and treating the large amounts of information has become problematic. The nature of the MCP (NP-complete) explains why is it more complicated to find the maximum clique when the number of vertice N Copyright retained by the authors. increases dramatically. Traditional heuristic approaches for finding the maximum clique problem have become insufficient for this new challenge.
Cheng et al. [
A well-known metaheuristic in evolutionary algorithms is
the genetic algorithm. The earliest work related to GAs
dates back to 1954 when Nils and Barricelli published a
paper on computer simulation of evolution [
A GA is a combinatorial optimization technique that mimics the process of natural evolution. The algorithm does not rely on building the final solution based on local search, which distinguishes itself from traditional approaches. A subset of feasible solutions of a problem is encoded in chromosomes that represent individuals in a population. The evolutionary process is then applied through population selection, crossover, and mutation operations. Each individual is then evaluated using a fitness function and the best of the individuals are transmitted into the next generation. The following procedure shows a basic genetic algorithm: GA procedure(){
Initialize population(); Evaluate population(); While not (End_Condition){
Select parent(); Crossover(); Mutation();
Evaluate population(); } } score of individual in populated landscapes. This technique is known as one of the best niching technique to escape from local optima.
In this paper, we implemented the sharing method, as we are attempting to diversify and explore the elements of the graph more thoroughly. The sharing function recalculates the fitness function based on how dense an area of the graph is used. Therefore, as with any fitness function, our shared fitness becomes that shown in equation 1.
f (i) j =1 where sh is the sharing based on the distance d between vertex i and j. The sharing function is found in equation (2).
n ∑ sh(d(i, j)) (1) (2)
Since the 1990s, significant research has been conducted on genetic algorithm, especially for finding the maximum clique.
Early works on the maximum clique problem were focused
on greedy approaches. One of the first significant
improvements on the maximum clique was done by
BronKerbausch[
In 1986, Robson improved this algorithm by adding
backtracking techniques in combination with more
complicated case analyses and dynamic programm€ing.
This however increased the space complexity of the MCP
[
Genetic algorithms have been successfully applied to many
NP-hard problems in various domains [
The idea of combining a genetic algorithm and a
heuristic local search has been used in earlier applications.
Marchiori [
Fitness sharing method has been used to avoid GA
converging to local maxima. This technique was proposed
by Holland [
d σ share 0, otherwise
)α , if d < σ share
Yet another technique that inspired sociological and ecological movements between sub-populations is the concept of migration. Migration in genetic algorithms has been well studied and applied in many parallel genetic algorithms.
There are important considerations before implementing migration in genetic algorithms. Migration policies define the replacement rule to apply between two sub-populations. It is equivalent to answering the question: “What kind of individual in a sub-population A is replacing what kind of individual in sub-population B”. Topology is another important aspect in multi-population genetic algorithm.
The topology defines the structure of communication
between several sub-populations [
Migration rates and migration policies have been shown
to improve the convergence of genetic algorithm
considerably. Cantu-Paz has conducted experiments in
which the best-replacing-worst population policy has
demonstrated the best results for migration policies [
The heuristic local search algorithm is a local search based
on greedy approach. Given a set of vertices, this algorithm
finds the maximal clique using a “Relax”, a “Repair” and
an “Extend” steps. Marchiori described this algorithm in
details [
The HGA is then obtained by combining the heuristic local search with a genetic algorithm given in figure 1. The heuristic function is added after the crossover operation to find maximal clique.
In our solution we propose a migration mechanism based on two sub-populations, a main sub-population and a secondary sub-population. The main population will have the role of a standard HGA. The secondary sub-population will serve as a pool that generates the new chromosomes for migrating into the main subpopulation. This mechanism should help to accelerate the convergence of the current hybrid genetic algorithm.
The idea of combining a heuristic local search and a genetic algorithm is not new. It has proven to be competitive in solving the maximum clique problem. One issue with this approach is the convergence into local optima. The diversification strategy relies on the genetic operators: crossover and mutation. The exploration of the set of feasible solutions (or neighborhood) in hybrid genetic algorithm is an area that can be improved.
In our approach we define two sub-populations. The
Main sub-population uses a generic HGA defined
previously. This sub-population specializes in the
exploitation of the data. The secondary sub-population will
be dedicated to exploration of the data. In the secondary
population, an effort is made to diversify the population.
The sub-population will then transfer the best of its
population to the main sub-population through a migration
mechanism. In this approach, we want to maximize the
functions of exploration and exploitation of the genetic
algorithm. Figure 2 shows the role of each sub-population.
In our algorithm, it was decided to use a best-replace-worst
migration policy at each generation, where the best
individuals in the sub-population will replace a percentage
of the worst individuals in the main sub-population. We
also used a ladder migration topology defined in [
The main sub-population is the standard genetic heuristic
algorithm discussed by Marchiori [
To initialize the population, we randomly choose vertices for each chromosome in the new population. We then apply the heuristic function, which extracts the maximal clique from each chromosome. We then sort the population by fitness, to determine which of the elements should migrate to the main sub-population.
The data used for our experiments are from the DIMACS
(Center for Discrete Mathematics and Theoretical
Computer Science) benchmark graphs. It is composed of a
collection of 9 different classes of graphs for evaluating
and comparing different algorithms for solving the
maximum clique problem. This collection consists of
random graphs with known maximum clique size as well as
graphs obtained from various areas of applications. The
CFAT graphs are based on the fault diagnosis problem [
A series of experiments were conducted using a small subset of the Dimacs data sets. The results obtained show that the performance of our algorithm is close to the best results obtained on the same data sets from the DIMACS challenge (table 1).
keller4 keller5 keller6 hamming8-‐4 hamming10-‐4 MANN_a27 MANN_a81
In these experiments, we evaluate the effect of the mutation by holding other parameters static. We analyzed the effect of mutation on the Keller5 graph with the mutation rate parameters: 0.5%, 1%, 5%, 10% and 20%. Table 2 shows the parameters chosen for this set of experiments.
Population size 100 Maximum iteration 50 Mutation 0.5%, 1%, 5%, 10%, 20% Crossover rate 100% (uniform crossover)
At each generation, the mutation breaks current maximal clique in every chromosome, by replacing current nodes by other random nodes.
On one hand, a low mutation rate keeps nodes that are good candidates for the maximum clique and the heuristic algorithm find good local solutions. But less graph exploration are possible using a low mutation rate. On the other hand, a high mutation rate gives a good chance of graph exploration, but the local search become less efficient, as to many nodes are exchanged in chromosomes. Choosing a good mutation rate is a trade-off between finding a good local solution and good graph exploration. Figure 4 shows the minimum, the average and maximum fitness score for each chromosome for 1% mutation rate.
We can observe two phases applying the GA to the maximum clique problem. In the first phase, a high variation of the fitness score phase can be observed from 0 to the 15th generation. During this phase, the HGA explores various combinations of nodes in the graph, so the fitness score change rapidly. Then a phase of stabilization is observed where the maximal cliques are kept in the population and improvement occurs progressively. During the stabilization phase, the chances of discovering bigger cliques are low because the HGA reach local maxima.
The results obtained in our experiments shows that 1% mutation rate achieves the best performance with the fastest convergence and helps diversifying the population to its maximums. The HGA algorithm found a 24-clique after only eight generations.
In this set of experiments, we fix the mutation rate with the value found greedily in the previous experiment. We then vary the migration rate with the parameters: 1%, 5%, 10%, 20%, 30%, 50% and 90%. Table 3 shows the parameters chosen applied on the same graph (Keller5).
Population size 100 Maximum iteration 50 Mutation 1% Crossover rate 100% (uniform crossover) Migration rates 1%, 5%, 10%, 20%, 30%,
Table 3 Parameters for50te%sti,n9g0m%igration rate
The effect of a high migration rate is the replacement of good solutions obtained by the HGA, whereas a low migration rate injects not enough new seeds in new population. The experiments show that the optimum migration rate is reached at 10% and the maximum clique is found after 28 generations (ground truth maximum clique=27). Figure 5 shows the minimum, the average and maximum fitness score for each chromosome for 10% migration rate.
In this graph, we can observe that the maximum fitness increase by levels, which means that new maximal cliques are found. After one or two generations the stabilization phase is reached and the GA continued graph exploration. The results show that the migration process helped the genetic algorithm to escape from local maxima and find the maximum clique by adding more graph exploration capability. In these experiment we test the effect of migration on a variation of the population size and maximum number of generation. We compare the effect of migration on different parameter setup. Table 4 shows the parameters for this set of experiments.
(Population size / (10/1000,y), (10/1000,n), Maximum iteration / (50/200,y), (50/200,n), migration) (100/100, y), (100/100,n), (200/50,y), (200/50,n) Mutation 1% Crossover rate 100% (uniform crossover) Migration rates 10%
Table 4 Parameters for testing effects of migration The results indicate that for each configuration, applying our migration mechanism increase the size of maximum clique found and also accelerates the convergence toward the best solution.
In these experiments we test the effect of fitness sharing on same graph. The parameter σshare from equation (2) represents the number of niches. We vary the number of niches with the values: 3, 7, 10, 20. Table 5 shows the parameters used for this set of experiments.
Population size Maximum iteration Mutation Crossover rate Number of Niches (σshare)
A high number of niches (σshare) allow diversifying the population by reducing the fitness value of individual from the same niche. This way, the chance to promote other individuals from other niches is higher.
We obtained the best results in this series of experiments with the parameter σshare=20. the maximum clique is found after 170 generations. Figure 6 shows the minimum, the average and maximum fitness score for each chromosome for σshare=20.
The fitness sharing method also plays a function of graph exploration by reducing the fitness values of individual in the same niche. Then other individual from other niches are promoted in the population. Finally we have shown that fitness sharing method is also well suited for graph exploration and helps to find the maximum clique.
For the maximum clique problem, we have proposed a solution that implemented a migration mechanism composed of two subpopulations. The main sub-population is specialized on data exploitation and the secondary subpopulation is specialized on data exploration.
Our results have shown that both sharing and migration improve the convergence and results of the genetic algorithm. We have shown that migration proves to be a valuable tool in converging on the maximum, or high maxima relatively quickly. We have also discussed the potential usefulness in using sharing to find multiple maximum solutions in the same problem. We also found that in order to maximize the difference and prevent fast convergence of the minimum fitness value, a 1% mutation rate appears to give the best results. The migration rate was also empirically derived to be best at 10% migration.
These experiments lay groundwork for potential research in the future. We used a non-evolutionary approach by adding a second sub-population, which serves the main population by generating random new seeds. Other improvements can be made by developing a more specific heuristic local search algorithm for the secondary subpopulation dedicated to graph exploration.
There are more improvement possibilities by developing a co-evolutionary method where instead of generating new seed at each iteration, the second sub-population evolves at the same time with the main sub-population. Migration is maintained at every generation for faster convergence. Finally a cultural co-evolutionary approach would give feedback from the main sub-population to the secondary sub-population, to help building better candidate for exploration.