PROC GA: Using Multisegment Encoding :: SAS/OR(R) 9.2 User's Guide: Local Search Optimization

The GA Procedure

Using Multisegment Encoding

The GA procedure enables you to represent problems with solutions consisting of mixed parameter types by using multisegment encoding. Solutions can contain multiple segments, where each segment is a vector of one particular parameter type. Multiple segments can also be used to store additional information you want to keep for each solution for user objective functions or genetic operators. The utility functions provided by the GA procedure give you full access to read from and write to individual solution segments you define.

Segments are set up with a SetEncoding call. The input parameter to this call is a string consisting of letter-number pairs, with each pair describing the type and number of elements in one segment. The permitted letters and corresponding encodings are as follows:

R or r	specifies real encoding. The elements of the solution segment are real numbers. One common problem where this encoding is used is nonlinear function optimization over the real domain.
I or i	specifies integer encoding. The elements of the solution segment are integers. Examples of where this encoding might be used include assignment problems where the integers represent which resources are assigned to particular tasks, or problems involving real variables that are constrained to be integers.
B or b	specifies Boolean encoding. The elements of the solution consist of binary (0 or 1) bits. This type of encoding might be used, for example, to represent variables in a variable selection problem, or inclusion of particular items in a 0/1 knapsack problem.
S or s	specifies sequence encoding. The segment consists of randomly ordered sequences of integers ranging from 1 to the number of elements. For example, [2, 4, 5, 1, 3] is an example of S5 encoding, as is [5, 3, 2, 1, 4]. Sequence encoding is a natural way to represent routing optimizations like the traveling salesman problem, or any problem optimizing permutations of parameters.

Suppose the problem is to optimize the scheduling of 20 tasks, and for each task you need to choose one machine out of a set of appropriate machines for each task. The natural encoding for that problem could be set up with the following call:

  
    call SetEncoding('I20S20');

This call specifies a two-segment solution encoding, with segment 1 (I20) an integer vector representing the machine assignment for each task, and segment 2 (S20) representing the sequence of tasks.

When you use multisegment encoding, you must specify the segment parameter in SetMut or SetCross calls to specify an operator in a segment other than the first one. If you code your own operator subroutines, you can use utility functions provided by the GA procedure to extract and write out values to individual segments of the solution, and routines provided by the GA procedure to perform standard genetic crossover and mutation operations on selected segments. See the section "Using Standard Genetic Operators and Objective Functions" for a discussion of the operators provided by the GA procedure. See the section "Defining User Genetic Operators" and the section "Defining an Objective Function" for details of defining user routines.

Top of Page