4.2 Функция приспособленности
и кодирование решений
Итак, пусть перед нами стоит задача оптимизации.
Варьируя некоторые параметры, к примеру,
если решать задачу размещения, координаты
размещаемых элементов, нужно найти такую
их комбинацию, чтобы минимизировать занимаемую
площадь. Такую задачу можно переформулировать
как задачу нахождения максимума некоторой
функции
. Эта функция называется функцией
приспособленности (fitness function) и используется
для вычисления приспособленности особей.
Она должна принимать неотрицательные
значения, а область определения параметров
должна быть ограничена.
Если нам, к примеру, требуется найти
минимум некоторой функции, то достаточно
перенести область ее значений на положительную
область, а затем инвертировать. Таким
образом, максимум новой функции будет
соответствовать минимуму исходной.
В генетических алгоритмах никак не используются
такие свойства функции, как непрерывность,
дифференцируемость и т. д. Она подразумевается
как устройство (blackbox), которое на вход
получает параметры, а на выход выводит
результат.
Теперь обратимся к кодировке набора
параметров. Закодируем каждый параметр
строкой битов. Если он принимает непрерывное
множество значений, то выберем длину
строки в соответствии с требуемой точностью.
Таким образом, параметр сможет принимать
только дискретные значения (у этих значений
будет степень 2), в некотором заданном
диапазоне.
Например, пусть переменная
принадлежит отрезку
. Закодируем ее бинарной строкой из
битов. Тогда строка
обозначает следующее значение переменной
:
,
если в формуле
обозначает значение бинарного числа,
кодируемого этой строкой.
Если же некоторый параметр принимает
конечное количество значений, к примеру,
целые от 0 до 1000, то закодируем его бинарной
строкой достаточной длины, в данном случае
10. Лишние 23 строки могут повторять уже
закодированные значения параметра, либо
они могут быть доопределены в функции
приспособленности как «худшие», т. е.
если параметр кодируется одной из этих
строк, то функция принимает заведомо
наименьшее значение.
Итак, мы определили для каждого параметра
строку, кодирующую его. Особью будет называться
строка, являющаяся конкатенацией строк
всего упорядоченного набора параметров:
101100 11001011
01101100 1100 1 11101
|
|
|
| | |
|
Приспособленность особи высчитывается
следующим образом: строка разбивается
на подстроки, кодирующие параметры. Затем
для каждой подстроки высчитывается соответствующее
ей значение параметра, после чего приспособленность
особи получается как значение функции
приспособленности от полученного набора.
Вообще говоря, от конкретной
задачи зависят только такие
параметры ГА, как функция приспособленности
и кодирование решений. Остальные
шаги для всех задач производятся одинаково,
в этом проявляется универсальность ГА.
4.3 Алгоритм работы
На рисунке изображена схема работы любого
генетического алгоритма:
В классическом ГА начальная популяция
формируется случайным образом. Фиксируется
размер популяции (количество особей в
ней будем обозначать символом N), который
не изменяется в течение работы всего
алгоритма. Каждая особь генерируется
как случайная L-битная строка, где L —
длина кодировки особи, она тоже фиксирована
и для всех особей одинакова.
Следует заметить, что каждая особь является
одним из решений поставленной задачи.
Более приспособленные особи — это более
подходящие ответы. Этим ГА отличается
от большинства других алгоритмов оптимизации,
которые оперируют лишь с одним решением,
улучшая его.
Шаг алгоритма состоит из трех стадий:
генерация промежуточной популяции (intermediate
generation) путем отбора (selection) текущего поколения
(current generation), скрещивание (recombination) особей промежуточной
популяции путем кроссовера (crossover), что приводит к
формированию нового поколения (next generation), и мутация нового
поколения. На рисунке изображены первые
две стадии:
Промежуточная популяция — это набор
особей, которые получили право размножаться.
Приспособленные особи могут быть записаны
туда несколько раз. «Плохие» особи с большой
вероятностью туда вообще не попадут.
В классическом ГА вероятность каждой
особи попасть в промежуточную популяцию
пропорциональна ее приспособленности,
т. е. работает пропорциональный отбор
(proportional selection). Можно его реализовать
следующим образом: пусть особи располагаются
на колесе рулетки, так что размер сектора
каждой особи пропорционален ее приспособленности.
Изначально промежуточная популяция пуста.
раз запуская рулетку, выберем требуемое
количество особей для записи в промежуточную
популяцию. Ни одна выбранная особь не
удаляется с рулетки. Такой отбор называется stochastic
sampling.
Другой способ отбора, который также
является пропорциональным, это remainder stochastic sampling. Для каждой
особи вычисляется отношение ее приспособленности
к средней приспособленности популяции.
Целая часть этого отношения указывает,
сколько раз нужно записать особь в промежуточную
популяцию, а дробная — это ее вероятность
попасть туда еще раз. Пусть, к примеру,
для некоторой особи
(
— средняя приспособленность текущей
популяции). Тогда она будет выбрана один
раз, а затем с вероятностью
еще раз. Реализовать такой способ
отбора удобно следующим образом: расположим
особи на рулетке так же, как было описано.
Теперь пусть у рулетки не одна стрелка,
а
, причем они отсекают одинаковые сектора.
Тогда один запуск рулетки выберет сразу
все
особей, которые нужно записать в
промежуточную популяцию. Такой способ
иллюстрируется следующим рисунком:
После отбора особи промежуточной популяции
случайным образом разбиваются на пары.
Каждая из них с вероятностью
скрещивается, т. е. к ней применяется
оператор кроссовера, в результате чего
получаются два потомка. Они записываются
в новое поколение. Если же паре не выпало
скрещиваться, в новое поколение записываются
сами особи этой пары.
В классическом генетическом алгоритме
применяется одноточечный оператор кроссовера
(1-point crossover): для родительских хромосом
(т. е. строк) случайным образом выбирается
точка раздела, и они обмениваются отсеченными
частями. Полученные две строки являются
потомками:
11010 01100101101 ⇒ 10110 01100101101
10110 10011101001 ⇒ 11010 10011101001
К полученному в результате скрещивания
новому поколению применяется оператор
мутации. Каждый бит каждой особи популяции
с вероятностью
инвертируется. Эта вероятность обычно
очень мала, менее 1%.
1011001100101101 ⇒ 1011001101101101
Таким образом, процесс отбора, скрещивания
и мутации приводит к формированию нового
поколения. Шаг алгоритма завершается
объявлением нового поколения текущим.
Далее все действия повторяются.
Вообще говоря, такой процесс эволюции
может продолжаться до бесконечности.
Критерием остановки может служить заданное
количество поколений или схождение (convergence)
популяции.
Схождением называется такое состояние
популяции, когда все строки популяции
почти одинаковы и находятся в области
некоторого экстремума. В такой ситуации
кроссовер практически никак не изменяет
популяции. А вышедшие из этой области
за счет мутации особи склонны вымирать,
так как чаще имеют меньшую приспособленность,
особенно если данный экстремум является
глобальным максимумом. Таким образом,
схождение популяции обычно означает,
что найдено лучшее или близкое к нему
решение:
Ответом на поставленную задачу может
служить набор параметров, кодируемый
наилучшей особью последнего поколения.
5 Пути решения задач оптимизации
Генетический алгоритм – новейший, но
не единственно возможный способ решения
задач оптимизации. С давних пор известны
два основных пути решения таких задач
– переборный и локально-градиентный.
У этих методов свои достоинства и недостатки,
и в каждом конкретном случае следует
подумать, какой из них выбрать.
Рассмотрим достоинства и недостатки
стандартных и генетических методов на
примере классической задачи коммивояжера
(TSP – travelling salesman problem). Суть задачи
состоит в том, чтобы найти кратчайший
замкнутый путь обхода нескольких городов,
заданных своими координатами (рисунок
1). Оказывается, что уже для 30 городов поиск
оптимального пути представляет собой
сложную задачу, побудившую развитие различных
новых методов (в том числе нейросетей
и генетических алгоритмов).
Рисунок 1 – Кратчайший путь
Каждый вариант решения (для 30 городов)
- это числовая строка, где на j-ом месте
стоит номер j-ого по порядку обхода города.
Таким образом, в этой задаче 30 параметров,
причем не все комбинации значений допустимы.
Естественно, первой идеей является полный
перебор всех вариантов обхода.
Переборный метод наиболее прост по своей
сути и тривиален в программировании (рисунок
2).
Рисунок 2 – Переборный метод
Для поиска оптимального решения (точки
максимума целевой функции) требуется
последовательно вычислить значения целевой
функции во всех возможных точках, запоминая
максимальное из них.
Недостатком этого метода является большая
вычислительная стоимость. В частности,
в задаче коммивояжера потребуется просчитать
длины более 1030 вариантов путей, что совершенно
нереально. Однако, если перебор всех вариантов
за разумное время возможен, то можно быть
абсолютно уверенным в том, что найденное
решение действительно оптимально.
Второй популярный способ основан на
методе градиентного спуска (рисунок 3).
При этом вначале выбираются некоторые
случайные значения параметров, а затем
эти значения постепенно изменяют, добиваясь
наибольшей скорости роста целевой функции.
Достигнув локального максимума, такой
алгоритм останавливается, поэтому для
поиска глобального оптимума потребуются
дополнительные усилия.
Рисунок 3 – Метод градиентного спуска
Градиентные методы работают очень быстро,
но не гарантируют оптимальности найденного
решения. Они идеальны для применения
в так называемых унимодальных задачах,
где целевая функция имеет единственный
локальный максимум (он же - глобальный).
Легко видеть, что задача коммивояжера
унимодальной не является.
Типичная практическая задача, как правило
мультимодальна и многомерна, то есть
содержит много параметров. Для таких
задач не существует ни одного универсального
метода, который позволял бы достаточно
быстро найти абсолютно точное решение
(рисунок 4).
Рисунок 4
Однако, комбинируя переборный и градиентный
методы, можно надеяться получить хотя
бы приближенное решение, точность которого
будет возрастать при увеличении времени
расчета (рисунок 5).
Рисунок 5
Генетический алгоритм представляет
собой именно такой комбинированный метод
(рисунок 6). Механизмы скрещивания и мутации
в каком-то смысле реализуют переборную
часть метода, а отбор лучших решений -
градиентный спуск. На рисунке показано,
что такая комбинация позволяет обеспечить
устойчиво хорошую эффективность генетического
поиска для любых типов задач.
Рисунок 6
Итак, если на некотором множестве задана
сложная функция от нескольких переменных,
то генетический алгоритм – это программа,
которая за разумное время находит точку,
где значение функции достаточно близко
к максимально возможному. Выбирая приемлемое
время расчета, мы получим одно из лучших
решений, которые вообще возможно получить
за это время.
6 Примеры экстремальных комбинаторных
задач
Множество задач, имеющих одинаковую
постановку и отличающихся только значениями
параметров, будем называть массовой задачей. В дискретной
оптимизации широко известные массовые
задачи имеют названия, отражающие их
интерпретацию.
6.1 Задача об одномерном
ранце
Задача о ранце формулируется следующим образом: из
заданного набора предметов , каждый из которых имеет
вес и ценность (стоимость) , нужно выбрать несколько
и наполнить ими ранец таким образом, чтобы
суммарная выгода по выбранным предметам
была наибольшей, а их общий вес не превосходил
вместимость ранца P. Или формально:
(1.14)
(1.15)
Отметим, что для всех . Допустимым
решением задачи о ранце является бинарный
вектор , удовлетворяющий ограничениям
задачи. Очевидно, что допустимое решение
всегда существует.
Задача легко кодируется при помощи бинарного
представления. Число кодировок , что и определяет вычислительную
сложность задачи. Однако при таком кодировании
не все получаемые кодировки будут допустимыми,
поскольку соответствующие им решения
могут нарушать ограничения на общий вес
ранца. Предложенный способ кодирования
является неортогональным. Целесообразно
исключать недопустимые кодировки из
поиска.
6.2 Задача дихотомического
разбиения графа
Пусть задан неориентированный граф
порядка , где - множество вершин; -
множество ребер; - отображение, определяющее
вес каждого ребра.
Дихотомическим разбиением будем называть такое разбиение
графа на два подграфа и , что:
(1.16)
(1.17)
(1.18)
где - целое положительное число , которое
задается как внешний параметр перед решением
задачи разбиения.
Система требований (1.16)-(1.18), предъявленных
к разбиению , определяет область поиска
D.
В качестве критерия оптимальности ,
определяющего эффективность дихотомического
разбиения , будем рассматривать вес
разреза – сумму весов ребер, соединяющих
вершины из разных подграфов:
(1.19)
Тогда оптимальное дихотомическое разбиение
является оптимальным решением следующей
экстремальной задачи однокритериального
выбора: