.NET Fiddle (https://dotnetfiddle.net/) — это быстрый и удобный способ создавать и тестировать различные идеи и проекты с использованием C#. Если вы хотите сохранить или загрузить программный код, вы должны зарегистрироваться в .NET Fiddle. В этой статье я покажу, как создать генетический алгоритм для оптимизации определенных значений или параметров.
Мы все знаем биологическую эволюцию жизни на Земле, открытую Чарльзом Дарвином. Этот эволюционный процесс оказался чрезвычайно эффективным методом поиска оптимальных решений для выполнения определенных задач. Из поколения в поколение особи популяции лучше способны выполнять необходимые задачи или приспосабливаться к окружающей среде. Это происходит путем отбора, мутации и скрещивания генетической информации.
Мы можем перенести эффективный генетический алгоритм из биологии в информатику и использовать его для решения сложных задач оптимизации. В нашем случае для простоты ограничимся поиском оптимальных значений для 20 целочисленных параметров.
Сначала мы устанавливаем «C#» в качестве языка программирования, «Консоль» в качестве «Типа проекта» и «.NET 7» в качестве компилятора. Он также должен работать с «.NET 6» или «NET 5». Для этой цели нам не нужны никакие пакеты NuGet.
В самом начале мы пишем операторы использования, чтобы включить необходимые пространства имен:
using System; using System.Collections.Generic; using System.Linq;
Теперь мы можем написать код для метода Main() следующим образом:
const int countOfGenerations = 10000;
const int countOfIndividuals = 500;
const int countOfGenes = 20;
int minGeneValue = 0;
int maxGeneValue = 1000;
// Build a test solution we try to find via the genetic optimization algorithmus
List<int> testSolution = new List<int>(new int[countOfGenes]{58,0,401,66,171,53,22,232,28,309,29,34,356,30,0,46,19,41,56,999});
// Create a population of random solutions
Population pop = new Population(countOfIndividuals, countOfGenes, minGeneValue, maxGeneValue);
// Now start the optimization process
for(int z = 0; z < countOfGenerations; z++)
{
// Test fitness of the current population
double bestFitness = pop.CheckFitness(testSolution);
Console.WriteLine(string.Format("Generation: {0} Fitness: {1}", z, bestFitness));
//Console.WriteLine(string.Format("Generation: {0} Fitness: {1} Solution: {2}", z, bestFitness, string.Join(", ", pop.Individuals[0].Genes)));
if(bestFitness == countOfGenes) break; //This line has to be remove if we do not know the optimal solution
// Build the next generation
pop.BuildNextGeneration();
}
Console.WriteLine("---------------------------------------------------------------------------------------------------");
Console.WriteLine(string.Format("Found solution: {0}", string.Join(", ", pop.Individuals[0].Genes)));
Console.WriteLine(string.Format("Target solution: {0}", string.Join(", ", testSolution)));
Console.WriteLine("---------------------------------------------------------------------------------------------------");
Во-первых, мы определяем, из скольких особей должна состоять популяция и сколько генов для оптимизации должно быть у каждой особи. Мы также определяем диапазон чисел, в котором должны быть значения генов.
Затем мы создаем геном произвольных значений для нашего алгоритма. Нам это нужно только для проверки алгоритма, чтобы мы могли увидеть, способен ли он найти оптимальное решение.
Теперь создается начальная популяция. Далее следует петля, в которой процесс эволюции проходит от поколения к поколению. Каждая особь каждого поколения оценивается по тому, насколько хорошо она может решить поставленную задачу. Отображается лучшее значение пригодности в каждом поколении, чтобы можно было увидеть, как улучшаются значения пригодности в процессе оптимизации.
Процесс оптимизации завершается досрочно, когда решение найдено. Это работает только для нашего тестового примера, где решение известно. Для обычных процессов оптимизации вы не знаете решения, поэтому вам нужно спроектировать завершение цикла по-другому. В таких случаях цикл можно прервать, если за сотни поколений не было найдено лучшего значения пригодности.
Размещаем необходимые классы «Индивидуум» и «Население» ниже класса «Программа»:
internal class Individual
{
public List<int> Genes {get;}
public double Fitness {get; set;}
private Random rnd = new Random((int)DateTime.Now.Ticks);
public Individual(int countOfGenes, int minGeneValue, int maxGeneValue)
{
Genes = new List<int>(new int[countOfGenes]);
Fitness = 0;
for(int j = 0; j < countOfGenes; j++)
{
// Set each gene value randomly
Genes[j] = rnd.Next(minGeneValue, maxGeneValue);
}
}
}
Каждый человек содержит геном или набор генов. Это те значения, которые следует оптимизировать для решения поставленной задачи. Значение пригодности человека показывает, насколько хорошо человек может решить задачу.
internal class Population
{
public List<Individual> Individuals {get; set;}
public int CountOfIndividuals;
public int CountOfGenes;
public int MinGeneValue;
public int MaxGeneValue;
private Random rnd = new Random((int)DateTime.Now.Ticks);
public Population(int countOfIndividuals, int countOfGenes, int minGeneValue, int maxGeneValue)
{
CountOfIndividuals = countOfIndividuals;
CountOfGenes = countOfGenes;
MinGeneValue = minGeneValue;
MaxGeneValue = maxGeneValue;
Individuals = new List<Individual>(new Individual[CountOfIndividuals]);
for(int j = 0; j < countOfIndividuals; j++)
{
Individuals[j] = new Individual(CountOfGenes, MinGeneValue, MaxGeneValue);
}
}
// Check and calculate the fitness level of each individual
public double CheckFitness(List<int> testSolution)
{
for(int j = 0; j < Individuals.Count; j++)
{
Individual curInd = Individuals[j];
curInd.Fitness = 0;
for(int k = 0; k < testSolution.Count; k++)
{
if(curInd.Genes[k] == testSolution[k])
curInd.Fitness += 1;
}
}
// Sort list by fitness
Individuals = Individuals.OrderByDescending(x => x.Fitness).ToList();
return Individuals[0].Fitness;
}
// Use selection, crossing and mutation in order to build the next generation of individuals
public void BuildNextGeneration()
{
// Selection: Take over the best solutions unchanged
int individualsToLeaveUnchanged = (int)CountOfIndividuals / 3;
int individualsToBeChanged = CountOfIndividuals - individualsToLeaveUnchanged;
// Mutation: Change some individuals by mutation of a single gene
for(int i = 0; i < individualsToBeChanged; i++)
{
int idx1 = rnd.Next(individualsToLeaveUnchanged, CountOfIndividuals);
int idx2 = rnd.Next(0, CountOfGenes);
int newGene = rnd.Next(MinGeneValue, MaxGeneValue);
Individuals[idx1].Genes[idx2] = newGene;
}
// Crossing: Change some individuals by crossing with another
for(int i = 0; i < individualsToBeChanged; i++)
{
int idx1 = rnd.Next(individualsToLeaveUnchanged, CountOfIndividuals);
int idx2 = rnd.Next(0, CountOfIndividuals);
for(int j = 0; j < CountOfGenes; j++)
{
int cross = rnd.Next(0, 2);
if(cross == 1)
Individuals[idx1].Genes[j] = Individuals[idx2].Genes[j];
}
}
} // BuildNextGeneration
} // class Population
При создании объекта «Население» создается столько «Индивидуальных» объектов, сколько указано. Изначально все гены особей имеют случайные значения в заданных пределах.
Метод «CheckFitness» используется для проверки того, насколько хорошо гены человека решают поставленную задачу. В нашем тестовом случае проверяется, сколько генов имеют правильное значение. Если вы не знаете решения, вам нужно определить фитнес-тест по-другому. Оценка физической подготовки каждого человека хранится в каждом из этих объектов, поэтому население можно сортировать по показателю физической подготовки.
Метод «Build Next Generation» определяет процесс эволюции или оптимизации. Особи с наилучшей приспособленностью переходят в следующее поколение (отбор). Кроме того, некоторые гены некоторых особей случайным образом изменены (мутация). Гены некоторых особей также сочетаются друг с другом (скрещивание). Таким образом, новое поколение включает в себя новые решения, не теряя лучших из существующих. Если мы запустим программу, мы получим такой вывод:
Теперь вы можете поиграть с кодом и расширить пример до десятичных дробей (вместо целых) или увеличить или уменьшить количество особей в популяции. Надеюсь, что моя статья содержит полезную пищу для размышлений. Кстати, я не имею никакого отношения к сайту .NET Fiddle. Я всего лишь постоянный пользователь этого сайта.
Вы можете найти и протестировать весь код здесь: https://dotnetfiddle.net/2tWkyN
Эта статья не была написана (даже частично) ChatGPT!
Спасибо за прочтение!
