多维度解优化/预测的AI算法
AI algorithm for multi dimension solution optimization / prediction
我有 6 个 int 参数，范围从 0 到 100
数字的总组合为 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
结果越高的数字组合越好，我已经有计算出结果了，我只需要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
注意：数字的顺序也很重要。
如何使用 AI 减少 100^6 的总组合，以便在不遍历所有 100^6 组合的情况下获得最佳结果？
我打算在 C# 中使用 Accord.NET（或者有更好的东西吗？），代码示例会有所帮助，因为我是 AI 新手。
您不需要机器学习框架来实现局部优化算法。
// 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 }
请注意，这种局部优化方法仅适用于大多数线性问题。
未显示，但您还希望看到不同的起始值，或者多次重新运行整个过程。
有一种 nifty image on wikipedia page for hill climbing 算法可以展示这种方法试图做的事情的本质。
您可以尝试使用 Metaheuristic / Stochastic Local Search 算法来解决许多评论和 BurnsCA 解决方案中提到的此类问题。
模拟退火和遗传算法是示例，但还有更多。
这种方法是否可行，取决于您计算 objective 函数变化的速度，即评估解决方案的质量及其变化。
如果您的模拟输出具有 属性 微小的变化会显着改变结果，那么它可能是也可能不是比通过一定数量的随机分配强制执行并获得最佳分配更好的方法。您将不得不进行试验。
这些算法本身的实现通常不是很复杂，我认为你甚至可以使用像 NMath 这样的库，例如看看
http://www.centerspace.net/doc/NMath/user/simulated-annealing-85273.htm
您的 "objective function"，您尝试最大化（或最小化）的值是模拟的输出。
虽然算法本身的实现并不难，但算法各个方面的高效实现却很困难。
您需要做的是定义邻域函数，即从解决方案（或状态，如果您愿意）到另一个解决方案的方法。
在您的情况下，这可能涉及 BurnsCA 建议的代码示例，这将是一个 1-opt 移动，因为您会随机 select one 参数的另一个值。如果 1-opt 不能足够快地显示改进，您也可以尝试 2-opt 或更多动作。
接下来您需要的是评估采取行动的效果的方法。换句话说，objective 函数在您的当前值和您采取行动后将拥有的值之间有什么区别。
如果可能的话，您会想要一种评估着法的方法，而不必每次都重新执行整个模拟。
最幼稚的方法（通常称为下降）是随机移动到相邻解决方案，如果它找到更好的（在您的情况下更高的 objective 函数）值，则将其作为新的解决方案，然后重复该步骤，直到您找不到更多改进。
这种方法的问题是您很快就会陷入局部最大值。模拟退火提供了一种尝试避免这种情况的方法，通过不 select 只改进，而是 select 非改进的移动，其概率取决于当前 'temperature' 这只是一个根据您定义的一些退火计划减少每次迭代的变量。
由于实现这些方法的关键不在于整体算法本身（尽管确实需要一点时间），而在于实现你的邻里和邻里评估功能，我个人认为没有通过为此使用一些框架节省了大量时间。
如果这是一次性的事情，上述方法不可行，你也可以考虑在数千台机器上并行计算以获得最优解。例如。 Azure Batch 或类似服务。由于您可以在 30 分钟内测试 50 个 mio 组合（在没有并行化的一台机器上？），原则上您可以提供 20 000 个虚拟机并在 30 分钟内测试所有组合。
欢迎来到多域Objective优化。这是我写论文的领域。解决此类问题的算法很多，但最著名的两个可能是 NSGA-II 和 SPEA2。
当然，你只有一个-objective：无论你的评分函数是什么，它都会产生。我认为多 objective 算法也适用，因为您不仅对单个解决方案感兴趣，而且对它们的总体感兴趣。
我可以向你指出 http://jmetalnet.sourceforge.net/ 吗？
我们的想法是，您将生成随机向量的总体，其中包含的输入范围涵盖您的 100^6 个可能解决方案的域。这些种群将发生变异并相互交配以产生新的解决方案，并且从这些新种群中，以这样一种方式向下选择它们，即选择保留更优选的解决方案（并在进化中幸存下来）。
在多世界中，比较不同解决方案的适用性可能会遇到挑战。但在你的单身 objective 世界里，比较适应度很容易：你只需要决定你想要更高的数字还是更低的数字。看来你想要更高。
概述
- 创建随机的解决方案。
- 在您的解决方案中随机 mutate/crossover。
- 计算每个人的适应度，并排序。
- 下采样回到最佳解决方案的初始总体规模。
- 重复步骤 2-4 [直到收敛：直到 avg fitness > threshold?]
- 输出最终代。
结果：
这是一个糟糕的分析，需要注意的是，您可以通过在每个参数级别平均（比如说）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);
}
}
}
其他注意事项
您的运行时间主要取决于您的健身评分功能。对于简单的数学函数，这个运行时不会很难。显然，如果涉及一个过程，您会希望将评估次数保持在最低限度。这就是我为 Ph.D. 研究的内容，并开发了一个名为 GALE:
的新算法
我有 6 个 int 参数，范围从 0 到 100
数字的总组合为 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
结果越高的数字组合越好，我已经有计算出结果了，我只需要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
注意：数字的顺序也很重要。
如何使用 AI 减少 100^6 的总组合，以便在不遍历所有 100^6 组合的情况下获得最佳结果？
我打算在 C# 中使用 Accord.NET（或者有更好的东西吗？），代码示例会有所帮助，因为我是 AI 新手。
您不需要机器学习框架来实现局部优化算法。
// 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 }
请注意，这种局部优化方法仅适用于大多数线性问题。
未显示，但您还希望看到不同的起始值，或者多次重新运行整个过程。
有一种 nifty image on wikipedia page for hill climbing 算法可以展示这种方法试图做的事情的本质。
您可以尝试使用 Metaheuristic / Stochastic Local Search 算法来解决许多评论和 BurnsCA 解决方案中提到的此类问题。
模拟退火和遗传算法是示例，但还有更多。 这种方法是否可行，取决于您计算 objective 函数变化的速度，即评估解决方案的质量及其变化。
如果您的模拟输出具有 属性 微小的变化会显着改变结果，那么它可能是也可能不是比通过一定数量的随机分配强制执行并获得最佳分配更好的方法。您将不得不进行试验。
这些算法本身的实现通常不是很复杂，我认为你甚至可以使用像 NMath 这样的库，例如看看
http://www.centerspace.net/doc/NMath/user/simulated-annealing-85273.htm
您的 "objective function"，您尝试最大化（或最小化）的值是模拟的输出。
虽然算法本身的实现并不难，但算法各个方面的高效实现却很困难。
您需要做的是定义邻域函数，即从解决方案（或状态，如果您愿意）到另一个解决方案的方法。 在您的情况下，这可能涉及 BurnsCA 建议的代码示例，这将是一个 1-opt 移动，因为您会随机 select one 参数的另一个值。如果 1-opt 不能足够快地显示改进，您也可以尝试 2-opt 或更多动作。
接下来您需要的是评估采取行动的效果的方法。换句话说，objective 函数在您的当前值和您采取行动后将拥有的值之间有什么区别。 如果可能的话，您会想要一种评估着法的方法，而不必每次都重新执行整个模拟。
最幼稚的方法（通常称为下降）是随机移动到相邻解决方案，如果它找到更好的（在您的情况下更高的 objective 函数）值，则将其作为新的解决方案，然后重复该步骤，直到您找不到更多改进。
这种方法的问题是您很快就会陷入局部最大值。模拟退火提供了一种尝试避免这种情况的方法，通过不 select 只改进，而是 select 非改进的移动，其概率取决于当前 'temperature' 这只是一个根据您定义的一些退火计划减少每次迭代的变量。
由于实现这些方法的关键不在于整体算法本身（尽管确实需要一点时间），而在于实现你的邻里和邻里评估功能，我个人认为没有通过为此使用一些框架节省了大量时间。
如果这是一次性的事情，上述方法不可行，你也可以考虑在数千台机器上并行计算以获得最优解。例如。 Azure Batch 或类似服务。由于您可以在 30 分钟内测试 50 个 mio 组合（在没有并行化的一台机器上？），原则上您可以提供 20 000 个虚拟机并在 30 分钟内测试所有组合。
欢迎来到多域Objective优化。这是我写论文的领域。解决此类问题的算法很多，但最著名的两个可能是 NSGA-II 和 SPEA2。
当然，你只有一个-objective：无论你的评分函数是什么，它都会产生。我认为多 objective 算法也适用，因为您不仅对单个解决方案感兴趣，而且对它们的总体感兴趣。
我可以向你指出 http://jmetalnet.sourceforge.net/ 吗？
我们的想法是，您将生成随机向量的总体，其中包含的输入范围涵盖您的 100^6 个可能解决方案的域。这些种群将发生变异并相互交配以产生新的解决方案，并且从这些新种群中，以这样一种方式向下选择它们，即选择保留更优选的解决方案（并在进化中幸存下来）。
在多世界中，比较不同解决方案的适用性可能会遇到挑战。但在你的单身 objective 世界里，比较适应度很容易：你只需要决定你想要更高的数字还是更低的数字。看来你想要更高。
概述
- 创建随机的解决方案。
- 在您的解决方案中随机 mutate/crossover。
- 计算每个人的适应度，并排序。
- 下采样回到最佳解决方案的初始总体规模。
- 重复步骤 2-4 [直到收敛：直到 avg fitness > threshold?]
- 输出最终代。
结果：
这是一个糟糕的分析，需要注意的是，您可以通过在每个参数级别平均（比如说）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);
}
}
}
其他注意事项
您的运行时间主要取决于您的健身评分功能。对于简单的数学函数，这个运行时不会很难。显然，如果涉及一个过程，您会希望将评估次数保持在最低限度。这就是我为 Ph.D. 研究的内容，并开发了一个名为 GALE:
的新算法