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

Сначала по заданной исходной схеме составляется матрица связей , в которой каждый элемент показывает количество связей между i-м и j-м модулями. По заданному исходному размещению модулей в позициях составляется матрица расстояний , в которой каждый элемент показывает в условных единицах длины расстояние между i-м и j-м модулями. После этого по специально выведенной формуле производится вычисление значений DWij - величин, показывающих изменение суммарной длины соединений при перестановке местами i-го и j-го модулей. Если DWij меньше или равно нулю, то перестановка считается нецелесообразной. Если же  DWij - ,больше нуля, то перестановка считается целесообразной, i-й   и   j-й модули переставляются местами и вычисление значений DW_рк для нового размещения модулей в позициях производится вновь и так до тех пор, пока не наступит оптимизация,  т. е. все значения DW_рк будут отрицательными или равными нулю. Для достижения оптимизации часто бывает достаточно 2-4 перестановок, снижение суммарной длины соединений после оптимизации по сравнению с исходной происходит обычно в 1,5 - 2 раза.

Рассмотрим эту задачу математически и выведем формулу для вычисления значений величины DWij.

Пусть имеется какое-либо коммутационное поле с N  установочными позициями для N модулей. Каждая позиция, а значит каждый установленный в эту позицию модуль характеризуется двумя координатами  x_i    и  y_i  (рис. 3.1).

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

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

;                    (3.1)

,                          (3.2)

где  l_ij  и  l*_{i j}   -  расстояние между   i-й   и   j-й позициями или между модулями, установленными в эти позиции;

x_i,  y_i  -  координаты   i-й   позиции;

x_j,  y_j  -  координаты   j-й   позиции;

Исходными данными для решения задачи  будут: матрица соединений, координаты расположения всех позиций и какое-либо начальное размещение модулей  в позициях. Если учесть, что  i-й  модуль устанавливается при начальном размещении в  i-ю  позицию, а  j-й модуль  -  в  j-ю  позицию, то можно считать, что исходными данными будут: матрица соединений и координаты модулей при начальном размещении.

Суммарная длина соединений i-го модуля, стоящего в i-й позиции, со всеми остальными выразится формулой

,          i ¹ k.          (3.3) 

Тогда полная суммарная длина соединений всех модулей в исходном состоянии выразится формулой

            ,           i¹ j,       (3.4)

где   l_{i j}   -  расстояние  между  i- м   и   j- м   модулями, S_{i j}   -  количество  связей  между  ними.

В формуле (3.4) перед суммой ставится коэффициент 1/2, так как при суммировании длина связей между i-м и j-м модулями складывается дважды: один раз как длина связей между i-м и j-м, а второй раз как  длина  связей  между j -м и i-м модулями. Фактически же эта длина должна учитываться только один раз. Чтобы   избавиться  от  этого коэффициента и от условия i¹j формулу (4.4) можно записать в виде

.         (3.4.a)

Подставив  в формулы (3.4) и (3.4.а) вместо  l_ij   их выражения  из (3.1)  и  (3.2),  получим

,  .       (3.5)

.        (3.5.а)

,   .      (3.6)

.           (3.6.а)

После перестановки i-го модуля в j-ю позицию, а j-го модуля в i-ю позицию суммарная длина всех соединений изменится на величину