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

Государственный комитет СССР по народному образованию

Московский ордена Трудового Красного Знамени горный институт

РАЗРАБОТКА ПРОГРАММНЫХ ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ ПРИ МНОГОВАРИАНТНОМ АВТОМАТИЗИРОВАННОМ ПРОЕКТИРОВАНИИ ИА ОСНОВЕ ТЕОРЕТИКО-ГРАФОВОЙ МОДЕЛИ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ

Специальность 05.13.12 — «Системы автоматизации проектирования (промышленность)»

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

ФЕДОРОВ Максим Всеволодович

УДК 65.011.56

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

Москва 1991

/

//•• С

Работа выполнена в Московском ордена Трудового Красного Знамени горном институте.

Научный руководитель академик АЕН РСФСР ГОРБАТОВ В. Л.

Официальные оппоненты: . проф., докт. техн. наук ФРОЛОВ А. Б., канд. тахн. наук ВАСИЛЬЕВ В. Н.

Ведущая организация—ВЦ АН СССР.

- в час. на. заседании специализированного совета

Д.053.12.12 в Московском ордена Трудового Красного Знамени горном институте по адресу: 117935, Москва, В-49, Лс-" пинский проспект, 6. д 1-1/п

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

Автореферат разослан « . . . ».....1991 г.

у.?.

Защита диссертации состоится

Ученый секретарь специализированного совета

доц., канд. телн. наук ТОРХОВ В. Л.

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

Актуальность рзСоты. Хэряктер решаемых в САПР заг.яч, а именно сложность и неформализованной* р-яссч»?, обус.ювдчр?'ст ятгуйплссть задали иптсяяейгуаяаза-щш аЕтомзппчргглнпогипроеиттродзшгг. СуЕ;ест:пчэтд!е подходы к интзллгктуоллза-ции САП? заключаются, ипкимм ойрчзС'М, в и!гкУ!'7".1стуальиоГ1 ггоддгрхгсе функдиопи-рзвзнва компопеят кифоризгс^ямко сСсгяечак'? САПР, i го яе имеет ке-тосрсдстаея-ного ¡шшчи na nprssccc spmmns яростного р^пичик. С друге ¡i стером*, интеллекту-елгоацвчпрчкетпя perneteroя САПР татру/, пеп reí!, что:i:¡ -сстеые модели представления пп.шгш нллсг.ригог,!! •! дчя спхеанчэ сnsu <фш:и зюттд ькеяерта-прогкткровшика. Егведгтвге атого np;i сут-гтаук>г.да'1 ксоЗходикостн осуществления мвскдориаппюЯ прорзбоп-.n прогкта пепрелсг)1\'1гг1'сялозмсжн1.!мфп>.1гл>13оагтьсаг:опон:!т1:ег>лр1:ан",5 проектного реше:п;я (ГШР). Это треб)'гг изучения споЛста а структуры пространства проектных решений и разработки формальной медали, способной адекватно отас»1вать его. Возможность сформировать пространство чзрчзнтез ьа рампих этапах проектироза-пия и пчбора из шгх оптимального множестеа для детальсоЛ проработки на елгдугадих этапах позволит сущгстаеняо погыснть кач(__тво проектов н значительно сокрапгть гремя проектирования. Наиболее предпочтительным формализмом, пригодным для использования в пространствах дгсехретных значенкл, исшейя теоретико-графовый аппарат.

ОдпоЕремепно следует отметить, что еджгм г.з осиспкьгх направлений развития систем искусственного интеллекта, пзлпетса те:!Д£га!'8 к созданию югвариантнцх методов п ппструментальных средств, т?мегощях ткрсклЗ грут потенциальных приложений.

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

Цгль и задачи. Целью работа является разработка «етодоз я инструментальных средств генерация ВПР. Для доеттсяагия этой цата необходимо регепть следующее задачи:

