Znalostné systémy pre riešenie konfiguračných problémov

Marian Bobrík

 

Slovenská technická univerzita, Fakulta elektrotechniky a informatiky
Katedra informatiky a výpočtovej techniky
Ilkovičova 3, 831 02 Bratislava, Slovenská republika
bobrik@cauldron.sk

 

Spracované podľa: (1)

Abstrakt. Tento príspevok by mal slúžiť ako úvod do problematiky riešenia konfiguračných úloh pomocou počítača. Je tu popísané, čo sa rozumie pod pojmom konfiguračná úloha, rozoberajú sa niektoré základné vlastnosti konfiguračných úloh, popisujú sa niektoré modely a prístupy používané pri návrhu systémov pre riešenie konfiguračných úloh. To na zahrňuje oblasti ako špecifikácia požiadaviek, model jednotlivých častí a popisu ich vzájomných potrieb a požiadaviek, model rozmiestňovania častí a model zdieľania častí. Na záver sa tu popisujú niektoré principiálne problémy, ktoré riešenie konfiguračných úloh oproti predikčným podstatne sťažujú. Konkrétne je ďalej rozvedený problém „prahového efektu“ a „efektu horizontu“.

Abstract. This paper should serve as a introduction to problematics of computer solution of configuration tasks. It is described here, what is a configuration task. As next, basic properties of a configuration task will be examined here. Some common models and aproaches used in systems for solution of configuration tasks will be described too. This includes fielsd like specification language, a submodel for selecting parts and determining their mutual requirements, a submodel for arranging parts and a submodel for sharing parts across multiple uses. Finaly, I try to describe some of worst problems, which make configuration tasks much harder than others. That includes  a horizon effect and threshold effect.

Obsah

1 Úvod

Z hľadiska množiny potenciálnych výstupov by sa znalostné systémy dali rozdeliť na diagnostické a konfiguračné. Kým diagnostické znalostné systémy majú relatívne malý počet možných výstupov (riešení), pri čom je ich úlohou klasifikovať vstupy. T.j. priradiť daným vstupom niekoľko z možných výstupov.

Pri konfiguračných úlohách je situácia podstatne zložitejšia, množina možných výstupov je potenciálne nekonečná, alebo aspoň výrazne väčšia, ako pri klasifikačných úlohách. Cieľom je z databázy znalostí a zo vstupných informácií zkonštruovať riešenie.

Tento článok obsahuje stručný úvod do problematiky, popis najčastejších úloh, problémov, prehľad niekoľkých metód používaných na ich riešenie. Po pri algoritmoch a dátových štruktúrach, ktoré sa pri konfiguračných problémoch využívajú.

Pre upresnenie sa pod konfiguráciou sa v tomto kontexte rozumie spôsob, akým sa z daných častí zostaví celok a konfiguračný priestor je priestor všetkých možných spôsobov, ako sa to dá uskutočniť. Tento typ úloh sa často vyskytuje pri zostavovaní počítačov, návrhu zariadení, ale na príklad aj v medicínskej oblasti je možné nechať počtač vypracovať návrch terapie.

 

2 Popis problematiky

Aj keď konfiguračné problémy predstavujú pomerne širokú oblasť s veľmi rôznymi úlohami, zahrnujú množstvo rôznych typov úloh, ktoré vyžadujú rozdielne prístupy riešenia, niekoľko pojmov a postupov činnosti sa vyskytuje pri všetkých úlohách tohto typu. Tu sa pokúsim popísať model, ktorý sa používa v (1) – je zobrazený na obr.1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 


V tomto modeli sa rozlišuje špecifikácia požiadaviek, abstraktná konfigurácia, ktorá po procese postupného zjemňovania postupne prechádza na expandovanú (zjemnenú) konfiguráciu, zavádza sa hierarchizácia požiadaviek, abstrakcie funkcií, fyzického zloženia komponent . Samotný model sa skladá z

1.)                modelu špecifikačného  jazyka

2.)                model jednotlivých častí a popisu ich vzájomných potrieb a požiadaviek,

3.)                model rozmiestňovania častí

4.)                model zdieľania častí.

