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

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

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

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

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

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

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

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

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

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

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

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

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