改进贪心算法

前言

贪心算法很容易陷入局部最优，基本无法找到全局最优解，为了得到更好的解，可以考虑在贪心算法求得解的基础上，对解进行进一步改进，接下来将使用爬山法对贪心算法的解进行改进。

爬山法

爬山法是一种局部搜索方法，在有一个解决方案的基础上，我们可以对解决方案进行适当地改变，这种操作也称之为领域操作，如果改变后的解决方案优于改变前的解决方案，则保持这种改变，否则做还原操作。爬山法是典型的局部搜索算法，它只接受好的改变，拒绝坏的改变，这有很大的局限性。与之相对应的是模拟退火算法，他以一定的概率接受坏的改变，可以看作一种全局优化算法。总之，使用爬山法虽然不能保证达到最优，但是能在一定程度上对解作出改进。

求解

使用贪心求解TSP问题，与之前整数规划使用的为同一数据。

import pandas as pd
from ortools.linear_solver import pywraplp# 数据
distance = pd.read_table('distance.txt', header=None, index_col=None)
distance = distance.values.tolist()
city_num = len(distance)# 计算距离
def calculate_distance(record):total_distance = 0for i in range(city_num):total_distance += distance[record[i]][record[i + 1]]return total_distance# 交换位置
def swap(record, i, j):temp = record[i]record[i] = record[j]record[j] = temp# 初始化
traveled = [0 for i in range(city_num)]  # 城市是否访问
traveled_record = [-1 for i in range(city_num)]  # 记录访问城市
traveled_distance = 0  # 遍历总距离
cur_city = -1  # 当前所在城市# 第一个访问的城市为0
traveled[0] = 1
traveled_record[0] = 0
cur_city = 0# 贪婪地选择n-1个城市
for i in range(1, city_num):min_distance = 10000index = -1for j in range(city_num):# 已经访问过的不再访问if traveled[j]:continue# 不能访问当前城市if j == cur_city:continue# 选择一个最小距离作为下一个节点if distance[cur_city][j] < min_distance:min_distance = distance[cur_city][j]index = j# 更新当前节点、城市状态、遍历记录、总距离if index != -1:cur_city = indextraveled[index] = 1traveled_record[i] = indextraveled_distance += min_distanceelse:print('error：no distance smaller than min_distance')
# 回到城市0
traveled_distance += distance[traveled_record[city_num - 1]][0]# 优化:交换城市i和城市j
traveled_record.append(0)
for i in range(1, city_num):for j in range(1, city_num):if i == j:continuepre_distance = calculate_distance(traveled_record)swap(traveled_record, i, j)cur_distance = calculate_distance(traveled_record)if pre_distance < cur_distance:swap(traveled_record, i, j)# 输出
print('total length = ', calculate_distance(traveled_record))
print('the travel order is:')
for i in range(len(traveled_record)):print(traveled_record[i])

结果

求解结果为1034，GAP=（1034-937）/ 937 = 10.4%，与贪心算法的18%的GAP相比，还是有了一定的改进。

total length =  1034
the travel order is:
0
14
13
12
11
10
9
8
6
7
15
18
19
17
16
20
21
25
22
23
24
2
4
5
3
1
0Process finished with exit code 0

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！