Я довольно часто пишу про развитие, эволюцию, прогресс и прочие подобные продукты мыслительной деятельности накопленной человечеством по отношении к этому самому человечеству (мне это просто нравится), но сегодня я захотел рассказать о том, что такое генетические алгоритмы. Точнее даже не то, что это такое по сути, это отдельный разговор, а о том как они работают на конкретном примере.
В качестве задачи я взял задачу Коммивояжера (задача поиска кратчайшего маршрута соединяющего некоторое количество контрольных пунктов, городов). В общем-то есть много методов её решения, зависящие от структуры расположения городов и их количества.
Есть устойчивое мнение что задачу Коммивояжера не возможно решить точно уже при числе городов больше 30, однако это заблуждение, можно найти точное и абсолютно кратчайшее решение этой задачи, причем не численное, а аналитическое, при любом счетном количестве городов, но не всегда, точнее даже почти никогда, но иногда всё же можно, простейший пример - города расположенные по окружности, их может быть любое количество, ответ всегда(почти всегда) будет однозначный и точный (и наглядный).
Итак, начнем с того, что я кратко поясню что такое генетические алгоритмы. Своими словами, это эвристические алгоритмы манипулирующие данными подобно изменениям генома в процессе эволюции. (ключевое слово: "подобно").
Если вам интересно, можете найти точное описание где-нибудь на просторах интернета, мне не очень хочется заниматься копипастой.
Как правило генетические алгоритмы устроены по одинаковому шаблону, но возможно в одной из следующих статей я приведу пример того, как и где можно менять шаблон и к чему это приведет.
Базовый шаблон Генетического Алгоритма (ГА):
- Начальная популяция.
- Скрещивание.
- Мутация.
- Приспособленность.
- Отбор.
Алгоритм стартует с начальной популяции, как правило случайной, и далее в цикле повторяются остальные 4 пункта. Алгоритм останавливается при достижении какого-либо условия.
Для его реализации, в программном пакете MathCAD 15, в процедурном стиле, нужно (можно) определить ряд функций отвечающих за каждый из указанных ранее пунктов в базовом шаблоне.
почему именно маткад? ооо... старый-добрый маткад, он мне очень нравится, нравится как красиво выглядят формулы и алгоритмы, нравится лаконичность и минимализм в его программировании, по сути всего два условия и два цикла, больше ничего и не нужно... в общем наверное уже понят что мне просто нравится маткад, а сердцу как известно не прикажешь...
В начале нужно понять, что будет являться нашей особью. В данном случае я решил что это будет список городов, последовательно двигаясь по списку мы должны пройти его весь, побывав в каждом городе один раз, это и есть путь через все города.
Что бы генерировать этот путь и не повторять города, можно определить несколько функций отвечающих за операции над узлами графа (я не буду вдаваться в глубины теории графов, нам это не понадобится).
Первая такая функция, это функция перестановки двух случайных вершин местами: "Shuffle(O)".
В ней генерируются два случайных различных целых числа и города под этими номерами меняются друг с другом местами в маршруте следования.
Вот так это наглядно иллюстрируется (нарисовал как смог).
Почему вообще именно перетасовка двух городов?
Во первых, это просто и наглядно.
Во вторых, перетасовка не меняет количество городов, не добавляет новых и не удаляет уже имеющихся, она обладает свойством которое можно назвать "Законом сохранения набора городов": города из списка не откуда не берутся и никуда не исчезают, список переходит из одной формы в другую. (как вы заметили это калька с закона сохранения энергии, хах, не смотря на юмор это не далеко от истины, те преобразования которые мы наблюдаем для энергии не добавляют к ней ничего и не удаляют - они просто меняют форму энергии, это особенность связана с свойством замкнутости алгебраических систем, но об этом в другой статье)
Вторая функция "rndOsob(n)", это функция генерирует случайную особь размера n на основе некоторой эталонной (просто последовательный маршрут) путем перемешивания порядка её городов при помощи уже известной ранее функции "Shuffle(O)".
И только сейчас функция из базового шаблона генетического алгоритма, функция "NACHPOP(n,NOsob)" генерирующая начальную популяцию состоящую из NOsob (штук) случайных особей размером n (длиной в штуках городов).
Следующая базовая функция "MUT(Pop1)", функция мутации каждой особи популяции при помощи случайной перестановки (работает аналогично начальной популяции, оптимально было бы вначале написать эту функцию и применить её в начальной популяции для сокращения количества одинакового кода, но мне лень переделывать).
Ещё одна сервисная функция, для вычленения части списка всех городов одной особи.
Теперь переходим к скрещиванию, для этого нужно определить функцию скрещивающую двух особей O1 и O2 (напомню что каждая особь это просто список), функция "crossingover(O1,O2)".
Она берет геномы двух особей, разрезает их на 3 части (случайной длины, но одинаковые для обоих особей) и меняет средние части местами (если они содержат одинаковые наборы городов), далее возвращает двух особей с измененным геномом.
И на основе предыдущей функции определяем функцию которая скрещивает последовательно всех особей популяции с соседними к ним (т.е. i-ю особь скрещивает с (i+1)-й особью, а последнюю с первой, для замкнутости) и возвращает дополненную новыми особями популяцию.
(Для определенности поясню, в алгоритме в нашем случае, есть два вида списков:
++ первый вид - это список городов, он же геном, он же - особь;
++ второй вид списков - это список особей, он же - популяция, это список содержащий списки, в данном случае одинаковой длины, но по разному отсортированные)
Функция вычисления приспособленности, также иногда именуемая фитнесс-функцией, вычисляет приспособленность каждой особи популяции как длину всего маршрута заданного геномом особи (вычисляется почти как сумма квадратов разностей координат соседних городов маршрута).
Последняя функция которая необходима для реализации всего ГА это функция отбора особей. В данном случае она получает на вход популяцию, список приспособленностей всех особей и количество особей которое нужно отобрать в следующее поколение. (потом объединяет эти массивы в матрицу с двумя столбцами, сортирует по столбцу с приспособленностями в направлении возрастания и вырезает первые несколько особей имеющих минимальную приспособленность - минимальную длину маршрута - из этой отсортированной матрицы передавая их в следующее поколение)
И наконец-то сам ГА, собираемый из предыдущих функций нехитрым способом. Он получает на вход список с координатами городов, количество эпох и количество особей в популяции.
В начале мы имеем следующий набор городов (синим обозначен стартовый и он же финишный город).
Приведу несколько примеров маршрутов случайных особей, сгенерированных функцией "rndOsob(n)", с них начинается эволюция. Фактически это просто случайные замкнутые маршруты проходящие по разу через каждый город
Как видите их сложно назвать кратчайшими))) (в среднем, на сколько я заметил, они в 2-2.5 раза длиннее "оптимальных")
Результат запуска нашего ГА выглядит куда более обнадеживающим и рациональным (в сравнении с случайными маршрутами), эти решения нашлись за примерно 500 поколений (точнее, не более чем за 500 поколений, примерно за 100-200):
Для наглядности я сделал анимацию на которой приведены 12 особей из которых состоит вся популяция, и вы можете наблюдать как меняются особи и вся популяция по поколениям (счетчик T в левом верхнем углу), над каждой особью выводится информация о её приспособленности - длине маршрута заданного её геномом. (всего 200 поколений)
Можно заметить что самые стабильные это первые особи, и не удивительно, это лучшие особи, а изменяются чаще всего последние так как туда добавляются мутанты и потомки, потом они все оцениваются на предмет интересуемой приспособленности и худшие ликвидируются, а их место занимают новые мутанты и потомки, которые имеют шанс стать лучшими. Так вся популяция неуклонно движется к оптимуму (правда иногда локальному, но это уже совсем другая история)
Кстати, если наблюдать только за левой верхней особью, можно увидеть как отыскивалось решение, так как в качестве решения часто берут например первую лучшую особь из всей популяции.
П.С. на анимации немного другой список городов, он был получен ранее и мне лень его переделывать...
Ссылка на весь документ на Гугл диске
П.П.С. не так давно я провёл пару стримов на которых с нуля в MathCad15 написал генетический алгоритм и нейросеть, которую обучал этим алгоритмом, так что если интересно, как это можно сделать, милости прошу поиск в ютубе (и она же ссылка) "Пишем простую нейросеть в MathCad 15", вся работа заняла два стрима (на первом написали нейронку и частично ГА, на втором дописали ГА и исправили ошибки)