Прежде всего я хочу представить эволюцию интересным образом, чтобы далее проще было шаг за шагом написать программу с генетическим алгоритмом.
Я не буду вдаваться в подробности того, как компилировать и запускать программы на C. Если вы этого не знаете, пожалуйста, изучите сначала основы.
Ииии?! Что такое генетический алгоритм?!
Нуу, чтобы на это ответить, нужно знать, что такое эволюция. Но эволюция — простая вещь, которую легко можно объяснить кружками и квадратиками (ну, может быть, нужно будет еще чуть-чуть цвета 😉 ):
На первом рисунке — стартовая популяция (цветные кружки), на втором — популяция показана в окружающей среде (квадраты — хищники, а серый фон — местность, где живёт популяция). Наконец, третий рисунок показывает только выжившее население. Причина, по которой выжили красный и серый кружки — в том, то красный запугивает хищников, а серого гораздо сложнее найти среди камней. Вы могли бы заметить, что это ещё не полная эволюция, так как если мы оставим выжившее население на некоторое время, в среде ещё что-нибуть произойдёт, а именно:
Вкратце — эволюция с дарвинисткой точки зрения выглядит так:
Основное население + среда обитания = выжившее население.
А выживание населения спустя некоторое время = выживание населения + новое поколение.
Это самое «выживание + новое поколение» будет формировать уже новое население, которое в свою очередь будет взаимодействовать с окружающей средой, что-то вроде этого цикла:
Хорошо, но где же в этом всём объяснение генетического алгоритма (ГА)? Всё просто, ГА — это алгоритм, который пытается развивать нечто (программу, уравнение или что-то, что вы хотите и можете описать) аналогично эволюции. Идея заключается в том, чтобы получать, как и в эволюции, всё более адаптированные к каким-то условиям вещи, и если они оказываются действительно лучше предыдущих — выводя условия, при которых решение задачи улучшается. Не то, чтобы руководство эволюцией было тривиальным, но оно и не сложно.
Ассоциируя цикл ГА с циклом эволюции (цикл показан выше), можно легко проверить, соответствует ли новая сущность условиям окружающей среды. То есть, мы пытаемся симулировать пресс эволюции, чтобы выбрать сущности, более подходящие к заданным эволюцией (нами) условиям.
ГА начинается с исходной популяции, которая может быть случайной комбинацией символов, которые и должны будут развиваться. Далее эта комбинация проходит процесс оценки, где каждому из популяции будет присвоен ранг на основе его характеристик (функция, которая даёт нам этот ранг, называется фитнесс-функцией).
После создания начальной популяции каждый экземпляр оценивается и каждому присваивается фитнесс. Этот фитнесс будет принят во внимание при принятии каким-то образом решения о размножении, обычно таким образом, чтобы лучше адаптированные экземпляры (с лучшим фитнессом) оказывали влияние на новое поколение более, чем их хуже оцененные собратья. Тогда, убив часть изначальной популяции, мы даём место новой популяции, которая будет преемником изначальной.
Мы проводим этот цикл до достижения некоторого числа поколений или пока не выполнится некое условие.
Вы устали от объяснений, не так ли? Ну, давайте прекратим говорить и немного развлечемся программированием ;Р
Программирование
Вот секретный магический рецепт. Сначала создаём файл genetic.cpp и вставляем скелет кода:
#include<stdlib.h>int main()
{return 0;
}
Нуу, у нас уже есть готовая к компиляции программа 😉
Давайте представим, что мы хотим развить какие-нибуть характеристики. Мы знаем, какие характеристики хороши, а какие не очень хороши, и мы хотим их развить.
Предположим, что то, во что мы хотим развиться — это лимонад. Дааа, что лучше летом? 😉
Чтобы получить лимонад, у нас на кухне есть некие ингридиенты, и мы хотим, чтобы компьютер попытался приготовить из них смесь, а затем рассказать нам, какие из ингридиентов входят в лимонад на вершине эволюции.
Список ингредиентов: соль, сахар, лимон, яйца, вода, лук и яблоко. Это будут наши хромосомы, то есть ДНК, который мы хотим изменить, чтобы получить лимонад.
Но мы хотим не всего одну хромосому в коде, а население хромосом, тем самым, установив начальную популяцию из 10 случайных хромосом, у нас будет: ps2 gameplay bleach
int population=10;
bool chromosome[10][7]; // популяция// инициализация популяции
for(i=0;i<population;i++)
{
for(j=0;j<7;j++)
{
// randomize
chromosome[i][j]=rand()%2;
}
}
В приведенном коде хромосомы установлены в bool, потому что мы хотели просто узнать, какие ингредиенты нужно положить в лимонад. Таким образом, 0 означает «не класть», 1 — «положить».
Нам нужна фитнесс-функция для оценки популяции хромосом. Тогда если ингредиенты, присутствующие в лимонаде, получают положительную оценку, а те, что не присутствуют — отрицательную, путём максимизации этой функции (выбор хромосомы с большим фитнессом) мы бы руководили эволюцией лимонада. Итак, зададим функцию для расчета фитнесса:
{
// the ingredients are: 0 1 2 3 4 5 6
// salt sugar lemon egg water onion apple
return ( —chromosome[0] + chromosome[1] + chromosome[2]
—chromosome[3] + chromosome[4] — chromosome[5]
—chromosome[6] );
}
Цикл эволюции:
{
printf(«generation %d
«,g);//Evaluation//Reproduction
}
Мы ограничиваем ГА в 100 поколений, после этого проверяем, какие у нас выходят хромосомы (в нашем случае — каков на вкус наш лимонад, хе-хе).
Теперь работаем внутри цикла эволюции, оценка будет выглядеть так:
int best=0; // Будет хранить индекс лучшего в популяцииfor(i=1;i<population;i++)
{
if(fitness(chromosome[best])<fitness(chromosome[i]))
best=i;
}
В приведённом коде лучшая хромосома выбирается из всей популяции. И ниже код, воспроизводящий элитную популяцию:
for(i=0;i<population;i++)
{
// не воспроизводить себя, это будет потерей времени
if(i!=best)
{
for(j=0;j<7;j++)
{
//либо будет сохранён тот же ген, либо
//заменён на лучшую хромосому
if(rand()%2)
chromosome[i][j]=chromosome[best][j];
else
chromosome[i][j]=chromosome[i][j];//мутация
if(rand()%100<4)
chromosome[i][j]=rand()%2;}}
}printf(«best fitness %d
«,fitness(chromosome[best]));
Основа формирования элиты — выбор лучших, воспроизведение их со всеми другими (это как спаривание одного лучшего быка со всеми коровами). Но нужно и оставить место мутациям в воспроизводстве для увеличения разнообразия.
Ну и… Мы сделали это! Если вы запустите программу, то увидите растущий фитнесс, пока он не достигнет 3 уровня, поскольку в нашей функции может быть только три положительных гена.