Чтобы убедить вас, что метод генетических алгоритмов — это очень простая штука, был создан данный пример. Мы найдем с помощью генетического алгоритма, что кратчайший путь между двумя точками — это прямая.
Постановка задачи:
Заданы две точки на плоскости A и B. Между ними через N точек проложен маршрут. Нужно оптимизировать (минимизировать) путь, используя генетический алгоритм.
Решение:
Опираясь на выводы прошлой статьи о генетических алгоритмах, мне понадобятся: начальное решение (одно или несколько), метод отбора и методы генерации новых потомков.
Начальное решение:
Я случайно задам на плоскости N точек маршрута, соединяющего точки А и B.
|
1 2 3 4 |
//массив точек, здесь N - кол-во промежуточных точек var pts = []; while (pts.length < N) pts.push([Math.random(), Math.random()]); |
Метод отбора:
Мы будем убирать из популяции самых длинных агентов (особей, маршрутов).
Но перед тем как убрать их от туда, надо измерить длину пути:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//координаты точек А и B var A = [0.2, 0.5]; var B = [0.8, 0.5]; //аккумулятор длины var size = 0; var lastP = A; //начинается маршрут с точки А pts = ... //здесь у нас массив точек одного из агентов for (var k=0; k < N; k++) { //прибавляем отрезок пути - это гипотенуза = корень из квадрата катетов size += Math.sqrt(Math.pow(lastP[0] - pts[k][0], 2) + Math.pow(lastP[1] - pts[k][1], 2)); lastP = pts[k]; } //завершается маршрут в точке B size += Math.sqrt(Math.pow(lastP[0] - B[0], 2) + Math.pow(lastP[1] - B[1], 2)); /* теперь size содержит длину пути */ |
Генерация потомков.
Простейшая мутация — это смещение одной или нескольких точек агента в произвольном направлении. Можно также реализовать кроссовер, скрещивание — будем брать часть одного маршрута и присоединять к нему часть другого маршрута.
Я реализовал и мутацию и кроссовер. В исходном коде это два метода класса GASIMLINE.
addMutant — имитирует мутацию.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//мы передаём номер агента в массиве, который является //отправной точкой для мутации this.addMutant = function(agentIndex) { //клонируем объект var newAgent = JSON.parse(JSON.stringify(this.agents[agentIndex])); //выполняем изменение нескольких координат for (k = 0; k < Math.floor(1 + Math.random() * Math.sqrt(this.N)); k++ ) { var mutPosIndex = Math.floor(Math.random() * this.N); var rMut = 0.10 * Math.random(); var alphaMut = 2 * Math.PI * Math.random(); //apply mutation newAgent.p[mutPosIndex][0] += rMut * Math.sin(alphaMut); newAgent.p[mutPosIndex][1] += rMut * Math.cos(alphaMut); } //добавляем агента в популяцию this.agents.push(newAgent); } |
addCrossOver — имитирует скрещивание.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//нам нужны два агента для обмена генетической информацией this.addCrossOver = function (agentIndex1, agentIndex2) { //узнаём какую часть возьмем из первого предка var mutPosIndex = Math.floor(Math.random() * this.N); //клонирум агента var newAgent = JSON.parse(JSON.stringify(this.agents[agentIndex1])); //дописываем гены из второго предка while (mutPosIndex < this.N) { newAgent.p[mutPosIndex][0] = this.agents[agentIndex2].p[mutPosIndex][0]; newAgent.p[mutPosIndex][1] = this.agents[agentIndex2].p[mutPosIndex][1]; } //добавляем агента в популяцию this.agents.push(newAgent); } |
Где взять исходник?
Алгоритм «упакован» в специальный объект, где все и происходит. Для рендеринга картинки используется html 5 контейнер canvas. Функция прорисовки также внутри этого класса.
Симуляция
Укажите кол-во промежуточных точек в маршруте (число от 1 до 1000) и нажимите кнопку "Задать".
Кол-во промежуточных точек маршрута:
GEN - число поколений, прошедших с начала симуляции.
LEN - текущая длина в % по отношению к идеальному расстоянию.
N - число промежуточных точек маршрута.
Наша популяция состоит из 20 "особей", наиболее короткий путь прорисован жирнее.
