Диссертация (1137155), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

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

Этотпроцесс повторяется до тех пор, пока не будут исчерпаны всевозможности и/или не будет найдено решение. Различные алгоритмыпоискасвозвратамиразличаютсяпоскоростиобнаружениятупиковых вершин, а также по тому, насколько далеко они способныделать возврат. Алгоритм поиска с возвратами характеризуетсяэкспоненциальной временной сложностью, но является линейным поиспользованию памяти [86].Рисунок 18.

Поиск с возвратами как обход дереваПростые алгоритмы, такие как хронологический поиск свозвратами, имеют ряд недостатков, самым существенным из которыхявляются так называемые «метания» [76], когда поиск бываетбезуспешен повторно из-за одних и тех же ограничений. Дляпреодоленияэтихнедостатковразработанрядалгоритмов,объединяемых в группу алгоритмов интеллектуального поиска свозвратами [64]. Такие алгоритмы позволяют обнаруживать, чтоконкретная тупиковая вершина дерева присвоения значений не100связана с некоторыми присвоениями и значительно сократить времяпоискадопустимыхнедостатковрешений.универсальныхКрометого,простыхдляалгоритмовпреодолениявозможныразличные модификации с учетом характера ограничений конкретнойзадачи.Приближенные методы.Приближенные методы широко применяются при решениизадач комбинаторной оптимизации, так как нахождение точногорешения может потребовать значительных вычислительных ресурсов.Современныеприближенныеметодыобычноявляютсякомбинированными, т.е.

содержат в себе элементы различныхметодов. В приближенных методах решение задачи производитсяобычно в два этапа: построение начального решения и улучшениеначального решения. При этом на первом этапе широко используютсяэвристическиеалгоритмы–алгоритмы,основанныенаправдоподобных, но не обоснованных строго предположениях освойствах оптимального решения задачи [43].Отметим, что существуют задачи, для которых переход кприближенной постановке не представляется возможным.

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

Поиск глобальногорешения задачи оптимизации происходит путем перебора локальныхрешений.Существует множество методов глобальной оптимизации,однако все они имеют общие черты [9]: для поиска глобального оптимума следует анализироватьразличные области множества решений X; в каждой области происходит поиск оптимума с помощьюалгоритма локальной оптимизации (спуск по градиенту); необходим критерий остановки алгоритма на основаниикачества полученного решения, поскольку область поиска может бытьбесконечно большой.Нужно подчеркнуть, что в общем случае нельзя гарантироватьточноерешениезадачиглобальнойоптимизациидлямногоэкстремальной функции за конечное число шагов.

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

Большинство стохастическихметодов оценивают значение функции цели в случайных точкахдопустимого множества с последующей обработкой выборки [9]. Кним относятся методы мультистарта, имитации отжига, генетическиеалгоритмы.Историческипервымметодомглобальнойоптимизацииявляется метод Монте-Карло, на базе которого был создан методмультистарта [92]. В чистом виде метод мультистарта не являетсяэффективным, так как одно и то же локальное решение может бытьнайдено не один раз. Мультистарт – это обобщенный подход:большинствоэффективныхметодовглобальнойоптимизацииосновано на идее метода мультистарта – запуска стандартныхлокальныхалгоритмовизмножестваточек,равномернораспределенных на множестве D. Таким образом, метод мультистартаможно назвать прототипом таких методов.Существует множество модификаций метода мультистарта,например, методы группировок, в которых предпринимается попыткаустраненияглавногонедостаткаметодовданногокласса–многократного нахождения одних и тех же локальных решений.Основная идея метода имитации отжига (simulated annealing)[80] исходит из физики процесса замерзания жидкостей или103рекристаллизации металлов в процессе отжига.

Целевая функцияздесь является аналогом равновесия термодинамической системы ивидоизменяется путем добавления случайных величин (условийтемпературного режима). Процесс повторяется достаточное число раздля каждой температуры, после чего температура понижается и весьпроцесс происходит снова до состояния полной заморозки. Избеганиепопадания в незначительные локальные минимумы (замерзание)зависит от «схемы отжига», выбора начальной температуры,количества итераций для каждой температуры и того, насколькоуменьшается температура на каждом шаге процесса «охлаждения» [9].Генетические алгоритмы (ГА), как и другие алгоритмырассматриваемой группы, ориентированы на поиск субоптимальногорешения в условиях невозможности полного перебора вариантов.ОсновойбиологическойдлявозникновенияэволюциииметодыГАпослужилислучайногомодельпоиска.ГАосуществляют поиск баланса между эффективностью и качествомрешений за счет «выживания сильнейших альтернативных решений»в неопределенных и нечетких условиях.ГА отличаются от других оптимизационных и поисковыхпроцедур следующим [12]: работают в основном не с параметрами задачи, а скодированным множеством параметров; осуществляют поиск не путем улучшения одного решения, апутем использования сразу нескольких альтернатив на заданноммножестве решений; используют целевую функцию, а не ее различные приращениядля оценки качества принятия решений; применяют не детерминированные, а вероятностные правилаанализа оптимизационных задач.104Генетические алгоритмы обладают рядом преимуществ [35]: ГА не требуют никакой информации о поведении функции(например, дифференцируемости и непрерывности); разрывы, существующие на поверхности ответа, имеютнезначительный эффект на полную эффективность оптимизации; ГА относительно стойки к попаданию в локальные оптимумы; ГА пригодны для решения крупномасштабных проблемоптимизации; ГА могут быть использованы для широкого класса задач; ГА просты в реализации; ГА могут быть использованы в задачах с изменяющейсясредой.Следует подчеркнуть однако, что ГА в окрестности глобальногоминимума может быть менее эффективным, чем алгоритм спуска поградиенту или другой алгоритм локальной оптимизации.

