AI алгоритм для оптимизации / прогнозирования многомерных решений
У меня есть 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
Чем выше результат, тем лучше комбинация чисел, у меня уже есть расчет, который дает результат, мне нужен только ИИ, чтобы найти лучшую комбинацию чисел, которая дает более высокий результат.
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 с ИИ, чтобы получить наилучший результат без перебора всех 100^6 комбинаций?
Я планирую использовать Accord.NET в C# (или есть что-то лучше?), Пример кода был бы полезен, потому что я новичок в AI.
3 ответа
Добро пожаловать в область многоцелевой оптимизации. В этой области я написал диссертацию. Существует множество алгоритмов для решения подобных задач, но, пожалуй, два самых известных - это NSGA-II и SPEA2.
Конечно, у вас есть только одна цель: что бы вы ни делали, ваша функция подсчета очков дает результат. Я бы сказал, что многоцелевые алгоритмы также применимы, потому что вас интересует не только одно решение, но и их совокупность.
Могу ли я указать вам на http://jmetalnet.sourceforge.net/?
Идея состоит в том, что вы будете генерировать совокупности случайных векторов, содержащих входные данные, которые охватывают ваш домен 100^6 возможных решений. Эти популяции будут мутировать и спариваться друг с другом, чтобы генерировать новые решения, и из этих новых популяций они отбираются таким образом, что выбираются более предпочтительные решения, чтобы остаться (и пережить эволюцию).
В мультимире могут возникнуть проблемы при сравнении пригодности различных решений. Но в вашем единственном объективном мире сравнить пригодность очень просто: вам просто нужно решить, хотите ли вы большее число или меньшее. Кажется, вы хотите выше.
Изложенные
- Создать случайную совокупность решений.
- Произвольно видоизменять / пересекать ваши решения.
- Рассчитать пригодность каждого и отсортировать.
- Уменьшите выборку до исходного размера лучших решений.
- Повторите шаги 2-4 [до конвергенции: до средней пригодности> порога?]
- Вывод окончательного поколения.
Результаты:
Вот плохой анализ, и отметим, что вы могли бы сделать намного лучше, усреднив результат (скажем) 20 прогонов на каждом уровне параметров. Сразу же, вы можете сказать, что уровень мутаций должен оставаться низким, и, очевидно, более высокий размер популяции может помочь (до сходящейся точки).
Результаты отформатированы как средняя оценка до, после, с максимальным значением 600
PopSize = 100, NumGens = 50, MutRate = 0,2, 0,8 = кросс-курс
295.23,542.12
PopSize = 100, NumGens = 500, MutRate = 0,2, 0,8 = кросс-курс
298.53,565
PopSize = 1000, NumGens = 50, MutRate = 0,2, 0,8 = кросс-курс
301.814,579.334
PopSize = 10000, NumGens = 500, MutRate = 0,2, 0,8 = кросс-курс
299.8901,588
PopSize = 1000, NumGens = 50, MutRate = 0,4, 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:
Вы можете попытаться использовать метаэвристический / стохастический алгоритм локального поиска для решения этого типа проблемы, как упомянуто во многих комментариях и решении BurnsCA.
Имитация отжига и генетические алгоритмы являются примерами, но их гораздо больше. Реален ли такой подход, зависит от того, насколько быстро вы сможете рассчитать изменения в вашей целевой функции, то есть оценить качество решения и его изменения.
Если выходные данные вашей симуляции обладают свойством, что незначительные изменения кардинально изменяют результат, это может быть или не быть лучшим подходом, чем грубое форсирование некоторого числа случайных назначений и выбор лучшего. Вам придется экспериментировать.
Реализация самих этих алгоритмов, как правило, не очень сложна, и я думаю, что вы даже можете использовать такую библиотеку, как NMath, например, взглянуть на
http://www.centerspace.net/doc/NMath/user/simulated-annealing-85273.htm
Ваша "целевая функция", значение, которое вы пытаетесь максимизировать (или минимизировать), является результатом симуляции.
Хотя реализация самих алгоритмов не является сложной, эффективная реализация различных их аспектов.
Что вам нужно сделать, это определить функцию соседства, то есть способ перехода от решения (или указать, если хотите) к другому решению. В вашем случае это может включать в себя пример кода, предложенный BurnsCA, который был бы ходом в один шаг, потому что вы случайным образом выбрали бы другое значение для одного параметра. Вы также можете попробовать 2 или более ходов, если 1-вариант не показывает улучшения достаточно быстро.
Следующее, что вам нужно, это способ оценить эффект от движения. Другими словами, какова разница в целевой функции между вашим текущим значением и значением, которое вы будете иметь, если вы сделаете ход. Если это вообще возможно, вам понадобится способ оценить ход, без необходимости каждый раз заново выполнять всю симуляцию.
Самый наивный подход (который часто называется спуском) - это случайное перемещение к соседнему решению, и если оно нашло лучшее значение (в вашем случае более высокая целевая функция), задайте это новое решение и повторяйте этот шаг, пока не сможете не найти больше улучшений.
Проблема такого подхода в том, что вы довольно быстро застрянете в локальном максимуме. Имитационный отжиг предоставляет один из способов избежать этого, не выбирая только улучшения, а выбирая не улучшающие ходы с вероятностью, которая зависит от текущей "температуры", которая является просто переменной, которую вы уменьшаете на каждой итерации в соответствии с определенным графиком отжига, который вы определили,
Так как суть реализации этих методов заключается не в самих общих алгоритмах (хотя это занимает немного времени), а в реализации ваших функций оценки окрестности и оценки окрестности, я лично не думаю, что сэкономлено много времени используя некоторые рамки для этого.
Если это единоразово, а вышеприведенное неосуществимо, вы можете также рассмотреть возможность распараллеливания вычислений на тысячах машин, чтобы получить оптимальное решение. Например, Azure Batch или аналогичные сервисы. Поскольку вы можете протестировать 50 миллионов комбинаций за 30 минут (на одной машине без распараллеливания?), Вы можете в принципе выделить 20 000 виртуальных машин и протестировать все комбинации за 30 минут.
Вам не нужна структура машинного обучения для реализации алгоритма локальной оптимизации.
// 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 }
Обратите внимание, что этот подход локальной оптимизации работает только для в основном линейных задач.
Не отображается, но вы также хотели бы увидеть другие начальные значения или перезапустить все несколько раз.
На странице Википедии есть отличное изображение для алгоритмов восхождения на гору, которые как бы показывают суть того, что пытается сделать этот подход.