def ant_colony_optimization(g, verbose=True, iterations = 100, ants_per_iteration = 50, q = 10, degradation_factor = .9, use_inertia = False): best_cycle = best_so_far # can be pre set or set to None best_length = cycle_length(g, best_so_far) #hardcoded instance. Else use None if use_inertia: #this is adding pheromones everywhere if the process stagnates. This did not improve my results and is left off. old_best = None inertia = 0 patience = 100 for iteration in range(iterations): cycles = [traverse_graph(g, random.randint(0, g.nodes -1)) for _ in range(ants_per_iteration)] # could be trivially parallelized if not on Mac through multiprocessing cycles.sort(key = lambda x: x[1]) cycles = cycles[: ants_per_iteration//2] #optionally keep best half. if best_cycle: #elitism cycles.append((best_cycle, best_length)) if use_inertia: old_best = best_length for cycle, total_length in cycles: # pheromone update total_length = cycle_length(g, cycle) if total_length < best_length: best_length = total_length best_cycle = cycle delta = q/total_length i = 0 while i < len(cycle) -1: g.intensity[cycle[i]][cycle[i+1]]+= delta i+=1 g.intensity[cycle[i]][cycle[0]] += delta g.intensity *= degradation_factor if use_inertia and best_cycle: if old_best == best_length: inertia+=1 else: inertia = 0 if inertia > patience: g.intensity += g.intensity.mean() # applying shake return best_cycle