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

РГ6 ОД

ТЛГАШ'ГП СйШИ ПОаУДАРСТВЕННЫИ РАДИОТЕХНИЧЕСКИИ ° УНИВЕРСИТЕТ

На правах рукописи

Файзуллин Лльфир Зарифьянович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ-ГЕНЕТИЧЕСКИХ МЕТОДОВ РАЗМЕЩЕНИЯ ДВУМЕРНЫХ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ

Специальность: 05.13.12 — системы автоматизации проектирования

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

Таганрог - 1996

Г .

Работа выполнена на кафедре САПР Таганрогского Государственного радиотехнического университета

Научный руководитель — академик АЕН РФ и МАИ, доктор технических наук, профессор Курбйчик В.М.

Официальные оппоненты — 'д.т.н., профессор Чернышев Ю.О., к.т.н., Тищенко В.А.

Ведущее предприятие —НИЦ ЭВТ (г. Москва)

Защита состоится 1936 г. п 14 часов на

заседании диссертационного совета Д (ИЗ. 13.12 по защите диссертаций при Таганрогском Государственном радиотехническом университете но адресу: 347928, г. Таганрог, пер. Некрасовский 44, ауд. Д—406.

С диссертацией можно ознакомиться^библиотеке университета.

Автореферат разослан " Т~" ¡^АПТУОкЦ 1996 г.

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

V

А.Н. Целых

ВВЕДЕНИЕ

Системы автоматизации проектирования (САПР) являются важным гструменгом развития научно-технического прогресса в электронной ¡скышипюсга и приборостроении. Сфера проектирования изделий ектронной промышленности включает в себя ряд задач: ко.миоповка диоэлемеотоп, размещение элементов, трассировка печатных плат и т.п. дачи размещения геометрических объектов, известные как .'задачи змещення элементов на печатной плате, планирования кристалла, гамновки заготовок и т.п. имеют важные практические приложения.

Поскольку задача размещения является ИР — полной, то разработать иверсалышй алгоритм размещения, который позволяет находить точно;' птималькое) решение за разумное время, невозможно. В этом случае врабатываются алгоритмы размещения, предназначенные для поиска боптимальных решений. Внедрение новых технологий обработхи ¡чатных плат, полупроводниковых материалов, использование в качестве фья дорогостоящих материалов предъявляют все более жесткие ебопания к качеству субоптнмальных размещений.

Таким образом, задача размещения двумерных геометрических гьектов произвольной формы (РДГО ПФ) была и остается АКТУАЛЬНОЙ РОБЛЕМОЙ ресурсосбережения, стоящей перед разработчиками САПР.

ЦЕЛЬЮ диссертационной- работы является разработка и следование генетического метода размещения двумерных ометрическигх объектов произвольной формы, позаоляющего повысить ;фоктншюсть решения задачи размещения я САПР.

Для достижения [.оставленной цели были решены следующие дачи:

! ) разработана новая методика описания объектов;

2) разработана структурная схема процесса размещения, >зволяющая генерировать, модифицировать и использовать знания о ойствах объектов;

3) разработаны компоненты процесса размещения, а) процедуры тановки объектов в ограниченную область; б) процедуры выявления ласти пересечения; в) процедуры оценки размещения объектов;

4) построен генетический алгоритм размещения на основе ализа механизма эволюции;

5) разработаны проблемно — зависимые модули генетического горитма (структура и кодирование хромосомы, функция пригодности);

6) исследован генетический алгоритм размещения двумерных ометрических объектов произвольной формы.

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на пользовании элементов теории множеств, элементов теории алгоритмов, ембнтов теории статистических вычислений. .

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в едующем;

- а) создан векторный , >|етод описания объектов для !шеция задачи размещения, который позволяет повысить

качество- (прецизионность) размещения за счет векторного представление объектов;

б) разработана стратегия "магнита" для установки объектов которая позволяет сократить сроки проектирования за счет исключени) неперспективного множества установок объекта в ограниченную область;

и) разработана эвристическая йроцедура проверки пересеченю двух геометрических объектов на плоскости, которая позволяет сократит] сроки проектирования за счет внедрения элемегггов искусственное интеллекте! в механизм размещения;