Поэтому ГАможно использовать не только в «чистом виде», но и совместно страдиционными алгоритмами локальной оптимизации [35].Посколькузадача(2.30)–(2.33)имеетдвакритерияоптимальности, целесообразно рассматривать модификации методовдискретной оптимизации, специально разработанные для решениямногокритериальных экстремальных задач.Известнобольшоечислометодоврешениязадачимногокритериальной оптимизации, из числа которых перспективнымиявляются методы, основанные на предварительном построенииаппроксимации множества Парето (а тем самым, и фронта Парето)этой задачи.

Простейшим из таких методов является сеточный метод[27]. В ситуации, когда требуется высокая точность аппроксимациимножеств Парето и/или когда имеет место высокая вычислительная105сложность целевых функций, сеточный метод может требоватьнеприемлемовысокихвычислительныхресурсов.Поэтомувнастоящее время интенсивно развиваются альтернативные методы[26]. Прежде всего – эволюционные методы Парето-аппроксимации.ИзвестнонесколькоклассификацийметодовПарето-аппроксимации. Используем классификацию, предложенную в [21], вкоторой выделены следующие пять классов методов Паретоаппроксимации: «наивные»методы(например,методнаосновелексикографической турнирной селекции (lexicographic tournamentselection) [85]); методы переключающихся целевых функций(наиболееизвестный алгоритм этого класса – VEGA (Vector Evaluated GeneticAlgorithm) [95]); методы агрегации целевых функций (например, методвзвешенных критериев, метод идеальной точки, адаптивный методвзвешенных сумм); методы на основе ранжирования агентов популяции (методнедоминируемой сортировки (Non-Dominated Sorting, NDS), методПарето-силы (Pareto strength) [85]); прочие методы.Мы рассмотрели основные методы, применяемые для решениязадачкомбинаторнойоптимизации,и,вчастности,многокритериальных задач.При выборе конкретного метода необходимо руководствоватьсятем, какие методы применяются на практике для решения задач,подобных массовым задачам (если для решаемой задачи такое же106подобие удается установить), а также исходными данными, преждевсего, характером целевой функции и ограничений.Первым этапом всех приближенных методов является начальноепостроение допустимых решений.

Способ построения допустимыхрешений сам по себе может представлять нетривиальную задачу.Вопрос о существовании допустимого решения задачи дискретнойоптимизации в общем виде сводится к выяснению, разрешима лисистема линейных равенств и неравенств в целых неотрицательныхчислах. Известно, что это трудоемкая вычислительная задача изкласса NP [43]. Следовательно, в общем случае поиск допустимогорешения может оказаться столь же трудоемким, как и поископтимального решения. Поэтому покажем сначала, как могут бытьпостроены допустимые решения для задачи (2.30) – (2.33), а затемпроведемвычислительныйэкспериментнатестовыхданныхнебольшой размерности для выявления характера целевых функций ипроверки некоторых утверждений, сделанных в параграфах 2.1 – 2.3.3.3.Алгоритм построения допустимых решенийЗадача построения допустимых решений () для(2.30) – (2.33) может быть сформулирована как задача УО.Даномножествопеременныепеременныхимеютодинаковые.домены.

Требуется найти такиеприсвоенияВсезначений, для которыхудовлетворяет ограничениям (2.32), (2.33).Необходимо также, чтобы значения, присвоенные переменным былипопарно различными (– ограничение “all-different”).Данная задача является бинарной задачей УО, посколькувыраженияпеременных.(2.32),(2.33)накладываютограничениянапары107Опишем алгоритм простого хронологического поиска в глубинудля решения поставленной задачи УО.Алгоритм 1. Хронологический поиск c возвратамиПроцедура Поиск_с_возвратами_1(k)1: для j := 1 до n+m цикл2:Tr[k] := D[j]3:Consistent := Истина4:для h := 1 до k-1 пока Consistent цикл5:Consistent := Test(h, k)6:кцикл7:если Consistent8:если k = n+m9:Вывод Tr10:иначеПоиск_с_возвратами_1(k+1)11:12:кциклКонец процедурыАлгоритмиспользуетрекурсивныйвызовфункцииПоиск_с_возвратами_1().

Характеристики

Список файлов диссертации