An optimal solution is the solution that performs best according to the criterion used to judge answers to a problem. The criterion depends on the task: a maze may reward the fewest steps, while a knapsack problem may reward the greatest value without exceeding its capacity. A good solution can be useful without being optimal. section 2.3 section 4.2
Treat optimality as a comparison against an explicit evaluation rule:
- Define the goal, such as minimizing distance or maximizing item value. section 2.3 section 4.2
- Compare valid solutions using that criterion rather than judging them by appearance or convenience. section 2.3 section 6.9
- Separate solution quality from computational efficiency: an answer can be better while taking longer to find. section 4.2
- Check whether the method guarantees the best answer or merely searches for an acceptable one. section 4.2
A maze and a knapsack
In a 10-by-10 maze, valid paths reach the goal while avoiding barriers. Recorded attempts take 17, 23, 17, and 15 actions; the 15-action path is the best among those found. In a knapsack problem, the optimal selection maximizes total value under a weight limit. As the number of items grows, exhaustive comparison becomes expensive, so an evolutionary algorithm may find a desirable solution without guaranteeing the one true optimum. section 2.3 section 4.2
Figure 6.11 The ACO algorithm life cycle
Trace how ant-colony optimization repeatedly builds tours, updates pheromone trails, records the best solution, and stops after a chosen number of iterations. section 6.4
