65.9K
CodeProject 正在变化。 阅读更多。
Home

C# 中的粒子群优化器

George Swan
starIconstarIconstarIconstarIconstarIcon

5.00/5 (17投票s)

2016年9月7日

CPOL

5分钟阅读

viewsIcon

31133

downloadIcon

1329

一种人工生命算法，通过让实体群在各种可能的解决方案中飞行来尝试解决问题，其中每个实体都受到群体其他成员表现的指导

引言

粒子群优化器 (PSO) 是一个问题求解算法，于 1995 年首次由 Jim Kennedy 和 Russ Eberhart 提出。它最初用于模拟鸟群的运动。基本思想是让一组（群体）问题求解实体（粒子）在问题所有可能解的范围内移动（飞行）。这个范围被称为问题空间。粒子在问题空间内的移动具有随机分量，但主要受三个因素的指导。

  1. 粒子的当前位置
  2. 粒子找到的最佳位置（称为个体最佳或 pBest）
  3. 种群中找到的最佳位置（称为全局最佳或 gBest）

粒子群优化分步详解

举个例子，问题是找出方程 (X*X)-(Y*Y) 在 X 和 Y 为 0 到 10 之间的整数时的最小值。算法将遵循以下执行路径。

  1. 用 0-10 范围内的随机 X 和 Y 值初始化粒子。
  2. 通过评估当前 X 和 Y 值下的方程来确定粒子的适应度。
  3. 根据粒子的个体最佳适应度和全局最佳适应度值更新每个粒子的位置。
  4. 要么，在达到预设的适应度值或设定的迭代次数后终止，或者重复步骤 2 和 3。

Rosenbrock 函数

Rosenbrock 函数常被用作优化器的测试。由于它是多维的且具有许多局部最小值，因此很难找到最小值。在选择 合适的测试函数 时，需要牢记优化器有一个内置的偏向。它更容易找到位于问题空间中心或边缘的解。

关键优化公式分步解析

阶段 1

更新每个维度的粒子速度，在这个例子中，就是 X 和 Y。速度是位置变化的量。

vid=vid*W+C1*rand(pid-xid)+C2*Rand(pgd-xid)

其中

  • vid 是当前速度，
  • W, C1, C2 是常数。常数的近似值为 C1=C2=1.4 W=0.7
  • Rand 和 rand 是两个随机生成的双精度浮点数，值 >=0 且 <1
  • xid 是当前位置，pid 是个体最佳位置，pgd 是全局最佳位置。

阶段 2

通过将新速度加到当前位置来更新当前位置。

xid=xid+vid

就这样。没有变异或新粒子的生成。它只是一个半随机搜索过程，通过种群成员之间的信息交换进行引导。

近期改进

算法的现代变种使用局部最佳位置而不是全局最佳位置。这倾向于确保对问题空间更好的探索，并防止过快地收敛到某个区域最小值。每个粒子都有一个固定的、重叠的信息源集合，从中得出其局部最佳位置。粒子以环状结构相互连接。例如，在一个有 6 个粒子的种群中，从 A 到 F，信息源数量设置为两个，粒子 A 将由粒子 F 和 B 提供信息。粒子 B 将由粒子 A 和 C 提供信息，粒子 F 将由粒子 E 和 A 提供信息。另一种变种是拥有离散的信息源组，并在全局最佳值没有变化的固定数量的迭代后重新组织它们。这种变种使得所有组可以在不同的线程上并发优化，并在没有改进的情况下经过设定的时期数后重新分配。

保持粒子在问题空间内

粒子有可能飞出问题空间，例如，X 可能会获得大于 10 的值。有几种方法可以处理这种情况。最简单的方法是让它们飞出去，但不允许逃逸的粒子更新 pbest 或 lbest 位置。在 pbest 和 lbest 的影响下，粒子将被拉回正确的范围内。

代码

Particle 类具有以下构造函数。

    public Particle(int dimensions,Func<double[], double> errorFunc,
                    ParticleManager particleManager)
        {
            this.Dimensions = dimensions;
            this.particleManager = particleManager;
            this.errorFunc = errorFunc;
            this.Initialize();               
        }

要解决的问题作为 Func<double[], double> 传入。它返回一个算法将尝试最小化的误差值。double[] 包含函数的所有参数（维度）。ParticleManager 类处理数学运算。

  public double[] UpdateVelocity(IParticle particle, double[] bestLocalPosition)
        {
            var newVelocity = new double[particle.Velocity.Length];
            for (int j = 0; j < particle.Velocity.Length; ++j) // each component 
                                                               // of the velocity
            {
                newVelocity[j] = (this.psoAttributes.W * particle.Velocity[j])
                                 + (this.psoAttributes.C1 * 
                                    this.randomFactory.NextRandomDouble()
                                    * (particle.BestPosition[j] - particle.Position[j]))
                                 + (this.psoAttributes.C2 * 
                                    this.randomFactory.NextRandomDouble()
                                    * (bestLocalPosition[j] - particle.Position[j]));
            }
            newVelocity.CopyTo(particle.Velocity, 0);
            return particle.Velocity;
        }
        
  public double[] UpdatePosition(IParticle particle)
        {
            var newPosition = new double[particle.Position.Length];
            for (int j = 0; j < particle.Position.Length; ++j)
            {
                double newPositionJ = particle.Position[j] + particle.Velocity[j];

                newPosition[j] = newPositionJ;
            }
            newPosition.CopyTo(particle.Position, 0);
            return particle.Position;
        }

Optimize 函数相当直观。连续的 static epoch 数量用于在没有改进的情况下提供提前退出。优化器的属性在 app.config 文件中设置。

     public double[] Optimize()
        {
            int epoch = 0;
            int staticEpochs = 0;
            while (epoch < this.psoAttributes.MaxEpochs && 
                   staticEpochs < psoAttributes.MaxStaticEpochs)
            {
                bool isErrorImproved = false;
                foreach (IParticle particle in this.Swarm)
                {
                    double error = particle.OptimizePosition();

                    if (error < this.BestGlobalError)
                    {
                        particle.Position.CopyTo(this.BestGlobalPosition, 0);
                        this.BestGlobalError = error;
                        isErrorImproved = true;
                        staticEpochs = 0;
                    }
                }
                if (!isErrorImproved)
                {
                    staticEpochs++;
                }
            
                epoch++;
            }
            return this.BestGlobalPosition;
        }

  public double UpdateErrorValues()
        {
           if(this.particleManager.CheckIsInRange(this.Position))
             {
              double newError = this.particleManager.CalculateError
                                (this.Position,this.errorFunc);
               if (newError < this.BestError )
                {
	
                this.Position.CopyTo(this.BestPosition, 0);
                this.BestError = newError;
                }
               this.Error = newError;
           }
            return this.BestError;
        }

示例应用程序

示例控制台应用程序尝试优化四个常用的测试函数。

  1. Beale 函数。解位于 xd[0]=3 xd[1]=0.5
  2. Rosenbrock 函数。解位于 xd[0]=1 xd[1]=1
  3. Sphere 函数。解位于 xd[0]=0 xd[1]=0 xd[2]=0 xd[3]=0
  4. Griewank 函数。解位于 xd[0]=0 xd[1]=0 xd[2]=0 xd[3]=0

结论

粒子群优化器是众多采用人工智能形式来解决问题的算法集合中的一个有用补充。它们特别擅长找到使用多个、连续可变值的问题的解决方案。但它们也可以改编来解决离散值问题，例如 旅行商问题，正如我希望在未来的文章中能够展示的那样。

参考文献

历史

  • 2016 年 9 月 7 日：初始版本
© . All rights reserved.