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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

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

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

Скачать.

Симуляция

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

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

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

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

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

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

Подключение CAPTCHA к пользовательской форме в drupal

Февраль 19, 2012 г.

У вас есть запрограммированная форма в друпал, и вы хотите добавить в неё антиспам поле из модуля CAPTCHA. Смотрим как это сделать. Для начала модуль СAPTCHA надо скачать и установить (активировать на странице доступных модулей сайта - /admin/build/modules). ...

Читать

Кол-во знаков после запятой при генерации css препроцессором sass

Март 28, 2018 г.

В одном из проектов использовался SASS, но оказалось, что у другого разработчика другие настройки SASS. И конечные CSS генерировались с числами другой точности (другое кол-во знаков после запятой). Любое изменение в файле приводило к огромному ...

Читать

 

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

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



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