Дано начальное размещение элементов (или результат предыдущей итерации). Выбирают элементы хi и хj и меняют местами. Рассчитывается F(p) для этого нового варианта, если оно меньше прежнего, то перестановка осуществляется. Выбирается другая пара элементов и процесс повторяется пока не сработает правило остановки.
Рассмотрим случай, когда в качестве критерия используется минимальная суммарная длина соединений:
n n
F (p) = ∑ ∑ r ij d p(i)p(j),
i=1 j=i+1
где R=||rij||nxn (матрица соединений) и D=||dij||nxn (матрица расстояний).
Существуют различные варианты выбора пары элементов для перестановки. Например, существуют алгоритмы, в которых для сокращения машинного времени и упрощения вычислений на каждом шаге итерации исследуются лишь перестановки соседних элементов (соседних позиций).
Имеем массив позиций. Расстояние между соседними позициями равно единице.
Мi
| ||||||
Мi® | ||||||
i
Рис.6.4.1
Обозначим изменение суммарной длины соединений при перемещении элемента хi
|
|
в позицию сверху Мi
в позицию снизу Мi¯
в позицию слева Мi
в позицию справа Мi®
При перемещении элемента в позицию слева изменение суммарной длины соединений
Мi = ∑ r ij - ∑ r ij
j, xj < xi j, xj³xi
При перемещении элемента влево сокращается на единицу длина его соединений со всеми элементами, находящимися левее i–го столбца и увеличивается на единицу длина соединений со всеми элементами, расположенные в i–ом столбце и правее его.
Аналогично получаем выражения для трех других характеристик.
Теперь найдем приращение суммарной длины при перестановке двух элементов.
Очевидно yi = yj, а хj = хi +1
DFij®= Мi® + Мj -2 rij
2 rij – поправочный член. Он учитывает связи i–го и j–го элементов друг с другом, т.к. они использовались при расчетах Мi® и Мj.
Для вертикального расположения переставляемых элементов (хi = хj; yj = yi +1)
DFij¯= Мi + Мj¯ -2 rij
Для сокращения времени поиска лучшей перестановки используют таблицу предпочтений, куда записывают характеристики М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 не рассматриваем, так как они уже анализировались. Итоговое размещение на рис. второго шага.