г) реализована идея накопления знаний, которая позволяв-сократить сроки проектирования за счёт гибкого подхода к генерации модификации и использованию знаний.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

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

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

— программа регрессионного анализа по методу Чебышева.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические V

практические результаты диссертационной работы использованы I госбюДжетных работах "Разработка теории и методов построение интегрированных САПР БИС с элементами искусственного интеллекта' ' (№. ГР 01.9.50004188), "Разработка методов и моделей генетического поиске в интеллектуальных САПР", выполненной в рамках государственной научно—технической программы "Университеты России" (1995—1996гг.) "Разработка учебно—методочес^их кйиядексов по изучение перспективных информационных технологий" межвузовской научно-технической программы ГОСКОМВУЗА РФ (1995г.). Результаты работы внедрены в НИИ МВС в качестве ПО САПР размещения. Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ-при чтении лекций и в цикле лабораторных работ по курсу "Методы генетического поиска".

АПРОБАЦИЯ основных теоретических и практических^ результатов работы проводилась на научных семинарах ^Генетические алгоритмы" (осень 1994—весна 1995 гг. ТРТУ), Всероссийской научно—технической конференции ' студентов и аспирантов "Новые информационные технологии. Информационное, программное и аппаратное обеспечение' (г.Таганрог 1995 г.), Всероссийской научно—технической конференции с участием зарубежных представителей "Интеллектуальные САПР" (г.Геленджик 1995г.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 4-х печатных работах.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 161 стр., включая 27 рис., 14 табл., список литературы из 67 наименований, 5 стр. приложений и актов. об использовании. •

СОДЕРЖАНИЕ РАБОТЫ

ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной |боты, поставлена цель работы, дано общее описание, выполненной

- ' I *

В ПЕРВОЙ ГЛАВЕ приведена классификация подходов к решению Р —полных задач САПР. Определена перспективная с( точки зрения и'анизации перебора область исследований, Рассмотрены существующие . горитмы решения задачи размещения, которые относятся к рспективному подходу. Выявлены недостатки и достоинства этих горитмов. Отмечены свойства, которыми необходимо наделить зрабатываемый алгоритм размещения.

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

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

Для разработки эффективного алгоритма размещения и выбора зоного метода оптимизации выявлены достоинства и недостатки шествующих алгоритмов размещения. - ,

Достоинством метода ссужающихся окрестностей является то, что ■ьект устанавливается в ограниченную область в соответствии со-. аниямН о ранее" размещенных объектах. Метод сужяющйхся рёстностей и моделирование отжига обладают следующими, достатками: . ■ ,

1) описание объектов базируется на , прямоугольной системе ординат,' что приводит к снижению быстродействия и точности змещения; • ~ ,

2) не используются свойства Достигнутых субоптимальных . тений, в результате чего снижается быстродействие.

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

Для . разработанного алгоритма в качестве базового метода тимизяции нспользовай генетический алгоритм, который обладает, ханизмом случайно—направленного--перебора множества решений. В нтексте задачи размещения * разработаны } проблемно—зависимые мпоненты . ГА. В алгоритме генетического поиска реализованы здующие положительные качества:

1) использование знаний о свойствах объектов, для исключения корректных решений и сокращения сроков п роектирования;

2) векторное описание .объектов для повышения быстродействш и точности размещения.

ВО ВТОРОЙ ГЛАВЕ приведена, формулировка задачи размещения которая необходима для достижения основной цели работы. На осиош. приведенной формулировки задачи размещения и отмеченнъп положительных качеств алгоритмов — аналогов разработана структурна* схема поиска субоптимального размещения. Определены компонента схемы: интерфейс; процедура установки двумерного • объекта i ограниченную двумерную область; процедура выявления пересечения дву> объектов; процедура оценки размещения; механизм оптимизационногс поиска. Разработаны интерфейс и комплекс процедур. Для этих компонент разработаны оценки пространственной "и временной сложности. Показан^ полиномиальный характер тих оценок, свидетельствующий о практической ценности новых разработок.

Задача размещения формулируется следующим образом.

