<<
>>

Эволюционные методы оптимизации

В последнее время дальнейшим совершенствованием итера­ционных алгоритмов была разработка поисковых методов, ос­нованных на моделировании естественных процессов, протека­ющих в живой и неживой природе. К ним относятся метод моделирования отжига [2.10], методы генетического поиска (эво­люционная адаптация) [2.11, 2.12, 2.13], методы альтернатив­ной адаптации [2.14, 2.15, 2.16]. Являясь по своей сути ите­рационными, алгоритмы на основе моделирования отличаются от обычных итерационных процедур слепого поиска.

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

1. Моделирование отжига. В 1953 г. Метрополис предло­жил вычислительную процедуру, воспроизводящую механизм от­жига металлов, для моделирования состояния равновесия слож­ных систем при заданной конечной «температуре» [2.10]. Идея переноса механизма отжига металлов на решение оптимизацион­ной задачи состоит в том, что процесс оптимизации связывают с некоторой температурой. На каждом шаге поиска случайным образом осуществляется малое изменение состояния объекта и вычисляется изменение ΔE энергии системы. Новая конфи­гурация системы принимается с вероятностью 1, если ΔE ≤ 0,

и с вероятностью, равной exp(-ΔE∕kt),если ΔE >0. Эта проце­дура переносится на решение оптимизационных задач. При этом состояния физической системы заменяются изменением критерия качества, а значение ktзаменяется обобщенным понятием «тем­пература» T, которая может рассматриваться как управляющий параметр оптимизационной процедуры.

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

Не вдаваясь в предысторию и теоретические выкладки метода суть моделирования отжига можно описать следующим образом.

Задаются параметры, названия которых отражают историю возникновения метода. Это Th, Tk— начальная и конечная тем­пература, Δt — интервал изменения температуры. Температура T меняется от Tkдо Tkс интервалом Δt. Начальные значения Th— высокое, Tk— низкое, обычно Tk = 0. При каждом значении T выполняется заданное множество итераций. На каждой итерации выполняются действия, представлденные на рис. 2.4. С помощью некоторого оператора D осуществляется пробное изменение со­стояния (решения).

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

где k — константа.

Выбирается случайное число ζиз равномерного распределе­ния от нуля до единицы.

Если ζ ≤ P , то изменение сохраняется , если ζ>Р, то осуществляется возврат к предыдущему состоя­нию.

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

Рис. 2.4. Структура метода моделирования отжига

Недостатком метода моделирования отжига является то, что он не хранит информацию о разных действиях, выполненных на предыдущих итерациях. Особенностью метода является то, что качество получаемого решения во многом зависит от начального. Чем лучше начальное решение, тем выше шанс получения нового решения с лучшим качеством [2.10].

2. Генетические алгоритмы. Генетические алгоритмы (ГА) оперируют с популяцией решений. C одной стороны это позво­ляет быстрее находить лучшие решения, но с другой стороны требуется больше памяти для хранения информации о популяции решений. Тем не менее, последние исследования, связанные с ис­пользованием генетических методов оптимизации в различных областях показали их высокую эффективность.

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

Идеи использования методов естественной генетики появи­лись в результате работ Холланда [2.17]. Генетический алгоритм есть адаптивный поисковый метод, который основан на селекции лучших индивидуальностей в популяции, подобно эволюционной теории Дарвина.

Отличительной особенностью генетических алгоритмов яв­ляется следующее. Оперирование производится не с решения­ми, а с их кодами. Каждому решению соответствует одна или несколько хромосом, которые представляют собой закодирован­ный генетический материал. Хромосомы состоят из генов. Каж­дый ген имеет свой локус или позицию в хромосоме. Гены могут иметь различные значения: число, строка, сектор, массив и т. д. Генетические алгоритмы работают на основе популяции, т. е. на множестве индивидуальностей. Решение получается на основе декодирования хромосом. Особенности строения хромосом и ге­нов, а также их значения, образуют генотип индивидуальности. Построенный на основе декодирования хромосом (индивидуаль­ности) объект образует фенотип [2.17].

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

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

Рис. 2.5. Структура генетического алгоритма

отбора или методу выживания сильнейшего, основанного на эво­люционной теории Дарвина.

Селекция — это процесс, посредством которого хромосомы, имеющие более высокое функциональное значение, получают большую возможность для репродукции, чем «слабые» хромосо­мы. Элементы, выбранные для селекции, обмениваются генети­ческим материалом, создавая потомков. Существует несколько основных видов селекции [2.12, 2.13].

