Консалтология Общая теория консалтинга (стр. 105 )

В общем случае

(10.234)

F =

Поскольку из связей (10.234) можно получить неравенство

F s+1j( s+1j)≤ F s+1j( sj),

совместное рассмотрение которого с выражениями (10.183), (10.184) дает

F ≤

то

F ≤ F , s = 0, 1...

Таким образом, алгоритм обеспечивает монотонное изменение показателя эффективности МСК. Поскольку он ограничен снизу и изменяется на замкнутом ограниченном (конечном) множестве, ал­горитм сходится к некоторой неулучшаемой стратегии А, а усло­вие остановки будет As+1 = As.

Для уменьшения перебора используем тот факт, что поскольку на каждом шаге при изменении стратегии заменяется лишь один ее элемент, из перебора исключаются элементы у Y, расположенные не далее чем на z от элементов уже рассмотренных стратегий А. Аналогично из перебора исключаются элементы уY, располо­женные не далее чем на z от элементов уже рассмотренных страте­гий, где z удовлетворяет условию

z< (10.235)

являющемуся следствием из условий (10.208), (10.209).

Алгоритм улучшения несколько более трудоемок, чем рас­смотренный выше алгоритм распределения, но и несколько эффек­тивнее его. Обозначим через FA,j значение показателя эффективности МСК на области Дирихле j-го элемента стратегии А. По условиям (10.183), (10.184)

F ≤

Пусть A0={у0j}j = 1,..., т, — некоторая начальная страте­гия. Для любого элемента у Yк можно вычислить

∆0(у)= (-F +F )=-F +F ).(10.236)

Произведем перебор у YK, для которых вычисляется выраже­ние (10.236). Если для некоторого у YK оказывается

∆0()<0 и F ≤F , (10.237)

то А0 замещается новой стратегией:

А1 = (А0\у0) ,

т. е. элемент у заменяется элементом , и процесс продолжается. Он прекращается, когда

∆p()≥0 yYK.

Таким образом, в общем случае

∆s(у)= ( F -F )=F;

As(s)<0 при Fs+1A ≤FsA

As+1= (As\ysjs) s, s=0,1,…

С учетом этого условие (10.237) означает

F ≤F , s = 0, 1,...,

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

Перейдем к конструированию рационального управления об­щим алгоритмом оптимизации MCК (рис. 10.59).

Рис. 10.59. Блок-схема общего алгоритма оптимизации МСК

Его основными функ­циональными составляющими являются:

- выявление и уточнение коэффициентов, характеризующих вы­числительные особенности решаемой задачи;

- прогнозирование вычислительных характеристик различных вариантов организации решения задачи и выбор в возможном диа­логе с пользователем варианта, наиболее соответствующего вы­деленным вычислительным ресурсам;

- расчет оценок, необходимых для модификации сетей в множе­ствах X и Y;

- модификация сетей;

- оптимизация МСК с конечным внешним множеством и множест­вом стратегий.

Структурные составляющие (блоки) алгоритма объединяют, в отдельных случаях, несколько функциональных составляющих.

Исходными данными для алгоритма являются описание опти­мизируемой МСК, т. е. множеств X, Y (в том числе п, р, Ω, ΩY) и функции локальной эффективности ρ (х, у), а также типа МСК и для ИМСК, порождающей функции G(t). Кроме того, могут быть заданы постоянные Липшица LX, LY, число элементов стратегии т, точность решения z, машинное время Т и объем памяти W.

Если они не заданы, то LX, LY устанавливают в процессе решения, а m, ε, Т и W уточняют в диалоге по мере прогнозиро­вания вычислительных характеристик решения и получения про­межуточных результатов.

После ввода исходных данных производится формирование пробной сети Х1 Y1 и оптимизация соответствующей пробной МСК с использованием всех наличных алгоритмов оптимизации МСК с конечными множествами. Пробные сети формируют возможно более грубыми, содержащими малое число элементов, с тем, чтобы выполнение указанной операции требовало сравнительно малого машинного времени и заведомо было обеспечено вычислительными ресурсами. Цель формирования и оптимизации пробной МСК со­стоит в том, чтобы получить приближенные значения коэффициен­тов, характеризующих вычислительные особенности задачи. К ним относятся: LX, LY (если они не заданы); Сх, Су— связывающие параметры сетей с числом элементов в них; С0, Ср, Су —определяю­щие трудоемкость различных алгоритмов оптимизации; d0, dp, dy, dlK, d2K, d3K — задающие объемы памяти, необходимые для различных алгоритмов оптимизации; α, z, ycp — характеризую­щие возможность отбрасывания элементов сетей при модификации.

Одновременно подсчитывают (хотя и очень грубые) оценки для оптимального значения показателя эффективности, которые уже используют на следующем шаге для уменьшения переборов.

После получения перечисленных характеристик прогнозируют время счета и объем памяти для различных вариантов организации решения. Каждый вариант представляет собой ряд последова­тельных модификаций сетей в множествах X и Y, к каждой из которых применяют алгоритмы оптимизации МСК с конечными множествами. Число модификаций и параметры сетей устанавли­вают в соответствии с анализом, проведенным выше, так что раз­личные варианты отличаются друг от друга набором и последова­тельностью применяемых алгоритмов оптимизации. Целесообразно рассмотреть 8 вариантов алгоритмов. Дадим их описание, обозна­чая: К — комбинаторный алгоритм, О — алгоритм оценок, Р — алгоритм распределения, У — алгоритм улучшения.

Вариант К — используется комбинаторный алгоритм. При т > 2 этот вариант требует заведомо больше времени, чем все остальные, зато гарантирует отыскание с заданной точностью абсолютно оптимального решения.

Вариант О (У) — используется алгоритм оценок. При т > 2 требует меньше времени, чем вариант К, но значительно больше, чем при использовании алгоритмов распределения и улучшения. Гарантирует получение двусторонней оценки для показателя эф­фективности абсолютно оптимального решения. Если его решение целочисленно, то тем самым определяется абсолютно оптимальное решение; если нецелочисленно, то ближайшее целочисленное реше­ние отыскивается алгоритмом улучшения. Важным параметром варианта является

δуп ≥ δ*j — параметр сети в Y, начиная с ко­торого следует переходить к атгоритму улучшения.

Вариант РУ — используется алгоритм распределения вплоть до δ*j - сети в Y, после чего однократно применяется алгоритм улуч­шения. Это самый быстрый вариант, однако полученное им реше­ние лишь неулучшаемо, оно может не быть абсолютным оптиму­мом. О степени близости к абсолютному оптимуму можно судить по оценкам, полученным после оптимизации пробной МСК. Его рекомендуется использовать, если известно начальное прибли­жение стратегии, улучшение которого заведомо приведет к абсо­лютному оптимуму, а также для быстрого получения ориентиро­вочных результатов в задаче.

Вариант У—используется алгоритм улучшения. Время счета несколько больше, чем при варианте РУ, зато полученное решение может быть лучше (по показателю эффективности), чем в варианте РУ. В остальном справедливо все, сказанное о преды­дущем варианте.

Вариант РУК — до получения сети в Y с параметром δуп используется алгоритм распределения, затем однократно приме­няется алгоритм улучшения. Полученное решение используется для оценок, уменьшающих перебор в комбинаторном алгоритме, который применяется вплоть до получения заданной точности решения. Здесь обеспечивается отыскание абсолютного минимума, а машинное время может оказаться меньше, чем в варианте К, если затраты времени на работу алгоритмов распределения и улучшения будут перекрыты экономией за счет уменьшения переборов.