Навигация
Пути решения задач оптимизации
43393
знака
24
таблицы
4
изображения
2.4. Пути решения задач оптимизации
Генетический алгоритм - новейший, но не единственно возможный способ решения задач оптимизации. С давних пор известны два основных пути решения таких задач - переборный и локально-градиентный. У этих методов свои достоинства и недостатки, и в каждом конкретном случае следует подумать, какой из них выбрать.
Рассмотрим достоинства и недостатки стандартных и генетических методов на примере классической задачи коммивояжера (TSP - travelling salesman problem). [20] Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов).
рис. 1 Кратчайший путь
Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.
|
рис.2 Переборный метод | Переборный метод наиболее прост по своей сути и тривиален в программировании. Для поиска оптимального решения (точки максимума целевой функции) требуется последовательно вычислить значения целевой функции во всех возможных точках, запоминая максимальное из них. |
Недостатком этого метода является большая вычислительная стоимость. В частности, в задаче коммивояжера потребуется просчитать длины более 1030 вариантов путей, что совершенно нереально. Однако, если перебор всех вариантов за разумное время возможен, то можно быть абсолютно уверенным в том, что найденное решение действительно оптимально.
| Второй популярный способ основан на методе градиентного спуска (рис. 7). При этом вначале выбираются некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости роста целевой функции. Достигнув локального максимума, такой алгоритм останавливается, поэтому для поиска глобального оптимума потребуются дополнительные усилия. |
рис. 3 Метод градиентного спуска |
Градиентные методы работают очень быстро, но не гарантируют оптимальности найденного решения. Они идеальны для применения в так называемых унимодальных задачах, где целевая функция имеет единственный локальный максимум (он же - глобальный). Легко видеть, что задача коммивояжера унимодальной не является.
|
рис. 4 | Типичная практическая задача, как правило, мультимодальна и многомерна, то есть содержит много параметров. Для таких задач не существует ни одного универсального метода, который позволял бы достаточно быстро найти абсолютно точное решение (рис. 8). |
| Однако, комбинируя переборный и градиентный методы, можно надеяться получить хотя бы приближенное решение, точность которого будет возрастать при увеличении времени расчета. (рис. 9) |
рис. 5 |
| Генетический алгоритм представляет собой именно такой комбинированный метод (рис. 10). Механизмы скрещивания и мутации в каком-то смысле реализуют переборную часть метода, а отбор лучших решений - градиентный спуск. На рисунке показано, что такая комбинация позволяет обеспечить устойчиво хорошую эффективность генетического поиска для любых типов задач. |
|
рис. 10Итак, если на некотором множестве задана сложная функция от нескольких переменных, то генетический алгоритм - это программа, которая за разумное время находит точку, где значение функции достаточно близко к максимально возможному. Выбирая приемлемое время расчета, мы получим одно из лучших решений, которые вообще возможно получить за это время [20].
2.5 Решение задачи коммивояжера.
Задача коммивояжера является классической оптимизационной задачей. Суть ее заключается в следующем. Дано множество из п городов и матрица расстояний между ними или стоимостей переезда (в зависимости от интерпретации). Цель коммивояжера – объехать все эти города по кратчайшему пути или с наименьшими затратами на поездку. Причем в каждом городе он должен побывать один раз и свой путь закончить в том же городе, откуда начал.
Для решения предлагается следующая задача: имеется пять городов, стоимость переезда между которыми представлена следующей матрицей:
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 4 | 6 | 2 | 9 |
| 2 | 4 | 0 | 3 | 2 | 9 |
| 3 | 6 | 3 | 0 | 5 | 9 |
| 4 | 2 | 2 | 5 | 0 | 8 |
| 5 | 9 | 9 | 9 | 8 | 0 |
Для решения задачи применим следующий генетический алгоритм. Решение представим в виде перестановки чисел от 1 до 5, отображающей последовательность посещения городов. А значение целевой функции будет равно стоимости всей поездки, вычисленной в соответствии с вышеприведенной матрицей. Сразу заметим, что одним из оптимальных решений задачи является последовательность 514235 стоимостью 25.
Заметим, что чем меньше значение целевой функции, тем лучше. То есть целью в данном случае является поиск минимума целевой функции.
В качестве оператора скрещивания выберем процедуру, похожую на двухточечный оператор скрещивания. Поясним его работу на примере. Пусть есть две родительские перестановки (12345) и (34521). Случайно и равновероятно выбираются две точки разрыва. Для примера возьмем ситуацию, когда первая точка разрыва находится между первым и вторым элементами перестановки, а вторая точка – между четвертым и пятым: (1 | 2 3 4 | 5), (3 | 4 52 | 1). На первом этапе перестановки обмениваются фрагментами, заключенными между точками разрыва: (* | 452 | *) , (* | 234 | *). На втором этапе вместо звездочек вставляются соответствующие числа из исходной родительской перестановки, начиная со второго числа выделенного фрагмента и пропуская уже имеющиеся в новой перестановке числа. В данном случае в первой перестановке (1 | 234 | 5) таким начальным числом является 3, за ним идет 4, которое есть в новой перестановке, и мы его пропускаем, также пропускаем число 5, переходим на начало перестановки и выбираем число 1. В итоге вместо (* | 4 5 2 | *) получаем (34521), аналогично из (3| 452|1) и (*|234|*) получаем (52341).
Оператор мутации будет представлять собой случайную перестановку двух чисел в хромосоме, также выбранных случайно по равномерному закону. Вероятность мутации 0,01. Размер популяции выберем равным 4.
Исходная популяция представлена в таблице 1.
Таблица 1
| № строки | Код | Значение целевой функции | Вероятность участия в процессе размножения |
| 1 | 12345 | 29 | 32/122 |
| 2 | 21435 | 29 | 32/122 |
| 3 | 54312 | 32 | 29/122 |
| 4 | 43125 | 32 | 29/122 |
Пусть для скрещивания были выбраны следующие пары: (1, 3) и (2, 4). В результате были получены потомки, представленные в таблице 2.
Таблица 2
| № строки | Родители | Потомки | Значение целевой функции для потомков |
| 1 | 1|23|45 | 5|43|12 | 32 |
| 3 | 5|43|12 | 1|23|54 мутация 13254 | 28 |
| 2 | 2|143|5 | 4|312|5 | 32 |
| 4 | 4|312|5 | 2|143|5 | 29 |
Пусть для потомка (12354) сработал оператор мутации, и обменялись местами числа 2 и 3. В данном случае строка (12354) изменилась и приняла значение (13254). Популяция первого поколения после отсечения худших особей в результате работы оператора редукции приняла вид, представленный в таблице 3.
Таблица 3
| № строки | Код | Значение целевой функции | Вероятность участия в процессе размножения |
| 1(1) | 12345 | 29 | 28/122 |
| 2(2) | 21435 | 29 | 28/122 |
| 3(н) | 13254 | 28 | 29/122 |
| 4(н) | 21435 | 29 | 28/122 |
Пусть для получения второго поколения были выбраны следующие пары строк: (1,4) и (2, 3). И в результате были получены потомки, показанные в таблице 4.
Таблица 4
| № строки | Родители | Потомки | Значение целевой функции для потомков |
| 1 | |123|45 | |214|35 | 29 |
| 4 | |214|35 | |123|45 | 29 |
| 2 | |21|435 | |13|452 | 32 |
| 3 | |13|254 | |21|354 | 29 |
Популяция второго поколения после отсечения худших особей приняла вид, показанный в таблице 5.
Таблица 5
| № строки | Код | Значение целевой функции | Вероятность участия в процессе размножения |
| 1(1) | 12345 | 29 | 28/111 |
| 2(2) | 21435 | 29 | 28/111 |
| 3(3) | 13254 | 28 | 29/111 |
| 4(н) | 21354 | 29 | 28/111 |
Таким образом, после двух итераций значение целевой функции для лучшего решения изменилось с 29 на 28, среднее значение изменилось с 30,5 до 28,75, а общее качество с 122 до 111. То есть также налицо незначительное, но улучшение популяции [21].
Вывод
Существует множество вариантов задач оптимизации. Особенно трудно переоценить их значимость в математической экономике. Мы с вами рассмотрели их основные пути решения и на примере решения Диофантова уравнения и задачи коммивояжера убедились в том, что генетический алгоритм является наиболее универсальным методом решения.
ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ. СОЗДАНИЕ ПОСОБИЯ ПО ГЕНЕТИЧЕСКИМ АЛГОРИТМАМ.
Похожие работы
... число эпох функционирования алгоритма, или определение его сходимости, обычно путем сравнивания приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра. 3. Непрерывные генетические алгоритмы. Фиксированная длина хромосомы и кодирование строк двоичным алфавитом преобладали в теории генетических алгоритмов с момента начала ее развития, когда были получены ...
... в популяциях, которые являются существенными для развития. Точный ответ на вопрос: какие биологические процессы существенны для развития, и какие нет? - все еще открыт для исследователей. Реализация генетических алгоритмов В природе особи в популяции конкурируют друг с другом за различные ресурсы, такие, например, как пища или вода. Кроме того, члены популяции одного вида часто конкурируют ...
... N строк. Для популяции вводится понятие средней ценности популяции Fср (G(t)): Аналогично для подпопуляции GH(t), удовлетворяющей схеме H, вводится понятие средней ценности подпопуляции Fср (GH(t)):. Генетический алгоритм осуществляет переход от популяции G(t) к популяции G(t+1) таким образом, чтобы средняя ценность составляющих её строк увеличивалась, причём количество новых строк в популяции ...
... решения Скрещивание, рекомбинация, кроссинговер Оператор рекомбинации мутация Оператор модификации При разработке генетических алгоритмов преследуется две главные цели: · Абстрактное и формальное объяснение процессов адаптации в естественных системах; · Проектирование искусственных программных систем, воспроизводящих механизмы функционирования естественных систем. Основные отличия ГА от ...
0 комментариев