6.2.3.5. Алгоритм глобальной минимизации критерия оптимальности Q(U) [114]

Будем «глобализировать» алгоритм, описанный в подразделе

6.2.3.4. Это можно сделать двумя способами. Прежде всего, применим случайный выбор исходных разрезаний:

удовлетворяющих ограничениям 5 на размер сегментов. Локальный спуск с помощью описанного выше алгоритма из каждой начальной точки (6.2.74) дает локальные оптимумы

Естественно глобальный оптимум оценивать лучшим из локальных:

Другой мерой, «глобализирующей» алгоритм, является введение возможности ухудшения критерия. Для этого достаточно формулы (6.2.61), (6.2.63) и (6.2.65) записать соответственно в виде

где в ограничениях вместо нуля введен параметр а. При возможно увеличение минимизируемого критерия и образуются предпосылки «перевала» в зону глобального экстремума. Очевидно, что на эту меру следует идти лишь попав в локальный экстремум.

Рис. 6.2.7. Поведение связности графа в процессе адаптации. Штриховкой отмечены интервалы времени, когда

Алгоритм глобального разрезания в этом случае представляется таким образом. При достигается локальный экстремум который запоминается вместе с Далее параметр а на некоторое число шагов увеличивается и затем снова Полученное локальное значение критерия сравнивается с Если вместо запоминаются как лучшее решение и , в противном случае поиск продолжается, и т. д. Легко заметить, что в результате работы алгоритма шансы найти глобальный экстремум со временем увеличиваются.

Приведем пример работы этого алгоритма [114]. Рассматривается граф с который необходимо разрезать на семь подграфов, т. е. при ограничениях Веса всех вершин графа одинаковы и равны единице Значения функции качества в локальных минимумах бьши следующими:

Начальное значение функции качества . В качестве глобального решения получено разрезание, при котором функция качества имеет значение

На рис. 6.2.7 показана динамика поведения критерия при поиске. В моменты вводились рандомизированные изменения начальных условий, что вызвало резкое увеличение критерия.

Таким образом, разумное оперирование обоими средствами глобализации позволяет эффективно и без лишних затрат оценивать глобальный экстремум в задаче о разрезании.