PROGRAM OG FILSTRUK1UR

8 .1 Beskrivelse av programstruktur

Figur 8 .3 beskriver program-strukturen i SAf<A.i>IM, som er i>AK\ uttrykt i prograimenngssptåket dIMUlA.

8 .1 .1 Statusti_la_STATUE.

Fila har følgende format:

Figur 8 .1 som viser sta cast n a

a n t fil er antallet torskjellige f ci seksti. :r som er opp­

retta. f^ inneholder noen opplysninger om det l-te forsøket, f ^ s format er

navn m n a vor d a l avorudd2 an tri

Figur 8 .2 som viser beskrivelse av status t i l lorson i i sta tu sfila STA1UE.

navn er navnet på forsøket, m er a ntallet argumentpar.

ri er antallet beslutninger, avbruddl og avbruaa2 inneholoer opplysninger om avbrudd under innlesing av navn på argumentpar eller veraitabell. antrr (antall regelfiler) forteller hvor mange forskjellige regelriler som er knytta t il hver

rorsøksfil. Det er lagra et S-regelsett på hver r e g e lf il.

Det første som skjer når SARA settes i gang er at OTAUJE lades inn i hurtighukonnielsen.

a n t fil

Ianttil

1 1 8

-«•LOAD

•F IN IS H

119 argumentpar som er komplementære henholusvis ufullstendige.

Deretter starter inniesinga av verai- og resulcattaoelien for beslutning etter beslutning.

Når argumentpar- opplysninger og verditabellen er lest inn må regelsettet derineres. så aerineres nver regel i regelsettet. Først oppgis gjennamsnitevekt og så selve reglene. I programmet tillater vi den som bruker systemet å definere maksimalt 10 s-regelsett tor nvert m ateriale. Hvert S-regelsett har maksimalt 10 S-regler.

Hvis brukeren v il detinere beskrankingei for noen av

begin .nteger array radpeker(l:ant) real array w (l:m )I

end;

For hver S-regel dannes det ei s lik gruppe, i programmet et SIMUIA-objekt. La oss si at situasjonen i er som på figur 8 .4 og at neste beslutning skal inn i grutpa.

120

-L _

r a d p e k e r

Figur 8 .4 . Illustrasjon av representasjonen av e i gruppe.

Det som nå skjer er at -japeKertant+l) settes liK raa- nummeret i verd inna trisa t i l beslutm nga som skal innlenmes i gruppa, og så økes ant med 1.

Når grupperinga er ferdig inneholder radpeker raanumrcne t i l a lle beslutningene i gruppa, ant forteller hvor mange beslutninger aette er.

Når iraterialet er gruppert kan oeregningene begynne.

8 .1 .4 Lfciine.ring_av e t n^tt regelsett.

Hvis brukeren v il oefinere et nytt regelsett gjfcnnanuør- es følgende uialog i SARA.

■ex SAKA.SIMj

skal du lese inn et nytt forsøk? neij hvilket forsøk v il du gjøre? navnj itDEFINE j

Når forsøket med det oppgitte navnet allereae er aefinert så er systemet nå klart t il å motta oetinisjonen av e t nytt

121

-regelsett. Dette gjelder ikke hvis det maksnnale antallet regelsett som kan d e n n e r e s ailereae er nåda. I dette t i l f e l l ­

Fila inneholder opplysninger om argumentparene, resu ltattabell, verditabell og navn på regelsettene.

tér forsøksfila er lest inn spør , >AKA hvilket regelsett v il au bruke? navngi

SARA leser så inn den fvia som inneholder regelsettet;. F ila er organisert etter gruppeinndelinga. For hver gruppe er regelen, a n t, radpeker, gjennomsnittsvekta, vent og beskrankingene oppgitt.

2

H

6

8

F N er en f o r k o r t e l s e or s a k f i l n u m m e r . F er en f o r k o r t e l s e

o r antfil.

F i g u r 8 . 6

L o a d S T A T U E

forstfk

o p p g

nav

r.ne

LOAD

Deflr.er

"ferdi

SFÎI: = A ?:*

Ar ♦

1

;

- 123

