העבודה עוסקת בפתרון סאב-אופטימלי לבעיית הקליקה המקסימלית, באמצעות אלגוריתמים גנטיים.
היא מציעה פתרונות, מבצעת עליהם שינויים ומשווה את התוצאות לאלגוריתמים אלטרנטיביים. העבודה כתובה באנגלית.
Genetic Algorithm for the Maximum Clique Problem             August 31st, 2005
Abstract             This paper investigates GA's power in solving the Maximum Clique Problem.
At first, a basic GA is generated, with most simple GA's operators. The first algorithm preliminary converge to a local optima. Several modifications are done, including The function check which checks if some chromosome is an expandable clique and expands it if it is, mutation variations such as guided mutation, which uses the lower bound of the maximum clique as the clique that was already found, in order to search in thinner search space, greedy replacement which is like the regular mutations, but mutates only if it makes progress. These modifications increased the local optima's cardinality, but the global optimum wasn't reached most of the times. Trying to escape from the local optima and to perform some local search, the anticheck function was used and a little better results were reached, but still way from satisfactory.
It was then clear that some major changes are required. Major changes, including changing the fitness function to a variation of annealed fitness function, using union crossover [2] and diversity operator. Few instances of DIMACS benchmarks are tested and some completely solved, but as the problem size increases, the algorithm is still stuck at suboptimal solution.
In this paper We're going to discuss this phenomenon and examine the GA's power at solving the MCP.