Добро пожаловать в область многоцелевой оптимизации. Это область, в которой я написал диссертацию. Существует множество алгоритмов для решения подобных задач, но, пожалуй, самыми известными являются два — NSGA-II и SPEA2.
Конечно, у вас есть только одна цель: независимо от того, что дает ваша функция подсчета очков. Я бы сказал, что многоцелевые алгоритмы также применимы, потому что вас интересует не просто одно решение, а их совокупность.
Могу я указать вам на http://jmetalnet.sourceforge.net/?
Идея состоит в том, что вы будете генерировать популяции случайных векторов, содержащих входные данные, которые варьируются в вашей области из 100 ^ 6 возможных решений. Эти популяции будут мутировать и скрещиваться друг с другом для создания новых решений, и из этих новых популяций они будут отобраны таким образом, что будут выбраны более предпочтительные решения, чтобы остаться (и выжить в эволюции).
В мультимире у вас могут возникнуть проблемы со сравнением пригодности различных решений. Но в вашем одноцелевом мире сравнивать пригодность легко: вам просто нужно решить, хотите ли вы получить более высокие значения или более низкие. Кажется, вы хотите выше.
Изложил
- Создайте случайную популяцию решений.
- Произвольно изменяйте/пересекайте свои решения.
- Подсчитайте пригодность каждого и рассортируйте.
- Уменьшите выборку до исходного размера популяции лучших решений.
- Повторяйте шаги 2-4 [до сходимости: пока средняя пригодность > порога?]
- Выходное окончательное поколение.
Полученные результаты:
Вот плохой анализ, и обратите внимание, вы могли бы добиться большего успеха, усредняя результат (скажем) 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:
person
Joe
schedule
12.10.2017
Calculation, чтобы найти оптимальное решение, или вы спрашиваете, как найти довольно хорошее решение? Вы можете использовать инфраструктуру ИИ, чтобы найти довольно хорошее решение, но это в основном проблема локально-максимального типа, и, кроме того, она имеет небольшую область. Типичный подход (очень грубо) состоит в том, чтобы попробовать случайные числа, выбрать лучшие результаты, а затем попробовать другие комбинации ближайших чисел и повторять, пока вы не будете удовлетворены. - person BurnsBA schedule 05.10.2017