Mit både forsøks- og r e g e ls e ttiU a er lest inn er uttøringa av LOAD-koijiiiancioen ferdig.

8 . 1 . 6 Fl£t-nulighete£ t^ram_tii_Koninanaoplass_n Hvis v i nå "forstørrer" en del av tlyt-oiagramnet fra figur 8 .3 en del kan det tegnes slik som på figur 8.6. 1 u t ­ gangspunktet kan det se ut som det er 8 muligheter for fly t gjennom diagraiimet. Vi skal nå komnentere u is s e.

1. Meningsfylt, bruneren fortsetter d e n n e r in g a av et forsøk der definisjonen tidligere er avoruot.

2. M eningsfylt. Definering av et nytt forsøk.

Lykkes ikke nvis kapasiteten er sprengt.

6. Unulig. Havner i situasjon 2 siden en v il derinere et beregningene. Beregningene er oeskrevet i kapittel 5.

Modellen er skrevet som ei prosedyre og italt KurmiiL.

Denne kan startes når V og b er lest inn i hurtighuKommeisen og sakene er gruppert.

Beregningene skjer gruppevis. De viktigste variaolene i KOKREL er BDA, BDE og k3 som blir brukt t il å lagre verdiene for BDA, BDE og k3 rra n a p it te l 5. Videre verdimatrisa V, resultatiTBtrisa b, de teoretiske resultatene D, teilene E,

124

De viKtigste proseayrene i K01<HEL er tølgenoe:

Prosea>*.a bygkortao æ regner k3 når V og b er lest inn og legger den i arrayen k3. Prosedyra bestemvekt beregner

startvektoren wlt:1 når arrayen k3 er beregna og gjennomsnittsvekta foreligger og legger resultatet i w.

Prosedyra beregnres beregner innholdet i D når V og w er beregna. Beregnteil beregner E når D og o er g it t .

Iterasjv>nene blir utført t il stoppetoe tinge isene er opp­

f y lt . Disse er beskrevet i kapittel 5. Iterasjonene er litKe inplementert slik som de er Desnrevet i kapittel 5 . Alyoriuna søker ut aktuelle verdikorabinasjoner olant argunentene i ^teaet for å prøve a l l e . vekt. SARA normaliserer vektene s lik at gjennomsnittet scettroer med det oppgitte. Sa sjeKkes mot eventuelle ueskrankinger og beskranKingskrav oppfylles. Deretter beregnes F o . l .

(3) Trestruktur for generering av en redusert ijnpi ikasjonsgr a f

For å illustrere ett av de forslag t i l løsninger på systemutfornungsproblemer som jeg nar valgt så skal jeg vise nvordan jeg har implementert genereringa av en redusert implikasjonsgrac.

Jeg definerer to klasser. Klassen decis nar ett otijekt for nver beslutning. Klassen jjnp har ett objekt for hver implikasjon. Klassene er deklarert s l ik :

- 125

class d ec is;

begin ref (decis) vsub,nsub;

ref (unp) l is t e ; integer lopno;

end d ec is ;

class iinp;

Degin ref(decis) im pli;

ref(imp) neste;

end imp J

Vi danner et tre av Desiutm ngsobjektene. Treet er Dirwrt meo rot xalt rot ( r e t (d e c is )r o t ,) . Por a lle objekter, ooj , av klassen decis så peker obj.vsub på objektets venstre suutre og ouj.hsub på objektets høyre suotre. FOr a ile aecis-noaer gjelder at hvis noden har to lkke-tomne suDtrær, så er

noden. vsub. lopno^ noaen. lopno< noden.nsuu.lopno . l is te er ei lis te av objekter som refererer o e s l u t n i n ^ r . Hvis vi for to reslutninger som er representert i o d jI og o o j2 nar at

Ee'o d j1. lopno ^ FbODj2.lopno

så skal det når strukturen er leraig generert fin s e t element imp2 slik at

unp2 £ o b j l .l i s t e og unp2. unpli == o b j2.

impli peKer pa aen impliserte oeslutninga.

EKseinpex pa et lit e tre:

Aita at v i har beslutninger x ,y ,z og p uer

FBy-

^{° V * FV} FUz ^ ™ y

°9