• разработка теорегихо-графовоЯ модели представления зиакнй о пространстве проектных решений п формализация понятая варианта проектного решения в терминах предложенной подели;

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

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

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

Методы исследования. Поставленная в работе задача решается методами теории графов и искусственного интеллекта.

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

• предложена новая теоретихо-графовая модель предстаалсния экспертных знаний в области проектирования, позволяющая формализовать понятие варианта проектного решения;

® предложены методы генерации оптимального множества вариантов проектного решения, позволяющие получать на ранних этапах проектирования структурный ей; окончательного решения;

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

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

Предложены методика создания базы зизний, фиксирующей взаимосвязи су ¡двостей конкретной предметной области, и методика применения шкета в целом. С поыотью разработанного пакета создана интеллектуальная подспетека генерации проехтдых решений, входящая в интегрированную сютег-у прегр: чшиого обеспечения ИНФО-СЛПР ПО "Точмаш", чти практичеекп пр геало к егьташшио трудоемкости процесса проеетвр* • ваши изделий м.лш. ^строения.

1асчс ш экономический эффею сосга гег ¿3 тыс. рублей в год. В с-хл-а>с интеллектуальной ихледс ¡атсльской САПР этот пакет такке внедрен в учебшы процесс в МГЦ.

Апробация работ- и Основные положения дкссеръ дай докладывал, сь па XII и XIII всесоюзных симпозиумах "Логическое управление с использованием ЭВМ" , XI и XII

Координациочных совещаниях "Математическое обеспечение п интеллектуализация систем СЛПР-ГЛП" (г.Снмферополь, 19S9 н г.С;:мен з, 1990 г.) и Всесоюзном совещании "Экспертные свсгеми" (г.Суздаль, 1990 г.).

Публикации. Основное содержание работы отражено в 3 публикациях.. Объем и структура рпСог;.!. Диссертационная работа состоит из введения, четырех глав и г.аключепня. Она содеругнт 12S страниц маииношиного текста, включает 19 рпсункоз, 8 таблиц и список литературы mill наименований.

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

I. РАЗРАБОТКА МОДЕЛИ ПРВДСГЛИПЕГШЯЗНАНИЙ

Удовлетворить комплексу прогаворечнсых требований, прсдьяилчемых к ссвргмен-пому нроектпрованто, а нмелчо - сокращению сроков разработки проекта при одновременном повышении качества н росте сложности обьегсгов проектирования, невозможно без применения систем ггагомативиросакнего проектирования. Высокая сложность проектируемых объектов выражается в большом числе параметров, описывающих эти объекты, и их многозначности. Это прггаодит к току, что размерность пространства потенциально возможных вариантов огромна. С другой стороны, в этих условиях, когда полный перебор псех альтерната невозможен, отсутствуют формальные процедуры, способные реализовать прямую функциональную зависимость меяду входным» данники и ВОЗМОЕП1П.С1 ВПР. Именпо это н заставляет проектировщика прибегать к вариантной проработке проекта, предварительно сокращая круг рассматриваемых альтернатив. Принятие решения по такому сокращению всегда отчасти субъективно п пе получает какой-либо количественной оценки, а поэтому приводит к снижению качества проекта. Для более обоснованного ограничения числа рассматриваемых вариантов необходимо выявить свойства пространства проектных решений, которые позволяли бы структурнзовать его, и на основе формальной модели и соответствующего теоретического аппарата разработать методы генерации ВПР.

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

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

Введем бинарное отношение совместимости. Предстшшм его в вмде взвешенного графа совместимости

