用粒子群优化算法求解旅行商问题

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

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

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

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