^{FBp ^}

FBz 126 FBz

-Figur 8 .7 Binært tre som representerer unpiiKabjonsgraf

En r e f (o ec is )array topp(I:ant) refererer alle decis-noaer z som i<ke er reterert (implisert) av andre. Et sliK t nytt topp-element må legges inn hver gang det genereres en ny decis noae x , der FBy. Bi slik topp-noae må fjernes hver gang det legges inn en ny implikasjon FB^ FB^ og y er en

toppnode. Hvis vi skal legge inn en inklinasjon FB = p F a , og implikasjonene FB fb og FB = * FB fin n es, da

/ Z x z

skal implikasjonen EBi<= ^fBz fjernes tra <j|aten s lik at implikasjonene framkonmer ao lengst mulig v e i.

Hvis den i-te beslutninga i e i gruppe impliserer ac den j-te oeslutm nga i gruppa er forklart, så irarkerer v i aecte i en DQOj.ean array u n p l (l :a n t ,l :a n t ) , ved å sette

im p K i, j) :=true. Implikasjon er en tran sitiv relasjon og v i Kan bruke warshall-algontjra for å generere den transitive

tillukninga for impl.

Jeg lager ei ref(decis) proceaure look(x,lopnr) for å lete fram e i beslutning mea løpenunmer lopnr, eventuelt lete fram den noaun der noaen med løpenunmer lopnr skal settes inn.

x peker på det subtreet det j * a l letes i . prosedyra er rekursiv.

127

Ei prosedyre gunptre genererer impliKasjonsgraren. Ei prosedyre travtre traverserer treet og skriver ut

implikasjonene. Her er det verat å merke seg at hvis

128 umulige og urorxlarte oeslut- n in g e r .

skriver ut unpnicasjons- og motsigelsesgraf

" inkonsistente mengder av æ slu tn in g er

129

-Vj hat lagt ned svært lit e arbeia i å gjøre taoellene som kan v ises s i presentaole som mulig. Uesign Mac iKke vært prioritert.

8 . 1 . 9 Av3lutting_av ec_forsøK Komnai idoen

4 FINISH )

fra Konmandoplass II avslutter forsøket meo det aktuelle r eg el­

sette t. Etter konmandoen <omner spørsmålet vil du avslutte torsøket ?

opp på skjermen. Cm svaret er nei returnerer progranmet t il kommandoplass I og et nytt regelsett kan aetineres. Hvis svar­

et er ja og forsøket ikke er lagra tør så lagres d e t, Lixeaan nied regelsettet. STATOE oppdateres hvis UEFINt-Kommanaoen er brukt og ae aefinerte størrelsene skal b l i lagra.

8 .1 .1 0 Filstrukturen

Hele filstrukturen ser nå ut som på tigur 8.8.

8 .1 .1 1 KritiK<_dV programstrukturen (1) F e il s k n v in g veo innlesing.

SARA g ir ikke noe mulignet tor å gå tiloake å rette på f e i l ved registrering. Veu feilregistrering mi en r>are fort­

sette og så rette opp feilene når registreringene er feraig . Feil unoer registrering av navnene på argumentparene må rettes i SOS, som er et eaitenngsprogram vea DEC-10.Peil i verdi- taoellen kan rettes opp vea i fjerne beslutninga ineci feilen og så skyte inn ei beslutning på nytt mea ae riktige veraiene.

De to siste teknikkene er implementert ved CSAkA.SIM.

-1 3 0

-S T A T U E

A R S s t å r f o r a n t a l l r e g e l s e t t f i l e r . D e t t e e r e n l o k a l v a r i a b e l . Ar s t å r f o r a n t f i l . n e r e n f o r k o r t e l s e f o r n a v r..

F i g u r o-3 ? i l s t r u k t u r e n i S A R A .

131

-(2) Grupperinga av beslutningene forecas svært ennelt Qi styrke ved prograimiet er at grupperinga av

beslutningene skjer svøert enkelt, nemlig ved ett gjennomløp av verditabellen . Hvilke ueflutninger som er mea i gruppa bestemnes av radpekerarrayen. Ved omgruppering ænolcier en verditabellen og lager nye grupper etter de nye system-reglene med sine radpekere. Dermed trengs bare en utgave av

