Итерационные алгоритмы улучшения начального размещения
Для этих алгоритмов необходимо задать начальный вариант размещения.
Итерационные алгоритмы применяются для решения задачи размещения с различными критериями оптимизации: суммарная длина соединений, наиболее длинная связь, суммарное число пересечений соединений и т.д.
В любом итерационном алгоритме исследуется подмножество размещений, в некотором смысле близких к начальному, для выделения в нем размещения с меньшим значением функции - критерия. Найденное размещение вновь принимается за начальное и процесс повторяется. Алгоритм завершается при отыскании некоторого размещения, в окрестности которого отсутствуют варианты с меньшим значением функции - критерия. В большинстве случаев такой процесс приводит к получению локального минимума функции - критерия.
В качестве начального может быть взято размещение, полученное конструктивным алгоритмом размещения, с помощью генератора случайных размещений или заданное конструктором.
Простейшим итерационным алгоритмом является алгоритм парных перестановок.
Он заключается в cледующем: в начальном размещении меняются местами два элемента и для новой конфигурации вычисляется функция – критерий. Если наблюдается уменьшение функции, то новое размещение заменяет старое, в противном случае этого не происходит. Затем выбирается другая пара элементов и процесс повторяется до тех пор, пока не будет применено правило остановки.
Рассмотрим алгоритм парных перестановок, в котором в качестве функции – критерия используется максимальная длина соединений. Такие задачи называют минимаксными (минимизация максимальной длины соединений). Данный критерий позволяет легко определять пары элементов для перестановки.
Алгоритм состоит из следующих шагов:
1. Для каждой пары соединенных вершин ei и ej вычисляется длина проводника
lij= |xi - xj| + |yi - yj|, где xi , yi и xj, yj координаты вершин ei и ej в размещении.
2. Определяются maxlij (если их несколько, то подсчитывается их количество k) и вершины ei, ej, дающие этот максимум.
3. Вершина ei переставляется в размещении с соседней вершиной такой, что она находится слева или справа и сверху или снизу от ei и ближе к ej.
4. Для нового размещения повторяется п.1.
5. Определяются maxl’ij (и их количество k’).
6. Если maxlij > maxl’ij или maxlij = maxl’ij и k > k’, то переход к п.3, в противном случае прежнее размещение восстанавливается.
7. Вершина ej переставляется в размещении с соседней вершиной такой, что она находится слева или справа и сверху или снизу от ej и ближе к ei.
8. Пока есть не рассмотренные соседи вершины ej выполняются п.п. 4-6.
9. Итерационный процесс заканчивается.
Пусть дано размещение рис. 6.9 (а).
Рисунок 6.9. Положение элементов: до (а) и после перестановки (б)
Значение функции F(р)=18.
1. Для каждой пары соединенных вершин ei и ej вычислим lij:
l12=1; l13=2; l24=2; l25=1; l34=3; l56=1; l57=2; l68=2; l78=1; l79=2; l89=1.
maxlij = l34 = 3.
2. Меняем местами вершины e3 и e2 (рис. 6.9 (б)).
3. Для каждой пары соединенных вершин ei и ej вычислим новые l’ij:
l12=2; l13=1; l24=3; l25=2; l34=2; l56=1; l57=2; l68=2; l78=1; l79=2; l89=1.
maxl’ij = l24 = 3. Максимальная длина не уменьшилась, возвращаем размещение (рис. 6.9 (а)).
4. Меняем местами вершины e3 и e6 (рис. 6.10 (а)).
Рисунок 6.10. Перестановка элементов e3 и e6 (а); e4 и e5 (б)
5. Для каждой пары соединенных вершин ei и ej вычислим новые l’ij:
l12=1; l13=3; l24=2; l25=1; l34=2; l56=2; l57=2; l68=3; l78=1; l79=2; l89=1.
maxl’ij = l13 = l68 =3. Максимальная длина не уменьшилась, возвращаем размещение (рис. 6.9 (а)).
6. Меняем местами вершины e4 и e5 (рис. 6.10 (б)).
7. Для каждой пары соединенных вершин ei и ej вычислим новые l’ij:
l12=1; l13=2; l24=1; l25=2; l34=2; l56=2; l57=1; l68=2; l78=1; l79=2; l89=1.
maxl’ij=l13=l25=l34= l56= l68= l79=2. Максимальная длина уменьшилась. Сохраняем полученное размещение. Количество максимумов k = 6.
8. Меняем местами вершины e1 и e2 (рис. 6.11 (а))
Рисунок 6.11. Перестановка элементов e1 и e2 (а); e4 и e5 (б)
9. Для каждой пары соединенных вершин ei и ej вычислим новые l’ij:
l12=1; l13=1; l24=2; l25=1; l34=2; l56=2; l57=1; l68=2; l78=1; l79=2; l89=1.
maxl’ij = 2. Максимальная длина не изменилась. Количество максимумов k’=5< k. Сохраняем полученное размещение, k=5.
10. maxl’ij = l24= l34=l56= l68= l79=2. Меняем местами e2 и e1 и возвращаемся к размещению рис. 6.10 (б).
11. Меняем местами e2 и e5 (рис.6.12 (б)).
12. Для каждой пары соединенных вершин ei и ej вычислим новые l’ij:
l12=2; l13=1; l24=1; l25=1; l34=2; l56=3; l57=2; l68=2; l78=1; l79=2; l89=1.
maxl’ij = l56=3. Максимальная длина увеличилась. Возвращаем размещение.
13. Меняем местами e4 и e5 (рис.6.12 (а)).
14. Для каждой пары соединенных вершин ei и ej вычислим новые l’ij:
l12=1; l13=1; l24=1; l25=2; l34=3; l56=1; l57=2; l68=2; l78=1; l79=2; l89=1.
maxl’ij = l34=3. Максимальная длина увеличилась. Возвращаем размещение.
15. Меняем местами e4 и e1 (рис.6.12 (б)).
16. Для каждой пары соединенных вершин ei и ej вычислим новые l’ij:
l12=2; l13=2; l24=1; l25=1; l34=1; l56=2; l57=1; l68=2; l78=1; l79=2; l89=1.
17. maxl’ij = 2. Максимальная длина не изменилась. Количество максимумов k’ = 5 = k.
Возвращаем размещение рис. 6.11 (а).
Длину соединения (e2, e1) уменьшить не удалось. Алгоритм заканчивает работу.
Значение функции F(р)=16.
Заметим, что если в размещении рис. 6.11 (а) поменять местами элементы e8 и e9 (рис. 6.12 (в)), то количество максимумов уменьшится (k’ =4). Значение функции F(р)=15. Но максимальная длина останется такой же, поэтому алгоритм заканчивает работу при первой неудачной попытке уменьшения maxl’ij.
Рисунок 6.12. Перестановка элементов e4 и e5 (а); e4 и e1 (б); e8 и e9 (в)
Алгоритм групповых перестановок
Классическим алгоритмом такого типа является алгоритм Штейнберга. В алгоритме используется тот факт, что для множества несвязных между собой элементов задача минимизации СДС сводится к задаче о линейном назначении.
Пусть W={e1, e2, …, ek} - некоторое несвязное множество элементов, а L={p1, p2, …, pk} – множество позиций, занятых этими элементами в исходном размещении. Можно составить матрицу А = ||аij||k´ k, элемент аij которой представляет собой суммарную длину соединений элемента еiÎ W, при условии его установки в позицию рjÎ L. Поскольку элементы в W не связаны, значение аij не зависит от положения других элементов W. Решая задачу линейного назначения для матрицы А, получим оптимальное размещение элементов из W в позициях L, для которого СДС оптимальна.
Последовательно исследуются различные несвязные множества элементов, для которых решается задача линейного назначения.
В целом алгоритмы размещения с групповыми перестановками характеризуются значительными временными затратами. Эффективность алгоритма О(m3), где m = |W|.
Среди итерационных алгоритмов наиболее эффективны алгоритмы парных перестановок. Они позволяют уменьшить длину межсоединений от 1% до 50% в зависимости от качества начального размещения. Наибольшая скорость уменьшения длины соединений наблюдается на первых итераций. Длина монотонно уменьшается к значениям, близким к 1% при числе итераций n > 5.
Непрерывно-дискретные методы размещения
Для данного класса алгоритмов в отличие от рассмотренных, задание фиксированного набора позиций не обязательно - размещение осуществляется на непрерывной плоскости.
Примером алгоритмов данного класса может служить метод силовых функций. Он основан на следующей механической аналогии. Элементы считаются материальными точками, на которые действуют силы притяжения и отталкивания. Сила притяжения между элементами ei и ej полагается пропорциональной расстоянию между ними. Силы отталкивания вводятся для предотвращения слияния или перекрытия элементов. Далее осуществляется поиск состояния равновесия системы материальных точек, которое и определяет размещение элементов на плоскости.
Сила притяжения вычисляется следующим образом:
Fij = kf rij dp(i)p(j), где kf – коэффициент.
Сила отталкивания вычисляется следующим образом:
Fij = kj / dp(i)p(j), где kj – коэффициент.
Составляется система дифференциальных уравнений, описывающая движение материальных точек к положению равновесия.
После решения системы, каждый из элементов ei, имеющий координаты (xi , yi), перемещается в ту из незанятых позиций ps, для которой изменение суммарной длины соединений минимально.
Метод силовых функций трудоемок и требует подбора коэффициентов опытным путем.
Метод ветвей и границ и непрерывно-дискретные алгоритмы размещения из-за их трудоемкости применяются лишь для задач небольшой размерности (n £ 20).
Достаточные результаты достигаются сочетанием конструктивного алгоритма (сложность ~ О(n)) с улучшающим итерационным (сложность ~ О(n2) ¸ О(n4)).
Популярное:
