PROC GA: Using Standard Genetic Operators and Objective Functions :: SAS/OR(R) 9.2 User's Guide: Local Search Optimization

The GA Procedure

Using Standard Genetic Operators and Objective Functions

The GA procedure includes a set of objective functions and crossover and mutation operators, and also enables you to define your own with a subroutine. The standard operators and objectives that are provided for each encoding type are summarized in Table 1.8.

Table 1.8: Standard Genetic Operators for Each Encoding

Encoding	Crossover	Mutation	Objective
real	arithmetic	delta
	heuristic	null
	null	uniform
	simple
	twopoint
	uniform
integer	arithmetic	delta
	null	null
	simple	uniform
	twopoint
	uniform
Boolean	simple	null
	null	uniform
	twopoint
	uniform
sequence	cycle	invert	TSP
	null	null
	order	swap
	pmatch

The following sections describe the standard genetic operators and objectives and how to invoke them.

Crossover Operators

Arithmetic

This operator is defined for real and integer encoding. It treats the solution segment as a vector, and computes offspring of parents and as

where is a random number between 0 and 1 generated by the GA procedure. For integer encoding, each component is rounded to the nearest integer. It has the advantage that it always produces feasible offspring for a convex solution space. A disadvantage of this operator is that it tends to produce offspring toward the interior of the search region, so it might not work if the optimum lies on or near the search region boundary. For single-segment encoding, you can specify the use of this operator with the call

call SetCross( 'Arithmetic');

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetCross( 'Arithmetic', segment);

From within a user crossover subroutine, you can use the call

call Cross(selected, segment, 'Arithmetic');

where selected is the selection parameter passed to your subroutine, and segment is the segment to which the arithmetic crossover operator is to be applied.

Cycle

This operator is defined for sequence encoding. It produces offspring such that the position of each element value in the offspring comes from one of the parents. For example, consider parents and ,

For the first child, pick the first element from the first parent:

To maintain the condition that the position of each element value must come from one of the parents, the position of the '8' value must come from , because the '8' position in is already taken by the '1' in :

Now the position of '5' must come from , and so on until the process returns to the first position:

At this point, choose the remaining element positions from :

For the second child, starting with the first element from the second parent, similar logic produces

This operator is most useful when the absolute position of the elements is of most importance to the objective value. For single-segment encoding, you can specify this operator with the call

call SetCross( 'Cycle');

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetCross( 'Cycle', segment);

From within a user crossover subroutine, you can use the use the call

call Cross(selected, segment, 'Cycle');

where selected is the selection parameter passed to your subroutine, and segment is the segment to which the cycle crossover operator is to be applied.

Heuristic

This operator is defined for real encoding. It treats the solution segments as real vectors. It computes the first offspring from two parents and , where is the parent with the best objective value, as

where is a random number between 0 and 1 generated by the GA procedure. The first child is a projection, and the second child is a convex combination, as with the arithmetic operator. This operator is unusual in that it uses the objective value. It has the advantage of directing the search in a promising direction, and automatically fine-tuning the search in an area where solutions are clustered. If the solution space has upper and lower bound constraints, the offspring are checked against the bounds, and any component outside its bound is set equal to that bound. The heuristic operator performs best when the objective function is smooth, and might not work well if the objective function or its first derivative is discontinuous.

For single-segment encoding, you can specify this operator with the call

call SetCross( 'Heuristic');

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetCross( 'Heuristic', segment);

From within a user crossover subroutine, you can use the call

call Cross(selected, segment, 'Heuristic');

where selected is the selection parameter passed to your subroutine, and segment is the segment to which the heuristic crossover operator is to be applied.

Null

This operator is used to specify that no crossover operator be applied. It is not usually necessary to specify the null operator, except when you want to cancel a previous operator selection. You can specify the null operator with the call

call SetCross( 'null');

For multisegment encoding, you can specify a segment to which the operator should be applied with the call

call SetCross( 'null', segment);

Order

This operator is defined for sequence encoding. It produces offspring by transferring a randomly chosen subsequence of random length and position from one parent, and filling the remaining positions according to the order from the other parent. For parents and , first choose two random cutpoints to define a subsequence:

Starting at the second cutpoint and cycling back to the beginning, the elements of in order are as follows:

  
        2 5 6 8 7 9 3 4 1

After removing 3, 4, 5 and 6, which have already been placed in , you have the following entries:

  
        2 8 7 9 1

Placing these back in order starting at the second cutpoint yields the following sequence:

Applying this logic to yields the following sequence:

This operator maintains the similarity of the relative order, or adjacency, of the sequence elements of the parents. It is especially effective for circular path-oriented optimizations, such as the traveling salesman problem. For single-segment encoding, you can specify this operator with the call

