使用粒子群优化器解决旅行商问题（译文）

原文地址：https://www.codeproject.com/Articles/1182794/Solving-the-Travelling-Salesman-Problem-With-a-Par

原文作者：George Swan

译文由本站 robot-v1.0 翻译

前言

A way of adapting a particle swarm optimizer to solve the travelling salesman problem.

一种采用粒子群优化器解决旅行商问题的方法.

• 下载演示-116.2 KB(Download demo - 116.2 KB)

介绍(Introduction)

粒子群优化器采用一种人工智能形式来解决问题.查找使用多个连续可变值的函数的解决方案特别擅长.本文涉及修改算法以解决使用离散的固定值的问题,例如旅行商问题.(The Particle Swarm Optimizer employs a form of artificial intelligence to solve problems. It is particularly good at finding solutions to functions that use multiple, continuously variable, values. This piece is concerned with modifying the algorithm to tackle problems, such as the travelling salesman problem, that use discrete, fixed values.)

背景(Background)

粒子群优化器(PSO)在较早的版本中进行了讨论和演示(Particle Swarm Optimizers (PSO) were discussed and demonstrated in an earlier) 文章(article) .如该文章所述,基本思想是在整个问题的可能解决方案范围内移动(飞行)一组(大量)问题解决实体(粒子).此范围称为问题空间.粒子在问题空间内的运动具有随机分量,但主要受三个因素指导.(. As stated in that piece, the basic idea is to move (fly) a group (swarm) of problem solving entities (particles) throughout the range of possible solutions to a problem. This range is known as the problem space. The movement of particles within the problem space has a random component but is mainly guided by three factors.)

• 粒子的当前位置.(The present position of the particle.)
• 粒子找到的最佳位置,称为"个人最佳"或" pBest".(The best position found by the particle, known as personal best or pBest.)
• 在群体中找到的最佳位置,称为全球最佳或gBest.(The best position found  in the swarm, known a global best or gBest.) 该算法的现代变体使用局部最佳位置而不是全局最佳位置.这倾向于确保更好地探究问题空间,并防止过于迅速地收敛到某个区域的最小值.在这些变体中,群被分为称为告密者的粒子群.在组的每个成员之间交换信息,以确定该组的局部最佳位置.如果经过一定数量的迭代而没有更改全局最佳值,则粒子将被重组为新的组.(Modern variations of the algorithm use a local best position rather than a global best. This tends to ensure better exploration of the problem space and prevents too rapid a convergence to some regional minimal value. In these variations, the swarm is divided into  groups of particles known as informers. Information is exchanged between every member of a group to determine the local best position for that group The particles are reorganised into new groups if a certain number of iterations pass without the global best value changing.)

原始的PSO公式.(The Original PSO Formula.)

处理连续变量值的公式是(The formula for dealing with continuously variable, values is) Vid =vid * W + C1 * rand(pid-xid)+ C2 * Rand(pgd-xid)(Vid=vidW+C1rand(pid-xid)+C2Rand(pgd-xid)*) 哪里(where) **vid(vid)**是当前速度,(is the current velocity and)**影片(Vid)**是新的速度.在这种情况下,速度是位置改变的量.(is the new velocity. The velocity, in this case, is the amount by which the position is changed.) **W,C1,C2(W, C1,C2)**是常数.常数的近似值为C1 =C2 =1.4 W =0.7(are constants. The approximate values for the constants are C1=C2=1.4 W=0.7) **兰德(Rand)**和(and)**兰德(rand)**是两个随机生成的双打> =0和<1(are two randomly generated doubles >=0 and <1) **西德(xid)**是当前位置(is the current position,)**pid(pid)**是个人的最佳职位,(is the personal best position and)**pgd(pgd)**是全球最佳位置.然后通过向其添加新速度来更新位置.(is the global best position. The position is then updated by adding the new velocity to it.)xid =xid + Vid(xid=xid+Vid).此公式适用于头寸的每个维度.(. This formula is applied to each dimension of the position.)

旅行商问题.(The Travelling Salesman Problem.)

问题是找到一个推销员到他的路线上的每个城市只需要一次旅行并回到他始发地的最短距离.这不是完全学术性的练习.在接线图和印刷电路板的设计中也会出现类似情况.这是一个有据可查的问题,其中包含许多标准示例(The problem is to find the shortest distance that a salesman has to travel to visit every city on his route only once and to arrive back at the place he started from. It’s not a totally academic exercise. A similar situation arises in the design of wiring diagrams and printed circuit boards. It is a well-documented problem with many standard example) 城市清单(lists of cities) .有关如何使用PSO解决此问题的论文很多.此处使用的方法基于一篇名为的文章,(. There have been lots of papers written on how to use a PSO to solve this problem. The method used here is based on an article named,) 遗传算法与粒子群算法相结合解决旅行商问题.(A combination of genetic algorithm and particle swarm optimization method for solving traveling salesman problem.) Keivan Borna和Razieh Khezri(By Keivan Borna and Razieh Khezri)

使用PSO更新推销员的路线.(Using a PSO to Update the Salesman’s Route.)

如我们所见,粒子的新位置受到三个因素的不同程度的影响.它们是粒子的当前位置,它的最佳先前位置以及在其组中找到的最佳位置.可以通过将销售人员的路线分为三个部分来更新路线,其中三个因素中的每个因素都由一个部分组成,其中每个部分的大小取决于该部分的相对强度.然后可以将这些部分连接在一起以形成更新的路线.但是这种方法存在问题.城市只能列出一次,并且部分中可能包含先前路线部分中已经列出的城市.因此,需要一种机制来确保将每个城市都添加到路线中,并且在此过程中不会重复任何城市.(As we have seen, the new position of a particle is influenced to varying degrees by three factors. They are, the particle’s present position, its best previous position and the best position found within its group. The salesman’s route can be updated by dividing it into three sections, one for each of the three factors, where the size of each section is determined by that section’s relative strength. The sections can then be joined together to form an updated route. But there is a problem with this approach. Cities can only be listed once and sections may contain cities that have already been listed in a previous route section. So there needs to be mechanism to ensure that every city is added to the route and that no city is duplicated in the process.)

