6.4 Итерационные алгоритмы улучшения начального размещения

Для алгоритмов этой группы задают начальный вариант размещения. Например, используя последовательный алгоритм. В итерационных алгоритмах используют различные критерии оптимизации:

 суммарная длина соединений;

 суммарное число пересечений соединений.

Исследуются несколько вариантов размещения, близких к начальному. Лучшим считается тот, который имеет минимальное значение критерия. Найденное размещение вновь принимается за начальное, и процесс повторяется. Алгоритм завершен, когда вокруг занятых позиций отсутствуют варианты с меньшим значением функции-критерия.

Пусть F_(p) - функция-критерий размещения, p_нач - начальное размещение. В процессе работы алгоритма получаем последовательность размещений p_нач, p₁, p₂,…, p_. этой последовательности соответствует монотонно убывающая последовательность значений F_(pнач)  F_(p1)  F_(p2)  F_(p). Особенность итерационного процесса в том, что можно остановиться на любом шаге.

На практике процесс заканчивается, когда разность значений функции-критерия для двух соседних итераций становиться относительно малой:

Структура итерационных алгоритмов размещения:

1 преобразование очередного размещения;

2 вычисление функции размещения;

3 выбор лучшего размещения на основе п.2.;

4 переход к следующей итерации и правило остановки.

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

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

Дано начальное размещение элементов (или результат предыдущей итерации). Выбирают элементы х_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

F_ij= М_i + М_j -2 r_ij

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

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

F_ij= М_i + М_j -2 r_ij

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

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

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

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

2

3

●

4

●

5

6

●

7

●

●

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

	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

4	7	5	1
2	3	6

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

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

		М	М	М	М.
	1	-	-	-	-
	2		-	0	-
	3				-
	4	4	-	-	3
	5	-		-
	6	-			-
	7		-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. Рассчитываем суммарную характеристику обмена: F_(4,7) =4-4-2*1= -2.

Так как F_(4,7) 0, то выбираем следующую по величине положительную характеристику элемента 4, определяем соответствующий соседний элемент и рассчитываем его характеристику: М_ (2)= 1+1-2=0. Тогда F_ (4,2) =3+0-2*1=1. Так как F_ (4,2) 0, то меняем местами элементы 4 и 2 и получаем новое размещение.

2	7	5	1
4	3	6

Рис.6.4.4

2 шаг.

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

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

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

2	3	5	1
4	7	6

Рис.6.4.5

3 шаг.

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

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

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

встречная характеристика М_(7)= - 4; характеристика обмена F_ (4,7) = -2 – обмен не производим; встречная характеристика М_(2)= -2; характеристика обмена F_ (4,2) = -3 – обмен не производим.

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

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

28