使用粒子群优化器解决旅行商问题
4.81/5 (11投票s)
一种将粒子群优化器应用于解决旅行商问题的方法。
引言
粒子群优化器采用一种人工智能形式来解决问题。它特别擅长找到使用多个连续可变值的函数。本文旨在修改该算法以解决使用离散、固定值的旅行商问题。
背景
先前的一篇文章讨论并演示了粒子群优化器 (PSO)。正如该文中所述，基本思想是将一组解决问题的实体（粒子）在问题所有可能解的范围内移动（飞行）。这个范围被称为问题空间。粒子在问题空间内的运动包含一个随机分量，但主要由三个因素引导。
- 粒子的当前位置。
- 粒子找到的最佳位置，称为个人最佳或
pBest。 - 群体中找到的最佳位置，称为全局最佳或
gBest。
该算法的现代变体使用局部最佳位置而不是全局最佳位置。这倾向于确保更好地探索问题空间，并防止过快地收敛到某个区域最小值。在这些变体中，群体被划分为称为信息员的粒子组。组内的每个成员之间交换信息，以确定该组的局部最佳位置。如果达到一定迭代次数而全局最佳值没有改变，粒子将被重新组织成新的组。
原始 PSO 公式
处理连续可变值的公式是：
Vid=vid*W+C1*rand(pid-xid)+C2*Rand(pgd-xid)
其中
vid是当前速度，Vid是新速度。在这种情况下，速度是位置改变的量。W、C1、C2是常数。常数的近似值为C1=C2=1.4 W=0.7Rand和rand是两个随机生成的双精度数，>=0且<1xid是当前位置，pid是个人最佳位置，pgd是全局最佳位置。然后通过将新速度加到当前位置来更新位置。xid=xid+Vid。此公式应用于位置的每个维度。
旅行商问题
问题在于找到销售员在一次访问路线上的所有城市并返回出发点所需的最短距离。这并非完全是学术练习。在布线图和印刷电路板的设计中也存在类似的情况。这是一个有大量标准城市列表示例的著名问题。已经有很多论文讨论了如何使用 PSO 来解决这个问题。这里使用的方法基于一篇题为《A combination of genetic algorithm and particle swarm optimization method for solving traveling salesman problem.》的文章，作者是 Keivan Borna 和 Razieh Khezri。
使用 PSO 更新销售员的路线
正如我们所见，粒子的新位置在不同程度上受到三个因素的影响。它们是粒子当前的最佳位置、其之前的最佳位置以及其所在组中找到的最佳位置。销售员的路线可以通过将其划分为三个部分来更新，每个部分对应一个因素，每个部分的长度由该部分的相对强度决定。然后可以将这些部分连接起来形成一条更新的路线。但这种方法存在一个问题。城市只能列出一次，并且部分可能包含已经在先前路线部分中列出的城市。因此，需要一种机制来确保每个城市都被添加到路线中，并且在过程中没有重复的城市。
在上图中，从当前路线选择的片段是 6,3,5。这些城市被添加到新路线中。个人最佳路线选择了片段 1,3,2。片段 3 已经被添加，所以只添加了城市 1 和 2。局部最佳路线选择了片段 7,3。城市 3 已经被添加，所以只选择了城市 7。最后，未被选中的两个城市，即城市 0 和 4，按照它们在当前路线中出现的顺序添加到新路线中。
通过使用 BitArrays 来方便地选择要添加的城市。一个 BitArray 用作可用性掩码，所有位最初都设置为 true。另一个 BitArray 用作要添加的片段的选择掩码。为了说明这一点，请考虑添加当前片段后的情况。
示例应用程序
随机数生成
应用程序生成大量随机数，因此值得寻找最佳随机数生成器 (RNG)。经过大量研究，我发现 System.Random 与任何生成器一样好，甚至比大多数生成器都好。如果您有兴趣探索 RNG 的质量，这里有一个链接 这里 指向用 C# 编写的 Diehard 系列 15 个测试。出于某种原因，我无法运行测试 2，也许是我缺少了样本数据所需的 8000 万位。
城际查找表
为了找到两个城市之间的距离，该应用程序使用二维矩阵形式的查找表。例如，要获取城市 A 和城市 B 之间的距离。查找城市 A 的行和城市 B 的列。距离在行和列的交叉处给出。该表以 索引器 的形式实现，使其实际上成为一个只读的二维数组。考虑到该表由多个对象共享，最好使其不可变。
public class LookUpTable<T> : ILookUpTable<T>
{
public LookUpTable(T[,] arr)
{
this.arr = arr;
}
private readonly T[,] arr;
// The indexer allows the use of [,] operator.
public T this[int r, int c]
{
get
{
return arr[r, c];
}
}
public int RowCount
{
get
{
return arr.GetLength(0);
}
}
public int ColCount
{
get
{
return arr.GetLength(1);
}
}
}
实现
示例应用程序实现了一个 TspParticle 对象数组作为粒子群。它使用 SwarmOptimizer 来优化粒子群。优化器的属性，例如粒子群大小和迭代次数，从 app.config 文件中读取。
public int Optimize(ITspParticle[] swarm, PsoAttributes psoAttributes)
{
this.BestGlobalItinery = swarm[0].CurrentRoute.Clone();
int[] particleIndex = this.InitArray(psoAttributes.SwarmSize);
int epoch = 0;
int staticEpochs = 0;
while (epoch < psoAttributes.MaxEpochs)
{
bool isDistanceImproved = false;
foreach (ITspParticle particle in swarm)
{
double distance = particle.Optimize(psoAttributes);
if (distance < this.BestGlobalItinery.TourDistance)
{
particle.CurrentRoute.CopyTo(this.BestGlobalItinery);
isDistanceImproved = true;
this.consoleWriter.WriteDistance(distance);
}
}
if (!isDistanceImproved)
{
staticEpochs++;
if (staticEpochs == psoAttributes.MaxStaticEpochs)
{
this.UpdateInformers(swarm, particleIndex,
psoAttributes.MaxInformers);
staticEpochs = 0;
}
}
epoch++;
}
return (int)this.BestGlobalItinery.TourDistance;
}
每个粒子都包含指向其 CurrentRoute、PersonalBestRoute 和 LocalBestRoute 的引用，形式为整数数组，其中包含要访问的城市的顺序，最后一个列出的城市链接回第一个城市。路线使用 ParticleOptimizer 进行更新。
public int[] GetOptimizedDestinationIndex(
IRoute currRoute,
IRoute pBRoute,
IRoute lBRoute,
PsoAttributes psoAttribs)
{
//update all the velocities using the appropriate PSO constants
double currV = routeManager.UpdateVelocity(currRoute, psoAttribs.W, 1);
double pBV = routeManager.UpdateVelocity
(pBRoute, psoAttribs.C1, randomFactory.NextRandomDouble());
double lBV = routeManager.UpdateVelocity
(lBRoute, psoAttribs.C2, randomFactory.NextRandomDouble());
double totalVelocity = currV + pBV + lBV;
//update the Segment size for each Route
currRoute.SegmentSize =
routeManager.GetSectionSize(currRoute, currV, totalVelocity);
pBRoute.SegmentSize = routeManager.GetSectionSize(pBRoute, pBV, totalVelocity);
lBRoute.SegmentSize = routeManager.GetSectionSize(lBRoute, lBV, totalVelocity);
return routeManager.AddSections(new[] { lBRoute, pBRoute, currRoute });
}
RouteManager 负责将 CurrentRoute、PersonalBestRoute 和 LocalBestRoute 的片段组合起来形成新的 CurrentRoute。
//updates a particle's velocity.
//The shorter the total distance, the greater the velocity
public double UpdateVelocity(IRoute particleItinery,
double weighting, double randomDouble)
{
return (1 / particleItinery.TourDistance) * randomDouble * weighting;
}
// Selects a section of the route with a length proportional to the particle's
// relative velocity.
public int GetSectionSize(IRoute particleItinery,
double segmentVelocity, double totalVelocity)
{
int length = particleItinery.DestinationIndex.Length;
return Convert.ToInt32
(Math.Floor((segmentVelocity / totalVelocity) * length));
}
最后，RouteManager 使用 RouteUpdater 来处理更新路线的构建。
//sets the selected BitArray mask so that
//only cities that have not been added already are available
//pointer is set to the start of the segment
public void SetSelectedMask(int pointer, IRoute section)
{
int p = pointer;
this.SelectedMask.SetAll(false);
// foreach city in the section set the appropriate bit
// in the selected mask
for (int i = 0; i < section.SegmentSize; i++)
{
//set bit to signify that city is to be added if not already used
this.SelectedMask[section.DestinationIndex[p]] = true;
p++;
// p is a circular pointer in that it moves from the end of the route
// to the start
if (p == section.DestinationIndex.Length)
{
p = 0;
}
}
//in the AvailabilityMask, true=available, false= already used
//remove cities from the SelectedMask that have already been added
this.SelectedMask.And(this.AvailabilityMask);
}
//Updates the new route by adding cities, sequentially from the route section
//providing the cities are not already present
public void SetDestinationIndex(int startPosition, IRoute section)
{
int p = startPosition;
for (int i = 0; i < section.SegmentSize; i++)
{
if (this.SelectedMask[section.DestinationIndex[p]])
{
this.destinationIndex[this.destinationIndexPointer] =
section.DestinationIndex[p];
this.destinationIndexPointer++;
}
p++;
if (p == section.DestinationIndex.Length)
{
p = 0;
}
}
//update the City AvailabilityMask
//sets bits that represent cities that have been included to false
this.AvailabilityMask.Xor(this.SelectedMask);
}
测试结果
使用以下参数对 100 个粒子群优化进行了测试
- 测试文件 Pr76DataSet.xml，76 个城市，正确解为 108,159
- 粒子群大小（粒子数量） = 80
- 每个粒子群优化的迭代次数 = 30,000
- 组中的信息员数量 = 8
- 在信息员重新分组之前的静态迭代次数 = 250
- 权重 W=0.7 C1=1.4 C2 =1.4
结果
- 找到的正确解数 = 7
- 最高误差 = 6%
- 平均误差 = 2%
- 1 次粒子群优化的时间 = 1 分 30 秒。
结论
通过对简单算法进行多次重复，可以使用粒子群优化器来解决高度复杂的问题。