verditabellen.

8 .2 Efrdringer av representasjonen av et forsøksmaterlale

Det kan være ønskelig å foreta enaringer av representa­

sjonen av torsøksmaterialet. Vi nar laget et program

\_SAKA.bU-l som tar seg av de mest presserende oehov for endr ing­

e r . Prograimet har egentlig seks funksjoner, uet er å -fjerne et forsøk,

-fjerne et regelsett -fjerne beslutninger, -Ljerne argumentpar, -skyte inn beslutninger og -skyte inn argumentpar.

Når CSAKA.SIM har operert på et forsøk er tid lig ere de­

finerte regelsett for forsøket gått tapt. Vi har valgt aenne løsninga på grupperingsproblemet som oppstår etter e i enuring fordi alle typer endringer av et forsøk kan virke inn på grupperinga av det nye forsøket. I stedet for å skrive

progranmer for endringer av reglene, så velger vi å la orukeren definere disse h elt på nytt. (Jn bruken av systemet skulle t il t a , v il det lønne seg å skrive endringsprogrammer for reglene også.

Brjkeren kan velge ora han v il Devare d e r forsøket han skal endre i tille gg t il det endreae rorslaget som a l l t i a Dlir bevart.

132

-8.2 .1 Fj rruny_ay t_forsøk Ved å gjennomføre a l l o g e n

hvilket forsøk v il au endre? navn ; --- 1 v il du fjerne hele forsøket? j a ^

så fjernes forsøket fra sta tu sfila STATUE. Brukeren må sjøl fjerne de t u e n e som er definert i tilknytning t il forsøket veu å bruke UELETTE-funksjonen på nonitornivå i DBC-10.

8.2 .2 Fjer ng_av reijelsett

Når det er definert 10 regelsett t il et forsøk så kan aet ikke defineres fle r e . Por å tå d efin ert et nytt må dertor minst et regelsett fjernes. Det skjer vea at Drukeren gir Komnandoen DELETER l ^jAHA. På spørsmålet

nvilket regelsett v il du fjerne?

må brukeren oppgi navnet på t ila for det s ettet nan v il fjerne.

8 . 2 . 3 Fjernu.g av beslutninger

Brukeren må oppgi navn på forsøket som skal enares. Når CSAKA skriver u t * må brukeren skrive

» DELgnJ litapenrl, løpe nr 2... »

det v il si a lt som står over streken. La D iir oeslutningene (verdier og resultat) nea de oppgitte løpeniuimer fjerna og de nødvendige endringer i STAUIE u tfø rt. Uet kan ikke fjernes flere beslutninger om gangen enn så mange løpenumre en får plass t i l på ei l in je .

8 .2 .4 Fj<jrning_av ar^umentpar

Når brukeren har oppgitt nvilket fors«« h«ui v il enare, og CSARA s k r i v e r # , så SKriver nan

y pKrJTIEF argumentparrtavnl, arguinentparr>avn2, ... * ) Argumentparene olir da fjerna fra a rg urnen ti>ar iis ta og verditabellen. STATUE b lir oppdacert.

133

-8.2 .5 innskytuig_dv oeslutninger Når systemet skriver * skriver brukeren

* INSEKPC^

Brukeren tår spørsmålet

Hvor mange beslutninger skal du lese inn?

Etter å na oppgitt antallet inå han registrere beslutningene som beskrevet under detinering av et forsøk i 8 . 1 . 3 . STATUE opp­

dateres.

8.2 .6 Innskyting_ay nye argumeritpar ved å skrive

INSEKTF ^

får orukeren spørsmålet

hvor mange nye argumentpar vil au bruke?

Når brukeren svarer med antallet må han g i navn på parene, definere parene og lese inn veraier for argumentparene. Dette tilsvarer agentliq å aetxnere et rorsøk mea n æ slu tn in g er og itf= antallet nye argumentpar. STATUE oppdateres.

8 .2 .7 Sammensatte tunksjoner

Bi kan være interessert i å sp litte argumentpar eller slå argumentpar sammer.. La oss kalle funksjonene SPLITF og MEKIEF.