在上图中,从"当前路径"中选择的部分是6,3,5.这些城市已添加到新路线中.个人最佳路线选择了1,3,2部分.选择3已添加,因此仅添加了城市1和2.本地最佳路线已选择第7,3节.已经添加了城市3,因此仅选择了城市7.最后,将未选择的两个城市(城市0和4)按照它们在当前路线中出现的顺序添加到新路线中.(In the diagram above, the section selected from the Current Route is 6,3,5. These cities are added to the new route. The Personal Best Route has the section 1,3,2 selected. Selection 3 has already been added, so only cities 1 and 2 are added. The Local Best Route has section 7,3 selected. City 3 has already been added so only city 7 gets selected. Finally, the two cities that have not been selected, cities 0 and 4, are added to the new route in the order that they appear in the Current Route.) 使用可以方便地选择要添加的城市(The selection of cities to be added is facilitate by using) 位数组.(BitArrays.) 一(One) BitArray 用作可用性掩码,所有位最初都设置为true.另一个(is used as an availability mask with all the bits being set initially to true. Another) BitArray 用作要添加的段的选择掩码.为了说明这一点,请考虑添加"当前细分"后的情况.(is used as a Selection Mask for the segment to be added. To illustrate this, consider the situation after the Current Segment has been added.)

示例应用程序.(The Example Application.)

随机数生成.(Random Number Generation.)

该应用程序会生成许多随机数,因此值得寻找最佳的随机数生成器(RNG).经过大量研究,我发现(The application generates a lot of random numbers so it was worth looking to find the best random number generator (RNG). After a lot of research, I found that) System.Random 比其他都好,也比大多数更好.如果您有兴趣探索RNG的质量,请访问以下链接(was as good as any and better than most. If you are interested in exploring the quality of RNGs, there is a link) 这里(here) 到(to the) 死硬死硬的顽固的(Diehard) 用C#编写的15个测试系列.由于某种原因,我无法运行测试2,也许我比示例数据所需的8000万位少了一点.(series of 15 tests written in C#. For some reason, I couldn’t get test 2 to run, perhaps I was a little short of the 80 million bits required for the sample data.)

城际查询表.(The Intercity Lookup Table.)

要查找两个城市之间的距离,该应用程序使用二维矩阵形式的查找表.例如,要获取城市A和城市B之间的距离.查找城市A的行和城市B的列.在行和列的交点处给出距离.该表以(To find the distance between two cities, the app uses a lookup table in the form of a two dimensional matrix. For example, to get the distance between city A and city B. Look up the row for city A and the column for city B. The distance is given at the intersection of the row and the column. The table was implemented in the form of an) 索引器(Indexer) 因此它实际上变成了只读的二维数组.人们认为,由于表被多个对象共享,因此最好使其不可变(so that it became, in effect, a read-only two dimensional array. It was thought that, as the table was shared by multiple objects, it was best to make it immutable)

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);
            }
        }
    }

实作(Implementation)

该示例应用程序将swarm实现为一组数组(The sample application implements the swarm as an array of) TspParticle 对象.它使用(objects. It uses a) SwarmOptimizer 优化群.可以从app.config文件中读取优化程序的属性,例如群大小和时期数.(to optimize the swarm. The optimizer’s attributes, such as swarm size and number of epochs, are read in from the app.config file.)

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;
       }

每个粒子都包含对其引用(Each particle contains references to its) CurrentRoute ,(,) PersonalBestRoute 和(and) LocalBestRoute 以包含要访问的城市顺序的整数数组的形式,其中列出的最后一个城市链接回到第一个城市.使用以下命令更新路线(in the form of integer arrays containing the order of the cities to be visited, where the last city listed links back to the first city. The routes are updated using a) 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 });
 }

一种(A) RouteManager 负责加入(is responsible for joining the section of the) CurrentRoute ,(,) PersonalBestRoute 和(and) LocalBestRoute 形成新的(to form the new) 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));
}

最后,(Lastly, the) RouteManager 使用一个(uses a) RouteUpdater 处理更新后的路线.(to handle the building of the updated route.)

//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);
}

检测结果(Test Results)

使用以下参数对100个群组优化进行了测试,(A test of 100 swarm optimizations was carried out using the following parameters,) 测试文件Pr76DataSet.xml,76个城市,正确的解决方案为108,159(Test File Pr76DataSet.xml, 76 Cities, Correct Solution is at 108,159) 群大小(粒子数)=80(Swarm Size (number of particles ) =80) 每个群体优化的时代数=30,000(Number of Epochs per swarm optimization =30,000) 一组中的线人数量=8(Number of Informers in a group = 8) 重新组合线人之前的静态时期数=250(Number of Static Epochs before regrouping the informers= 250) 权重W =0.7 C1 =1.4 C2 =1.4(Weightings W=0.7 C1=1.4 C2 =1.4) 结果(Results) 找到正确的解决方案=7(Correct Solutions Found = 7) 最高误差=6%(Highest Error= 6%) 平均误差=2%(Average Error = 2%) 1群优化的时间=1分30秒.(Time for 1 Swarm Optimization = 1 minute 30 seconds.)

结论.(Conclusion.)

通过简单算法的多次重复,粒子群优化器可用于解决高度复杂的问题.(A Particle swarm optimizer can be used to solve highly complicated problems by multiple repetitions of a simple algorithm.)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。