PROC GA: Choosing the Problem Encoding :: SAS/OR(R) 9.22 User's Guide: Local Search Optimization

The GA Procedure

Choosing the Problem Encoding

Problem encoding refers to the structure or type of solution space that is to be optimized, such as real-valued fixed-length vectors or integer sequences. The GA procedure offers encoding options appropriate to several types of optimization problems. You specify the problem encoding with a SetEncoding CALL statement,

call SetEncoding('encoding');

where the encoding string is a letter followed by a number, which specifies the type of encoding and the number of elements. The permitted letters and corresponding types of encoding are as follows:

R or r:	real-valued vector. This type of encoding is used for general non-linear optimization problems.
I or i:	integer-valued vector. This encoding is used for integer-valued problems. The integer size is 32 bits, which imposes a maximum value of 2,147,483,647 and a minimum value of –2,147,483,648 for any element of the vector. The integer vector encoding can also be used to represent bit vectors, where the 0–1 value of each bit in the integer vector is treated as a separate element. An example might be an assignment problem, where the positions within the vector represent different tasks, and the integer values represent different machines or other resources that might be applied to each task.
B or b:	Boolean vector. Each element represents one true/false value.
S or s:	sequence or permutation. In this encoding, each solution is composed of a sequence of integers ranging from 1 to the number of elements, with different solutions distinguished by different orderings of the elements. This encoding is commonly used for routing problems such as the traveling salesman problem or for scheduling problems.

For example, the following statement specifies a 10-element integer vector encoding:

   call SetEncoding('I10');

For problems where the solution form requires more than one type of encoding, you can specify multiple encodings in the encoding string. For example, if you want to optimize the scheduling of 10 tasks and the assignment of resources to each task, you could use a segmented encoding, as follows:

   call SetEncoding('I10S10');

Here the I10 (10-element integer vector) is assigned to the first segment, and represents the resource assignment. The S10 (10-element sequence) is assigned to a second segment, and represents the sequence of tasks. The use of segmented encodings is described in the section Using Multisegment Encoding.

Top of Page