где носитель У~(У,} - ыяожегтво значений, ¡-1,пр, У,^*,^}"!.!!,) - множество значений 1-го параметра, п^ - количество параметров, п, - количество значений 1-го параметра. Сигнатура II 1рафа соаыеотшости 1)с у'представляет собоЗ множество дуг, соединяющих вершины, соответствующие тем ы;.: гениям, которые могут бить допустимы одновременна Множество весов вершин Р~{Р,}, где Р|~{рц/}"*3 ,о,} - множество весов вершин 1-го параметра, содержит коэффициента предпочтительности значений, смысл которых подобен коэффициентам достоверности гипотез, вичнслесным г.ри классическом логическом выеодс "от целен". Мцогсстго весов дуг грд(]ц ссиместхмосги У/»,{\УуЛ,х»,1,п|} содержит коэффициенты соиысстиь.оста пар злачены"!, покоз^ьлювд:г, каскады; о согме-стама данная пара. На рис. 1 представлен граф совместимости некоторых тнпоз оборудования, выбор которого ясляется одной из задач проектирования открытых горных работ.

Веса вершин определаютса входными дзшшш: требокшдэш к проектируемому объекту и описанием внешних ус/.озл;".. Веса дугмогуг быть фиксирогашшми, задотшш зкспертом-прсектнровщпком на осиосзяшз его сс&твишого представления пространства значений, ио мо1ут явлзпгсл и фунхцзшй входных дмшмх, как, например, в случае выбора согместикых пар сгыосвал-гжсхаватор. Вьед.'лше надобных коэффиудапез позволяет оцеш;&иь и сравнивать Совиестшжта я доггозеркост значений палуч&еш»х ЕПР и, таким образом, получать предварительную ецгшеу качества ргкеп-ля.

Из свойств опиолсын соэмсетоийгти следул пгаеты;« тс, '.гэ оиа на траиздшзпо н иг пошгосма определено, т.е., как следу ет ю с^шш, ие лс&а ихра параметра. ысьтет находиться в игношешш соЕиес^жсти - дя л в«:ст.рых кз шис это отношение модет бить не определено в том случае, вг су«эдст«уя каикх-лсбо пргтач, погксля1Шцн;>. обосновано судачь о том, кйсходьи^ ссвмести; кх

Преложены* модель позволяй! наест • об^апагую сссрсцхо ссаер'шр.чкшия ц&фа <опюше1шг) ивмес.лмсста. Для етого сьсц^ы б«нарп)\о фуштаю согксстшгастп 5:

0-<^,Р),<и,\У)>

я матриц» смежности £;) и с^ исходного и итшгртпрокшиого графов:

Г г>'ч, ес<и (у„уре и

Ч о, еста (у,л'р« и,

V -1, если З^рУ^аО

Теперь операцию иш'.ертнрованкя можно опр?;,е.итть та::

1) V 1^:3 (у,,урс: и - -;

2) V 1, ]: Я (у,,ур " 1 & (>',,ур ' и - тех пар параметров, совместимость которых задана, всриютл, сопчгстимосгь кото,!ы>: гзе укг.гапа, соединяются ребрами);

3) у "(УрУр' О -. (1,^0 (для тех пар параметров, совместимость которых ие задана, носке ребра пе создаются, т.е. иесогмггткмость также не задана).

Как легко убедиться, операц.!!! ппвертгрсзания обратила п, таким образом, пе приводит к нскахеншэ иди потере кпформацгг:!, а пространство ГШР .чожет одпнакопо эдекгзттю списигапзся как отношение! I совместимости, так п отношением несовместимости.

Рассматривая процесс проеэтнрсвзшш как многоэтапный процесс, па каждом из зтаггоч которого решаются определенные задачи и существует 'шокесяо париаптов частого проектного регаечия, а задачи л решений различных этапоз вгаш.'осгязашл, мозжо укрупнить предложенную графопую модель п примчит» ее для цредстатлепяя пространства решений сквозной спстемн проектирования. При этом вершины графа соотгетстзуют часшын проет'.тпь'м ргптсгихяч, а дуга соединяют взаитюсв.чзапныереше-гак, поэтому прого^ког рясгмотргш:г ирмультгтм можно корректно применить а для полного сроцесса пра?кт!1розанп», подразумевая под параметрами этапы просктт:1;<-па-нпя.

С учетом следующих практических требоггшгй к свойствам варгиптон прое<~ного решения:

в) достоверность геперт^/емих вариантов долхпа бнть максимальной,

б) совместимость значений гарпакарешениядолжка бить максимальной,

в) вариант решения долгееи содержать, по крайней мере, с",ло зпаче!ше каждого параметра, можно формализовать понятие ВПР в терминах предложенной графовой модели.

Ретеппгм будем считап> такой подоргф ^(г/г'КпД графа сопмеяимосш, у кэтгрого:

а) величина

р = (П V"'. ьй

(предпочтительность) максимальна,

б) при мачсш,сальной в-лг.-.чикз V/ (спмеспшоск.)

У»™ 100 * II (v, /100), ^

\ I л пр з $ е Е: VJ е Р, Будем называть подграф, покр2Л1ИЮЕ,ий все искомые подграфы, пргд.гтааателъип.ч. Таким образом, предложена модель кредстоьлениа знапяй о пространстве проехги^а решений я формализовано, в рамках этой модели, понятие игр;ш1гга ирое-пкого решглая (БПР).

2. МЕТОДЫ ГЕНЕРАЦИИ ВАРИАНТОВ ПРОЕКТНОГО ГЕШЕНИЯ

Обратимость операции шш^ртирсл: аия 1];афд совместимости позиольет адекватно опнсиват:» простринпхо г.роск л>пх решений графом иссоьмсстимэстя. При этом ЕПР можно представитьв ииде пустого прадпавотсльного подграфа. ИзБестны методы нахождения всех пустых подграфов, поза.-мккичиа в принципе получать и ПР. Одиахо этот подход - иазовам его точлым - имеет следующие исдостатш::

• комбш:«торизясло}ы!€сг/>пзгадоз нахождения бхх суетах подграфов, как НР-ислкой гадачн, зге позволяет рассчкш^мь на практическую сримсиимосгь это IX) подхода;

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

® иг все посгроенпыг таким образом подграфа будут средсквлтслыш-мд;

• кскошвподграфамогут «праидшю илычыъп дул;, сашыссссмзл

по срггпсшно с кесгии ьшщдспгшсл км аерш-'тп. Укязаптшз недостатки сгсшмзяэт нсить ^з&ггжешшг: мел оды поиска предегсгл-тслышх пустг_х подтрафоз, среда кстср-и« гтеггпаг методы соцска мамшшышх пусти* подгрдфоз, пид кото;ш1ш аде будем лодшуигвагь подграфы с какездилыш. сумзархшм посо. вер-лш. Зги сцр!;..ткчгст:а ¡¿коды - Суд л саз-лстъ1.:; ираСижск-- об-аде мт полкдотда/шпей слоа-зсстьм еда-.»ко пг у чкшеиот кгсда дуг п, во-вторых, геяерзуукттол!ко г вауягиг^шеил. Учет одновременно ксои втриаш, и дуг требует врацгнезля огтгиальяих нгтгдо втеха, т.е. кигодов, которые гсиер.:р■> •„-)-;' реиеюц с стздюяъаым. в скис.» адиасмэй целевой фующда, оатпошгкнем ецгяог

Л'. crrv?f чести -i спп I-ос. "5. Предл'гисмы'; .-.eisn отги\'а."ч.:>го помеха заключается з кепюг.гдиич airryragm '{т.'кчжичпа:

' — '»t* .L *

ПО - А ■ -—т8-^ ~ В ■ р, i С - y,'<i) ,

'Ч

где i - поме;) в* r.-jimm, р, - е: гее, *#(!) - су:г!«;"<7!й е;од>т, состчпипощлх !• ю ггрлтпу с г.^-сгел-л'И, у:.:е гсглчшнтш и стрьч^иЯся р-^1', Г, - огр?сшсаъ 1-й герипга-», f, - отргсгсося» у.-л жяючжмк a подгрч','! т.гркид, f(i - пер?гг«0!'че згсх ог.рг.:т;;оете'1. Псггмй ч'чи фу;.лдажа.те Г,;'х-ч-очатди"! а сс.1ч н; '»'..?:одлу;о rpr-.фа кесее:'еегй'.;ос-п1, гпзррл"сг1,иС|,;£ат7.т?.гпе oxpccri.rrni е-?егглх wKwri'iv.'ofc.ixa окргегго-

