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

Evolution .NET - 最大化未知

D. Infuehr
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.48/5 (11投票s)

2014年7月17日

MIT

6分钟阅读

viewsIcon

18541

downloadIcon

460

如何优化给定问题以达到可计算的最优解。

引言

本文将通过一个易于使用的 C# Evolution 类和 Schwefel 函数的示例，解释进化算法的基础知识。您可以将此项目用于查找任何以数字作为输入参数并返回一个要最大化的值的系统的解决方案。例如，风力涡轮机的效率或函数的返回值。

为什么需要进化？

假设您有一个带有 2 个滑块的黑箱，每个滑块有 10 个位置。这个黑箱的输出是能量。您可以尝试推导出黑箱的分析模型，或者您可以使用组合数学来找到最大能量输出。让我们想象一下：您有 10^2 个位置来尝试找到最佳解决方案。如果您有 20 个带有 100 个位置的滑块呢？您将获得 20^100 种可能性。即使是整个宇宙的时间也不足以尝试所有位置。这时进化就派上用场了。它不会尝试所有可能性，但它能在相对较短的时间内找到好的滑块位置。

现实世界要复杂得多。想象一下您正在制造一台引擎。您有 4000 个自由参数，例如材料成分和零件宽度。您想最大化引擎的效率。Evolution .NET 只需要对自由参数的引用以及返回的效率。唯一的要求是您可以在其他地方计算效率并将其反馈给该类。

如果您想亲自尝试一下，请随意下载演示项目。

Using the Code

此类设计得尽可能直观。您只需要说：这是我的变量引用，请为我的问题提供一个好的解决方案。不需要包装类。非常方便。所有神奇的操作都在后台进行。

double a=0;

var Evo=new Evolution(EvolutionMode.Maximize);
Evo.AddVariable(ref a);

while(true)
{
    Evo.Fitness=Math.Sin(a/2);
}

这里发生了很多事情

  1. 您告诉进化算法最大化适应度。如果您最小化循环，适应度值将接近 -1。
  2. 该类不知道如何计算适应度值，但它会找到正确的解决方案。
  3. "a" 在设置 Fitness 属性时被更改。有一个内部的 IntPtr 引用列表。
  4. 您在进化范围 -500 到 500 的标准范围内交替。

请注意：在您将 "a" 的值传递给函数后，它会在没有额外代码的情况下被更改。

"a" 的值将接近 p。一次测试运行显示 Fitness 为 0.9999999999946 ，这对于该函数（1）的高点来说是一个很好的近似值。

此类不仅支持 double 类型，还支持几乎所有有符号数值类型。Float、Int、Double，甚至 Bool。以及这些类型的所有列表和 public 属性。

幕后

此类是一个自适应遗传算法，这意味着进化速率和其他参数可以由用户更改，也可以由类本身更改。

进化算法使用一个称为基因组的隐藏数字列表。基因组有一个称为适应度的值。进化算法的目标是最大化适应度值。如第二段所述，尝试所有可能性不是一个选项。进化算法使用三个原则。

  • 繁殖
  • 变异
  • 选择

事实上，这三件事一直在自然界中发生。第四步是隐含的，也非常重要：重复，直到您对结果满意为止。

想对主要思想有一个好的介绍，请查看

在后台，有一个已排序的基因组和适应度值列表。这个列表称为种群。其大小可以更改，默认值为 100。下面是负责找到比之前更好的值的代码行。

//marry best mate
if (SafeRandom.Percent(20) && Population.Count > 2) 
{ genome = neu.Marry(Population[Population.Count - 2]).genome; return; }
//add variation
if (SafeRandom.Percent(80)){genome=neu.Mutate(Properties.Mutationrate,Properties).genome;return;}
//marry stranger
if (SafeRandom.Percent(20) && Population.Count > 2) 
{ genome = neu.Marry(Population[(int)SafeRandom.Between(0,Population.Count-2)]).genome; return; }
//introduce new person
genome=neu.Mutate(100,Properties).genome;

对于百分比的百分比值，没有经过验证的最优百分比。这些是经验值，并且优化了找到一个最优值所需的时间。

这里有 3 种结果

  • 交叉
  • 变异
  • 随机

交叉是通过从某个（随机）起始索引用另一个好的基因组替换一个基因组。这并非必需，因为变异可以做到类似的事情，但它确实能缩短找到完美配置所需的时间。变异以一定的概率改变一些基因。这在您已经处于局部最大值但仍想获得更好分数时很有用。随机性对于找到可能更好的其他最大值很重要。

