<<
>>

Механизмы адаптации при разбиении

Представим исходную формулировку задачи в виде адап­тивной системы, основанной на идеях коллективного поведения объектов адаптации.

Работу адаптивной системы можно представить как функци­онирование некоторого вероятностного автомата (автомата адап­тации), действующего в случайной среде [5.17, 5.18]. Под средой понимается объект управления (объект оптимизации). Функ­ции управляющего устройства реализуются автоматом адаптации (AA), выход которого A изменяется в соответствии с входом Q.

В нашем случае в качестве объекта оптимизации рассмат­ривается гиперграф, разбитый на K-узлов.

Состояние объекта оптимизации оценивается вектором S = {si| i = 1,2,...,n}, где si— номер узла, в который помещена вершина xi.

При втором способе решение представляется вектором S = = {s^i| i = 1,2,...,n}, Si = Xi.

Значением Siявляется номер некоторой вершины. Элементы si, для которых 1 ≤ i ≤ ni, соответствуют первому узлу Xl. Элементы si, для которых nι + 1 ≤ i ≤ nι + n2, соответствуют второму узлу X2 и т. д. В общем случае для элементов Si справедливо

где

Таким образом, разбиение определяется перестановкой эле­ментов xiв векторе S. Пусть P = {Si| i = 1,2,... } — про­странство возможных состояний (возможных решений задачи разбиения).

Предлагаемый алгоритм разбиения является алгоритмом слу­чайного поиска в пространстве состояний P. Aлгоритм случай­ного поиска представляется в виде коллектива вероятностных автоматов, адаптация которых производится путем введения са­мообучения в процессе их функционирования [5.19].

В качестве элементарного объекта адаптации рассматривает­ся вершина xi∈X. Коллектив объектов адаптации (их совокуп­ность) соответствует объекту оптимизации (ОО).

Пусть объект оптимизации находится в некотором состоянии Sj, т. е. задано разбиение X и соответственно распределение вершин xi по узлам.

Пусть ρ+— число гиперребер, связывающих xi∈Xvс верши­нами xj∙ ∈Xv, xi= xj∙, a ρ-— число гиперребер, связывающих xi∈Xvс вершинами xi∈Xv. На рис. 5.2 показан пример размещения вершины xi∈Xv. ρi≤ ρ++ + ρ-, где ρi— локальная степень вер­шины Xi.

Рис. 5.2. Пример разме­щения вершины xi∈Xv

Локальная цель объекта адаптации Xi — достижение такого состояния (т. е. такого распределения Xi), при котором его оценка ρ-= 0. Другими словами в процессе адаптации минимизирует­сяρ.∙ ■

Глобальная цель коллектива объек­тов адаптации заключается в достижении такого состояния S (т. е. такого распределения вершин по узлам), при котором F(S) → min.

Для реализации механизма адаптации каждому объекту xi∈X сопоставляется автомат адаптации αi, моделирующий поведение объекта адаптации в среде [4.10].

Автомат адапта­ции имеет две группы состояний: Ci = {cιi| i = 1,2,...,g}и C,2 = {c21}, соответствующие двум альтернативам Ai и A2 по­ведения объекта адаптации в среде. Здесь альтернатива A1— остаться в том же узле, A2— выйти из узла и перераспределить­ся. Таким образом, выходной алфавит автомата A = {Aι, A2}. Входной алфавит Q = {+, —} включает возможные отклики сре­ды — «поощрение» (+) и «наказание» (—).

Граф-схема переходов AA показана на рис. 5.3.

Рис. 5.3. Граф-схема переходов AA

Отклик среды для AA aiв соответствии с состоянием среды и объекта адаптации формируется следующим образом.

Если ρ-> ρ+, то всегда вырабатывается сигнал «наказа­ние» (—).

tji 1 tji

Рассмотрим процесс реализации для объектов адаптации аль­тернативы A2— «выход из узла и перераспределение».