етч у г г г.-_',;з>;еН7т::м т .-и, что ¡еи^'.грст.ть пусп'е почту „rh,: но:гт:о

бэлълкй мощности д."л того, чтоби они <5ыли пргдето.гел!

Всссгм! котффкг.чекти Л,В » С иог-псо-г :п,т.е; гь сзсйстлз ггнерг.руемнх этим методом ггптсний. Так, 0 ;.-гг пудт" ';м с нлибол'-тач п-сси Есрк::!а, т.е.

регеенчя с лаксимги.чс'» доетогсрпос.мо, г,о, бъпъ ':з:кет, с шикой соииеспуюстыо составляющих ах smw-aS. Оллягке yi.s*-гачека коэфф "даента С сйргтггое. Коэффициент А исяс.чьзустея для блязгла с о сСеспече:'1;я гредставстгльпоста пелучг.ехмх подгрзфез.

Генерация ез/пгш.» наборов глрпаптов решения обгссечгвагтся следующим сбра-ес>;. Указгшшй истод прьчепкется тр:5уг.\ ое кыт'.чеегоо p ir., причем в качестве иетта3 г.ерцкпи побирается ггршздаа с ;йг.спмаг!.'и.:!« ггеом к не вхлючсееяя ни в один гз уже вираСотапных ВПР. Есга количестг .•> получегстк ВПР мсгтысе аздд'шого, то геперзция очередного крпглпа [!ачпгастсясолре.хйл-..п'япгри (тройни, чстзерки .х г.д.) '..ecircsoib-x Е?рлнпт с клюзяадыагм весом п не аходгщ-лх сдчопрв!«-спяо rai и одяп из уже гырг.бстзч-тшх ВПР. Тг><сим образок, все полувек»« подляфы будут раяятивтмя.

Для сохращсгаи 1рг,:.:гни гслералдз наборов режегпЛ бил рззрзботап второй прв-Сллзтетг.ши метод, с котором большая ч-сть гытнелгннн вьшсссна в операцию предобработки грз'£>а созместикости

P(G) --G*, которая заключается в следуюдем:

я) Ey~wr * V[* Vj (jsvitn cscoB дуг пропгяеяет ;гм tc»e луг.; -л кпглд зтешх ей ребер); б) s,j -J, кот v,c Vt, Vfs P,, 3(k,l)"-0 (езлйпе flixxinK'-f..''» ребер >гяду верпгя'л>и, "«терьте с««тг4тстчуй.т>ярч>етре> с2е«»редс<е5Д«" fciwn'-cnio);

В этт< слупгз псгсяин («кгттием будет гадкгься итредгтг. -.•кте.'п.чы^ полет»«! подграф. Качество решвлиз оярмеявяся лишь гсссм "п1, поэтому имезая фл1тхц:1я упрощается до F(i)«^v(i). Kns rrtatsH гкепераметтпл с тесгогымя графив*, г.ргялот:сяв.гв

предобработка графа совместимости позколкет в 5-7 раз ускорить процесс генерация вариантов решения.

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

3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

На основе предложенных методов генерации оптимального набора ВПР были разработаны точный (PRECISE) и приближенные (ALCOR1, ALGOR2) алгоритмы.

Программная реализация алгоритмов генерации оптимального набора ВПР и вспомогательные программные средства создания, редактирования и тестирования структуры связей значений параметров составляют содержание пакета IntelGen. Программы написаны на языке Си и рассчитаны на применение на IBM-совместимых ПЭВМ в операционной среде MS DOS.

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

- CENTRE: центральный блок монитора;

- BUILD: блок интеллектуальной генерации структуры связей значений параметров;

- EDIT: блок непосредственного ввода, тестирования и редактирования структуры свазей значений параметров;

- SYNT: блок синтеза графа проектнров. лии;

- GENER: блок генерации множества ВПР.

Работа системы происходит под управлением блока монитор; CENTRE. Этот блс.; " помощью мешо "редоставлает пользователю возможность ..роЛтн весь процесс генерации оптимального множества ВПР, изобра женный ш "ис.2, или ка}./ю-либо его часть, испаъ ював да1- ше, полученные ранее и сохраненные во внешних файлах.

Формирование структуры евлзей значений параметров можно осуществлять различными путями:!) в ходе сеанса с экспертной системой (блок BUILD),2) путем непосред-

