旅行推销员问题使用遗传算法

huangapple
go评论103阅读模式
英文:

The Travelling Salesman Problem Using Genetic Algorithm

问题

我尝试调整参数值，但最终距离始终在上限9500左右，从未降至9000以下。我该如何改进以使其适用于我的位置文件？

  1. pop_size = 100  # Increase population size
  2. elite_size = 40  # Try adjusting the elite size
  3. mutation_rate = 0.001  # Experiment with different mutation rates
  4. gen = 500  # You can increase the number of generations
  6. # Consider adjusting the following parameters based on the characteristics of your problem and results:
  7. # - ordered_crossover
  8. # - fit_proportionate_selection
  10. # Example:
  11. # def ordered_crossover_pop(mating_pool, elite_size):
  12. #     ...
  14. # def fit_proportionate_selection(top_pop, elite_size):
  15. #     ...

请尝试更改这些参数，以及调整遗传算法的其他相关函数，以找到更好的解决方案。

英文:

I was looking to learn about AI and found the traveling salesman problem very interesting. I also wanted to learn about genetic algorithms, so it was a fantastic combo. The task is to find the shortest distance traveling from id 1 to each location from the list once and returning to the starting location id 1

Restriction for the problem :

> The location id 1 must be the starting and the ending point
>
> The maximum distance allowed is distance <= 9000
>
> Only max of 250000 fitness calculation is allowed

Code :

  1. import numpy as np
  2. import random
  3. import operator
  4. import pandas as pd
  6. val10 = 0
  7. val9 = 0
  8. class Locations:
  9.     def __init__(self, x, y):
  10.         self.x = x
  11.         self.y = y
  13.     def dist(self, location):
  14.         x_dist = abs(float(self.x) - float(location.x))
  15.         y_dist = abs(float(self.y) - float(location.y))
  16.         # √( (x2 − x1)^2 + (𝑦2 − 𝑦1)^2 )
  17.         dist = np.sqrt((x_dist ** 2) + (y_dist ** 2))
  18.         return dist
  20.     def __repr__(self):
  21.         return "(" + str(self.x) + "," + str(self.y) + ")"
  24. class Fitness:
  25.     def __init__(self, route):
  26.         self.r = route
  27.         self.dist = 0
  28.         self.fit = 0.0
  30.     def route_dist(self):
  31.         if self.dist == 0:
  32.             path_dist = 0
  33.             for i in range(0, len(self.r)):
  34.                 from_location = self.r[i]
  35.                 to_location = None
  36.                 if i + 1 < len(self.r):
  37.                     to_location = self.r[i+1]
  38.                 else:
  39.                     to_location = self.r[0]
  41.                 path_dist += from_location.dist(to_location)
  42.             self.dist = path_dist
  43.         return self.dist
  45.     def route_fittness(self):
  46.         if self.fit == 0:
  47.             self.fit = 1 / float(self.route_dist())
  48.         global val9
  49.         val9 = val9 + 1    
  50.         return self.fit
  53. def generate_route(location_list):
  54.     route = random.sample(location_list, len(location_list))
  55.     return route
  58. def gen_zero_population(size, location_list):
  59.     population = []
  61.     for i in range(0, size):
  62.         population.append(generate_route(location_list))
  63.     return population
  66. def determine_fit(population):
  67.     result = {}
  68.     for i in range(0, len(population)):
  69.         result[i] = Fitness(population[i]).route_fittness()
  70.     global val10
  71.     val10 = val10 + 1
  72.     return sorted(result.items(), key=operator.itemgetter(1), reverse=True)
  75. def fit_proportionate_selection(top_pop, elite_size):
  76.     result = []
  77.     df = pd.DataFrame(np.array(top_pop), columns=["index", "Fitness"])
  78.     df['cumulative_sum'] = df.Fitness.cumsum()
  79.     df['Sum'] = 100*df.cumulative_sum/df.Fitness.sum()
  81.     for i in range(0, elite_size):
  82.         result.append(top_pop[i][0])
  83.     for i in range(0, len(top_pop) - elite_size):
  84.         select = 100*random.random()
  85.         for i in range(0, len(top_pop)):
  86.             if select <= df.iat[i, 3]:
  87.                 result.append(top_pop[i][0])
  88.                 break
  89.     return result
  92. def select_mating_pool(populatoin, f_p_s_result):
  93.     mating_pool = []
  94.     for i in range(0, len(f_p_s_result)):
  95.         index = f_p_s_result[i]
  96.         mating_pool.append(populatoin[index])
  97.     return mating_pool
  100. def ordered_crossover(p1, p2):
  101.     child, child_p1, child_p2 = ([] for i in range(3))
  103.     first_gene = int(random.random() * len(p1))
  104.     sec_gene = int(random.random() * len(p2))
  106.     start_gene = min(first_gene, sec_gene)
  107.     end_gene = max(first_gene, sec_gene)
  109.     for i in range(start_gene, end_gene):
  110.         child_p1.append(p1[i])
  112.     child_p2 = [item for item in p2 if item not in child_p1]
  114.     child = child_p1 + child_p2
  115.     return child
  118. def ordered_crossover_pop(mating_pool, elite_size):
  119.     children = []
  121.     leng = (len(mating_pool) - (elite_size))
  122.     pool = random.sample(mating_pool, len(mating_pool))
  124.     for i in range(0, elite_size):
  125.         children.append(mating_pool[i])
  127.     for i in range(0, leng):
  128.         var = len(mating_pool)-i - 1
  129.         child = ordered_crossover(pool[i], pool[var])
  130.         children.append(child)
  131.     return children
  134. def swap_mutation(one_location, mutation_rate):
  135.     for i in range(len(one_location)):
  136.         if (random.random() < mutation_rate):
  137.             swap = int(random.random() * len(one_location))
  139.             location1 = one_location[i]
  140.             location2 = one_location[swap]
  142.             one_location[i] = location2
  143.             one_location[swap] = location1
  144.     return one_location
  147. def pop_mutation(population, mutation_rate):
  148.     result = []
  150.     for i in range(0, len(population)):
  151.         mutaded_res = swap_mutation(population[i], mutation_rate)
  152.         result.append(mutaded_res)
  153.     return result
  156. def next_gen(latest_gen, elite_size, mutation_rate):
  157.     route_rank = determine_fit(latest_gen)
  158.     selection = fit_proportionate_selection(route_rank, elite_size)
  159.     mating_selection = select_mating_pool(latest_gen, selection)
  160.     children = ordered_crossover_pop(mating_selection, elite_size)
  161.     next_generation = pop_mutation(children, mutation_rate)
  162.     return next_generation
  165. def generic_algor(population, pop_size, elite_size, mutation_rate, gen):
  166.     pop = gen_zero_population(pop_size, population)
  167.     print("Initial distance: " + str(1 / determine_fit(pop)[0][1]))
  169.     for i in range(0, gen):
  170.         pop = next_gen(pop, elite_size, mutation_rate)
  172.     print("Final distance: " + str(1 / determine_fit(pop)[0][1]))
  173.     best_route_index = determine_fit(pop)[0][0]
  174.     best_route = pop[best_route_index]
  175.     print(best_route)
  176.     return best_route
  179. def read_file(fn):
  180.     a = []
  181.     with open(fn) as f:
  182.         [next(f) for _ in range(6)]
  183.         for line in f:
  184.             line = line.rstrip()
  185.             if line == 'EOF':
  186.                 break
  188.             ID, x, y = line.split()
  189.             a.append(Locations(x=x, y=y))
  190.     return a
  193. location_list = read_file(r'path_of_the_file')
  195. population = location_list
  196. pop_size = 100
  197. elite_size = 40
  198. mutation_rate = 0.001
  199. gen = 500
  200. generic_algor(population, pop_size, elite_size, mutation_rate, gen)
  202. print(val10)
  203. print(val9)

