多维解优化/预测的人工智能算法

Question

我有6个int参数，从0到100。

这些数字的总组合为100^6，每个组合给出的结果范围约为100^6。从-10000到100000甚至更多。

Input data example:
MySimulation (57, 78, 20, 10, 90, 50) = 300  <- Best Result
MySimulation (50, 80, 10, 90, 35, 8) = 200
MySimulation (4, 55, 40, 99, 40, 50) = -50 <- Worst Result

结果越高，数字组合越好，我已经有了给出结果的计算，我只需要人工智能就可以找到一个更好的数字组合，从而得到更高的结果。

Output data example:
55, 70, 25, 15, 95, 52   <- Let's say these combination of
                            numbers was choosen by AI and would 
                            give a result of 400 with my simulation

注:数字的顺序也很重要。

我如何减少100^6与AI的总组合，以获得最好的结果，而不迭代所有100^6的组合？

我计划在Accord.NET中使用C# (或者有更好的地方吗？)，一个代码的例子会有帮助，因为我对AI是新手。

Answer 1

欢迎来到多目标优化领域。这是我写过论文的一个领域。解决这类问题的算法很多，但也许最著名的两个算法是NSGA-Ⅱ和SPEA2。

当然，你只有一个目标:不管是什么，你的得分函数都是屈服的.我认为多目标算法也适用，因为你不仅对单一的解决方案感兴趣，而且对它们的总体感兴趣。

我能告诉你http://jmetalnet.sourceforge.net/吗？

其思想是，您将生成随机向量的总体，其中包含跨域100^6可能的解决方案的输入。这些群体将相互变异和交配，以产生新的解决方案，而从这些新的群体中，他们被选择的方式是选择更可取的解决方案来保留(并在进化中生存)。

在多个世界中，比较不同解决方案的适用性可能会遇到挑战。但是在你的单一客观世界中，比较合适的条件很容易:你只需要决定你想要更高的数字还是更低的数字。看起来你想要更高的。

概述

1. 创建解决方案的随机种群。
2. 在你的解决方案中随机变异/交叉。
3. 计算每个人的健康状况，并进行排序。
4. 向下样本返回到初始人口规模的最佳解决方案。
5. 重复步骤2-4直到收敛:直到avg适应度>阈值？
6. 输出最后一代。

结果：

下面是一个糟糕的分析，注意，通过在每个参数级别平均运行20次，您可以做得更好。从一开始，你就可以看出突变率应该保持在低水平，而且很明显，更高的种群规模可以帮助(到一个汇合点)。

结果格式化为平均分数之前，之后，最高为600。

PopSize=100，NumGens=50，MutRate=0.2，CrossRate=0.8

295.23 542.12

PopSize=100，NumGens=500，MutRate=0.2，CrossRate=0.8

298.53,565

PopSize=1000，NumGens=50，MutRate=0.2，CrossRate=0.8

301.814 579.334

PopSize=10000，NumGens=500，MutRate=0.2，CrossRate=0.8

299.8901,588

PopSize=1000，NumGens=50，MutRate=0.4，CrossRate=0.8

306.22 385.55

代码

我在大约20分钟内编写了这段代码，所以它不是优雅的，也不是很棒的。我希望这能让人明白。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace moo_in_csharp
{
    internal class Individual
    {
        public int[] Decisions;
        public double Fitness;
        private int _numdecisions = 6;

        /// <summary>
        /// Default constructor.
        /// </summary>
        public Individual()
        {
            Decisions = new int[_numdecisions];
        }

        /// <summary>
        /// Replaces first half of decisions with those of the mate.
        /// </summary>
        /// <param name="mate"></param>
        public void Crossover(Individual mate)
        {
            int crossoverPoint = _numdecisions / 2;
            for (int i = 0; i < crossoverPoint; i++)
            {
                Decisions[i] = mate.Decisions[i];
            }
        }

        /// <summary>
        /// Simple fitness function that computes sum of a+b+c+d+e+f.
        /// </summary>
        public double Evaluate()
        {
            Fitness = Decisions.Sum();
            return Fitness;
        }

        /// <summary>
        /// Assigns random values to its decisions.
        /// </summary>
        public void Generate()
        {
            for (int i = 0; i < _numdecisions; i++)
            {
                Decisions[i] = Program.rand.Next(0, 101);
            }
        }

        /// <summary>
        /// Randomly mutate select decisions.
        /// </summary>
        public void Mutate()
        {
            for (int i = 0; i < _numdecisions; i++)
            {
                Decisions[i] = Program.rand.Next(0, 101);
            }
        }
    }

    internal class Program
    {
        public static Random rand = new Random();

        private static void Main(string[] args)
        {
            //parameters
            int populationSize = 100;
            int numGenerations = 50;
            double mutationRate = 0.2;
            double crossoverRate = 0.8;

            //build initial population
            List<Individual> solutions = new List<Individual>();
            for (int i = 0; i < populationSize; i++)
            {
                var solution = new Individual();
                solution.Generate();
                solution.Evaluate();
                solutions.Add(solution);
            }

            //calculate average score of initial population
            var averageScoreBefore = solutions.Select(x => x.Evaluate()).Average();

            //iterate across number of generations
            for (int i = 0; i < numGenerations; i++)
            {
                //build offspring by mating sequential pairs of solutions
                var offspring = new List<Individual>();
                for (int e = 0; e < solutions.Count() - 1; e += 2)
                {
                    if (rand.NextDouble() < crossoverRate)
                    {
                        var newIndividual = new Individual();
                        solutions[e].Decisions.CopyTo(newIndividual.Decisions, 0);
                        newIndividual.Crossover(solutions[e + 1]);
                        offspring.Add(newIndividual);
                    }
                }

                //add our offspring to our solutions
                solutions.AddRange(offspring);

                //mutate solutions at a low rate
                foreach (var solution in solutions)
                {
                    if (rand.NextDouble() < mutationRate)
                    {
                        solution.Mutate();
                    }
                }

                //sort our solutions and down-sample to initial population size
                solutions = solutions.OrderByDescending(x => x.Evaluate()).ToList();
                solutions = solutions.Take(populationSize).ToList();
            }

            //calculate average score after
            var averageScoreAfter = solutions.Select(x => x.Evaluate()).Average();
            Debug.WriteLine(averageScoreBefore + "," + averageScoreAfter);
        }
    }
}

