介绍
粒子群优化器，作为一种使用人工智能来解决问题的方式，在解多元、恒变的方程式方面有很大的优势。在本文中我们主要讲的是通过修改算法来解决一些问题，例如使用离散固定值作为参数的旅行商问题。
背景
在之前的一些文献中，PSO粒子群优化器（Particle Swarm Optimizers）已经得到了比较详细的阐述。如在先前那篇文章中所描述的，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.7 Rand和rand是两个随机生成的值，都满足0<=Rand/rand<1 xid是当前位置，pid是个人最佳位置，pgd是全局最佳位置。然后通过向其添加新的速度来更新位置。xid=xid Vid.。此公式适用于该职位的每个维度。
旅行商问题。
旅行商问题描述的是以为旅行社是那个人需要找到一条能够经过所有目的点一次并且回到出发原点的最短的路径问题。这不是一个特别学术化的练习，在接线图和印刷电路板的设计中也会出现类似的情况。现在已经有许多关于如何使用PSO来解决这个问题的论文。本文所使用的方法是基于一篇由Keivan Borna和Razieh Khezri所编写的一篇论文，名为A combination of genetic algorithm and particle swarm optimization method for solving traveling salesman problem.
使用PSO方法来更新推销员的路线。
正如我们所看到的，粒子的新位置受到三个因素的不同程度的影响。它们是粒子现在的位置，以前的最佳位置和它在该组中最佳的位置。推销员的路线可以分为三个部分进行更新，每个部分的大小由该部分的相对强度决定。这些部分可以连接在一起形成一个更新的路线。但这种方法存在一个问题就是城市只能被列入一次，这可能包含已经在之前的路线部分列出的城市。所以需要有一个机制来确保每个城市都被加入到这个路线中，并且在这个过程中没有任何一个城市重复。
在上图中，从当前路线选择的部分是6,3,5。这些城市被添加到新的路线。个人最佳路线选择了第1,3,2部分。3已经被添加过了，所以只有城市1和2被添加。本地最佳路线选定了第7,3。然而城市3已经被添加，所以只有城市7被选中。最后，未被选中的两个城市，即城市0和城市4，按照它们出现在当前路线中的顺序被添加到新路线。
添加的城市的选择通过使用BitArray会更加方便。一个BitArray用作可用性掩码，所有的位最初设置为true。另一个BitArray被用作要添加的片段的选择掩码。为了说明这一点，请考虑添加当前分段后的情况。
示例应用程序。
随机数生成。
该应用程序产生大量的随机数，所以它是值得期待找到最好的随机数发生器（RNG）。经过大量的研究，我发现System.Random比大多数方法要好。
城际查找表。
为了找到两个城市之间的距离，应用程序使用二维矩阵形式的查找表。例如，为了得到城市A和城市B之间的距离。查找城市A的行和城市B的列。在行和列的交点处给出距离。该表是以Indexer的形式实现的，所以它实际上变成了一个只读的二维数组。有人认为，由于表是由多个对象共享的，所以它最好是恒定不变的
代码语言：javascript复制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);
}
}
}实现
示例应用程序将swarm作为一个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 每个群组优化的次数=30000 群组中线人的数量 = 8 重新分组之前的静态时期数= 250 权重W = 0.7； C1 = 1.4； C2 = 1.4
结果 找到正确解= 7 最高错误率= 6％ 平均误差= 2％ 1个群组的优化时间= 1分30秒。
结论
粒子群优化器可用于通过多次重复简单的算法来解决高度复杂的问题。
pidswarmpidswarm