Дано : а) некоторое множество Мп двумерных, объектов произвольной формы (где "п"~-количество элементов, п=1, 2, ..., N); б) двумерная геометрическая фигура F (в большинстве случаез — прямоуг ольник с заданной шириной W, и произвольной длиной L).

Необходимо найти такое расположение множества Мп , объектов внутри" ограниченного пространства F, при котором выполняются следующие условия: 1) объекты Oj и Oj" (Oj.Oj е Мд; i,j = l,2,...,n) ne

к

пересекают друг друга; 2) величина SS = S ¡г - £ $(% (где Sp — площадь

Ы

фигуры F, Sqî-площадь i — го объекта), является минимальной.

Если фигура F является прямоугольником с фиксированной шириной W, то целевая функция определяется следующим' образом:

L. = f(Mn) -> Lmbl, . , : . •

где L — длина прямоугольника,' которая зависит от параметров размещаемых объектов. Величина L должна стремиться к минимуму Lrajn.

Общая структурная схема поиска субоптималыюго размещения представлена на рис.1. В начале работы пользователь вводит информацию об размещаемых объектах Мп. Эти данные поступают на вход интерфейса, который преобразует их в массивы данных, описывающих объекты.

МЕТОДИКА ОПИСАНИЯ ДВУМЕРНЫХ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ 'ПРОИЗВОЛЬНОЙ ФОРМЫ зависит от стратегии установки объекта в ограниченную область.?. В данной работе предлагается новая стратегия установки, назовем ее стратегией "магнита". Согласно этой стратегии:

/

Г

вводдлнных —

к Л11 игм/иИО

ЗНАНИЯ О

СВОЙСТВАХ .<1 1

ОБЪЕКТОВ

ПРОЦЕДУРА УСТАНОВКИ ОБЪЕКТА

3:

ПРОЦЕДУРА ВЫЯВЛЕНИЯ ПЕРЕСЕЧЕНИЙ

ПРОЦЕДУРА .ОЦЕНкИ РЕШЕНИЯ

ГЕНЕРАТОР ЗНАНИЙ

Ж.

МЕХАНИЗМ ОПТИМИЗАЦИИ

АЛГОРИТМ ОПТИМИЗАЦИИ

СУБОПТИМАЛЬНОЕ РАЗМЕЩЕНИЕ

Рис.1. Структурная схема процесса поиска субоптимальйого размещения

1) выбираются два объекта — устанавливаемый С>2 и становленншй О1;

2) ■ для каждого объекта выбирается базовая- точка — точка на эанице объекта, относительно которой описывается объект;

3) объект С>2 устанавливается в области И таким образом, чтобы го базовая точка совпала на плоскости с базовой точкой объекта О}.

Для принятой стратегии установки объекта — стратегии "магнита", азработана методика описания двумерных объектов произвольной юрмы, которая представляет собой совокупность следующих положений:

1) двумерный объект О задается замкнутой цепочкой отрезков,

бразующих границу: 0 = С, С={Х], Х2, ..., Х^..... Хц>, где С —' граница

бъекта О; Х^ .— отрезок границы С; Н — количество отрезков;

2) объект в описывается относительно базовой точки Сц;

, 3) базовой, точкой является одна из двух точек, ограничивающих азовый отрезок Хд (Хд е С, В = 3,2.....Н);

4) каждый отрезбк Х^ множества в, задается двумя точками :Ь = |С„. Сы-,1;

5) каждая точка С^ описывается относительно базовой точки Сд трезка Хв тремя параметрами: а) расстоянием А^ между базовой очкой С в и точкой О,; б) углом . а^, образуемым двумя • лучами, сходящими из базовой точки Сд, первый из которых находится на рямой проходящей через "базовый" отрезок Хв, а второй — на прямой.

проходящей через точки С в и С^; в) фактором разграничена относительно прямой, проходящей через базовый отрезок Х&.

Недостатком разработанного метода является избыточности ,. тих описывающих объект. '

К достоинствам данного метода можно отнести:

1) независимость данных, описывающих объект, от установи этого объекта относительно других. Это позволяет сократить срои проектирования за счет исключения дополнительных расчето) необходимых для согласования объектов;

2) модификация и реализация , векторного метода описания который позволяет улучшить качество (прецизионность) размещения;

Асимптотическая пространственная сложность алгоритм;

я

составляет величину порядка 0(к*( ), где к — константа; п -... 1-/

количество размещаемых объектов; с; —. количество прямолинейны? отрезков 1 — го объекта.

Приведенная оценка ПСА показывает, что необходимые для работь алгоритма данные занимают в ОЗУ полиномиальную (квадратичную память в зависимости от размера входа. •

ПРОЦЕДУРА УСТАНОВКИ предназначена для последовательногс объединения объектов в соответствии с рассмотренной выще страте-и« "магнита". Первый объект фиксируется внутри фигуры Р на таком участке ее границы, который не подвергается растяжению. Назовем его "дном' фигуры. Разработанная процедура установки состоит из следутощю действий: ' ■

1) выбрать из множества Мп первый объектО^

2) установить объект на "дне" фигуры И;

3) .включить О1 во множество' Р объединенных объектов;

4) выбрать из множества Р опорный объект О^;

5) выбрать из множества С; базовый отрезок X;

6) выбрать из множества Мп устанавливаемый объект О^

7) выбрать из множества Gj базовый отрезок У;

8) выбрать вариант установки объекта Oj относительно О). '

9) выполнить процедуру выявления пересечений между О^ и ' объединением объектов Р, а также между О^ и границей фигуры И; .

10) если пересечения существуют, то необходимо отменить заданный вариант установки и перейти к выполнению пункта 4, 5, 6;

11) в противном случае включить объект О^ во множество Р • объединенных объектов; ,

12) записать идентификатор корректной установки в знания о свойствах объектов;

13) выполнить процедуру оценки частичного решения.

14) проверить, исчерпано ли множество Мп;

15) если нет, то перейти к выполнению пункта №4;

16). в противном случае передать оценку полученного размещения на вход механизма оптимизации.

Асимптотическая ВСА п . худшем случае не превышает величии где к — константа; п. — количество размещаемых объектов;

/-/

- количество прямолинейных отрезков ¡ — го объекта.

Временная сложность в лучшем случае равна: 0(к*п).

Временная сложность процедуры является полиномиальной, а пень полшюма изменяется от 1-до 2.

ПРОЦЕДУРА ВЫЯВЛЕНИЯ ПЕРЕСЕЧЕНИЙ предназначена для мружения пересечений между двумя произвольными объектами О] и при заданной ориентации этик объектов относительно друг друга.

На вход процедуры поступают Данные, описывающие:

1) множество отрезков границы объекта О} — С) = {X], Х2, ... , , ... , Х[-)} и множество отрезков границы объекта О2 — С2= {V] ... , , ... , У у} , где Н (V) — количество отрезков, образующих границу ¿.екта О] (О2). . ч

2) идентификатор установки объекта О2 относительно О!-

Выявление пересечения двух произвольных объектов О^ и О2

'Дится к поиску двух отрезков Хь и Уу, которые принадлежат границам ,ектов О1 и 02 соответственно и пересекают друг друга.

Процедура выявления пересечений работает следующим образом:

1) из множества С^ выбирается отрезок X},;

2) из множества С2 выбирается отрезок Уу;

3) выполняется процедура проверки пересечения между X}! и Уу;

4) если пересечение есть, то выполнение процедуры завершается ыходная переменная принимает значение "пересечение есть";

5) для множества Сч осуществляется проверка равенства '\<У?", исчерпано ли множество С2',

6) если нет, та из С2 выбирается следующий отрезок Уу после о управление передается в пункт "3";

7) для множества в! осу ще ствл я етс я проверка равенства "Ь<Н?", исчерпано ли множество С); •

8) если нет, то из С] выбирается следующий отрезок Х^ после о управление передается в пункт "2";

9) выходная переменная пригашает значение "пересечение нет";

10) выполнение процедуры завершается. •

Ключевым и самым трудоемким в этой процедуре является пункт №

Эвристическая процедура проверки пересечения двух отрезков гцествляется в три этапа (рис.2):

