Содержание к диссертации
Введение
1. Анализ систем управления базами данных САПР СБИС 11
1.1. Анализ процесса проектирования и средств автоматизации проектирования СБИС 11
1.2. Обзор стандартных подходов организации доступа к данным САПР СБИС 20
1.3. Постановка задач выбора оптимального порядка соединения отношений,
расположенных на одном и на нескольких узлах распределенной САПР 30
1.4. Обзор перспективных методов решения оптимизационных задач 37
1.5. Выводы 41
2. Разработка генетических алгоритмов и алгоритмов случайного поиска для решения задач выбора оптимального порядка соединения отношений, на основе статического метода оптимизации запросов 42
2.1. Математическая формулировка задачи выбора оптимального порядка соединения отношений расположенных на одном узле САПР СБИС 44
2.2. Математическая формулировка задачи выбора оптимального порядка соединения отношений расположенных на нескольких узлах распределенной САПР СБИС 47
2.3. Анализ целесообразности применения стандартных генетических операторов для построения генетических алгоритмов решающих поставленные задачи 50
2.4. Разработка и анализ генетического алгоритма решающего задачу выбора оптимального порядка соединения отношений расположенных на одном узле САПР, на основе стандартных генетических операторов 58
2.5. Разработка и сравнительный анализ модифицированного генетического алгоритма, решающего задачу выбора оптимального соединения отношений расположенных на одном узле САПР 65
2.6. Разработка и анализ модифицированного генетического алгоритма, решающего задачу выбора оптимального соединения отношений расположенных различных узлах САПР 75
2.7. Разработка алгоритмов случайного поиска решения задачи выбора оптимального порядка соединения отношений расположенных на одном узле САПР 84
2.8. Сравнительный анализ результатов работы разработанных алгоритмов 92
2.9. Выводы 101
3. Разработка генетических алгоритмов и автоматов адаптации для поиска решения задачи выбора оптимального порядка соединения отношений расположенных на одном узле сапр, на основе адаптивной схемы оптимизации запросов 103
3.1. Разработка и анализ модифицированного генетического алгоритма решения задачи 112
3.2. Анализ результатов работы разработанного алгоритма 115
3.3. Разработка автомата адаптации для решения поставленной задачи 119
3.4. Анализ результатов работы автоматов адаптации использующих различные алгоритмы оптимизации 126
3.5. Выводы 128
4. Вычислительный эксперимент 129
4.1. Описание пакета программ моделирующих работу генетических алгоритмов и автоматов адаптации 129
4.2. Определение вычислительной сложности алгоритмов для динамического программирования и жадного алгоритма 133
4.3. Анализ алгоритмов разработанных для поиска решения задачи выбора оптимального порядка соединения отношений расположенных на одном узле САПР, на основе статического подхода 136
4.4. Анализ алгоритмов разработанных для поиска решения задачи выбора оптимального порядка соединения отношений на основе адаптивного подхода. 142
4.5. Выоды 146
Заключение 147
Список литературы
- Обзор стандартных подходов организации доступа к данным САПР СБИС
- Математическая формулировка задачи выбора оптимального порядка соединения отношений расположенных на нескольких узлах распределенной САПР СБИС
- Разработка автомата адаптации для решения поставленной задачи
- Определение вычислительной сложности алгоритмов для динамического программирования и жадного алгоритма
Введение к работе
Актуальность темы. Важной составляющей процесса автоматизации проектирования СБИС является организация оперативного доступа к данным, описывающим структуру и функциональные характеристики объекта проектирования. Ключевой проблемой оптимизации запросов к данным САПР СБИС является выбор оптимального порядка соединения отношений. При реализации особо сложных проектных решений СУБД сосредоточенной САПР, испытывая дефицит оперативной памяти, не имеет возможности использовать более эффективные однопроходные алгоритмы соединения со значительно меньшим числом операций обращения к жесткому диску. Вследствие чего возрастает время доступа к данным и время решения проектных задач. Для эффективной эксплуатации распределенных САПР необходимо использовать схемы соединения отношений, способствующие снижению сетевого трафика. В условиях функционирования современных САПР СБИС, существующие методы выбора оптимального порядка соединения отношений не обеспечивают получение качественного решения, это обуславливает необходимость разработки принципиально новых подходов.
В последнее время для решения сложных оптимизационных задач на практике успешно используются генетические алгоритмы, алгоритмы случайного поиска и автоматы адаптации. Их широкое применение обусловлено тем, что они имеют меньшую временную сложность и позволяют получать приемлемые для практики субоптимальные решения. В связи, с чем исследование и разработка генетических алгоритмов и механизмов адаптации для оптимизации доступа к проектным данным САПР СБИС является актуальной научной задачей представляющей практический интерес.
Развитие эволюционных подходов к решению оптимизационных задач в значительной мере определяется работами M.JL Цетлина, Л. Фогеля ( L.J. Fogel), Г. Шефеля (Н. Schwefel), Дж. Холланда (Holland John Н.) и др. Теоретические основы систем автоматизации проектирования СБИС получили развитие в работах К.К. Морозова, В.М. Курейчика, И.П. Норенкова и др. Большой вклад в
развитие теории и практики организации доступа к данным внесли С.Д. Кузнецов, Дэйт (С. 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 таблиц.
Во введении обоснована актуальность, определены цель и задачи диссертационной работы, основные положения, выносимые на защиту, приведены сведения об использовании результатов и краткое содержание основных разделов диссертации.
В первой главе проведен анализ процесса и средств автоматизации проектирования СБИС. Средства автоматизации проектирования СБИС анализировалось на примере подсистемы автоматизированного проектирования СБИС в составе САПР CADENCE - OrCAD 9.2. и платформы Galaxy компании Synopsys. На основании проведенного анализа установлено, что при современном уровне развития информационного обеспечения САПР, поиск решений ряда проектных задач, вследствие больших объемов обрабатываемой информации осуществляется в течении несколько часов. Показано что актуальным направлением развития информационного обеспечения САПР является совершенствование алгоритмов выбора оптимального порядка соединения отношений. Приведены формулировки задач выбора оптимального порядка соединения отношений расположенных на одном и на нескольких узлах распределенной САПР. Показаны недостатки существующих способов выбора оптимального порядка соединения отношений. Произведен обзор наиболее перспективных методов решения оптимизационных задач и стандартных подходов к построению СУБД.
Во второй главе математически сформулированы задачи выбора оптимального порядка соединения отношений расположенных на одном и на нескольких узлах распределенной САПР. Построены генетические алгоритмы решения поставленных задач на основе стандартных генетических операторов. Показано, что применение генетических алгоритмов на основе стандартных генетических операторов не является оправданным. По причине сложности построения пригодных генетических алгоритмов, на основе стандартных генетических операторов, для решения поставленных задач, были разработаны генетические алгоритмы на основе модифицированных генетически операторов. Было показано что применение модифицированных генетических алгоритмов, для решения поставленной задачи, целесообразнее в сравнении с генетическими алгоритмами построенными без учета знаний о специфики предметной области. Разработаны алгоритмы случайного поиска с линейной и нелинейной тактиками, а также с линейной тактикой и возвратами решающие задачу выбора оптимального порядка
соединения отношений расположенных на одном узле САПР. Приведен сравнительный анализ разработанных алгоритмов случайного поиска.
В третьей главе описана схема адаптивной оптимизации запросов которую предложили Кабра и Девит, используемая в ситуациях, когда есть основания предполагать что статистические характеристики БД не соответствуют фактическим. Данный подход предполагает чередование процессов выполнения, и оптимизации невыполненной части запроса. Для оптимизации запросов при помощи данной схемы построены генетический алгоритм и автоматы адаптации.
Алгоритм осуществляет поиск решения при помощи модифицированных генетических операторов. Разработаны два автомата адаптации осуществляющие поиск решения на основе разработанных во второй главе алгоритмов случайного поиска.
В четвертой главе приведены результаты экспериментальных исследований разработанных алгоритмов. Эксперименты проводились с целью определения сравнительной оценки вычислительной сложности разработанных алгоритмов.
В заключении представлены основные результаты и выводы диссертационной работы.
В приложении приведены акты об использовании результатов работы.
Обзор стандартных подходов организации доступа к данным САПР СБИС
Для организации информационного обеспечения, в том числе и обмена информацией между компонентами САПР, используются системы управления проектными данными. Основной компонент системы управления проектными данными - банк данных (БнД). Он состоит из системы управления базами данных и баз данных. При помощи БнД организуется межпрограммный интерфейс, который осуществляет информационный обмен при реализации заданного маршрута проектирования [3].
Реляционные системы управления базами данных.
Реляционный подход в настоящее время представляет наиболее развитую идеологию построения БД [6]. Пользователю данная структура представляется как набор связанных между собой таблиц [5].
Реляционный подход основывается на математической теории отношений. Термин "отношение" определяется в [5] следующим образом: даны множества DuD29...9Dn (не обязательно взаиморазличные), R является отношением на этих множествах, если имеется множество упорядоченных кортежей из п элементов {dl9d2t...tdu)9 таких, что с/,є/)(і = 1„л). Множества D19D29...,DB принято называть доменами. Таким образом, отношение R определяется как подмножество декартова произведения доменов: DlxD2x,..xDn [6]. Для получения информации из отношений Коддом были разработаны три абстрактных языка манипулирования данными [6]: - реляционная алгебра; - реляционное исчисление с переменными кортежами; - реляционное исчисление с переменными доменами; Реляционная алгебра выражает запросы при помощи специализированных операторов применяемых к отношениям. Поскольку отношения являются множествами то средства манипулирования отношениями могут основываться на теоретико-множественных операциях, дополненных некоторым набором операций специфичных для баз данных [4]. Каждая операция реляционной алгебры преобразует одно или несколько исходных отношений в новое отношение. В состав теоретико-множественных операций входят следующие операции [3]: объединения отношений; пересечения отношений; взятия разности отношений; прямого произведения;
Специальные реляционные операции [3]: ограничения отношения; проекция отношения; соединение отношений; деление отношений;
Результатом объединения двух отношений А и В (совместных по объединению) является отношение, которое содержит кортежи, принадлежащие либо А, либо В, либо им обоим [4].
Пересечением отношений А и В (совместных по объединению) называется множество кортежей (отношение), каждый из которых принадлежит и А и S.
Разностью между отношениями А и В (совместными по объединению) называется множество кортежей (отношение), каждый из которых принадлежит А и не принадлежит В.
Декартово произведение двух отношений А и В - это отношение С, состоящее из таких кортежей / что С является конкатенацией А и В (соединением каждого кортежа а принадлежащего Л с каждым кортежем b принадлежащими).
Обозначим любой оператор сравнения скалярных значений -9 9Ф И т. д. Тогда 0 селекцией отношения А по атрибутам X и Y называется множество кортежей t таких что истинен предикат tJCQtY. Вместо L Y может быть поставлена константа.
Операция проекции позволяет получать вертикальное" подмножество заданного отношения, которое содержит не все атрибуты, а только нужные.
Операцией О - соединения отношения А по атрибуту X с отношением В по атрибуту Y называется множество всех таких кортежей /, что / является конкатенацией какого либо кортежа а, принадлежащего А7 и какого-либо кортежа Ь, принадлежащего В, при этом должно выполнятся условие a.XQb.Y, Если в качестве 0 выступает оператор "= то операция называется эквисоединением.
Оставшиеся два языка производят селекцию предикатов и доменов по заданным критериям. По своей выразительности все три языка эквивалентны [6]. Рассмотрим преимущества и недостатки реляционного подхода[4Д8]: наличие простого и мощного математического аппарата (отсутствующего в объектно-ориентированных СУБД); возможность ненавигационного манипулирования данными, без учета физической организации БД во внешней памяти (в отличии от дореляционных СУБД); наличие небольшого набора абстракций, позволяющих достаточно просто моделировать большую часть предметных областей; Недостатки: недостаточная эффективность при описании сложных структур данных (в сравнении с объектно- реляционными); невозможность адекватного отображения семантики предметной области (в сравнении с объектно- реляционными);
Математическая формулировка задачи выбора оптимального порядка соединения отношений расположенных на нескольких узлах распределенной САПР СБИС
Ранее было показано, что оптимальное решение, задачи выбора порядка соединения отношений расположенных на нескольких узлах может соответствовать произвольному дереву соединения. В связи с более сложной структурой области определения, при кодировании решения необходимо описывать не только порядок следования отношений, но и структуру дерева характеризующего схему соединения отношений.
Обозначим множество вершин дерева соединения W = {wi,w2...wl}, выделим во множестве W, подмножество внутренних вершин WW, дерева соединения отношений (рис. 2.2). Каждой внутренней вершине w, соответствует, отношение, полученное в результате объединения отношений соответствующих двум дочерним вершинам wk и w}.
При соединении двух отношений расположенных на различных серверах БД, с целью минимизации трафика будем пересылать отношение, содержащее меньшее число строк, на сервер, хранящий большее отношение.
Тогда затраты на соединение отношений соответствующих вершинам wkuw, можно определить по формуле: ) = 5( )- (7-( ), ( )), (2.5) где: - r(Wj) количество кортежей в отношении соответствующем вершине W,, являющейся одной из двух дочерних вершин хл; - S(wt) количество кортежей которое необходимо переслать, чтобы путем соединения отношений соответствующих вершинам wk и W,, получить отношение соответствующее вершине Wj.
Вершине wi будет соответствовать отношение rjy полученное в результате соединения отношений гк и /} соответствующих вершинам WktfWj9 мощность которого ) = 0 ), по аналогии с [7] будет определяется как: т )- %?у ц, (2.6) где: T(wk) количество кортежей в отношении соответствующем вершине wk; - Z O Ow,) количество кортежей в отношении, являющемся результатом натурального соединения отношений соответствующих вершинам wkuw, ; - V(wktx) количество различных значений атрибутах, отношения соответствующего вершине wk ; - х,у- атрибуты отношений по которым производится соединение. Если имеется два общих атрибута соединения то : T(vM) туты v ! max(V(wk.x\\V(w[.y\))-max(V(wk.x2),V(wl.y2)) К } где: - T(wt) количество кортежей в отношении соответствующем вершине wk; - T(wk0wt) количество кортежей в отношении, являющемся результатом натурального соединения отношений соответствующих вершинам wtuwl ; - V(wk,x) количество различных значений атрибутах, отношения соответствующего вершине wk ; - xl, x2,yl,y2- атрибуты отношений по которым производится соединение.
В случае если соединяемые отношения не имеют общего атрибута, мощность результирующего отношения определяется как декартово произведение: П ) = ГК)-П"/) (2.8) Вслучаеесли Д ) Д)сг) и V{w,.x) T(wk)w формула (2.6) примет вид: тЩ) = . (2.9) так как V{w.x) T{wk) то к) , 1 вследствие чего будет справедливо V(wtx) неравенство: r(wjt0wf) r(wl), (2.10) В случае если к отношению wk7 применяется оператор выборки, с отбирающий кортежи отношения wk, по заданному условию и характеризующийся коэффициентом отбора &{щ) [7,12]. Справедливо условие [7]: К) КЧ) (2Л1)
Таким образом, на основе формул 2.8 - 2.11, а также на основании [7Д2] можно заключить, что в ряде случаев в результате соединения двух отношений может получиться отношение меньшей мощности, нежели исходные отношений.
Поскольку для получения итогового отношения необходимо, осуществить соединение всех вершин, необходимо определить величину S{wt) для каждой внутренней вершины дерева соединения. Тогда критерий оптимальности можно определить как; 5]5( )-мшп (2Л2) 2.3. Анализ целесообразности применения стандартных генетических операторов для построения генетических алгоритмов решающих поставленные задачи
К настоящему времени разработано большое количество генетических операторов (ГО), но параллельно с усложнением структур генетических алгоритмов (разработка новых ГО, принципов формирования стартовых популяций) развивается встречная тенденция направленная на создание упрощенных (как правило с минимальным набором ГО) ГА [24,27,28]. Чтобы получить представление о принципиальной возможности разработки ГА на основе стандартных ГО рассмотрим результаты применения ГА построенных на основе распространенных ГО. Необходимо произвести анализ как для локальной так и для распределенной задачи выбора оптимального порядка соединения отношений. В качестве эталонного решения, локальной задачи выбора оптимального порядка соединения отношений, использовалось решение полученное при помощи динамического программирования [7]. В качестве эталонного решения распределенной задачи выбора оптимального порядка соединения отношений, использовалось решение полученное при помощи эвристики согласно которой необходимо осуществить передачу всех отношений на узел содержащий наибольшее отношение [3].
Исследование стандартного способа формирования стартовой популяции.
Так же как процесс эволюции начинается с начальной популяции, так и алгоритм начинает свою работу с создания начального множества конкурирующих между собой решений оптимизационной задачи [28] . Известно, что генерация стартовой популяции является важнейшим этапом для последующей работы ГА, т.к. при получении "хороших" решений хромосомы находятся близко к точкам локального оптимума [25]. Универсальным методом построения стартовой популяции является случайное генерирование. Известно что на процесс формирования стартовой значительно популяции влияют два фактора: число особей стартовой популяции и общее число возможных решений [25].
Для оценки эффективности применения данного метода, при решении задачи выбора оптимального порядка соединения отношений расположенных на одном узле САПР, была произведена серия опытов, часть полученных результатов приведена в таблице 2.2.
Разработка автомата адаптации для решения поставленной задачи
При наличии адекватной модели объекта адаптации (в которой связаны параметры входной задачи X, решения У, состояние объекта S, адаптирующего воздействия U) для синтеза адаптирующего воздействия по параметрам X и алгоритму можно «вычислить» на модели необходимое адаптирующее воздействие U, которое должно перевести объект адаптации в требуемое состояние(максимум эффективности и выполнение заданных ограничений ) [48]. Представленная на рисунке 3.10 модель преобразует состояние среды X и адаптирующее воздействие U в состояние модели Ym.
Если математическая модель адекватна объекту адаптации т.е. Ym= Y то нет необходимости измерять состояние объекта [48]. Т.к. оптимизатору запросов известны статистические значения вектора входных задач X , которые не соответствуют фактическим можно утверждать что состояние ММ не будет соответствовать состоянию объекту адаптации. Таким образом периодически необходимо осуществлять корректировку Ym.
На рис. 3.11: S- состояние объекта адаптации, U-управляющее воздействие, А-выход АА, Q- формирование отклика среды. Вероятностный автомат адаптации определяется следующей пятеркой [19]: S(t+l) = 0(S(t),I(t+l)); A(t)=f(S(t)), где: - S(t) внутреннее состояние автомата в момент t; - I(t) отклик среды на сигнал поощрения или наказания; - Ф- функция перехода из состояния в состояние; - A(t) выход автомата в момент времени t; - f функция выхода;
В начале, случайным образом или по результатам работы какого либо алгоритма, реализуется начальная альтернатива. В последующем на каждом шаге (итерации) адаптивного алгоритма выполняется 4 такта [48]: - На первом такте рассчитываются параметры среды и ОА после реализации ранее выбранной альтернативы; - На втором этапе по параметрам оценивается состояние ОА в среде, на основании чего вырабатывается управляющий сигнал поощрения или наказания. - На третьем такте под действием управляющего сигнала АА переходит в новое состояние; - На четвертом такте реализуется альтернатива, соответствующая состоянию АА.
Первым этапом выполнения запроса адаптивной СУБД является генерация опорного плана выполнения запроса. В данном случае это будет некоторый план (порядок) соединения отношения. После того, как будет определен порядок соединения, начинается его выполнение. Особенностью работы адаптивной СУБД является чередование процессов оптимизации и выполнения запросов. После того как выполнена некоторая часть плана запроса можно сверить полученный промежуточный результат с запланированным. Если результаты не совпадают необходимо осуществить переоптимизацию невыполненной части.
Был реализован АА поддерживающий две альтернативы. Альтернатива А1-перед выполнением очередной части запроса необходимо осуществить переоптимизацию и альтернатива А2- выполнять план соединения полученный на предыдущем шаге. В общем виде каждой альтернативе может соответствовать некоторое число состояний (рис. 3.13.) . Граф- схема реализованного автомата адаптации приведена на рис. 3.14.
На первом этапе работы при помощи алгоритма случайного поиска определяется начальное решение a = {r0, rl7 r2i... /j,... ). Стоимость целевой функции полученного решения обозначим как Рг. Моделируется соединение первых двух отношений из а, после чего становятся известны их фактические характеристики. На основе уточненных характеристик осуществляется перерасчет целевой функции а. Определяется величина Рг оценка стоимости порядка соединения отношений на текущем шаге. В зависимости от текущего состояния \Рг-Р\
АА и заначения J , АА переходит в новое состояние на основе правил выработки управляющих сигналов (таблица 3.2). Если под действием управляющего сигнала АА, переходит в состояние соответствующее альтернативе А1, то осуществляется переоптимизация невыполненной части а, расчет величины Рг и осуществляется присоединение очередного отношения. таблице 33 приведено распределение результатов автомата адаптации построенного на основе алгоритма случайного поиска с линейной тактикой. В ксчестве эталонного использовалось решение полученное при помощи жадного алгоритма. Представленные в таблице 3.3 данные позволяют предположить что в большинстве случаев ЖА находит более предпочтительное решение.
В таблице 3.4 приведено распределение результатов автомата адаптации построенного на основе алгоритма случайного поиска с нелинейной тактикой относительно результатов получаемых при помощи жадного алгоритма. Представленные в таблице 3.4 данные позволяют предположить что АА построенный на основе алгоритма поиска с нелинейной тактикой позволяет определять более предпочтительные решения (в сравнении с ЖА) с вероятностью более 50%.В таблице 3,5 приведено распределение результатов автомата адаптации построенного на основе алгоритма случайного поиска с линейной тактикой и возвратами. В качестве эталонного использовалось решение полученное при помощи жадного алгоритма. Представленные в таблице 3,5 данные позволяют предположить что АА построенный на основе алгоритма поиска с линейной тактикой и возвратами позволяет определять более предпочтительные решения ( в сравнении с ЖА) с вероятностью более 0,5.
Определение вычислительной сложности алгоритмов для динамического программирования и жадного алгоритма
Объем информации используемой алгоритмом определяется как суммарный объем необходимый для размещения программной, исходной и промежуточной информации [21]. Объем исходного программного кода составляет 8.8 к/байт для генетического алгоритма и 11.6 к/байт для динамического программирования. Но с учетом того что эти величины в значительной мере зависят от языка программирования, методики программирования и некоторых второстепенных: факторов таких как наличие комментариев, длина имен переменных и т.д. примем допущение о том что объемы программной информации динамического программирования и генетического алгоритма совпадают. В качестве исходной информации используется файл заданной структуры. Выходом генетического алгоритма, после заданного числа итерации является особь, описывающая определенный порядок соединения отношений и обладающая наименьшей стоимостью. Выходом методики основанной на динамическом программировании является эквивалентная структура данных, полученная на соответствующей итерации. Промежуточная - это информация, полученная на этапе переработки входной информации в выходную. Поскольку тестируемые алгоритмы не подразумевают, какой либо специальной обработки выходной информации под сочетанием промежуточные данные будем понимать совокупность выходных и промежуточных данных.
В таблице 4.5.: N- размерность задачи, РО- вероятность определения оптимального решения, PLO- вероятность определения решения погрешность которого составляет не более 15%, Т - время заданного числа запусков генетического алгоритма, t - ВСА.
Результаты опытов позволяют говорить о том что: - для задач размерность которых не превышает 6, за время работы ДП, ГА находит оптимальное либо субоптималыюе решение с вероятностью 0Д0-0Д5 процентов; - для задач размерности 8, ГА находит оптимальное (субоптимальное) решение с вероятностью 0,55-0,60, вероятность получения решения отличающегося от оптимального не более чем на 15% составляет 0,7-0,80 случаев; - на задачах размерности 8-15 генетический алгоритм позволяет определять оптимальные решения с вероятностью 0,50-0,55, субоптимальные с вероятностью 0,7-0,8; - на задачах размерности 15-30 генетический алгоритм позволяет определять оптимальные решения с вероятностью 0,50-0,60, субоптимальные с вероятностью 0,7-0,5.
В таблице 4.6., частично приведены результаты экспериментов, проводимых с целью определения сравнительных оценок ВСА ГА, ЖА и ДП, В приведенной ниже таблице: АПНЛТ - ВСА алгоритма случайного поиска с нелинейной тактикой, РАГШТ - ВСА АА осуществляющего поиск при помощи алгоритма случайного поиска с линейной тактикой и возвратами, Р1 - вероятность определения алгоритмом случайного поиска с нелинейной тактикой, решения на 8-12% лучше, чем решение получаемое при помощи жадного алгоритма, Р2 -вероятность определения алгоритмом случайного поиска с линейной тактикой и возвратами решения на 8-12% лучше чем решение получаемое при помощи жадного алгоритма
На основании сравнения ВСА ГА и ДП а также анализа результатов работы ГА установлено что разработанный генетический алгоритм для решения задачи выбора оптимального порядка соединения отношений, расположенных на одном узле САПР, на основе статического подхода к оптимизации запросов позволяет определять оптимальные решения с вероятностью 0,5-ОД субоптимальные (отличающиеся от оптимального не более чем на 15%) с вероятнорстью 0,7-0,85. При этом на задачах, размерности (количество соединяемых отношений) 8 - І 5 экономия по времени составляет 15-20%, на задачах размерности 15 - 30, 25-30% по сравнению с методом динамического программирования.
На основании проведенных экспериментов установлено на малых размерностях задачи (N =6) целесообразнее применять динамическое программирование т.к. эта методика гарантирует нахождения оптимума и имеет приемлемую вычислительную сложность. Существенная экономия по времени (15-30 %) а также достаточно высокая вероятность определения субоптимального решения позволяют сделать заключение что на размерностях 8-30 целесообразнее использовать разработанный ГА в сравнении методом ДП.
При размерностях задачи более 6, на ряду с разработанным генетическим алгоритмом, также целесообразно использовать жадный алгоритм или алгоритм случайного поиска (по причине сравнительно низкой ВСА), Проведенный анализ показан что - разработанные алгоритмы случайного поиска для решения задачи выбора оптимального порядка соединения отношений, расположенных на одном узле САПР, осуществляющие поиск решения на основе статического подхода к оптимизации запросов позволяют определять приемлемые субоптимальные решения с вероятностью 0,4-0,5. Разработанные алгоритмы требуют на 20-30% больше времени по сравнению с жадным алгоритмом, но с вероятностью 0,7-0,9 гарантируют улучшение по качеству на 8-12%.
