Применение генетических алгоритмов к решению задач дискретной оптимизации

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

«Комсомольский-на-Амуре государственный

технический университет»

 

 

Факультет компьютерных технологий

Кафедра «Прикладная математика и информатика»

 

 

 

 

 

РЕФЕРАТ

по дисциплине «Дискретные математические модели»

Применение генетических алгоритмов к решению

задач дискретной оптимизации

 

 

 

 

 

 

Студент группы 3МИм-1   Я.А. Рассолова

Руководитель работы  Г.И. Коротеев

 

 

 

2014

Содержание

 

 

 

 

 

Введение

 

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

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

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

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

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

 

1 Постановки задач дискретной оптимизации

 

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

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

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

Управляющие переменные оказывают влияние на свойства объекта исследования как единой системы. Подобное влияние может быть позитивным или негативным. Если в первом случае значимые для задачи характеристики улучшаются, то во втором, соответственно, ухудшаются. Величины, характеризующие качественные показатели объекта исследования, будем называть выходными параметрами или характеристиками и обозначать . Выходные параметры можно измерять, можно вычислять, но непосредственно изменять нельзя.

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

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

1.  «лучше»   () тогда и только тогда,

когда ;

2. «не хуже»   тогда и только тогда,         (1.1)

когда ;

3. «эквивалентно» тогда и только тогда,

когда .

 

Из соотношений (1.1) следует, что механизм выбора «лучшего» решения сводится к отбору тех и только тех решений, которые доставляют наибольшее значение критерию оптимальности Q в области поиска D:

 

,      (1.2)

где – оптимальное решение;    – наибольшее значение критерия оптимальности среди всех значений критерия   в области поиска .

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

В том случае, когда область поиска состоит из счетного числа решений, принято говорить о задаче (1.2) как о задаче дискретной оптимизации.

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

.       (1.3)

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

,       (1.4)

, где  такое, что , ,    (1.5)

 

       (1.6)

 

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

, .       (1.7)

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

В случае унимодальной функции (или одноэкстремальной функции) оптимальное решение единственно и достигается в точке локального максимума:

,      (1.8)

где – -окрестность точки локального максимума .

Многоэкстремальная функция предполагает несколько локальных максимумов. Глобальный максимум – наибольший из всех локальных максимумов. По аналогии формулируются понятия локальный и глобальный минимумы для задач минимизации (1.3).

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

, .     (1.9)

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

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

       (1.10)

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

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

 

1. «лучше» тогда и только тогда, когда

  для любого   и существует

по крайней мере один частный критерий,

обращающий неравенство в строгое:

 ;

2. «не хуже»   тогда и только тогда, когда                           (1.11)

 для любого ;          

3.  «эквивалентно»   тогда и только тогда,

когда   для любого .

 

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

 

2  Метод исчерпывающего  перебора и понятие задачи  переборного

    типа

 

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

      (1.12)

Здесь множество – конечно, и количество возможных решений равно N. В силу этого формально все допустимые решения можно пронумеровать: и поиск лучшего варианта из множества допустимых решений сводится к полному перебору. Именно этим обстоятельством объясняется название переборных задач.

 

3 Оценка трудности задач дискретной оптимизации

 

Назовем алгоритм эффективным, если он способен найти решение задачи за время, полиномиально зависящее от объема входной информации, а задачи, имеющие такой алгоритм, – полиномиально разрешимыми. Являются ли задачи переборного типа полиномиально разрешимыми? Чтобы ответить на этот вопрос, оценим объем перебора.

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

     (1.13)

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

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

 

4 Основные понятия о генетических алгоритмах

4.1 Природный механизм

 

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

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

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

Изредка происходит мутация: некоторый случайный нуклеотид цепи ДНК особи может измениться на другой. Если полученная цепь будет использоваться для создания потомства, то возможно появление у детей совершенно новых качеств.

Естественный отбор, скрещивание и мутация обеспечивают развитие популяции. Каждое новое поколение в среднем более приспособлено, чем предыдущее, т. е. оно лучше удовлетворяет требованиям внешней среды. Этот процесс называется эволюцией.

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

 

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)

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