Non-Deterministic Optimization with Genetic Algorithms

Preface

0. Optimization Problems

Optimization problems come in many forms, including linear, nonlinear, convex, and combinatorial. Since the majority of problems of combinatorial nature are non-deterministic, genetic algorithms are a popular choice for solving them, for it is an easy and structured approach to solving them.

A linear optimization problem has the following form

max \(Z = ax_1 + bx_2 + cx_3 + ... + nx_n \geq K\)
subjected to:
\(x_i \geq 0, \forall i \in \mathbb{N}\)
\(x_1 + x_2 \leq 10\)
\(x_3 + x_4 \leq 15\)
with \(x_i\) being the decision variables and \(a, b, c, ..., n\) being the coefficients. The function Z has to be maximized for a given value of K, that is often calculated using the simplex method. But it can also be solved using other methods such as the graphical method or the branch and bound.

What matter most is that the linear problems are approximations of non-linear ones. An as almost everything in nature is nonlinear, we can make only rough predictions of the behavior of the system, using linearization techniques to transform it into a linear one.

Nonlinear problems involves the use of nested, or recursive structures, such as trees and graphs. The traveling salesperson problem is a classic example of a nonlinear problem. So are the problem of verifying arrays of input data to determine if they are valid or not. Or problems involving games and interactions between agents, that have adaptative behavior, according to the evolution of the game's states.