Из всех подмножеств Xvудаляются вершины xi,для которых реализуется альтернатива A2. Все такие вершины объединяются в множество R, рис. 5.4. R = {Rv| v = 1,2, ...k}, где Rv— мно­жество вершин, удаленных из Xv.

Рис. 5.4. Пример построения множества R

Процесс переназначения вершин осуществляется последова­тельно. На каждом шаге случайным образом (равновероятно) выбирается вершина xi∈R. Для нее определяется множество доступных узлов. Узел xvявляется доступным, если после на­значения в него xiдопустимый вес pvили допустимое число вершин nv не будут перекрыты.

Обозначим через ρvчисло гиперребер связывающих выбран­ную xiс доступным узлом — число связей xi

с доступными узлами. v

Пусть w — число доступных узлов.

Назначение xi в один из доступных узлов осуществляется вероятностным способом. Вероятность назначения xiв недоступ­ный узел равна нулю.

Вероятность попадания xiв один из доступных узлов xv пропорциональна числу связей xiс Xvи определяется как

Pi— распределение вероятности назначения для xi. Pi— рас­считывается только для выбранной для переназначения вершины xi. С помощью параметра δ осуществляется управление распре­делением вероятностей для xi.

В работе используется подход, аналогичный методу модели­рования отжига [21].

Параметр δ вычисляется по формуле

αn, αo, Δα — управляющие параметры, задаваемые заранее (выбираемые из эвристических соображений). Величина δ имеет максимальное значение на первой итерации работы адаптивной системы. Параметр δ последовательно уменьшается и приобре­тает минимальное значение на итерации To и после этого не меняется. В процессе переназначения множества R на итерации t параметр δ не меняется.

Чем больше δ, тем более близкими (рав­новероятными) становятся значения p% ∈ Pi. Другими словами, на первых итерациях переназначаемые элементы имеют большую степень свободы и меньшую степень зависимости от pV, поэтому элемент xi может попасть в узел, с которым он не связан. После выполнения T0итераций, если, при переназначении, xi имеет связи с доступными узлами, то вероятность попадания xi в доступный узел, с которым нет связей, близка к нулю.

Отметим, что δ не может быть равной нулю, (а следовательно, и αo), ибо возможна ситуация в процессе переназначения R, когда будет выбрана такая вершина xi, что для всех доступных узлов ρV = 0, ^ρi = 0.

Такой подход к расчету распределения вероятности назначе­ния вершины создает условия для выхода из локальных оптиму- мов.

Представим псевдокод адаптивного алгоритма разбиения.

Algorithm Адаптивное разбиение

begin

граф=ИСХОД_ДАННЫЕ; управление=НАСТРОЙКА; решение=ИСХ0Д_РАЗБИЕНИЕ(граф);

лучш_решение= решение; состоян_аа=НАЧ_С0СТ0ЯНИЕ; итерация=ЧИСЛО_ИТЕРАЦИЙ;

while (итерация > 0) do {параметры_оа=РАСЧЕТ(решение);

отклик=РЕАКЦИЯ(параметры_оа); состоян_аа=ПЕРЕХОД(состоян_аа, отклик); вершина=ВЫХОД(граф, состоян_аа); решение=УДАЛИТЬ(решение, вершина);

while (вершины $\пе $ 0) do

{вершина=ВЫБОР_ВЕРШ(вершины);

распределение=ВЕРОЯТНО(вершина, решение, управление);

узел=ВЫБОР_УЗЛА(вершина, распределение); решение=ДОБАВИТЬ(решение, вершина, узел);

}

лучш_решение=СРАВНЕНИЕ(решение, лучш_решение); итерация=итерация -1;

} end

Процедурой ИСХОД_ДАННЫЕ формируется массив граф, в ко­тором хранятся исходные данные, описывающие задачу. Массив управление, сформированный процедурой НАСТРОЙКА, хранит значения управляющих параметров: число итераций, число на- бросов, αn, αo, Δα, g— глубина памяти AA и т. п.

Процедурой ИСХОД_РАЗБИЕНИЕ(граф) формируется слу­чайным образом начальное состояние среды S, т. е. начальное разбиение гиперграфа — решение. Это решение на данный момент считается лучшим и заносится в массив лучш_решение.

