PROC GA: Specifying the Selection Strategy :: SAS/OR(R) 9.22 User's Guide: Local Search Optimization

The GA Procedure

Specifying the Selection Strategy

There are a number of different strategies that can employed to select the most fit solutions from a population to be propagated into the next solution generation. Regardless of the strategy chosen, the user must try set the selection properties to maintain a productive balance between selection pressure and preservation of diversity. Enough selective pressure must be maintained to drive the algorithm toward an optimum in a reasonable time, but too much selective pressure will eliminate the diversity of the population too quickly and lead to premature convergence to a suboptimal solution. One effective technique is to start the optimization process at a lower selective pressure, and increase it as the optimization continues. You can easily do this in the GA procedure by modifying the selection strategy with a SetProperty call inside an update routine. A description of the selection strategies and their properties follows.

Tournament Selector

This selector has one property, $\text{[math]}$ . The selector repeats the following process until the next generation of solutions has been specified: randomly choose a small subset of the current population, and then select the most fit from that subset. The selection pressure is controlled by the size of the subset chosen, specified by the $\text{[math]}$ property. Tournament sizes from 2 to 10 have been successfully applied to various genetic algorithm optimizations, with sizes over 4 or 5 considered to represent strong selective pressure. If the $\text{[math]}$ property is not set by the user, it defaults to a value of 2. The Duel selector is a modification of this selector that permits further lowering of selection pressure.

With this selector the objective value is normally used to compare the fitness of competing solutions, with better objective values corresponding to higher fitness. However, there are techniques for multiple objective optimization and constraint handling that use more complicated criteria than just the objective value. See the section Optimizing Multiple Objectives for further discussion of this topic. You can set your own fitness comparison routine to implement those techniques with the SetCompareRoutine call, and that routine will be used by the tournament selector to compare solution fitness. For a simple single-objective problem you normally do not need to specify a special fitness comparison routine, unless have a secondary objective you might want to use to break a tie.

Duel Selector

This selector has one property, $\text{[math]}$ . It operates in the same manner as the Tournament selector with tournament size 2, except it permits you to reduce selection pressure further by specifying a probability, $\text{[math]}$ , for selecting the most fit solution from the pair. The $\text{[math]}$ property is assigned a default value of 0.8, but you can change it to a value between 0.5 (corresponding to pure random selection) and 1. By default, solution fitness is compared by comparing the solution objective values. However, you can also set your own fitness comparison routine with the SetCompareRoutine call. See the tournament selector for a discussion of when you would need to specify a special fitness comparison routine.

Top of Page