а) если флаги разграничения отрезков совпадают, то отрезки4' не есекаются (рис.2.а), в противном случае выполняется второй этап верки (рис.2.б);

б) если угловые сектора отрезков не пересекаются, то отрезки не, есекаются (рис.2.в), в 'противном случае выполняется третий этап верки (рис.2.г);

в) третий этап проверки пересечений состоит из следующих ствий (рис.Хд):

1) определение углов а, р, ф1 на основе входных данных;

РГУ) == о

„ Базовая

точка

ррс)=о

а) пересечений нет (этап №1)'

Базовая точка

в) пересечений нет (этап №2)

X

Р(Х)=0

б) выполнить этап №2 • (этап №1)

г) выполнить Э'Лш №3 (этап №2)

д) пересечение есть (этап №3)

Рис.2. Выявление пересечения двух отрезков

определение угла Ф2 по фррмуле: ыпО«)3-^)

2)

92 = <*гс'£\

¿у/Ьх +соа(\Ш-<р1),

(град.],

и угла фз на основе ф! и <Р2

3) если угол а меньше угла (рз, то выполнение пунктов №№ 4,5 в противном случае — пунктов №№ 6,7;

4) если угол р. меньше угла <Р2> то отрезки пересекаются;

5) в противном случае — не пересекаются;

6) если угол Р больше угла <рг> то отрезки пересекаются;

7) в противном случае — не пересекаются;

8) завершение процедуры.

ИСПОЛЬЗОВАНИЕ ЗНАНИЙ о ранее размещенных объектах исключает появление некорректных решений (пересечение объектов). Е разработанном алгоритме применена идея использования знаний с сопряжении объектов для установки объектов внутри ограниченного пространства Б. Для этого была решена проблема формализации знаний.

Варианты установки двух объектов мшуг быть определены у представлены в списке. Аналогично можно определить список варианте» корректной установки трех и более объектов, но современное развита« вычислительной техники не позволяет выполнить нео(5ходикые расчеты 3«

¡илемое время. В разработанном алгоритме' знания о сопряжении кто в представляют собой список вариантой корректной установки объектов. На этапе оптимизации для установки 1,2,3 — го объектов лъзуются знания о сопряжении объектов. Для установки четвертого го и т.д. объектов информация о корректных сопряжен., ^вливаемых объектов синтезируется 'редкого списка ./.и рируется процедурой выявления пересечений.

Выявление знаний о сопряжении заданных объектов и запись ий в базу данных позволяет сократил, сроки проектирования са счет льзовапия выявленных ранее; знаний. Например, в базо данных осп, зрмация (И= {Л,В,С,...}) 'о сопряжении множества объехтов (а.Ь.с,-..). 'стим, что объект Ь был нзкенен (Ъ — >!У). В этом случае достаточно итать варианты сопряжения с измененным объектом (В'), а остальные анты позаимствовать из знаний {А,В,С,...}, т.е. получаем

Основной недостаток идеи накопления знаний используемый » эитме размещении заключается в полном расчете карнантез совки, что.вед,от к увеличению времени 1 проектирования и по всегда кт быть оправдано. -

Достоинством применения этой идея является сокращение сроков ктирозалия за счет повторного использований знаний или их [фнхагцш.

ПРОЦЕДУРА ОЦЕНКИ частичного решения предназначена для эта целевой функции решения. Целевая функция пролстапля^т собой гэяние от "дна" фигуры Н до максимально удаленной точки •«»пленного объекта. На .плод . этой процедуры поступает •ядоченный список вида: Ьщ.^х, <0, 0,,У.зЛ'й>, где

1гп.гх ~ максимально удалённая '¡очка объединенного Од}, где О^ — установленные объекты;

<Oj.Oj.XB.YB> — идентификатор установи: объекта О] сителъно объекта О;;

©¡¡О]) ~ идентификатор опорного (устанавливаемого) объекта; ), ] = 0,1, 2, ..., п; 1 ф ]; (в качестве объекта Од выступает дно ■ртл Г, на которое устанаашва^гся первый обгьект);

ХВ(УВ) . — идентификатор базовой " точки опорного игавлимомого) объекта.