下面的代码行负责自适应。每次变异序列都会在最小和最大值之间改变基因组。这是一个随机过程，因此是一个正态分布过程。在这种情况下，Tau（一次生成中的最大基因组变化）被定义为从全局最大值到全局最小值所需的最小步数。您可以看到精度与搜索空间成正比。如果没有找到更好的解决方案，Tau 值会减少 10 倍。当值达到全局搜索空间的 1/300 时，算法会识别出局部最小值并调用 OptimumReached 事件。

if (noimprove > 10 && Properties.Selfadapting == true&&Properties.Tausteps<300)
                {
                    Properties.Tausteps++;
                    noimprove = 0;
                }
                if (noimprove>15&&Properties.Tausteps>=300)
                {
                    bool cont=false;
                    if (OptimumReached != null)
                    {
                        var arg = new EvolutionEventArgs(gen, DateTime.Now - start.Value);
                        OptimumReached(this, arg, ref cont);

                        if (arg.Hardreset == true) { Population.Clear(); 
                        genome = genome.Select(x => x = 0).ToList(); this.StartTraining();  }
                        Continue = cont;
                    }
                }

无法确定是否真正找到了全局最优值，您的搜索空间中可能总会有更好的解决方案。

示例项目

此示例项目使用进化类来查找 Schwefel 函数的最小值。

f(x,y) = (-x * Math.Sin(Math.Sqrt(Math.Abs(x)))) + (-y * Math.Sin(Math.Sqrt(Math.Abs(y))))

using Evolution;

static void Main(string[] args)
        {
            double x = 0;
            double y = 0;

            var evolute = new Evolution(EvolutionMode.Minimize);
            evolute.AddVariable(ref x);
            evolute.AddVariable(ref y);

            evolute.OptimumReached += evolute_OptimumReached;
            evolute.Properties.Globalmin = -500;
            evolute.Properties.Globalmax = 500;

            while (evolute.Continue)
            {
                evolute.Fitness = (-x * Math.Sin(Math.Sqrt(Math.Abs(x)))) + (-y * Math.Sin(Math.Sqrt(Math.Abs(y))));
                Console.WriteLine(" x:"+x+" y:"+y+" = " +evolute.Fitness);
            }

            Console.Clear();
            Console.WriteLine("Schwefel’s Function has its minimum at:");
            double val = (-x * Math.Sin(Math.Sqrt(Math.Abs(x)))) + (-y * Math.Sin(Math.Sqrt(Math.Abs(y))));
            Console.WriteLine(" x:" + x.ToString("0.000") + 
            " y:" + y.ToString("0.000") + " Z= " + val);
            Console.ReadKey();
        }

        static void evolute_OptimumReached(Evolution Evo, EvolutionEventArgs Arg, ref bool Continue)
        {
            Continue = false;
            Console.WriteLine("Found minimum after: " + Arg.Duration);
        }

请注意：OptimumReachedEvent 在 while 循环中非常有用。作为用户，您可能不知道何时停止函数。当过去几代适应度没有显著变化时，会触发此事件。该事件允许您停止、继续或从头开始，如果您对适应度不满意，并提供一些其他统计值作为参数。

该函数的最小值为 -837.9658，在 x = y = 420.9687 处。

示例项目的输出为 -837.965773，在 x=420.968 和 y = 420.972 处。

为简化起见，未描述某些机制。请随时下载源代码（VS2013）。

结论

Evolution .NET 是进化算法的一个轻量级实现。它不区分列表属性或变量。它有一个事件处理程序来“知道”何时停止进化循环。

此类不需要问题的包装类。变量、变量列表和属性可以直接添加。如果您使用 redist DLL，则不需要使用 /unsafe 进行编译。

关注点

在编码过程中，我遇到了一个问题：将值类型的引用保存在列表中并在之后更改它。托管代码严格禁止存储 ref 参数。所有列表都存储为引用，但我希望在同一作用域中使用相同的变量。

死胡同 1

List<ref int> //not possible

死胡同 2

这个函数看起来很有希望

static void change(ref int a)
{
     var variables = new StackTrace().GetFrame(1).GetMethod().GetMethodBody().LocalVariables;
} //gets information of all variables. Only Variable info no setter, have to find a

解决方案

public void AddVariable(ref double Variable)
{
      unsafe
      {
          fixed (void* location = &Variable)
          {
              pointers.Add(new IntPtr(location));
              pointertypes.Add(Variable.GetType());
          }
      }
}

这是 ref 变量的最终解决方案。类实例的列表和属性可以在完全托管的代码中存储和更改。不幸的是，没有其他方法可以做到这一点（至少，我现在还不知道）。

该解决方案允许通过 ref 传递 blittable 类型并稍后进行更改。所有其他类型都通过 List 传递，而 List 总是通过引用传递。问题解决。

http://msdn.microsoft.com/en-us/library/75dwhxf7%28v=vs.110%29.aspx
© . All rights reserved.