Рвс.1. Совместимость некоторых типов горного оборудования

Рис. 2. Процесс генерации оптим^.п логь множества ЗПР

стяышого ввода соответствующей информации (блох EDIT), 3) с помощью обь'чясго текстового редактора, зная и соблюдая формат представления информации.

Первый способ ввода информации (блок BUILD) реализован в резработазшем канете с помощ! I') обслочечион экспертной системы Guru, использующей продукционный логический вывод. С среде этой системы создаются прикладная программа, управляют:"»'.." диалогом с пользователем, и база знании, содержащая описания вершин графа совместимости и их связен. На основе нравил, хранящихся в базе данных и моделирующих взаимосвязи различных значений, определяется предпочтитсльногть тех или иных значений параметров н определяется, насколько в данной ситуации оптимальна их созмсст-ная реализация, т.е. совместимость.

Возможности Guru, реализованные в IntelGen, позволяют создавать продукции различных видов:

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

2) продукции, задающие отношение совместимости различных значений,

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

В работе предложена методика итеративного построения базы знаний для ЗС блоха BUILD.

Блок EDIT содержит средства тестирования результатов работы ¿лоха GENER к значительно упрощает отладку создаваемых систем за счет удобного многооконного способа езода информации. Быстрота и удобство ввода позволяют разработчику прикладных систем создавать тестовые структуры связей и отлаживать существующие. Средства тестирования создаваемых структур способны сигнализировать о различных подозрительных ситуациях, которые могут вознЛхнуть при неправильном вводе информации или из-за некорректности базы знаний.

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

1) выработать любое задаваемое количество представительных подграфов;

2) все вырабатываемые представительные подграфы б,¿ли Си различными;

3) качество вырабатываемых подграфов (т.е. достоверность и совместимость) било бы максимальным;

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

Экспериментальные исследования разработанных алгоритмов на тестовых >рафах позволяли оценить примерны!! объем вычислительных затрат при решении сложных практических задач. Для этого было измерено время поиска одного решения для графов р13лччной размерности и осуществлена аппроксимация и экстраполяция полученных дат;.',:к. Гргфики зсг::симости времени вычислений от числа искомых параметров, выполненные в полулогарифмическом масштабе, показывают, что эта зависимости слабее экспоненциальных. Нсэкспоненциальмый характер зависимости t(n) позволяет рассчитывать ий применимость разработанных алгоритмов при решении современных практических задач большой размерности. С целью оценки величины t при большом числе параметров била проведена аппроксимация зависимости t(n) с помощью известных алгоритмов регрессионного анализа. Логарифмированные значения исходных данных били аппроксимированы различными функциями - логарифмической A+B*log(n) и степенной А*В Результаты регрессионного анализа и экстраполяции (в миллисекундах) обобщены в табл.1. Она содержит коэффициенты А. и В логарифмической и степенной функций и оценочные величины t для п, равного 10, 50 и 100.

Таблица 1

Результаты регрессионного анализа и экстраполяции

Алгоритм Функция А В л-10 п-50 а- 100

ALGOR1 A + Blojn 1,2 1.2 450 2700 6000

