Previous Page | Next Page

Genetic Algorithms

Setting the Objective Function

Before executing a GA, you must specify the objective function to be optimized. There are currently two options available: a user function module and an IML-supplied traveling salesman problem (TSP) objective function.

User Function Module: The module must take exactly one parameter, which will be one solution, and return a numeric scalar objective function value. The module can also have a global clause, which may be used to pass in any other information required to determine the objective function value. If global parameters are used, you must be careful about changing them after the optimization has been initialized. If a change in a global parameter affects the objective function values, you must reevaluate the entire solution population (see GAREEVAL call) to ensure that the values are consistent with the changed global parameter.

The solution parameter passed into the routine is also written back out to the solution population when the module exits, so you should take care not to modify the parameter and therefore the solution population unintentionally. However, it is permissible and may prove very effective to add logic to the module to improve the solution through some heuristic technique or local optimization, and deliberately pass that improved solution back to the solution population by updating the parameter before returning. Using this hybrid approach may significantly improve the convergence of the GA, especially in later stages when solutions may be near an optimum.

TSP Objective Function: An objective function for the traveling salesman problem can be specified with integer sequence encoding. For the TSP, a solution sequence represents a circular route. For example, a solution s with the value

s = {2 4 3 1 5};

represents a route going from location 2 to location 4 to 3 to 1 to 5 and back to 2. You must also specify a cost matrix c, where c[i,j] is the cost of going from location i to location j. The objective function is just the cost of traversing the route determined by s, and is equivalent to the IML code:

start TSPObjectiveFunction(s) global(c);
nc = ncol(s);
cost = c[s[nc],s[1]];
do i = 1 to nc-1;
 cost = cost + c[s[i],s[i+1]];
end;
return (cost);
finish;

The IML-supplied order crossover operator and invert mutation operator are especially appropriate for the TSP and other routing problems.

Previous Page | Next Page | Top of Page