Model špecifikačného jazyka . Špecifikačný jazyk pre konfiguračná úlohy by mal umožňovať popísať jednak požiadavky na systém, ako aj informáciu o optimalizácii. T.j. kritériá, ktoré sa majú pri návrhu optimalizovať, lebo aj podpriestor konfigurácií, ktoré spĺňajú požiadavky napísané v špecifikácii môže byť značne veľký a nás obyčajne zaujíma iba jedno konkrétne riešenie. Ako príklad uvediem konfiguráciu počítača, kde požiadavku na možnosť tlačiť dokumenty, keď tejto požadavke rovnako vyhovie celeron s laserovou tlačiarňou, aj konfigurácia dvomi PIII pripojená na počítačom riadenú veľkokapacitnú tlačiareň s cenou 1000 krát väščou, prípadne ten istý celeron ale s 10, 20, 100, ... pripojenými tlačiarňami, pri čom nás obyčajne zaujíma iba tá najlacnejšia konfigurácia, ktorá ešte spĺňa požaidavky.

Je viac spôsobov, ako v špecifikácii popísať, čo vlastne chcem. Je tiež možné, rovno zadať, z ktorých abstraktných častí sa má výledný celok skladať, oveľa častejšie sa však používa tzv. funkcionálny prístup, ktorý spočíva v tom, že sa na miesto potrebných častí určia iba funkcie alebo schopnosti, ktoré by výsledné riešenie malo spĺňať. Napr. Počítač potrebuje scanner vs. počítač má mať schopnosť snímať obrázky v takej a takej kvalite.Je jasné, že funkcionálny prístup umožňuje väčšiu flexibilitu, je menej závislý na konkrétnych moduloch, ale vyžaduje dodatočnú informáciu o vzťahu medzi komponentami a ich funkciami. Toto priradenie zoznamu funkcií každej komponente môže podstatne zvýšiť náročnosť úlohy, náklady na zostavenie databázy komponent atď. Pre to sa často používa zjednodušenie v (1) nazývané ako „key-component approach“. Spočíva v tom, že sa pre každú funkciu určí jeden komponent, ktorý je pre ňu kľúčový a všetky kľúčové komponenty budú takýmto spôsobom uvedené už v špecifikácii, t.j. žiadna kľúčová komponenta by do riešenia nemala byť pridávaná na základe nepriamych požiadaviek, ktoré zo špecifikácie vyplynuli len nepriamo...

Model jednotlivých častí a popisu ich vzájomných potrieb a požiadaviek popisuje špecifikácie jednotlivých komponent funkcie, ktoré vykonávajú a ďalšie komponenty, funkcie alebo zdroje, ktoré pre svoju činnosť potrebujú, prípadne ktoré sa s ich činnosťou vylučujú (na príklad z dôvodu nekompatibility ).

Model rozmiestňovania častí má na starosti rozmiestňovanie komponent, špecifikuje rôzne spôsoby alokácie priestoru, ale aj iných zdrojov, ako financie, odber elektrickej energiea podobne. Popisuje ktoré rozmiestnenia sú dovolené, a ktoré nie. Táto časť konfiguračného zs je zo všetkých najkomplikovanejšia, najnáročnejšia a spôsobuje najviac problémov, lebo aj keď je možné jednoducho popísať požiadavky každej komponenty napr. na priestor, algoritmický postup, ktorý by z nich dokázal vyprodukovať ideálne riešenie sa dá nájsť len veľmi ťažko alebo vôbec nie. Ako ukážkový príklad by mohla slúžiť hra tetris, ktorá je v podstate o umiestňovaní rôzne tvarovaných komponent v 2D priestore tak, aby zaplnili vždy celý riadok. Na dokreslenie zložitosti si potom treba predstaviť tetris v 3D, pri čom niektoré dielce nesmú, iné zas musia byť vedľa seba, niektoré sú potrebné pre ďalšie a z toho všetkého treba potom vybrať ten naj... ...lacnejší  ...menší  ...rýchlejší útvar.

Model zdieľania častí určuje obmedzenia podmienok, za ktorých je možné danú komponentu využívať ostatnými časťami konfigurácie, prípadne na plnenie nejakej funkcie keď je daná časť využívaná na plnenie viac, ako jednej požiadavky. Môže sa vyskytnúť niekoľko typov takéhoto zdieľania častí. Napr.

1.)                Výlučné použitie – časť môže byť využitá iba raz.

2.)                Limitované zdieľanie – komponenta môže byť zdieľaná iba určitými funkciami a inými nie.

