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

Основу элементной базы современных радиоэлектронных устройств (РЭА) составляют сверхбольшие интегральные схемы (СБИС), которые выполняют определенную функцию преобразования сигнала и (или) накапливания информации и имеют сверхвысокую плотность упаковки электрически соединенных элементов. С момента появления интегральных схем резко изменились их основные характеристики — быстродействие, размеры, стоимость. Современные СБИС содержат порядка 10−15 миллионов на кристалле размером 25*25 мм с минимальным топологическим размером 0,18 м.

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

В связи с возросшими технологическими возможностями изготовления в настоящее время в СБИС произошло увеличение области межсоединений. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов (транзисторов). В современной СБИС, содержащей 10 миллионов транзисторов, использующей 4 слоя металлизации, около 40% площади отводится под межсоединения. Возрастает число переходов из слоя в слой, что вырастает в отдельную проблему, и тенденция эта растет. В связи с этим особо актуальна разработка новых эффективных методов решения задач конструкторского проектирования: покрытия, разбиения, размещения, трассировки и т. д. 1].

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

Основные задачи синтеза и формирования топологии СБИС — покрытие, разбиение, размещение, глобальная трассировка, перераспределение соединений между выводами, распределение соединений между слоями и т. д. являются КР-полными. Из теории алгоритмов известно, что для задач класса ЫР в природе не существует алгоритма, кроме алгоритма «полного перебора «, который бы гарантировал нахождение глобального оптимума. Понятно, что для задач большой размерности этот алгоритм неприемлем. Поэтому очень большой класс разработанных к настоящему времени алгоритмов проектирования СБИС основан на различных эвристиках, обеспечивающих получение решений в полиномиальное время. Основным недостатком этих алгоритмов (последовательных и итерационных) является невысокое качество результатов из-за попадания в «локальные ямы», малая пригодность для задач большой размерности, плохая приспособленность для реализации на современных технических средствах, отсутствие альтернатив. Одним из возможных методов решений этой проблемы является использование методов случайного направленного поиска, основанного на моделирование естественных процессов. К таким относятся бурно развивающиеся в последнее время методы поисковой адаптации на основе механизмов самоорганизации, генетического поиска и эволюционного развития. Слово адаптация, широко используемое в современной научно-технической литературе, заимствовано из биологии, где оно означает приспособление живых организмов к изменяющимся окружающим условиям. Адаптация многолика и разнообразна. Известны такие проявления адаптации, как эволюция, привыкание, обучение и самообучение, организация и самоорганизация и т. д. [2,3].

Изучение законов биологической эволюции показало, что в их основе лежит закон взаимной адаптации. Существование и развитие живой системы (в том числе человека) суть процесс взаимной опережающей многоуровневой адаптации компонентов системы между собой и системы с внешней средой [4]. Наблюдения в области адаптации живых организмов привели к идее «наделить» указанным свойством технические системы. Это достигается введением в конструкцию технической системы возможности приспособления к новым ситуациям, заранее не предвиденным с тем, чтобы в процессе функционирования эта система изменялась и улучшала свои характеристики.

Значительный вклад в разработку технических устройств и моделей, имитирующих процессы подобной адаптации, внесли M.JI. Цетлин, JI.A. Растри-гин, A.A. Красовский, Д. А. Поспелов, Г. С. Поспелов, В. Ф. Венда, A.A. Самарский, Я. З. Цыпкин, П. В. Куропаткин, В. Г. Срагович, Б. И. Кузьмин, В. П. Сигорский и др.

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

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

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

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

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

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

Основным объектом адаптации является КПС и, следовательно, и математическое обеспечение, на основе которого разработаны прикладные программы, входящие в состав КПС.

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

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

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

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

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

Значительным шагом в развитии технических устройств, для имитации адаптации, был предложенный М. Л. Цетлиным подход, основанный на использовании вероятностных обучающихся автоматов [11].

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

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

Основываясь на этой идее, М. Л. Цетлин поместил в среду, характеризующуюся случайной реакцией, вероятностный автомат адаптации (АА) для реализации функции управляющего устройства. Адаптация автомата производится путем самообучения в процессе его функционирования.

На каждом такте работы адаптивной системы в соответствии со значениями, А выхода автомата адаптации АА формируется управляющее воздействие и, приводящее к изменению состояния среды 8 и показателя качества Р (8). Идеи М. Л. Цетлина в основу теории построения алгоритмов альтернативной поисковой адаптации.

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

— генетические алгоритмы работают на основе популяции, т. е. на множестве индивидуальностей;

— оперирование производится не с решениями, а с их кодами. Каждому решению соответствует одна или несколько хромосом, которые представляют собой закодированный генетический материал. Хромосомы состоят из генов. Каждый ген имеет свой локус или позицию в хромосоме. Гены могут иметь различные значения: число, строка, сектор, массив и т. д. Решение получается на основе декодирования хромосом.

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

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

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

Цель и задачи исследования

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

— проведение сравнительного анализа методов оптимизации и выработка общего подхода и структуры к организации оптимизационных процедур на основе методов поисковой адаптации и интеллектуализации процедур поиска;

— разработка новых критериев, моделей и подходов к решению основных задач синтеза топологии СБИС;

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

— разработка представлений исходных формулировок задач конструкторского проектирования СБИС в виде адаптивных процессов на основе самообучения и самоорганизации, моделируемых вероятностными автоматами адаптации (АА), и механизмов их функционирования, что предполагает: a) формирование моделей среды и объекта адаптации, локальных целей объектов адаптации и глобальной цели коллективаb) разработку структуры обучающегося АА и механизмов переходов в ААc) разработка общей структуры процесса адаптивного поиска;

— разработка представлений исходных формулировок задач конструкторского проектирования СБИС в виде адаптивных поисковых процессов на основе генетической эволюции, что предполагает: а) разработку и модификацию механизмов генетического поискаb) разработку, модификацию и адаптацию к решаемой задаче генетических операторовc) формирование структур и принципов кодирования хромосом с учетом специфики решаемых задач, оптимизирующих процесс генетического поиска;

— разработка и исследование алгоритмов топологического синтеза на базе общего подхода к построению адаптивных поисковых процедур, опирающихся на сочетание принципов адаптации на основе самообучения, самоорганизации и генетического поиска;

— разработка программных средств на основе проведенных исследований для решения задач топологического синтеза.

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

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

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

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

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

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

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

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

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

Достоверность результатов диссертационной работы.

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

Основные научные результаты, выносимые на защиту.

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

2. Модели, методы и алгоритмы альтернативной коллективной адаптации для решения задач покрытия, разбиения, размещения, глобальной трассировки, перекоммутации соединений, разнесения соединений по слоям.

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

4. Модели, методы и алгоритмы решения задач покрытия, разбиения, размещения, глобальной трассировки, канальной трассировки, трассировки в трассировки в коммутационном блоке, перекоммутации соединений, разнесения соединений по слоям на основе генетической адаптации.

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

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

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

8. Программные средства, реализующие предложенные методы и алгоритмы.

Практическая ценность работы состоит в том, что основные теоретические положения доведены до конкретных методик и алгоритмов. Предложенные методы поисковой адаптации, опирающиеся на сочетание принципов адаптации на основе самообучения, самоорганизации, генетического и интеллектуального поиска, являются мощным средством выхода их «локальных ям», приводящим к синтезу решений, близких к оптимальным. 19 разработанных алгоритмов синтеза топологии методами адаптивного и интеллектуального поиска реализованы в виде программ на языке Borland С++ для Windows. Созданный комплекс программ позволяет при решении задач синтеза топологии СБИС осуществлять выбор метода решения: только методами генетического поискаметодами коллективной, альтернативной адаптации, моделируемой вероятностными обучающимися автоматами адаптациилибо их совместное использование. Предложенные методы позволяют достигнуть улучшенных показателей объектов проектирования. Кроме того, предложенные алгоритмы и программы носят достаточно универсальный характер и могут быть использованы для решения широкого круга задач.

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