SPLITF = UfclLETEF(l) + INSEKTF(2) . MEHGEF = DELEIEF(2) + IN S E K If(l).

Vi har her brukt notasjonen DEI£TEF(2) for å fortelle at 2 argumentpar fje rn e s. Likedan for INSEKTF.

134

-Sluttord:

Det er ennå mange uløste problemer. A rinne en minuikil generator lor e t konsistent materiale er ett proolew. Et annet er å finne ut om det er et hardt proolem å avgjøre om et materiale er konsistent eller ikke. Og er det et harat problem å finne m in(F)? Konvergens- "garanti" for minlF)-aigoritma må bestenmes.

Men v i har oppnåoa noe også. EJi matematisk representasjon av beslutningene er utvikla på grunnlag av ju ridisk funderte antakelser. I sats 4 .7 hac vi påvist en ekvivalens mellom utledninger og lineær avhengighet for veraiene på

beslutningene. I sats 4 .1 3 nar vi uttrykt en nøavenaig og tilstrekkelig oetingelse for inKonsistens i et m ateriale. I sats 4 .1 5 har vi påvist at e i optimalt konsistent mengae er identisk med komplementet t i l e i minimal kutt-mengoe. I sats 4 .9 har vi v is t at en minimal jenerator danner en Ddais (som definert i 3 .7 .7 ) for et optimalt Konsistent m ateriaie. ixden utledninger kan fortolkes som presedens, i jurioiSK torstana, kan påvising av en basis for utledninger v ise seg a få stor nytteverdi. I sats 4 .1 9 har vi vist at om M er m inim an inkonsistent så er j n j i m + 1 . Ideer t il "dybde-rørst"

ut-Lconinger er g i t t .

Ei algoritme for minlFJ-proolemet er besKrevet. Likeaan noen kriterier for konsistens og m o n s is t e n s . P a r a lle llite t, dominansegenskaper 09 statistiske mål er viktigst av det deskriptive verktøyet som er utv iklet. Vi nar også utviKia en

test for å undersøke om et argument er uten innvirkning på resultatene.

135

-APPENDIKS A

(1) Lineære diskriminant-funksjoner

E)e metodene jeg skal skissere har jeg tra Du_ia 6 bart.

min(F) problemet løses av SIMPI£X-algoritma når min(F) = 0 . Iteonen bak denne - og algoritma sjø l - linnes i svært mange tekstbøker om lineærprogrannfering.

Jucj & Hart diskuterer lineære diskriminantfunksjoner tor klassifikasjonsrorm ål. Problemet med å finne lineære diskrim- inantfunksjoner s t il l e r ae som problemet å minunalisere tor- s kjellig e kri terlefunksjoner. Formålet je r e s , som vårt, er å finne diskriminantfunksjoner som klassitiserer objektene, (beslutningene hos o s s ) , godt.

Duda & Hart beskriver ulike teknikker, som jeg skal gjengi svært grovt:

"Graoient oescent" prosedyrer.

Vi skal finne ei løsning på VW>0. Vi ønsker å finne en

kriteriefunksjon J(w ) som er minimert av en løsningsvektor. Den grunnleggende "descent" algoritma er s l ik :

Velg w<°> v ilk å r lig . Bereqn

V j

(w) w(k+l) . W(K)

^ er en skalar som bestemmer skr i tt-s tiar reisen.

Newtons algoritme.

u (k+l) = w (k) _ b ' j7 j (m | , der D. =

Algoritma g ir v anligvis nedre torbearing per iterasjon enn generell descent algoritma, men er beregningsmessiy dårligere.

D kan være singulær og det tar mye tid å beregne D-* .

"perceptron" kriteriefunksjon.

Duda & Hart sier at den mest opplagte k r ite n efu n ksjonen for å løse ulikhetene

V-w> 0

er å la J(w) = F (w ). Men siaen F er stykkevis konstant er den ikke særlig velegna t il gradienL søk.

136

r^rj3k er konstant kalles algoritjna "fixed lncrement" - tiltellet.

Hvis materialet er lineært separabelt så v il algoritma gi

Den grunnleggende descent algoritma konvergerer nir er en positiv konstant eller avtar som l/k eller øker som k.

