next up previous

4.1.1 Solution Representation and Generation     continued...

For combinatorial, or permutation, optimization problems, the solution representation and generation mechanism(s) will necessarily be problem-specific. For example, in the famous traveling salesman problem (TSP) of finding the shortest cyclical itinerary visiting N cities, the most obvious representation is a list of the cities in the order they are to be visited. The solution generation mechanism(s), or move set, must, obviously, be compatible with the chosen representation. For combinatorial problems, it is common for the move set to permute a small, randomly chosen, part of the solution. For example, the move set suggested by Lin [43] for the TSP makes two types of change: