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

• Бакало, Михаил Анатольевич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Бакало, Михаил Анатольевич

ВВЕДЕНИЕ.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К МОДЕЛИРОВАНИЮ ЭВОЛЮЦИОННОГО ПОИСКА.

1.1. МЕТОДЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

1.2. ОПИСАНИЕ МОДЕЛЕЙ ЭВОЛЮЦИИ.

1.3. СРАВНИТЕЛЬНАЯ ХАРАКТЕРИСТИКА СУЩЕСТВУЮЩИХ ПРОГРАММ ГЕНЕТИЧЕСКОГО ПОИСКА.

1.4. ПОСТАНОВКА ЗАДАЧИ РАЗМЕЩЕНИЯ.

1.5. ВЫВОДЫ.

2. АРХИТЕКТУРА ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

2.1. СТРУКТУРА И ОРГАНИЗАЦИЯ ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

Подсистема пользовательского интерфейса.

Ядро подсистемы генетического поиска.

2.2. КОНЦЕПТУАЛЬНАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ РЕШЕНИЯ ЗАДАЧИ.

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

Представление решения задачи размещения.

2.3. КОНЦЕПТУАЛЬНАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА.

2.4. ВЫВОДЫ.

3. РАЗРАБОТКА БЛОКОВ ИНТЕРИРОВАННОЙ

ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА И АЛГОРИТМОФ ЕЕ ФУНКЦИОНИРОВАНИЯ.

3.1. КОМПОНЕНТНАЯ МОДЕЛЬ ОРГАНИЗАЦИИ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

3.2. ВНУТРЕННЯЯ СТРУКТУРА ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

3.3. ЛИНГВИСТИЧЕСКИЕ СРЕДСТВА ОПИСАНИЯ ПРОЦЕДУР ГЕНЕТИЧЕСКОГО ПОИСКА ПРОЕКТНЫХ РЕШЕНИЙ.

3.4. РАЗРАБОТКА АЛГОРИТМОВ ФУНКЦИОНИРОВАНИЯ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

3.5. РАЗРАБОТКА МОДИФИЦИРОВАННЫХ ГЕНЕТИЧЕСКИХ ОПЕРАТОРОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ.

3.6. РАЗРАБОТКА АЛГОРИТМА ДВУМЕРНОГО РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СХЕМ.

3.7. ВЫВОДЫ.

4. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА И НА ПРИМЕРЕ ЗАДАЧИ РАЗМЕЩЕНИЯ РАЗНОГАБАРИТНЫХ ЭЛЕМЕНТОВ СХЕМЫ.

4.1. ЦЕЛЬ ЭКСПЕРИМЕНТА.

4.2. ТЕОРЕТИЧЕСКАЯ ОЦЕНКА ВРЕМЕННОЙ И ПРОСТРАНСТВЕННОЙ СЛОЖНОСТИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗМЕЩЕНИЯ.

4.3. ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА.

4.4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА.

4.5. ВЫВОДЫ.

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

Проектирование электронно-вычислительной аппаратуры (ЭВА) [1] начинается с разработки технического задания (ТЗ) [2], отражающего потребности человека и завершается реализацией ТЗ в виде набора конструкторской и технологической документации [3]. При этом поставленные перед разработчиком задачи должны быть решены с максимальной эффективностью, что охватывает не только снижение себестоимости продукции и сокращение сроков проектирования и производства, но и обеспечение удобства освоения и снижения затрат на будущую эксплуатацию изделий. В связи со сложностью современных ЭВА достижение поставленных целей и формирование проектных решений оказывается невозможным без широкого использования систем автоматизированного проектирования (САПР) [1 -3]. Задачи конструкторского проектирования приобрели характеристики оптимизационных многокритериальных задач [1 -4], решение которых высокую эффективность показывают методы эволюционного моделирования.

Эволюционное моделирование является одной из фундаментальных областей научных исследований на стыке информатики, биологии и искусственного интеллекта [4, 5, 6]. Они находят применение при решении различных задач исследования графов [6], автоматизированного проектирования [6-1], построения правил вывода в самонастраивающейся экспертной системе продукционного типа [8].

