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

• Венцов, Николай Николаевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Венцов, Николай Николаевич

Оглавление.

ВВЕДЕНИЕ.

1. АНАЛИЗ СИСТЕМ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ САПР СБИС.

1.1. Анализ процесса проектирования и средств автоматизации проектирования СБИС.

1.2. Обзор стандартных подходов организации доступа к данным САПР СБИС

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

1.4. Обзор перспективных методов решения оптимизационных задач.

1.5. Выводы.

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

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

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

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

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

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

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

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

2.8. Сравнительный анализ результатов работы разработанных алгоритмов.

2.9. Выводы.

3. РАЗРАБОТКА ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ И АВТОМАТОВ АДАПТАЦИИ ДЛЯ ПОИСКА РЕШЕНИЯ ЗАДАЧИ ВЫБОРА ОПТИМАЛЬНОГО ПОРЯДКА СОЕДИНЕНИЯ ОТНОШЕНИЙ РАСПОЛОЖЕННЫХ НА ОДНОМ УЗЛЕ САПР, НА ОСНОВЕ АДАПТИВНОЙ СХЕМЫ ОПТИМИЗАЦИИ ЗАПРОСОВ.

3.1. Разработка и анализ модифицированного генетического алгоритма решения задачи.

3.2. Анализ результатов работы разработанного алгоритма.

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

3.4. Анализ результатов работы автоматов адаптации использующих различные алгоритмы оптимизации.

3.5. Выводы.

4. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ.

4.1. Описание пакета программ моделирующих работу генетических алгоритмов и автоматов адаптации.

4.2. Определение вычислительной сложности алгоритмов для динамического программирования и жадного алгоритма.

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

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

4.5. Выводы.

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

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

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

Развитие эволюционных подходов к решению оптимизационных задач в значительной мере определяется работами 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%.

Список литературы диссертационного исследования кандидат технических наук Венцов, Николай Николаевич, 2006 год

1. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация: теория и практика. М.: ФИЗМАТЛИТ,2006.

2. Гузик В.Ф., Пьювченко А.О., Панов Д.И., Переверзов В.А. Введение в систему автоматизированного проектирования OrCAD: структура и применение. Учебное пособие. Часть 1. Таганрог. Изд-во ТРТУ 2001 г.

3. Норенков И.П. Основы автоматизированного проектирования. Учеб. Для вузов М.: Изд-во МГТУ им. Н.Э. Баумана, 2000.

4. Кузнецов С.Д. СУБД (системы управления базами данных) и файловые системы. М.: Майор, 2001.176 с. - (Мой компьютер).

5. Трамбле Ж., Соренсон П. Введение в структуры данных: Пер. с англ./Пер. В.И. Бриккер и др.; Под ред. А.Е. Костина, В. Ф. Шаньгина. -М.: Машиностроение, 1982. 784 е., ил.

6. Григорьев Ю.А., Ревунков Г.И., Банки данных: Учеб. Для вузов.-М.:Изд-во МГТУ им. Н.Э. Баумана, 2002. 320 с. (Сер. Информатика в техническом университете).

7. Гарсиа Молина, Гектор, Ульман, Джеффри, Д., Уидом, Джениффер Системы баз данных. Полный курс.: Пер.с англ.- М.: Издательский дом "Вильяме", 2003.-1088 е.: ил. - Парал. тит. Англ.

8. Архипенков С.Я. Аналитическая система на базе Oracle Express OLAP: Проектирование, создание, сопровождение. М.: Диалог - МИФИ, 1999. -319 с.: ил.

9. Базы данных: Интеллектуальная обработка информации / В.В. Корнеев, А.Ф. Гареев, С.В. Васютин, В.В. Райх. 2-е изд. - М.: Молгачева С.В., 2001.-494с.: ил.

10. Delphi 7 / Под общ. Ред. А.Д. Хоменко. СПб.: БХВ - Петербург,2003.

11. Торбен Бэч Педерсен, Кристиан Йенсен. Технология многомерных баз данных. Открытые системы # 01/2002. с 21-23.

12. Михаэл Стоунбрейкер Объектно реляционные системы баз данных. Открытые системы. № 4/1994. с 12-14.

13. Д. Чемберлин Анатомия объектно- реляционных баз данных. «СУБД» №1-2/1998.

14. Е. Григорьев. Представление идентифицируемых сложных объектов в реляционной базе данных. Открытые системы № 01-02/ 2000.

15. Волкер Маркл, Гай Лохман, Виджайшанкар Раман LEO: самонастраивающийся оптимизатор запросов для DB 2. Открытые системы № 04/ 2003.

16. Джозеф Хеллерштейн, Майкл Франклин, Сириш Чандрасекаран, Амол Дешпанде, Крис Хилдрум, Сем Медлен, Виджайшанкар Раман, Мехул Шах. Адаптивная обработка запросов: технология в эволюции. Открытые системы № 07-08/ 2000 с 27-32.

17. Адаптация на основе самообучения / В.М. Курейчик, Б.К. Лебедев, О.Б. Лебедев, Ю.О. Чернышев . РГАСХМ ГОУ Ростов н/Д., 2004. - 146 с.

18. Кузнецов С.Д. Об основаниях ненавигационного языка запросов к объектно- ориентированным базам данных. Программирование №2 1995. с 15-18.

19. Компьютер и задачи выбора М.:Наука, 1989- 208 с.

20. Кузнецов С.Д. Оптимизация запросов: вечнозеленая область. Открытые системы #04/2003 с 32-35.

21. Michael Stillger, Guy Lohmann, Volker Markl, Mortkal Kandil. LEO DB's LEarning Optimizer.

22. Лебедев Б.К. Адаптация в САПР. Монография. Таганрог: Изд-во ТРТУ, 1999.

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

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

25. Дискретная математика, Часть 1.Учебное пособие. Таганрог: ТРТУ, 1997,130 с.

26. A.M. Наместников, Н.Г. Ярушкина Эффективность генетических алгоритмов для задач автоматизированного проектирования. Известия академии наук. Теория и системы управления, 2002, №2. с 127-133.

27. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: ФИЗМАТЛИТ, 2003. - 432с.

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

29. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978. - 400 с.

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

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