В рамках научно-технических программ Минобразования РФ «Научные исследования ВШ по приоритетным направлениям науки и техники»: «Разработка теории и методов построения интегрированных САПР СБИС с элементами искусственного интеллекта» (№ ГР 01.950 004 188) — «Разработка интеллектуальных систем проектирования на основе эволюционной адаптации» (№ ГР. 01.960 004 346).

В рамках государственной научно-технической программы «Университеты России» (1995;1996г.): «Разработка методов и моделей генетического поиска в интеллектуальных САПР», «Исследование генетических методов оптимизации» .

Поддержана грантами РФФИ: «Генетические алгоритмы в интеллектуальных САПР» (шифр 99−01−50) — «Символьные информационные технологии проектирования на основе эволюционной адаптации» (шифр 00−01−125) — «Эволюционное проектирование с адаптацией» (шифр 01−01−44). Поддержана грантом Минобразования РФ на проведение фундаментальных исследований в области технических наук (Исследование и разработка методов трассировки СБИС на основе эволюционной адаптации). В работе, выполняемой по ЕЗН Минобразования РФ (Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений).

В работе «Учебно-методический комплекс, Применение экспертных систем в инженерной практике», выполненой в рамках научно-технической программы «Компьютеризация образования^ 995 г.)» ;

Теоретические и практические результаты, полученные в диссертационной работе, использованы в Ростовском филиале Всесоюзного научно исследовательского института автоматизированных систем в системах расчета параметров внешней среды и выработке оптимального управляющего воздействия. В НКБ «Миус» и НИИ МВС применение предложенных в диссертационной работе алгоритмов и разработанных программ позволило уменьшить время проектирования элементов вычислительных систем.

За разработку САПР двухслойных и многослойных схем автор награжден серебренной и бронзовой медалями ВДНХ.

Научные результаты и разработанное программное обеспечение диссертационной работы внедрены в учебный процесс по курсам «Искусственный интеллект», «Прикладные интеллектуальные системы», «Проблемы разработки и перспективы интеллектуальных САПР», «Методы оптимизации», «Исследование операций», обобщены в изданных учебных пособиях. Акты внедрения и использования научных результатов прилагаются.

Апробация работы. Основные положения и результаты докладывались и обсуждались на: Всероссийской НТК с международным участием «Интеллектуальные САПР», (Геленджик, 1992;2001гг) — Международной НТК «Новые информационные технологии в науке образования и бизнесе»", (Крым, Гурзуф, 1991;1995 г. г.) — Всероссийской конференции «Интеллектуальные информационные системы» (Воронеж, 1999 г.) — 1 Международной НТК «Проблемы реального управления, экономики, права и инновационных процессов в образовании» (Таганрог, 1999 г.) — Международной конференции и школе молодых ученых и специалистов «САПР-92, новые информационные технологии в науке, образовании и бизнесе» (Воронеж, 1992 г.) — Всесоюзной конференции «Создание интеллектуальных САПР БИС и электронных средств» (Москва, 1990 г.) — 3 International Conference «Interactive System: The problems of Human Computer Interaction» (Ulyanovsk, 1999 г.) — Всесоюзном совещании «Методы и программы решения оптимизационных задач на графах и сетях» (Новосибирск, 1980, 1983, 1989 г. г.) — XXX Всесоюзной школе-семинаре им. М. А. Гаврилова «Развитие теории дискретных систем и проблемы логического проектирования» (Кишинев, 1988 г.) — Всесоюзной конференции «Автоматизация технического проектирования цифровой аппаратуры» (Каунас, 1981, 1984, 1985, 1987, 1988, 1989 г. г.) — Межреспубликанском семинаре «Интеллектуальные САПР СБИС» (Ереван, 1988 г.) — Всесоюзной конференции «Проблемы адаптации алгоритмического и информационного обеспечения САПР» (Киев, 1987 г.) — НТК «Автоматизация проектирования РЭА и ЭВА» (Пенза, 1983;1988 г. г.) — Всесоюзной конференции «Автоматизация поискового конструирования и подготовки инженерных кадров» (Иваново, 1983 г.) — Всесоюзной НТК «Теория и практика конструирования и обеспечения надежности и качества электроаппаратуры и приборов» (Москва, 1984 г.) — Всесоюзной конференции «Микропроцессоры 85. Методы и микроэлектронные устройства цифрового преобразования и обработки информации» (Москва, 1985 г.) — Всесоюзной конференции «Проблемы создания и развития интегрированных систем в проектировании и производстве» (Москва, 1987 г.) — Международном НТС «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2001 г.) — Международном конгрессе «Искусственный интеллект в XXI веке» (Дивноморское, 2001 г.);

