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

□озоеесиз

На правах рукописи ВЕНЦОВ НИКОЛАЙ НИКОЛАЕВИЧ 7

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

Специальности (15 13 12 - системы автоматизации проектирования 05 13 17 - теоретические основы ипформат ики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Ростов-на-Дону - 2006

003068013

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

Научный руководитель

Научный консулы шгг

Официальные онпо! кн гы •

Ведущая организация:

заслуженны;'! деятель науки РФ.

доктор течннческик паук,

профессор Чернышев К) О.

доктор технических наук,

профессор Лебедев Ь К.

доктор технических наук, доцент 1ТИ ЮФУ Ьоженюк Л.В

кандидат технических пах к. доцент ДГТУ Остроух Е.П.

Ф1 У11 "ВНИИ Градиент".

Защита состоится 2.0 апреля 2007 с. в 14"" на заседании диссер1аниошюто совета Д 212.208.22 при федеральном государе] пенном образовательном учреждении высшего профессионального образования «Южный федеральный университет») по адресу: 347928,1. Таганро!. нер. Некрасовский. 44. а) д. Д-406.

С диссертацией можно ознакомиться в библиотеке 'I ечиологическон» института федерального государственного обрачовак'лынмо х чрежденин высшего профессионального образования «Южный федеральный универешет» в г. Таганроге.

Автореферат разослан) 2. марта 2007 I.

Ученый секретарь диссертационного совет а д-р техн. наук, проф.

Целых А.II

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

С.Д. Кузнецов. Дойт (С. J Date), 11.11. Чен (Chen P.P.), Д.Д. V.n.viaii (IJIIman J.l) ) Г. Гарсиа- Молима, (Garsia-Molitia Л.) и др.

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

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

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

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

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

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

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

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

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

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

расположенных на одном узле САПР СБИС, соответственно, на основе статического и адаптивного подхода к оптимизации запросов.

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

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

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

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

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

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

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

Реализация результатов работы. Полученные результаты использованы при выполнении фундаментальных госбюджетных научно-исследовательских работ Рос товской-на-Дону государа венной академии сельскохозяйственного чашиноа роения (РГАСХМ) на кафедре "Прикладная математика и вычисли 1ельная техника" но заказу Минобрнауки РФ по теме "Теория интсллек1уальных процедур поиска оптимальных решений'' (01.01.2005 г.-

