Local Search Optimization

Comprehensive Tools for Local Search Optimization

Local search optimization methods are used for obtaining "good" solutions to combinatorial problems when the search space is large, complex, or poorly understood. In such cases, traditional search methods cannot be used. SAS/OR software enables you to implement genetic algorithms using the procedure - PROC GA.

Genetic Algorithms

Genetic algorithms are a family of local search algorithms that seek optimal solutions to problems using the principles of natural selection and evolution. They can be applied to almost any optimization problem, and are especially useful for problems where other calculus-based techniques do not work, such as when the objective function has many local optima, is not differentiable or continuous, or solution elements are constrained to be integers or sequences.

The GA procedure enables you to implement the basic genetic algorithm by default, and also to employ other advanced techniques to handle constraints, accelerate convergence, and perform multiobjective optimizations. PROC GA enables you to model your problem using a variety of solution forms including sequences, integer or real vectors, boolean encodings, and combinations of these. It also provides you with a choice of genetic operators appropriate for these encodings, while allowing you to write your own.

Outlined below is the sequence of steps involved in a typical genetic algorithm optimization:

  1. Initialize the problem data, such as cost coefficients and parameter limits.
  2. Specify the following five basic optimization parameters:

    1. Encoding: The general structure and form of the solution

    2. Objective: The function to be optimized

    3. Selection: How members of the current solution generation are chosen to propagate the next generation

    4. Crossover: How the attributes of parent solutions are combined to produce new offspring solutions

    5. Mutation: How random variation is introduced into the new offspring solutions to maintain genetic diversity.
  3. Generate a population of solutions for the initial generation.

  4. Monitor the progress of the algorithm and record your results.