import random
import time
import pandas as pd
import numpy as np
import pickle
import datetime
starttime=datetime.datetime.now()
population_size = 100 # Population size
mutation_rate = 0.02 # mutation rate
generations = 10000 # Evolutionary generations
#Create initial population
def create_initial_population():
population = []
cities = list(range(len(distance_matrix)))
cities.remove(m)
for _ in range(population_size):
random.shuffle(cities)
population.append(cities[:]) # Randomly shuffle the order of cities
return population
# Calculate the total distance of the path
def calculate_total_distance(path):
total_distance = 0
for i in range(len(path) - 1):
total_distance + = distance_matrix[path[i]][path[i + 1]]
return total_distance
# Select individuals with higher fitness
def select_parents(population):
population.sort(key=lambda path: calculate_total_distance(path))
return population[:int(0.2 * population_size)]
# Crossover operation
def crossover(parent1, parent2):
start = random.randint(0, len(parent1) - 1)
end = random.randint(start, len(parent1) - 1)
child = parent1[start:end]
missing_cities = [city for city in parent2 if city not in child]
child.extend(missing_cities)
return child
# Mutation operation
def mutate(path):
if random.random() < mutation_rate:
i, j = random.sample(range(len(path)), 2)
path[i], path[j] = path[j], path[i]
return path
# Distance matrix between cities, fill in the distance data of china31 here
distance_matrix=[(0,107,241 ,190 ,124 ,80 ,316 ,76 ,152 ,157 ,283 ,133 ,113 ,297 ,228 ,129 ,348 ,276 ,188 ,150 ,65 ,341 ,184 ,67 ,221 , 169,108,45,167),
(107, 0,148,137, 88,127,336,183,134,95,254,180,101,234,175,176,265,199,182,67,42,278,271,146,251 ,105,191,139,79),
(241,148,0,374,171,259,509,317,217,232,491,312,280,391,412,349,422,356,355,204,182,435,417,292,424 ,116 ,337 ,273 ,77),
(190,137,374,0,202, 234,222,192,248,42,117,287,79,107,38,121,152,86,68,70,137,151,239,135,137 ,242,165,228,205),
(124, 88,171,202, 0,61,392,202,46,160,319,112,163,322,240,232,314,287,238, 155, 65,366,300,175, 307 , 57 ,220, 121 , 97),
(80, 127,259,234,61,0,386,141,72,167,351,55,157,331,272,226,362,296,232,164,85,375,249,147,301 ,118 ,188 , 60, 185),
(316,336,509,222,392,386, 0,233,438,254,202,439,235,254,210,187,313,266,154,282,321, 298,168,249, 95 ,437 ,190 ,314, 435),
(76 ,183 ,317 ,192, 202, 141, 233 , 0 ,213 ,188 ,272, 193, 131 ,302, 233 , 98, 344, 289 ,177, 216, 141, 346 ,108, 57, 190 ,245, 43, 81, 243),
(152,134,217, 248, 46,72,438,213, 0,206,365,89,209,368,286,278,360,333,284,201,111,412,321,221,353 ,72 ,266 ,132 ,111),
; ,161 ,189 ,163),
(283 ,254 ,491 ,117 ,319,351 ,202 ,272 ,365, 159 , 0 ,404 ,176 ,106 , 79 ,161, 165 ,141, 95, 187, 254, 103 ,279 ,215 ,117 ,3 59 ,216, 308 ,322),
(133,180,312,287,112, 55,439,193, 89,220,404,0,210,384,325,279,415,349,285,217,138,428,310,200,354,16 9 ,241,112,238),
(113,101,280,79,163,157,235,131,209, 57,176,210, 0,186,117, 75,231,165, 81, 85, 92, 230, 184, 74,150 ,208, 104, 158, 206),
(297, 234 ,391, 107, 322 ,331 ,254 ,302, 368, 149 ,106 ,384, 186 , 0 , 69 ,191 ,59 , 35 ,125 ,167, 255 , 44 ,309, 245, 169 , 327, 246, 335,288),
(228 ,175, 412, 38 ,240, 272, 210 ,233 ,286, 80 ,79 ,325 ,117 , 69 , 0 ,122 ,122 ,56 , 56 ,108 ,175, 113, 240 ,176 ,125 , 280, 177 ,266, 243),
(129,176, 349, 121, 232, 226, 187, 98,278, 132, 161, 279, 75,191, 122, 0, 244, 178, 66,160, 161,235, 118, 62,92 ,277, 55, 155 ,275),
(348, 265,422,152,314,362,313, 344, 360,193, 165,415,231,59,122,244, 0, 66,178,198,286,77,362,287,228 ,358 ,299 ,380 ,319),
(276, 199,356, 86,287, 296, 266,289, 333, 127,141, 349,165,35,56,178,66,0,112,132,220, 79,296, 232, 181 ,292,233,314,253),
(188 ,182, 355 ,68 ,238 ,232 ,154 ,177 ,284 ,100 ,95 ,285 , 81 ,125 , 56 ,66 ,178 ,112 , 0 ,128 ,167, 169, 179 ,120 , 69 , 283 ,121 ,213 ,281),
(150, 67,204, 70,155, 164, 282,216,201,28, 187,217, 85,167,108,160,198,132,128, 0,88,211,269,159,197 ,172 ,189 ,182 ,135),
(65 ,42, 182 ,137 , 65 , 85 ,321 ,141, 111 , 95 ,254 ,138 ,92 ,255,175 ,161 ,286, 220 ,167 ,88 , 0 ,299 ,229 ,104, 236, 110 , 149, 97, 108),
(341 ,278, 435 ,151 ,366, 375 ,298 ,346 ,412 ,193 ,103, 428, 230 , 44 ,113 ,235 ,77 , 79, 169, 211, 299 , 0 ,353, 289 ,213 ,371 ,290, 379 ,332),
(184, 271 ,417, 239 ,300 ,249 ,168, 108, 321 ,241 ,279 ,310 ,184, 309, 240 ,118, 362, 296 ,179 ,269, 229 ,353 , 0 ,121 ,162 ,345, 80,189, 342),
(67,146, 292, 135,175,147, 249,57,221, 131, 215, 200, 74,245, 176,62,287,232, 120, 159, 104,289,121, 0,154 , 220 , 41 , 93 ,218),
(221 ,251 ,424 ,137, 307 ,301 ,95, 190 ,353 ,169 ,117 ,354 ,150 ,169 ,125 , 92 ,228 ,181 , 69 ,197 ,236 ,213, 162 ,154 , 0 ,352 ,147 ,247 ,350),
(169 ,105, 116 ,242, 57 ,118, 437, 245, 72 ,200 ,359 ,169 ,208 ,327, 280 ,277 ,358 ,292 ,283 ,172 ,110 ,371 ,345 ,220, 352 , 0 ,265 ,178 , 39),
(108, 191, 337 ,165, 220 ,188 ,190 , 43, 266 ,161 ,216 ,241 ,104 ,246, 177 , 55,299, 233 ,121 ,189, 149, 290 ,80 , 41 ,147 , 265 , 0 ,124 ,263),
(45, 139, 273 ,228 ,121 , 60 ,314 , 81 ,132 ,189 ,308, 112 ,158 ,335 ,266 ,155 ,380 ,314 ,213 ,182 , 97 ,379 ,189, 93 ,247 ,178 ,124, 0, 199),
(167 , 79 , 77 ,205 ,97 ,185 ,435 ,243 ,111 ,163 ,322 ,238 ,206 ,288 ,243, 275 ,319 ,253 ,281 ,135 ,108 ,332, 342 ,218, 350 , 39 ,263, 199 , 0)]
# Main loop
# The optimal path for verification (the optimal path imported below is bays29's optimal path that starts at 0 o'clock and does not return to 0 o'clock)
standard_path=[0, 20, 1, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6, 22, 26, 15, 12, 23, 7, 27, 5, 11 , 8, 4, 25, 28, 2]
# Optimum path value for verification
standard_distance=calculate_total_distance(standard_path) #bays29 The optimal path value starting from 0 o'clock and not returning to 0 o'clock is 1882
print("standard_distance",standard_distance)
dt_ms = datetime.datetime.now().strftime('%Y-%m-%d %H:%M:%S.%f') # Date and time including microseconds, source bit quantization
print(dt_ms)
while True:
m= int(input("Please enter the starting node:")) #Please enter 0 for the starting point for pk
if m>=0 and m<=len(standard_path)-2:
break
x=True
while x==True:
population = create_initial_population()
for generation in range(generations):
parents = select_parents(population)
new_population = parents[:]
while len(new_population) < population_size:
parent1, parent2 = random.choices(parents, k=2)
child = crossover(parent1, parent2)
child = mutate(child)
new_population.append(child)
population = new_population
best_path = min(population, key=calculate_total_distance)
best_path.insert(0,m)
best_distance = calculate_total_distance(best_path)
# print("Optimal solution path (excluding starting point):", best_path)
# print("Optimal solution path value (excluding starting point):", calculate_total_distance(best_path))
if best_distance ==standard_distance:
print("Optimal solution path (excluding starting point):", best_path)
print("Optimal solution path value (excluding starting point):", calculate_total_distance(best_path))
endtime0 = datetime.datetime.now()
print(endtime0 - starttime)
if best_distance <standard_distance:
print("Optimal solution path (excluding starting point):", best_path)
print("Optimal solution path value (excluding starting point):", calculate_total_distance(best_path))
endtime0 = datetime.datetime.now()
print(endtime0 - starttime)
x=False
endtime=datetime.datetime.now()
print(endtime-starttime)
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57053 people are learning the system