Материал: Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС. Муратов А.В., Скоробогатов В.С

16

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

1)использования единого функционала;

2)выбора ведущего показателя;

3)параллельной оптимизации по нескольким показателям.

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

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

Простейшими примерами использования единого функционала качества являются выражения (2.4) и (2.5), позволяющие учесть требования уменьшения длин отдельных соединений и рассредоточения теплонагруженных элементов при минимизации общей суммарной длины всех соединений. При необходимости повышения плотности размещения разногабаритных модулей на монтажной плоскости в качестве единого функционала используют взвешенную сумму эффективности использования площади F1 и суммарной длины соединений F2 : F = k1F1 + k2F2.

Данный метод получил широкое распространение на практике К достоинствам данного метода относятся возможность варьирования весовыми коэффициентами и простота его реализации на ЭВМ Недостатком метода является трудность обоснования важности каждого i-ro показателя и задания конкретных значений весовых коэф-

фициентов.

Метод выбора ведущего показателя основан на использовании принципа последовательной субоптимизации результатов, получаемых на каждом этапе поиска. Все показатели качества располагают в порядке важности и сначала отыскивают оптимальное решение по первому из них. Остальные показатели выступают в роли ограничений. Затем определяют допустимую область, в которой значение первого показателя отличается от оптимального на некоторую величину S (например, на 5—10%) и в этой области ищут оптимальное решение по второму показателю и т. д.

Основное достоинство метода заключается в возможности учета в виде списка ограничений большого числа различных требований предъявляемых к конструкции РЭА.

Быстрый рост затрат машинного времени и объема памяти ЭВМ при расширении списка ограничений, а также значительные трудности получения оптимального решения по

17

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

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

/1/.

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

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

чтобы степень оптимизации была наибольшей, не приводится. В связи с этим тема дипломной работы ―Исследование алгоритмов парных перестановок при решении задач компоновки и размещения в САПР‖ представляется актуальной.

3. АЛГОРИТМ ПАРНЫХ ПЕРЕСТАНОВОК ПРИ РЕШЕНИИ ЗАДАЧ

КОМПОНОВКИ

3.1. Метод парных перестановок

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

Пусть какое-либо устройство имеет Х элементов (модулей первого уровня,

например, микросхем) и каждый i - й элемент имеет с j - м элементом Cij соединений.

Схема такова, что ее не разместить на одной плате, то есть требуется всѐ устройство разделить на составные части (например, на модули 2 - го уровня, то есть блоки). В

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

-снижение количества используемого монтажного провода (экономический эффект);

-увеличение надежности изделия;

18

-снижение массы и трудоемкости изготовления изделия;

-уменьшение паразитных взаимосвязей.

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

Число возможных сочетаний элементов определяется по формуле :

n

где Cm - число сочетаний из m элементов по n элементов,

m - число всех элементов; n - число элементов в одном блоке.

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

Таким методом является метод парных перестановок.

Пусть в результате произвольного начального распределения нами сформированы Z блоков. Обозначим их через X , X , X ,...,XZ. Подсчитав количество соединений между двумя блоками, например, между блоком Х и блоком Х , меняем взаимно местами по одному модулю из блока Хи из блока Х . После этого вновь считаем количество соединений между блоками. Если после перестановки количество соединений уменьшилось, то перестановка целесообразна. Если же увеличилось или осталось прежним, то перестановка нецелесообразна. Можно производить перестановку каждого модуля блока Х с каждым модулем блоков Х , Х , ..., Хz, а затем каждого модуля блока Хс каждым модулем остальных блоков и т.д. В результате можно получить минимизацию соединений между блоками. Чтобы упростить вычисления выведем формулу для определения целесообразности перестановки местами i и j модулей,

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

из-за того, что общие (прямые) соединения между переставляемыми модулями учтены и в значении mi , и в значении m j , то есть дважды, а надо их учесть только один раз, то из

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

20

Таким образом целесообразность перестановки i - го модуля, находящегося в блоке Х , с j - м модулем, находящимся в блоке Х , определяется по формуле:

перестановка не ведет к уменьшению числа межблочных соединений, а ведет к их

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

котором вычисляются значения функционалов F для всех пар модулей и из всех возможных целесообразных перестановок пар модулей выбирается та пара модулей,

перестановка которых дает максимальное уменьшение количества межблочных соединений (рис. 3.1), а не первая попавшаяся целесообразная перестановка. Подсчитав функционалы всех пар модулей и произведя перестановку двух модулей, для которых функционал имеет максимальное положительное значение, вновь производят вычисления всех функционалов для этих двух блоков. Если окажется, что для каких-либо двух модулей максимальный функционал больше нуля, то снова производят перестановку и так несколько раз, до тех пор, пока все функционалы будут равны или меньше нуля. Следует