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

Таблица 2.1

Матрица связей

Формирование блока X^b проводим аналогичным образом, исключив из матрицы (табл. 2.1) строки и столбцы, соответствующие модулям, включенным в блок X^a. Максимальное число соединений, равное 5, имеют модули x₃^a и x₂^g, их заносим в список модулей блока X^b и добавляем к ним еще один модуль x₃^b, как имеющий максимальное число соединений с уже установленным модулем x₃^b. Таким образом в блок X^b включаются модули x₃^a, x₃^b и x₂^g, то есть имеем оптимальный вариант     (рис. 2.5). Оставшиеся модули включаются в блок Х^g.

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

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

Рассмотрим пример решения задачи минимизации межблочных соединений с помощью ПЭВМ.

Пусть требуется схему из 12 элементов (рис. 2.6), матрица соединений которой представлена в табл. 2.2, разделить оптимальным образом на 2 блока по 6 элементов.

Таблица 2.2

Матрица соединений