qweqweqe123123

Применения алгоритма модельной закалки

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

□         размещение и соединение компонентов СБИС;

□         разработка компоновочных планов;

□         маршрутизация и оптимизация маршрутов;

□          проектирование размещения;

□          двумерное уплотнение (компоновка);

□          разработка цифровых фильтров;

□          распознавание образов;

□          обработка изображений.

Мы рассмотрим два примера решения задач оптимизации при помощи алгоритма модельной закалки.

Задача коммивояжера

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

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

□   выбирается произвольная часть текущего маршрута и внутри нее порядок объезда городов меняется на противоположный;

       □   либо выбранная часть перемещается в случайное место текущего маршрута.

Четыре конфигурации, полученные в процессе решения задачи коммивояжера со 100 городами методом модельной закалки, показаны на рис. 9.7. Города расположены в вершинах правильной решетки. Начальная конфигурация на рис. 9.7, а задается случайной последовательностью городов, далекой от оптимальной. Конфигурация выглядит вполне хаотично, а стоимость объезда оказывается велика. В процессе оптимизации получаются конфигурации (рис. 9.7, б, в), которые ближе к минимуму стоимости. Они становятся менее хаотичными и стоимость их уменьшается. Наконец, на рис. 9.7, г показана конфигурация с минимальной стоимостью. Видно, что последовательность объезда городов в этой конфигурации строго упорядочена [97]. Еще один пример задачи коммивояжера, успешно решенной Керкпатриком и соавторами при помощи модельной закалки, показан на рис. 9.8.

Применения алгоритма модельной закалки

Применения алгоритма модельной закалки

Оптимальная компоновка

Задача оптимальной компоновки (optimal nesting) состоит в минимизации использования исходных листов (заготовок) при производстве деталей различной формы. Типичные ограничения задачи состоят в том, что формы не должны перекрываться, но при этом должны целиком располагаться внутри границ листа.

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

F(S) = отходы + w х перекрытие.

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

Конфигурация S', соседняя с текущей конфигурацией S, может быть построена небольшим возмущением текущей конфигурации. Например, можно случайным образом выбрать одну деталь из всех размещенных на листе и немного изменить ее положение и ориентацию. Изменение конфигурации с S на S' называется перемещением и выполняется в соответствии с алгоритмом Метрополиса (листинг 9.2).

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

Применения алгоритма модельной закалки

Применения алгоритма модельной закалки

Применения алгоритма модельной закалки

 

Смотрите также