Ant colony optimization (ACO) searches for good solutions by simulating ants that leave and follow pheromone trails. Imagine ants crossing two bridges to reach food: ants on the shorter bridge make more trips, strengthening its trail faster and drawing more ants toward it. ACO turns that feedback into a way to explore routes. section 6.1
ACO is useful when there are many possible routes or sequences and finding the best one is difficult. A delivery route, for example, must account for multiple stops and may also face traffic, package, and timing constraints. A useful route is not necessarily made up of the shortest-looking next step at every stop. section 6.11 section 6.7
For a tour of carnival attractions, the search follows a repeating cycle:
- Give every path the same initial pheromone strength, so no path starts with an advantage. A matrix can hold the strength for each pair of attractions. section 6.5
- Start a population of ants at different attractions. Each ant visits the remaining attractions once to complete a tour. section 6.4
- Choose each next stop using both its trail strength and a heuristic—a practical clue, here the distance. Give promising paths higher chances without ruling out less-promising ones. section 6.7
- After the tours, update the trails, account for evaporation, and record the shortest tour found. Repeat until the stopping condition is met, then return that best-found tour. section 6.4
def roulette_wheel_selection(possible_indexes, possible_probabilities):
slices = []
total = 0
for i in range(len(possible_indexes)): #A
start = total #B
end = total + possible_probabilities[i] #B
slices.append([possible_indexes[i], start,
➥end]) #B
total += possible_probabilities[i]
spin = random.random()
for slice_data in slices: #C
attraction_index = slice_data[0]
lower_bound = slice_data[1]
upper_bound = slice_data[2]
if lower_bound <= spin < upper_bound: #D
return attraction_index
return possible_indexes[-1] #E
The Python roulette-wheel selection makes the choice concrete: each available stop receives a slice sized by its probability, and a random spin selects one slice. section 6.7
The same pattern can represent other problems by changing what an ant visits and how a choice is judged. For job scheduling, ants visit tasks in different orders; for image edge detection, they move between pixels. The heuristic must fit the problem rather than always mean distance. section 6.11
