Решение задач оптимизации генетическими алгоритмами на примере задачи коммивояжера

Размещено на http://www.allbest.ru/

Санкт-Петербургский Государственный Политехнический Университет

кафедра прикладной математики

Курсовая работа по методам оптимизации:

«Решение задач оптимизации генетическими алгоритмами

на примере задачи коммивояжера»

Студент Кацман Виктор, группа 33601/2

• Оглавление
• Введение
• 1. Постановка задачи
• 1.1 Общее описание задачи
• 1.2 Формальная постановка
• 2. Общее описание генетического алгоритма
• 2.1 Формализация задачи для решения генетическим алгоритмом
• 2.2 Общая схема алгоритма
• 2.3 Подробный разбор некоторых элементов алгоритма
• 3. Описание алгоритмов решения задачи
• 3.1 Алгоритм полного перебора
• 3.2 Алгоритм динамического программирования
• 3.3 Генетический алгоритм
• 4. Описание исследований и их результатов
• 4.1 Перечень тестировавшихся алгоритмов
• 4.2 Тест на задачах малой размерности
• 4.3 Тест на задачах средней размерности
• 4.4 Тест на задачах высокой размерности
• 4.5 Тест для исследования «алгоритма повторных применений» генетического алгоритма
• Выводы
• Литература
• Введение
• Данная работа посвящена исследованию возможности решать дискретные оптимизационные задачи с помощью генетических алгоритмов. Исследования проводились на примере решения «несимметричной незамкнутой задачи коммивояжера» - известной комбинаторной NP-трудной задачи, для которой наилучший известный на данный момент точный алгоритм работает с асимптотикой O(2^n). В ходе исследований результаты работы генетического алгоритма сравнивались с результатами работы с решением «несимметричной незамкнутой задачи коммивояжера» динамическим программированием по таким параметрам, как время работы, точность результата и объем используемой памяти на различных входных данных.

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

1.1 Общее описание задачи

Коммивояжер - странствующий торговец должен объехать N городов. Известны затраты на переезд между i-ым и j-ым городами, которые заданы в виде матрицы C = (c[i][j]), i = 1..N, j = 1..N. Коммивояжер должен объехать все города один раз. Требуется определить, в каком порядке следует объезжать города, чтобы суммарные затраты были минимальны.

Задача коммивояжера называется симметричной, если затраты на переезд между парой городов не зависят от направления переезда, в противном случае задача несимметрична.

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

1.2 Формальная постановка

На вход получаем матрицу затрат C = (c[i][j]), i = 1..N, j = 1..N, c[i][j] - затраты на переезд из i-го города в j-ый, c[i][j] неотрицательно, ограниченно; при желании запретить переезд из i-го города в j-ый следует сделать c[i][j] максимально большим.

Существует несколько вариантов выбора переменных для данной задачи:

1. В качестве переменных выбираем элементы матрицы переездов X = (x[i][j]), i = 1..N, j = 1..N, x[i][j] = {0,1}; x[i][j] = 1, если переезд из i-го города в j-ый включается в маршрут и x[i][j] = 0, если переезд из i-го города в j-ый не включается в маршрут. Получаем следующую задачу:

2. В качестве переменных выбираем элементы «вектора номеров городов» X = (x[i]), i = 1..N, x[i] ; ЃНj ? k: x[j] ? x[k]. Получаем следующую задачу:

2. Общее описание генетического алгоритма

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

2.1 Формализация задачи для решения генетическим алгоритмом

Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов, где каждый ген может быть битом, числом или неким другим объектом. В классических реализациях генетического алгоритма предполагается, что генотип имеет фиксированную длину. Также существуют вариации генетического алгоритма, свободные от этого ограничения.

Применительно к «задаче коммивояжера» для решения её генетическим алгоритмом лучше выбрать представление переменных в виде «вектора номеров городов».

2.2 Общая схема алгоритма

НАЧАЛО

Создать начальную совокупность структур (популяцию)

Оценить каждую структуру

остановка := FALSE

ПОКА НЕ остановка ВЫПОЛНЯТЬ

НАЧАЛО

Применить оператор отбора

ПОВТОРИТЬ (F(размер популяции)) РАЗ

НАЧАЛО

Выбрать две структуры (родители) из множества предыдущей итерации

Применить оператор кроссовера к выбранным структурам и получить две новые структуры (потомки)

Оценить эти новые структуры

Поместить потомков в новое поколение

КОНЕЦ

Применить оператор мутации

ЕСЛИ С(популяция) ТО остановка := TRUE

КОНЕЦ

КОНЕЦ

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

F(размер популяции) - функция от размеров текущей популяции, возвращает неотрицательное целое число.

С(популяция) - функция от текущей популяции, проверяет, сошлась ли она или нет, возвращает true/false.

2.3 Подробный разбор некоторых элементов алгоритма

1. Создание начальной популяции:

Перед первым шагом нужно случайным образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, вероятно, что генетический алгоритм все равно достаточно быстро переведет её в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности.

2. Оператор кроссовера:

Оператор, который для двух выбранных родителей (обычно двух) вычисляет потомков так, чтобы они унаследовали общие черты родителей, а остальные черты смешали бы каким-либо особым образом.

3. Оператор мутации:

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

4. Оператор отбора:

На этапе отбора нужно из всей популяции выбрать определённую её долю, которая останется «в живых» на этом этапе эволюции и примет участие в следующем этапе развития. Критерий отбора, как правило, в основном использует функцию приспособленности, но при этом также может использовать некоторые особенности конкретной особи.

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

Функция приспособленности - целевая функция для данного вектора (особи).

3. Описание алгоритмов решения задачи

3.1 Алгоритм полного перебора

Заключается в полном переборе всевозможных маршрутов коммивояжера и выборе самого оптимального из них. Данный алгоритм позволяет получить точное решение задачи, использует O(N^2) памяти (память нужна для матрицы С и одного вектора Х). Однако данный алгоритм является очень трудоемким по времени работы, поскольку всего существует N! различных маршрутов, и использовать его имеет смысл только при N < 15. В данной работе он использовался для тестирования результатов других алгоритмов при маленьких N.

