|
一直关注公众号的小伙伴想必通过蚁群算法通俗讲解(附MATLAB代码)这篇推文已经了解了蚁群算法(ACO)的基本思想。今天在此基础上,我们分析ACO参数对算法性能的影响。
▎实际案例
求解下述标星位置的最短路线,具体位置信息如下所示。
图片
cities = { "Oklahoma City": (392.8, 356.4), "Montgomery": (559.6, 404.8),
"Saint Paul": (451.6, 186.0), "Trenton": (698.8, 239.6),
"Salt Lake City": (204.0, 243.2), "Columbus": (590.8, 263.2),
"Austin": (389.2, 448.4), "Phoenix": (179.6, 371.2),
"Hartford": (719.6, 205.2), "Baton Rouge": (489.6, 442.0),
"Salem": (80.0, 139.2), "Little Rock": (469.2, 367.2),
"Richmond": (673.2, 293.6), "Jackson": (501.6, 409.6),
"Des Moines": (447.6, 246.0), "Lansing": (563.6, 216.4),
"Denver": (293.6, 274.0), "Boise": (159.6, 182.8),
"Raleigh": (662.0, 328.8), "Atlanta": (585.6, 376.8),
"Madison": (500.8, 217.6), "Indianapolis": (548.0, 272.8),
"Nashville": (546.4, 336.8), "Columbia": (632.4, 364.8),
"Providence": (735.2, 201.2), "Boston": (738.4, 190.8),
"Tallahassee": (594.8, 434.8), "Sacramento": (68.4, 254.0),
"Albany": (702.0, 193.6), "Harrisburg": (670.8, 244.0) }
▎ACO算法求解TSP问题Python代码
ACO算法求解TSP问题Python代码如下:
import time
from itertools import chain
from typing import Any, Callable, List, Tuple, Union
import matplotlib.pyplot as plt
from Data import *
import numpy as np
import random
class AntColonySolver:
def __init__(self,
cost_fn: Callable[[Any, Any], Union[float, int]],
time=0, # run for a fixed amount of time
min_time=0, # minimum runtime
timeout=0, # maximum time in seconds to run for
stop_factor=2, # how many times to redouble effort after new new best path
min_round_trips=10, # minimum number of round trips before stopping
max_round_trips=0, # maximum number of round trips before stopping
min_ants=0, # Total number of ants to use
max_ants=0, # Total number of ants to use
ant_count=64, # this is the bottom of the near-optimal range for numpy performance
ant_speed=1, # how many steps do ants travel per epoch
distance_power=1, # power to which distance affects pheromones
pheromone_power=1.25, # power to which differences in pheromones are noticed
decay_power=0, # how fast do pheromones decay
reward_power=0, # relative pheromone reward based on best_path_length/path_length
best_path_smell=2, # queen multiplier for pheromones upon finding a new best path
start_smell=0, # amount of starting pheromones [0 defaults to `10**self.distance_power`]
verbose=False,
):
assert callable(cost_fn)
self.cost_fn = cost_fn
self.time = int(time)
self.min_time = int(min_time)
self.timeout = int(timeout)
self.stop_factor = float(stop_factor)
self.min_round_trips = int(min_round_trips)
self.max_round_trips = int(max_round_trips)
self.min_ants = int(min_ants)
self.max_ants = int(max_ants)
self.ant_count = int(ant_count)
self.ant_speed = int(ant_speed)
self.distance_power = float(distance_power)
self.pheromone_power = float(pheromone_power)
self.decay_power = float(decay_power)
self.reward_power = float(reward_power)
self.best_path_smell = float(best_path_smell)
self.start_smell = float(start_smell or 10 ** self.distance_power)
self.verbose = int(verbose)
self._initalized = False
if self.min_round_trips and self.max_round_trips: self.min_round_trips = min(self.min_round_trips,
self.max_round_trips)
if self.min_ants and self.max_ants: self.min_ants = min(self.min_ants, self.max_ants)
def solve_initialize(
self,
problem_path: List[Any],
) -> None:
### Cache of distances between nodes
self.distances = {
source: {
dest: self.cost_fn(source, dest)
for dest in problem_path
}
for source in problem_path
}
### Cache of distance costs between nodes - division in a tight loop is expensive
self.distance_cost = {
source: {
dest: 1 / (1 + self.distances[source][dest]) ** self.distance_power
for dest in problem_path
}
for source in problem_path
}
### This stores the pheromone trail that slowly builds up
self.pheromones = {
source: {
# Encourage the ants to start exploring in all directions and furthest nodes
dest: self.start_smell
for dest in problem_path
}
for source in problem_path
}
### Sanitise input parameters
if self.ant_count <= 0:
self.ant_count = len(problem_path)
if self.ant_speed <= 0:
self.ant_speed = np.median(list(chain(*[d.values() for d in self.distances.values()]))) // 5
self.ant_speed = int(max(1, self.ant_speed))
### Heuristic Exports
self.ants_used = 0
self.epochs_used = 0
self.round_trips = 0
self._initalized = True
def solve(self,
problem_path: List[Any],
restart=False,
) -> List[Tuple[int, int]]:
if restart or not self._initalized:
self.solve_initialize(problem_path)
### Here come the ants!
ants = {
&#34;distance&#34;: np.zeros((self.ant_count,)).astype(&#39;int32&#39;),
&#34;path&#34;: [[problem_path[0]] for n in range(self.ant_count)],
&#34;remaining&#34;: [set(problem_path[1:]) for n in range(self.ant_count)],
&#34;path_cost&#34;: np.zeros((self.ant_count,)).astype(&#39;int32&#39;),
&#34;round_trips&#34;: np.zeros((self.ant_count,)).astype(&#39;int32&#39;),
}
best_path = None
best_path_cost = np.inf
best_epochs = []
epoch = 0
time_start = time.perf_counter()
while True:
epoch += 1
### Vectorized walking of ants
# Small optimization here, testing against `> self.ant_speed` rather than `> 0`
# avoids computing ants_arriving in the main part of this tight loop
ants_travelling = (ants[&#39;distance&#39;] > self.ant_speed)
ants[&#39;distance&#39;][ants_travelling] -= self.ant_speed
if all(ants_travelling):
continue # skip termination checks until the next ant arrives
### Vectorized checking of ants arriving
ants_arriving = np.invert(ants_travelling)
ants_arriving_index = np.where(ants_arriving)[0]
for i in ants_arriving_index:
### ant has arrived at next_node
this_node = ants[&#39;path&#39;][-1]
next_node = self.next_node(ants, i)
ants[&#39;distance&#39;] = self.distances[this_node][next_node]
ants[&#39;remaining&#39;] = ants[&#39;remaining&#39;] - {this_node}
ants[&#39;path_cost&#39;] = ants[&#39;path_cost&#39;] + ants[&#39;distance&#39;]
ants[&#39;path&#39;].append(next_node)
### ant has returned home to the colony
if not ants[&#39;remaining&#39;] and ants[&#39;path&#39;][0] == ants[&#39;path&#39;][-1]:
self.ants_used += 1
self.round_trips = max(self.round_trips, ants[&#34;round_trips&#34;] + 1)
### We have found a new best path - inform the Queen
was_best_path = False
if ants[&#39;path_cost&#39;] < best_path_cost:
was_best_path = True
best_path_cost = ants[&#39;path_cost&#39;]
best_path = ants[&#39;path&#39;]
best_epochs += [epoch]
if self.verbose:
print({
&#34;path_cost&#34;: int(ants[&#39;path_cost&#39;]),
&#34;ants_used&#34;: self.ants_used,
&#34;epoch&#34;: epoch,
&#34;round_trips&#34;: ants[&#39;round_trips&#39;] + 1,
&#34;clock&#34;: int(time.perf_counter() - time_start),
})
### leave pheromone trail
# doing this only after ants arrive home improves initial exploration
# * self.round_trips has the effect of decaying old pheromone trails
# ** self.reward_power = -3 has the effect of encouraging ants to explore longer routes
# in combination with doubling pheromone for best_path
reward = 1
if self.reward_power: reward *= ((best_path_cost / ants[&#39;path_cost&#39;]) ** self.reward_power)
if self.decay_power: reward *= (self.round_trips ** self.decay_power)
for path_index in range(len(ants[&#39;path&#39;]) - 1):
this_node = ants[&#39;path&#39;][path_index]
next_node = ants[&#39;path&#39;][path_index + 1]
self.pheromones[this_node][next_node] += reward
self.pheromones[next_node][this_node] += reward
if was_best_path:
# Queen orders to double the number of ants following this new best path
self.pheromones[this_node][next_node] *= self.best_path_smell
self.pheromones[next_node][this_node] *= self.best_path_smell
### reset ant
ants[&#34;distance&#34;] = 0
ants[&#34;path&#34;] = [problem_path[0]]
ants[&#34;remaining&#34;] = set(problem_path[1:])
ants[&#34;path_cost&#34;] = 0
ants[&#34;round_trips&#34;] += 1
### Do we terminate?
# Always wait for at least 1 solutions (note: 2+ solutions are not guaranteed)
if not len(best_epochs): continue
# Timer takes priority over other constraints
if self.time or self.min_time or self.timeout:
clock = time.perf_counter() - time_start
if self.time:
if clock > self.time:
break
else:
continue
if self.min_time and clock < self.min_time: continue
if self.timeout and clock > self.timeout: break
# First epoch only has start smell - question: how many epochs are required for a reasonable result?
if self.min_round_trips and self.round_trips < self.min_round_trips: continue
if self.max_round_trips and self.round_trips >= self.max_round_trips: break
# This factor is most closely tied to computational power
if self.min_ants and self.ants_used < self.min_ants: continue
if self.max_ants and self.ants_used >= self.max_ants: break
# Lets keep redoubling our efforts until we can&#39;t find anything more
if self.stop_factor and epoch > (best_epochs[-1] * self.stop_factor): break
# Nothing else is stopping us: Queen orders the ants to continue!
if True: continue
### We have (hopefully) found a near-optimal path, report back to the Queen
self.epochs_used = epoch
self.round_trips = np.max(ants[&#34;round_trips&#34;])
return best_path
def next_node(self, ants, index):
this_node = ants[&#39;path&#39;][index][-1]
weights = []
weights_sum = 0
if not ants[&#39;remaining&#39;][index]: return ants[&#39;path&#39;][index][0] # return home
for next_node in ants[&#39;remaining&#39;][index]:
if next_node == this_node: continue
reward = (
self.pheromones[this_node][next_node] ** self.pheromone_power
* self.distance_cost[this_node][next_node] # Prefer shorter paths
)
weights.append((reward, next_node))
weights_sum += reward
# Pick a random path in proportion to the weight of the pheromone
rand = random.random() * weights_sum
for (weight, next_node) in weights:
if rand > weight:
rand -= weight
else:
break
return next_node
def AntColonyRunner(cities, verbose=False, plot=False, label={}, algorithm=AntColonySolver, **kwargs):
solver = algorithm(cost_fn=distance, verbose=verbose, **kwargs)
start_time = time.perf_counter()
result = solver.solve(cities)
stop_time = time.perf_counter()
if label: kwargs = {**label, **kwargs}
for key in [&#39;verbose&#39;, &#39;plot&#39;, &#39;animate&#39;, &#39;label&#39;, &#39;min_time&#39;, &#39;max_time&#39;]:
if key in kwargs: del kwargs[key]
print(&#34;N={:<3d} | {:5.0f} -> {:4.0f} | {:4.0f}s | ants: {:5d} | trips: {:4d} | &#34;
.format(len(cities), path_distance(cities), path_distance(result), (stop_time - start_time), solver.ants_used,
solver.round_trips)
+ &#34; &#34;.join([f&#34;{k}={v}&#34; for k, v in kwargs.items()])
)
if plot:
show_path(result)
plt.show()
return result
# Solving the Traveling Salesman Problem
results = AntColonyRunner(cities, distance_power=1, verbose=True, plot=True)
Data.py读取位置数据,绘制路线图。
import numpy as np
import math
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
united_states_map = mpimg.imread(&#34;united_states_map.png&#34;)
def show_cities(path, w=12, h=8):
&#34;&#34;&#34;Plot a TSP path overlaid on a map of the US States & their capitals.&#34;&#34;&#34;
if isinstance(path, dict): path = list(path.values())
if isinstance(path[0][0], str): path = [item[1] for item in path]
plt.imshow(united_states_map)
for x0, y0 in path:
plt.plot(x0, y0, &#39;y*&#39;, markersize=15) # y* = yellow star for starting point
plt.axis(&#34;off&#34;)
fig = plt.gcf()
fig.set_size_inches([w, h])
def show_path(path, starting_city=None, w=12, h=8):
&#34;&#34;&#34;Plot a TSP path overlaid on a map of the US States & their capitals.&#34;&#34;&#34;
if isinstance(path, dict): path = list(path.values())
if isinstance(path[0][0], str): path = [item[1] for item in path]
starting_city = starting_city or path[0]
x, y = list(zip(*path))
# _, (x0, y0) = starting_city
(x0, y0) = starting_city
plt.imshow(united_states_map)
# plt.plot(x0, y0, &#39;y*&#39;, markersize=15) # y* = yellow star for starting point
plt.plot(x + x[:1], y + y[:1]) # include the starting point at the end of path
plt.axis(&#34;off&#34;)
fig = plt.gcf()
fig.set_size_inches([w, h])
def polyfit_plot(x, y, deg, **kwargs):
coefficients = np.polyfit(x, y, deg, **kwargs)
poly = np.poly1d(coefficients)
new_x = np.linspace(x[0], x[-1])
new_y = poly(new_x)
plt.plot(x, y, &#34;o&#34;, new_x, new_y)
plt.xlim([x[0] - 1, x[-1] + 1])
terms = []
for p, c in enumerate(reversed(coefficients)):
term = str(round(c, 1))
if p == 1: term += &#39;x&#39;
if p >= 2: term += &#39;x^&#39; + str(p)
terms.append(term)
plt.title(&#34; + &#34;.join(reversed(terms)))
def distance(xy1, xy2) -> float:
if isinstance(xy1[0], str): xy1 = xy1[1]; xy2 = xy2[1]; # if xy1 == (&#34;Name&#34;, (x,y))
return math.sqrt( (xy1[0]-xy2[0])**2 + (xy1[1]-xy2[1])**2 )
def path_distance(path) -> int:
if isinstance(path, dict): path = list(path.values()) # if path == {&#34;Name&#34;: (x,y)}
if isinstance(path[0][0], str): path = [ item[1] for item in path ] # if path == (&#34;Name&#34;, (x,y))
return int(sum(
[ distance(path, path[i+1]) for i in range(len(path)-1) ]
+ [ distance(path[-1], path[0]) ] # include cost of return journey
))
cities = { &#34;Oklahoma City&#34;: (392.8, 356.4), &#34;Montgomery&#34;: (559.6, 404.8),
&#34;Saint Paul&#34;: (451.6, 186.0), &#34;Trenton&#34;: (698.8, 239.6),
&#34;Salt Lake City&#34;: (204.0, 243.2), &#34;Columbus&#34;: (590.8, 263.2),
&#34;Austin&#34;: (389.2, 448.4), &#34;Phoenix&#34;: (179.6, 371.2),
&#34;Hartford&#34;: (719.6, 205.2), &#34;Baton Rouge&#34;: (489.6, 442.0),
&#34;Salem&#34;: (80.0, 139.2), &#34;Little Rock&#34;: (469.2, 367.2),
&#34;Richmond&#34;: (673.2, 293.6), &#34;Jackson&#34;: (501.6, 409.6),
&#34;Des Moines&#34;: (447.6, 246.0), &#34;Lansing&#34;: (563.6, 216.4),
&#34;Denver&#34;: (293.6, 274.0), &#34;Boise&#34;: (159.6, 182.8),
&#34;Raleigh&#34;: (662.0, 328.8), &#34;Atlanta&#34;: (585.6, 376.8),
&#34;Madison&#34;: (500.8, 217.6), &#34;Indianapolis&#34;: (548.0, 272.8),
&#34;Nashville&#34;: (546.4, 336.8), &#34;Columbia&#34;: (632.4, 364.8),
&#34;Providence&#34;: (735.2, 201.2), &#34;Boston&#34;: (738.4, 190.8),
&#34;Tallahassee&#34;: (594.8, 434.8), &#34;Sacramento&#34;: (68.4, 254.0),
&#34;Albany&#34;: (702.0, 193.6), &#34;Harrisburg&#34;: (670.8, 244.0) }
cities = list(sorted(cities.items()))
print(len(cities))
show_cities(cities)
求解结果如下所示:
图片
{&#39;path_cost&#39;: 4118, &#39;ants_used&#39;: 1, &#39;epoch&#39;: 3717, &#39;round_trips&#39;: 1, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 3942, &#39;ants_used&#39;: 86, &#39;epoch&#39;: 9804, &#39;round_trips&#39;: 2, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 3781, &#39;ants_used&#39;: 133, &#39;epoch&#39;: 12887, &#39;round_trips&#39;: 3, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 3437, &#39;ants_used&#39;: 135, &#39;epoch&#39;: 12900, &#39;round_trips&#39;: 3, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 3428, &#39;ants_used&#39;: 138, &#39;epoch&#39;: 13019, &#39;round_trips&#39;: 3, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 3192, &#39;ants_used&#39;: 143, &#39;epoch&#39;: 13339, &#39;round_trips&#39;: 3, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2981, &#39;ants_used&#39;: 193, &#39;epoch&#39;: 15646, &#39;round_trips&#39;: 4, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2848, &#39;ants_used&#39;: 198, &#39;epoch&#39;: 15997, &#39;round_trips&#39;: 4, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2760, &#39;ants_used&#39;: 199, &#39;epoch&#39;: 16030, &#39;round_trips&#39;: 4, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2757, &#39;ants_used&#39;: 216, &#39;epoch&#39;: 16770, &#39;round_trips&#39;: 4, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2662, &#39;ants_used&#39;: 222, &#39;epoch&#39;: 16973, &#39;round_trips&#39;: 4, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2600, &#39;ants_used&#39;: 263, &#39;epoch&#39;: 18674, &#39;round_trips&#39;: 5, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2504, &#39;ants_used&#39;: 276, &#39;epoch&#39;: 19218, &#39;round_trips&#39;: 5, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2442, &#39;ants_used&#39;: 284, &#39;epoch&#39;: 19338, &#39;round_trips&#39;: 5, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2313, &#39;ants_used&#39;: 326, &#39;epoch&#39;: 20982, &#39;round_trips&#39;: 6, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 2226, &#39;ants_used&#39;: 728, &#39;epoch&#39;: 35648, &#39;round_trips&#39;: 12, &#39;clock&#39;: 0}
N=30 | 7074 -> 2240 | 2s | ants: 1727 | trips: 28 | distance_power=1
[(&#39;Albany&#39;, (702.0, 193.6)), (&#39;Hartford&#39;, (719.6, 205.2)), (&#39;Providence&#39;, (735.2, 201.2)), (&#39;Boston&#39;, (738.4, 190.8)), (&#39;Trenton&#39;, (698.8, 239.6)), (&#39;Harrisburg&#39;, (670.8, 244.0)), (&#39;Richmond&#39;, (673.2, 293.6)), (&#39;Raleigh&#39;, (662.0, 328.8)), (&#39;Columbia&#39;, (632.4, 364.8)), (&#39;Atlanta&#39;, (585.6, 376.8)), (&#39;Montgomery&#39;, (559.6, 404.8)), (&#39;Tallahassee&#39;, (594.8, 434.8)), (&#39;Baton Rouge&#39;, (489.6, 442.0)), (&#39;Jackson&#39;, (501.6, 409.6)), (&#39;Little Rock&#39;, (469.2, 367.2)), (&#39;Oklahoma City&#39;, (392.8, 356.4)), (&#39;Austin&#39;, (389.2, 448.4)), (&#39;Phoenix&#39;, (179.6, 371.2)), (&#39;Sacramento&#39;, (68.4, 254.0)), (&#39;Salem&#39;, (80.0, 139.2)), (&#39;Boise&#39;, (159.6, 182.8)), (&#39;Salt Lake City&#39;, (204.0, 243.2)), (&#39;Denver&#39;, (293.6, 274.0)), (&#39;Des Moines&#39;, (447.6, 246.0)), (&#39;Saint Paul&#39;, (451.6, 186.0)), (&#39;Madison&#39;, (500.8, 217.6)), (&#39;Lansing&#39;, (563.6, 216.4)), (&#39;Columbus&#39;, (590.8, 263.2)), (&#39;Indianapolis&#39;, (548.0, 272.8)), (&#39;Nashville&#39;, (546.4, 336.8)), (&#39;Nashville&#39;, (546.4, 336.8)), (&#39;Albany&#39;, (702.0, 193.6))]▎ACO算法性能分析
01 | 当不考虑启发因子,仅考虑信息素时
results = AntColonyRunner(cities, distance_power=0, min_time=30, verbose=True, plot=True)
求解结果如下:
图片
{&#39;path_cost&#39;: 6700, &#39;ants_used&#39;: 1, &#39;epoch&#39;: 6202, &#39;round_trips&#39;: 1, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 6693, &#39;ants_used&#39;: 2, &#39;epoch&#39;: 6522, &#39;round_trips&#39;: 1, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 5986, &#39;ants_used&#39;: 67, &#39;epoch&#39;: 13559, &#39;round_trips&#39;: 2, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 5902, &#39;ants_used&#39;: 391, &#39;epoch&#39;: 50120, &#39;round_trips&#39;: 7, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 5886, &#39;ants_used&#39;: 473, &#39;epoch&#39;: 59009, &#39;round_trips&#39;: 8, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 5683, &#39;ants_used&#39;: 514, &#39;epoch&#39;: 62612, &#39;round_trips&#39;: 9, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 5516, &#39;ants_used&#39;: 591, &#39;epoch&#39;: 72020, &#39;round_trips&#39;: 10, &#39;clock&#39;: 0}
{&#39;path_cost&#39;: 5297, &#39;ants_used&#39;: 648, &#39;epoch&#39;: 77733, &#39;round_trips&#39;: 11, &#39;clock&#39;: 1}
{&#39;path_cost&#39;: 5290, &#39;ants_used&#39;: 671, &#39;epoch&#39;: 79463, &#39;round_trips&#39;: 11, &#39;clock&#39;: 1}
{&#39;path_cost&#39;: 5192, &#39;ants_used&#39;: 684, &#39;epoch&#39;: 80368, &#39;round_trips&#39;: 11, &#39;clock&#39;: 1}
{&#39;path_cost&#39;: 4359, &#39;ants_used&#39;: 707, &#39;epoch&#39;: 83222, &#39;round_trips&#39;: 12, &#39;clock&#39;: 1}
N=30 | 7074 -> 4375 | 1s | ants: 958 | trips: 16 | distance_power=0 stop_factor=1.25
实验结果表明,仅考虑信息素,而不考虑启发因子,求解质量严重下降。
02 | 启发因子距离权重
启发因子距离权重n影响蚂蚁在选择下一节点时“看见”距离的能力,而不仅仅盲目地依赖信息素。接下来将距离权重n取不同值进行实验,验证其对求解质量的影响。
for distance_power in [-2.0, -1.0, 0.0, 0.5, 1.0, 1.25, 1.5, 1.75, 2.0, 3.0, 5.0, 10.0]:
result = AntColonyRunner(cities, distance_power=distance_power, timeout=60)
求解结果如下:
N=30 | 7074 -> 8225 | 1s | ants: 577 | trips: 10 | distance_power=-2.0 timeout=60
N=30 | 7074 -> 7957 | 1s | ants: 577 | trips: 10 | distance_power=-1.0 timeout=60
N=30 | 7074 -> 3947 | 22s | ants: 12439 | trips: 196 | distance_power=0.0 timeout=60
N=30 | 7074 -> 2558 | 7s | ants: 4492 | trips: 72 | distance_power=0.5 timeout=60
N=30 | 7074 -> 2227 | 2s | ants: 1168 | trips: 19 | distance_power=1.0 timeout=60
N=30 | 7074 -> 2290 | 4s | ants: 2422 | trips: 39 | distance_power=1.25 timeout=60
N=30 | 7074 -> 2367 | 1s | ants: 679 | trips: 11 | distance_power=1.5 timeout=60
N=30 | 7074 -> 2211 | 2s | ants: 1412 | trips: 23 | distance_power=1.75 timeout=60
N=30 | 7074 -> 2298 | 7s | ants: 4429 | trips: 70 | distance_power=2.0 timeout=60
N=30 | 7074 -> 2200 | 2s | ants: 1411 | trips: 23 | distance_power=3.0 timeout=60
N=30 | 7074 -> 2232 | 1s | ants: 758 | trips: 12 | distance_power=5.0 timeout=60
N=30 | 7074 -> 2240 | 1s | ants: 577 | trips: 10 | distance_power=10.0 timeout=60
实验结果表明:
1.当n取负数时,鼓励蚂蚁先到更远的节点,因此出现求解结果比随机路线更差的情况。
2.当n=0时,蚂蚁完全依赖信息素选择下一节点。
3.当n=1时,求解质量较好,但是在间隔紧密的节点周围存在一些“循环”路线。
4.当n=1.25~2时,算法收敛更快,求解质量更佳(通常默认n=2)。
5.当n大于等于3时,算法收敛速度过快,导致算法搜索空间缩小,求解质量下降。
03 | 信息素权重
信息素权重影响信息素的相对差异被注意到的能力。接下来将信息素权重取不同值进行实验,验证其对求解质量的影响。
第1轮实验:
for distance_power in [0,1,2]:
for pheromone_power in [-2.0, -1.0, 0.0, 0.5, 1.0, 1.25, 1.5, 1.75, 2.0, 3.0, 5.0, 10.0]:
result = AntColonyRunner(cities, distance_power=distance_power, pheromone_power=pheromone_power, time=0)
print()
第1轮实验求解结果如下:
N=30 | 7074 -> 5477 | 1s | ants: 574 | trips: 10 | distance_power=0 pheromone_power=-2.0 time=0
N=30 | 7074 -> 5701 | 1s | ants: 688 | trips: 11 | distance_power=0 pheromone_power=-1.0 time=0
N=30 | 7074 -> 6039 | 2s | ants: 570 | trips: 10 | distance_power=0 pheromone_power=0.0 time=0
N=30 | 7074 -> 5970 | 2s | ants: 689 | trips: 11 | distance_power=0 pheromone_power=0.5 time=0
N=30 | 7074 -> 5628 | 2s | ants: 573 | trips: 10 | distance_power=0 pheromone_power=1.0 time=0
N=30 | 7074 -> 5246 | 2s | ants: 894 | trips: 15 | distance_power=0 pheromone_power=1.25 time=0
N=30 | 7074 -> 4035 | 13s | ants: 7217 | trips: 114 | distance_power=0 pheromone_power=1.5 time=0
N=30 | 7074 -> 4197 | 9s | ants: 4602 | trips: 73 | distance_power=0 pheromone_power=1.75 time=0
N=30 | 7074 -> 4328 | 3s | ants: 1788 | trips: 29 | distance_power=0 pheromone_power=2.0 time=0
N=30 | 7074 -> 4188 | 1s | ants: 700 | trips: 11 | distance_power=0 pheromone_power=3.0 time=0
N=30 | 7074 -> 5151 | 1s | ants: 577 | trips: 10 | distance_power=0 pheromone_power=5.0 time=0
N=30 | 7074 -> 5278 | 1s | ants: 577 | trips: 10 | distance_power=0 pheromone_power=10.0 time=0
N=30 | 7074 -> 4444 | 1s | ants: 561 | trips: 10 | distance_power=1 pheromone_power=-2.0 time=0
N=30 | 7074 -> 4035 | 1s | ants: 564 | trips: 10 | distance_power=1 pheromone_power=-1.0 time=0
N=30 | 7074 -> 4016 | 1s | ants: 788 | trips: 13 | distance_power=1 pheromone_power=0.0 time=0
N=30 | 7074 -> 2733 | 4s | ants: 1968 | trips: 32 | distance_power=1 pheromone_power=0.5 time=0
N=30 | 7074 -> 2263 | 3s | ants: 2424 | trips: 39 | distance_power=1 pheromone_power=1.0 time=0
N=30 | 7074 -> 2315 | 2s | ants: 1863 | trips: 30 | distance_power=1 pheromone_power=1.25 time=0
N=30 | 7074 -> 2528 | 1s | ants: 1107 | trips: 18 | distance_power=1 pheromone_power=1.5 time=0
N=30 | 7074 -> 2593 | 1s | ants: 615 | trips: 10 | distance_power=1 pheromone_power=1.75 time=0
N=30 | 7074 -> 2350 | 1s | ants: 631 | trips: 10 | distance_power=1 pheromone_power=2.0 time=0
N=30 | 7074 -> 2806 | 1s | ants: 680 | trips: 11 | distance_power=1 pheromone_power=3.0 time=0
N=30 | 7074 -> 3079 | 1s | ants: 577 | trips: 10 | distance_power=1 pheromone_power=5.0 time=0
N=30 | 7074 -> 3087 | 1s | ants: 577 | trips: 10 | distance_power=1 pheromone_power=10.0 time=0
N=30 | 7074 -> 3277 | 1s | ants: 558 | trips: 10 | distance_power=2 pheromone_power=-2.0 time=0
N=30 | 7074 -> 3191 | 1s | ants: 536 | trips: 10 | distance_power=2 pheromone_power=-1.0 time=0
N=30 | 7074 -> 2958 | 2s | ants: 1124 | trips: 19 | distance_power=2 pheromone_power=0.0 time=0
N=30 | 7074 -> 2229 | 4s | ants: 3027 | trips: 49 | distance_power=2 pheromone_power=0.5 time=0
N=30 | 7074 -> 2432 | 1s | ants: 560 | trips: 10 | distance_power=2 pheromone_power=1.0 time=0
N=30 | 7074 -> 2275 | 5s | ants: 4391 | trips: 70 | distance_power=2 pheromone_power=1.25 time=0
N=30 | 7074 -> 2320 | 3s | ants: 2194 | trips: 35 | distance_power=2 pheromone_power=1.5 time=0
N=30 | 7074 -> 2534 | 1s | ants: 778 | trips: 13 | distance_power=2 pheromone_power=1.75 time=0
N=30 | 7074 -> 2233 | 1s | ants: 938 | trips: 15 | distance_power=2 pheromone_power=2.0 time=0
N=30 | 7074 -> 2308 | 1s | ants: 897 | trips: 15 | distance_power=2 pheromone_power=3.0 time=0
N=30 | 7074 -> 2320 | 1s | ants: 645 | trips: 11 | distance_power=2 pheromone_power=5.0 time=0
N=30 | 7074 -> 2653 | 1s | ants: 577 | trips: 10 | distance_power=2 pheromone_power=10.0 time=0
第2轮实验:
for distance_power in [0,1,2]:
for pheromone_power in [-2.0, -1.0, 0.0, 0.5, 1.0, 1.25, 1.5, 1.75, 2.0, 3.0, 5.0, 10.0]:
result = AntColonyRunner(cities, distance_power=distance_power, pheromone_power=pheromone_power, time=0)
print()
第2轮实验求解结果如下:
N=30 | 7074 -> 5842 | 2s | ants: 577 | trips: 10 | distance_power=0 pheromone_power=-2.0 time=0
N=30 | 7074 -> 5897 | 3s | ants: 1080 | trips: 18 | distance_power=0 pheromone_power=-1.0 time=0
N=30 | 7074 -> 5798 | 1s | ants: 574 | trips: 10 | distance_power=0 pheromone_power=0.0 time=0
N=30 | 7074 -> 6059 | 1s | ants: 570 | trips: 10 | distance_power=0 pheromone_power=0.5 time=0
N=30 | 7074 -> 4068 | 7s | ants: 3562 | trips: 57 | distance_power=0 pheromone_power=1.0 time=0
N=30 | 7074 -> 3620 | 3s | ants: 2553 | trips: 41 | distance_power=0 pheromone_power=1.25 time=0
N=30 | 7074 -> 3994 | 5s | ants: 2822 | trips: 45 | distance_power=0 pheromone_power=1.5 time=0
N=30 | 7074 -> 4067 | 3s | ants: 2210 | trips: 35 | distance_power=0 pheromone_power=1.75 time=0
N=30 | 7074 -> 4232 | 3s | ants: 2057 | trips: 33 | distance_power=0 pheromone_power=2.0 time=0
N=30 | 7074 -> 4559 | 2s | ants: 1179 | trips: 19 | distance_power=0 pheromone_power=3.0 time=0
N=30 | 7074 -> 4566 | 1s | ants: 575 | trips: 10 | distance_power=0 pheromone_power=5.0 time=0
N=30 | 7074 -> 5565 | 1s | ants: 577 | trips: 10 | distance_power=0 pheromone_power=10.0 time=0
N=30 | 7074 -> 4377 | 1s | ants: 570 | trips: 10 | distance_power=1 pheromone_power=-2.0 time=0
N=30 | 7074 -> 4459 | 1s | ants: 535 | trips: 10 | distance_power=1 pheromone_power=-1.0 time=0
N=30 | 7074 -> 4269 | 1s | ants: 559 | trips: 10 | distance_power=1 pheromone_power=0.0 time=0
N=30 | 7074 -> 3144 | 1s | ants: 636 | trips: 11 | distance_power=1 pheromone_power=0.5 time=0
N=30 | 7074 -> 2371 | 2s | ants: 1265 | trips: 21 | distance_power=1 pheromone_power=1.0 time=0
N=30 | 7074 -> 2298 | 4s | ants: 2880 | trips: 47 | distance_power=1 pheromone_power=1.25 time=0
N=30 | 7074 -> 2337 | 7s | ants: 4058 | trips: 65 | distance_power=1 pheromone_power=1.5 time=0
N=30 | 7074 -> 2317 | 2s | ants: 1647 | trips: 27 | distance_power=1 pheromone_power=1.75 time=0
N=30 | 7074 -> 2386 | 2s | ants: 808 | trips: 13 | distance_power=1 pheromone_power=2.0 time=0
N=30 | 7074 -> 2434 | 1s | ants: 573 | trips: 10 | distance_power=1 pheromone_power=3.0 time=0
N=30 | 7074 -> 2776 | 1s | ants: 578 | trips: 10 | distance_power=1 pheromone_power=5.0 time=0
N=30 | 7074 -> 3255 | 1s | ants: 577 | trips: 10 | distance_power=1 pheromone_power=10.0 time=0
N=30 | 7074 -> 2748 | 1s | ants: 560 | trips: 10 | distance_power=2 pheromone_power=-2.0 time=0
N=30 | 7074 -> 3224 | 1s | ants: 542 | trips: 10 | distance_power=2 pheromone_power=-1.0 time=0
N=30 | 7074 -> 2958 | 1s | ants: 543 | trips: 10 | distance_power=2 pheromone_power=0.0 time=0
N=30 | 7074 -> 2705 | 2s | ants: 816 | trips: 14 | distance_power=2 pheromone_power=0.5 time=0
N=30 | 7074 -> 2205 | 2s | ants: 1033 | trips: 17 | distance_power=2 pheromone_power=1.0 time=0
N=30 | 7074 -> 2301 | 2s | ants: 1071 | trips: 17 | distance_power=2 pheromone_power=1.25 time=0
N=30 | 7074 -> 2248 | 2s | ants: 1171 | trips: 19 | distance_power=2 pheromone_power=1.5 time=0
N=30 | 7074 -> 2194 | 2s | ants: 1001 | trips: 16 | distance_power=2 pheromone_power=1.75 time=0
N=30 | 7074 -> 2371 | 1s | ants: 575 | trips: 10 | distance_power=2 pheromone_power=2.0 time=0
N=30 | 7074 -> 2338 | 2s | ants: 1310 | trips: 21 | distance_power=2 pheromone_power=3.0 time=0
N=30 | 7074 -> 2371 | 1s | ants: 576 | trips: 10 | distance_power=2 pheromone_power=5.0 time=0
N=30 | 7074 -> 2942 | 1s | ants: 577 | trips: 10 | distance_power=2 pheromone_power=10.0 time=0
第3轮实验:
for distance_power in [0,1,2]:
for pheromone_power in [1.0, 1.1, 1.2, 1.3, 1.4]:
result = AntColonyRunner(cities, distance_power=distance_power, pheromone_power=pheromone_power, time=0)
print()
第3轮实验求解结果如下:
N=30 | 7074 -> 5107 | 1s | ants: 764 | trips: 13 | distance_power=0 pheromone_power=1.0 time=0
N=30 | 7074 -> 3393 | 15s | ants: 8420 | trips: 134 | distance_power=0 pheromone_power=1.1 time=0
N=30 | 7074 -> 3548 | 20s | ants: 12669 | trips: 200 | distance_power=0 pheromone_power=1.2 time=0
N=30 | 7074 -> 4267 | 2s | ants: 831 | trips: 14 | distance_power=0 pheromone_power=1.3 time=0
N=30 | 7074 -> 5194 | 1s | ants: 562 | trips: 10 | distance_power=0 pheromone_power=1.4 time=0
N=30 | 7074 -> 2231 | 3s | ants: 1507 | trips: 25 | distance_power=1 pheromone_power=1.0 time=0
N=30 | 7074 -> 2297 | 4s | ants: 2213 | trips: 36 | distance_power=1 pheromone_power=1.1 time=0
N=30 | 7074 -> 2399 | 5s | ants: 2586 | trips: 41 | distance_power=1 pheromone_power=1.2 time=0
N=30 | 7074 -> 2274 | 3s | ants: 1365 | trips: 22 | distance_power=1 pheromone_power=1.3 time=0
N=30 | 7074 -> 2323 | 2s | ants: 1164 | trips: 19 | distance_power=1 pheromone_power=1.4 time=0
N=30 | 7074 -> 2244 | 3s | ants: 1724 | trips: 28 | distance_power=2 pheromone_power=1.0 time=0
N=30 | 7074 -> 2240 | 3s | ants: 1518 | trips: 25 | distance_power=2 pheromone_power=1.1 time=0
N=30 | 7074 -> 2251 | 3s | ants: 1736 | trips: 28 | distance_power=2 pheromone_power=1.2 time=0
N=30 | 7074 -> 2259 | 1s | ants: 895 | trips: 15 | distance_power=2 pheromone_power=1.3 time=0
N=30 | 7074 -> 2257 | 6s | ants: 4397 | trips: 70 | distance_power=2 pheromone_power=1.4 time=0
实验结果表面:
1.负数使信息素被排斥,但是求解结果仍比随机结果更优。
2.蚂蚁对信息大于1的信息素较为敏感,稍微增加一点就会大幅度改进求解结果,但会增加算法求解时间。
3.通常默认信息素权重取值1.25。
04 | 蚂蚁数量
我们的直觉是蚂蚁数量越大,收敛速度更快,求解质量更好,那么结果究竟是否如此,下面的实验为我们揭晓答案。
for ant_count in range(0,16+1):
AntColonyRunner(cities, ant_count=2**ant_count, time=60)
求解结果如下:
N=30 | 7074 -> 2711 | 60s | ants: 3722 | trips: 3722 | ant_count=1 time=60
N=30 | 7074 -> 2785 | 60s | ants: 6094 | trips: 3047 | ant_count=2 time=60
N=30 | 7074 -> 2228 | 60s | ants: 14719 | trips: 3682 | ant_count=4 time=60
N=30 | 7074 -> 2338 | 60s | ants: 23195 | trips: 2902 | ant_count=8 time=60
N=30 | 7074 -> 2465 | 60s | ants: 27378 | trips: 1714 | ant_count=16 time=60
N=30 | 7074 -> 2430 | 60s | ants: 41132 | trips: 1291 | ant_count=32 time=60
N=30 | 7074 -> 2262 | 60s | ants: 43098 | trips: 676 | ant_count=64 time=60
N=30 | 7074 -> 2210 | 60s | ants: 63140 | trips: 496 | ant_count=128 time=60
N=30 | 7074 -> 2171 | 60s | ants: 68796 | trips: 272 | ant_count=256 time=60
N=30 | 7074 -> 2196 | 60s | ants: 67791 | trips: 134 | ant_count=512 time=60
N=30 | 7074 -> 2203 | 60s | ants: 73140 | trips: 73 | ant_count=1024 time=60
N=30 | 7074 -> 2227 | 60s | ants: 81049 | trips: 41 | ant_count=2048 time=60
N=30 | 7074 -> 2196 | 60s | ants: 73486 | trips: 19 | ant_count=4096 time=60
N=30 | 7074 -> 2210 | 60s | ants: 71547 | trips: 10 | ant_count=8192 time=60
N=30 | 7074 -> 2176 | 60s | ants: 63254 | trips: 5 | ant_count=16384 time=60
N=30 | 7074 -> 2357 | 60s | ants: 33481 | trips: 2 | ant_count=32768 time=60
N=30 | 7074 -> 3490 | 61s | ants: 10391 | trips: 1 | ant_count=65536 time=60实验结果表明:
1.蚂蚁数量在64~16384之间,ACO求解质量较佳。
2.当蚂蚁数量大于32768时,ACO求解质量急剧下降。
▎总结
我们通过这期推文分析了距离权重、信息素权重和蚂蚁数量对ACO性能的影响,初步结论为距离权重通常设为2,信息素权重通常设为1.25,蚂蚁数量取值范围为64~16384。
▎参考
[1]
咱们下期再见
▎近期你可能错过了的好文章:
新书上架 | 《MATLAB智能优化算法:从写代码到算法思想》
优化算法 | 灰狼优化算法(文末有福利)
优化算法 | 鲸鱼优化算法
遗传算法(GA)求解带时间窗的车辆路径(VRPTW)问题MATLAB代码
粒子群优化算法(PSO)求解带时间窗的车辆路径问题(VRPTW)MATLAB代码 |
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有账号?立即注册
×
|