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

Актуальность темы

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

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

Развитие эволюционных подходов к решению оптимизационных задач в значительной мере определяется работами M.JI. Цетлина, JI. Фогеля (L.J. Fogel), Г. Шефеля (Н. Schwefel), Дж. Холланда (Holland John Н.) и др. Теоретические основы систем автоматизации проектирования СБИС получили развитие в работах К. К. Морозова, В. М. Курейчика, И. П. Норенкова и др. Большой вклад в 5 развитие теории и практики организации доступа к данным внесли С. Д. Кузнецов, Дэйт (С. J. Date), П. П. Чен (Chen P.P.), Д. Д. Ульман (Ullman J.D.), Г. ГарсиаМолина, (Garsia-Molina Н.) и др.

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

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

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

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

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

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

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

Научная новизна заключается в следующем:

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

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

Решение поставленных задач позволяет вынести на защиту следующие научные результаты:

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

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

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

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

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

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

Реализация результатов работы. Полученные результаты использованы при выполнении фундаментальных госбюджетных научно-исследовательских работ Ростовской-на-Дону государственной академии сельскохозяйственного машиностроения (РГАСХМ) на кафедре «Прикладная математика и вычислительная техника» по заказу Минобрнауки РФ по теме «Теория интеллектуальных процедур поиска оптимальных решений» (01.01.2005 г.-31.12.2005 г.) и «Развитие теории канальной трассировки на основе эволюционного моделирования» (01.01.2006 г. — 31.12.2006 г.) Кроме того, результаты выполненных работ внедрены и используются в учебном процессе в РГАСХМ при чтении лекций и проведении практических занятий по дисциплинам «Дискретная математика» и «Программные средства САПР». Разработанные генетические алгоритмы использовались в ФГУП Научно-исследовательский институт специальных информационно-измерительных систем (г. РостовнаДону).

Апробация работы и публикации. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные системы» (AIS-05, 06) и «Интеллектуальные САПР» (CAD-2005, 2006) (г. Геленджик, 2005, 2006 гг.,), «Компьютерные и вычислительные технологии в задачах естествознания и образования» (г. Пенза, 2005 г.), Всероссийской научно-практической конференции «Транспорт- 2006» (г. РостовнаДону 2006 г.). Материалы диссертационной работы вошли в два отчета по НИР: «Теория интеллектуальных процедур поиска оптимальных решений» № ГР 012.00.50.55.01 и «Развитие теории канальной трассировки на основе эволюционного моделирования» № ГР 012.00.60.42.68.

По материалам диссертации опубликовано 8 печатных работ, в том числе 2 статьи в периодических научных журналах рекомендованных ВАК.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 118 наименований и приложения, изложенных на 161 странице. Содержит 61 рисунок, 37 таблиц.

4.5. Выводы.

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

2. Экспериментально определена вычислительная сложность генетического алгоритма решающего задачу выбора оптимального порядка соединения отношений, расположенных на одном узле САПР, на основе статического подхода к оптимизации запросов. На задачах, размерности 8−15 экономия по времени в среднем составляет не менее 15−20%, на задачах размерности 15−30, не менее 25−30% по сравнению с методом динамического программирования.

3. Алгоритмы случайного поиска позволяют определять приемлемые субоптимальные решения с вероятностью 0,4−0,5. Не смотря на то, что разработанным алгоритмам требуется на 20−30% больше времени по сравнению с жадным алгоритмом, вероятность улучшения решения на 8−12% составляет 0,7−0,9.

4. При решении задачи выбора оптимального порядка соединения отношений, в соответствии со схемой оптимизации запросов, которую предложили Кабра и Девит, применение предлагаемых автоматов адаптации требует на 15−25% больше времени, чем использование жадного алгоритма.

ЗАКЛЮЧЕНИЕ

.

1. Для решения задачи выбора оптимального порядка соединения отношений расположенных на одном узле САПР в соответствии со статическим подходом к оптимизации запросов, разработаны генетический алгоритм и два алгоритма случайного поиска.. Вероятность определения оптимального решения генетическим алгоритмом составляет 0,5−0,6, субоптимального (отличающегося от оптимального не более чем на 15%) 0,7−0,85. На задачах, размерности (количество соединяемых отношений) 8−15 экономия по времени составляет 15−20%, на задачах размерности 15−30, 25−30% по сравнению с методом динамического программирования. Алгоритмы случайного поиска позволяют определять приемлемые субоптимальные решения с вероятностью 0,4−0,5. Не смотря на то, что разработанным алгоритмам требуется на 20−30% больше времени по сравнению с жадным алгоритмом, вероятность улучшения решения на 8−12% составляет 0,7−0,9.

2. Для решения задачи выбора оптимального порядка соединения отношений, расположенных на различных узлах САПР в соответствии со статическим подходом к оптимизации запросов, разработан генетический алгоритм который позволяет определять более приемлемое решение, по сравнению со стандартным методом, пересылки отношений на узел хранящий наибольшее отношение, с вероятностью 0,15−0,20, при этом улучшение по качеству составляет 5−8%.

3. Разработан генетический алгоритм для решения задачи выбора оптимального порядка соединения отношений расположенных на одном узле САПР на основе адаптивного подхода к оптимизации запросов. Алгоритм определяет оптимальное (либо отличающиеся от оптимального не более чем на 15%) решение с вероятностью 0,6−0,8.

4. При решении задачи выбора оптимального порядка соединения отношений, в соответствии со схемой оптимизации запросов, которую предложили Кабра и Девит, применение предлагаемых автоматов адаптации требует на 15−25% больше времени, чем использование жадного алгоритма, но с вероятностью 0,5 гарантируется улучшение получаемого решения на 15−30%.