Genetic heuristics in optimization problems (abstract)

ABSTRACT

In this work we investigate different heuristics for solving NP-hard problems. These heuristics explore the solution space in a parallel fashion, attempting to converge to an optimal solution by mimicking the way natural selection and genetics favor the fittest candidates. These randomized, but not directionless, search procedures were developed and labeled genetic algorithms by John Holland. We apply the heuristics to various classical optimization problems, including the knapsack problem and the maximum cut problem. The latter consists of partitioning the set V of vertices of a graph G = (V, E) into two disjoint sets V1 and V2 such that the sum of the weights of the edges from E that have one endpoint in V1 and the other in V2, is maximized. Starting with a randomly chosen initial population, the genetic algorithm will move from one generation to a better one by using the operations of reproduction, crossover and mutation. We investigate and compare different crossover techniques. The survival of well fit individuals is based on the computation of a fitness function which is closely related to the objective function in the optimization problem. This study considers and compares various fitness functions. We thus make use of a fitness function that penalizes overfilled knapsacks for instance. We conclude this work by giving a few suggestions on the use of genetic algorithms in combinatorial optimization problems.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms