<<
>>

Организация поисковых процедур на основе коллективной адаптации для решения задачи покрытия

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

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

Обычно в процессе поиска осуществляется переход к лучше­му решению. Введем на множестве матриц P отношение пред­почтения -0, будем считать, что pij находится в неудовлетворительном состоянии.

Этим самым задается стремление к минимизации общего числа элементов в покрывающем наборе.

Для реализации механизма коллективной адаптации каж­дому объекту (элементу pij) ставится в соответствие автомат адаптации (AA) aaijс двумя группами состояний: Ci = {c↑i| i = = 1,2,..., m}и C2 = {c2i| i = 1,2,...,n}, соответствующим двум альтернативам Aiи A2. На рис. 4.2, а, б приведены два варианта граф-схем переходов AA.

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

Здесь альтернатива Ai — не уменьшать pij∙; A2 — уменьшить pij∙. Число состояний в группе задается параметром m — глубина памяти (степень доверия). На каждом шаге работы адаптивной системы процесс коллективной адаптации осуществляется за че­тыре такта.

Ha первом такте (см. рис. 4.1) по рассчитанным параметрам среды (матрица D)оцениваются состояния объектов pij∙ в среде.

На втором такте вырабатывается сигнал «поощрения» (+), если pij∙ — в удовлетворительном состоянии, или сигнал «нака­зание» (—), если pij∙ — в неудовлетворительном состоянии.

На третьем такте под действием сигналов «поощрения» и «наказания» AA переходят в новые состояния.

На четвертом такте реализуются альтернативы, в соответ­ствии с состояниями автоматов адаптации.

При этом, если автомат адаптации ααij∙ находится в состоя­нии, соответствующем Ai, то управляющему сигналу sij∙ присва­ивается значение 0, sij = 0, а если в состоянии, соответствующем A2, то sij = 1. После реализации альтернатив осуществляются постпереходы в AA. Вырабатывается сигнал г, под действием которого AA, находящийся в состоянии С21, переходит в сц. Таким образом, в начале каждого шага адаптивной системы все AA находятся в группе Ci.

В простейшем случае m = 1 и граф-схема переходов AA имеет вид, представленный на рис. 4.2, б.

В нашей модели автоматы не получают никакой непосред­ственной информации о действиях других участников коллекти­ва и не общаются между собой. Однако выработку управляюще­го воздействия uijбудем осуществлять на основе обмена инфор­

Рис. 4.3. Структурная схема алгоритма выработки Ut

Далее формируется управляющее воздействие — матрица Uo. В ячейках матрицы Uo (см.

ниже) занесены значения uij, u2j∙ и uij = uj + u2j∙. Если uj =0, то результирующее значение равно uj. Вначале под действием управляющих сигналов sij∙ форми­руются значения uij, равные минимальной величине, которая приведет к уменьшению dijна единицу. Затем рассчитываются прогнозируемые значения dij∙ и djmax после формирования pij∙ с учетом uj. Запись -2(3) в ячейке матрицы Uo с координатами i = 1, j = 1 означает, что ujι = -2, a d∏ = 3. Если в конце запи­сан знак •, например — 1(3)∙, то это значит, что dij∙ = djmax= 3, a kij = 0. Вверху над каждым столбцом матрицы Uo (и последу­ющих матриц Ui)в скобках записано число, значение которого равно начальному прогнозируемому значению djmaxс учетом uj. Матрица Uo имеет вид

4 В. М. Курейчик, Б. К. Лебедев, О. Б. Лебедев

В матрице D1 только два элемента: d22 и d25 имеют нуле­вое значение, следовательно, в удовлетворительном состоянии находятся p22и p25и для них вырабатывается сигнал «поощре­ние»; для остальных — сигнал «наказание». Порядок расчета U1 аналогичен процессу, рассмотренному выше. Матрица U1 имеет вид

Ниже представлены результаты вычислений на 3-5 шагах работы алгоритма. В итоге будет получен покрывающий набор, составленный из 12 ячеек, включающий 70 элементов.

На шаге 3 получим

На шаге 6 получим

На рисунках 4.4 и 4.5 представлены графики изменения по шагам tчисла ячеек Nzи числа элементов N3в покрывающих наборах.

Рис. 4.4. График изменения по шагам числа ячеек в покрываю­щих наборах

Рис. 4.5. График изменения по ша­гам числа элементов в покрываю­щих наборах

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

В заключение отметим, что адаптивный поисковый алгоритм покрытия может быть использован для решения любой задачи линейного целочисленного программирования, постановка ко­торой сведена к рассмотренной выше постановке (4.1) с уче­

том того, что показатель cj∙ равен сумме показателей aij, т. е.

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

Еще по теме Организация поисковых процедур на основе коллективной адаптации для решения задачи покрытия:

  1. Аналитические методы решения двумерных задач строительной механики
  2. 4.1. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ
  3. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ПО РАСЧЕТУ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  4. ПРОБЛЕМЫ РАЗВИТИЯ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК
  5. Приближенные методы решения задач технической теории пластинок
  6. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  7. Графическое представление решений для пластинок в виде треугольников
  8. § 2. Надлежащие основания для отмены арбитражного решения. Применение Европейской Конвенции 1961 года
  9. § 2. Последствия исключения отмены арбитражного решения из перечня оснований для отказа в его признании и приведении в исполнение
  10. 1. Коллективные субъекты административного права: понятие и виды
  11. Шляхов Станислав Владимирович. РАЗВИТИЕ И ПРИМЕНЕНИЕ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ К РЕШЕНИЮ НЕКОТОРЫХ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК C КРИВОЛИНЕЙНЫМИ УЧАСТКАМИ КОНТУРА. Диссертация на соискание учёной степени кандидата технических наук. Орёл - 2019, 2019
  12. Карбовский Владислав Александрович. ТЕХНОЛОГИИ ЭКСТРЕННЫХ ВЫЧИСЛЕНИЙ ДЛЯ ИНДИВИДУАЛЬНОЙ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ В КРИТИЧЕСКИХ СИТУАЦИЯХ. ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук. Санкт-Петербург - 2014, 2014
  13. Тема 6. Коллективные субъектыадминистративного права
  14. Глава II. Зависимость между признанием и приведением в исполнение отмененного арбитражного решения и признанием судебного акта, отменяющего такое решение, в зарубежной судебной практике и доктрине
  15. 2.16.1 Тестирование функции (2.48) в задачах поперечного изгиба пластинок с жестко защемленным контуром
  16. 1. Правовые основы системы образования
  17. 3. Основы административно-правового статуса граждан
  18. Основные нерешенные проблемы в развитии МИКФ Цели и задачи диссертационной работы
  19. Основные задачи и интегральные физические характеристики, рассматриваемые в работе
  20. Тестирование функции (2.48) в задачах поперечного изгиба пластинок с шарнирно опертым контуром