Кудрявтсев Методы оптимизатсии 2015

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

Задача коммивояжера: дано множество из n городов и матрица расстояний (стоимости переезда) между городами. Необходимо объехать все города по кратчайшему пути (с минимальными затратами), причем в каждом городе необходимо побывать только один раз и вернуться в город начала путешествия. Имеется пять городов и дана матрица расстояний вида табл. 5.1.

Для решения данной задачи с помощью генетического алгоритма введем вектор вида [12345], отражающий последовательность посещения городов. Данный вектор представляет собой геном. Целевая функция вычисляется на основании приведенной таблицы как сумма расстояний между городами. Начинать путешествие будем из города 5.

Оператор скрещивания представляет собой двухэтапную процедуру. Пусть имеются два родителя:

Родитель 1: [12345], Родитель 2: [34521].

Случайно выбираем две точки разрыва, например: Родитель 1: [1 | 234 | 5], Родитель 2: [3 | 452 | 1].

На первом этапе происходит обмен фрагментами между точками разрыва:

Потомок 1: [* | 452 | *], Потомок 2: [* | 234 | *].

На втором этапе происходит замена звездочек на числа из исходной родительской последовательности, начиная со второго числа выделенного фрагмента. У Родителя 1 это цифра 3, у Родителя 2 – цифра 5. При этом происходит пропуск цифры, если она

131

уже имеется у Потомка. У Потомка 1 на место первой звездочки появится 3, цифры 4 и 5 будут пропущены, так как они уже есть у Потомка. По достижении конца вектора Родителя переходят к его началу и берут цифру 1. Таким образом Потомки будут иметь вид:

Потомок 1: [3 452 1], Потомок 2: [5 234 1].

Оператор мутации представляет собой случайную перестановку двух чисел в геноме, которые выбираются случайно. Вероятность мутации – 0,01.

Размер популяции N=4.

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

1. Формирование начальной популяции (табл. 5.2).

2. Выбор родителей для размножения и формирование потомков. Для скрещивания выбраны особи (1,3) и (2,4). Кроме того, для потомка [1 | 23 | 45] сработала мутация и образовался новый геном [1 | 32 | 45] (табл. 5.3).

3. После отсечения худших особей популяция первого поколения приняла вид (табл. 5.4).

132

4. Для получения второго поколения для скрещивания выбраны особи (1,4) и (2,3) (табл. 5.5).

5. После отсечения худших особей популяция второго поколения приняла вид (табл. 5.6).

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

133

Контрольные вопросы

1.Сформулируйте общую постановку задачи оптимизации. Дайте классификацию задач математической оптимизации.

2.Постройте математическую модель задачи размещения производства.

3.Приведите общий вид однокритериальной оптимизационной задачи.

4.Дайте определение локального и глобального минимума функции.

5.Дайте классификацию методов решения детерминированных задач оптимизации.

6.Опишите основные этапы алгоритма метода поразрядного поиска.

7.Опишите основные этапы алгоритма метода равномерного поиска.

8.Опишите основные этапы алгоритма метода деления пополам (дихотомии).

9.Опишите основные этапы алгоритма золотого сечения.

10.Опишите основные этапы алгоритма метода Фибоначчи.

11.По какому критерию производится сравнение эффективности алгоритмов оптимизации?

12.Дайте описание основной идеи метода квадратичной аппроксимации целевой функции.

13.Опишите основные этапы метода Пауэлла.

14.Опишите основные этапы метода Ньютона-Рафсона.

15.Опишите основные этапы метода секущих.

16.Сформулируйте задачу многомерной безусловной оптимизации.

17.Опишите основные этапы метода Гаусса — Зейделя (покоординатного спуска).

18.Опишите основные этапы метода Хука-Дживса (поиск по образцу).

19.Опишите основные этапы обычного симплекс-алгоритма. Что собой представляет многомерный симплекс?

20.Опишите основные этапы метода Нелдера-Мида (деформи-

руемого многогранника).

134

21.Опишите основные этапы простого градиентного метода.

22.Опишите основные этапы метода наискорейшего спуска.

23.Опишите основные этапы метода Бокса-Уилсона (крутого восхождения).

24.Чем отличаются общая, каноническая и стандартная формы задач линейного программирования?

25.Дайте геометрическую интерпретацию задачи ЛП. Рассмотрите особые случаи.

26.Что собой представляет опорный план (базисное решение) задачи ЛП?

27.Каков признак оптимальности опорного плана?

28.Что собой представляет начальный и искусственный базис?

29.Дайте определение двойственной задачи ЛП.

30.В чем особенность и сложность решения задачи линейного целочисленного программирования?

31.Что собой представляет метод отсечения Гомори?

32.Опишите основные этапы метода ветвей и границ.

135

Список литературы

1. Вентцель Е.С. Исследование операций: Задачи, принципы,

методология. М.: Высшая школа, 2001.

2. Карманов В.Г. Математическое программирование: учебное пособие. М.: Физматлит, 2004.

3.Кулябичев Ю.П., Анитова Т.В. Теоретико-игровые методы исследования. М.: МИФИ, 1994.

4.Губарь Ю. http://www.intuit.ru/studies/courses/1020/188/info.

http://www.intuit.ru. [Online]

5. Загребаев А.М., Крицына Н.А., Кулябичев Ю.П., Шумилов Ю.Ю. Методы математического программирования в

задачах оптимизации сложных технических систем: учебное

пособие. М.: МИФИ, 2007.

6. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. М.: Нолидж, 2001.

136

Приложение 1

Построение графиков в SciLab

1. Выполнить в командной строке инструкцию

deff('[z]=surf(x1,x2)','z=x1^3+13.5*x1^2-66*x1+(5*x1-x2)^2');

Здесь во втором параметре нужно после «z=» написать выражение для вашей функции. Тем самым вы подготавливаете функцию

крисованию.

2.Задать диапазон изменения независимых переменных с помощью команды

t=-5:0.2:5;

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

3. Построить поверхность командой

fplot3d(t,t,surf,35,45,"X@Y@Z");

Описание параметров можно посмотреть в справке. После этого график можно вращать, чтобы добиться максимально наглядного положения поверхности.

4. Построить изолинии командой

fcontour(1:0.1:3,5:0.1:15,surf,10);

Описание ее также можно посмотреть в справке. Нужно варьировать диапазоны изменения переменных, чтобы был наглядно виден минимум (максимум) функции.

137

138

140