Метод итерационного улучшения

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

Если имеется некоторое исходное решение, то генерация других вариантов может быть выполнена путем допустимых по смыслу задачи перестановок элементов в подмножествах, либо в парах взаимнооднозначных соответствий. Осуществляются те перестановки, которые приводят к улучшению целевой функции с учётом заданных ограничений. Для выбора переставляемых элементов должна существовать некоторая мера. Как правило, хорошей мерой является приращение значения целевой функции, а также может использоваться некоторый критерий, который имеет с ней сильную корреляцию. Перестановки могут быть парными и групповыми. Рассмотрим парные перестановки:

Критерий оптимизации – минимальное количество рёбер, попадающих в разрез.

Если поменять X_i и Х_j, то количество рёбер уменьшится с 3 до 2

Для всех пар необходимо подсчитать DF. Выбирается та пара, у которой DF³0 и максимальна. Процесс заканчивается если:

1. нет DF>0,

2. .

3. DF£e

4. K=K_доп -допустимое количество итераций

В ряде случаев количество операций может быть ограничено некоторой константой.

 

Этот метод гарантирует лишь нахождение локального оптимума. Избежать этого позволяют групповые перестановки. Их идея заключается в следующем: для всех и получаем и выбираем не проверяя условия . Процесс продолжается до тех пор, пока не будут выполнены все парные перестановки. При этом подсчитывается суммарное приращение . Определяется перестановка, для которой P>0 и максимальна. Т.о. определяется группа вершин, принадлежащих Х₁ и вершин, принадлежащих Х₂, для которых и выполняется перестановка.

 

.

 

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

Асимптотическая оценка вычислительной сложности итерационного алгоритма О(n³). Сокращение затрат машинного времени возможно за счёт сокращения числа перестановок. К сокращению перестановок приводит упорядочивание элементов в исходных множествах в соответствии с некоторой мерой. Рассмотрим один из способов упорядочивания:

или подсчитываем величину вклада любого элемента в значение целевой функции. Элементы множества Х упорядочиваются по убыванию вклада подсчитанной оценки. (для другого варианта). Далее в качестве кандидатов на обмен на любом шаге К рассматриваем: