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

简单的C#遗传算法

Barry Lapthorn
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.83/5 (81投票s)

2002 年 11 月 10 日

CDDL

7分钟阅读

viewsIcon

682960

downloadIcon

14519

在本文中，我们将用C#实现一个简单的遗传算法。

摘要

在本文中，我们将用 C# 实现一个简单的遗传算法。它不会是多线程的，也不会包含奇异的运算符或收敛标准（即，许多找到的解非常相似的条件）。它将简单地演示在托管代码中利用 .NET 运行时某些特性实现的遗传算法。

引言

遗传算法是一种依赖于自然界相似之处的优化技术。它能够解决各种优化问题，前提是这些问题能够以某种方式参数化，从而使问题的解决方案能够衡量算法找到的解决方案的准确性。我们将这种衡量标准定义为适应度。

遗传算法最初是在 20 世纪 70 年代早期提出的（Holland，1975）。最初的想法来自于观察生物的进化如何源于其组成的 DNA 和染色体。在这个意义上，可以简单地将其类比为一个由许多参数组成的数学问题。在真实化学序列的数学类比中，每个参数都可以取代染色体。

在自然界中，进化是通过选择过程进行的，其典型表达是适者生存。为了选择一个个体，我们需要一个由这样的个体组成的群体，从中选择以产生新一代个体。

对于我们希望解决的任何问题，我们需要衡量解决方案的优劣，即适应度，通常是χ2 (卡方) 衡量标准，即解决方案越好，函数返回的适应度越高。适应度越低的解决方案，它们生存到下一代群体的可能性就越小。通过采用这种技术，算法可以减少其检查的可能解决方案的数量。

许多问题在各种遗传算法中都以二进制形式内部表示。这里我们只考虑十进制表示。只要实现彻底（Field，1995），遗传算法的内部表示实际上并不重要。

问题

在我们的示例代码中，我们提供了一个测试函数，它使用 sin 和 cos 来生成下图。

此问题的最优解是 (0.5, 0.5)，即最高峰。我们选择这个例子是为了演示遗传算法如何不被周围的局部最大值（即高峰）所迷惑。

测试夹具

我们首先声明一个新遗传算法

GA ga = new GA(0.8,0.05,100,2000,2);

ga.FitnessFunction = new GAFunction(theActualFunction);

其中参数是交叉率、变异率、种群大小、代数和我们正在求解的参数数量。我们将 FitnessFunction 属性声明为

public delegate double GAFunction(double[] values);

public class GA
{
  static private GAFunction getFitness;
  public GAFunction FitnessFunction {  
    // etc.
  };
  //  etc.
}

这样我们就可以将适应度函数声明为与委托函数相同

public static double theActualFunction(double[] values) 
{
  if (values.GetLength(0) != 2)
  throw new ArgumentOutOfRangeException("should only have 2 args");
   double x = values[0];
   double y = values[1];
   double n = 9; 
   double f1 = Math.Pow(15*x*y*(1-x)*(1-y)*Math.Sin(n*Math.PI*x)
      *Math.Sin(n*Math.PI*y),2);
   return f1;
}

因此被算法接受。然后遗传算法被设置为运行

ga.Go();

遗传算法现在将运行指定的代数。

算法

算法代码包含两个简单类，GA 和 Genome，以及一个辅助类 GenomeComparer。

Genome 类可以被认为是一个简单的容器。底层结构是 0 到 1 范围内的双精度浮点数数组。用户需要获取这些值并将其缩放到他们所需的任何值。由于变异发生在基因组上，因此 Mutate 方法存在于此类别中。交叉操作符需要访问基因组的私有数据，因此它也是一个成员函数，它接受第二个基因组，并输出两个子基因组对象。特定基因组的适应度也存储在基因组对象中。代码本身中可能还有一些额外的辅助函数。

GA 类完成了所有工作。遗传算法包含以下基本步骤

  1. 创建新种群
  2. 从种群中选择两个个体，倾向于代表迄今为止最佳解决方案的个体。
  3. “繁殖”它们以产生后代。
  4. 如果我们没有足够的后代来组成新种群，则返回步骤 2。
  5. 用新种群替换旧种群。
  6. 如果我们没有产生足够的世代，则返回步骤 2。
  7. 我们已经完成了。