Denne krltenetunksjonen leder til aenne gr jnnleggenue descent algoitma:

ij7

Ei algoritme som braiandler oeslutningene sekvensielt er Widrow-Haff algoritma:

1JB

-w1K> = v+ er v's pseuuoinvers

Hvis materialet er linasrt separabelt og hvis i K l , s«'i v il Ho-Kashyap algoritma finne løsninga mea e n d e n g måi.je step.

U n m r proqc unnering.

A finne nun(F) hvis im n(F)> 0 er ikke et lineært program­

m e n ngsproblem. A . inne qiin(E) er d e t. Hor 5 unngå løsninga w = 0 innføres marginer b .

Minimaliser z = ^ t nåe v ^ w + t 4 > c L> 0

minimaliserer sujmen av slakk-variablene for g itte marginer w i 0

13»

-APPENDIKS B: teferanser

Bing, Jon, "Fra problem t il resultat", jussens venner, Ih iv e r s it e t s f o n a y e t , nette 1 1975 Borchgrevink, Mette og Hansen, Johs, SAxa-rapporten,

skriftserien jus og edb 44,

institutt Cor privatrett, avdeling tor eut>, 1JU0

□uda, Rictiard O . , og Hart, Peter E . , "Pattern Classicication and Scene A n a ly s is ", John W iley , New York, l i7 3 R3Ckafellar, K. T . , "Oxivex Analysis", Princeton lluversity

Press, 1970

T h r aii, R. M ., "Vector Spaces and Matrices", Jorui W iley , New York, 1957

140

-APPENDIKS C Innholasliste:

1 INNLEDNING 3

1 .1 Bakgrunn for oppgaven 3 1 .2 Terminologi 4

1 .3 Hva slags problemer Skal løses? 6

1 .4 Hvordan v i tenker oss systrmet tilpasset og brukt 7 1 .4 .1 Beslutningssystemet 7

1 .4 .2 Saxsbenandlersystemet 7 1 .4 .3 Analysesysternet 7

2 REPh^bht/rAbJON AV- UG ANfAKELSKk Un BESLUTNINGENE 11 2 .1 presentasjon av beslutningene 11

2 .2 Matematiske modeller av beslutninger 17

2 .2 .1 R illstenaig matematisk inouell av besljtningene meo im plisitte vekter 17

2 .2 .2 Ufullstendig matematiSK modell 17 2 .3 Antanelser om materialet 19

2 .3 .1 Systemproolemer i foroinaelse mea antakelsene 19

3 MAItMATISKE DEFINISJONER 27

3 .1 V erdi, vekt, teoretisn resultat, forkiaring av beslutninger og feilen for beslutninger 27 3 .1 .1 Veraien t n argumentene 27

3 . 1 . 2 Veitene på argumentparene 28 3 .1 .3 TteoretisK resultat for oesiutningene iti 3 .1 .4 Forklaring av ei reslutning 29 3 .1 .5 Efeixen for beslutninger 30

3 .2 Konsistente mengder av æ slu tn in ger 3U 3 .2 .1 Konsistent mengde av æ slu tn in g er 30

3 .2 .2 Maksimalt nonsistent mengae av æ slu tn in g e r 30 3 .2 .3 optimal mengae av Konsistente oeslucninger 31 3 .3 Inkonsistente mengaer av oesiutninger 31

3 .3 .1 Minimale inkonsistente mengaer av æ slu tn in g er 31

141

3 .8 .1 Implikasjoner mellom forklaringer 46 3 .8 .2 Motsigelser inelloin oeslutninger 47

3 .8 .3 Beslutning i uforklart impliserer oeslutning j forklart 47

3 .8 .4 Spesielle parallellitetsrelasjoner 49 3 .8 .5 Parallellitetsanalyse av et materiale 52 3 .8 .6 En måte å representere parallellitetsrelasjonene

på i én grar 52

3 .9 Partisjon av materialet 55

3 .9 .1 Konsistente partisjoner av materialet 55 3 .9 .2 Minimal konsistent partisjon av materialet 5a

In document ET EDB-SYSTEM FOR (sider 122-146)