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

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

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

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

2. АЛГОРИТМ ПАРНЫХ ПЕРЕСТАНОВОК

ПРИ РЕШЕНИИ ЗАДАЧ КОМПОНОВКИ

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

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

Пусть какое-либо устройство имеет Х элементов (модулей первого уровня, например, микросхем) и каждый i - й элемент имеет с j - м элементом C_ij соединений. Схема такова, что ее не разместить на одной плате, то есть требуется всё устройство разделить на составные части (например, на модули 2 - го уровня, то есть блоки). В качестве критерия оптимизации при решении этой задачи выбирается минимизация числа межблочных соединений, которая достигается за счет установки в каждом блоке максимально связанных элементов. Этот критерий оптимизации выбирается потому, что он обеспечивает ниже перечисленные положительные эффекты : снижение количества используемого монтажного провода (экономический эффект);

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

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

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

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

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

= ,                                (2.1)

где  - число сочетаний из m элементов по n элементов, m - число всех элементов; n - число элементов в одном блоке.

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