Разработка и исследование биоинспирированных алгоритмов разбиения схем при проектировании СБИС тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Полупанова, Елена Евгеньевна

• Полупанова, Елена Евгеньевна
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Полупанова, Елена Евгеньевна

Список иллюстраций.

Введение.

Глава 1 Анализ алгоритмов и методов решения задачи разбиения при проектировании СБИС.

1.1 Классификация алгоритмов разбиения.

1.2 Построение математической модели для задачи разбиения.

1.3 Постановка задачи разбиения схем при проектировании СБИС.

1.4 Учёт тепловых характеристик.

1.5 Выводы.

Глава 2 Применение методов биоинспирированного поиска для решения задачи разбиения схем при проектировании СБИС.

2.1 Разработка биоинспирированных методов и принципов разбиения схем при проектировании СБИС.

2.2 Методика кодирования информации в биоинспирированном алгоритме.

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

2.4 Формирование начального множества решений методом колонии пчел.

2.5 Схема биоинспирированного алгоритма разбиения элементов СБИС.

2.6 Выводы.

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

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

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

3.3 Разработка эвристического биоинспирированного алгоритма разбиения элементов СБИС.

3.4 Выводы

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

4.1 Обзор основных пунктов меню разработанной программы разбиения схем

4.2 Цель проведения экспериментальных исследований.

4.3 Формат входного файла.

4.4 Формат выходного файла гиперграфа.

4.5 Порядок проведения экспериментальных исследований.

4.6 Оценка результатов проведенных исследований.

4.6.1 Результаты применения генетических операторов.

4.6.2 Результаты экспериментальных исследований АВС-алгоритма.

4.6.3 Результаты исследований для разработанного алгоритма (БАР).

4.7. Сравнение разработанного биоинспирированного алгоритма с аналогами .110 4.8 Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование биоинспирированных алгоритмов разбиения схем при проектировании СБИС»

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

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

На этапе синтеза взаимодействие человека и ЭВМ происходит в интерактивном режиме. Основные недостатки такого подхода:

1) получение далёких от оптимальных решений;

2) возможности человека в решении задач синтеза сужаются в связи с усложнением проектируемых изделий;

3) возрастают затраты вычислительных ресурсов.

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

К основным критериям эффективности моделей, методов и алгоритмов автоматизированного проектирования относятся:

1) точность решения задач;

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

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

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

В результате решения задачи размещения для каждого блока на кристалле определяется конкретное место.

Основной результат решения задачи трассировки - конструктивная реализация связей между элементами.

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

Развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС нашло отражение в работах Норенкова И.П., Казеннова Г.Г., Шервани Н., Бершадского A.M., Курейчика В.М., Морозова К.К., Селютина В.А., и др. В большинстве своём разрабатываемые алгоритмы, программы и пакеты направлены на формирования базового плана кристалла (оптимизацию разбиения, размещения разногабаритных объектов) и на оптимизацию этапа трассировки соединений по критерию минимизации длины связей и занимаемой площади [3 - 5]. Из-за тесной взаимосвязи задач конструкторского проектирования и большой размерности каждой из них, а также появления новых направлений в технологии изготовления СБИС, появляется необходимость в разработке новых, методик и алгоритмов для решения данного класса задач. Для решения NP-полных задач, в которых оптимальное решение возможно найти только методами полного перебора непрерывно разрабатываются новые алгоритмы, позволяющие получать эффективные решения за приемлемое время. К таким алгоритмам можно отнести методы эволюционного поиска и генетические алгоритмы (ГА), развитие которых началось в начале 1970 гг., но только сейчас стало приоритетным в отношении других методов. В последние годы широкое распространение также получили алгоритмы, основанные на роевом интеллекте (Swarm-based optimization algorithms (SOAs)).

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

Над развитием стратегий эволюционного поиска работали такие учёные, как: Холланд Д.Х., Гольдберг Д.Е., Батищев Д.И., Букатова И.Л., Курейчик В.М., Норенков И.П., Растригин Л.А. и др. Эволюционные методы, генетические алгоритмы и алгоритмы роевого интеллекта являются одним из фундаментальных направлений научных исследований в области случайно-направленного поиска. Часто для сложной задачи необходимо найти любое решение, удовлетворяющее заданным ограничениям, поэтому целью биоинспирированных (эволюционно-генетических) алгоритмов является нахождение наилучшего, а не оптимального варианта разбиения. При этом применение других методов становится невозможным, вследствие чрезвычайной сложности решаемой задачи.

Таким образом, АКТУАЛЬНОСТЬ работы состоит в разработке новых алгоритмов и методов биоинспирированного поиска задачи разбиения схем при проектировании СБИС, позволяющих улучшить показатели качества, трудоёмкости и времени работы ЭВМ.

ЦЕЛЬ работы состоит в разработке и исследовании биоинспирированных алгоритмов для решения задачи разбиения схем при проектировании СБИС.

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

1) анализ задачи разбиения при автоматизированном проектировании;

2) обоснование выбора математической модели схем для решения поставленной задачи;

3) теоретические исследования эволюционных, генетических алгоритмов, а также алгоритмов роевого интеллекта, ориентированных на решение задачи разбиения схем при проектировании СБИС;

4) построение модифицированных генетических процедур для решения задачи разбиения схем при проектировании СБИС;

5) построение новых архитектур биоинспирированного поиска ориентированных на решение задачи разбиения схем при проектировании СБИС;

6) экспериментальные исследования разработанных алгоритмов и методов, а также их сравнение с известными аналогами.

В качестве МЕТОДОВ ИССЛЕДОВАНИЯ будем использовать законы и правила теории множеств, высшей математики, элементы теории графов и гиперграфов, алгоритмы комбинаторной оптимизации и эволюционного моделирования, элементы теории статистических вычислений.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в том, что:

1) разработана трёхуровневая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, оптимизирующая процесс эволюционно-генетического поиска;

2) разработан биоинспирированный алгоритм решения задачи разбиения, основанный на трёхуровневой архитектуре и использующий три алгоритма: алгоритма колонии пчёл, алгоритма генетического поиска и алгоритма эволюционного поиска;

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

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

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

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

1) Методика поиска решений, которая позволяет улучшить практические результаты по сходимости алгоритма, в связи с учетом математических и статистических закономерностей при распределении элементов.

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

3) Биоинспирированный алгоритм и программа для разбиения СБИС, созданная в среде объектно-ориентированного программирования Borland С++ Builder™ 6.0.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Материалы диссертационной работы использованы в Г/б № 12354 (1.04.01) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», Г/б № 12355 (12.8.08) «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений», грант РФФИ № 12388 (№ 08 - 01 - 00473) «Разработка теории и принципов решения задач проектирования, оптимизации и принятия решений на основе биоинспирированных нечетких генетических и эволюционных методов», грант РФФИ № 12382 (№ 09- 01 - 00492) «Разработка общей теории и когнитивных принципов эволюционных вычислений», грант РФФИ № 12383 (№ 09 - 07 -00318) «Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта», грант РФФИ №12389 (№10-01-00115) «Разработка теории и принципов построения интеллектуальных интегрированных подсистем в задачах проектирования и управления», РНП 2.1.2.1652 «Разработка теории и когнитивных принципов принятии решений на основе распределенных алгоритмов, инспирированных природными системами».