其他备注

您的运行时将主要依赖于您的健身评分功能。对于简单的数学函数，这个运行时并不难。显然，如果涉及到一个过程，您可能希望将评估的数量保持在最低限度。这是我为博士研究的，并开发了一种名为GALE的新算法：

• http://ieeexplore.ieee.org/document/7105950/

Answer 2

您可以尝试使用元启发式/随机局部搜索算法来解决这类问题，如许多注释和BurnsCA解决方案中提到的那样。

模拟退火和遗传算法是例子，但还有更多。这种方法是否可行，取决于您能以多快的速度计算出目标函数的变化，即评估解决方案的质量及其变化。

如果模拟的输出具有微小的变化会显着地改变结果的特性，那么它可能是一个更好的方法，也可能不是一个更好的方法。你得做实验。

这些算法本身的实现通常并不十分复杂，我认为您甚至可以使用像NMath这样的库，例如查看

http://www.centerspace.net/doc/NMath/user/simulated-annealing-85273.htm

您的“目标函数”，您试图最大化(或最小化)的值是模拟的输出。

虽然算法本身的实现并不难，但其各个方面的高效实现却是如此。

您需要做的是定义一个邻域函数，即从解决方案(或者如果您愿意的话)获得另一个解决方案的方法。在您的示例中，这可能涉及BurnsCA建议的代码示例，这将是一个1-opt移动，因为您将随机为一个参数选择另一个值。你也可以尝试2-选择移动或更多，如果1-选择没有显示出足够快的改进。

接下来你需要的是一种评估采取行动的效果的方法。换句话说，如果你采取行动，你现在的价值和你的价值之间的目标函数有什么区别？--如果有可能的话--，您需要一种评估移动的方法，而不必每次都执行整个模拟。

最天真的方法(通常称为下降)是随机移动到邻居的解决方案，如果它找到了一个更好的(在您的情况下是更高的目标函数)值，那么让新的解决方案，然后重复这一步骤，直到您找不到更多的改进。

这种方法的问题是，您会很快陷入局部最大值。模拟退火提供了一种避免这种情况的方法，不只是选择改进，而是选择不改进的移动，其概率取决于当前的“温度”--这只是一个变量，根据所定义的退火时间表，每次迭代都会减少。

由于实现这些方法的关键不在于整体算法本身(尽管这需要一些时间)，而在于实现您的邻里和邻里评估函数，因此我个人认为使用某种框架不会节省太多时间。

如果这是一次性的事情，而且上面的内容是不可行的，那么您也可以考虑并行处理数千台机器的计算，以获得最优解。例如，Azure批次或类似的服务。由于您可以在30分钟内测试50个mio组合(在一台机器上没有并行化？)，原则上您可以提供20000台虚拟机，并在30分钟内测试所有组合。

Answer 3

您不需要机器学习框架来实现本地优化算法。

// Example linear calculation
public int Calculation(int a, int b, int c, int d, int e, int f)
{
    int result = 0;
    unchecked
    {
        result = (int)((double)a * Math.Tan((double)b * Math.PI / ((double)c + 0.001)));
        result += d + e + f;
    }

    return result;
}


var rand = new Random();

// The currently best known solution set
var best = new int[6] { 1, 1, 1, 1, 1, 1 };

// Score for best known solution set
int bestScore = int.MinValue;

// loop variables
int score;
var work = new int[6];

// Loop as appropriate.
for (int i=0; i<500; i++)
{
    // Copy over the best solution to modify it
    best.CopyTo(work, 0);

    // Change one of the parameters of the best solution
    work[rand.Next() % 6] = rand.Next() % 101;

    // Calculate new score with modified solution
    score = Calculation(work[0], work[1], work[2], work[3], work[4], work[5]);

    // Only keep this solution if it's better than anything else
    if (score > bestScore)
    {
        work.CopyTo(best, 0);
        bestScore = score;
    }
}

上面的算法收敛得非常快，主要是因为计算函数非常友好。经过500次迭代后：

int[6] { 98, 1, 2, 98, 99, 100 }

其中最优解将是{ 100, 1, 2, 100, 100, 100 }

请注意，这种局部优化方法只适用于大多数线性问题。

没有显示，但是您也希望看到不同的起始值，或者多次重新运行整个事件。

维基百科上有一个关于漂亮的图像算法的爬山页面，它展示了这种方法的本质。