3.)                Neobnedzené zdieľanie – komponenta môže byť ľubovoľne využívaná. (dosť zriedkavá situácia)

4.)                Sériové využítie – môže byť ľubovoľne používaná, ale iba na jeden účel v danom čase.

5.)                Obmedzená kapacita – Každé jedno využitie spotrebováva časť kapacity komponenty, ktorá môže byť zdieľaná až kým sa nedosiahne maximum kapacity. Ako príklad môže slúžiť na príklad spotreba elektrickej energie. Zdroj je schopný dodať len určité maximum, potom už k nemu nesmú byť pripojené ďalšie spotrebiče. Ešte komplikovanejší prípad predstavuje na príklad priestor vo vnútri skrinky, kde o tom, či sa do nej nejaká komponenta ešte zmestí rozhoduje aj jej tvar. Na tomto mieste sa totiž tento a predchádzajúci model prelínajú.

Pri tomto type zdieľania sa obyčajne používa tzv. aditívna spotreba, ktorá neznamená nič inšie, len, že každá komponenta má číslom popísané svoje požiadavky a požiadavky z celej skupiny sa získajú sčítanim ich požiadaviek.

 

Tieto modely resp. typy informácií a postupov sa v rôznych podobách vyskytujú vo všetkých konfiguračných problémoch,väčšinou predstavujú dobre rozpoznateľné celky, aj keď niekedy sa vzájomne prekrývajú.

3 Rôzne problémy a ich zdroje  pri konfiguračných úlohách

Prahový efekt vzniká, keď pomerne malá zmena v konfigurácii vyvolá prekročenie maximálnej kapacity nejakej komponenty, čo vyvolá kaskádovú reakciu – prekročenú kapacitu je treba nejak doplniť, nové komponenty sa musia pridať, prípadne nahradiť výkonnejšími, čo zase spôsobi ďalšie prekročenie iného limitovaného zdroja tak to môže pokračovať až kým sa pôvodná konfigurácia zmení úplne, alebo aspoň v nej dôjde k podstatným úpravám, ktoré spôsobia, že aj keď pôvodná konvigurácia bola v istom smere optimálna, po tejto úprave už nebude. Prahové efekty môžu vzniknúť v každej fáze konštrukcie riešenia, principiálne sa im nedá vyhnúť, lebo požiadavky na zdroje v riešení nie je možné dopredu určiť (súvisí to efektom horizontu, druhým hlavným problémom). Úlohou algoritmov a stratégií rozdelenia možností poskytovaných jedenotlivými komponentami je ,aby podobné efekty nastávali (keď už niekde musia nastať) čo najskôr v priebehu riešenia úlohy, keď je ešte vygenerovaná konfigurácia malá a riešenie sa nachádza ešte na veľmi vysokej úrovni abstrakcie. V takomto prípade sa totiž musí spätne meniť len minimum objektov, jednak pre to, že abstraktná konfigurácia sa ľahšie mení a pre to, že sa do zaradilo výslednej iba minimum komponent, tým pádom ani úplná zmena konceptu riešenia nemusí znamenať žiadne výrazné zníženie efektívnosti automatickej konfigurácie. Na príklad je dobré pri konfigurácii siete počítačovej čo najskôr zistiť, že jednotlivé body, ktoré sa majú prepojiť sú príliš riedke (veľke vzdialenosti (v priemere) medzi uzlami) a pre to použiľť iný spôsob sieťového spojenia, ktorý podobnú situáciu zvláda, ako túto informáciu zistiť až na základe toho, že všetky spôsoby, ako jednotlivé body poprepájať skončili prekročením max. dĺžky vedenia.

Globálne limity na kapacitu (napr. hmotnosť prístroja, investičné náklady,dostupný výkon a pod ) predstavujú najväčší problém pre alokačné algoritmy, lebo sú konzumované postupne všetkými komponentami a nie je ich možné nijakým spôsobom pridať. V praxi to znamená, že sa algoritmus musí spätne vrátiť v priebehu riešenia a pokúsiť sa nájsť iné riešenie, ktoré limit eventuálne spĺňa.

