测试运行

项目
07/13/2015

细菌觅食优化

James McCaffrey
细菌觅食优化（BFO）是一种迷人的人工智能 (AI) 技术，可以用于查找近似极难或不可能的数字最大化或最小化问题的解决方案。我在本文中描述的 BFO 的版本基于 2002年纸，"仿生学的细菌觅食的分布式优化及控制，"由博士。Kevin Passino。（本文可以通过互联网搜索，找到，但订阅是必需的）。BFO 是一种概率的技术，模型的常见细菌如 E.寻找食物和生殖行为为了解决数值优化问题的大肠杆菌凡有不确定性的有效途径。为您的最佳方式，感受 BFO 是什么，看看这篇文章，我朝就检查图 1 和图 2。

The Rastrigin Function Problem
图 1 Rastrigin 功能问题

Using Bacterial Foraging Optimization
图 2 使用细菌觅食的优化

图 1 是一个图形的 Rastrigin 的功能，通常作为标准基准问题使用，测试优化算法的有效性。目标是找到值的 x 和 y 的最小化功能。你可以看到有很多谷，这是局部极小值的解决方案。然而，有只有一个全球解决方案在 x = 0.0 和 y = 函数的值在哪里 0.0 0.0。

图 2 是 BFO 尝试解决 Rastrigin 功能的截图。该程序设置几个参数，包括模拟细菌（在此示例中的 100）的数目。每一种细菌的立场，表示可能的解决方案。最初，所有的细菌都设置为随机的职位。每个位置都具有相关的成本，它表示 Rastrigin 函数的值。执行主处理循环，不同的细菌会发现先后有更好的解决方案。在处理结束后，找到最佳的解决方案是 0.0002 当 x =-0.0010 和 y = 0.0005 — 极其接近但不是完全的最优解。

我在本文的其余部分中详细解释 BFO 算法和你漫步显示运行的程序图 2。我编码演示计划在 C# 中，但您应该能够很容易适应这里提交给另一种语言如 Visual Basic 代码。NET 或 Windows PowerShell。完整的源代码的程序是可在 archive.msdn.microsoft.com/mag201203TestRun。本文假定您有中级或高级编程技巧与现代的程序语言，但是并不假设你知道任何关于 BFO 或相关的人工智能技术。

真正的细菌行为

E.如细菌大肠杆菌是这个星球上的最成功的生物之一。细菌有半刚性称鞭毛的附肢。当所有鞭毛不断以逆时针方向都旋转时，螺旋桨影响创建和一种细菌会游更多或少直方向。

细菌往往会游泳时他们正在努力改进在某种意义上，例如，当发现越来越多的养分渐变，例如。当所有的鞭毛旋转顺时针方向时，一种细菌会快速滚落和指向新的方向。细菌容易跌倒时遇到的有毒的物质，或当他们在不提高的渐变。细菌繁殖，约每隔 20 分钟左右通过无性划分成完全相同的两个女儿。更健康的细菌往往更比不太健康的细菌繁殖。

整体的程序结构

整体的程序结构，对于 BFO 演示中列出图 3。

图 3 整体 BFO 程序结构