В настоящее время генетические алгоритмы (ГА) — хорошо известная и эффективная оптимизационная методология, основанная на аналогии процессов натуральной селекции и генетических преобразований. Биологические основы этой эффективной методологии для адаптационных процессов есть эволюция от одного множества альтернативных решений к другому. Причем, основой этого процесса является "выживание сильнейших", что выполняется путем исключения "слабо приспособленных" решений и оставление оптимальных или квазиоптимальных решений [11].

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

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

Однако разработка и программная реализация ГА, а также их применение и распространение, совершенствование и развитие сдерживаются целым рядом причин, среди которых доминируют следующие [12]: разработка практически каждого ГА является уникальной ввиду жесткой привязки к задаче на этапах кодирования и декодирования ее решений в виде генов и хромосом. Разработчики обычно «наследуют» и развивают только опыт построения отдельных генетических операторов (ГО) и общей организации процедур генетического поиска решений в ГА; программная реализация ГА производится практически с нуля. При этом в новых проектах обычно теряются все наработки программистов, связанные с оптимизацией структур данных, построения и кода самой программы, а также средствами повышения эффективности вычислений на основе различных эвристик; программная реализация ГА, как правило, заканчивается разработкой «вещи в себе» - программного продукта, ни в коей мере не относящегося к категории открытых систем. При этом теряется возможность оперативных сравнительных исследований эффективности применения данного ГА для решения рассматриваемой задачи с подобными ему или алгоритмами других классов;

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

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

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

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

1. Построена открытая архитектура интегрированной инструментальной ПГП поиска.

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

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

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

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

6. Разработан ГА для решения задач автоматизированного проектирования, на примере которого исследована эффективность разработанной подсистемы.

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

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

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

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

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

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

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

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

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

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