31 12.2005 г.) и "Развитие leopnn канальной трассировки на псионе эволюционного моделирования" (01.(II.2006 i - 31.12.2006 г) Кроме тою. результаты выполненных работ внедрены и использукпея в учебном процессе к РГАСХМ при чтении лекций и проведении практических злняти но дисциплинам "Дискретная матемаписа" и "Профаммные средава САШ'" Разработанные i енетическис алюритмы использовались и Ф1УП Научно-исследовательский инсти [vi специальных информационно -измери тельных cucicM (1. Ростов- па- Дону)

Апробация работы и публикации. Основные научные и праюическле результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях "Интеллектуальные системы"" (AIS-05, 06) и "Ишеллектуальные САПР"' (l'AI)-2005, 20061 (г. Геленджик, 2005. 2006 гг.,), "Компьютерные и вычисли пмьпые icxho.ioiии в задачах естествознания и образования" (г. Пета, 2005 i,). Всероссийской научно-практической конференции "Транспорт- 2006" (г. Росюн- на- Дону 2006г.). Материалы диссертационной работы вошли и два отчета по НИР "Теория интеллектуальных процедур поиска ошимальных решений" № I Р 012.00.50.55.01 и "Развитие теории канальной трассировки на основе жолюционпою моделирования" № ГР 012 00.60.42.68.

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

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

Во введении обоснована актуальность, определены цель и задачи диссертационной работы, основные положения, выносимые на заши1\ приведены сведения об использовании результатов и кражое содержание основных разделов диссертации.

В первой 1ла»е приведен анализ процесса и средств авючатизацни проек!ирования. Средства автоматизации проектирования СЫК

анали ¡ировалось на примере подсистемы автоматизированного проектирования ("БИС в составе САПР CADENCE - OrCAD 9.2 и платформы Galaxy компании Synopsys. На основании проведенного анали м установлено, что при современном уровне развития информационного обеспечения САПР, поиск решений ряда проектных задач, вследствие большие объемов обрабатываемой информации осуществляется в течении несколько часов. Показано что актуальным направлением ратишя информационного обеспечения САПР является совершенствование алгоритмов выбора оптимально!о порядка соединения отношений. Приведены формулировки задач выбора оптимального порядка соединения отношений расположенных на одном и па нескольких узлах распределенной САПР.

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

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

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

Задача выбора оптимального порядка соединения отношений, расположенных на одном узле, формулируется следующим oôpatovi Имеется множество отношений ,г„, }. Мощность отношения, полеченною в

результате соединения двух отношений имеющих общий трибу!

соединения, определяется по формуле:

Т(г )- Г(г )

7'(г0/\)-=------!---........i./t 0.1. »,...«- I!

' ' гпах(Г(г,.*1),Г(г..у1))

при наличии двух афибушв соединения:

/'(г )■/'{г, )

Т(г0г )---------------------------------. (./€{0.1,2..,« 1}

' max(l- irl.x\)A'(rl ,vl))-max(K(r, ^î).V[rry2))

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

Г(/,<У,)-= /'(/;!• 7'<г,) /, / л {0 1.2. .// I'.

|де T(rL)~ количество кортежей в отношении г: /'(гОг) - количестве'кортежей в отношении, являющемся результагом соединения отношений >; и /'(/,-г) -количество различных значений атриб) ia.x отношения;- : - v/, x2,yl,}2- афибуп.1 отношений по которым производится соединение.

Необходимо найги такой порядок соединения отношений {>;,./,,/-, .>;. t„, ). чтобы суммарная мощность промежуючных отношений была минимальной.

Другими словами, требуется соединить oiношения {»<„r,,r, .<,, ] н гаком порядке, чтобы выполнялось условие*

"lin,

1 де RM*г{%г{ЧгН 0г{' 1 .

Показано, чю абсолют нос омслонение реи1сний, полученных при помощи жадною ашоритма, может быть весьма значительным (60 - 100 %), и мс зависш от размерности задачи.

Для решения там и выбора оптимального порядка соединения отношений, расположенных на одном узле САПР на основе статического подхода к оптимизации запросов разработаны генетический алгоритм (ГА) и алгоритмы случайною поиска Алгоритмы работаю! с решением, представленным в виде кор1ежа содержащего идентификаторы соединяемых отношений. Установлено, чю генетические алгоритмы, построенные на основе стандартных генетических операторов, обеспечиваю! досшточно низкую вероятность нахождения как оптимальных (0,01-0,02), так и субонтпмштьных (0,02-0,03) решений,

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

Рис. 1. Структурная схема генетического алгоритма: ОМ - оператор мутации; ОК - оператор кросеинговера; 08 - оператор селекции

На первом mate алгоритмом генерируется сшрювач поп\ляция при ее формировании, вероятность получения субоптималыюю решения .locmiaei 0,15. Особи стартовой популяции ратбиваюгея на четыре группы кршерием разбиения является -значение целевой функции. В группах применяются специфические модифицированные операторы кроесишовера ч Myiannn Алгоритм позволяет определять отимальные решения с вероятностью не менее 0,5-0,6 субонтималыше решения (отличающиеся oi оптимальною не более чем на 15%) с вероятностью 0,7-0.85.

На основе предложенных операторов случайною шаит разработаны адюртпм елучайн01'0 поиска с нелинейной тактикой и релаксационный алгоритм случайною поиска с линейной таки-ткой. Начальная алыерпатива определяется алп "итмами при помощи процедуры формирования аартоаой популяции, разработанного генетическою алюритма. Разработанные алгоритмы случайною поиска позволяют определять приемлемые субоптимальные решения с вероятностью 0,4-0,5.

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

Пусть W = {w„us, .и,} множество вершин дерева соединения отношений Каждой внутренней вершине v, соответствует отношение, полеченное в результате объединения отношений, соответствующих двум (очерним вершинам я,7лг(. Тотда затраты на соединение отношений соотвеiств\юши\ вершинам я', им) можно опретелить по формуле'

S( и',) -- Л'т, 0w,) = min( '/'(if,, >. 'Г(w,)),

где 7'(ir,) - количество кортежей в отношении, соответствующем вершине и являющейся одной из двух дочерних вершин И',:б'(и,) ~ количество кортежей которое необходимо переслать, чтобы посредством соединения отношений соответствующих вершинам it, и ic,, получить отношение, соответствующее вершине w(.

Мощность отношения г,, соответствующего вершине w,, полученного в результате соединения отношений rt и гп соответствующих вершинам «tu\<>,, определяется но формуле:

Пг^Пг.Ц).

Выделим во множестве IV подмножество внутренних вершин WIV. Для получения итогового отношения необходимо, осуществить соединение всех вершин и определить величину i'(ic,) для каждой внутренней вершины дерева соединения. Тогда критерий оптимальности можно определить как

—> min.

»,»II1Г

Для решения задачи разработан генетический алгоритм. Решение кодируется особью alt-- (ll\J!2). состоящей из двух хромосом. Хромосома Hl содержит информацию о порядке следования листьев дерева соединения, ее структура идентична хромосоме, используемой в разработанном ранее генетическом алгоритме. Хромосома /72 содержит закодированную при помощи польской записи ефуктуру дерева. К каждой хромосоме применяются специфические (снетичеекие операторы. Показано чго предложенный 1 Л позволяет определять более приемлемые решение, по сравнению со стандартным методом пересылки отношений паодим узел, с вероятностью не менее 0,15-0,2. в среднем улучшение но качеет ву составляет 5-8%.

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

■запроса, и мобильные, описывающие предполагаемый порядок дальнейшею соединения отношений. Разработанные генетические операторы нрименякмея только к мобильным генам. Алгоритм определяет ошимальное (либо отличающиеся от оптимального не более чем на 15%) решение с вероя гноеп.ю 0.6-0,8.

Для принятия решения о выполнении или персопти.мизации имеющеюся порядка соединения 01 ношений разработанные автоматы адаптации. использую! две альтернативы: А1- перед выполнением очередной части запроса необходимо осуществить переоптимизацию и альтернатива А2- выполнять план соединения, полученный ранее (рис. 2). Разработанные автоматы ачашации для поиска решения используют алгоритм случайного поиска с нелинейной тактикой и релаксационный алгоритм случайного поиска с линейной такт икон

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

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

Предсзавленные в работе алгоритмы реализованы в интегрированной среде разработки Borland Delphi 7.0 под операционные Windows 9*. NT. 2000, ХР. Эксперименты проводились на компьютере семейства PC1 с процессором Iniel Celeron 2.5 Ghz и оперативной памятью 512 Mb.

AI

Рис. 2. Граф-схема предлагаемых автоматов адаптации

[la основании проведенных эксперимента установлено:

- разработанный генетический алгоритм для решения задачи выбора оптимального порядка соединения отношений, расположенных на одном у з те СЛ11Р, на основе статического подхода к оптимизации запросов позволяет определи ib оптимальные решения с вероятностью 0,5-0,6, еубоптимальные (отличающиеся от оптимального не более чем на 15%) с верояпюреп.ю 0.7-0,85. При этом на задачах, ра ¡мерности (количество соединяемых отношений) 8-15 экономии по времени составляет 15-20%, на задачах размерности 15 -30,25-30% но сравнению с меголом динамического программирования.

- разработанные алгоритмы случайного поиска для решения задачи выбора оптимального порядка соединения отношений, расположенных на одном узле САПР, осуществляющие поиск решения на основе статического подхода к оптимизации запросов позволяют определять приемлемые еубоптимальные решения с вероятностью 0.4-05. Разработанные алгоритмы требуют на 20-30% больше времени но сравнению с жадным алгоритмом, но с вероятностью 0,7-0,9 i аран тирую i улучшение по качеству на 8-12% .

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

В заключении представлены основные результаты подученные в диесер|анионной работе.

В приложении приведены акты об использовании результатов дисеерг ai ihohi ю й работы.

ЗАКЛЮЧЕНИЕ

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

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

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

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

Публикации по теме диссертационной работы

1. Венцов H.H. Разработка и исследование простого генетического алгоритма выбора оптимального порядка соединения 0гношений // Компьютерные и вычислительные технологии в задачах естествознания и образования: сб. материалов международной науч.- техн. конф. - Пенза: РЖ) ПГСХА, 2005. С. 35-38.

2. Венцов H.H. Разработка и сравнительная оценка генетического алгоритма выбора оптимального порядка соединения отношений: Тр. междунар. науч,-техн. конф. "'Ингеллектуальные системы" (AIS'<)5) и "Интеллектуальные САПР" (CAD - 2005). Науч. изд. в 4 т. - М: Физматлит, 2005. - T. I. - С. 30-3 4.

3. Венцов H.H. Разработка теоретической модели автомата адаптации для решения задачи выбора оптимального порядка соединения отношений //Безопасность жизнедеятельности. Охрана труда и окружающей среды: Межвуз. сб. науч. тр. Вып. 9/ Рост. гос. акад. с. -х. машиностроения, Ростов н/Д. -'005. -С. 161-163.

4. Венцов H.H. Оценка влияния параметров простого генетическою алгоритма решающего задачу выбора оптимального порядка соединения отношений на его сходимость' Тр. междунар. иауч.-техн. конф. "Интеллектуальные системы" (AlS'06) и "Интеллектуальные САПР" (CAD- 2006). Науч. изд. в 3 т. - М.: Физматлп т, 2006. - Т.2. С. 519-520.

5. Венцов H.H. Анализ результатов работы адаптивного генетического алгори тма // Изв ТРТУ. Темат. вып. "Интеллектуальные САПР". - Таганрог: Изд-во TP ГУ.- 2006. - № 8(63). С. 286-287.

6. Венцов H.H. Анализ результатов применения стандартных операторов мутации к начальному решению задачи выбора оптимального порядка соединения отношений: Гр. Веерос. науч.-практ. конф. "Транспорт-2006", май 2006 г. в 3 ч. Ч. 3 / Рост, гос ун-т. зтутей сообщения. Ростов н/Д, 2006. С. 202-203.

7. Чернышев Ю.О. Венцов H.H. Анализ результатов работы ¡енешческою алгоритма решения задачи выбора оптимального порядка соединения отношений: Материалы XXX1IL мсждуиар. конф. и IV междунар. конф. молодых учен. "Информационные технологии в науке, образовании, телекоммуникации и бизнесе'(ГГ + S&E"06), Украина, Крым, Ялта-Гурзуф, 20-30 мая 2006 i.- С. 7172.

8. Венцов H.H. Анализ точности адаптивного диетического алюригма //И tu вузов. Сев.-Кавк. регион. Приложение. - 2006. - jY» 7. - С. 17-19

9. Венцов H.H. 1'азработка адаптивною 1енетическо1Х> ¡ипоритма решающею задачу выбора оптимального порядка соединения отношений: Гр. X межву! науч.-техн. конф. "Повышение эффективное i и и падежноаи авиационны\ комплексов и систем"/ СВВАИУ, Ставрополь, 2006,- С. 182-185 (в печати)

В совместно опубликованной работе [7], личный вклад автора заключается в разработке и программной реализации генетическою алгоритма.

Подписано в печать 02.03.2.007г. Бумага офсетная Объем 0,93 усл. п. л. Заказ Шйб/ОТ

Форма) 60x84/16 11счать типографская 0,61 уч.-изд.л. Тираж 120 жз

Оглавление.

ВВЕДЕНИЕ.

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%.

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