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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

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

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

Скачать.

Симуляция

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

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

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

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

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

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

Настройка ЧПУ в CMS

Август 3, 2015 г.

Как я напишу позднее, ЧПУ - один из факторов учитываемых в SEO. А пока как программист подскажу специалистам в SEO, где искать настройки ЧПУ в популярных CMS. Начну с рассказа о двух хорошо мне знакомых CMS, потом буду по мере возможности дополнять ...

Читать

Набор номера на смартфоне при нажатии на номер телефона на сайте

Сентябрь 10, 2015 г.

Мне казалось, что это естественная фича сотовых, когда тыкаешь в какое то число на странице сайта в мобильном браузере - он пытается с ним что то делать, предлагая свои обычные варианты - послать СМС или позвонить. Оказалось, что это не совсем ...

Читать

 

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

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



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