Материал: Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС. Муратов А.В., Скоробогатов В.С
21
подчеркнуть, что после каждой перестановки все функционалы вычисляются вновь. В
результате таких перестановок достигается обычно локальный минимум межблочных соединений. Близость его к глобальному минимуму, то есть степень оптимизации,
существенно зависит от начального (исходного) распределения модулей между блоками.
В тех случаях, когда всю схему надо разбить на 4 одинаковых по количеству модулей блоков, можно сначала произвести разбиение всей схемы на 2 блока, а затем разбить каждый из полученных блоков еще на 2 блока.
В том случае, когда в каком-либо блоке есть вакансии ( т.е. свободные места для модулей ), можно делать несимметричные перестановки, т.е. переставляют один модуль в тот блок, где есть вакансия, а взамен модуль не ставится. Для несимметричных перестановок :
F‘ = mi - zi
Если F‘ > 0, то перестановка целесообразна.
Рассмотрим приведенный способ оптимизации соединений между блоками на
примере.
Пусть какое - либо устройство состоит из 9 модулей. Их предварительно каким -
либо способом ( например, произвольным способом ) разбили на 3 блока по 3 модуля в каждом блоке (рис. 3.2):
в блоке Х |
: модули Х1 |
, Х2 , Х3 ; |
в блоке Х |
: модули Х1 |
, Х2 , Х3 ; |
в блоке Х
: модули Х1
, Х2
, Х3 ; На рис. 3.2 – 3.5 цифра у линии соединения модулей показывает количество
межмодульных соединений. Общее количество межблочных соединений в исходном состоянии (до оптимизации) равно 22 (рис. 3.2).
1
2
3
Н А Ч А Л О
Ввод матрицы соединений, начального распределения модулей
Вычисление числа межблочных соединений начального распределения
Вычисление матрицы Fij для всех пар модулей, находящихся в разных блоках
22
Произведем сначала оптимизацию межблочных соединений между блоком Х и
Х . Для этого вычислим значения F для всех пар модулей, расположенных в блоках Х
и Х :
F x |
|
x |
|
(m m |
|
) ( |
|
|
) 2m |
|
1 |
|||||
|
|
|
1 |
|
|
1 |
1 |
|
1 |
|
1 |
1 |
1 |
|||
|
|
|
|
|
|
|
=( 3 + 3 ) - ( 5 + 0 ) - 2 3 = -5 |
|
|
|
||||||
F x |
1 |
x |
2 |
(m m ) ( |
1 |
2 |
) 2m |
|
2 |
|||||||
|
|
|
1 |
2 |
|
|
1 |
|
|
|||||||
|
|
|
|
|
|
|
=( 3 + 4 ) - ( 5 + 0 ) - 2 0 = 2 |
|
|
|
|
|||||
F x |
|
|
x |
|
|
(m m ) ( |
|
|
) 2m |
|
|
|||||
|
|
1 |
|
3 |
1 |
3 |
|
1 |
3 |
|
1 |
|
3 |
|||
|
|
|
|
|
|
|
=( 3 + 2 ) - ( 5 + 0 ) - 2 0 = 0 |
|
|
|
|
|||||
F x |
2 |
x |
|
1 |
(m2 |
m1 |
) ( 2 |
1 |
) 2m |
2 |
1 |
|||||
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
=( 4 + 3 ) - ( 5 - 0 ) - 2 0 = 2 |
|
|
|
|
|||||
F x |
|
|
x |
|
(m m |
|
) ( |
|
|
) 2m |
2 2 |
|||||
|
|
|
2 |
|
|
2 |
2 |
|
2 |
|
2 |
2 |
|
|||
= ( 4 + 4 ) - ( 5 + 0 ) - 2 • 4 = - 5
|
|
|
|
23 |
F x3 x1 |
(m3 |
m1 ) ( 3 |
1 ) 2m3 1 |
|
|
|
= ( 2 + 3 ) - ( 0 + 0 ) - 2 • 0 = 5 |
||
F x3 |
x2 |
(m3 |
m 2 ) ( 3 |
2 ) 2m3 2 |
|
|
= ( 2 + 4 ) - ( 0 + 0 ) - 2 • 0 = 6 |
||
F x3 |
x3 |
(m3 |
m 3 ) ( 3 |
3 ) 2m3 3 |
|
|
= ( 2 + 2 ) - ( 0 + 0 ) - 2 • 2 = 0 |
||
Получили, что для 5 пар модулей F > 0. Теперь находим пару, для которой F = |
||||
max. Этой парой будет Х 3Х |
2, для которой F = 6, т.е. перестановка Х 3 и Х 2 местами |
|||
дает уменьшение количества связей на 6. Распределение модулей после первой перестановки показано на рис. 3.3. Количество межблочных связей стало равным 22 - 6 =
16. Чтобы производить оптимизацию дальше, необходимо вычислить все функционалы для модулей блоков Х , Х (рис. 3.3).
F x |
|
x |
|
(m |
m |
1 |
) |
( |
|
1 |
|
1 |
1 |
|
|
1 |
|
|
|
|
|
= ( 3 + 3 ) - ( 5 + 0 ) - 2 |
||||
F x |
|
x |
3 |
(m |
m |
3 |
) |
( |
|
1 |
|
1 |
|
|
1 |
||
|
|
|
|
= ( 3 + 0 ) - ( 5 + 2 ) - 2 |
||||
Х
|
Х1 |
3 |
Х2 |
5 |
4 |
|
||
|
|
2 |
|
Х3 |
|
5
4
Х
Х2
Х1
Х3
)
1
3 = -5
)
3
0 = - 4
4
2m1 1
2m1 3
Х
Х1
Х2
Х3
24
|
Х |
|
Х |
|
Х1 |
3 |
Х1 |
Х2 |
5 |
|
Х3 |
|
|
||
|
4 |
|
Х3 |
|
Х2 |
|
|
|
|
4 |
|
|
|
4 |
5 |
|
|
|
|
|
|
Х |
|
Х2
Х1
Х3
Рис. 3.3. Распределение модулей после первой перестановки.
F x |
|
x |
|
(m m |
|
) ( |
|
|
) |
2m |
|
|
|
1 |
|
3 |
1 |
|
3 |
|
1 |
3 |
|
1 3 |
|
|
|
|
|
= ( 3 + 0 ) - ( 5 + 2 ) - 2 0 = - 4 |
|
|
||||||
F x |
2 |
x |
|
(m m ) ( |
2 |
1 |
) 2m |
1 |
||||
|
1 |
2 |
|
1 |
|
|
2 |
|||||
|
|
|
|
= ( 0 + 3 ) - ( 4 + 0 ) - 2 0 = - 1 |
|
|
||||||
F x |
|
x |
|
(m m ) ( |
|
|
) 2m |
|
||||
|
2 |
|
3 |
2 |
|
3 |
|
2 |
3 |
|
2 |
3 |
|
|
|
|
= ( 0 + 0 ) - ( 4 + 2 ) - 2 0 = - 6 |
|
|
||||||
F x |
|
x |
|
(m m ) ( |
|
|
) |
2m |
|
|||
|
2 |
3 |
2 |
3 |
|
2 |
3 |
|
2 |
3 |
||
|
|
|
|
= ( 0 + 0 ) - ( 4 + 2 ) - 2 0 = - 6 |
|
|
||||||
F x |
|
x |
|
(m m ) ( |
|
|
) 2m |
|
||||
|
2 |
|
1 |
2 |
|
1 |
|
2 |
1 |
|
2 |
1 |
|
|
|
|
= ( 0 + 3 ) - ( 9 + 0 ) - 2 0 = - 6 |
|
|
||||||
F x |
2 |
x |
3 |
(m m ) ( |
2 |
3 |
) 2m |
3 |
||||
|
|
2 |
|
3 |
|
|
2 |
|||||
|
|
|
|
= ( 0 + 0 ) - ( 9 + 2 ) - 2 0 = - 11 |
|
|
||||||
F x |
|
x |
|
(m m ) ( |
|
|
) 2m |
|
|
2 |
|
3 |
2 |
3 |
2 |
3 |
2 3 |
25
= ( 0 + 0 ) - ( 9 + 2 ) - 2 0 = - 11
Все вычисленные F < 0, это означает, что перестановки пар модулей,
находящихся в блоке Х
и Х , нецелесообразны, то есть оптимизация между этими блоками достигнута.
Теперь проведем оптимизацию межблочных соединений между блоком Х |
и Х . |
||||||||||||||
Для этого вычислим F для всех пар модулей, находящихся в блоках Х и Х |
(рис. 3.3). |
|
|
||||||||||||
F x |
|
x |
|
|
(m m ) ( |
|
|
) 2m |
|
|
|
|
|
||
|
1 |
|
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
= ( 0 + 0 ) - ( 0 + 0 ) - 2 0 = 0 |
|
|
|
|
|
|
||||
F x x |
|
|
(m m ) ( |
|
|
) 2m |
|
|
|
|
|
||||
1 |
|
2 |
1 |
2 |
|
1 |
2 |
1 |
2 |
|
|
|
|
||
|
|
|
|
|
= ( 0 + 5 ) - ( 0 + 0 ) - 2 0 = 5 |
|
|
|
|
|
|
||||
F x x |
|
|
(m m ) ( |
|
|
) 2m |
|
|
|
|
|
||||
|
1 |
|
3 |
1 |
3 |
|
1 |
3 |
1 |
3 |
|
|
|
|
|
|
|
|
|
|
= ( 0 + 0 ) - ( 0 + 0 ) - 2 0 = 0 |
|
|
|
|
|
|
||||
F x |
|
x |
1 |
(m m |
1 |
) ( |
|
1 |
) 2m |
1 |
|
|
|
|
|
|
3 |
|
|
3 |
|
3 |
3 |
|
|
|
|
||||
|
|
|
|
|
= ( 5 + 0 ) - ( 2 + 0 ) - 2 0 = 3 |
|
|
|
|
|
|
||||
F x |
3 |
x |
2 |
(m m ) ( |
3 |
2 |
) 2m |
2 |
|
|
|
|
|||
|
|
3 |
2 |
|
3 |
|
|
|
|
||||||
|
|
|
|
|
= ( 5 + 5 ) - ( 2 + 0 ) - 2 5 = - 2 |
|
|
|
|
|
|||||
F x |
|
x |
3 |
(m m |
3 |
) ( |
|
3 |
) 2m |
3 |
|
|
|
|
|
|
3 |
|
|
3 |
|
3 |
3 |
|
|
|
|
||||
|
|
|
|
|
= ( 5 + 0 ) - ( 2 + 0 ) - 2 0 = 3 |
|
|
|
|
|
|
||||
F x |
|
x |
1 |
(m m |
1 |
) ( |
|
1 |
) 2m |
1 |
|
|
|
|
|
|
3 |
|
|
3 |
|
3 |
3 |
|
|
|
|
||||
|
|
|
|
|
= ( 0 + 0 ) - ( 2 + 0 ) - 2 0 = - 2 |
|
|
|
|
|
|||||
F x |
|
x |
|
2 |
(m m |
2 |
) ( |
|
2 |
) 2m |
2 |
|
|
|
|
|
3 |
|
|
3 |
|
3 |
3 |
|
|
|
|
||||
|
|
|
|
|
= ( 0 + 5 ) - ( 2 + 0 ) - 2 0 = 3 |
|
|
|
|
|
|
||||
F x |
|
x |
|
3 |
(m m |
3 |
) ( |
|
3 |
) 2m |
3 |
|
|
|
|
|
3 |
|
|
3 |
|
3 |
3 |
|
|
|
|
||||
|
|
|
|
|
= ( 0 + 0 ) - ( 2 + 0 ) - 2 0 = - 2 |
|
|
|
|
|
|||||
В результате вычислений получили, что для четырех пар модулей |
F > 0. Теперь |
||||||||||||||
находим ту пару модулей, для которой |
F = max. Этой парой является пара x и |
x |
2 |
, |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
для которой F = 5, что означает уменьшение количества межблочных соединений на 5
при перестановке местами этих модулей. Распределение модулей после этой (второй)
перестановки показано на рис. 3.4. Общее количество межблочных соединений уменьшилось еще на пять и стало равным 16 - 5 = 11.
По рис. 3.4 видно, что число межблочных соединений между блоками Х и Х
равно 0, то есть оптимизация между этими блоками достигнута. Достижение оптимизации