Итерационный алгоритм парных перестановок

Дано начальное размещение элементов (или результат предыдущей итерации). Выбирают элементы х_i и х_j и меняют местами. Рассчитывается F_(p) для этого нового варианта, если оно меньше прежнего, то перестановка осуществляется. Выбирается другая пара элементов и процесс повторяется пока не сработает правило остановки.

Рассмотрим случай, когда в качестве критерия используется минимальная суммарная длина соединений:

n n

F _(p) = ∑ ∑ r _ij d _p(i)p(j),

i=1 j=i+1

где R=||r_ij||_nxn (матрица соединений) и D=||d_ij||_nxn (матрица расстояний).

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

Имеем массив позиций. Расстояние между соседними позициями равно единице.

М_i­

i
				Мi®

i

Рис.6.4.1

Обозначим изменение суммарной длины соединений при перемещении элемента х_i

в позицию сверху М_i­

в позицию снизу М_i¯

в позицию слева М_i

в позицию справа М_i®

При перемещении элемента в позицию слева изменение суммарной длины соединений

М_i = ∑ r _ij - ∑ r _ij

j, x_j < x_i j, x_j³x_i

При перемещении элемента влево сокращается на единицу длина его соединений со всеми элементами, находящимися левее i–го столбца и увеличивается на единицу длина соединений со всеми элементами, расположенные в i–ом столбце и правее его.

Аналогично получаем выражения для трех других характеристик.

Теперь найдем приращение суммарной длины при перестановке двух элементов.

Очевидно y_i = y_j, а х_j = х_i +1

DF_ij®= М_i® + М_j -2 r_ij

2 r_ij – поправочный член. Он учитывает связи i–го и j–го элементов друг с другом, т.к. они использовались при расчетах М_i® и М_j.

Для вертикального расположения переставляемых элементов (х_i = х_j; y_j = y_i +1)

DF_ij­¯= М_i­ + М_j¯ -2 r_ij

Для сокращения времени поиска лучшей перестановки используют таблицу предпочтений, куда записывают характеристики М_i®, М_j, М_i­, М_j¯.

По таблицам находят максимально положительную характеристику и совершают данную перестановку.

Рассмотрим пример.

Исходные данные: коммутационная схема, начальное размещение и матрица соединений (R).

Коммутационная схема

	x1 x2 x3 x4 x5 x6 x7
x1	0 1 1 1 1 0 0
x2	1 0 2 1 1 0 0
x3	1 2 0 2 0 1 1
R = x4	1 1 2 0 0 1 1
x5	1 1 0 0 0 1 1
x6	0 0 1 1 1 0 3
x7	0 0 1 1 1 3 0

Рис.6.4.2 - начальное размещение

Первый элемент – это разъем, с ним связаны все внешние цепи схемы; перестановкам этот элемент не подлежит. Строим таблицу предпочтений:

		М®	М	М­	М¯.
		-	-	-	-
			-		-
					-
			-	-
		-		-
		-			-
			-4	-

Рис.6.4.3

1 шаг. Перемещаем 4-ый элемент вправо, влево.

Рассчитаем характеристики перемещения для элемента 4, находящегося в первой позиции: М_® (4)=1+2+1+1-1=4, М_¯ (4)= 1+2+1-1=3.

По наибольшей положительной характеристике выбираем соседний предполагаемый к обмену элемент 7 и рассчитываем встречную характеристику: М (7)= 1-1-1-3= -4. Рассчитываем суммарную характеристику обмена: DF_® (4,7) =4-4-2*1= -2.

Так как DF _® (4,7) <0, то выбираем следующую по величине положительную характеристику элемента 4, определяем соответствующий соседний элемент и рассчитываем его характеристику: М_­ (2)= 1+1-2=0. Тогда DF_­¯ (4,2) =3+0-2*1=1. Так как DF_­¯ (4,2) >0, то меняем местами элементы 4 и 2 и получаем новое размещение.

Рис.6.4.4

2 шаг.

Проводим аналогичные расчеты для всех оставшихся позиций.

Характеристики перемещения для элемента 7: М (7) = - 4; М_¯ (7) = 4; М_® (7) = 2.

По наибольшей положительной характеристике выбираем соседний предполагаемый к обмену элемент 3 и рассчитываем встречную характеристику: М_­ (3)=0. Рассчитываем суммарную характеристику обмена: DF_­¯ (7,3) = 2 – производим обмен и получаем новое размещение.

Рис.6.4.5

3 шаг.

Характеристики элемента 5: М (5)=0; М_¯ (5)= 1;

встречная характеристика М_­ (6)= -2; характеристика обмена DF_­¯ (5,6) = -3 – обмен не производим.

Характеристики элемента 4: М_­ (4)= 1; М_® (4) =4;

встречная характеристика М (7)= - 4; характеристика обмена DF_® (4,7) = -2 – обмен не производим; встречная характеристика М_¯ (2)= -2; характеристика обмена DF_­¯ (4,2) = -3 – обмен не производим.

Характеристики элемента 7: М_® (7)= 2 (другие характеристики можно не рассматривать, так как они анализировались раньше); встречная характеристика М (6)= 4; характеристика обмена DF_® (7,6)= 0 – обмен не производим.

Характеристики элемента 6 не рассматриваем, так как они уже анализировались. Итоговое размещение на рис. второго шага.