using System;
namespace BacterialForagingOptimization
{
  class BacterialForagingOptimizationProgram
  {
    static Random random = null;
    static void Main(string[] args)
    {
      try
      {
        int dim = 2;
        double minValue = -5.12;
        double maxValue = 5.12;
        int S = 100;
        int Nc = 20;
        int Ns = 5;
        int Nre = 8;
        int Ned = 4;
        double Ped = 0.25;
        double Ci = 0.05;
        random = new Random(0);
        // Initialize bacteria colony
        // Find best initial cost and position
        int t = 0;
        for (int l = 0; l < Ned; ++l) // Eliminate-disperse loop
        {
          for (int k = 0; k < Nre; ++k) // Reproduce-eliminate loop
          {
            for (int j = 0; j < Nc; ++j) // Chemotactic loop
            {
              // Reset the health of each bacterium to 0.0
              for (int i = 0; i < S; ++i)
              {
                // Process each bacterium
              }
              ++t;
             }
            // Reproduce healthiest bacteria, eliminate other half
          }
          // Eliminate-disperse
        }
        Console.WriteLine("\nBest cost found = " + bestCost.ToString("F4"));
        Console.Write("Best position/solution = ");
        ShowVector(bestPosition);
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    } // Main
    static double Cost(double[] position) { ...
}
  }
  public class Colony // Collection of Bacterium
  {
    // ...
public class Bacterium : IComparable<Bacterium>
    {
      // ...
}
  }
} // ns

我用 Visual Studio 创建 C# 控制台应用程序命名为 BacterialForagingOptimization。重命名为 BacterialForagingOptimizationProgram.cs 的 program.cs，然后从该文件，并删除所有模板生成使用语句除外的 System 命名空间的引用。

我声明类范围随机对象命名随机； BFO 是一种概率算法，你很快就会看到。我主要方法内声明的几个关键变量。 Dim 变量是问题中的维度数。因为在此示例中的目标是找到 x 和 y 的 Rastrigin 函数，设置 2 昏暗。 MinValue 和 maxValue 变量建立任意的 x 和 y 的限制。变量 S 是细菌的数量。我用稍有非描述性的变量名，如 S 和数控因为这些都用在研究文章中，您可以更轻松地的名称使用该文章作为参考。

可变 Nc 是所谓的趋化步骤的数目。你可以把它作为一个计数器，表示每个细菌的寿命。可变 Ns 是一种细菌会游在同一方向的最大次数。可变 Nre 是复制步骤的数目。你能想到的这代的细菌的数量。可变 Ned 是散布步骤的数目。现在然后 BFO 算法随机散至新的位置，模拟真实的细菌对外部环境的影响的一些细菌。可变 Ped 是细菌的特定被分散的概率。可变 Ci 是基本游泳长度为每个细菌。时游泳、细菌将 Ci 不超过任何一个步骤。变量 t 是时间计数器跟踪 BFO 进度。因为 BFO 是相对较新，非常了解甚少使用 BFO 参数的值不同的影响。

主要的 BFO 算法处理包括几个嵌套循环。不像大多数的人工智能算法如由单个时间计数器控制的遗传算法，BFO 是由多个循环计数器控制的。

程序使用静态的成本函数。这是你想的最小化或最大化的功能。在此示例中成本函数是刚刚的 Rastrigin 函数。输入是数组的两倍，代表一种细菌的位置，它反过来表示可能的解决方案。在此示例中成本函数定义如下：

double result = 0.0;
for (int i = 0; i < position.Length; ++i) {
  double xi = position[i];
  result += (xi * xi) - (10 * Math.Cos(2 * Math.PI * xi)) + 10;
}
return result;

你可以通过互联网搜索，找到有关 Rastrigin 函数的详细信息，但问题是成本函数接受一种细菌的位置，并返回的值，你想最小化或最大化。

细菌和殖民地的类

BFO 程序定义的殖民地类，该类的细菌的集合，使用嵌套的细菌类，定义单个细菌。嵌套的细菌类列在图 4。

图 4 细菌类

public class Bacterium : IComparable<Bacterium>
{
  public double[] position;
  public double cost;
  public double prevCost;
  public double health;
  static Random random = new Random(0);
  public Bacterium(int dim, double minValue, double maxValue)
  {
    this.position = new double[dim];
    for (int p = 0; p < dim; ++p) {
      double x = (maxValue - minValue) * random.NextDouble() + minValue;
      this.position[p] = x;
    }
    this.health = 0.0;
  }
  public override string ToString()
  {
    // See code download
  }
  public int CompareTo(Bacterium other)
  {
    if (this.health < other.health)
      return -1;
    else if (this.health > other.health)
      return 1;
    else
      return 0;
  }
}

类细菌源自 IComparable 接口，以便确定哪些细菌会生存的下一代时，可以按他们的健康排序细菌的两个对象。

位置字段表示一个解决方案。成本域是与位置相关的成本。字段的 prevCost 是一种细菌先前的立场；与相关的成本这样一种细菌，知道如果它提高与否，而且因此是否应游泳或滚落。卫生领域的细菌寿命期间的一种细菌的累积成本的总和。因为目标是尽量减少成本，健康的小值都优于较大的值。

细菌的构造函数初始化一个细菌的对象，以随机的位置。构造函数不是显式设置成本域。CompareTo 方法订单最大健康的细菌对象从最小的健康。

图 5 显示简单的殖民地类。

图 5 的殖民地类

public class Colony
{
  public Bacterium[] bacteria;
  public Colony(int S, int dim, double minValue, double maxValue)
  {
    this.bacteria = new Bacterium[S];
    for (int i = 0; i < S; ++i)
      bacteria[i] = new Bacterium(dim, minValue, maxValue);
  }
  public override string ToString() { // See code download }
  public class Bacterium : IComparable<Bacterium>
  {
    // ...
}
}

殖民地类是本质上是细菌的对象的集合。殖民地的构造函数创建的细菌，其中每个细菌分配的随机位置通过细菌的构造函数调用的集合。

该算法

设置了 S 和数控，BFO 算法等 BFO 变量初始化后这种细菌菌落像这样：

Console.WriteLine("\nInitializing bacteria colony");
Colony colony = new Colony(S, dim, minValue, maxValue);
for (int i = 0; i < S; ++i) {
  double cost = Cost(colony.bacteria[i].position);
  colony.bacteria[i].cost = cost;
  colony.bacteria[i].prevCost = cost;
}
...

由于成本函数是外部的殖民地，细菌的每个对象的成本以外使用成本函数的殖民地构造函数设置。

初始化之后，确定在香港最好的细菌，牢记更低的成本比更高的成本最小化的 Rastrigin 功能的情况下：

double bestCost = colony.bacteria[0].cost;
int indexOfBest = 0;
for (int i = 0; i < S; ++i) {
  if (colony.bacteria[i].cost < bestCost) {
    bestCost = colony.bacteria[i].cost;
    indexOfBest = i;
  }
}
double[] bestPosition = new double[dim];
colony.bacteria[indexOfBest].position.CopyTo(bestPosition, 0);
Console.WriteLine("\nBest initial cost = " + bestCost.ToString("F4"));
...

下一步，设置的主要 BFO 处理的多个环：

Console.WriteLine("\nEntering main BFO algorithm loop\n");
int t = 0;
for (int l = 0; l < Ned; ++l)
{
  for (int k = 0; k < Nre; ++k)
  {
    for (int j = 0; j < Nc; ++j)
    {
      for (int i = 0; i < S; ++i) { colony.bacteria[i].health = 0.0; }
      for (int i = 0; i < S; ++i) // Each bacterium
      {
        ...

与索引 l 的外层循环处理扩散的步骤。与索引 k 的 next 循环处理复制的步骤。与索引 j 第三循环处理的趋化的步骤，表示每个细菌的寿命。此趋化循环一代新的细菌已只生成，因此每个细菌的健康重置为 0。后重置细菌健康值趋化循环，每个细菌内跌倒，确定一个新的方向和新的方向，然后移动如下所示：

double[] tumble = new double[dim];
for (int p = 0; p < dim; ++p) {
  tumble[p] = 2.0 * random.NextDouble() - 1.0;
}
double rootProduct = 0.0;
for (int p = 0; p < dim; ++p) {
  rootProduct += (tumble[p] * tumble[p]);
}
for (int p = 0; p < dim; ++p) {
  colony.bacteria[i].position[p] += (Ci * tumble[p]) / rootProduct;
}
...

第一，每个组件的当前细菌的位置，生成-1.0 和 +1.0 之间的随机值。然后计算结果向量的根产品。并通过以旧位置和移动有小部分的 Ci 变量的值然后计算细菌的新位置。

后翻筋斗，更新当前细菌和细菌然后检查以查看是否它找到一个新的全球最佳解决方案：

colony.bacteria[i].prevCost = colony.bacteria[i].cost;
colony.bacteria[i].cost = Cost(colony.bacteria[i].position);
colony.bacteria[i].health += colony.bacteria[i].cost;
if (colony.bacteria[i].cost < bestCost) {
  Console.WriteLine("New best solution found by bacteria " + i.ToString()
    + " at time = " + t);
  bestCost = colony.bacteria[i].cost;
  colony.bacteria[i].position.CopyTo(bestPosition, 0);
}
...

下一步，这种细菌进入游泳循环哪里它会游在同一方向，只要它提高通过找到更好的位置：

int m = 0;
    while (m < Ns && colony.bacteria[i].cost < colony.bacteria[i].prevCost) {
      ++m;
      for (int p = 0; p < dim; ++p) {
        colony.bacteria[i].position[p] += (Ci * tumble[p]) / rootProduct;
      }
      colony.bacteria[i].prevCost = colony.bacteria[i].cost;
      colony.bacteria[i].cost = Cost(colony.bacteria[i].position);
      if (colony.bacteria[i].cost < bestCost) {
        Console.WriteLine("New best solution found by bacteria " +
          i.ToString() + " at time = " + t);
        bestCost = colony.bacteria[i].cost;
        colony.bacteria[i].position.CopyTo(bestPosition, 0);
      }
    } // while improving
  } // i, each bacterium
  ++t;   // increment the time counter
} // j, chemotactic loop
...

可变 m 是游泳计数器限制 Ns 变量中的值相同的方向连续游泳的最大数目。游完泳后, 时间计数器递增和趋化循环终止。

在这一点上，所有的细菌都住了他们的寿命的数控和蚁群的最健康的一半将生活和将死，最不健康的一半：

Array.Sort(colony.bacteria);
  for (int left = 0; left < S / 2; ++left) {
    int right = left + S / 2;
    colony.bacteria[left].position.CopyTo(colony.bacteria[right].position, 0);
    colony.bacteria[right].cost = colony.bacteria[left].cost;
    colony.bacteria[right].prevCost = colony.bacteria[left].prevCost;
    colony.bacteria[right].health = colony.bacteria[left].health;
  }
} // k, reproduction loop
...

因为细菌对象派生自 IComparable，Array.Sort 方法会自动排序，从最小的健康（以较小是更好），所以最好的细菌都是左的 S/2 细胞集落数组的最大的健康。蚁群的合适的细胞中细菌的弱半有效地被杀的好的一半的细菌数组的数据复制到较弱的右半部分。请注意，这意味着细菌，S，总人数应被 2 整除的数。

此时的趋化作用和繁殖的环路已完工，所以 BFO 算法进入分散相：

for (int i = 0; i < S; ++i) {
    double prob = random.NextDouble();
    if (prob < Ped) {
      for (int p = 0; p < dim; ++p) {
        double x = (maxValue - minValue) *
          random.NextDouble() + minValue;
        colony.bacteria[i].position[p] = x;
      }
      double cost = Cost(colony.bacteria[i].position);
      colony.bacteria[i].cost = cost;
      colony.bacteria[i].prevCost = cost;
      colony.bacteria[i].health = 0.0;
      if (colony.bacteria[i].cost < bestCost) {
        Console.WriteLine("New best solution found by bacteria " +
          i.ToString() + " at time = " + t);
        bestCost = colony.bacteria[i].cost;
        colony.bacteria[i].position.CopyTo(bestPosition, 0);
      }
    } // if (prob < Ped)
  } // for
} // l, elimination-dispersal loop
...

检查每个细菌。一个随机值生成和可变 Ped 确定如果当前细菌将被移动到任意位置进行比较。如果一种细菌事实上分散的它检查它是否找到新的全球最佳位置纯粹是偶然机会。

此时所有环已被执行都死刑，BFO 算法显示使用一个名为 ShowVector 的程序定义的帮助器方法找到最佳的解决方案：

Console.WriteLine("\n\nAll BFO processing complete");
    Console.WriteLine("\nBest cost (minimum function value) found = " +
      bestCost.ToString("F4"));
    Console.Write("Best position/solution = ");
    ShowVector(bestPosition);
    Console.WriteLine("\nEnd BFO demo\n");
  }
  catch (Exception ex)
  {
    Console.WriteLine("Fatal: " + ex.Message);
  }
} // Main
...

