A permutation is an ordered arrangement of elements in which every element appears exactly once. Order distinguishes a permutation from a combination: changing the sequence produces a different result. Permutations therefore model decisions such as arranging activities, assigning visit sequences, or ordering cities in a route. section 2.1.1
Use permutations when the arrangement itself affects the outcome:
- Classify problems involving sets, combinations, or permutations of integer-valued variables as combinatorial optimization problems. section 2.1.1
- Represent a traveling-salesman tour as the order in which cities are visited. section 9.6
- Distinguish permutations from combinations by asking whether order matters and whether repetition is allowed. section 2.1.1
A permutation as a route
For a traveling-salesman problem, an array of decision variables is converted into a city order by sorting its indices. The route cost sums distances between adjacent cities and then adds the return distance from the final city to the starting city. A particle-swarm optimizer can search for a low-cost permutation across twenty US cities. section 9.6
n_cities = len(city_names) #1
bounds = (np.zeros(n_cities), np.ones(n_cities)*(n_cities-1)) #1
def tsp_distance(position, distance): #2
tour = np.argsort(position) #3
total_distance = distance[0, tour[0]] #4
for i in range(n_cities-1): #4
total_distance += distance[tour[i], tour[i+1]] #4
total_distance += distance[tour[-1], 0] #4
return total_distance
def tsp_cost(x, distance): #5
n_particles = x.shape[0] #5
cost=0 #5
cost = [tsp_distance(x[i], distance) for i in range(n_particles)] #5
return cost #5
Inspect the distance function that turns a particle position into a permutation and evaluates the resulting tour. section 9.6
options = {'w': 0.79, 'c1': 2.05, 'c2': 2.05, 'k': 10, 'p': 2} #1
optimizer = ps.discrete.BinaryPSO(n_particles=100, dimensions=n_cities,
options=options) #2
cost, solution = optimizer.optimize(tsp_cost, iters=150, verbose=True,
distance=distance) #3
tour = np.argsort(solution) #4
city_names_tour = [city_names[i] for i in tour] #4
Route = " → ".join(city_names_tour) #5
print("Route:", Route) #5
print("Route length:", np.round(cost, 3)) #5
#1 Set up the PSO parameters.
#2 Instantiate the PSO optimizer.
#3 Solve the problem.
#4 Convert the best solution to a TSP tour.
#5 Print the best route and its length.
Inspect the optimizer settings, solve step, and conversion of the best position into a named city route. section 9.6