//solution_t - структура для хранения решений

solution_t base_solve::solve ()

{

res->size = N;

res->min = UINT_MAX;

for (int i = 1; i <= res->size; i++) {res->result[i] = i;}

rightSolve (1, res->size);

return res;

}

void base_solve::recursion (l, r)

{

arr = res->result;

if (l == r)

{

rest = 0;

for (i = 1; i < G.size; i++)

{

rest += G.graph[arr[i]][arr[i+1]];

}

if (rest < res->min)

{

res->min = rest;

}

return;

}

for (i = l; i <= r; i++)

{

v = arr[l]; arr[l] = arr[i]; arr[i] = v;

rightSolve (l+1, r);

v = arr[l]; arr[l] = arr[i]; arr[i] = v;

}

return;

}

3.2 Алгоритм динамического программирования

В основе алгоритма лежит идея сравнения различных вариантов допустимых решений задачи (по значению целевой функции) не в конце построения множества всех возможных вариантов, а на каждом шаге построения возможных вариантов (подзадаче).

Для «задачи коммивояжера» удобно выбрать следующие подзадачи и пересчет (способ перехода от одной подзадачи к другой):

Подзадачи: для подмножества городов S из {1..N}, и j ? S, обозначим через D[S,j] длину кратчайшего пути, проходящего через все города S и заканчивающегося в j.

Пересчет: D[S,j] =

Данный алгоритм позволяет получить точное решение задачи, использует O(N*2^N) памяти (память нужна для матриц C и D, а вариантов множества S - 2^N) и работает за O(N*2^N), так как должны заполниться все ячейки матрицы D. Таким образом, с помощью динамический алгоритм решения «задачи коммивояжера» можно использовать при N < 25. В данной работе он использовался для оценки точности результатов генетического алгоритма.

//B - матрица D

//Bj - матрица, в которой хранятся индексы последних городов на соответствующих маршрутах в D

solution_t *dinamic_solve::solve ()

{

res->size = N;

res->min = UINT_MAX;

B_length = 1 << res->size;

for (i = 1; i < B_length; i++)

{

for (j = 1; j <= res->size; j++)

{

B[i][j] = -1;

}

}

B[1][1] = 0;

k = 1;

for (i = 1; i <= res->size; i++)

{

B[k][i] = 0;

Bj[k][i] = i;

k <<= 1;

}

res->min = INT_MAX;

for (i = 1; i <= res->size; i++)

{

cr = rightSolve(B_length-1, i);

if (cr < res->min)

{

res->min = cr;

last = i;

}

}

res->result[res->size] = last;

j = B_length-1;

for (i = 1; i < res->size; i++)

{

j = j^(1 << (last - 1));

last = Bj[j][last];

res->result[res->size - i] = last;

}

return res;

}

dinamic_solve::rightSolve(unt mask,unt last)

{

&rest = B[mask][last];

&resj = Bj[mask][last];

if(rest == -1)

{

mask ^= (1 << (last-1));

rest = UINT_MAX;

for (unt i = 1; i <= res->size; i++)

{

if (mask & (1 << (i-1)))

{

unt cr = rightSolve(mask, i) + G.graph[i][last];

if (cr < rest) {rest = cr; resj = last; Bj[mask][last] = i;}

}

}

}

return rest;

}

3.3 Генетический алгоритм

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

1. Вид элемента популяции:

В качестве элемента популяции взята переменная в виде «вектора номеров городов». Данный выбор представляется удачным, поскольку он использует минимально возможный объем памяти O(N) (меньшим объемом невозможно описать путь коммивояжера через N городов) и позволяет производить за линейное время такие операции, как вычисление на нем функции приспособленности, кроссовер, мутация и т.д.

2. Создание начальной популяции:

Для создания начальной популяции создается набор из (2N - 2) особей, из которых затем отбираются N лучших.

Набор создается так:

· Первые N особей представляют собой маршруты, полученные из циклического маршрута обхода городов в порядке возрастания индекса (за исключением перехода из последнего в первый) выбрасыванием пути между двумя соседними городами

// generation - массив популяции

// generation[i]->result - маршрут i-ой особи

for (i = 0; i < N; i++)

{

for (j = 0; j < i; j++)

{

generation[i]->result[j + 1] = N + 1 - i + j;

}

for (j = i; j < N; j++)

{

generation[i]->result[j + 1] = j - i + 1;

}

}

· Последующие (N - 2) особи представляют собой маршруты, начинающиеся из последнего города и проходящие затем через несколько городов в порядке убывания индексов; далее маршрут включает в себя первый город и оставшиеся города в порядке возрастания индексов

// generation - массив популяции

// generation[i]->result - маршрут i-ой особи

for (i = N; i < 2*N - 2; i++)

{

i0 = i - N + 2;

for (j = 0; j < i0; j++)

{

generation[i]->result[j + 1] = i0 - j;

}

for (j = i0; j < N; j++)

{

generation[i]->result[j + 1] = j + 1;

}

}

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

Оценка трудоемкости работы алгоритма: O(N^2).

3. Оператор кроссовера:

Перед описанием используемых в данной работе операторов кроссовера приведено описание процедуры построения «сжатых» родителей.

Процедура заключается в следующем: для пары родителей находятся общие участки их маршрутов (участки, которые присутствуют у обоих родителей) и стягиваются в один элемент, эквивалентный городу. Получается два новых маршрута, не содержащих одинаковых участков, из которых рождается потомство. Далее стянутые элементы раскладываются в исходные участки маршрута и попадают в потомство (для этого используется отдельная «процедура раскладывания»). В результате получается, что потомство содержит в себе все общие черты родителей. Также, поскольку «сжатые» родители содержат меньше элементов, чем исходные родители - городов, процедура кроссовера будет работать быстрее.

Процедура построения «сжатых» родителей состоит из следующих этапов:

· Построение ссылок - векторов[1..N], содержащих на i-ом месте позицию города с i-ым индексом в исходном маршруте. Делается одновременно для обоих родителей.