C помощью процедуры НАЧ_СОСТОЯНИЕ все AA переводятся в состояние Cn. Состояние AA заносится в массив состо- ян_аа. Затем выполняется заданное число итераций. C помощью процедуры РАСЧЕТ(решение) рассчитываются параметры ρ+ и ρ-объектов адаптации, которые заносятся в массив парамет- ры_оа.

Процедурой РЕАКЦИЯ(параметры_оа) формируется массив отклик со значениями откликов среды для каждого автомата адаптации ai.

Процедурой ПЕРЕХОД(состоян_аа, отклик) автоматы адаптации переходят в новые состояния, которые фиксируются в массиве состоян_аа .

Затем процедурой ВЫХОД(граф, состоян_аа) формиру­ется массив вершины, в который включаются вершины, для которых реализуется альтернатива A2.

Процедурой УДАЛИТЬ(решение,вершина) полное решение задачи заменяется частичным путем удаления из Xvперераспре­деляемых вершин R.

После этого выполняется этап переназначения множества вершин R.

Процедурой ВЫБОР_ВЕРШ(вершины) выбирается случайным образом вершина. Для выбранной вершины процедурой ВЕРО- ЯТНО(вершина, решение, управление) формируется мас­сив распределения вероятности переназначения — распреде­ление.

Процедура ВЫБОР_УЗЛА(вершина, распределение) вы­бирает узел для назначения вершины.

Процедурой ДОБАВИТЬ(решение, вершина, узел) час­тичное решение уточняется путем размещения выбранной вер­шины в заданный узел. После назначения всех вершин множе­ства R массив решение вновь будет хранить полное решение задачи разбиения.

Если полученное решение имеет лучшую оценку F(S), то процедурой СРАВНЕНИЕ(решение, лучш_решение) оно зано­сится в массив лучш решение.

Отметим, что δ не может быть равной нулю (а следовательно, и αo) = o ибо возможна ситуация, когда для некоторой xi∈R при выборе узла окажется, что для всех доступных узлов значе­ния pv = o, pi = o. Наилучшие результаты адаптивный алгоритм показал при следующих значениях управляющих параметров: g (глубина памяти) = 2; T (число итераций) = 3oo; αn = ioo,oi; αo = o,oi; Δα = 1.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Механизмы адаптации при разбиении:

  1. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  2. Механизмы образования OA в кристаллах.
  3. Определение предела прочности при поперечном изгибе
  4. § 1. Права граждан при подготовке к рассмотрению дел об административных правонарушениях
  5. Определение секущих модулей и коэффициентов поперечных деформаций при отсутствии трещин
  6. Описание деформаций бетона при заданных секущих параметрах упругости
  7. Алгоритм формирования тремерной рабочей сцены при использовании нескольких оптико-электронных датчиков
  8. МЕТОД МАСШТАБИРОВАНИЯ ПРИ ОЦЕНКЕ ЖЕСТКОСТИ И ОСНОВНОЙ ЧАСТОТЫ КОЛЕБАНИЙ УПРУГИХ ПЛАСТИНОК
  9. Метод формирования тремерной рабочей сцены при использовании нескольких оптико-электронных датчиков
  10. Глава III. Применение национального законодательства при признании и приведении в исполнение отмененных арбитражных решений
  11. § 3. Обеспечение законности при выборе вида и размера административного наказания как способ защиты прав граждан
  12. АНДРЕЕВ АНДРЕЙ ИВАНОВИЧ. Обеспечение прав граждан при назначении административных наказаний. Диссертация на соискание ученой степени кандидата юридических наук. Москва - 2003, 2003
  13. Громова Алла Викторовна. СИНТАКСИС КАК СРЕДСТВО ПОНИМАНИЯ СОДЕРЖАТЕЛЬНОСТИ ТЕКСТА ПРИ ПЕРЕВОДЕ. Диссертация на соискание ученой степени кандидата филологических наук. Тверь 2019, 2019