<<
>>

Введение

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

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

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

Основные задачи синтеза и формирования топологии СБИС — покрытие, разбиение, размещение, глобальная трассировка, перераспределение соединений между выводами, распределение соединений между слоями и т. д. — являются NP-полными [1]. Из теории алгоритмов известно, что для задач класса NPв природе не существует алгоритма, кроме алгоритма полного перебора, который гарантировал бы нахождение глобального оптимума. Понятно, что для задач большой размерности этот алгоритм неприемлем. Поэтому большой класс разработанных к настоящему времени алгоритмов проектирования СБИС основан на различных эвристиках, обеспечивающих получение решений в полиномиальное время. Основным недостатком этих алгоритмов (последовательных

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

Слово адаптация, широко используемое в современной на­учно-технической литературе, заимствовано из биологии, где оно означает приспособление живых организмов к изменяющимся окружающим условиям. Адаптация многолика и разнообразна. Известны такие проявления адаптации, как эволюция, привыка­ние, обучение и самообучение, организация и самоорганизация и т. д. [4, 5].

Изучение законов биологической эволюции показало, что в их основе лежит закон взаимной адаптации.

Существование и развитие живой системы (в том числе че­ловека) — суть процесс взаимной опережающей многоуровневой адаптации компонентов системы между собой и системы с внеш­ней средой [6].

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

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

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

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

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

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

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

Значительный вклад в разработку технических устройств и моделей, имитирующих процессы адаптации, внесли: В. И. Варшавский, В. Ф. Венда, А. А. Красовский, Д. А. Поспелов, Л. А. Растригин, В. Г. Редько, В. П. Сигорский, В. Г. Срагович, В. Л. Стефанюк, Г.Хакен, М.Л.Цетлин, Я. 3. Цыпкин, и другие отечественные и зарубежные ученые [4-17].

В настоящее время в технических системах существуют два подхода к организации адаптационных процессов [11].

При первом подходе адаптивные процессы поддерживают объект в состоянии, определяемом целью и, в этом смысле, адаптация является управлением.

При втором подходе адаптивные процессы связаны с макси­мизацией эффективности функционирования некоторого объек­та. Здесь адаптация рассматривается как оптимизация.

В адаптивных системах управления информация об объекте и внешних воздействиях собирается в ходе эксплуатации, сразу же обрабатывается и используется для выработки управляю­щих воздействий. Это позволяет повысить качество управления в условиях неопределенности и нестабильности объекта и среды функционирования. Методы адаптивного управления в сложных системах на сегодняшний день уже достаточно развиты [12, 13].

При втором подходе решение задачи адаптации сводится к определению такого управляющего воздействия, при котором достигается максимальная эффективность работы объекта. При этом одновременно выполняются все жесткие требования, предъ­являемые к этому объекту [13-15]. Такая задача является зада­чей оптимизации (максимизации эффективности) в обстановке ограничений.

Обычно адаптация в САПР [16] рассматривается как адап­тация в сложной системе, состоящей из 4-х основных компо­нентов: комплекса программных средств, комплекса технических средств, объекта проектирования и пользователя.

Основным объектом адаптации является комплекс программ­ных средств, а, следовательно, и математическое обеспечение, на

основе которого разработаны прикладные программы, входящие в его состав.

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

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

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

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

В качестве модели обучающейся системы Цетлин М.Л. [17] предложил вероятностный обучающийся автомат, названный ав­томатом адаптации. Основы поведения обучающихся автома­тов, адаптирующихся к среде, можно представить следующим образом. Автомат адаптации способен воспринимать два вход­ных сигнала: поощрение (удовлетворительное состояние объекта в среде) и наказание (неудовлетворительное состояние объекта в среде). Состояние автомата адаптации соответствует некото­рой альтернативе проектного решения. В процессе адаптации на основе откликов внешней среды автомат переходит в состоя­ние, соответствующее лучшей альтернативе проектного решения. Обобщением идеи Цетлина М. Л. о целесообразном поведении стохастических автоматов явились работы Варшавского В. И., посвященные коллективному поведению автоматов адаптации.

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

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

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

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

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

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

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

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

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

Каждая глава книги завершается выводами.

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

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

А. Франс

Список литературы

1. Naveed Sherwani. Algorithms for VLSI physical design automation. — Boston /Dordrecht/ London: Kluwer academic publishers, 1995.

2. Лебедев Б. К. Адаптация в САПР. — Таганрог: Изд-во ТРТУ, 1999.

3. Лебедев Б. К. Методы поисковой адаптации в задачах автомати­зированного проектирования СБИС. — Таганрог: Изд-во ТРТУ, 2000.

4. Цыпкин Я. 3.Адаптация и обучение в автоматических системах. — M.: Наука, 1975.

5. Поспелов Д. А. Фантазия или наука: на пути к искусственному интеллекту. — М.: Наука, 1982.

6. Венда В. Ф. Системы гибридного интеллекта. Эволюция, психоло­гия, информатика. — M.: Машиностроение, 1990.

7. Поспелов Д. А. Ситуационное управление: теория и практика. — М.: Наука, 1986.

8. Редько В. Г. Эволюция, нейронные сети, интеллект. — M.: Ко- мКнига, 2005.

9. Варшавский В. И. Коллективное поведение автоматов. — M.: Ha- ука, 1973.

10. Хакен Г. Информация и самоорганизация. Макроскопический под­ход к сложным системам. — М.: Наука, 1991.

11. Растригин Л. А. Адаптивные компьютерные системы. — М.: Зна­ние, 1987. 64 с.

12. Срагович В. Г. Адаптивное управление. — М.: Наука, 1981.

13. Справочник по теории автоматического управления / Под ред. А. А. Красовкого. — М.: Наука, 1987.

14. Куропаткин П.В. Оптимальные и адаптивные системы. — M.: Высшая школа, 1980.

15. Растригин Л. А. Адаптация сложных систем. — Рига: Зинатне, 1981.

16. Сигорский В. Г. Проблемная адаптация в системах автоматизиро­ванного проектирования // Известия высших учебных заведений: Радиоэлектроника. 1988. Т.31, №6.

17. Цетлин М.Л. Исследования по теории автоматов и моделирова­нию биологических систем. — М.: Наука, 1969.

1.

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

Еще по теме Введение:

  1. ВВЕДЕНИЕ
  2. Введение
  3. ВВЕДЕНИЕ
  4. ВВЕДЕНИЕ
  5. ВВЕДЕНИЕ
  6. ВВЕДЕНИЕ
  7. Введение
  8. ВВЕДЕНИЕ
  9. Введение
  10. ВВЕДЕНИЕ
  11. ВВЕДЕНИЕ