А.п" 0,72 0,68 200 22000 ю6

ALCOR2 А + В log n -0,1 1.1 100 750 1500

А. nB 2,0 0,3 550 4000 30000

4. ВНЕДРЕНИЕ

Разработанный пакет инструментальных средств ЫеЮеи был внецрен в практик • проектных ре'хуг .а 110 "Топмаш" (г.Г кевсх) ч составе комплекса инструментальных средст ИНФО-САПР, позволившего создать систему автоматизм званного щ оектиро-кт1л машиностроительных изделий и технологий и техяоло ической подготоьки производства. в резу.:1.тат"; чего были сокращены срок - проектирования технологических процессов в 3-5 раз, повышено его качеетто, сокращена потребность в количественном сосгсгз технологов на 10% по сравнению с нормативом. Экономячесхпй эффехт от

внедрения собственно интеллектуальной подсистемы генерации ВПРсоставил 10% сум-нм экономического эффекта от внедрения комплекса инструментальных средств ИН-ФО-САПР, или 23 тыс. рублей. Внедрение подтверждено соответствующим актом.

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

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

Описанные задачи решает исследовательская интеллектуальная САПР, созданная на кафедре "Технология, механизация и организация открытых горпых работ" МГИ на основе пакета 1тгЮеп, реализующего предложенные методы и алгоритмы, которая способна генерировать решения как на основе опыта высококлассного специалиста, так и на основе небольших тестовых баз знаний, создаваемых обучающимися. В ходе развития БЗ происходит активное овладение пакоплсшг'м современным опытом проектирования. Тестирование системы на модельных ситуациях и сравнение качества результатов при различных БЗ позволяет контролировать рост квалификации обучаемого персонала.

В созданной исследовательской САПР процесс генерации полного проектного решения представлен в виде шести этапов: 1) определение границ карьера; 2) определение направления развития работ, 3) отвалообразование; 4) выбор комплекса механизации; 5) схема вскрытая; б) календарный план работ. На каждом из этапов определяются искомые параметры (например, геометрические - при определении грашщ карьера), их зависимость от внешних условий (например, механических свойств породы, требуемых темпов добычи и т.п.) п взаимосвязи. Практика показывает, что существующее противоречие мекду Ееобходимосгыо комплексного решения задачи и последовательным способом вычислений устраняется благодаря генерации ьарщягов решения, исходя из модели отношения различных параметров и решений.

ЗАКЛЮЧЕНИЕ

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

2. Предложена -теоретико-графе зоя модель представления зшишй о пространстве проехтаи решений, адекватно описывающая структурные и количественные характеристик этого прострапстза.

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

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

5. Разработанные программные средства генерации вариантов проектного решения п-гдрепа в практику ачтоматазацил проектных рабо подготор-и и организации про-гзчгдап л изделий па ПО "Точлаш"с -одоиым экономическим эф<; ектом 21 тыс. рублей, а таете а учгбт»"] процесс МГЦ,

'Чло-пчз полл'жег:1я дгссертацмо.'ший раооти нзло: екы в следующих публикациях:

1. Федорсз М.В. Языковые средства интеллектуализации СУБД. - В кн.: Логическое улр-здеже с элмоваиием ЭВМ. - ХП Гсесоюзпый симпозиум "Логачесхог упраате-пие с чгспользспадпемЭВМ". - М.: Симферополь, 1989.

и

2. Федоров М.В. Интеллектуализация процесса принятая решения по сокращению числа вариантов проекта в САПР горного производства. - В кн.: Логическое управление с использованием ЭВМ. - XIII Всесоюзный симпозиум "Логическое управление с использованием ЭВМ". - М.: Симеиз, 1990.

3. Горбатов В.А., Торхов В.Л., Федоров М.В. Интеллехтуализация принятия решения во многовариантных плохоформализуемых задачах проектирования. - Веб. тезисов Всесоюзного совещания "Экспертные системы", Суздаль, 1950.