call SetCross( 'Order');

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetCross( 'Order', segment);

From within a user crossover subroutine, you can use the call

call Cross(selected, segment, 'Order');

where selected is the selection parameter passed to your subroutine, and segment is the segment to which the order crossover operator is to be applied.

Pmatch

The partial match operator is defined for sequence encoding. It produces offspring by transferring a subsequence from one parent, and filling the remaining positions in a way consistent with the position and ordering in the other parent. Start with two parents and randomly chosen cutpoints as indicated:

The first step is to cross the selected subsegments as follows (note that '.' indicates positions yet to be determined):

Next, define a mapping according to the two selected subsegments:

  
        9-3, 3-4, 4-5, 1-6

Then, fill in the positions where there is no conflict from the corresponding parent, as follows:

Last, fill in the remaining positions from the subsequence mapping. In this case, for the first child, and , , , and for the second child, , , , and .

This operator tends to maintain similarity of both the absolute position and relative ordering of the sequence elements, it and is useful for a wide range of sequencing problems. For single-segment encoding, you can specify this operator with the call

call SetCross( 'Pmatch');

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetCross( 'Pmatch', segment);

From within a user crossover subroutine, you can use the call

call Cross(selected, segment, 'Pmatch');

where selected is the selection parameter passed to your subroutine, and segment is the segment to which the Pmatch crossover operator is to be applied.

Simple

This operator is defined for integer, real, and Boolean encoding. It has one property, . This operator performs the following action: a position within an encoding of length is chosen at random, such that $1 \leq k \lt n$ . Then for parents and , the offspring are as follows:

${child1} = [p_1, p_2,...,p_k,q_{k+1},q_{k+2},...,q_n]$

${child2} = [q_1, q_2,...,q_k,p_{k+1},p_{k+2},...,p_n]$

For integer and real encoding, you can specify an additional property of value , where $0 \lt a \leq 1$ . It modifies the offspring as follows:

$p_i = a p_i + (1-a) q_i, \: i=k+1,k+2,...,n$

$q_i = a q_i + (1-a) p_i, \: i=k+1,k+2,...,n$

${child1}= [p_1,p_2,...,p_k,q_{k+1},q_{k+2},...,q_n]$

${child2}= [q_1,q_2,...,q_k,p_{k+1},p_{k+2},...,p_n]$

For integer encoding, the elements are then rounded to the nearest integer. For Boolean encoding, the parameter is ignored, and is effectively 1.

For single-segment encoding, you can specify this operator with the call

call SetCross( 'Simple', 'alpha', a);

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetCross( 'Simple', segment, 'alpha', a);

From within a user crossover subroutine, you can use

call Cross(selected, segment, 'Simple', a);

where selected is the selection passed to your subroutine, and segment is the segment to which the simple crossover operator is to be applied.

Twopoint

This operator is defined for integer, real, and Boolean encoding of length $n \geq 3$ , and has one property,

. Two positions,

and

, are chosen at random, such that $1 \leq k1 \lt k2 \lt n$ . Element values between those positions are swapped between parents. For parents

and

, the offspring are as follows:

${child1}=[p_1,p_2,...,p_{k1},q_{k1+1},...,q_{k2},p_{k2+1},...,p_n]$

${child2}=[q_1,q_2,...,q_{k1},p_{k1+1},...,p_{k2},q_{k2+1},...,q_n]$

For integer and real encoding, you can specify an additional property of value , where $0 \lt a \leq 1$ . It modifies the offspring as follows:

$p_i = a p_i + (1-a) q_i, \: i=k1+1,k1+2,..., k2$

$q_i = a q_i + (1-a) p_i, \: i=k1+1,k1+2,..., k2$

${child1}=[p_1,p_2,...,p_{k1},q_{k1+1},...,q_{k2},p_{k2+1},...,p_n]$

${child2}=[q_1,q_2,...,q_{k1},p_{k1+1},...,p_{k2},q_{k2+1},...,q_n]$

Note that small values of reduce the difference between the offspring and parents. For Boolean encoding, is always 1. For single-segment encoding, you can specify the use of this operator with the call

call SetCross( 'Twopoint', 'alpha', a);

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetCross(selected, segment, 'Twopoint', 'alpha', a);

From within a user crossover subroutine, you can use the call

call Cross(selected, segment, 'Twopoint', a);

where selected is the selection passed to your subroutine, and seg is the segment to which the two-point crossover operator is to be applied.

Uniform

This operator is defined for integer, real, and Boolean encoding of length $n \geq 3$ , and has two properties, and , where $0 \lt alpha \leq 1$ and $0 \lt p \leq 0.5$ . For and parents and , offspring and are generated such that