Для поиска максимально удаленной точки расчитываются гояния до ка;кдоп из точек объекта Oj и из них выбирается ииальноо ¡где л» количество точек объекта 0|).

Процедура расчета расстояния от "дна" фк!уры Г до точки (пиленного объекта, при заданных значениях углов п •)> и расстояний ;остоит из следующих действий (ряс.З):

1) к=1; а = Ша),'где II — функция преобразовании у1 \а.

¡А.В'.С,...}.

2) Фк=к(Фк);

Рис.З.Расчет целевой функции размещения

3) для точки Y^, объекта Oj расчитывается величина D _ А * ш(Гк) . * sin(Vk) ' .

fAe Yk = и + фк,

ÍГк >fl*g = 0, V0°<írk<¡M°;

Гк~

fk

\360-ук , flag = /, У lSO°<yk <360°;

[град.];

где 0к =

ЦЩ /А+со*(МО°-ук)))

4| для точки Y); объекта Oj расчитывается величина

l-k — Dk * sin Oif,

¡auno :k-V>k)Mag \ ' . .

[a-(í80- Гк~¥к)УМ = 0 .' 5) если T-.|4>Lmax, то выполняется операция Ьгаах=1£ ; ;

6) k = k + 1; а = 0;

7) если к~ w, то выполнение процедуры завершается, противном случае уьравление передае тся в пункт № 2.

Таким образам, целевая функция, расчитывается по формуле: А * sin(y) sirí(tp)

'L = sin(О) *

(1)

Недостатком данной процедуры является отсутствие поддержи произвольных типов фигуры, внутри которой производится _ размещён» объектов. Достоинством предложенного подхода к оценке качеств решения является его повышенное быстродействие, которо обеспечивается использованием простых математических выражений. :

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

В ТРЕТЬЕЙ ГЛАВЕ разработаны проблемно — зависимые ¡поненты генетического алгоритма. Разработана блок — схемд алгоритма '¿г'ималыил о размещения на основе- разработанного комплекса щедур и классического генетического алгоритма с разработанными |блемно —зависимыми компонентами.

Для реализации ГА размещения разработаны проблемно — исимые модули генетического поиска: кодирование хромосом, функция

[годности.

Кодирование хромосом осуществляется в соответствии со дующими положениями <) каждая хромосома включает в себя п генов, п —количество объектов; б) первый ген — это идентификатор базовой ки первого объекта, устанавливаемого на "дно" фигуры F; п) каждый — это идентификатор участка сопряжения; г) каждая хромосома , ержит значение целевой функции размещения, которое она кодирует и вспомогательную информацию объемом "2*п".

Согласно положению "б", генетический поиск осуществляется в п уляциях, где п — количество объектов

Таким образом, при решении задачи размещения п объектов для дой хромосомы в ОЗУ необходимо выделить 4»п+8 байта памяти.

Достоинствами разработанной структуры хромосомы являются:

а) согласованность генов (все reina являются целыми числами от О 55535), которая обеспечивает сокращение сроков проектирования;

б) линейная зависимость. пространственной сложности мосомы от количества размещаемых объектов, что свидетельствует о ольшом количестве требуемой памяти ОЗУ для популяции, состоящей п хромосом: m*4*n+8.

Расчет функции пригодности выполняется по формуле (1).

Генетический алгоритм размещения разработан на основе ллекса процедур и отдельных проблемно —зависимых компонент, к—схема ГА размещения приведена в диссертационной работе. Для го алгоритма на языке Assembler реализована программа для ЭВМ типа [ PC/AT 486. Объем программы — 55 Кбайт.

В ЧЕТВЕРТОЙ ГЛАВЕ' описано проведение серии экспериментов разработанного во второй и третьей главах алгоритма размещения. По ультатам экспериментов уточнены оценки пространственной и менной сложности алгоритма. ■ Отмечены особенности и определены-асти, применения разработанного алгоритма размещения^

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

Цель экспериментального --исследования — получение точных дений о характере зависимости быстродействия (Yj) и требуемой для эти алгоритма па*шги ОЗУ (Yj) от количестве объектов (Xj) и ачества точек объектов (Хг): '

Yj =F(Xi), X2 = const; Y, « F(X2), X, = cor.st;) i'2 - F(Xj), AS ~ const; Y2 = F(X2), Xj - const; j