Основным итогом анализа генетического алгоритма стал вы­бор триады генетических операторов (ГО): кроссинговер - му­тация - инверсия. Воздействуя с некоторой вероятностью на генотипы родительских особей, каждый из них, с одной стороны,

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

В эволюционном моделировании под кроссинговером пони­мают оператор, который формирует хромосому потомка, форми­руя ее из фрагментов родительских хромосом [2.17]. Основная функция оператора кроссинговера (ОК) — создавать хромосомы потомков на основе различного скрещивания родителей.

Мутация — генетическое изменение, приводящее к каче­ственно новому проявлению основных свойств генетического ма­териала: дискретности, непрерывности и линейности. Таким об­разом, мутации представляют собой изменения генов, хромосом.

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

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

К недостаткам методов генетического поиска следует отнести большой объем вычислений на каждой итерации

3. Методы альтернативной адаптации. В задачах САПР особый интерес представляет поисковая адаптация, основан­ная на использовании обучающихся автоматов, моделирующих поведение объектов проектирования (ОП) в заданной среде. М. Л. Цетлин [2.18] поместил объекты проектирования в среду, характеризующуюся вероятностной реакцией. Далее он провел анализ связи структуры среды и ее поведения. Затем была рассмотрена адаптация объектов проектирования в такой среде с позиции теории игр.

В качестве модели объектов проектирования используется автомат адаптации (АА), представляющий собой обучающуюся систему. В процессе адаптации в случайной среде в ответ на состояние автомата адаптации в среде с вероятностью piвыда­ется сигнал «поощрения», а с вероятностью qi= 1 — piсигнал «наказания». Под действием этих сигналов автомат адаптации в результате обучения переходит в состояние, соответствующее лучшей альтернативе (стратегии).

Трудности использования такого подхода связаны в первую очередь с проблемой представления исходной формулировки за­дачи в виде адаптивной системы [2.14, 2.16, 2.18].

Ниже приведены материалы, в которых подробно рассматри­ваются основные проблемы, связанные с разработкой и исполь­зованием адаптивных поисковых алгоритмов.

2.3.

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

Еще по теме Эволюционные методы оптимизации:

  1. ГЛАВА 1. СОСТОЯНИЕ ВОПРОСА ПО РАСЧЕТАМ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ И МЕТОДАМ ОПТИМИЗАЦИИ ЖЕЛЕЗОБЕТОННЫХ КОНСТРУКЦИЙ
  2. ГЛАВА 4. РАЗРАБОТКА АЛГОРИТМА ОПТИМИЗАЦИИ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  3. ОПТИМИЗАЦИЯ ЖЕЛЕЗОБЕТОННЫХ КОНСТРУКЦИЙ
  4. ОСОБЕННОСТИ ОПТИМИЗАЦИИ ПЛИТ С УЧЕТОМ ЗАПРОЕКТНЫХ ВОЗДЕЙСТВИЙ
  5. 4.1. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ
  6. 4.2. ПРИМЕРЫ ОПТИМИЗАЦИИ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  7. Анализ методов и устройств трехмерного технического зрения и методов калибровки
  8. Муймаров Кирилл Викторович. ОПТИМИЗАЦИЯ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ С ВЫБОРОМ СТРУКТУР АРМИРОВАНИЯ. Диссертация на соискание ученой степени кандидата технических наук. Брянск - 2019, 2019
  9. 3.2 Метод дифференциальной коноскопии.
  10. 1.2.1 Вариационные методы
  11. Геометрические методы
  12. 3. Понятие и виды методов государственно-управленческой деятельности
  13. Изопериметрический метод
  14. Развитие метода интерполяции по коэффициенту формы
  15. Методы вычисления параметров и сопоставления характерных точек объектов
  16. ПРОБЛЕМЫ РАЗВИТИЯ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК
  17. ИССЛЕДОВАНИЕ МЕТОДОВ И УСТРОЙСТВ ВЫЧИСЛЕНИЯ ТРЕХМЕРНЫХ КООРДИНАТ ОБЪЕКТОВ РАБОЧЕЙ СЦЕНЫ
  18. Расчет железобетонных конструкций методом конечных элементов
  19. Перевод как герменевтический метод понимания текста
  20. ФОРМЫ И МЕТОДЫ ГОСУДАРСТВЕННОГО УПРАВЛЕНИЯ