// prnt1/2->result - маршрут первого / второго родителя

// links_to_vertices1/2 - вектор ссылок для первого / второго родителя

links_size = N;

for (i = 1; i <= links_size; i++)

{

links_to_vertices1[prnt1->result[i]] = i;

links_to_vertices2[prnt2->result[i]] = i;

}

· Построение «сжатых» родителей. Основано на проходе по маршруту одного из родителей и сравнению городов, в которые родительские маршруты приведут после покидания общего города.

// zip_prnt - структура данных, содержащая информацию о сжатых участках

// zip_prnt[i].vertex - массив, содержащий информацию о городах, входящих в i-ый элемент

// сжатого родителя

// prnt1/2->result - маршрут первого / второго родителя

// links_to_vertices1/2 - вектор ссылок для первого / второго родителя

// zip_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке,

// отвечающему исходным маршрутам

counter = 0;

vertex_counter = 0;

zip_size = 0;

for (i = 2; i <= links_size + 1; i++)

{

zip_prnt[counter].size = 1;

zip_prnt[counter].number = counter;

zip_prnt[counter].vertex[0] = prnt1->result[i - 1];

zip_links_1[counter] = counter;

vertex_counter = 0;

zip_numbers[i - 1] = counter;

while ((i <= links_size) &&

(prnt1->result[i] == prnt2->result[links_to_vertices2[prnt1->result[i - 1]] + 1]))

{

zip_prnt[counter].size++;

zip_prnt[counter].vertex[++vertex_counter] = prnt1->result[i++];

zip_numbers[i - 1] = counter;

}

counter++;

zip_size++;

}

counter = 0;

vertex_counter = 0;

for (i = 2; i <= links_size + 1; i++)

{

zip_links_2[counter] = zip_numbers[links_to_vertices1[prnt2->result[i - 1]]];

while ((i <= links_size) &&

(prnt2->result[i] == prnt1->result[links_to_vertices1[prnt2->result[i - 1]] + 1]))

{

i++;

}

counter++;

}

Данная процедура использует линейное время и память; в связи с этим она асимптотически не усложняет оператор кроссовера и её использование кажется очень удачным.

Перейдем к «процедуре раскладывания». Она состоит в проходе по «сжатому» потомку; в ходе прохода для каждого элемента находится соответствующий ему участок маршрута (он может состоять из одного или нескольких городов) и добавляется в итоговый вариант соответствующего потомка.

// zip_prnt - массив, содержащий информацию о сжатых участках

// g_son1/2->result - маршрут первого / второго потомка

// zip_res_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке,

// отвечающему исходным маршрутам

counter1 = 1, counter2 = 1;

for (i = 0; i < zip_size; i++)

{

current_zip1 = zip_res_links_1[i];

current_zip2 = zip_res_links_2[i];

for (j = 0; j < zip_prnt[current_zip1].size; j++)

{

g_son1->result[counter1++] = zip_prnt1[current_zip1].vertex[j];

}

for (j = 0; j < zip_prnt[current_zip2].size; j++)

{

g_son2->result[counter2++] = zip_prnt1[current_zip2].vertex[j];

}

}

Для исследования работы генетического алгоритма использовались следующие варианты кроссоверов (все варианты для двух родителей):

· Кроссовер по одной точке. Выполняем процедуру построения «сжатых» родителей. Проходим по элементам родителей, начиная от первого в порядке их следования в маршруте. Находится первый несовпадающий у родителей элемент. Два полученных в результате такого кроссовера потомка будут копиями родителей, за исключением двух элементов. Во-первых - первого несовпадающего элемента, замененного первым несовпадающим элементом другого родителя, во-вторых: элементом, на месте которого стоял элемент с индексом равным индексу первого несовпадающего элемента другого родителя (так, чтобы в маршруте потомков встречались все города).

// zip_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке,

// отвечающему исходным маршрутам

// zip_res_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке,

// отвечающему результирующим маршрутам потомков

// zip_size - размер сжатого родителя

if (zip_size == 1)

{

выход; //родители совпадают

}

for (i = 0; i < zip_size; i++)

{

zip_res_links_1[i] = zip_res_links_2[i] = -1;

}

i = 0;

while (zip_links_1[i] == zip_links_2[i])

{

zip_res_links_1[i] = zip_res_links_2[i] = zip_links_1[i++];

}

pnt1 = zip_res_links_2[i] = zip_links_1[i], i2 = i + 1;

pnt2 = zip_res_links_1[i] = zip_links_2[i], i1 = i + 1;

while (zip_links_1[i1] != pnt2)

{

zip_res_links_1[i1] = zip_links_1[i1++];

}

zip_res_links_1[i1++] = pnt1;

while (i1 < zip_size)

{

zip_res_links_1[i1] = zip_links_1[i1++];

}

while (zip_links_2[i2] != pnt1)

{

zip_res_links_2[i2] = zip_links_2[i2++];

}

zip_res_links_2[i2++] = pnt2;

while (i2 < zip_size)

{

zip_res_links_2[i2] = zip_links_2[i2++];

}

Выполняем процедуру «раскладывания».

При использовании данного кроссовера мы всегда будем получать потомка отличающегося двумя городами от исходного (за исключением случая полностью совпадающих родителей). Недостатком такого кроссовера является небольшой диапазон возможных результатов при его многократном применении.

· Кроссовер по двум точкам. Выполняем процедуру построения «сжатых» родителей. Проходим по элементам родителей, начиная от первого в порядке их следования в маршруте. Находится первый несовпадающий у родителей элемент. Два полученных в результате такого кроссовера потомка будут копиями родителей, за исключением двух элементов. Во-первых - первого несовпадающего элемента, замененного первым несовпадающим элементом другого родителя, во-вторых: элементом, на месте которого стоял элемент с индексом равным индексу первого несовпадающего элемента другого родителя (так, чтобы в маршруте потомков встречались все города). Теперь проходим по элементам родителей, начиная от последнего в порядке обратном порядку их следования в маршруте. Находится первый несовпадающий у родителей элемент. Два полученных в результате такого кроссовера потомка будут копиями родителей, за исключением двух элементов. Во-первых - первого несовпадающего элемента, замененного первым несовпадающим элементом другого родителя, во-вторых: элементом, на месте которого стоял элемент с индексом равным индексу первого несовпадающего элемента другого родителя (так, чтобы в маршруте потомков встречались все города).

// zip_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке,

// отвечающему исходным маршрутам

// zip_res_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке,

// отвечающему результирующим маршрутам потомков

// zip_size - размер сжатого родителя

if (zip_size < 6)

{

выход; //родители слишком похожи, используем другой оператор кроссовера

}

// при размере потомства большем 5 оператор кроссовера непременно выдаст потомство, не совпадающее с родителями, поскольку из 6 и большего числа элементов невозможно составить два вектора так, чтобы они отличались только двумя элементами, и элементы стояли бы так, чтобы пара соседних элементов одного сжатого родителя не совпадала с парой соседних элементов другого родителя (при просмотре в одном направлении). Это условие возникает из того, что сжатые родители не содержат одинаковых участков маршрута, эти участки были выявлены в процедуре сжатия

for (i = 0; i < zip_size; i++)

{

zip_res_links_1[i] = zip_res_links_2[i] = -1;

}

i = 0;

while (zip_links_1[i] == zip_links_2[i])

{

zip_res_links_1[i] = zip_res_links_2[i] = zip_links_1[i++];

}

pnt1 = zip_res_links_2[i] = zip_links_1[i], i2 = i + 1;

pnt2 = zip_res_links_1[i] = zip_links_2[i], i1 = i + 1;

while (zip_links_1[i1] != pnt2)

{

zip_res_links_1[i1] = zip_links_1[i1++];

}

zip_res_links_1[i1++] = pnt1;

while (i1 < zip_size)

{

zip_res_links_1[i1] = zip_links_1[i1++];

}

while (zip_links_2[i2] != pnt1)

{

zip_res_links_2[i2] = zip_links_2[i2++];

}

zip_res_links_2[i2++] = pnt2;

while (i2 < zip_size)

{

zip_res_links_2[i2] = zip_links_2[i2++];

}

i = zip_size - 1;

while (zip_res_links_2[i] == zip_res_links_1[i]) {i--;}

pnt1 = zip_res_links_2[i] = zip_links_1[i]; i2 = i - 1;

pnt2 = zip_res_links_1[i] = zip_links_2[i]; i1 = i - 1;

while (zip_links_1[i1] != pnt2){i1--;}

zip_res_links_1[i1++] = pnt1;

while (zip_links_2[i2] != pnt1){i2--;}

zip_res_links_2[i2++] = pnt2;

Выполняем процедуру «раскладывания».

При использовании данного кроссовера мы всегда будем получать потомка отличающегося нулем, двумя, тремя или четырьмя городами от исходного (При больших родителях значительно чаще будет реализовываться случай с четырьмя отличающимися городами). Данный кроссовер содержит больший диапазон возможных результатов, чем одноточечный, но тоже небольшой. Также при его использовании есть достаточно большая вероятность получения потомков, совпадающих с родителями и поэтому его желательно не применять при похожих родителях, пользуясь в этом случае другим кроссовером.

· Кроссовер по частям. Выполняем процедуру построения «сжатых» родителей. Строим вектора ссылок - вектора[1..N], содержащие на i-ом месте позицию элемента с i-ым индексом в исходном маршруте (вектора ссылок строятся одновременно для обоих родителей).

// links_to_vertices1/2 - вектор ссылок для первого / второго родителя

// zip_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке,

// отвечающему исходным маршрутам

for (i = 0; i < zip_size; i++)

{

links_to_vertices1[zip_links_1[i]] = i;

links_to_vertices2[zip_links_2[i]] = i;

}

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

// links_to_vertices1/2 - вектор ссылок для первого / второго родителя

// zip_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке,

// отвечающему исходным маршрутам

// zip_res_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке,

// отвечающему результирующим маршрутам потомков

// zip_size - размер сжатого родителя

for (i = 0; i < zip_size; i++)

{

zip_res_links_1[i] = zip_res_links_2[i] = -1;

}

flag = 0;

for (i = 0; i < zip_size; i++)

{

if (zip_res_links_1[i] == -1)

{

if (flag == 0)

{

flag = 1;

j = i;

zip_res_links_1[i] = zip_links_2[j];

while (zip_links_1[i] != zip_links_2[j])

{

j = links_to_vertices1[zip_links_2[j]];

zip_res_links_1[j] = zip_links_2[j];

}

}

else

{

flag = 0;

j = i;

zip_res_links_1[i] = zip_links_1[j];

while (zip_links_2[i] != zip_links_1[j])

{

j = links_to_vertices2[zip_links_1[j]];

zip_res_links_1[j] = zip_links_1[j];

}

}

}

}

flag = 0;

for (i = 0; i < zip_size; i++)

{

if (zip_res_links_2[i] == -1)

{

if (flag == 0)

{

flag = 1;

j = i;

zip_res_links_2[i] = zip_links_1[j];

while (zip_links_2[i] != zip_links_1[j])

{

j = links_to_vertices2[zip_links_1[j]];

zip_res_links_2[j] = zip_links_1[j];

}

}

else

{

flag = 0;

j = i;

zip_res_links_2[i] = zip_links_2[j];

while (zip_links_1[i] != zip_links_2[j])

{

j = links_to_vertices1[zip_links_2[j]];

zip_res_links_2[j] = zip_links_2[j];

}

}

}

}

Выполняем процедуру «раскладывания».

Кроссовер по частям дает возможность получить потомство, состоящее только из частей исходных родителей. Таким образом, он лучше отвечает контексту «задачи коммивояжера», чем точечные кроссоверы. Его минус заключается в том, что при невозможности разбить родительские маршруты на участки, содержащие одинаковые наборы вершин (можно «разбить» только на одну часть), мы получим потомство, совпадающее с родителями.

