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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

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

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

Скачать.

Симуляция

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

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

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

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

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

Апрель 23, 2016 г.

Wordpress XMLRPC DOS атака

Хакеры ищут разные пути взлома ваших сайтов. В большистве случаев, если только сайт не представляет какой то коммерческой ценности, это резвятся детишки, ...

Читать
Март 24, 2016 г.

Как в phpMyadmin увеличить размер импортируемого файла

Отличная утилита для администрирования баз данных phpMyAdmin используется как на профессиональных хостингах, так и начинающими веб-программистами. Этой ...

Читать

 

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




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