Теоретические и практические результаты работы прошли АПРОБАЦИЮ на научных семинарах (с 2008 по 2011 гг., ТТИ ЮФУ), VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «МОЛОДЕЖЬ XXI ВЕКА — БУДУЩЕЕ РОССИЙСКОЙ НАУКИ» (г. Ростов-на-Дону, 2009), Международных научно-технических конференциях "Интеллектуальные системы" (AIS'08) и "Интеллектуальные САПР" (CAD-2008) (Дивноморское, 2008 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2009» («ИС-2009») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09» (Дивноморское, 2009 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2010» («ИС-2010») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'10» (Дивноморское, 2010 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2011» («ИС-2011») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT' 11» (Дивноморское, 2011 г.).

ПУБЛИКАЦИИ. По теме диссертации опубликовано 14 печатных работ.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, и

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Полупанова, Елена Евгеньевна

Заключение

В диссертационной работе проведены следующие теоретические и практические исследования:

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

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

3) Для повышения качества решений, на начальном этапе работы биоинспирированного алгоритма, предложено использовать ABC - алгоритм роевого интеллекта. Для отбора решений в стартовую и последующие популяций используется «вариативный метод», состоящий из модифицированных эвристик отбора альтернативных решений: Э1, Э2, ЭЗ.

4) Предложен генетический алгоритм с модифицированными процедурами, для генетических операторов, зависящими от динамических параметров, позволяющих повысить устойчивость генетического поиска и качество получаемых решений. Для преодоления преждевременной сходимости применяется процедура «генетического всплеска». Предложен алгоритм эволюционного поиска, в состав которого входят эволюционные процедуры локального улучшения и преодоления преждевременной сходимости алгоритма (М1 и М2).

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

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

7) В результате комплексного исследования было выявлено, что улучшение работы биоинспирированного алгоритма разбиения по сравнению с ПГА составляет 3,3%. Предложенный БАР находит оптимальное решение за меньшее число итераций, т.е. эффективнее на 15,3%.

8) В качестве генератора стартовой популяции хромосом БАР использовался АВС-алгоритм. Результаты тестирования, показали, что для различных гиперграфов, среднее увеличение максимальной ЦФ составляет от 5% до 15%, а среднее увеличение минимальной ЦФ от 3%-19%. Таким образом, АВС-алгоритм позволяет повысить качество решений стартовой популяции, получает хорошие решения в задачах большой размерности, сокращая общее время работы БАР.

Список литературы диссертационного исследования кандидат технических наук Полупанова, Елена Евгеньевна, 2012 год

1. Норенков И. П., Арутюнян Н.М. Эволюционные методы в задачах выбора проектных решений // Электронное научно-техническое издание "Наука и образование", 2007.URL: http://technomag.edu.ru/doc/68376.html.

2. Норенков, И. П. Основы автоматизированного проектирования. М.: Изд-во МГТУ имени Н.Э. Баумана, 2006. 360 с.

3. Wei Y.C., Cheng С.К. "A two-level two-way Partitioning Algorithm", Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

4. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. "A general purpose multiple way Partitioning Algorithm", 28th ACM/IEEE Design Automation Conference, paper 25/1, pp.421-425., 1991.

5. Karypis G., Aggarwal R., Kumar V., and Shekhar S. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of the Design and Automation Conference, 2002.

6. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 2003.

7. Whitley L. D. An executable model of a simple genetic algorithm // In Whitley L.D. (ed): Foundations of Genetic Algorithms 2. Morgan Kaufmann, 2001.

8. Goldberg D.E., Kalyanmoy D. A comparative analysis of selection schemes used in genetic algorithms. In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. Mogan Kaufmann, San Mateo, С A, 1991.

9. Chen L. Chang Y., "Solve the vehicle routing problem with time windows via a genetic algorithm," Discrete and continuous dynamical systems supplement, C. 240-249, 2007.

10. Курейчик B.B., Курейчик B.M. Перспективные технологии для решения оптимизационных задач. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.1. М.: Физматлит, 2003, с 59-67.

11. Курейчик B.M. Генетические алгоритмы: Состояние. Проблемы. Перспективы. Теория и системы управления РАН. Москва. N 1, 2000, с.144-160.

12. Caldwell W.K. Mic Cut Partitioning With Functional Replication for Technology - Mapped Circuits Using Minimum Area Over hed. -//-V.21, №4, april 2002, pp. 491 -496.

13. Lieng J., Thulasiraman K. A Genetic Algorithm for Channel Routing in VLSI Circuits. Evolutionary Computation, 1(4), MIT, 1994. pp. 293-311.

