Генетический алгоритм — пример применения методики

Чтобы убедить вас, что метод генетических алгоритмов — это очень простая штука, был создан данный пример. Мы найдем с помощью генетического алгоритма, что кратчайший путь между двумя точками — это прямая.

Постановка задачи:

Заданы две точки на плоскости A и B. Между ними через N точек проложен маршрут. Нужно оптимизировать (минимизировать) путь, используя генетический алгоритм.

Решение:

Опираясь на выводы прошлой статьи о генетических алгоритмах, мне понадобятся: начальное решение (одно или несколько), метод отбора и методы генерации новых потомков.

Начальное решение:

Я случайно задам на плоскости N точек маршрута, соединяющего точки А и B.

Метод отбора:

Мы будем убирать из популяции самых длинных агентов (особей, маршрутов).

Но перед тем как убрать их от туда, надо измерить длину пути:

Генерация потомков.

Простейшая мутация — это смещение одной или нескольких точек агента в произвольном направлении. Можно также реализовать кроссовер, скрещивание — будем брать часть одного маршрута и присоединять к нему часть другого маршрута.

Я реализовал и мутацию и кроссовер. В исходном коде это два метода класса GASIMLINE.

addMutant — имитирует мутацию.

addCrossOver — имитирует скрещивание.

Где взять исходник?

Алгоритм «упакован» в специальный объект, где все и происходит. Для рендеринга картинки используется html 5 контейнер canvas. Функция прорисовки также внутри этого класса.

Скачать.

Симуляция

Укажите кол-во промежуточных точек в маршруте (число от 1 до 1000) и нажимите кнопку "Задать".

Кол-во промежуточных точек маршрута:

GEN - число поколений, прошедших с начала симуляции.
LEN - текущая длина в % по отношению к идеальному расстоянию.
N - число промежуточных точек маршрута.

Наша популяция состоит из 20 "особей", наиболее короткий путь прорисован жирнее.

Написать комментарий

Мало букафф? Читайте есчо !

Антиспам с использованием Javascipt для WordPress, обходимся без Captcha

Апрель 12, 2013 г.

О сути метода я рассказываю здесь - Бегство от спама. Для работы понадобится hook на новые комментарии - pre_comment_approved, который мы объявим в файле темы - function.php. Если в вашей теме нет такого файла - создайте :). Нужно модифицировать всего ...

Читать

Тонкости настройки в .gitignore

Июль 17, 2017 г.

Настройки в файле .gitignore позволяют исключить из списка файлов сканируемых GIT, все то что отслеживать не надо. Обычно это так называемые юзер-файлы, изображения, архивы, документация и т.п. В данной статье рассмотрим типовой случай настоек в .gitignore. ...

Читать

 

Комментарии к «Генетический алгоритм — пример применения методики»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: