Omega our multi ethnic genetic algorithm

Combinatorial optimization is a branch of optimization. Its domain is optimization\nproblems where the set of feasible solutions is discrete or can be reduced to a discrete\none, the goal being that of nding the best possible solution. Two fundamental\naims in optimization are nding algorithms characterized by both provably good\nrun times and provably good or even optimal solution quality. When no method\nto nd an optimal solution, under the given constraints (of time, space etc.) is\navailable, heuristic approaches are typically used. A metaheuristic is a heuristic\nmethod for solving a very general class of computational problems by combining user-\ngiven black-box procedures, usually heuristics themselves, in the hope of obtaining a\nmore e cient or more robust procedure. The genetic algorithms are one of the best\nmetaheuristic approaches to deal with optimization problems. They are a population-\nbased search technique that uses an ever changing neighborhood structure, based on\npopulation evolution and genetic operators, to take into account di erent points in\nthe search space. The core of the thesis is to introduce a variant of the classic GA\napproach, which is referred to as OMEGA (Multi Ethnic Genetic Algorithm). The\nmain feature of this new metaheuristic is the presence of di erent populations that\nevolve simultaneously, and exchange genetic material with each other. We focus our\nattention on four di erent optimization problems de ned on graphs. Each one is\niii\niv\nproved to be NP-HARD. We analyze each problem from di erent points of view, and\nfor each one we de ne and implement both a genetic algorithm and our OMEGA.