Все три вида оператора кроссовера используют O(N) памяти и работают за O(N) (все процедуры, используемые в кроссовере - линейные).

4. Оператор мутации:

Для исследования работы генетического алгоритма использовались следующие варианты мутаций:

· Мутация для одной особи по одному городу («циклическая»): выбирается произвольный город с индексом V и некоторое натуральное число K, не большее N. Выбранный город перемещается на K позиций по зацикленному маршруту особи (из последнего города маршрут ведет в первый).

// vec->result - маршрут мутирующей особи

// new_vec->result - маршрут мутировавшей особи

vertex = vec->result[V];

put_place = (V + K <= vec->size) ? (V + K) : ((V + K) % vec->size);

if (K > N - V)

{

for (i = V + 1; i <= N; i++)

{

new_vec->result[i-1] = vec->result[i];

}

new_vec->result[N] = vec->result[1];

K = K - (N - V) - 1;

for (i = 1; i <= K; i++)

{

new_vec->result[i] = vec->result[i+1];

}

new_vec->result[K + 1] = vertex;

for (i = K + 2; i < V; i++)

{

new_vec->result[i] = vec->result[i];

}

}

else

{

for (i = 1; i < V; i++)

{

new_vec->result[i] = vec->result[i];

}

for (i = V + 1, cnt = V + K; i <= cnt; i++)

{

new_vec->result[i-1] = vec->result[i];

}

new_vec->result[V + K] = vertex;

for (i = V + K + 1; i <= N; i++)

{

new_vec->result[i] = vec->result[i];

}

}

· Мутация для одной особи по одному городу («не циклическая»): выбирается произвольный город с индексом V и некоторое натуральное число K, не большее расстояния от города с индексом V до последнего города в маршруте особи. Выбранный город перемещается на K позиций по маршруту особи.

// vec->result - маршрут мутирующей особи

// new_vec->result - маршрут мутировавшей особи

vertex = vec->result[V];

for (i = 1; i < V; i++)

{

new_vec->result[i] = vec->result[i];

}

for (i = V + 1, cnt = V + K; i <= cnt; i++)

{

new_vec->result[i-1] = vec->result[i];

}

new_vec->result[num V + K] = vertex;

for (i = V + K + 1; i <= N; i++)

{

new_vec->result[i] = vec->result[i];

}

· Мутация для одной особи по двум городам («циклическая»): вызываются две «циклические» мутации для одной особи по одному городу для разных городов.

· Мутация для одной особи по двум городам («не циклическая»): вызываются две «не циклические» мутации для одной особи по одному городу для разных городов.

· Мутация для одной особи по двум городам («смешенная»): вызываются две «циклическая» и «не циклическая» мутации для одной особи по одному городу для разных городов.

Выбранные операторы мутаций имеют временную трудоемкость O(N) и требуют O(N) памяти.

«Циклическая» мутация для одной особи по одному городу позволяет равновероятно получить любую особь, отличающуюся от данной двумя участками маршрута. «Не циклическая» мутация для одной особи по одному городу позволяет перемещение городов из начала маршрута в конец, но не наоборот. Таким образом, вероятность перемещения какого-либо города в конец больше, чем в начало. При большом количестве применений данной мутации такое неравноправие безусловно уравновешивается, но, для количества особей в одном мутирующем поколении для этого может быть недостаточно.

5. Оператор отбора:

Отбор происходит исключительно по значению функции приспособленности: отбираются N наилучших маршрутов. Реализация основана на выборе N-ой статистики выборки из значений функции приспособленности (трудоемкость O(M)) и последующем отборе особей, значение функции приспособленности для которых не больше N-ой статистики (трудоемкость O(M)). M - количество особей перед отбором, в данной реализации алгоритма M N^2.

Алгоритм поиска N-ой статистики:

partition (arr, l, r)

{

x = arr[r];

i = l - 1;

for (j = l; j < r - 1; j++)

{

if (arr[j] <= x)

{

i++;

if (i != j)

{

arr[j] += arr[i];

arr[i] = arr[j] - arr[i];

arr[j] = arr[j] - arr[i];

}

}

}

i++;

if (i != r){ arr[r] += arr[i]; arr[i] = arr[r] - arr[i]; arr[r] = arr[r] - arr[i];}

return i;

}

rand_partition (arr, l, r)

{

i = rand () % (r - l) + l;

if (i != r){ arr[r] += arr[i]; arr[i] = arr[r] - arr[i]; arr[r] = arr[r] - arr[i];}

return partition (arr, l, r);

}

choose_i_min (arr, l, r, i)

{

if (l == r) return arr[l];

q = rand_partition (arr, l, r);

k = q - l + 1;

if (i == k) return arr[k];

else if (i < k) return choose_i_min (arr, l, q - 1, i);

else return choose_i_min (arr, q + 1, r, i - k);

}

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

6. Критерий сходимости популяции:

В исследованиях использовалось два критерия сходимости популяции: по прохождении определенного числа итераций и по достижению модулем разности между минимальным значением функции приспособленности и N-ой статистики выборки из функций приспособленности всех особей числа меньшего некоторого ? > 0.

7. Код основной части алгоритма:

solution_not_found = 1;

while (solution_not_found)

{

for (i = 0; i < cur_size; i++) {arr[i] = generation[i]->min;}

k_min = choose_i_min (arr, 0, cur_size - 1, G.size);

с = 0;

for (i = 0; i < cur_size; i++)

{

if (generation[i]->min <= k_min && с <= G.alloc*2)

{

ext = generation[i];

generation[i] = generation[с];

generation[с++] = ext;

}

}

cur_size = с;

//crossover

for (i = 0; i < cur_size; i++)

{

for (j = i+1; j < cur_size; j++)

{

if (!isEqual(generation[i], generation[j]))

{

if (crossover(generation[i], generation[j], &(generation[с]), &(generation[с + 1])))

с += 2;

}

}

}

cur_size = с;

//mytations

gsl min_genmin = UINT_MAX;

for (i = 0; i < cur_size; i++) {

if (min_genmin > generation[i]->min) {min_genmin = generation[i]->min;}

}

if (mytations)

{

for (i = 0; i < cur_size; i++)

{

if (generation[i]->min == min_genmin) continue;

ext3 = mytation (generation[i], ext1, ext2);

ext = generation[i];

generation[i] = ext3;

ext3 = ext;

}

}

min_genmin = UINT_MAX;

for (i = 0; i < cur_size; i++) {

if (min_genmin > generation[i]->min) {min_genmin = generation[i]->min; solution_ind = i;}

}

if (min_genmin + eps > k_min) solution_not_found = 0;

}