Location file with x and y coordinates :

  1. |Locations
  2. |
  3. |52 Locations
  4. |
  5. |Coordinates
  6. |
  7. 1 565.0 575.0
  8. 2 25.0 185.0
  9. 3 345.0 750.0
  10. 4 945.0 685.0
  11. 5 845.0 655.0
  12. 6 880.0 660.0
  13. 7 25.0 230.0
  14. 8 525.0 1000.0
  15. 9 580.0 1175.0
  16. 10 650.0 1130.0
  17. 11 1605.0 620.0 
  18. 12 1220.0 580.0
  19. 13 1465.0 200.0
  20. 14 1530.0 5.0
  21. 15 845.0 680.0
  22. 16 725.0 370.0
  23. 17 145.0 665.0
  24. 18 415.0 635.0
  25. 19 510.0 875.0  
  26. 20 560.0 365.0
  27. 21 300.0 465.0
  28. 22 520.0 585.0
  29. 23 480.0 415.0
  30. 24 835.0 625.0
  31. 25 975.0 580.0
  32. 26 1215.0 245.0
  33. 27 1320.0 315.0
  34. 28 1250.0 400.0
  35. 29 660.0 180.0
  36. 30 410.0 250.0
  37. 31 420.0 555.0
  38. 32 575.0 665.0
  39. 33 1150.0 1160.0
  40. 34 700.0 580.0
  41. 35 685.0 595.0
  42. 36 685.0 610.0
  43. 37 770.0 610.0
  44. 38 795.0 645.0
  45. 39 720.0 635.0
  46. 40 760.0 650.0
  47. 41 475.0 960.0
  48. 42 95.0 260.0
  49. 43 875.0 920.0
  50. 44 700.0 500.0
  51. 45 555.0 815.0
  52. 46 830.0 485.0
  53. 47 1170.0 65.0
  54. 48 830.0 610.0
  55. 49 605.0 625.0
  56. 50 595.0 360.0
  57. 51 1340.0 725.0
  58. 52 1740.0 245.0
  59. EOF

I have tried to tweak the value of the parameters but it has never gone below or be 9000 it is always around the upper 9500 What can I improve to get it to work for my location file?

旅行推销员问题使用遗传算法

答案1

得分: 0

原来一切都很好，微调distance函数和fit_proportionate_selection确保更快的运行时间，从而使测试参数更快。另一个变化是为random()使用固定种子，这样可以在没有太多变量的情况下进行比较。

  1. def fit_proportionate_selection(top_pop, elite_size):
  2.     indices, fitness = zip(*top_pop)
  3.     cumulative_sum = list(it.accumulate(fitness))
  4.     total = cumulative_sum[-1]
  5.     weights = [100*cs/total for cs in cumulative_sum]
  7.     result = list(indices[:elite_size])
  9.     for i in range(len(top_pop) - elite_size):
  10.         select = random.randrange(100)
  11.         for i, weight in enumerate(weights):
  12.             if select <= weight:
  13.                 result.append(top_pop[i][0])
  14.                 break
  15.     return result

从我的代码审查问题中提取的参数：

  1. pop_size = 150, elite_size=50, mutation_rate=0.0005, gen=400
英文:

Turns out everything is fine tweaking the distance function and the fit_proportionate_selection ensures a faster run time which makes testing the parameters faster. The other change is to have a fixed seed for the random() this way the results can be compared without much variant.

  1. def fit_proportionate_selection(top_pop, elite_size):
  2.     indices, fitness = zip(*top_pop)
  3.     cumulative_sum = list(it.accumulate(fitness))
  4.     total = cumulative_sum[-1]
  5.     weights = [100*cs/total for cs in cumulative_sum]
  7.     result = list(indices[:elite_size])
  8.     
  9.     for i in range(len(top_pop) - elite_size):
  10.         select = random.randrange(100)
  11.         for i, weight in enumerate(weights):
  12.             if select &lt;= weight:
  13.                 result.append(top_pop[i][0])
  14.                 break
  15.     return result

Taken from my review question Code review of the same code

The parameters picked where from the comment of the review question:

  1. pop_size = 150, elite_size=50, mutation_rate=0.0005, gen=400

huangapple
  • 本文由 发表于 2023年4月20日 03:45:50
  • 转载请务必保留本文链接：https://go.coder-hub.com/76058279.html
  • genetic-algorithm
  • performance
  • python
  • python-3.x
  • traveling-salesman
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定