14. Курейчик B.M. Генетические алгоритмы и их применение: Монография. Таганрог: Изд-во ТРТУ, 2002.

15. Чернышев Ю.О., Курейчик В.В. Генетические алгоритмы размещения / XXII International School And Conference On Computer Aided Design, CAD-95, Gurzuff, 1995. c. 329-330.

16. Cohoon J.P. and Paris W.D. Genetic placement. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.6, № 6, 1987. pp. 956-964.

17. Goodman, E. Tetelbaum, A. and Kureichik, V. (1994). A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems. Case Center Technical Report #940702, Michigan State University

18. Смирнова O.B. Модели эволюции в задачах компоновки схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №1 (19), 2002, с.47-49.

19. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, №10. Москва, 2001, стр.174-187.

20. Лебедев Б.К. Канальная трассировка на основе генетических процедур. Известия ТРТУ, №3. Таганрог, 1997. 53-60 с.

21. Лебедев Б.К. Планирование СБИС методом генетического поиска. Известия ТРТУ. Интеллектуальные САПР. Таганрог, Изд-во ТРТУ, 1999, №3. 119-126 с.

22. Vose M. D., Liepins G. E. Punctuated equilibria in genetic search // Complex Systems, 2001. no. 5, pp. 31-44.

23. Батищев Д.И., Власов C.E., Булгаков И.В. Плотное размещение разногабаритных объектов на плоскости с помощью генетических алгоритмов. XXIII International School and Conference on Computer Aided Design. Yalta-Gurzuff, 1996. 354 c.

24. Полупанов A.A., Полупанова E.E. Обзор современных методов и алгоритмов решения задачи компоновки // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'l 1». Научное издание в 4-х томах. М.: Физматлит, 2011. Т.З.

25. Ильин В.Н., Фролкин В.Т., Бутко А.И. и др.; «Автоматизация схемотехнического проектирования: Учебное пособие для вузов». Москва. : «Радио и связь», 2002.

26. Курейчик, В. М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990.

27. Емельянов, В. В. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.

28. Sherwani, N. A. Algorithms for VLSI Physical Design Automation. -Boston: Kluwer Academic Publishers, 1995. 538 p.

29. Karypis G., Kumar V. A coarse-grain parallel multilevel k-way partitioningalgorithm. In Proceedings of the eighth SIAM conference on Parallel

30. Processing for Scientific Computing, 2003.

31. Гладков JI. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы, учеб. пособие для. Ростов на - Дону: Ростиздат, 2004.

32. Лахути Д.Г. Садовский В.Н., Финн В.К. Эволюционная эпистемология и логика социальных наук: Карл Поппер и его критики. М.: Эдиториал УРСС, 2000.

33. Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.

34. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, №10. Москва, 2001.-стр. 174-187.

35. Тарасов В.Б. Интеллектуальные системы в проектировании. Новости ИИ, №4. 1993. - с.24 - 67.

36. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. М.: Эдиториал УРСС, 2002. -352с

37. Курносова Е.Е. Об одном подходе к построению интегрированных алгоритмов // Известия ЮФУ, Интеллектуальные САПР. Таганрог, 2008. с. 104.

38. Мищенко, М. Н. Бионический метод размещения элементов схем ЭВА // Перспективные информационные технологии интеллектуальные системы, №2 (22), 2005. с. 34 - 36.

39. Karaboga, D. An idea based on honey bee swarm for numerical optimization // Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

40. Субботин C.A., Олейник Ан.А., Олейник Ал.А. Интеллектуальные мультиагентные методы (Swarm Intelligence), часть III // Фрагмент рабочих материалов монографии. с. 35 - 52.

41. Курейчик В.В., Курносова Е.Е. Методы формирования стартовойпопуляции решений // Труды международных научно-техническихконференций «Интеллектуальные системы» (AIS'09) и