План проведения исследований яиляется следующим:

1) проведение серии экспериментов для различных значений )

2) определение математического ожидания Yj, Yj для всех серий;

3) построение регрессионных уравнений (2) по методу Чебышева В соответствии с составленным планом были пронедо

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

Зависимость быстродействия и памяти от количества точек объектов

__Таблица 1

Кол. обьек. Быстродействие [сек] Y1 / Память ОЗУ [Кб! Y2 Уравнение репрессии

- 4 точ. .10.380 6 гоч. 8 точ. 10 точ.

12.60 /' 21 .'604 40.53 / 36.414 76.23 / 49.294 " Y1=2.16-3.23xcr-2+1.2xI",:/ Y,= 19.7-35.9*° 1 + 1.2х0Л

4 9.66 / 25.874 51.41 / 60.96о 140.23/ 97.556 300.55/ 137.57 Y, =5.16+1 .бк^ + 6.2х4'^/ Y> = 3.8+1.5BxU'-4o.Cx1'9 ■

24.50/ 55.570 127.98/ ¡35.07 352.07/ 203.! 94 1*94.64 i 395.07 767.36/ 105.7 Y, = 1.3 + 4.5xJ"42.6x',<7 Yj = 0.4 -г 25х + 1.1 х^

о - 49.55/ 101.57 250.34/ 248/9 1410.В /1 Yi -1.4 -6.8.x l-i + 9.3xz'z/ Y-> =■ 23 + 98.6л0'8 + 3.9х' 8

7 87.5 / 169/ -12 ■■№.02 /' 416.576 1260.51/ 2226.7/( У, = 2.5-4.3х ■1 + (,89х11 / , !

8 13«. 74/ 262.98 644.00 / 1848.15/ 3675.27/j Yj = 1.6 — 1.04хи -'+ 15х' у /

Зависимость быстродействия и памяти от количества объектов

Таблица 2

Кол точ. Быстродействие [се Память ОЗУ {Кб к] Y1 / Y2 Уравнение регрессии

3 обГ1 4 об. 5 об. 6 об. 7 об. 8 об.

4 2.42 / 10.380 9.66 / 25.874 24.5 / 55.578 49.55/ 101.57 87.5 / 169.42 138.7/ 262.98 Y, =8.7 + 4.2xJ',J-i:0.6x2:37 Y2 = 1.9 - О.бх1 6 + 0 Зх2-6

6 12.69/ 21.8 51.4/1 60.97 127.9/ 135.07 250.8/ 248.91 439.0/ 416.58 644.0/ . Y1=287-212xua + 41xly/ Y2 = 9.8 - 5.4Х1 + 0.8x^s

8 40.53/ 36.414 140.2/ 9X566 327.1/ 209.19 694.6/ 396.07 1260./ 1848./ Y, = 927 - 660xua +123x1 -м/ Y2 = 9 + 3x2 + 0.2x3

10 76.23/ 49.29 300.5/ 137.56 767.4/ 305.7 14107 2226/ 3675./ Yj = 127 + 115xzo + 2.47xJO, Y2=9 + 3.ix2 + 0.3x:j

Результаты экспериментальных исследований показали, быстродействие разработанного алгоритма на 10 — 40% лучше, чем аналогичных алгоритмов. Однако следует отметить, что для раб( алгоритма требуется значительный объем памяти ОЗУ. В качестве прим можно привести следующие данные: а) размещение 7 прямоугольни

>ебопало 1.5 Мин на ЭВМ тина IBM PC/AT 486, сгходы составили 15% мещйние 9 прямоугольников ■ при помощи аналогичного ГА >ебовало 1.5 мин на ЭВМ типа IBM PC/AT 486); б) размещение 7 .тоугольных: многоугольников (количество вершин 6) pt . личной формы юбовало 11.5 мкн на ЭВМ типа IBM PC/AT 486, отходы составили 17% мещеппе 3 произвол^ых многоугольников одинаковой формы при эщи метода отжига потребовало 18 мин. на ЭВМ типа SUN rosystem 3/2Б0, отходы составили 17%).