在选择个体进行繁殖时，我们使用所谓的轮盘赌方法。适应度更高的个体在“轮盘”中占有更大的比例，更有可能被选中。我们选择在 System.Collections.ArrayList 中累积存储适应度，因为它有一些很好的特性，例如排序。不幸的是，它的二分搜索方法只适用于精确值，所以我们必须实现以下变通方法

mid = (last - first)/2;

// ArrayList's BinarySearch is for exact values only
// so do this by hand.
while (idx == -1 && first <= last)
{
  if (randomFitness < (double)m_fitnessTable[mid])
  {
    last = mid;
  }
  else if (randomFitness > (double)m_fitnessTable[mid])
  {
    first = mid;
  }
  mid = (first + last)/2;
  // lies between i and i+1
  if ((last - first) == 1)
     idx = last;
}

GenomeComparer 类继承自 IComparer 接口。每一代都存储在一个 System.Collections.ArrayList 中，我们希望按适应度对每一代进行排序。因此，我们需要实现此接口，如下所示

public sealed class GenomeComparer : IComparer
{
    public GenomeComparer()
    {
    }
    public int Compare( object x, object y)
    {
        if ( !(x is Genome) || !(y is Genome))
            throw new ArgumentException("Not of type Genome");
        if (((Genome) x).Fitness > ((Genome) y).Fitness)
            return 1;
        else if (((Genome) x).Fitness == ((Genome) y).Fitness)
            return 0;
        else
            return -1;
    }
}

请注意，我们需要将 ArrayList 元素显式转换回 Genome 类型。我们还将该类密封，因为没有必要从它继承。

关于操作符的简要说明

我们简要提到了两个操作符：交叉和变异，这里我们将更详细地解释它们。

交叉操作只是简单地取两个基因组，在某个点将它们分开，并通过交换末端部分产生两个新的基因组，例如：

10 20 30 40 50 60 70
80 90 00
  
10 20 30 40 50 60 70
30 20 10
   
===>
    
00 90 80 70 60 50 40
30 20 10
  
00 90 80 70 60 50 40
80 90 00

分裂发生在基因组长度上随机选择的点，并且只有在通过概率测试后才会发生分裂。这通常设置得很高，反映了自然界中发生的情况。

相比之下，变异很少发生，所以其发生的概率设置得很低，通常低于 5%。基因组内的每个基因都依次进行测试，看它是否允许变异，如果允许，则用一个随机数替换它，例如：

10 20 30 40 50 60
70
 80 90
      ===>      
 10 20 30 40 50 60
22
 80 90

结果

通过我们这个简单的例子，我们知道最优解在 (0.5, 0.5) 处，经过 250 代后，我们发现了一个非常接近该解（在 4 位有效数字内）的解。遗传算法的进展如下图所示

 

结论和注意事项。

遗传算法并非万能，无法解决所有最小化/最大化问题。在许多情况下，其他算法更快更实用。然而，对于参数空间大且问题本身易于指定的问题，它可能是一种合适的解决方案。

在编写本文时，我学到了 C# 的几个特性，我想在这里总结一下（我来自 C++ 背景）

  • System.Collections.ArrayList 容器只进行浅拷贝。
  • System.Collections.ArrayList 容器的二分查找只适用于精确值。
  • 显而易见的一点是，仅仅定义一个变量并不一定会给它赋值。
  • 实现 IComparer 接口相当简单（参见 GenomeComparer 类）。

通过实现各种奇妙的操作符，可以进一步改进算法。我相信会有人告诉我一种更简单的方法来自动提供问题所需的参数数量，而不是使用 GA 构造函数和委托函数。

参考文献

Field, P., "遗传算法的多进制理论：统一二进制和非二进制问题表示", 博士论文, 1995, 玛丽女王学院。

Holland, J.H., 《自然与人工系统中的适应》, 麻省理工学院出版社, 1975, (1992 年版)。

Lippman, S.B., 《C# 入门：一种实用方法》, Addison-Wesley, 2002, (第 1 版)。

链接

以下可能感兴趣

  • Wall, M., "GALib - 遗传算法的 C++ 实现," 麻省理工学院, 1999。
  • 本文的俄语版本可在此处找到，由 Vladimir Lioubitelev 翻译。

历史

  • 2003 年 8 月 22 日 - 代码更新。
  • 2003 年 5 月 3 日 - 结论更新。
  • 2003 年 3 月 15 日 - 文章文本更新。
  • 2002 年 11 月 16 日 - 文章文本更新。
  • 2002 年 11 月 6 日 - 初版。
© . All rights reserved.