Efekt Horizontu je dôsledkom toho, že rozhodnutia pri konfigurácii sú robené postupne a hodnotiace kritériá, ktoré určujú nasledujúci krok hodnotia situáciu iba v lokálnom kontexte, obmedzujúc sa na pomerne malú množinu faktorov. Tento „krátkozraký“ prístup spôsobuje, že nie je možné vidieť  všetky dôsledky rozhodnutí, jednak pre to, že niektoré efekty vznikajú práve na globálnej úrovni a jednak pre to, že niektoré rozhodnutia, od ktorých sú závislé iné ešte neboli vykonané.

V ideálnom prípade bú jednotlivé rozhodnutia nezávislé a lokálne potimálne riešenie je totožné s globálne optimálnym .V skutočnosti však toto v drvivej väčšine prípadov nie je dodržané a vplyv jednotlivých rozhodnutí navzájom je pre celkovú potimalizáciu kľúčový. Nasledujúce príklady závislostí medzi rozhodnutiami ukazujú, prečo to tak je.

Vychádzajme z toho, že máme časti A a B, z ktorých je prvá „lacnejšia“ ako druhá.

1.)    Nedetegované požadované časti. komponenty požadované časťou A sú o mnoho drahšie, ako časť B aj s pre ňu potrebnými časťami spolu. Tento jav nemusí nastať priamičiaro, môže „pôsobiť“ až o niekoľko urovní rozhodovani ďalej, keď sa ukáže, že A zavádza nové požiadavky, ktoré pri výbere A /  B ešte neboli vyjedrené, a tým pádom nemohli byť ani zohľadnené.

2.)    Neočakávané konflikty v alokácii zdrojov. časti požadované A spotrebovávajú o niečo viac, ako časti potrebné pre B, to prostredníctvom prahového efektu spôsobí, že sa musia pridať ďalšie komponenty, čo spôsobí ďalšie predraženie riešenia obsahujúceho A.

3.)    Netestovaná kompatibilita.  V prípade, že tu sú ešte nezohľadnené požiadavky kladené komponentou, ktorá je kompatibilná s B, ale nie je kompatibilná s A.To znamená, že ak by sa v tejto časti zvolila B na miesto A, nemusli by sa v budúcnosti pridávať ďalšie časti a celok by bol lacnejší.

Tieto problémy by sa dali odstrániť iba zohľadnením vplyvu všetkých rozhodnutí na všetky, čo by ale viedlo k exponenciálnej náročnosti riešenia a rovnalo by sa v podstate exhaustívnemu hľadaniu najlepšieho riešenia v celom priestore riešení.

Vzhľadom na to, že to ne buď celkom nemožné vzhľadom na jeho nekonečnosť, alebo pri najmenšom značne nepraktické, je potrebné nájsť rozumný kompromis medzi požiadavkou na optimálnosť riešenia a hlĺbkou, do ktorej sa dopredu vyhodnocujú dôsledky zmien.

Hlavná časť príspevku. Ďalšie nadpisy pridajte podľa potreby. Obrázky číslujte a odkazujte sa na ne v texte. Odkazy (aj na literatúru) zvýraznite linkami. Píšte po slovensky a používajte diakritiku.

4 Záver

V tomto príspevku som sa snažil o niečo ako úvod to problematiky, popis , ktorý by po prečítaní mal bližšie priblížiť o čom sa v danej oblasti pojednáva. Zdroj (1) je taký rozsiahly (je to spôsobené hlavne komplexnosťou problémovej oblasti a podrobnosťou popisu), že by vystačil na niekoľko príspevkov podobného rozsahu, ako je tento, mohli by sa zaoberať zvlášť úvodom do problematiky ,jednotlivými systémami v ňom popísanými, prípadne časťou z toho, časťou z toho. Nechcel som však vynechávať informácie, ne ktoré sa potom odvoláva pri popise existujúcich systémov. Porovnenie systémov by zase človeku, ktorý do problematiky nevidí nič nepovedalo. Keďže si nerobím ilúzie o tom ,že by môj príspevok mohol poskytnúť informácie niekomu znalému problematiky (ten si to asi prečíta priamo v (1) ), rozhodol som sa napísať tento príspevok ako úvod do problematiky. Dúfam, že aspoň niekomu pomôže pri zorientovaní sa v oblasti.

 

 

Použitá literatúra

(1) … Mark Stefir , Introduction to knowledge systems ,  Magan Kaufman Publ. , 1995  

 

Znalostné systémy
Zimný semester 2000/2001