用于多维解决方案优化/预测的AI算法

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

数字的总组合为100 ^ 6，每个组合给出的结果大约为100。 从-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 

结果越高，数字组合越好，我已经有了计算结果，我只需要AI来找到更好的数字组合，从而得到更高的结果。

 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的总组合，以获得最佳结果？

我计划在C＃中使用Accord.NET（还是有更好的东西？），代码示例会有所帮助，因为我是AI的新手。

Answer 1

欢迎来到多目标优化领域。 这是我撰写论文的一个领域。 有许多算法可以解决这类问题，但也许最着名的两个算法是NSGA-II和SPEA2。

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

我可以指你http://jmetalnet.sourceforge.net/吗？

我们的想法是，您将生成包含输入的随机向量群，这些输入跨越您的100 ^ 6个可能解决方案的范围。 这些种群将被突变并相互交配以产生新的解决方案，并且从这些新种群中，它们被选择下来以使得更优选的解决方案被选择保留（并且在进化中存活）。

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

概述

1. 创建随机的解决方案群。
2. 在您的解决方案中随机变异/交叉。
3. 计算每个人的健康状况，并进行排序。
4. 下采样回到最佳解决方案的初始种群大小。
5. 重复步骤2-4 [直到收敛：直到平均健康>阈值？]
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; /// 
 /// Default constructor. /// 
 public Individual() { Decisions = new int[_numdecisions]; } /// 
 /// Replaces first half of decisions with those of the mate. /// 
 ///  public void Crossover(Individual mate) { int crossoverPoint = _numdecisions / 2; for (int i = 0; i < crossoverPoint; i++) { Decisions[i] = mate.Decisions[i]; } } /// 
 /// Simple fitness function that computes sum of a+b+c+d+e+f. /// 
 public double Evaluate() { Fitness = Decisions.Sum(); return Fitness; } /// 
 /// Assigns random values to its decisions. /// 
 public void Generate() { for (int i = 0; i < _numdecisions; i++) { Decisions[i] = Program.rand.Next(0, 101); } } /// 
 /// Randomly mutate select decisions. /// 
 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 solutions = new List(); 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(); 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); } } } 

其他说明

您的运行时间主要取决于您的健身评分function。 对于简单的数学函数，这个运行时并不难。 显然，如果涉及到某个流程，您需要将评估数量保持在最低水平。 这是我为博士研究的，并开发了一个名为GALE的新算法：

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

Answer 2

您可以尝试使用Metaheuristic / Stochastic Local Search算法来解决许多评论中提到的这类问题以及BurnsCA的解决方案。

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

如果模拟的输出具有微小变化会显着改变结果的属性，那么它可能会或者可能不会比强制通过一些随机分配并采用最佳分配更好。 你必须做实验。

这些算法本身的实现通常不是很复杂，我认为你甚至可以使用像NMath这样的库，比如看看

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

您的“目标函数”，您尝试最大化（或最小化）的值是模拟的输出。

虽然算法本身的实现并不困难，但是它们的各个方面的有效实现。

您需要做的是定义一个邻域函数，即从解决方案（或您喜欢的状态）到另一个解决方案的方法。 在您的情况下，这可能涉及BurnsCA建议的代码示例，这将是1-opt移动，因为您将为一个参数随机选择另一个值。 如果1-opt没有足够快地显示改进，您也可以尝试2-opt移动或更多。

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

最天真的方法（通常称为下降）是随机移动到邻居解决方案，如果它找到了更好的（在您的情况下更高的目标函数）值，请将其作为新解决方案，然后重复该步骤，直到您可以找不到更多改进。

这种方法的问题在于你会很快陷入局部最大值。 模拟退火提供了一种尝试避免这种情况的方法，即不仅仅选择改进，而是选择非改进的移动，其概率取决于当前的“温度”，这只是根据您定义的某些退火计划每次迭代减少的变量。

由于实现这些方法的关键不在于整体算法本身（虽然确实需要一些时间），但在实现邻域和邻域评估function时，我个人并不认为有很多时间可以节省使用一些框架。

如果这是一次性事情并且上述情况不可行，您还可以考虑在数千台计算机上并行计算以获得最佳解决方案。 例如Azure Batch或类似服务。 既然您可以在30分钟内测试50 mio组合（在没有并行化的一台机器上？），原则上可以提供20 000个虚拟机并在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; } } 

上面的解决方案非常快，主要是因为计算function非常友好。 500次迭代后：

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

最佳解决方案是{ 100, 1, 2, 100, 100, 100 }

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

没有显示，但你也想看到不同的起始值，或者重复运行整个事情。

在维基百科页面上有一个漂亮的图像用于爬山算法，这种图像显示了这种方法试图做的事情的本质。