8. Оценки алгоритма:

Таким образом, описанная выше реализация генетического алгоритма использует:

· O(N^3) памяти: O(N) требуется для хранения одной особи, максимально возможный размер популяции (перед отбором) составляет O(N^2).

· O(N^3) времени на одну итерацию (наибольшее время уходит на кроссовер: требуется O(N^2) операций кроссовера, трудоемкость каждой из которых O(N))

Оценка трудоемкости всего алгоритма зависит от выбранного критерия сходимости популяции: в случае выбора первого критерия - O(N^3 * M), где M - число итераций; в случае второго критерия теоретическая оценка затруднительна в связи с разнообразным набором возможных входных данных, практическая оценка будет приведена ниже.

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

4. Описание исследований и их результатов

4.1 Перечень тестировавшихся алгоритмов

Таблица 4.1

Номер алгоритма	Описание
1	Алгоритм полного перебора
2	Алгоритм динамического программирования
3	Генетический алгоритм с кроссовером «по частям», «цикличекой» мутацией для двух городов и 1 итерацией
4	Генетический алгоритм с кроссовером «по частям», «цикличекой» мутацией для двух городов и 2 итерациями
5	Генетический алгоритм с кроссовером «по частям», «цикличекой» мутацией для двух городов и 5 итерациями
6	Генетический алгоритм с одноточечным кроссовером, «цикличекой» мутацией для одного города и вторым критерием сходимости
7	Генетический алгоритм с одноточечным кроссовером, «не цикличекой» мутацией для одного города и вторым критерием сходимости
8	Генетический алгоритм с одноточечным кроссовером, «цикличекой» мутацией для двух городов и вторым критерием сходимости
9	Генетический алгоритм с одноточечным кроссовером, «не цикличекой» мутацией для двух городов и вторым критерием сходимости
10	Генетический алгоритм с одноточечным кроссовером, «смешенной» мутацией для двух городов и вторым критерием сходимости
11	Генетический алгоритм с двухточечным кроссовером, «цикличекой» мутацией для одного города и вторым критерием сходимости
12	Генетический алгоритм с двухточечным кроссовером, «не цикличекой» мутацией для одного города и вторым критерием сходимости
13	Генетический алгоритм с двухточечным кроссовером, «цикличекой» мутацией для двух городов и вторым критерием сходимости
14	Генетический алгоритм с двухточечным кроссовером, «не цикличекой» мутацией для двух городов и вторым критерием сходимости
15	Генетический алгоритм с двухточечным кроссовером, «смешенной» мутацией для двух городов и вторым критерием сходимости
16	Генетический алгоритм с кроссовером «по частям», «цикличекой» мутацией для одного города и вторым критерием сходимости
17	Генетический алгоритм с кроссовером «по частям», «не цикличекой» мутацией для одного города и вторым критерием сходимости
18	Генетический алгоритм с кроссовером «по частям», «цикличекой» мутацией для двух городов и вторым критерием сходимости
19	Генетический алгоритм с кроссовером «по частям», «не цикличекой» мутацией для двух городов и вторым критерием сходимости
20	Генетический алгоритм с кроссовером «по частям», «смешенной» мутацией для двух городов и вторым критерием сходимости
21	Генетический алгоритм с кроссовером «по частям», без мутаций и вторым критерием сходимости

4.2 Тест на задачах малой размерности

Данный тест представляют собой «несимметричные незамкнутые задачи коммивояжера» при количестве городов не больше 10, даются программе на вход в виде матрицы затрат. Использовался этот тест для уверенности в правильности работы точных алгоритмов перебора и динамического программирования, а также для исследования работы генетического алгоритма на задачах малой размерности.

Тест включает в себя по 100 задач каждой из размерностей 5, 6, 7, 9, 10, матрица ограничений содержит значения от 0 до 1000.

Результаты тестов (в левом столбце указаны номера алгоритмов, в остальных - результаты для соответствующей размерности входных данных; в ячейке указано время работы в тактах процессора и точность результата в виде частного разности между полученными и точными решениями и 1000 - верхнего ограничения данных):

Таблица 4.2

№ алгоритма	5 городов	6 городов	7 городов	9 городов	10 городов
1	47940, 0	297555, 0	1999074, 0	125613126, 0	1159747715, 0
2	41012,0	125366, 0	293429, 0	2613265, 0	5285576, 0
3	245434, 0.310	329121, 0.535	352885, 0.644	548858, 1.352	597877, 1.312
4	383212, 0.210	540357, 0.423	608930, 0.483	871349, 1.013	1119372, 1.657
5	524690, 0.210	885583, 0.280	788040, 0.500	1712369, 0.727	1977881, 1.044
6	535421, 0.173	768059, 0.249	724162, 0.362	1544689, 0.682	1864501, 0.726
7	446293, 0.144	780759, 0.285	795200, 0.375	1298272, 0.859	1663050, 0.900
8	457493, 0.162	864851, 0.269	1119195, 0.359	2834889, 0.455	3380160, 0.621
9	615445, 0.195	885784, 0.263	1072128, 0.397	1871712, 0.648	2276078, 0.661
10	600075, 0.172	1002164, 0.253	989799, 0.333	2426724, 0.578	2869449, 0.641
11	463795, 0.155	727924, 0.267	737878, 0.413	1439068, 0.625	1688384, 0.850
12	384893, 0.169	718982, 0.315	668836, 0.503	1107253, 0.902	1824984, 0.970
13	731393, 0.104	904013, 0.265	1131401, 0.344	2778641, 0.561	3445356, 0.713
14	664261, 0.174	1068748, 0.277	794839, 0.446	1806951, 0.744	2347263, 0.887
15	890573, 0.172	969951, 0.232	1098898, 0.384	2056957, 0.619	2616159, 0.843
16	477237, 0.212	633770, 0.384	622857, 0.483	1244565, 0.745	1482849, 0.917
17	447806, 0.290	663264, 0.357	584099, 0.656	1068022, 0.936	1518663, 1.059
18	676178, 0.161	737040, 0.299	811023, 0.498	1810618, 0.726	1687509, 1.111
19	666856, 0.173	690027, 0.379	813683, 0.470	1754136, 0.740	2042246, 0.970
20	745182, 0.171	666424, 0.333	785375, 0.486	1786601, 0.834	1926489, 1.017
21	315644, 0.444	346189, 0.704	401958, 0.972	676170, 1.491	966292, 1.759

