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

6) График зависимости вероятности появления наилучшего (обычно глобального) минимума от количества назначений начальных исходных распределений (рис. 2.9), построенный для случая с наихудшей вероятностью P = 0,4 (P - вероятность появления наилучшего минимума), показывает, что для получения такого минимума с вероятностью, равной 0,99, достаточно десяти назначений.

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

Из изложенного выше можно отметить следующие способы повышения эффективности алгоритма парных перестановок при решении задач компоновки :

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

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

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

ДЛЯ ОПТИМИЗАЦИИ РАЗМЕЩЕНИЯ С МИНИМИЗАЦИЕЙ СУММАРНОЙ ДЛИНЫ СОЕДИНЕНИЙ

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

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

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

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

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