42. Курейчик В.В., Полупанова Е.Е. Эволюционная оптимизация на основе алгоритма колонии пчёл // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2009.

43. Goldberg D. Е. Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Company Inc., 1989. - 442p.

44. Курейчик В. M. Генетические алгоритмы и их применение, монография. Таганрог: Изд-во ТРТУ, 2002.

45. Гладков Л. А., Курейчик В.В. , Курейчик В.М. Генетические алгоритмы, под ред. В.М. Курейчика. М.: Физматлит, 2006. 320 с.

46. Курейчик В.В. , Полупанов А.А. Эволюционные методы разбиения схем на основе адаптивных генетических процедур, монография. Таганрог: Изд-во ТТИ ЮФУ, 2007. 160 с.

47. Secanina, L. Evolutionary design of digital circuits: where are current limits? // Proceedings of the first NASA/ESA conference on adaptive hardware and systems. 2006.

48. Конушин А. Эволюционные нейросетевые модели с незаданным заранее числом связей. www.ict.edu.ru/ft/002414/numlevol.pdf

49. Vose M.D. Modeling simple genetic algorithms // In Whitley L.D. (ed): Foundations of Genetic Algorithms 2. Morgan Kaufmann, 2003.

50. Stoica A. Evolvable hardware for autonomous systems // CEC-2004. -Tutorial.Portland, Oregon.

51. Miller, J. F. Job D., Vassilev V. K. Principles in the Evolutionary Designof Digital Circuits. Genetic Programming and Evolvable Machines. Part I.

52. Netherlands: Kluwer Academic Publishers, 2000. 1. - pp.7-35.

53. Курейчик В. M. , Зинченко JI. А. Эволюционное моделирование с динамическим изменением параметров // Труды VII национальной конференции по искусственному интеллекту. М.: Физматлит, 2000. с. 516-523.

54. Сороколетов П.В. Курейчик В.В. Концептуальная модель представления решений в генетических алгоритмах. Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР», №. 9, с. 7-12, 2008.

55. Гладков JI. А. , Зинченко JI. А., Курейчик В. В., Курейчик В. М., Лебедев Б. К., Нужнов Е. В., Сорокин С. Н. Методы генетического поиска. Научное издание. Таганрог: Изд-во ТРТУ, 2002. 122 с.

56. Курейчик В. В Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. Таганрог: Изд-во ТРТУ, 2001.

57. Potts J.С., Giddens Т., Yadav S. The Development and Evaluation of a improved Genetic Algorithm Based on Migration and Artificial Selection, IEEE Transactions on systems, man, and cybernetics. January 1994. -Vol.24, No.l.-pp. 73-86.

58. Herrera F., Lozano M. Adaptive Genetic Algorithms, based on Fuzzy Techniques. Granada, Spain, 1996. - pp. 775-780.

59. Батищев Д. И. Генетические алгоритмы решения экстремальных задач // Учебное пособие. Воронеж, 1995. 69 .

60. Davis L.D. Handbook of Genetic Algorithms // Van Nostrand Reinold. -New York, 1991.

61. Goldberg D. E., Kalyanmoy D. A. Comparative analysis of selection schemes used in genetic algorithms // In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. - Mogan Kaufmann, San Mateo, CA, 1991.

62. Курейчик B.B. Мищенко M. H. Бионический метод определения путей оптимальной длины в графовых моделях // III-й Международный научно

63. Генетические алгоритмы. URL: http://www.tspu.tula.ru/ivt/oldsite/umr/ ealg/w3c.html.

64. Норенков И. П., Косачевский О. Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Электронное научно-техническое издание "Наука и образование", 2005. URL: http://technomag.edu.ru/doc/56533.html.

65. Полупанов A.A., Полупанова Е.Е. Эвристический эволюционно-генетический алгоритм // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'IO». Научное издание в 4-х томах. М.: Физматлит, 2010. Т.З. - С. 83-89.

66. Митропольский А.К. Техника статистических исследований. М., "Наука", 1971. 576 с.: ил