Научно-технических конференциях профессорско-преподавательского состава ТРТУ (1980;2001 г. г.) и других конференциях.

По теме диссертации опубликовано 68 печатных работ, среди которых 4 монографии и 3 учебных пособия.

Структура и объем диссертационной работы. Диссертация состоит из введения, 8 глав, заключения, списка использованной литературы и приложения. Объем диссертации 376 страниц, включая список литературы из 172 наименований. В приложении вынесены акты об использовании и внедрении результатов диссертационной работы.

Выводы.

1. Приведена проблемная формулировка задачи разнесения соединений по слоям и описана методика формирования пространства решений и представления решения в виде бинарного вектора, что упрощает процесс поиска.

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

3. Для ускорения достижения объектом адаптации состояния с минимальным числом межслойных переходов разработан вероятностный механизм формирования откликов среды.

4. Для усиления способности выхода из локальных оптимумов при работе адаптивной системы автомат адаптации модернизирован введением вероятностных механизмов перехода из одной группы состояний в другую.

5. Исходя из эвристических соображений, множество объектов в зависимости от мощности разбито на классы. Для каждого класса вводятся индивидуальные значения параметра — глубина памяти. Это позволяет избежать резких изменений и более тщательно просматривать решения в некоторой окрестности.

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

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

8. Экспериментальные исследования процедур поисковой адаптации при их совместной работе показал, что вероятность получения оптимальных решений при одном прогоне программы составила 0,96, а среднее отклонение решений от глобального оптимума менее 1%.

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

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

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

11. Разработанные в диссертации теоретические положения, методы, алгоритмы и программные средства позволяют решать задачи по созданию эффективных средств синтеза топологии СБИС с учетом современных тенденций, обладающих улучшенными характеристиками. Большинство разработанных алгоритмов имеют линейную оценку ВСА и ПСА при фиксированных значениях управляющих параметров. В среднем вероятность получения глобального оптимума составила 0.9−0.96. Эксплуатация и исследования разработанных средств подтвердили их высокую эффективность. В сравнении с известными алгоритмами на стандартных бенчмарках полученные результаты были лучше на 5−10% при меньших затратах времени.

Заключение

.

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

2. На основе механизмов генетического поиска разработаны адаптивные поисковые алгоритмы синтеза топологии СБИС — покрытия, разбиения, размещения, глобальной трассировки, канальной трассировки, трассировки в коммутационном блоке, перекоммутации соединений, разнесения соединений по слоям.

3. На основе механизмов альтернативной коллективной адаптации, моделируемых вероятностными обучающимися автоматами адаптации, разработаны алгоритмы синтеза топологии СБИС — покрытия, разбиения, размещения, глобальной трассировки, перекоммутации соединений, разнесения соединений по слоям.

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

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

6. Разработана и теоретически обоснована новая технология генетического поиска на базе виртуального набора популяций на одном наборе генотипов для распараллеливания генетического поиска без увеличения сложности алгоритма.

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