$s_i = \{ a t_i + (1-a)s_i, & { with probability p} \ s_i, & { otherwise }\ .$

$t_i = \{ a s_i + (1-a)t_i, & { with probability p\space } \ t_i, & { otherwise } .$

Note that and determine how much interchange there is between parents. Lower values of and imply less change between offspring and parents. For Boolean encoding, is always assigned to be 1. If you do not specify , it defaults to a value of 1. If you do not specify , it defaults to a value of 0.5.

For single-segment encoding, you can specify the use of this operator with the call

call SetCross( 'Uniform', 'alpha', a, 'p', p);

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetCross( 'Uniform', segment, 'alpha', a, 'p', p);

From within a user crossover subroutine, you can use the call

call Cross(selected, seg, 'Uniform', a, p);

where selected is the selection parameter passed to your crossover subroutine, and seg is the segment to which the uniform crossover operator is to be applied. In both cases, if the encoding is Boolean, the parameter is ignored, and is effectively 1.

Mutation Operators

Delta

This operator is defined for integer and real encoding. It has two properties, and . It first chooses elements of the solution at random, where is the value of the property, and then perturbs each chosen element by a fixed amount, set by , the value of the property. must be an array with the same length as the encoding. A randomly chosen element of the solution is modified such that

$s_k \in \{ s_k - d_k , s_k + d_k \}$

If upper and lower bounds are specified with a SetBounds call, then is adjusted as necessary to fit within the bounds. This operator gives you the ability to fine-tune the search by modifying the magnitude of the property. One possible strategy is to start with larger values, and then reduce them as the search progresses and begins to converge to an optimum. This operator is also useful if the optimum is known to be on or near a boundary, in which case can be set large enough to always perturb the solution element to a boundary. For single-segment encoding, you can specify this operator with the call

call SetMut( 'delta', 'nchange', n, 'delta', d);

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetMut( 'delta', segment, 'nchange', n, 'delta', d);

You can invoke this operator on a solution segment from within a user mutation subroutine with the call

call Mutate( selected, segment, 'delta', d, n);

where is the selection parameter passed into the subroutine.

Invert

This operator is defined for sequence encoding. It picks two locations at random and reverses the order of elements between them. This operator is most often applied to the traveling salesman problem. For single-segment encoding, you can specify this operator with the call

call SetMut( 'invert');

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetMut( 'invert', segment);

You can invoke this operator on a solution segment from within a user mutation subroutine with the call

call Mutate( selected, segment, 'invert');

where is the selection parameter passed into the subroutine.

Null

This operator is used to specify that no mutation operator be applied. It is not usually necessary to specify the null operator, except when you want to cancel a previous operator selection. You can specify the null operator with the call

call SetMut( 'null');

For multisegment encoding, you can specify a segment to which the operator should be applied with

call SetMut( 'null', segment);

Swap

This operator is defined for sequence problem encoding. It picks two random locations in the solution vector and swaps their values. You can also specify that multiple swaps be made for each mutation, by setting the property. For single-segment encoding, you can specify the swap operator with the call

call SetMut( 'swap', 'nswap', n);

where is the number of swaps for each mutation. For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetMut( 'swap', segment, 'nswap', n);

You can invoke this operator on a solution segment from within a user mutation subroutine with the call

call Mutate( selected, segment, 'swap', n);

where is the selection parameter passed into the subroutine.

Uniform

This operator is defined for Boolean encoding or for real or integer encoding with upper and lower bounds specified with a SetBounds call. To apply this operator, a position is randomly chosen within the solution , and is modified to a random value between the upper and lower bounds for element . There are two properties you can specify, and . If you set the property to , the operator is applied to locations. If you set the property to a value , where $0 \lt p \lt 1$ , the operator is applied at each position with probability . Only the last property setting is active, overriding any previous settings. If no property is set, a default value of 1 is used. You can specify this operator with one of the following two calls:

call SetMut( 'uniform', 'nchange', n);

call SetMut( 'uniform', 'pchange', p);

For multisegment encoding, you can specify the segment to which the operator should be applied with the call

call SetMut( 'uniform', segment, 'nchange', n);

You can invoke this operator on a solution segment from within a user mutation subroutine by using one of the following statements, where is the selection parameter passed into the subroutine:

call Mutate( selected, segment, 'uniform', n);

call Mutate( selected, segment, 'uniform', p);

This operator can prove especially useful in early stages of the optimization, since it tends to distribute solutions widely across the search space, and to avoid premature convergence to a local optimum. However, in later stages of an optimization, when the search needs to be fine-tuned to home in on an optimum, the uniform operator can hinder the optimization.

Objective Functions

TSP

The TSP objective calculates the value of the traveling salesman problem objective. It has one property, , which is a two-dimensional array representing distances between locations. If , then d[,] is the distance between location and location .

Top of Page