67. Останин А.Н. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента // Учеб. Пособие. Минск: Вышэйшая школа., 1989. 218 с.: ил.

68. Львовский E.H. Статистические методы построения эмпирических формул // Учеб. пособие для втузов. М.: Высшая школа, 1988. 239 с.

69. Адлер Ю.П. Введение в планирование эксперимента. М.: Металлургия, 1969. 157 е.: ил.

70. Ежов И.И., Скороход A.B., Ядренко М.И. Элементы комбинаторики. М.: Наука, 1977. 264 с.

71. Гроппен В.О. Принципы оптимизации комбинаторных процедур. Ростов-на-Дону: Издательство РГУ, 1988. 195 е.: ил.

72. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.

73. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. М.: Наука, 1986. 544 е.: ил.

74. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений. М.: Физматгиз, 1962. 349 с.

75. Андерсон Т. Введение в многомерный статистический анализ/ Пер. с англ. Кичатова Ю.Ф. М.: Физматгиз, 1963. 500 е.: ил.

76. Большое Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 1965.464 с.

77. Гурский Е.И. Теория вероятностей с элементами математической статистики. М.: Высшая школа, 1971. 328 с.

78. Гренандер У. Случайные процессы и статистические выводы / Пер. с англ. и доп. Яглоба А.М. М.: Изд-во иностранной лит., 1961. 167 с.

79. Даймонд С. Статистика в науке / Пер. с англ. А.Л. Дружининой М.: Статистика, 1970. 155 с.

80. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

81. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский госуниверситет, 1994.

82. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с

83. Полупанова Е.Е. Экспериментальные исследования интегрированного алгоритма компоновки // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2010. - № 7 (108). - С. 96-100.

84. Thang Nguyen Bui, Byung-Ro Moon "GRCA: A Hybrid Genetic Algorithm for Circuit Ratio-Cut Partitioning". IEEE Transactions on computer-aided design of integrated circuits and systems, vol. 17, No.3, March 1998, pp. 193-204.

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

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

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

88. Зам. зав. кафедрой САПР по научной работе, д.т.н., проф.1. Б.К. Лебедев1. УТВЕРЖДАЮ» ПО НИДТТИЮФУ1. В. М. Курейчик 2012г.1. АКТ

89. Об использовании результатов кандидатской диссертации Полупановой Е.Е. в учебном процессе Южного федерального университета

90. Указанные результаты используются при чтении следующих курсов на кафедре САПР: «Автоматизация конструкторского и технологического проектирования»; «Методы оптимизации»; «Эволюционное моделирование и генетические алгоритмы».

91. Внедрение в учебный процесс ряда теоретических и практических результатов диссертационной работы Полупановой Е.Е. позволило повысить качество подготовки специалистов в области САПР и информационных технологий.

92. Начальник учебного отдела УМУ

93. Декан ФАВТ, д.т.н., профессор

94. Зам. зав. кафедрой САПР по учебной работе

95. Черный С.А. Вишняков Ю.М. Нужнов Е.В.1. РОС cutí ШСЛЛ ШДЖАЦ,FШ1. SS S м S йvC -ЧШВ1. Ш Ш й ЙШ Ш1. СВИДЕТЕЛЬСТВОо государственной регистрации программы мя ')ВМ2008615026

96. Программа компоновки технических элементов конструкций на основе бионических методов11раиоо6далате.'п.(ли): Федеральное государственное образовательное учреждение вгнешего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» (Я11)

97. Лвтор(ы): Курносова Елена Евгеньевна, Курейчик Владимир Викторович (ЯП)1. Заявка № 2008613928

98. Дата поступления 26 августа 2008 г.

99. Зарегистрировано в Рсестре программ для ЭВМ17 октября 2008 г.ч—>1. Ч ^

100. Руководитель Федеральной службы по интеллектуальной собственности, патентам и товарным знакам1. Б П. Симонов

101. Ш>ш ш $ ш WWWWWWm т WWWWWWWWWWWm mWWWWWWmW^