Основы САПР (CAD,CAM,CAE) - (Кунву Ли)(2004) (951262), страница 56
Текст из файла (страница 56)
В этом случае размещаемыми объектами являются города, а то, что каждый город нужно посетить ровно один раз, является ограничением [158[. Эту проблему можно интерпретировать в терминах обычной оптимизации. Посещаемые города — это переменные оптимизации, причем дискретное значение переменной означает номер„под которым данный город войдет в список посещенных Упомянутое выше условие может быть выполнено, если на дискретные значения, принимаемые переменными, наложить некоторое ограничение.
В исследованиях комбинаторной оптимизации были достигнуты значительные успехи. Однако лля многих важных комбинаторных задач, встречавшихся на практике и классифицированных как )чр-полные [52[, эффективные алгоритмы поиска оптимальных решений все еше неизвестны. ХР-полными называются за- .; Рачд,,рещеиие которых с вычислительиыми затратами, описывающимися по:,:п)виомиальиой функцией характерного масштаба задачи, крайне маловероятно, 4)а)обще говоря, все известные алгоритмы решения таких задач требуют вычисдительиых затрат, экспоиеициальио возрастающих с размером залачи, К тому же бгйгвлгоритмы находят обычио ие пспгиио оптимальные решения, ио лишь :-6)пвэкие к иим [158[.
1))дии из методов решеиия хР-полных задач состоит в использовании алгоритма ''х)((дг')йгксимации, позволяющего найти приближенное решение за разумиое вретдф.-':ййбп(ая стратегия разработки алгоритмов аппроксимации состоит в последо- ''[)111(зятьком улучшении, осиоваииом иа методе проб и ошибок. Поиск начинается е)ф~к())форой произвольной конфигурации и продолжается проверкой соседних с :д~4:;-'~[одгфигураций до тех пор, пока ие будет найдена конфигурация с меньшей ,:б)1)[[й[[)етые. Алгоритм завершает работу, если ои больше ие может найти соседфлв~~а~)1(фигурации более кивкой стоимости.
Эта стратегия кажется разумной, но [1[[[)' ~)ддФет один серьезиый недостаток: поиск решения оканчивается в ближай',,)т(окальиом минимуме (рис. 9.6). Решения, которые кажутся удачными по ив) с их близкими соседями, ие обязательно являются наилучшими в ' ом смысле. Стандартное итеративное улучшение позволяет лишь спус[()[г[й1к)[д:.,с холма, ио ие подниматься обратно, и потому ие гарантирует хорошего ; ф~~)[Ката [158, 134[. Текущая конфигурации Конфигяиции вяио. 9.6.
пространство конфигпявций о множеством покапьньи м»иимумое :.'йяпйуед( модельиой закалки основан иа аналогичной стратегии, ио существеиио ''«вх(лдчается от метода итеративного улучшения тем, что разрешает ограниченный ' дв()В(ьем евверхь по поверхности функции стоимости. Благодаря этому оказыва, дясд,возможным авыбратьсяь из локального минимума и спуститься в другой, "„'(я()лее глубокий [134!.
Фью, ДЛГЕРИТИ "ь))тдязгстическая механика изучает поведение сложных систем, состоящих из --,:болбшого числа взаимодействующих атомов, находящихся в тепловом равиове:; яо)ии при конечных температурах. Исследователи обнаружили, что вероятность ..явбиаружить систему в некотором состоянии 5 равна е ( )гч', где Е(5) — энергия ' 1(аниого состояния, а ль — постоянная Больцмапа. Таким образом, наиболее ее.:::;,Ржгиыми в тепловом равновесии врп любой температуре оказываются состоя- ': иия атомов с мивимзльиой эиергией [1581.
Аизлогия между задачей комбинаториой опттцыизации и определением осиовиого состояния физической системы со множеством взаимодействующих частиц впервые была обнаружена Керкпатриком, Гелаттом и Веччи в 1983 г. [85] и, иезависимо от иих, Перви [31[. Аналогия хорошо иллюстрируется табл. 9.1. Состояния системы соответствуют конфигурациям задачи комбииаториой оптимизации, Осиовиые состояния системы соответствуют опптмальиым конфигурациям, то есть таким коифигураШ(ям, которые минимизируют функцию стоимости.
Наконец, задача определения опптмальиой коифигурашти соответствует задаче поиска основного состояния системы при низкой температуре. Таблица 9.1. Аналогия между физической системой и задачей оптимизации ~':,~:..'В 1953 г. Метрополис [1131 предложил процедуру вычислений, позволяющую .моделировать равновесное состояние системы многих тел при конечной темпе',:,:ратуре. Алгоритм Метрополиса гюказан в листинге 9.1. На каждом шаге случайным образом выбирается небольшое возлгущеиие текущей конфигурации, после :,: .:чего вычисляется изменение эиергии системы А Новая коифшурация принимается с вероятностью 1, если А <О, и с вероятностью е "~ ~ при А с О.
Для этого Выбрасывается случайное число от О до 1. Если оио оказывается меньшим е Яг"'", ",, новая конфигурация принимается. Это обеспечивает заданную вероятность припяти я. ;:::;: Листинг 9.1. Алгоритм Метрополиса берти Выбрать случайную исходную конфигурацию 5: гереат 5' :- произвольно выбранная конфигурация, соседняя с 5: а :- Е(5') - Е(5): РгоЬ :- и(п(1,е агк)): тт гапбое(0,1) К РгоЬ Ебеп 5 := 5': Впг)1 Га1ве; епб: Описанную процедуру легко приспособить к решению задач комбинаториой оп'!,:': тимизации. Для этого состояния физической системы заменяются коифпгурациями задачи иа оптимизацию, а энергия состояния заменяется функцией стоимости или целевой функцией для соответствующей конфигурации.
После этого процедура может использоваться для моделирования процесса оптимизации комбииаториой задачи с зэланной функцией стоимости. Керкпатрик реализовал данный подход, рассматривая систему при постепенном понижении «температурым При каждой конкретной температуре система вы- держивается до тех пор, пока она не достигнет теплового равновесия. Это обеспечивается алгоритмом Метрополиса.
Общий алгоритм метода модельной закал. ки приведен в листинге 9.2. Обратите внимание, что в методе модельной закалки постоянная Больцмана включена в температуру, 1ак что температурой мы называем их произведение. Температура в данном случае является только управляющим параметром процелуры оптимизации. ' лвветзвнг 9.2. Алгоритм модельной закалки Ьедтп 5:- нвчвпьное рвиение 50, т:- нвчвпьнвя теипервтурв ТО: Ып1е (иритерий зввереения не выполнен) бо Ьедтп ипт 1е (рввновесие не достигнуто) бо Ьедтп 5' :- произвопьно выбранная конфигурация, соседняя с 5; й : Е(5') - Е(5).' РгоЬ :- атп().е'Ыит); тт гвпбои(0, 1) З РгоЬ гйеп 5 :- 5'; епб; Изиенить Т: епб; Вывести пучеее рвиение, епб, 'На.ззнтуитивном уровне алгоритм модельной закалки можно воспритвтмать как 1(соачршенствованную версию алгоритма итеративного улучшения.
Модельная завелка добавляет элемент случайности в алгоритм итеративного улучшения н .. Разрешает изменения, ухудшающие текущее состояние системы, но дающие возмйжзтость попасть в какой-штбудь другой минимум. более глубокий. Эти измене,;:: Рй)):управляются температурой и становятся все менее вероятиьпытт по мере при- ,~(а)р)гииия к окончанию процесса, потому что значение Т снижается (прп -)1))ттн»Х)Ких темпЕРатурах вероятность ухудшаюшего скачка велика).
";Вот)йетический анализ показывает, что алгоритм модельной закалки сходится -зт:,'глобально оптимальному решению с вероятностью 1 при условии, что выпол'-'-- "'ввяйзтся некоторые ограничения на количество итераций прн каждом значентш 'тйыцературы и на изменение этой температуры от шага к шату. Однако общего ° )тринципа, по которому можно было бы ставить эти ограничения для конкретиьтх задач, пока не сушествует. Поэтому большинсттю современных пртогожений ::.:, метла модельной закалки используют простой и эффективный подход КеркпатРика и других 1851 в различных разновидностях.
:.. ' Метод модельной закалки очень привлекателен, поскольку дает решения высокого качества и в общем случае прост в реализации даже для тех, кто не имеет , 'хорошего представления о задаче. Однако модельная закалка является скорее обшим методом оптимизации, нежели конкретным, полностью определенным алгоритмом.
Применение метода к конкретной задаче требует аккуратности: , ''' "1. Нужно сформулировать задачу, точно описав различные конфигурации. 2. Требуется систематически порождать решения, соседние с текущим. В. Нужно выбрать подходящую функшяю стоимости. 4. Наконец, важно правильно определить график чзакалкиьч то есть н ч ть начальную температуру, закон ее изменения, продолжительность выдержки прн каждом значении температуры и условие завершения работы алгоритма. $.::" 9.4.3. Применении алгоритма модельной закалки Недавние исследования продемонстрировали эффективность алгоритма модель- 4;:, ной закалки во многих задачах оптимизации, к числу которых относятся: О размещение и соединение компонентов СВИС; »1 О разработка компоновочных планов; О маршрут)таяния и оптимизация маршрутов; О проекшрование размешения; О двумерное уплотнение (компоновка); 'г О разработка цифровых филътров; О распознавание образов; ;;, О обработка изображений.
;, Мы рассмотрим два примера решения задач оптимизации при помощи алгорит° ыа модельной закалки. '„.':,-.'1йздача иоммивояи(ера 5- 'Задача коммивояжера состоит в том, чтобы найти маршрут, проходящий ровно :.,'',один раз через каждый город из предложенного набора и возвращаюшийся в ,.юнце концов в отправную точку. При этом стоимость маршрута должна быть ": "цинттмальной. Функция стоимости в общем случае связана с суммарной длиной ' маршрута коммивояжера. ,:,Поскольку метод модельной закалки требует порождения и оценют множества *;-конфигураций, необходимо наличие эффективных методов порождения сосед-„.
них конфигураций и их проверки. Модификация имеющегося маршрута (списка ; городов в порядке их посещения) обычно осуществляется следующим образом: ' О выбирается п бирается произвольная часть текущего маршрута и внутри нее порядок объезда городов меняется на противоположный; ;:, О либо выбранная часть перемещается в случайное место текущего маршрута. -' Четы етыре конфигурации, полученные в процессе решения задачи коммивояже ", со100 го 1 городами методом модельнои закалки, показаны на рис. 9.7. Города распоРа , ложены в вершинах правильной решетки. Начальная конфигурация на рис.
9.7, а ; задается случай)ной последовательностью городов, далекой от оптимальной. ;: Конфи фигурация выглядит вполне хаотично, а стоимость обьезда оказывается ,:., велика. В процессе оптимизации получаются конфигурации (рис. 9.7, б, в), кото- Р рые ближе к минимуму стоимости. Они становятся менее хаотичными и стои'т мость их уменьшается.
Наконец, на рис. 9.7, г показана конфигурация с мини:-. мальной стоимостью. Видно, что последовательность объезда п)родов в этой конфигурации строго упорядочена (971. Еще один пример задачи коммивояжера, успешно решенной Керкпатриком и соавторами при помощи модельной закалки, показан на рис. 9.8. * т 1.0 О.В О.В од 0.2 Доля о падов = 17.51ь 0.0 1.О О.В о.в О.4 0.2 Рис. 9.7. Решение задачи коммнвовкера для 100 городов 0.0 0 О О 2 О 4 0 6 О В 1.0 0 0.2 О 4 О 6 0 В 1.0 Рис. 9.9. Решение задачи коммивояжера для 400 городов„полученное о помощью метода модельной закалки ззптнззалъная ксиепоновиа Задача оппшлгазьиой компоновки (орг(та1 пея.'1пя) состоит в минимизации использоваиия исходных листов (заготовок) при производстве деталей различной формьь Типичиые ограничения задачи состоят в том, что формы ие должны перекрываться, ио при этом должны целиком располагаться внутри границ листа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
