<<
>>

Поисковые процедуры, основанные на объединении принципов эволюционной и альтернативной адаптации

Методы поисковой адаптации на основе механизмов генетики являются эффективным средством решения оптимизационных задач автоматизированного проектирования СБИС [2.13, 2.19].

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

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

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

При разработке генетических алгоритмов стремятся к тому, чтобы хромосомы были гомологичными, что исключает возник­новение нереальных решений и упрощает выполнение генети­ческих операторов, модифицирующих хромосомы. Достоинством генетических алгоритмов является линейная оценка временной и пространственной сложностей генетических процедур, выполня­емых на каждой итерации. Это дает возможность решать задачи большой размерности, что особенно важно при проектировании СБИС.

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

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

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

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

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

Адаптация на основе самообучения и самоорганизации доми­нирует в процессе существования и развития конкретного жи­вого организма. Объектом адаптации является конкретный ин­

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

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

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

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

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

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

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

После отработки генетического алгоритма в популяции, полу­ченной на последней генерации, отбирается несколько решений

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

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

Массив задача включает все исходные данные. В начале процедурой ФОРМ(задача) формируется начальная популяция нач_попул. На каждой генерации (число генераций равно T) сначала процедурой Генетика(нач_попул) реализуются гене­тические операторы, синтезирующие новые решения. В результа­те образуется расширенная популяция тек_попул. Процедурой АД_СЕЛЕКТ в популяции тек_попул отбирается множество ре­шений нач_адапт для дальнейшей обработки адаптивным обу­чающимся алгоритмом. Отметим, что в множество нач_адапт не включаются решения, полученные алгоритмом адаптивно­го обучения и не подвергавшиеся дальнейшим изменениям ге­нетическими операторами. Далее каждое решение множества нач_адапт с помощью процедуры АДАПТ(нач_адапт) подвер­гается обработке алгоритмом адаптивного обучения и получается множество решений адапт. Полученные решения процедурой ОБЪЕДИНИТЬ(тек_попул,адапт) включаются в популяцию тек_попул. В заключение процедурой СЕЛЕКТ(тек_попул) на базе популяции тек_попул осуществляется отбор и форми­рование популяции нач_попул.

Дополнительным источником усовершенствования является правильная настройка параметров управления.

Algoritm ПОИСКОВАЯ АДАПТАЦИЯ

begin

задача= ИСХОДНЫЕ ДАННЫЕ; нач_попул= ФОРМ (задача); while k>T do

{

тек_попул = ГЕНЕТИКА (нач_попул); ад_попул = А_СЕЛЕКЦИЯ (тек_попул); ад_попул = АДАПТАЦИЯ (ад_попул); тек_попул = ОБЪЕДИНИТЬ (тек_попул,ад_попул); нач_попул = СЕЛЕКЦИЯ (тек_попул);

к=к-1;

};

end

Рис. 2.6. Псевдокод комбинированной адаптивной поисковой процедуры

Использование рассмотренных средств и методов поисковой адаптации позволяет синтезировать новые эффективные алгорит­мы автоматизированного проектирования СБИС [2.20].

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

Еще по теме Поисковые процедуры, основанные на объединении принципов эволюционной и альтернативной адаптации:

  1. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  2. 2. Принципы административного процесса
  3. 3. Принципы административного права
  4. 1. Понятие и принципы государственной службы
  5. Конститутивные и регулятивные принципы персональных финансов[17]
  6. § 1. Генезис принципа зависимости в теории и международной практике
  7. 32. Приватизация жилых помещений: понятие, правовое регулирование, принципы, условия, оформление.
  8. ГЛАВА 4. РАЗРАБОТКА АЛГОРИТМА ОПТИМИЗАЦИИ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  9. ОПТИМИЗАЦИЯ ЖЕЛЕЗОБЕТОННЫХ КОНСТРУКЦИЙ
  10. Библиографический список
  11. ЗАКЛЮЧЕНИЕ
  12. 1. Субъекты административного права
  13. 1.2.1 Вариационные методы
  14. Введение