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

Проектирование электронно-вычислительной аппаратуры (ЭВА) [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 г. Получено свидетельство об официальной регистрации программы для ЭВМ № 2 006 612 763, 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, что говорит об эффективности предложенного алгоритма и подсистемы генетического поиска в целом.