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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

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

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

Скачать.

Симуляция

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

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

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

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

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

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

Работаем с HTML5 тегом audio из javascript

Декабрь 21, 2015 г.

В HTML5 появился тег для вставки проигрывателя аудио-файлов. Т.е. нам уже не нужно встраивать Flash проигрыватель и т.п, можно обойтись средствами браузера для проигрывания аудио-трека (-ов). Далее я расскажу о использовании тега и работе с ним средствами ...

Читать

Когда jQuery.find может не работать

Декабрь 8, 2012 г.

Обычно, "проблема" возникает с данными, получаемыми через асинхронные запросы (ajax-запрос). Вы пытаетесь выполнить jQuery.find() для полученных данных, а функция возвращает пустой объект. В примере ниже, мы пытаемся извлечь содержимое HTML контейнера ...

Читать

 

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

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



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