По результатам данного теста хорошо видна нецелесообразность использования алгоритма полного перебора для решения «задачи коммивояжера». Также можно заметить нецелесообразность использования генетического алгоритма без мутаций (21), потому как и время его работы и ошибка по сравнению с точным результатом растет быстрее, чем, например, у 3-его алгоритма (с одноточечным кроссовером и «циклической» мутацией для одного города и одной итерации).

Кроме того, из проведенных исследований следует, что для решения «задач коммивояжера» малой размерности лучше подходит алгоритм динамического программирования (и по времени и по точности).

4.3 Тест на задачах средней размерности

Данный тест представляют собой «несимметричные незамкнутые задачи коммивояжера» при количестве городов порядка 15-19, даются программе на вход в виде матрицы затрат. Использовался этот тест для исследования времени и точности работы генетического алгоритма на задачах средней размерности.

Тест включает в себя по 100 задач каждой из размерностей 15, 17, 19, матрица ограничений содержит значения от 0 до 1000.

Результаты тестов (в левом столбце указаны номера алгоритмов, в остальных - результаты для соответствующей размерности входных данных; в ячейке указано время работы в тактах процессора и точность результата в виде частного разности между полученными и точными решениями и 1000 - верхнего ограничения данных):

Таблица 4.3

№ алгоритма	15 городов	17 городов	19 городов
2	828575405, 0	4246515380, 0	21546365063, 0
3	1295253, 3.423	1685045, 4.166	2079217, 4.806
4	2228001, 2.970	2668267, 3.555	3517825, 4.137
5	3880801, 2.076	5693568, 2.548	6252386, 3.284
6	5179881, 1.574	8415665, 2.026	8612602, 2.550
7	4958129, 1.899	6020746, 2.289	8591202, 2.737
8	10007204, 1.464	12485682, 2.057	16063651, 2.507
9	7316538, 1.650	7442943, 2.435	11470503, 2.493
10	9035033, 1.425	12441862, 1.929	13588687, 2.536
11	6000724, 1.628	8024809, 1.819	11880129, 2.342
12	5195162, 1.843	6084621, 2.455	10374952, 2.439
13	11586620, 1.615	14710175, 1.874	18723471, 2.453
14	7425435, 1.602	8180333, 2.392	11759932, 2.856
15	10333317, 1.623	12357801, 2.122	16337563, 2.271
16	4556540, 1.943	5590378, 2.429	8760769, 2.496
17	4203885, 2.059	6003484, 2.466	7748776, 3.044
18	5953596, 2.005	7104790, 2.363	11222184, 2.694
19	5925075, 1.924	7754152, 2.508	8975546, 3.158
20	5961760, 1.911	8121099, 2.246	10559025, 2.718

По результатам данного теста хорошо видна нецелесообразность использования динамического программирования для решения «задачи коммивояжера» ввиду больших временных затрат. Трудоемкость работы генетического алгоритма на основе исследований составляет o(N^4), что позволяет надеяться на достаточно быстрое решение задачи высокой размерности. Плохую тенденцию представляет ухудшение точности: средняя разность между полученным и оптимальным значениями растет быстрее, чем линейно относительно N*1000 (1000 - верхняя граница данных). Для решения этой проблемы можно применять алгоритм несколько раз и брать наилучший результат, это может привести к лучшему результату в связи со случайными генерациями мутаций.

4.4 Тест на задачах высокой размерности

Данный тест представляют собой «несимметричные незамкнутые задачи коммивояжера» при количестве городов до 100, даются программе на вход в виде матрицы затрат. Использовался этот тест для исследования времени работы генетического алгоритма на задачах высокой размерности. Оценить отклонение полученного решения от точного на данных задачах затруднительно в связи с длительным временем, необходимым для получения точного решения

Тест включает в себя по 100 задач каждой из размерностей 40, 60, 80, 100 матрица ограничений содержит значения от 0 до 1000.

Результаты тестов (в левом столбце указаны номера алгоритмов, в остальных - результаты для соответствующей размерности входных данных; в ячейке указано время работы в тактах процессора):

Таблица 4.4

№ алгоритма	40 городов	60 городов	80 городов	100 городов
3	13869657	38421970	55298795	75944467
4	26485951	58478116	65362540	89778728
5	47573750	116052555	158248183	203085649
6	91932504	852802560	406025090	599689705
7	89224844	689499528	209191128	502414416
8	145264977	235647929	510230755	849701034
9	109529934	134146799	390671209	734172264
10	128015246	224339695	470048851	829701318
11	100875795	114735950	542020450	715425804
12	91671430	118870453	384195168	433715360
13	120963588	223183049	484323760	914393247
14	104692106	200380730	385446547	870083172
15	160120583	191328739	371821962	717835433
16	73306764	154243932	400560900	879946371
17	72630789	215827892	605618957	744229511
18	87109040	169618046	336987348	687957487
19	99422589	281745930	514861598	778038679
20	90700406	170255103	352518951	787416156

По результатам проведенных тестов на трудоемкость можно подвести следующие итоги по оценкам скорости работы генетического алгоритма:

· На процедуры алгоритма выполняющиеся один раз за весь алгоритм независимо от количества итераций тратится примерно треть времени от первой итерации или одноитерационного алгоритма (следует из сравнения времен, затраченных алгоритмами со сходимостью по конечному числу итераций).

· В среднем, в алгоритме со сходимостью по второму критерию проходит не более log(N)*5 итераций. Это подтверждает общую оценку трудоемкости алгоритма o(N^4).

· Оператор кроссовера «по частям» работает примерно столько же, сколько одноточечный оператор кроссовера и любой из них работает быстрее двухточечного оператора кроссовера.

· «Не циклическая» мутация по двум городам работает медленнее, чем «циклическая» мутация по одному городу и дает не лучший результат (исходя из результатов предыдущих тестов), её использование в алгоритме нецелесообразно.

· В целом, все вариации генетического алгоритма работают примерно одинаковое время, что дает возможность их комбинировать между собой без увеличения трудоемкости алгоритма.

4.5 Тест для исследования «алгоритма повторных применений» генетического алгоритма

«Алгоритм повторных применений» генетического алгоритма представляет собой решение одной и той же задачи несколько раз модификациями генетического алгоритма с последующим выбором наилучшего результата. В данном случае его использование представляется очень уместным, поскольку разные модификации генетического алгоритма для одной задачи могут дать решения сильно различающейся точности (разностью с оптимальным решением).

Задачей исследований является установить точность, которую можно будет ожидать при решении задач высокой размерности. (Время работы «Алгоритм повторных применений» генетического алгоритма можно оценить исходя из времен работы входящих в него модификаций генетического алгоритма)

Для этого исследуется точность, которую можно ожидать от решения задачи средней размерности различными комбинациями модификаций генетического алгоритма.

Тест включает в себя по 5 задач каждой из размерностей 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 матрица ограничений содержит значения от 0 до 1000.

Результаты тестов (в левом столбце указаны алгоритмы (в виде номеров входящих в них модификаций, отобраны на основе точности, показанной предыдущими тестами), в остальных - результаты для соответствующей размерности входных данных; в ячейке указана точность результата в виде частного разности между полученными и точными решениями и 1000 - верхнего ограничения данных):

Таблица 4.5

Алгоритм	11	12	13	14	15	16	17	18	19	20	21
6, 11, 16	0.460	0.351	0.648	0.707	0.837	0.654	1.339	1.344	1.637	1.525	2.314
7, 12, 17	0.402	0.606	0.811	0.896	0.855	1.248	1.420	1.537	1.660	1.524	1.934
8, 13, 18	0.335	0.488	0.699	0.710	0.869	0.938	1.191	1.269	1.285	1.085	1.851
9, 14, 19	0.641	0.767	0.605	0.665	1.012	1.107	1.044	1.400	1.565	1.422	1.656
10, 15, 20	0.410	0.584	0.689	0.722	0.932	1.149	1.035	0.921	1.140	1.230	1.475
6, 9, 12, 15, 18	0.290	0.566	0.534	0.548	0.584	0.632	1.259	1.007	1.154	1.399	1.502
7, 10, 13, 16, 19	0.427	0.335	0.429	0.432	0.545	1.018	0.942	1.032	1.006	1.069	1.423
8, 11, 14, 17, 20	0.384	0.505	0.479	0.470	0.532	0.878	1.013	1.002	1.024	1.685	1.270
6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20	0.150	0.271	0.322	0.341	0.525	0.578	0.796	0.808	1.052	0.945	0.972
10, 11, 13, 15	0.234	0.394	0.504	0.641	0.868	0.698	0.813	1.094	1.473	1.109	1.274
9, 11, 12, 13, 15, 16	0.229	0.390	0.496	0.606	0.704	0.690	0.993	0.962	1.282	0.921	1.438

По результатам проведенных тестов на точность можно подвести следующие итоги по оценкам точности работы генетического алгоритма:

· Как и ожидалось, алгоритм, включающий в себя все вариации, оказался наиболее точным (решение, возвращаемое им, ближайшее к оптимальному).

· Из мутаций наилучшую точность обеспечивают «не циклическая» по двум городам и «смешанная» по двум городам. То, что наиболее точные решения достигаются при мутациях для двух городов говорит о возможности достижения лучших результатов при увеличении числа городов, подвергающихся мутациям.

· Из кроссоверов наилучшую точность обеспечивают кроссовер «по частям» и двухточечный кроссовер, что, в сочетании с более быстрой работой кроссовера «по частям» дает преимущества в его использовании. Также, это говорит о том, что при увеличении числа городов точность решения при использовании кроссовера «по частям» наверняка будет улучшаться по сравнению с точностью решения при использовании двухточечного кроссовера (в связи с тем, что кроссовер будет влиять на расположение большего числа городов в потомстве).

· В целом, результаты позволяют ожидать точности примерно 20% от N для наилучших модификаций за достаточно быстрое время. Благодаря этому, появляется возможность оценить значение целевой функции в оптимальной точке. Теоретически, дальше можно применять различные модификации генетического алгоритма до тех пор, пока это значение не будет достигнуто, но оценить количество требуемых применений и модификации, которые следует применять затруднительно.

генетический алгоритм коммивояжер программирование

Выводы

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

Литература

1. Д.И. Батищев, С.А. Исаев. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов (1997)

2. Д.И. Батищев, С.А. Исаев, Е.К. Ремер. Эволюционно-генетический подход к решению задач невыпуклой оптимизации (1998)

3. Р. Акоф, М. Сасиени, Основы исследования операций, Издательство «Мир», (1971).

4. Задачи оптимизации и нечеткие переменные (1980)

5. А.И. Орлов. Теория принятия решений (2004)

6. R. Allenson. Genetic Algorithms with Gender for Multivariate Optimisation. (1992).

7. Blickle, Thiele "A Comparison of Selection Schemes used in Genetic Algorithms" (1993)

8. Darrel Whitley "A Genetic Algorithm Tutorial" (1993).

Размещено на Allbest.ru