Областью эффективного применения разработанного' алгоритма ющения является размещение геометрических объектов »гоуголышков) прямоугольной и произвольной формы.

Основешм недостатком алгоритма является большой объем памяти ', требуемый для работы программы.

Достоинством генетичесхого алгоритма является использование !ий о свойствах размещаемых объектов, что обеспечивает снижение :ов проектирования.

ЗАКЛЮЧЕНИЕ

1. Приведена классификация подходов к решению задачи ¡етцения двумерных. геометрических объектов. Определена :пектпвная с точпн зригия организации перебора область .едовашш. Проведен анализ алгоритмов размещения, которые рсятся к перспективному подходу. Выявлены достоинства и недостатки

алгоритмов. На Основе проведенного анализа предложен и обоснован тический поиск для решения задачи размещения."

2. Сформуляровзиа задача размещения двумерных обьектоз гаволъцой формы в ограниченно?! двумерном пространстве. Построена татурная схема процесса поиска субоптнмального размещения, ифкцироваиа и реализована методика векторного .описания горных объемов, которая позволяет повысить качество цизиошюсть) ра змещения за счет векторного представления объектов, аботаны компоненты алгоритма размещения, которые позволяют атить сроки проектирования за счет реализации эвристических :мои размещения, а также за счет накопления, использования si (фикации знаний о свойствах объектов.

3. Разработаны проблемно — зависимые компоненты ГА: [рование хромосом и оператор мутации. Построен механизм мизации. На основе механизма оптимизации и комплекса процедур, аботан генетический алгоритм размещения.

4. Для алгоритма размещения двумерных объектов разработан т программ для ЭВМ Типа IBM PC/AT 486 на языках раммиропання Assembler иС+ + .

5. На этапе исследования алгоритма размещения составлен план :едения экспериментов, проведены серии экспериментов и )лнена статистическая обработка экспериментальных данных, зеденное исследование показало, что применение генетического ритма размещения позволяет сократить сроки проектирования на 10 —

40%. Генетический алгоритм по сравнению с аналогами -эффективт работает в области размещения прямоугольных многоугольник Достоинством генетического алгоритма размещения является < способность генерировать, модифицировать и использовать знания свойствах размещаемых объектов, что обеспечивает снижение срок проектирования.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ <

.1. Файзуллин А.З. Система управления базой дшш электрорадноэдементов. // Интеллектуальные С1АПР, Тагацрог. 1994 Вы». 4, стр. 121 - 122. ,

2. Файзуллин А.З. Генетический алгоритм упаковки элеменч произвольной фориы на плоскости. //Интеллектуальные САПР, Таганр 1995 г. Вып. 5, стр. 76-80.

3. Файзуллин А.З. Определение функции пригодности индивг популяции в генетическом алгоритме упаковки.// Сборник тезис докладов к Всероссийской научной конференции студентов и лспираип Таганрог., 1995 г. стр.86. .;<;' . .

4. Курейчик Лебедев Б.К., Нужное Е.В., Файзуллин А.З. др. "Разработка TeogH)i>;H методов построения интегрированных CAI БИС С элементами искусственного интеллекта". Деионир. в ВИНИТИ; ГР 01.9.50004188, i. Таганрог, 1995г, с.65. " íi

5. Файзуллин А.З. Определение пересечения двух объекте! задаче размещения. // Интеллектуальные САПР, Таганрог. 1996 г. Вып. 6

6. Файзуллин А.З. Использование знаний в алгорт размещения. // Интеллектуальные САПР, Таганрог. 1996 г. Выи. 6.

7. Файзуллин А З. Определение параметров треугольника задачах САПР. // Интеллектуальные САПР, Таганрог. 1996 г. Выи/ 6.

В работе [4] лично ачтором проведен .шализ механична эволп ч органических систем й нз основе этого анализа изложены ocho и принципы построения генетических алгоритмов, применяемых [ оптимизации технически?, объектов САПР.

■