1

我有包含机票价格的大型数据集

CITY_ORIGIN, CITY_DESTINATION, PRICE

我想解决 TSP 问题，即从数组中找到最便宜的旅行CITY_START开始CITY_END并通过最大N城市。CITIES_THROUGH

我正在尝试使用TSP 示例代码使用 DEAP python lib 解决此任务。

如何在 DEAP TSP 示例中冻结第一个和最后一个城镇？

铁

CITY_START = "London"
CITY_END = "Paris"
CITY_THROUGH = ["Amsterdam", "Berlin", "Rome", "Barcelona"]
CITY_MAX = 2

因此，我想限制算法以在此类可能解决方案的子集中找到最便宜的航班：

London -> [CITY_MAX random cities from CITY_THROUGH] -> Paris
4

2 回答 2

0

我一直在研究基于以下内容的 TSP 解决方案的实现：

https://github.com/lmarti/evolutionary-computation-course/blob/master/AEC.03%20-%20Solving%20the%20TSP%20with%20GAs.ipynb

因此，对于我的实现，我有一个初始城市列表，称为“城市”，我将每个人表示为一个索引列表，这些索引对应于初始列表中每个城市的位置。这意味着生成新个体的机制是根据 numpy 的 random.permutation 函数。但有两种情况，一种是起点和终点不固定，所以我们在工具箱中声明机制如下：

toolbox.register("indices", numpy.random.permutation, len(cities))
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

但是，以防万一“城市”初始列表的第一个和最后一个位置是固定的，那么您需要排列除第一个和最后一个之外的其余位置。所以你声明这样的机制：

permutableList = []
for row in range(1, len(cities)-1):
    permutableList.append(row-1)

toolbox.register("indices", numpy.random.permutation, permutableList)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

然后你只需要更改评估函数以包含“城市”初始列表的第一个点和最后一个点，如下所示：

def create_tour(individual):

    listOfLocations = [list(cities)[e+1] for e in individual]
    # Adding first and last points to the tour
    listOfLocations.insert(0, cities[0])
    listOfLocations.append(cities[len(cities)-1])

    return listOfLocations

然后根据 listOfLocations 列表计算距离。

于 2019-01-24T10:48:41.910 回答
0

我建议将您的航班价格数据映射到嵌套字典：

flight_price = {"london": {"paris": 100}}

现在您只需要调整评估功能：

def evalTSP(individual):
    cities = ["london"] + individual + ["paris"]
    price = sum(flight_price[start][end] for start, end in zip(cities, cities[1:]))
    return price,


evalTSP([])
>>> 100
于 2017-03-15T20:32:16.880 回答