Апробация основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Международных научно-технических конференциях: Международной научно-технической конференции «Интеллектуальные системы (IEEE AIS'04)» (с. Дивноморское, 2004), Международной научно-технической конференции «Интеллектуальные системы» (AIS'05) и «Интеллектуальные САПР» (CAD-2005) (с. Дивноморское, 2005г. Получено свидетельство об официальной регистрации программы для ЭВМ № 2006612763, 2006г. По итогам открытого конкурса на лучшую научную работу студентов по естественным, техническим и гуманитарным наукам в вузах Российской Федерации, проводимого Министерством образования и науки

РФ, получена медаль и удостоверение от 15.07.2005г. «за лучшую научную работу».

Публикации. По теме диссертационной работы опубликовано 7 печатных работы, сделано 2 доклада на Международных научно-технических конференциях.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 175 страницах, содержит 28 рисунков, 14 таблиц, 104 наименования библиографии и приложения.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Бакало, Михаил Анатольевич

4.5. ВЫВОДЫ

1. Дополнительные расходы времени, затраченные подсистемой генетического поиска на реализацию генетического алгоритма, не превосходят 6% по сравнению с реализацией данного алгоритма на языке программирования С++.

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

3. Качество размещений, полученных генетическим алгоритмом, разработанным с использованием интегрированной инструментальной подсистемы, в среднем на 6,38% превосходит результаты размещения, полученные с использованием известных алгоритмов Capo 8.6, Feng Shui 2.0, Dragon 2.23, что говорит об эффективности предложенного алгоритма и подсистемы генетического поиска в целом.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

7. Разработаны алгоритмы детализации описания ГА, функционирования ядра ПГП, а также алгоритмы функционирования подсистем макроэволюционно-го и метаэволюционного моделирования на этапе сборки и на этапе выполнения ГА.

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

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

10.С использованием реализованной подсистемы генетического поиска разработан генетических алгоритм двумерного размещения разногабаритных элементов схем ЭВА, который использует мультихромосомное кодирование содержащее: числовую гомологичную хромосому - определяющую последовательность элементов, путем «кодирования перестановок»; двоичную хромосому - для кодирования ориентации элементов в пространстве.

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

Проведенный вычислительный эксперимент подтвердил полиномиальную вычислительную и пространственную сложность разработанного алгоритма. При этом качество размещений, полученных генетическим алгоритмом в среде ПГП, в среднем на 6,56% превосходит результаты размещения, полученные с использованием известных алгоритмов Capo 8.6, Feng Shui 2.0, Dragon 2.23, что говорит об эффективности предложенного алгоритма и подсистемы генетического поиска в целом.

Список литературы диссертационного исследования кандидат технических наук Бакало, Михаил Анатольевич, 2007 год

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

2. Колчин А.Ф. и др. Управление жизненным циклом продукции. М.: Анарха-сис, 2002.

3. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Воронеж: Изд-во ВГУ, 1997.

4. Holland John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975.

5. Грант В. Эволюционный процесс http://alpha.ipr.serpukhov.su/~mlobanov/-grant/index.html

6. Гринченко С.Н. «Метод «проб и ошибок» и поисковая оптимизация: анализ, классификация, трактовка понятия «Естественный отбор» http://zhurnal.ape.relarn.ru/articles/2003/104.pdf

7. Курейчик В.М. Генетические алгоритмы. Монография. Таганрог: ТРТУ, 1998.

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

9. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: учебное пособие под ред. В.М. Курейчика. Ростов-на-Дону:000 «Росиз-дат», 2004.-400с.

10. Kureichik V.M., Zinchenko L.A. Evolutionary adaptation in the modeling of nonlinear electrical circuits. Proceedings NOLTA 2000, Dresden, 17-21 September, 2000, v.l, p. 221-224.

11. И.Курейчик B.B. Эволюционные методы решения оптимизационных задач. Таганрог, 1999, ТРТУ.

12. Курейчик В.В., Нужнов Е.В. «Возможности организации интегрированной инструментальной среды поддержки процедур генетического поиска и оптимизации решений»

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

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

15. Рутковская Д. Пилиньски М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая линия - Телеком, 207. 452с.

16. Исаев С. «Генетические алгоритмы в задачах оптимизации» http://www.uran.donetsk.ua/~masters/2005/kita/shestopalov/library/gaoptim.htm

17. Цой Ю.Р. «Применение генетического алгоритма для задач оптимизации многоэкстремальных функций».

18. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Van No-strand Reinhold, New York, 1991.

19. Редько В.Г., Цой Ю.Р. «Оценка эффективности эволюционных алгоритмов».

20. Редько В.Г., Цой Ю.Р. «Уточнение оценок эффективности эволюционных алгоритмов». Конференция «Интеллектуальные системы».

21. Гридин В.Н. Теоретические основы построения базовых адаптируемых компонентов САПР МЭА. М.: Наука, 1989.

22. Редько В.Г. «Оценка эффективности простейшей версии генетического алгоритма».

23. Редько В.Г. «Эволюционная кибернетика» http://library.mephi.ru/data/-scientific-sessions/2002/Lec Neuro 1/029.html

24. Цой Ю.Р. «О математических моделях эволюционных алгоритмов» //Перспективные информационные технологии и интеллектуальные системы 2006г.

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

26. Дарвин Ч. Происхождение видов путем естественного отбора. М.: Наука, 2000.

27. Goldberg David Е. Genetic Algorithm in Search, Optimization and Machine Learning. USA.: Addison-Wesley Publishing Company. Ind., 1989.

28. Ламарк Ж.Б. Философия зоологии. T.1,2, М.-Л.: «Академия», 1939.

29. Дубинин Н.П. Избранные труды, Т.1. Проблемы гена и эволюции. М.: Наука, 2000.

30. Кимура М. Молекулярная эволюция: теория нейтральности. М.: Мир, 1985, 400 с.

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

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

33. Luger G. Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Fourth Edition. Addison-Wesley Publishing Company, 2002.

34. GeneHunter targets optimal solutions with genetic http://www.neuroproiect.ru/-aboutproduct.php?info=ghinfo

35. Evolver The Innovative Optimizer for Windows. http://www.palisade-europe.com/evolver/default.asp

36. Афанасьев M.K. «Построение и исследование генетических алгоритмов с использованием NSGalaxy» http://alice.stup.ac.ru/005/nits2000/sec2/sec2-16.htm.

37. Вермишев Ю.Х. Основы автоматизированного проектирования. М.: Радио и связь, 1988.

38. Библиотека GeneBase 2.0 http://www.basegroup.ru

39. GAlib: Matthew's С++ Genetic Algorithms Library http://lancet.mit.edu/ga/

40. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. -М.: Энергоатомиздат, 1987.

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

42. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных ИС. Ростов-на-Дону, изд-во РГУ,1999.

43. Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры. М.: Изд-во МГТУ, 2002.

44. Автоматизация проектирования БИС. В 6 кн. Под ред. Г.Г. Казеннова. М.: Высшая школа, 1990.

45. Малышев Н.Г., Мицук Н.В. Основы оптимального управления процессами автоматизированного проектирования. М.: Энергоатомиздат, 1990.

46. Sherwani Naveed. Algorithms for VLSI Physical Design Automation Boston/Dordrecht/London: Kluwer Academic Publishers, 1995.

47. Бакало M.A., Курейчик B.B. К вопросу модифицированного алгоритма размещения. // ПИТИС 2006г. № 4(28) Таганрог, 2006, с.44-55.

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

49. Бакало М.А., Курейчик В.В. Модифицированный алгоритм размещения методом парных перестановок. //ИЗВЕСТИЯ ТРТУ. Интеллектуальные САПР 2007г. Таганрог.: Науч. изд., 2007, с.77-84.

50. Харари Ф. Теория графов. М.: Мир, 1977.51 .Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

51. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. -Саратов: Изд-во СГУ, 1993.

52. Глушань В.М. Графовые модели представления вычислительных алгоритмов. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 133-138.

53. Bourque P., Dupuis R. Guide to the Software Engineering Body of Knowledge // IEEE Computer Society, 2001.

54. Автоматизация проектирования БИС. В 6 кн. Под ред. Г.Г. Казеннова. М.: Высшая школа, 1990.

55. Вигерс К. Разработка требований к программному обеспечению /Пер. с англ. М.: Издательско-торговый дом «Русская редакция», 2004. - 574с.: ил.

56. Гатчин Ю.А., Коробейников А.Г. Методы представления математических моделей в САПР при концептуальном и инфологическом моделировании. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 35-41.

57. Макконнел С. Совершенный код. Мастер класс / Пер. с англ. М.: Издательско-торговый дом «Русская редакция»; СПб.: Питер, 2005 - 896с.: ил.

58. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ М.: МЦМО, 2000.

59. Бородкин Л.И. «Многомерный статистический анализ» http://iwww.iskunstvo.info/-,edu/iinf/-,cluster.htm

60. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. «Приемы объектно-ориентированного проектирования: паттерны проектирования» СПб: Питер, 2001 -368с.

61. Gunderloy М. Developer to Designer. GUI Design for the Busy Developer San Francisco, London: Sybex, 2005 - 367c.

62. Backalo M.A.The finding of the maximum matching using neural network. Proceedings of the International Scientific Conferences "Intelligent Systems (IEEE AIS'04)" and "Intelligent CAD's (CAD- 2004)". M, Physmathlit, 2004. vol. 3. pp. 121.

63. Страуструп Б. Язык программирования С++, спец.изд. /Пер. с андл. М.; СПб.: «Издательство БИНОМ» - Невский диалект», 2002 - 1099с.

64. Бакало М.А. Варианты представления различных типов данных, их кодирование и декодирование в виде хромосом // ИЗВЕСТИЯ ТРТУ. Интеллектуальные САПР 2007г. Таганрог : Науч. изд., 2007, с.70-75.

65. Гладков JI.A., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов / под ред. В.М. Курейчика. Учебное пособие по курсу «Математическая логика и теория алгоритмов». Таганрог. ТРТУ, 2002, - 82с.

66. Мелихов А.Н., Берштейн JI.C. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов на-Дону. Изд-во РГУ,1981.

67. Схемы алгоритмов и программ. Правила выполнения. ГОСТ 19.002-80.

68. Схемы алгоритмов и программ. Обозначение условные графические. ГОСТ 19.003-80.

69. Спецификация Extensible Markup Language http://www.w3.org/XML.

70. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000.

71. Семакин М.М. «Компонентная модель организации программных систем» -Ижевск, 2004.

72. Бакало М.А., Курейчик В.В. Концепция построения системы поддержки генетических алгоритмов // Прикладные информационные технологии и интеллектуальные системы №4 Науч. изд. Таганрог, 2006.

73. Элджер Жд. С++:Библиотека программиста СПб.: Питер, 2000. - 320с.

74. Плаугер П., Степанов А., Ли М., Массер Д. STL стандартная библиотека шаблонов С++ / Пер. с англ. - СПб.: БХВ-Петербург, 2004. - 656с.: ил.

75. Александреску А. Современное проектирование на С++. Серия С++ in-Depth, т.З.: Пер. с англ. М.: Издательский дом «Вильяме», 2002 - 336с.: ил.

76. Леденев А., Акентьев А., Сторожевых В., Семенов И. Вопросы написания DLL. http://www.progz.ru/print.php?articles=45.

77. Спецификация языка описания схем XML (XML Schema Definition XSD) http://www.w3.org/2001XMLShcema.

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

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

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

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

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

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

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

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

86. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий. -М.: Наука, 1971.283 е.: ил.

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

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

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

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

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

92. Caldwell А. Е., Kahng А. В., Markov I. L. Can Recursive Bisection Alone Produce Routable Placements? DAC 2000, pp.477-82.

93. Caldwell A. E., Kahng A.B., Markov I. L. Optimal Partitioners and End-case Placers for Standard-cell Layout IEEE Trans, on CAD, vol. 19(11) 2000, pp. 1304-1314

94. Wang M., Yang X., Sarrafzadeh M. Dragon2000: Standard-cell Placement Tool for Large Industry Circuits ICCAD2000, pp. 260-263.

95. Yang X., Choi B.-K., Sarrafzadeh M. Routability Driven White Space Allocation for Fixed-Die Standard-Cell Placement ISPD 2002, pp. 42-50.

96. Yang X., Choi B.-K., Sarrafzadeh M. Timing-Driven Placement using Design Hierarchy Guided Constraint Generation ICC AD 2002, pp. 177-184.

97. Agnihotri A., Yildiz M. C., Khatkhate A., Mathur A., Ono S., Madden P.H. Fractional Cut: Improved Recursive Bisection Placement ICCAD2003

98. Yildizand M.C., Madden P.H. Improved Cut Sequences for Partitioning Based Placement DAC2001, pp.776-779.

99. IBM-PLACE 2.0 benchmark suits http://er.cs.ucla.edu/benchmarks/ibm-place2/bookshelf/ibm-place2-all-bookshelf-nopad.tar.gz1. АКТоб использовании результатов диссертационной работы Бакало М.А.

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

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

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

103. Научные результаты, полученные в диссертационной работе Бакало М.А., использовались в г/б НИР №12362 «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».

104. Технологического института Южного федерального университета в г. Таганроге результатов кандидатской диссертации Бакало М.А.

105. Разработка и исследование интегрированной инструментальной подсистемыгенетического поиска»

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

107. Работа выполнена в рамках приоритетного национального проекта «Образование».

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

109. Гривцов В.В. Вишняков Ю.М. Лебедев Б.К.оводителя1. ИЮФУ Пугач 2007 г.1. Начальник УО

110. Декан ФАВТ, д.т.н., профессор Зам. заведующего каф. САПР, д.т.н., профессор