点是什么？

BFO 是一种近似解决不能使用传统的数学技术处理的数值优化问题的相对较新方法。在我看来，BFO 是遗传算法与粒子群优化的替代方法。有小研究证据来回答问题的只是如何有效 BFO 是或不是。

BFO 可能会如何使用？有很多可能性相关软件测试，并优化一般。例如，假设你想预测某事很困难，如一些在纽约证交所的股票价格的短期变化。收集的一些历史数据，并就一些复杂的数学方程与股票价格有关您的输入数据，但您需要确定您的方程的参数。您可能有可能使用 BFO 估计您的参数的值成本函数在哪里你方程所作的不正确预测的百分比。

BFO 是 meta-heuristic，意味着它只是一个概念框架，可以用于设计特定的算法。我在这里已经给出了的 BFO 的版本只是许多可能性的一，应考虑实验，而不是主题最终决定权的起点。事实上，为了使这篇文章的大小易于管理，删除群集功能所提出的原始 BFO 研究文章的细菌。

**博士。**James McCaffrey为伏信息科学 Inc.，凡他管理技术培训工作在华盛顿雷德蒙的微软校园软件工程师的工作。他被在几个 Microsoft 产品，包括互联网资源管理器和 MSN 搜索。博士。麦卡弗里的作者是"。网络测试自动化食谱"（很，2006年），可以在达到 jammc@microsoft.com。

多亏了以下的技术专家审查这篇文章：Paul Koch， Dan Liebling， Anne Loomis Thompson 和 Shane Williams