Zusammenfassung Softcomputing (c) 2003-07-13 F.M. Suchanek http://www.mpi-inf.mpg.de/~suchanek/personal/texts/summaries/sc.txt Dieses ist die Zusammenfassung des Kurses "Softcomputing" von Dr. Barbara Hammer an der Universitaet Osnabrueck im SS 2003. Da dieser Text ASCII-Graphiken enthaelt, sollte er ___ | nur mit einer Festschriftart (zB Courier New) benutzt / \ | / und ausgedruckt werden. Wenn die Schriftart in ( ) |< Ordnung ist, erscheint rechts ein OK. \___/ | \ Durch das Weiterlesen akzeptiert der Leser, dass der Autor keinerlei Verantwortung fuer die Richtigkeit oder Vollstaendigkeit dieser Zusammenfassung uebernimmt. Wenn jemand einen Fehler gefunden hat, so waere ich fuer eine Mail dankbar. Nur so habe auch ich etwas von der Veroeffentlichung dieser Zusammenfassung. Meine E-Mail-Adresse ist f.m.suchanek@zweb.de, wobei das 'z' aus der Adresse geloescht werden muss. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Intro ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ s.a. algebra.txt fuer theoretische Hinterguende s.a. analysis.txt fuer theoretische Hinterguende Menge: Eine ungeordnete Ansammlung nicht identischer Elemente. M = {x1, x2, ..., xn} ist die Menge dieser Elemente M = {x | f(x) } ist die Menge aller x, fuer die eine Bedingung f(x) gilt Teilmenge einer Menge M: Eine Menge T, von der jedes Element auch in M ist. Dieses gilt auch im Falle T=M. T < M Obermenge einer Menge M: Eine Menge O, von der M eine Teilmenge ist. O > M Erlaubt man auch Gleichheit, so schreibt man O >= M. Maechtigkeit einer Menge M: Die Anzahl der Elemente von M. |M| = n Reelle Zahlenmenge: Die Menge aller rellen Zahlen, mit R bezeichnet. Natuerliche Zahlenmenge: Die Menge aller natuerlichen Zahlen, mit N bezeichnet. Klasse: Eine Menge aehnlicher Objekte. Beispiel: Haeuser, Baeume, Wale... Grundbereich: Eine grundlegende Menge, von der Teilmengen betrachtet werden, z.B. eine Klasse. Intervall: Eine Zahlenmenge M, zu der es zwei Grenzen a und b gibt, sodass M={x | x >=a & x =< b} gilt. Man schreibt M=[a;b]. Sollen eine Grenze nicht dazu gehoeren, so dreht man die entsprechende Klammer nach aussen. // Was dann immer sehr unschoen nach Bracket-Mismatch aussieht... Funktion: Eine Abbildung, die jedem Element einer Definitionsmenge genau ein Element einer Bildmenge zuordnet. Schreibweise: Funktion:Definitionsmenge -> Bildmenge Damit ist der Begriff "Funktion" so allgemein, dass z.B. auch eine Saftpresse eine Funktion ist: Presse ich eine Zitrone, kommt Zitronensaft heraus, presse ich eine Orange, kommt Orangensaft heraus. // Diese Funktion ist also sogar injektiv! :-) Approximation einer Funktion: Die naeherungsweise Berechnung ihrer Werte. Funktionenklasse: Eine Menge von Funktionen. Approximationsvollstaendigkeit einer Funktionenklasse: Die Eigenschaft, dass sich fuer jede beliebige Funktion f eine Funktion g in der Funktionenklasse findet, sodass g f approximiert. Stelligkeit einer Funktion: Die Anzahl ihrer Argumente. Bild eines Elementes unter einer Funktion: Das Ergebnis, welches die Funktion fuer dieses Element liefert. Urbild eines Elementes y unter einer Funktion f: Ein Element des Definitionsbereichs von f, dessen Bild y ist. Unaere Funktion: Eine einstellige Funktion. Statt f(a) schreibt man auch af. Nullstelle einer Funktion f: Ein Wert x mit f(x)=0. Lineare Funktion: Eine Funktion f:R^n -> R^m, deren Funktionswert fuer eine Eingabe durch eine Gleichung beschrieben wird, in der die Eingaben nur in einfacher oder nullfacher Potenz vorkommen. Beispiel: f(x,y,z) = 3*x+4*y Funktionsgraph einer Funktion f: Ein Koordinatenkreuz, in dem auf der waagerechten Achse die Elemente des Definitionsbereichs aufgetragen sind und auf der senkrechten Achse die Elemente des Wertebereichs. Man zeichnet nun fuer jedes x aus dem Definitionsbereich einen Punkt an der Stelle (x;f(x)) ein. Operation: Eine zweistellige Funktion. Statt f(a,b) schreibt man auch a f b. Beispiel: '+' ist eine Funktion, die zwei Zahlen auf ihre Summe abbildet. Statt "+(a,b)" schreibt man auch "a + b". Reflexivitaet einer Operation f: Die Eigenschaft, dass f(x,x)=1. Kommutativitaet einer Operation f: Die Eigenschaft, dass f(x,y)=f(y,x). Assoziativitaet einer Operation f: Die Eigenschaft, dass f(a,f(b,c)) = f(f(a,b),c). Assoziative Operationen koennen klammerfrei geschrieben werden: a f b f c oder f(a,b,c). Distributivitaet der Operation f1 mit f2: Der Sachverhalt, dass f1(a,f2(c,d)) = f2(f1(a,c), f1(a,d)). Beispiel: + ist mit * distributiv, da a*(b+c)=(a*b)+(a*c). Idempotenz einer Operation f: Die Eigenschaft, dass f(a,a)=a. Vereinigung: Die Operation \/, die zu zwei Mengen diejenige Menge liefert, die alle Elemente aus M1 und alle Elemente aus M2 enthaelt. M = M1 \/ M2 Die Vereinigung ist idempotent, kommutativ und assoziativ. Schnitt: Die Operation /\, die zu zwei Mengen diejenige Menge liefert, die diejenigen Elemente enthaelt, die sowohl in M1 als auch in M2 sind. M = M1 /\ M2 Der Schnitt ist idempotent, kommutativ und assoziativ. // Anmerkung: Wir werden zu verschiedenen Mengen verschiedene Schnitte // definieren. Dieses ist der Standard-Default-Schnitt. Inversion: Die Funktion, die zu einer Menge M alle Elemente des Grundbereichs liefert, die nicht in M sind. Man schreibt Mc. Involution: Die Tatsache, dass Mcc=M. Identitaetseigenschaft: Die Tatsache, dass die Vereinigung einer Menge mit dem Grundbereich wieder den Grundbereich ergibt: A \/ X = X Ebenso die Tatsache, dass der Schnitt einer Menge mit der leeren Menge die leere Menge ergibt: A /\ {} = {} deMorgan-Beziehung: Die Tatsache, dass (A /\ B)c = (Ac \/ Bc) (A \/ B)c = (Ac /\ Bc) Eselsbruecke: Das 'c' wirkt sich auf alle Komponenten in den Klammern aus: Es macht A zu Ac, es dreht den Operator um und es macht B zu Bc. Gesetz vom Widerspruch: Die Tatsache, dass der Schnitt einer Menge mit ihrem Komplement die leere Menge ergibt. A /\ Ac = {} Gesetz des ausgeschlossenen Dritten: Die Tatsache, dass die Vereinigung einer Menge mit ihrem Komplement den Grundbereich ergibt. A \/ Ac = X Folge, Tupel: Geordnete Zusammenfassung von Objekten. v = (v[1], v[2], ... v[n]) Algorithmus: Eine endliche Folge von Anweisungen. Liste: Ein Tupel, zu dem Elemente hinzugefuegt werden koennen und aus dem Elemente entfernt werden koennen. Dimension eines Tupels: Die Anzahl seiner Elemente. Man schreibt dim(x). Kartesisches Produkt der Mengen M[1]..M[n]: Die Menge aller Tupel (m[1], m[2], ... m[n]) aller m[1] aus M[1], aller m[2] aus M[2] etc. M x N = { (m1, n1), (m1, n2), ... } M^n = M x M x ... x M Beispiel: {1,2} x {a,b,c} = { (1,a), (2,a), (1,b), (2,b), (1,c), (2,c) } Punkt, Vektor: Element einer Menge, welche die Axiome des Vektorraums erfuellt. Hier: Ein Tupel aus reellen Zahlen. v = (v[1], v[2], ... v[n]) mit v[i] aus R v aus R^n Matrix: Ein Tupel aus Vektoren derselben Dimension. M = ( (M[1][1], M[1][2], ... M[1][n1]), ... (M[n2][1], M[n2][2], ... M[n2][n1])) Ist n2=1 oder n1=1, so fasst man die Matrix als Vektor auf. Quadratische Matrix: Eine Matrix M mit dim(M)=dim(M[1]). Diagonale einer quadratischen Matrix M: Die Menge {M[i][i] | i=1..dim(M)}. Diagonalmatrix: Eine Matrix, bei der alle Elemente bis auf die Diagonale 0 sind. Transponierte einer Matrix M: Die um die \-Achse gespiegelte Matrix t(M) mit t(M)[i][j]=M[j][i]. Damit ist auch die Transponierte eines Vektors definiert: In Formeln werden die Komponenten von Vektoren uebereinander geschrieben. t(x) ist damit der Vektor x, bei dem die Zahlen nebeneinander geschrieben sind. Orthogonale Vektoren: Zwei Vektoren x und y, fuer die t(x)*y=0. Dieses entspricht der intuitiven Vorstellung von Orthogonalitaet. Produkt zweier Matritzen A und B: Die Matrix C mit C[i][j] = SUM k=1..dim(A[1]) A[i][k]*B[k][j] Da Vektoren nur spezielle Matritzen sind, ist damit auch das Produkt von Vektor und Matritze definiert. Das Produkt ist nur definiert, wenn dim(A[1])=dim(B). positiv definite Matrix: Eine Matrix M, bei der fuer alle Vektoren x gilt t(x)*M*x > 0. Symmetrische Matrix: Eine Matrix M mit M=t(M). Metrik: Eine positiv definite symmetrische Matrix. Koordinate eines Vektors: Eines seiner Elemente. Summe zweier Vektoren: Der Vektor aus den Summen ihrer Elemente. Differenz zweier Vektoren: Der Vektor aus den Differenzen ihrer Elemente. Vielfaches eines Vektors v: Der Vektor, der sich durch Multiplikation aller Komponenten von v mit einer reellen Konstante ergibt. Linearkombination: Eine Summe von Vielfachen von Vektoren. Die Konstanten der Vielfachen heissen "Koeffizienten". Linear unabhaengige Vektoren: Eine Menge von Vektoren, deren Linearkombination nur dann den Vektor (0,0,...) ergibt, wenn alle Koeffizienten 0 sind. Arithmetisches IF: Eine Funktion f:{true, false} * R * R -> R mit f(true,x,y)=x und f(false,x,y)=y. Wird meist infix mit den Zeichen '?' und ':' geschrieben. Beispiel: maxvalue = ( (a>b) ? a : b) // Diese Funktion dient hier lediglich zum Verfassen dieses Textes Summenzeichen: Das grosse Sigma, hier "SUM". Mit "SUM i aus M a(i)" ist die Summe aller a(i) gemeint, wobei i alle Elemente von M durchlaeuft. a ist dabei eine Funktion von M in die reellen Zahlen oder einfach ein mathematischer Ausdruck, in dem i vorkommen kann. Beispiel: SUM i aus {1,2,3,4} 3*i = 3*1 + 3*1 + 3*2 + 3*4. Ist M eine Folge natuerlicher Zahlen von m bis n, so schreibt man auch SUM i=m..n a(i). Produktzeichen: Das grosse Pi, hier "PROD". Mit "PROD i aus M a(i)" ist das Produkt aller a(i) gemeint, wobei i alle Elemente von M durchlaeuft. sqrt: Die Wurzel-Funktion, die diejenige Zahl liefert, die mit sich selbst multipliziert das Argument ergibt. min: Die Funktion min(a,b) = (a>b)?b:a. max: Die Funktion max(a,b) = (a>b)?a:b. abs: Die Funktion, die einen Vektor x=(x[1],...x[n]) abbildet auf abs(x) = sqrt( SUM i=1..n x[i]^2 ) Fuer eindimensionale Vektoren (d.h. reelle Zahlen) z heisst das: abs(z) = (z>0)?z:(-z). Abstand zweier Vektoren x und y bezueglich einer Metrik M: Der Wert sqrt(t(x)*M*x). Anschaulich formuliert verformt eine Metrik den Raum: Ellipsen koennen Kreise werden, weil alle Punkte auf der Ellipsenlinie durch die geaenderte Abstandsberechnung rein rechnerisch ploetzlich gleichen Abstand zum Mittelpunkt haben. Abstand zweier Vektoren x und y: Der Abstand bezueglich der Diagonalmetrik mit nur 1 in der Diagonale. Dieses entspricht einfach dem gewohnten euklidischen Abstand abs(x-y). %: 1/100. Relation: Eine Teilmenge des kartesischen Produktes zweier Mengen. Fuer "(a,b) ist Element der Relation r" schreibt man auch "r(a,b)" oder "a r b" oder "(a,b) Element von r". Beispiel: Die Relation ">" ist die Menge aller Paare von reellen Zahlen, bei denen die erste Komponente groesser ist als die zweite, es ist > = { (1,0), (27.3,12.5), (17,-12), ... } und man schreibt: >(3,2) oder 3 > 2 oder (3,2) Element von >. Symmetrische Relation: Eine Relation R, fuer die gilt: R(x,y)=R(y,x). endliche Menge: Eine Menge, deren Maechtigkeit nicht unendlich ist. abgeschlossene Menge: Eine reelle Menge, in der sich eine Zahl finden laesst, die groesser ist als alle anderen Zahlen. Beispiel fuer eine nicht abgeschlossene Menge: M = { -1/n | n ist natuerliche Zahl } Diese Menge ist unendlich und fuer jedes Element aus M laesst sich immer ein anders Element findes, was noch groesser ist. // Fuer eine professionellere Definition siehe analysis.txt beschraenkte Menge: Eine Menge von Vektoren, zu der es einen Vektor v gibt, sodass fuer alle x der Menge gilt: abs(x) < abs(v). Auf eindimensionale Vektoren (reelle Zahlen) uebertragen heisst das: Alle Zahlen der Menge liegen in einem endlichen Bereich. kompakte Menge: Eine Menge, die abgeschlossen und beschraenkt ist. Maximum einer Menge M: Die groesste Zahl aus M. Das Maximum von nicht abgeschlossenen Mengen ist nicht definiert. Man schreibt max(M) = x. Minimum einer Menge M: Die kleinste Zahl aus M. Das Minimum von nicht abgeschlossenen Mengen ist nicht definiert. Man schreibt min(M) = x. Supremum einer Menge M: Die kleinste Zahl, die groessergleich allen Elementen von M ist. Wenn M abgeschlossen ist, ist das Maximum gleich dem Supremum. Man schreibt sup(M)=x. Ist M leer, so wird der kleinste sinnvolle Wert zurueckgegeben, in den folgenden Anwendungen also 0. Infimum einer Menge M: Die groesste Zahl, die kleinergleich allen Elementen von M ist. Man schreibt inf(M)=x. stetige Funktion: Eine Funktion f:M->R, fuer die man an jeder Stelle a aus M fuer ein vorgegebenes eps>0 ein delta>0 finden kann, sodass |f(a)-f(x)|< eps fuer alle x aus [a-delta;a+delta]. Mit anderen Worten: Die Funktion springt nicht. Steigung einer Funktion f:R^n -> R fuer x in Dimension i: Der (Grenz-)Wert ( f(x[1],x[2],...x[n]) - f(x[1],x[2],... x[i]+h, ... x[n]) ) / h fuer h gegen 0. Meist gibt man statt der Nummer der Dimension den Namen der i-ten Eingabe-Komponente an. Ableitung einer Funktion f nach einer Dimension i: Die Funktion f', die zu jedem Eingabewert x die Steigung der Funktion f an dieser Stelle in die Dimension i berechnet. Ist statt der Dimension der Name der i-ten Eingabe-Komponente gegeben (z.B. "z"), so spricht man von der "Ableitung von f nach z" und schreibt df/dz. Fuer den berechneten Wert fuer einen Eingabewert x schreibt man df(x)/dz. Bildlich gesprochen sagt df(x)/dz aus, wie stark sich f(x) veraendert, wenn man an z ruettelt. Ableitungsregel: Eine Regel zur Berechnung der Ableitung einer Funktion nach einer Groesse. d(f(x)+g(x))/dx = df(x)/dx + dg(x)/dx d(f(g(x)))/dx = df(g(x))/dx * dg(x)/dz "Kettenregel" df(g1(x),...gn(x))/dx = df/dg1 * dg1(x)/dx + ... + df/dgn * dgn(x)/dx "mehrdimensionale Kettenregel" d(c*f(x))/dx = c*df(x)/dx fuer Konstanten c dg/dx = 0 fuer von x unabhaengige Terme g differenzierbare Funktion: Eine Funktion, zu der man an jeder Stelle x die Steigung in jede Dimension angeben kann. Gradient einer Funktion f an der Stelle x: Der Vektor der Steigungen an dieser Stelle x in alle Dimensionen: Df = (df(x)/dx1, df(x)/dx2, ... df(x)/dxn ) Integral einer reellen Funktion f auf dem Interval [a;b]: Die Flaeche unter dem Funktionsgrpahen von f im Intervall [a;b], wobei Flaechen von Teilintervallen mit negativem Funktionswert negativ in die Rechnung eingehen. // Fuer eine genauere Definition siehe analysis.txt Minimum, lokales Minimum einer Funktion: Ein Eingabewert, fuer den die Funktion niedrigere Werte liefert als fuer die Eingabewerte um das Minimum herum. Die Steigung in einem Minimum ist 0, da es zu beiden Seiten nach oben geht. Die Steigung der Ableitung im Minimum ist meist positiv, da die Steigung der Funktion meist zunaechst negativ ist und dann positiv. globales Minimum: Ein Eingabewert, fuer den die Funktion ihre kleinstmoegliche Ausgabe hat, also das beste Minimum. Maximum, lokales Maximum einer Funktion: Ein Eingabewert, fuer den die Funktion hoehere Werte liefert als fuer die Eingabewerte um das Maximum herum. Monoton fallende Funktion: Eine Funktion mit nicht-positiver Ableitung. Vergleich zweier Funktionen: Der Vergleich aller ihrer Funktionswerte. Beispiel: Mit f1(x) = 2+x f2(x) = 3+x^2 gilt: f1 < f2 Summe der Intervalle [a;b] und [c;d]: Das Intervall [a+c;b+d]. Dieses Intervall umschliesst alle moeglichen Ergebnisse der Summe eines Elementes des ersten Intervalls mit einem Element des zweiten Intervalls. Produkt der Intervalle [a;b] und [c;d]: Das Intervall [min({a*c, a*d, b*c, b*d}); max({a*c, a*d, b*c, b*d})]. Dieses Intervall umschliesst alle moeglichen Ergebnisse des Produktes eines Elementes des ersten Intervalls mit einem Element des zweiten Intervalls. Mittelwert einer reellen Menge M: Die Summe aller ihrer Elemente, dividiert durch die Anzahl der Elemente: mean(M) = SUM i=1...|M| M[i] / |M| e: Die Naturkonstante e=2.718281828459045. Graph: Ein Tupel (K,R) aus einer Menge K und einer Relation R auf K. Die Elemente der Menge heissen "Knoten". Die Relation heisst "verbunden mit". Graphen werden haeufig visualisiert, indem man alle Knoten als Kreise zeichnet und fuer jede Verbindung einen Pfeil zeichnet. s.a. gc.txt ("Graphes et Complexite", auf Franzoesisch) Ungerichteter Graph: Ein Graph, dessen Relation symmetrisch ist, d.h. wannimmer ein Knoten x mit einem Knoten y verbunden ist, so ist auch y mit x verbunden. In einem solchen Graphen heissen die Verbindungen "Kanten". Weg in einem Graphen: Eine Folge seiner Knoten, wobei jeder Knoten mit seinem Nachfolger verbunden ist. Zyklus in einem Graphen: Ein Weg mit mehr als einem Knoten, dessen Anfangs- und Endknoten uebereinstimmen. zyklischer Graph: Ein Graph, der einen Zyklus enthaelt. voll verbundener Graph: Ein Graph, in dem jeder Knoten mit jedem anderen verbunden ist. Graph mit Distanz: Ein Graph, in dem jeder Verbindung eine positive reelle Zahl zugeordnet ist, der Abstand. Laenge eines Weges in einem Graphen mit Distanz: Die Summe der Abstaende seiner Verbindungen. Baum: Ein Element oder ein Element mit mehreren (Unter-)Baeumen. Binaerer Baum: Ein Baum, der keine Unterbaeume hat oder 2 binaere Unterbaeume. Blatt: Ein Unterbaum, der keine Unterbaeume hat. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Fuzzymengen ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Softcomputing: Die Disziplin, die sich beschaeftigt mit * Genetischen und evolutionaeren Algorithmen (hier behandelt) * Fuzzy Systemen (hier behandelt) * Neuronalen Netzen (siehe nn.txt) Softcomputing erlaubt es, unscharfe Probleme zu loesen. Charakteristische Funktion auf einem Grundbereich X: Eine Funktion, die zu einem Element aus X eine reelle Zahl aus [0;1] liefert. Chi:X -> [0;1] FM, Fuzzymenge A mit charakteristischer Funktion Chi[A]: Eine ungeordnete und unscharfe Ansammlung von nicht-identischen Objekten, deren Zugehoerigkeitsgrad zur Ansammlung durch Chi[A] gegeben ist. // Anmerkung: Der Begriff "Fuzzymenge" ist nirgends definiert. // Es heisst lediglich "Eine Fuzzymenge ist gegeben durch Chi[A]". // Das wirft die Frage auf, ob eine Fuzzymenge nicht einfach ihre // charakteristische Funktion *ist* // (s.a. http://www.mpi-inf.mpg.de/~suchanek/personal/philo.txt) // Um aber dem Sprachgebrauch gerecht zu werden, sind in dieser // Zusammenfassung Fuzzymenge und Funktion verschieden. Beispiel: Die Klasse aller Lebewesen kann als Fuzzymenge L modelliert werden: Chi[L]( hund ) = 1 Chi[L]( katze ) = 1 Chi[L]( stein ) = 0 Chi[L]( koralle ) = 0.5 Eine Fuzzymenge kann veranschaulicht werden durch den Funktionsgraphen von Chi. ^ 1.0 _| x x 0.5 _| x 0.0 _|____x_________________________\ stein hund katze koralle / Zugehoerigkeit eines Elementes x zu einer Fuzzymenge A: Der Wert Chi[A](x). Ein x mit Chi[A](x)=1 heisst "voll zugehoerig", ein x mit Chi[A](x)=0 heisst "nicht zugehoerig". crispe Menge, klassische Menge: Eine Menge. Der Begriff dient der Unterscheidung zu Fuzzy Mengen. Es zeigt sich, dass crispe Mengen spezielle Fuzzymengen sind, deren charakteristische Funktion nur auf 0 und 1 abbildet. Trapezfunktion: Eine Funktion f, die gegeben ist durch 4 reelle Zahlen a,b,c,d und die Gleichung f(x) = (x < a) ? 0 : (x < b) ? (x-a)/(b-a) : (x < c) ? 1 : (x < d) ? (d-x)/(d-c) : 0 _^ 1.0 _| _________ 0.5 _| / \ 0.0 _|____/___________\____ Dreiecksfunktion zu den Eckpunkten a,b,c: Die Funktion f(x) = (x < a) ? 0 : (x < b) ? (x-a)/(b-a) : (x < c) ? (c-x)/(c-b) : 0 Dreiecksmenge: Eine Fuzzymenge, deren charakeristische Funktion eine Dreiecksfunktion ist. Sind a,b,c die Eckpunkte der Dreiecksfunktion, so bezeichnet man die zugehoerge FM mit (a,b,c). _^ 1.0 _| /\ 0.5 _| / \ 0.0 _|____/____\______ Konzentration einer FM: Die Quadrierung ihrer charakteristischen Funktion. Dadurch werden wenig zugehoerige Elemente noch weniger zugehoerig. Dieses entspricht einer Kriterienverschaerfung fuer die Zugehoerigkeit zu der FM. Diletation einer FM: Das Ziehen der Wurzel aus ihrer charakteristischen Funktion. Dadurch werden wenig zugehoerige Elemente mehr zugehoerig. Dieses entspricht einer Kriterienverwischung fuer die Zugehoerigekeit zu der FM. Support einer FM: Die crispe Menge derjenigen Elemente, die eine positive Zugehoerigkeit haben. Toleranz einer FM: Die crispe Menge derjenigen Elemente, die volle Zugehoerigkeit haben. _^ _______ 1.0 _| /\ / \ 0.5 _| / \/ \ 0.0 _|____/_______________\______ ----------------- Support - -------- Toleranz normale Fuzzymenge: Eine Fuzzymenge mit nicht-leerer Toleranz. F(X): Die crispe Menge aller Fuzzymengen ueber dem Grundbereich X. Teilmenge einer FM A: Eine FM, deren charakteristische Funktion kleiner- gleich der charakteristischen Funktion von A ist. _^ ____ 1.0 _| / _ \__ 0.5 _| / / \_ \ 0.0 _|______/__/____\__\_________ Komplement einer FM A: Die FM Ac, die gegeben ist durch Chi[Ac]=1-Chi[A]. _^_____ ____________ <-- Komplement der Dreiecksmenge 1.0 _| \ /\ / 0.7 _| \/ \/ 0.3 _| /\ /\ 0.0 _|_____/__\/__\_______________ Leere FM: Die FM FM0, die gegeben ist durch Chi[FM0](x)=0. Universelle FM: Die FM FMX, die gegeben ist Ch[FMX](x)=1. t-Norm, verallgemeinerter Schitt: Eine Funktion T:[0;1]^2->[0;1] mit * T(a,1) = a (Eigenschaft des neutralen Elements) * T(a,b) = T(b,a) (Kommutativitaet) * T(a,T(b,c)) = T(T(a,b),c) (Assoziativitaet) * Wenn a== T(min(a,b),min(a,b)) = min(a,b) = Tmin(a,b) Da Tmin aber die groesste moegliche T-Norm ist, folgt: T=Tmin. _^ _________ 1.0 _| /\/ \ Tmin-Schnitt ist die Flaeche * 0.5 _| / /\____ \ 0.0 _|____/_/__*___\______\_______ Extreme Norm: Die T-Norm T1(a,b) = (a=1)?b:(b=1)?a:0. T1 ist die kleinste moegliche T-Norm, denn fuer beliebige T-Norm T gilt: * Falls a=1: T(a,b) = T(1,b) = T(b,1) = b = T1(a,b) * Falls b=1: T(a,b) = T(a,1) = a = T1(a,b) * Falls a!=1 und b!=1: T(a,b) >= 0 = T1(a,b) Also T(a,b) >= T1(a,b) Yager-Norm: Die T-Norm T[w](a,b) = 1-min( 1 , ((1-a)^w+(1-b)^w)^(1/w) ) fuer einen Parameter w. Es ist * T[0]=T1 * T[1]=Tluka * T[INF]=Tmin Schwaches Gesetz vom Widerspruch: Die Tatsache, dass Chi[A /\ Ac] < 0.5. Alle Fuzzy-Schnitte erfuellen das schwache Gesetz vom Widerspruch, da fuer beliebeige T-Norm T gilt: T(a,1-a) =< Tmin(a,1-a) = min(a,1-a) =< 0.5 T-Conorm: Eine Funktion C:[0;1]^2->[0;1] mit * C(a,0) = a (Eigenschaft des neutralen Elements) * C(a,b) = C(b,a) (Kommutativitaet) * C(a,C(b,c)) = C(C(a,b),c) (Assoziativitaet) * Wenn a== C(1,0) = 1 // 'C' schreibt sich als umgedrehtes 'T' Fuzzy-Vereinigung nach einer t-Conorm C: Die Operation \/, die zu zwei Fuzzymengen A und B die FM liefert, die gegeben ist durch Chi[A \/ B](x) = C(Chi[A](x), Chi[B](x)). Diese Vereinigung setzt die klassische Vereinigung fort, d.h. auf crispen Mengen liefert die Fuzzy-Vereinigung die Menge, die auch die normale Vereinigung liefern wuerde: * Fuer x in A und in B: Chi[A\/B](x) = C(1, 1) = 1 * Fuer x in A, aber nicht in B: Chi[A\/B](x) = C(1, 0) = 1 * Fuer x weder in A noch in B: Chi[A\/B](x) = C(0, 0) = 0 Die Fuzzy-Vereinigung erfuellt * die Identitaetseigenschaft * die Kommutativitaet * die Assoziativitaet aber nicht notwendigerweise * die Idempotenz * das Gesetz vom Widerspruch Die Fuzzy-Vereinigung setzt gleiche Grundbereiche voraus. T-Conorm einer T-Norm T: Die T-Conorm C(a,b)=1-T(1-a,1-b). C ist eine T-Conorm, denn * C(a,0) = 1-T(1-a,1) = 1-(1-a) = a * C(a,b) = 1-T(1-a,1-b) = 1-T(1-b,1-a) = C(b,a) * C(a,C(b,c)) = 1-T(1-a,1-(1-T(1-b,1-c))) = 1-T(1-a,T(1-b,1-c)) = 1-T(T(1-a,1-b),1-c) = C(C(a,b),c) * Sei a== T1(1-a,1-b) <=> 1-C(a,b) >= 1-C1(a,b) <=> C(a,b) =< C1(a,b) Cmax: Die T-Conorm Cmax(a,b) = max(a,b). Cmax ist die kleinste T-Conorm, denn fuer beliebeige T-Conorm C mit zugehoeriger T-Norm T gilt: T(1-a,1-b) =< Tmin(1-a,1-b) <=> 1-C(a,b) =< 1-Cmax(a,b) <=> C(a,b) >= Cmax(a,b) Cmax ist die einzige idempotente T-Conorm, denn fuer beliebige idempotente T-Conorm C gilt: C(a,b) =< C(max(a,b),max(a,b)) = max(a,b) = Cmax(a,b) Da Cmax aber die kleinste moegliche T-Norm ist, folgt: C=Cmax. Fuer dieselben Fuzzymengen wie unter Tmin ist die Vereinigung nach Cmax: _^ _________ 1.0 _| /\/ \ 0.5 _| / \ 0.0 _|____/_______________\_______ FM-Operationen und Distributivitaet: Tmin und Cmax sind die einzigen Normen, die Distributivitaet erfuellen, denn fuer beliebige distributive T-Norm T und T-Conorm C gilt: x = C(0,x) = C(T(0,0),x) = T(C(0,x),C(0,x)) = T(x,x) => T idempotent => T=Tmax Negation: Eine Funktion n:[0;1]->[0;1], die monton fallend ist und fuer die gilt: * n(0)=1 * n(1)=0 Ist T eine T-Norm, C eine T-Conorm und n eine stetige Negation, so dass das Gesetz vom Widerspruch gilt, so sind T und C nicht idempotent und nicht distributiv. Es reicht zu zeigen, dass die genannten Kriterien nicht alle gleichzeitig wahr sein koennen: Die einzigen distributiven und idempotenten T-Normen und T-Conormen sind Tmin und Cmax. Da n stetig ist, gibt es ein x>0 mit n(x)>0. Dann aber gilt fuer dieses x der Satz vom ausgeschlossenen Dritten nicht: Tmin(x,n(x))=min(x,n(x))>0 // Beweis selbst gestrickt. Standard-Negation: Die Negation n(x) = 1-x. Yager-Negation: Die Negation n[w](x) = (1-x^w)^(1/w). Verallgemeinertes Komplement: Die Funktion c, die zu einer FM A die FM Ac liefert, die gegeben ist durch Chi[Ac]=n(Chi[A]), wobei n eine Negation ist. alpha-Schnitt einer Fuzzy-Menge A: Die crispe Menge aller Elemente mit mindestens Zugehoerigekeit alpha: [Chi[A]]alpha = { x | Chi[A](x)>=alpha } Anschaulich entspricht ein Alpha-Schnitt einer Waagerechten durch den Funktionsgraphen von Chi[A]: Alle x-Werte, deren Funktionswert oberhalb oder auf der Geraden liegen, gehoeren zum Schnitt dazu. Bei stetigem Chi sind die Alpha-Schnitte Vereinigungen von Intervallen. Aus den Alpha-Schnitten ist die charakteristische Funktion rekonstruierbar: Chi[A](x) = sup({alpha | x ist in [Chi[A]]alpha}) Man sucht also das groesste alpha, in dessen Schnitt x noch drin ist. Speichert man eine charakteristische Funktion als Menge ihrer Alpha-Schnitte so kann man bei n Alpha-Schnitten die Original-Funktion auf 1/n genau wiedergewinnen. Man schneidet die y-Achse statt der x-Achse aus folgenden Gruenden: * Feinheiten der Funktion (z.B. Chi(x0)=1, Chi(x)=0 fuer x!=x0) sind mit dieser Einteilung darstellbar * Die Alpha-Schnitte beantworten direkt Fragen wie "Welche x haben einen Wert groesser 0.7?" * Die y-Achse ist immer auf natuerliche Weise einteilbar, da sie im Gegensatz zur x-Achse immer das Intervall [0;1] darstellt. Schnitt, Vereinigung und Komplement einer FM unter Tmin und Cmax lassen sich direkt als Schnitt, Vereinigung und Komplement der entsprechenden Alpha-Schnitte berechnen. Fuer beliebeige T-Norm T gilt [T(Chi[A],Chi[B])][1] = Toleranz(A) /\ Toleranz(B) Beweis: Fuer jedes x, welches sowohl in Toleranz(A) als auch in Toleranz(B) ist, gilt Chi[A](x)=Chi[B](x)=1 und mithin T(Chi[A](x),Chi[B](x)) = T(1,1) = 1. Wenn andersrum fuer ein x T(Chi[A](x),Chi[B](x))=1 ist, so folgt, dass Chi[A](x)=1 und Chi[B](x)=1. Waere naemlich z.B. Chi[A](x)<1, so waere T(Chi[A](x),Chi[B](x)) = 1 > Chi[A](x) = min(Chi[A](x),Chi[B](x)) = Tmin(Chi[A](x),Chi[B](x) was ein Widerspruch ist. // Beweis selbst gestrickt. Der alpha-Schnitt einer Dreiecksmenge ergibt sich als [(a,b,c)]alpha = [ a+alpha*(b-a) , c-alpha*(c-b) ] Der 0-Schnitt einer Fuzzymenge ist immer der Grundbereich. Der 1-Schnitt ist immer die Toleranz. _^ _______ 1.0 _| /\ / \ 0.5 _|-----/--\/---------\-------- 0.0 _|____/_______________\______ --- ---------- 0.5-Schnitt Treppenfunktion: Eine Funktion, bei der endlich viele alpha-Schnitte genuegen, um sie vollstaendig zu rekonstruieren. Diese Definition formalisiert lediglich die intuitive Vorstellung einer "Treppenfunktion". Treppenfunktionen sind approximationsvollstaendig, da sie bei genuegend kleiner Wahl der "Stufen" jeden Funktionsverlauf nachbilden koennen. Abdecken eines geordneten Grundbereiches: Das Uebersetzen natuerlich- sprachlicher geordneter Klassen in Fuzzymengen. Beispiel: Die Klassen "kleine Menschen", "mittelgrosse Menschen" , "grosse Menschen" sind geordnet. Man kann nun fuer jeden dieser Begriffe eine charakeristische Funktion definieren, die die Zugehoerigkeit eines Menschen zu dieser Klasse in Abhaengigkeit von seiner Koerpergroesse angibt: Chi[Klein](2 m) = 0.1 Chi[Klein](1.7 m) = 0.5 Chi[Klein](0.3 m) = 1.0 Chi[Gross](2 m) = 0.9 Chi[Gross](1.7 m)=0.5 etc. Zusammen decken diese Funktionen den gesamten Bereich der Koerpergroessen ab. _^____________ _________________ 1.0 _| Chi[klein] \ / Chi[gross] 0.5 _| \/ 0.0 _|_____________/\_______________________ Groesse in cm Gewicht: Eine reelle Zahl aus [0;1], die sich mit den anderen vorkommenden Gewichten zu 1 addiert. Man gibt z.B. einem Messwert ein Gewicht, um seine Wichtigkeit zu steuern: Ist das Gewicht gross, wird der Messwert stark mit in Berechnungen einbezogen, bei kleinem Gewicht hingegen kaum. Zufaellige Menge zu einer Klasse K ueber einem Grundbereich X: Eine Menge { ( P[i],p[i] ) | i=1..n } wobei * n eine Anzahl Meinungen ist * p[i] das Gewicht der i-ten Meinung ist * P[i] eine Menge von Objekten aus X ist, die nach der i-ten Meinung zur Klasse K gehoeren Zufaellige Mengen modellieren eine Meinungsumfrage, die feststellt, inwieweit eine Auswahl von Objekten einer vorgegegebenen Klasse K zugerechnet werden. Person i | Gewichtung p[i] | nach Meinung von i gute Vorlesungen P[i] ---------+-----------------+----------------------------------------- Barbara | 0.1 | { NN, SC, InfoD } Elmar | 0.1 | {InfoA, InfoB, InfoC, InfoD } ... | ... | ... Konturfunktion einer zufaelligen Menge Z: Die Funktion f(x) = SUM i=1..n (x in P[i])?p[i]:0. Fuer ein Objekt x summiert man also die Gewichte all derer Meinungen, die x zur Klasse rechnen wuerden. Der resultiernde Wert gibt dann den Grad der Zugehoerigkeit von x zur Klasse laut Meinungsbild an. _^ 1.0 _| * 0.5 _| * 0.0 _|____________*_____*____*_____*_________ NN SC InfoA InfoB InfoC InfoD Fuzzymenge zu einer zufaelligen Menge Z: Die Fuzzymenge FM(Z), die gegeben ist durch die Konturfunktion von Z. Man schreibt allgemein die Konturfunktion einer zufaelligen Menge Z als Chi[FM(Z)] Zufaellige Menge zu einer Fuzzymenge M: Die zufaellige Menge { (P[i],p[i]) | P[i]=[Chi[M]]alpha[i], p[i]=alpha[i]-alpha[i-1], i=1..n } Dieses funktioniert nur, wenn die Wertemenge von M endlich ist. Man setzt n auf die Anzahl dieser Werte n = |{y | y=Chi[M]}| und die alpha[i] auf diese Werte von klein nach gross sortiert. alpha[0] ist dabei 0. Die Konturfunktion dieser zufaelligen Menge ist dann f(x) = SUM i=1..n (x in P[i])?p[i]:0 = SUM i=1..n (Chi[M](x) >= alpha[i] ? alpha[i]-alpha[i-1] : 0) = SUM i=1..k alpha[i]-alpha[i-1] mit k sodass alpha[k]=Chi[M](x) = alpha[k] = Chi[M](x) Wenn die Summe der p[i] nicht 1 ergibt, so fuegt man die Differenz p[n+1]=1-a[n] noch mit jemandem meinungslosen dazu: ({},1-a[n]). Schnitt zweier zufaelliger Mengen: Die Operation /\, die zu zwei zufaelligen Mengen A und B die folgende zufaellige Menge liefert: A /\ B = { (P[A][i] /\ P[A][i], p[i]) | i=1..n } Dafuer muss gelten: * A und B haben denselben Grundbereich X * A und B sind Meinungen zu verschiedenen Klassen * A und B haben dieselben Meinungsgewichte 1..n Fuer die zugehoerige Fuzzymenge FM(A/\B) ergibt sich fuer alle Objekte x: Tluka(Chi[FM(A)](x),Chi[FM(B)](x)) =< Chi[FM(A/\B)](x) =< Tmin(Chi[FM(A)](x),Chi[FM(B)](x)) Ist kein Objekt in den Schnittmengen P[A][i]/\P[B][i], so ist Chi[FM(A/\B)] die Tluka-Norm. Schliessen sich die P[A][i] fuer i=1..n der Reihe nach ein und schliessen sich auch die P[B][i] fuer i=1..n der Reihe nach ein, so ist Chi[FM(A/\B)] die Tmin-Norm. Die Menge unter "Zufaellige Menge" geschnitten mit der folgenden Person i | Gewichtung p[i] | selbst gehaltene Vorlesungen P[i] ---------+-----------------+----------------------------------------- Barbara | 0.1 | { NN, SC, GeneticProgramming } Elmar | 0.1 | { InfoB } ... | ... | ... >>>>>>>> ergibt >>>>>>>>>>> Person i | Gewichtung p[i] | selbst gehaltene Vorlesungen P[i] ---------+-----------------+----------------------------------------- Barbara | 0.1 | { NN, SC } Elmar | 0.1 | { InfoB } ... | ... | ... Vereinigung zweier zufaelliger Mengen: Die Operation \/, die zu zwei zufaelligen Mengen A und B die folgende zufaellige Menge liefert: A \/ B = { (P[A][i] \/ P[A][i], p[i]) | i=1..n } Dafuer muss gelten: * A und B haben denselben Grundbereich X * A und B sind Meinungen zu verschiedenen Klassen * A und B haben dieselben Meinungsgewichte 1..n Fuer die zugehoerige Fuzzymenge FM(A/\B) ergibt sich fuer alle Objekte x: Cmax(Chi[FM(A)](x),Chi[FM(B)](x)) =< Chi[FM(A\/B)](x) =< Cluka(Chi[FM(A)](x),Chi[FM(B)](x)) Ist kein Objekt in den Schnittmengen P[A][i]/\P[B][i], so ist Chi[FM(A\/B)] die Cluka-Conorm. Schliessen sich die P[A][i] fuer i=1..n der Reihe nach ein und schliessen sich auch die P[B][i] fuer i=1..n der Reihe nach ein, so ist Chi[FM(A/\B)] die Cmax-Conorm. Diese Abschaetzungen zeigen: Fuehrt man eine Operation auf zwei zufaelligen Mengen aus, so ist die zum Ergebnis gehoerige FM nicht unbedingt die FM, die man erhaelt, wenn man die zufaelligen Mengen zuerst in Fuzzymengen uebersetzt und dann die Operation anwendet. Komplement einer zufaelliger Menge: Die Function c, die zu einer zufaelligen Menge A die folgende zufaellige Menge liefert: Ac = { (P[i]c, p[i]) | i=1..n } Fuer die zugehoerige Fuzzymenge FM(A) ergibt sich: Chi[FM(Ac)] = 1-Chi[FM(A)] d.h.: Chi[FM(Ac)] = n(Chi[FM(A)]) mit Standard-Negation n Gleichheitsrelation bezueglich einer T-Norm T: Eine Funktion E:X^2 -> [0;1] fuer die gilt: * X ist ein Grundbereich * E(x,x) = 1 (Reflexivitaet) * E(x,y) = E(y,x) (Kommutativitaet) * T(E(x,y), E(y,z)) =< E(x,z) (Transitivitaet) Eine Gleichheitsrelation misst also die Gleichheit zweier Objekte auf einem Bereich von 0..1 (1 heisst: komplett gleich). Beispiele: * E(x,y) = (x=y)?1:0 mit Tmin * E(x,y) = 1-abs(x-y) mit Tluka und X=[0;1] Extensionale Huelle einer Menge A unter einer Gleichheitsrelation E: Die Fuzzymenge, die gegeben ist durch die charakteristische Funktion Chi[FM(A)](x) = sup({E(x,y) | y in A}) Zu einem Objekt x sucht man also das aehnlichste Objekt y, was zu A gehoert. Der Zugehoerigkeitsgrad von x zu FM(A) ist dann die Aehnlichkeit von x zu y. Jede normale FM A laesst sich als extensionale Huelle ihrer Toleranz auffassen, wenn man als Gleichheitsrelation E(x,y) = 1 - abs( Chi[A](x) - Chi[A](y) ) mit der Tluka-Norm verwendet. Beweis: Sei A' die Toleranz von A. Dann ergibt sich als Zugehoerigkeit fuer ein x zur extensionalen Huelle von A': Chi[FM(A')](x) = sup({E(x,y) | y in A'}) = sup({E(x,y) | Chi[A](y)=1 }) = sup({1-abs(Chi[A](x)-Chi[A](y)) | Chi[A](y)=1 }) = sup({1-abs(Chi[A](x)-1)}) = sup({Chi[A](x)}) = Chi[A](x) _^ * * ********* <-- crispe Menge 1.0 _| / \ / \ / \ <-- extensionale Huelle 0.5 _| / \/ \ / \ 0.0 _|_/__________\_____/_____________\___________ Gewinnen einer Fuzzymenge: Die Erzeugung einer Fuzzymenge, meist nach einem der folgenden Verfahren: * Abdecken eines geordneten Grundbereiches * Bilden der Konturfunktion einer zufaelligen Menge * Bilden der extensionalen Huelle einer crispen Menge * Fuzzy-Clustering (s.u.) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ k-means ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ s.a. "Classification automatique" (ca.txt, auf franzoesisch) Datenmenge: Eine Menge von Eingabevektoren { x[1], ... x[n] }. Mittelpunkt einer Datenmenge x[1], ... x[n]: Der Punkt SUM i=1..n x[i]/n. Wolke einer Datenmenge: Eine groesstmoegliche Teilmenge der Datenmenge, deren Elemente untereinander einen kleinen Abstand haben. Ausreisser einer Datenmenge: Ein Eingabevektor, der einen grossen Abstand von allen Wolken hat. Rauschen einer Datenmenge: Die Menge der Ausreisser. Gruppe einer Datenmenge: Eine (evtl. fuzzy) Teilmenge, die als zusammengehoerig betrachtet wird. Gewichtsvektor, Zentroid, Prototyp, Codebook, Zentrum einer Gruppe: Ein Vektor, der zu allen Vektoren der Gruppe einen kleinen Abstand hat. Dieses Zentrum repraesentiert die Gruppe. Clustering einer Datenmenge: Das automatische Einteilen der Datenmenge in Gruppen. Im Optimalfall stimmen die Gruppen mit den Wolken ueberein. k-means: Der folgende Algorithmus zum Clustering einer Datenmenge x[1],...x[n]: 1. Waehle die gewuenschte Anzahl von Gruppen k 2. Waehle Zentren w[1],...w[k] zufaellig 3. Sei die Funktion Chi[i](j) = (abs(w[j]-x[i]) minimal) ? 1 : 0 Diese Funktion liefert also 1, wenn w[j] das zu x[i] naechste Zentrum ist 3. While sich noch was tut 4. For i=1..k 5. Setze w[i] = (SUM j=1..n Ch[i](j)*x[j]) / (SUM j=1..n Chi[i](j)) 6. EndFor 7. EndWhile Dieser Algorithmus berechnet also jedesmal den Mittelpunkt aller zu einem w[i] gehoerigen Datenpunkte. Dann wird das w[i] dorthin verschoben. Auf diese Weise setzen sich die w[i] in die Mittelpunkte der Wolken der Datenpunkte. Ein Datenpunkt gehoert dann zur Gruppe desjenigen w[i], der ihm am naechsten ist. Problem: Die Datenpunkte gehoeren immer voll zu einer Gruppe, obwohl vielleicht auch graduelle Zugehoerigkeit sinnvoll sein koennte. k-means ist nicht stetig, d.h. eine geringe Aenderung der Datenpunkte kann die Gruppen drastisch veraendern. * * * * Beispielclustering * * * * * * * * * * Datenpunkte * + * * * + + Zentren * * * * * * * Quantisierungsfehler einer Datenmenge x[1],...x[n] in Bezug auf die Zentren w[1],...w[k]: Die Zahl SUM i=1..k SUM j=1..n (x[j] zu w[i]?abs(x[j]-w[i])^2:0) Es kann gezeigt werden, dass k-means diesen Quantisierungsfehler minimiert. Fuzzy Clustering, Fuzzy k-means: Der folgende Algorithmus zum unscharfen Clustering einer Datenmenge x[1],...x[n]: 1. Waehle die gewuenschte Anzahl von Gruppen k 2. Waehle eine Konstante d, z.B. d=2 3. Waehle eine Konstante delta 4. Waehle Zentren w[1],...w[k] zufaellig 5. While sich noch was tut 6. Bestimme alle Chi[i](j) = abs(w[i]-x[j]) ^ (-1 / (d-1)) / ( delta ^ (-2/(d-1)) + SUM m=1..k abs(w[m]-x[j]) ^ (-1 / (d-1)) ) 7. For i=1..k 8. Setze w[i] = (SUM j=1..n Ch[i](j)^d*x[j]) / (SUM j=1..n Chi[i](j)^d) 9. EndFor 10. EndWhile Ebenso wie k-means werden also abwechselnd die Gruppenmittelpunkte bestimmt und dann die w[i] in diese Mittelpunkte geschoben. Allerdings ist die Zugehoerigkeit eines x[j] zu einem w[i] nun eine Zahl zwischen 0 und 1: Die Gruppen sind Fuzzymengen. Fuzzy-k-means ist nicht stetig, d.h. eine geringe Aenderung der Datenpunkte kann die Gruppen drastisch veraendern. Fuzzy-Quantisierungsfehler einer Datenmenge x[1],...x[n] in Bezug auf die Zentren w[1],...w[k]: Die Zahl SUM i=1..k SUM j=1..n Chi[i](x[j])^d*abs(x[j]-w[i])^2 wobei d eine Konstante ist (meist 2) und Chi[i](j) die Zugehoerigkeit von x[j] zu w[i] angibt. Es kann gezeigt werden, dass Fuzzy-k-means diesen Quantisierungsfehler minimiert. Less Fuzzy Fuzzy k-means: Der Fuzzy k-means-Algorithmus mit kleinem d. Fuer d=1 ist der Fuzzy-k-means-Algorithmus gleich dem k-means Algorithmus. Dieses ergibt sich, da fuer d=1 der Fuzzy-Quantisierungsfehler die gleichen Minima hat wie der Quantisierungsfehler, naemlich Chi[i](x[j]) aus {0,1}. Very Fuzzy Fuzzy k-means: Der Fuzzy k-means-Algorithmus mit grossem d. Je groesser d gewaehlt wird, desto niedrigere Gruppenzugehoerigkeiten erhaelt man. Fuer sehr grosse d setzen sich alle Zentren in den Mittelpunkt der Daten und jeder Datenpunkt ist zu jeder Gruppe gleich zugehoerig. d drueckt also den Grad der Unschaerfe des Clusterings aus. d gross * * * * Beispielclustering * * * * * * * * * * Datenpunkte * * * * + + + Zentren * * * * * * * Probabilistisches Fuzzy Clustering: Fuzzy Clustering mit der Forderung, dass fuer j=1..n SUM i=1..k Chi[i](j) = 1, d.h. die Zugehoerigkeiten eines Datenpunktes zu allen Gruppen summieren sich zu 100%. Dieses erreicht man durch die Wahl eines sehr grossen deltas: Dann naemlich wird der Summand delta^(-2/(d-1)) vernachlaessigbar und durch die Normung mit SUM m=1..k abs(w[m]-x[j])^(-1 / (d-1)) ) ergibt die Summe der Zugehoerigkeiten zu den Gruppen fuer ein x[i] dann 100%. Ein grosses delta fuehrt dazu, dass jeder einzelne Datenpunkt und insbesondere jeder Ausreisser mit in die Gruppen einbezogen wird. delta gross **** Beispielclustering **** + ** * Datenpunkte **** + Zentrum Possibilistisches Fuzzy Clustering: Fuzzy Clustering, bei dem ein Datenpunkt nicht unbedingt zu Gruppen zugehoerig sein muss. Dieses erreicht man durch ein kleines delta: Dadurch wird die Normung ausgehebelt und die Summe der Zugehoerigkeiten eines Datenpunktes zu den Gruppen muss nicht mehr 100% ergeben. Nun werden Ausreisser nicht mehr beruecksichtigt: Der Summand delta^(-2/(d-1)) fungiert als ein "virtuelles Zentrum", welches alle Ausreisser um sich schaart. Also haben die Ausreisser eine nur geringe Zugehoerigkeit zu den tatsaechlichen Zentren. Je kleiner man delta waehlt, desto eher wird ein Punkt als Rauschen abgetan. delta klein **** Beispielclustering **+* ** * Datenpunkte **** "Rauschen"--^ + Zentrum Ellipsoid: Eine Datenmenge x[1],...x[n], fuer die es eine Metrik A gibt und eine reelle Zahl r, sodass gilt t(x[j]-m)*A*(x[j]-m) ~= r fuer sehr viele j=1..n und t(x[j]-m)*A*(x[j]-m) < r fuer die anderen j=1..n // Stimmt das (?) Dieses entspricht also einer mehrdimensionalen Ellipse Ellipsoid laengs zu einer Koordinatenachse k: Ein Ellipsoid, fuer das die Metrik A eine Diagonalmatrix ist. Naives Clustering mit laenglichen Wolken: Das Clustering einer Datenmenge, deren Wolken Ellipsoide sind, die laengs zu einer Koordinatenachse liegen. In diesem Fall kann es geschehen, dass die Zentren sich zwischen die Wolken legen, anstatt in deren Mittelpunkte. Um dies zu vermeiden, staucht man das Ellipsoid zu einer Kugel: Man multipliziert die Koordinaten einer Gruppe mit einem Faktor (1 gleicher Faktor alpha[i][m] pro Koordinate m fuer alle Punkte einer Gruppe i). In der so verformten Gruppe findet dann das Zentrum den Mittelpunkt. Mathematisch gesehen benutzt man eine andere Metrik, d.h. im Clustering statt des Standard-Abstandes abs(x[j]-w[i]) den Abstand SUM m=1..dim(x[j]) alpha[i][m]*(x[j][m]-w[i][m])^2 Dieses entspricht einem Abstand mit einer Diagonalmetrik, der die Dimensionen unterschiedlich gewichtet. Die alpha[i][m] werden auch jedesmal angeglichen: alpha[i][m] = PROD p=1..dim(x[1]) SUM j=1..n Chi[i](j)^d*(x[i][p]-w[i][p])^2 / SUM j=1..n Chi[i](j)^d*(x[i][m]-w[i][m])^2 Gustafson-Kessel-Clustering: Das Clustering einer Datenmenge, deren Wolken Ellipsoide sind, die nicht laengs zu einer Koordinatenachse liegen. Dazu werden die Ellipsoide zu Kugeln verformt, indem im Clustering statt des Standard-Abstandes der folgende Abstand verwendet wird: t(x[j]-w[i])*A*(x[j]-w[i]) Die Matrix A gewichtet die Koordinaten dabei derart, dass Ellipsoide gedreht und gestaucht werden. A wird im Laufe des Algorithmus staendig angepasst. // Haengt A nicht noch von i ab (?) Gustafson-Kessel-Feld: Eine durch Gustafson-Kessel-Clustering erhaltene Gruppe. Die Zugehoerigkeit eines Datenpunktes zu einer Gruppe ergibt sich aus dem Abstand zum Zentrum der Gruppe -- wobei durch den Einfluss der Metrik A die Gruppen unterschiedlich geformt und sogar geteilt sein koennen. Variety, Affiner Unterraum: Eine Punktemenge P, zu der es einen Stuetzvektor s gibt und Richtungsvektoren r[1],...r[n] gibt, sodass gilt: P = { s + PROD i=1..n k[i]*r[i] | k ist ein Vektor } Ein affiner Unterraum ist also eine Gerade, eine Ebene oder im Hoeherdimensionalen ein Hyperebene. Abstand eines Punktes x von einem affinen Unterraum P: Der Wert d(x,s) = sqrt( abs(x,s) - SUM i=1..n (t(x-s)*r[i])^2 ) wobei s der Stuetzvektor von P ist und die r[i] die Richtungsvektoren, die paarweise orthogonal sein muessen. Bei gleichem P ist der Abstand unabhaengig von der Wahl von s und der r[i]s. Der Abstand eines Punktes von P ist genau dann 0, wenn der Punkt in P liegt. Fuzzy k-varieties: Der Fuzzy k-means-Algorithmus, dessen Gruppen affine Unterraeume sind. Die Zentren sind dabei die Stuetzvektoren der Unterraeume. Die Richtungsvektoren sind zusaetzliche Parameter, die ebenfalls im Laufe des Algorithmus angeglichen werden. Man ersetzt den Standard-Abstand durch den Abstand eines Punktes von den affinen Unterraeumen. Dadurch findet der Algorithmus Linien in den Daten und kann z-B. zur Mustererkennung eingesetzt werden. ****+**** Das AVZ, geclustert mit 1-varienties * * * Datenpunkte * * + Zentren + + * * * * Kugel: Eine Punktemenge P, zu der es eine reelle Zahl r und einen Punkt m gibt, sodass gilt P = { x | abs(x-m)=r }. Radius einer Kugel: Der Abstand ihrer Punkte vom Mittelpunkt. Fuzzy k-shell: Der Fuzzy k-means-Algorithmus, dessen Gruppen Kugeln sind. Die Zentren sind dabei die Mittelpunkte der Kugeln und die Radien sind zusaetzliche Parameter, die mit angepasst werden. Der Algorithmus approximiert diese Werte nur. Cluster-Validity-Problem: Die Frage, welche Anzahl k von Gruppen eine Datenmenge am besten darstellt. Um die optimale Anzahl zu finden, laesst man Fuzzy k-means mit k=1..n laufen und bewertet die entsprechenden Ergebnisse. Elbow-Criterion: Das folgende Kriterium zur Bewertung einer Gruppenanzahl k: Wenn der Quantisierungsfehler fuer k ploetzlich sehr stark absinkt, so ist k die optimale Gruppenanzahl. Das "sehr stark Absinken" orientiert sich dabei am bisherigen Verlauf des Quantisierungsfehlers fuer steigendes k. Dieses Kriterium waehlt also dasjenige k, was den groessten Fehlerverlust ausloest. ^ QF | * | * | * <-- Elbow | * | * | * |___________|________________________ k Partition coefficient Criterion: Das folgende Kriterium zur Bewertung einer Gruppenanzahl k: k ist optimal, wenn der Wert SUM i=1..k SUM j=1..n Chi[i](j)^2/|X| minimal ist. Das Partition coefficient Criterion bevorzugt also crispes Clustering. Muster, Beispiel: Etwas, was eine Menge repraesentiert. Hier: Ein Tupel aus einem Eingabevektor und einer erwuenschten Ausgabe ( (x[1],...x[n]), f(x[1],...x[n])) Trainingsmenge: Eine endliche Menge von Beispielen. Funktionslernen: Das Generieren einer Funktion, die Elemente einer Eingabevektoren einer Trainingsmenge auf die zugehoerigen Ausgabevektoren abbildet. Gibt man der Funktion einen Eingabewert, der nicht der Trainingsmenge angehoert, so soll auch dieser auf einen sinnvollen Ausgabewert abgebildet werden. Funktionslernen wird angewandt, um aus Daten-Beispielen auf eine Gesetzmaessigkeit zu schliessen und fuer neue Daten KOnsequenzen vorhersagen zu koennen. // Fuer Details siehe nn.txt Testmenge: Eine Menge von Beispielen, die nicht in einer zugehoerigen Trainigsmenge vorkommen. Hat man eine Funktion anhand der Trainigsmenge gelernt, so prueft man anhand der Beispiele der Testmenge, ob die Funktion auch hier die zugehoerigen Ausgabevektoren liefert. Diese Faehigkeit wird als Guetekriterium fuer die gelernte Funktion benutzt. Funktionslernen mit Fuzzy-k-means: Der folgende Algorithmus zum Funktionslernen: 1. Fuehre Fuzzy-k-means auf den Eingabevektoren der Trainingsmenge durch 2. Versieh jeden Zentrumsvektor mit einer Sollausgabe f(w[i]) = (SUM j=1..n Chi[i](j)^d*f(x[j]) ) / (SUM j=1..n Chi[i](j)^d) 3. Der Funktionswert fuer neue Daten x ist f(x) = (SUM i=1..k Chi[i](x)*f(w[i])) / (SUM i=1..k Chi[i](x)) wobei Chi[i](x) die nach Fuzzy-k-means berechnete Zugehoerigkeit des Vektors x zur Gruppe i bezeichnet. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Operationen auf Fuzzymengen ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Matrix einer FM A mit endlichem Grundbereich X x Y: Die |X|x|Y|-Matrix, deren Komponente an der Stelle i,j die Zahl Chi[A]((X[i],Y[j])) ist. Dabei ist X[i] das i-te Element von X und Y[j] das j-te Element von Y, eine willkuerliche Ordnung innerhalb der Menge vorrausgesetzt. kartesisches Produkt zweier Fuzzymengen A und B: Die Fuzzymenge A x B, deren Grundbereich das kartesische Produkt der Grundbereiche von A und B ist und die gegeben ist durch die charakteristische Funktion Chi[A x B](x,y) = min(Chi[A](x), Chi[B](y)) Anschaulich kann man im 3D-Koordinatensystem Chi[A] auf der x-Achse aufzeichnen und Chi[B] auf der y-Achse aufzeichnen und erhaelt im x-y-Raum stehend ein 3D-Gebilde fuer A x B. Das kartesische Produkt entspricht einer unscharfen Relation, d.h. Chi[A x B](x,y) gibt an, wie stark die Objekte x und y in der durch A x B definierten Verbindung stehen. Das kartesische Produkt laesst sich auch ueber Alpha-Schnitte berechnen: [Chi[A x B]]alpha = { (x,y) | Chi[AxB](x,y) >= alpha } = { (x,y) | min(Chi[A](x),Chi[B](x)) >= alpha } = { (x,y) | Chi[A](x)>=alpha und Chi[B](x)>=alpha} = [Chi[A]]alpha x [Chi[B]]alpha Fuer gegebene Fuzzymengen A und B mit endlichen (und kleinen) Grundbereichen X und Y laesst sich die Matrix von A x B wie folgt berechnen: y1 y2 y3 ... x1 min(x1,y1) min(x1,y2) min(x1,y3) x2 min(x1,y1) min(x1,y2) min(x1,y3) x3 min(x1,y1) min(x1,y2) min(x1,y3) ... ^ | | /\ A | / \ |_____/____\________ /\ / | \/ /\ B | / /\ \ A x B | / / \ \ |/ /____\/ / Projektion eines kartesischen Produkts P auf die i-te Komponente: Die Menge aller i-ten Komponenten der Tupel als P. proj[i]( { (x[1], ...x[n]) | x[1] aus X[1], ... x[n] aus X[n] } ) = X[i] Man schreibt auch projX fuer proj[1] und projY fuer proj[2]. Projektion einer Fuzzymenge A x B auf die erste Komponente: Die ("einfache") Fuzzymenge projX(A x B), die gegeben ist durch die charakteristische Funktion Chi[projX(A x B)](x) = sup({ Chi[A x B](x,y) | y aus Grundbereich von B}) Analog definiert man die Projektion projY(A x B) auf die zweite Komponente. Bildlich gesprochen ist die Projektion der Schattenwurf des 3D-Gebildes von A x B auf die Flaeche der x-Achse. Kartesisches Produkt und anschliessende Projektion sind nicht informationserhaltend! Es gilt: Chi[A] = Chi[projX(A x B)] wenn B normal Chi[A x B] =< Chi[projX[A x B] x projY[A x B]] Die Projektion laesst sich auch durch die strikten Alpha-Schnitte berechnen: [Chi[projX(A x B)]]_alpha = { x | Chi[projX(A x B)] > alpha } = { x | sup({ Chi[AxB](x,y) }) > alpha } Wenn die kleinste obere Schranke groesser als alpha ist, so muss auch ein Chi[AxB](x,y) existieren, welches groesser als alpha ist. Andernfalls waere die kleinste untere Schranke ja gleich alpha. = { x | Es existiert ein y mit Chi[AxB](x,y) > alpha } = { x | Es existiert ein y mit (x,y) in [Chi[AxB]]_alpha } = projX([Chi[A x B]]_alpha) Max-Min-Komposition, Komposition der Fuzzymengen A aus F(X x Y) und B aus F(Y x Z): Die Fuzzymenge B o A, die gegeben ist durch die charakteristische Funktion Chi[B o A](x,z) = max({ min({Chi[A](x,y), Chi[B](y,z)}) | y aus Y}) Die Fuzzymenge B o A hat dabei den Grundbereich X x Z. Es handelt sich um eine unscharfe Relation, die den Grundbereich Y "ueberspringt". Die Komposition ist assoziativ. Sind zwei FM symetrisch mit Chi[A](x,y)=Chi[A](y,x) und Chi[B](x,y)=Chi[B](y,x) so folgt nicht, dass auch ihre Max-Min-Komposition symmetrisch ist: Chi[A o B](x,y) != Chi[A o B](y,x) fuer einige A,B,x,y Berechnung der Max-Min-Komposition zweier FM A und B mit endlichen Grundbereichen (nach dem Franzoesischen Algorithmus fuer die Matritzenmultiplikation, s.a. maths.txt): 1. Schreibe A (Grundbereich X x Y) als Matrix 2. Schreibe B (Grundbereich Y x Z) als Matrix rechts ueber die Matrix von A: ---------Z-----> | | / a b c \ Matrix von B ---> Y | d e f | | \ g h i / v ------Y----> | | / j k l \ / \ Matrix von A -> X | m n o | | | <-- Ergebnismatrix | \ p q r / \ / v 3. Durchlaufe alle Komponenten i,j der Ergebnismatrix 4. Durchlaufe die i-te Zeile von A gleichzeitig mit der j-ten Spalte von B (zB. fuer i=j=1: j,k,l und a,d,g) 5. Bilde fuer jedes Paar das Minimum und merke dir das groesste der Minima ( min(j,a), min(k,d), min(l,g), groesstes merken) 6. Schreibe dieses groesste Minimum in die Ergebnismatrix an der Stelle i,j Extensionsprinzip: Die folgende Idee zum Uebertragen einer reellen Funktion f:X->Y auf Fuzzymengen: f^:F(X) -> F(Y) Chi[f^(A)](y) = sup({Chi[A](x) | f(x) = y}) f^ ist also die f entsprechende Funktion, die zu einer Fuzzymenge A eine neue Fuzzymenge B liefert. Die charakteristische Funktion von B liefert dann fuer ein y den groessten Zugehoerigkeitswert unter allen Urbildern von y. Da y im Grundbereich von B liegen, liegen seine Urbilder im Grundbereich von A. Hier kann also Chi[A] benutzt werden. In der Anwendung kann sich das Extensionsprinzip als rechenaufwaendig erweisen. Fuer die Alpha-Schnitte gilt folgender Zusammenhang: [Chi[f^(A)]]alpha >= { y | y ist Bild eines x aus [Chi[A]]alpha } Die Alpha-Schnitte der uebertragenen Fuzzymenge schliessen also die Uebertragung der Alpha-Schnitte ein. Beweis: [Chi[f^(A)]]alpha = { y | Chi[F^(A)](y) >= alpha } = { y | sup({Chi[A](x) | f(x) = y}) >= alpha } Dieses sind alle y, fuer die das Supremum der Urbilder groessergleich alpha ist. Nun gibt es y's, bei denen zwar das Supremum alpha ist, nicht aber die Werte selber. Diese y's fallen bei der folgenden Menge raus: >= { y | Ex x f(x)=y, Chi[A](x)>=alpha } = { y | Ex x f(x) = y , x aus [Chi[A]]alpha } = { y | y ist Bild eines x aus [Chi[A]]alpha } Gleichheit gilt in folgenden Faellen: * f ist stetig und alle Alpha-Schnitte von A sind kompakt ODER * Chi[A] ist eine Treppenfunktion Dann ist der Schnitt des Bildes gleich dem Bild des Schnittes. Daraus ergibt sich zB: * r*(a,b,c) = (r*a,r*b,r*c) * (a,b,c) + (d,e,f) = (a+d,b+e,c+f) * (a,b,c)*(d,e,f) : Toleranz {b*e} Support [ a*d , c*f ] Beispiel: Sei X={a,b,c}, Chi[X](a)=0.1, Chi[X](b)=0.3, Chi[X](c)=0.2 Y={A,B} f:X->Y wie folgt X f:X->Y Y Chi[Y](y) a -------------> A sup({Chi[X](a)}) = 0.1 b -----------,-> B sup({Chi[X](b), Chi[X](c)}) = 0.3 c __________/ Strikter alpha-Schnitt einer Fuzzy-Menge A: Die crispe Menge aller Elemente mit hoeherer Zugehoerigekeit als alpha: [Chi[A]]_alpha = { x | Chi[A](x)>alpha } Anschaulich entspricht ein Alpha-Schnitt einer Waagerechten durch den Funktionsgraphen von Chi[A]: Alle x-Werte, deren Funktionswert oberhalb (und nicht auf) der Geraden liegen, gehoeren zum Schnitt dazu. Fuer strikte Schnitte gilt nun immer mit alpha > 0: [Chi[f^(A)]]_alpha = { y | y ist Bild eines x aus [Chi[A]]_alpha } Beweis: [Chi[f^(A)]]_alpha = { y | Chi[F^(A)](y) > alpha } = { y | sup({Chi[A](x) | f(x) = y}) > alpha } Sobald das Supremum der Urbilder groesser als alpha ist, muss es auch ein Urbild geben, was groesser als alpha ist. Waere dem naemlich nicht so, so waere alpha ja eine kleinere obere Schranke als das Supremum -- was ja nicht geht. = { y | Ex x f(x)=y, Chi[A](x)>=alpha } = { y | Ex x f(x) = y , x aus [Chi[A]]alpha } = { y | y ist Bild eines x aus [Chi[A]]alpha } Mit strikten Schnitten kann also eine Funktion auf eine Fuzzymenge uebertragen werden -- wenn man sich mit der Darstellung der Fuzzymenge durch die strikten Schnitte zufrieden gibt. Notwendigkeit einer crispen Menge M gegeben eine FM A: Die Zahl Nec[A](M) = 1 - sup({Chi[A](x) | x nicht in M}) Die Notwendigkeit gibt an, wie sehr die Elemente ausserhalb von M nicht in Frage kommen. Defuzzifizierung einer Fuzzymenge: Eine Abbildung der Fuzzymenge auf dasjenige Element des Grundbereichs, welches die Fuzzymenge am besten repraesentiert. Man geht davon aus, das der Grundbereich reell ist. Nichtstetigkeit einer Defuzzifizierung: Ihre Eigenschaft, dass schon eine leichte Aenderung der zugrundeliegenden charakteristischen Funktion das Ergebnis der Defuzzifizierung grundlegend veraendert. Im Allgemeinen wird Nichtstetigkeit als negativ angesehen, da leichte Aenderungen der charakteristischen Funktion sich leicht durch Messfehler und Rauschen ergeben koennen und dann jedesmal wechselndes Verhalten hervorrufen. Kleinstes-Maximum-Strategie: Die Defuzzifizierung, die eine Fuzzymenge auf das kleinste Maximum der charakteristischen Funktion abbildet. Hat man eine Fuzzymenge gegeben, so sucht man nach denjenigen Elementen, die hoechste Zugehoerigkeit haben und nimmt unter diesen das kleinste. Probleme: * Nichtstetigkeit: Hat die charakteristische Funktion 2 Maxima, so genuegt eine leichte Erhoehung des zweiten Maximalwertes, um das Ergebnis der Defuzzifizierung vom ersten Maximum zum zweiten springen zu lassen * Informationsvernachlaesigung: Hat die charakteristische Funktion 2 Maxima, so wird das zweite von der Kleinstes-Maximum-Strategie voellig vernachlaessigt Means of Maxima-Strategie, MOM-Strategie: Die Defuzzifizierung, die eine Fuzzymenge auf den Mittelwert der Maxima der charakteristischen Funktion abbildet. Probleme: * Nichtstetigkeit: Verringert sich ein Maximalwert der charakteristischen Funktion, so zaehlt er nicht laenger als Maximum und die Defuzzifizierung springt. * Das MOM kann ein Element liefern, was selbst die Zugehoerigkeit 0 hat und damit die Fuzzymenge gar nicht repraesentiert. Center of Gravity-Strategie, COG-Strategie: Die Defuzzifizierung, die eine Fuzzymenge A mit Grundbereich X abbildet auf (SUM x aus X x*Chi[A](x)) / (SUM x aus X Chi[A](x)) Dieser Wert entspricht dem Zentrum der "groessten Masse" des Funktionsgraphen von Chi[A]. Probleme: * Diese Strategie kann ein Element liefern, was selbst die Zugehoerigkeit 0 hat und damit die Fuzzymenge gar nicht repraesentiert. * Diese Strategie wird sehr von Ausreissern, d.h. weitab liegenden zugehoerigen Elementen, beeinflusst. Median-Strategie: Die Defuzzifizierung, die eine Fuzzymenge A abbildet auf dasjenige Element, das die Flaeche unter dem Funktionsgraphen von Chi[A] in Haelften teilt. Problem: * Diese Strategie kann ein Element liefern, was selbst die Zugehoerigkeit 0 hat und damit die Fuzzymenge gar nicht repraesentiert. Der Unterschied zur COG-Strategie liegt in der Behandlung eines Ausreissers: Wenn dieser weiter weg von der Hauptmenge ist, so verschiebt sich das COG, nicht aber der Median. _^ 1.0 _| /\ /\ 0.5 _| / \/ \ 0.0 _|____/________\______________________/\________ 1 23 4 1 = Kleinstes Maximum 2 = MOM 3 = Median 4 = COG Kombinierte Defuzzifizierung: Die Defuzzifizierung, die eine Fuzzymenge zunaechst in mehrere Fuzzymengen aufteilt, diese mit anderen Strategien defuzzifiziert und schliesslich diese Ergebnisse verrechnet. Bedingung: Ein Ausdruck der Form f(x[1],x[2],...) op c wobei f eine reelle Funktion ist, die x[i] reelle Variablen, op ein Vergleichsoperator ist und c eine reelle Konstante. Man sagt, dass ein Tupel von reellen Werten (x[1],x[2],...) die Bedingung "erfuellt", wenn der Vergleich stimmt. Beispiel: 3*x + 6*x =< 7 Simplex-Algorithmus: Ein Algorithmus zur Loesung eines Problems der Form Suche ein Maximum fuer f(x[1],x[2],...) Beachte die Nebenbedingungen f[1](x[1],x[2],...) =< c[1] ... f[n](x[1],x[2],...) =< c[n] wobei die f[i] und f linear sind. Der Algorithmus betrachtet alle Paare (i,j) mit i und j aus {1,...n}. Zu jedem Paar bestimmt er dasjenige x=x[1],x[2],..., fuer welches gilt: f[i](x[1],x[2],...) = c[i] f[j](x[1],x[2],...) = c[j] Es ergibt sich eine Menge von Vektoren, je ein Vektor x fuer jedes Paar (i,j). Anschaulich sind dieses die Schnittpunkte der affinen Unterraeume, die diejenigen Werte enthalten, die nach den Bedingungen i und j noch in Frage kommen. Aus dieser Menge sind diejenigen Schnittpunkte auszusortieren, die irgendeine andere der n Bedingungen schon nicht erfuellen. Anschliessen berechnet der Simplexalgorithmus fuer die verbleibenden Schnittpunkte den Wert f(x[1],x[2],...) und waehlt dann denjenigen Schnittpunkt mit dem groessten Wert. Problem: Da dieser Algorithmus genau die Raender der Bedingungen ausnutzt, wird die Loesung voellig unbrauchbar, sobald sich eine Bedingung ganz wenig verschaerft. ^ | \ / Geraden: Bedingungen |------*---/------- Flaeche mit Plus: Zugelassene Werte | \ / Sternchen: von Simplex untersuchte Werte | + * |_______/_\_________ Fuzzy-Bedingung: Ein Ausdruck der Form f(x[1],x[2],...) op c Nec >= a wobei die x[i] reelle Variablen sind, f eine Funktion ist, die reelle Fuzzymengen mit den x[i] verrechnet, op ein Vergleichsoperator ist und c eine reelle Konstante. a ist eine reelle Zahl und heisst "Notwendigkeit der Bedingung". Man sagt, dass ein Tupel von rellen Werten (x[1],x[2]...) die Bedingung erfuellt, wenn gilt: Wannimmer man fuer die in f beteiligten Fuzzymengen reelle Werte mit mindestens Zugehoerigkeit 1-a waehlt, erfuellt der Ausgabewert der Funktion den Vergleich mit c. Fuzzy-Simplex-Algorithmus: Ein Algorithmus zur Loesung eines Problems der Form Suche ein Maximum fuer u Beachte die Fuzzy-Bedingungen f(x[1],x[2],...) > u Nec >= a[0] f[1](x[1],x[2],...) op[1] c[1] Nec >= a[1] ... f[n](x[1],x[2],...) op[n] c[n] Nec >= a[n] wobei die f[i] und f linear sind. Der Algorithmus ersetzt zunaechst die in den f[i] vorkommenden Fuzzymengen nach folgendem Schema Falls op[i] ein Groessergleich oder Groesser ist Falls die Fuzzymenge A den Ausdruck f[i] vergroessert Ersetze A durch min([Chi[A]](1-a[i])) (d.h. durch das kleinste Element ihres (1-a[i])-Schnittes) (fuer (a,b,c) ist dies a+(1-a[i])*(b-a) ) Falls die Fuzzymenge A den Ausdruck f[i] verkleinert Ersetze A wird durch max([Chi[A]](1-a[i])) (fuer (a,b,c) ist dies c-(1-a[i])*(c-b) ) Falls op[i] ein Kleinergleich oder Kleiner ist Falls die Fuzzymenge A den Ausdruck f[i] vergroessert Ersetze A durch max([Chi[A]](1-a[i])) (fuer (a,b,c) ist dies c-(1-a[i])*(c-b) ) Falls die Fuzzymenge A den Ausdruck f[i] verkleinert Ersetze A durch min([Chi[A]](1-a[i])) (fuer (a,b,c) ist dies a+(1-a[i])*(b-a) ) Das entstehende Problem mit nunmehr normalen Bedingungen wird dann mit dem Simplexalgorithmus geloest. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Fuzzy Logic ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Fuer den klassischen Teil: s.a. ia.txt ("Intelligence artificielle", auf franzoesisch) fuer eine sehr detaillierte Diskussion s.a. infod.txt ("Theoretische Informatik") fuer eine theoretische Abhandlung s.a. ai.txt ("Artificial intelligence", auf englisch) fuer eine praktische Abhandlung s.a. funclog.htm ("Logique des Fonctions", auf franzoesisch) oder philo.txt ("Functional Logic", auf englisch) fuer einen verallgemeinernden Ansatz s.a. fol.txt fuer eine Uebersicht ueber die klassische Logik // Dieses Kapitel enthaelt eine Vielzahl an Kalkuelen, die sich // nach m.E. wie folgt gliedern // // Modelle Formeln // crisp crisp Standard-Kalkuel // crisp fuzzy Possibilistische Resolution // fuzzy fuzzy Possibilistischer Modus Ponens // FM crisp Regelungstechnik ------------ Einfuehrung -------------- einstelliges Praedikat, boolsche Variable: Ein Symbol (meist X, Y, Z). Diese Symbole stehen meist fuer Zustaende der Welt, die erfuellt sein koennen oder nicht. // In diesem Abschnitt wird der Begriff "Variable" synonym benutzt mit // "boolsche Variable". Da wir es mit einer Logik nullter Ordnung zu // tun haben werden (s.a. ia.txt), ist auch der Begriff "einstelliges // Praedikat" gleichwertig. (crispe) boolsche Formel ueber einer boolschen Variablenmenge V: * ein Element aus V ODER * ein String der Form "~x", wenn x eine boolsche Formel ist ODER * ein String der Form "(x /\ y)", wenn x,y boolsche Formeln sind ODER * ein String der Form "(x \/ y)", wenn x,y boolsche Formeln sind ODER * ein String der Form "(x => y)", wenn x,y boolsche Formeln sind ODER * der String "true" ODER * der String "false" Die Klammerung wird oft weggelassen. Boolsche Formeln stellen Bedingungen an boolsche Variablen. // In diesem Abschnitt wird der Begriff "Formel" synonym benutzt mit // "boolsche Formel ueber einer Variablenmenge V" // Boolsche Formeln werden im Folgenden mit "phi" oder "psi" // bezeichnet, Variablen mit v[i]. // Da boolsche Formeln spaeter zu possibilistischen Formeln // erweitert werden, heissen nicht erweiterte, normale Formeln hier // "crispe Formeln". Beispiel: (jetzt \/ nie) Formelmenge: Eine Menge boolscher Formeln. Diese sind implizit /\-verknuepft, sodass eine Formelmenge als eine einzige Formel aufgefasst werden kann. true: Die Zahl 1. false: Die Zahl 0. crisper Wahrheitswert: Ein Element der Menge {true, false}. Fuzzy-Wahrheitswert: Ein Element der Menge [0;1]. Fuzzymengen-Wahrheitswert: Eine charakteristische Funktion. Modell, Variableninterpretation: Eine Abbildung von Variablen auf Wahrheitswerte. Man schreibt I(v)=a, wobei v die Variable ist und a ein Wahrheitswert. Eine solche Variableninterpretation entspricht also einem fiktiven Zustand der Welt, in dem die durch die Variablen bezeichneten Zustaende entweder erfuellt sind (I(v)=1) oder nicht. Eine Variableninterpretation kann auch als Tupel angegeben werden: (I(v[1]), I(v[2]), ... ) Beispiel: I(SC_ist_toll)=true Formelinterpretation bezueglich eines Modells I: Eine Funktion I*, die eine Formel abbildet auf einen Wahrheitswert. Eine Formelinterpretation prueft also, ob die Formel bei einem durch das Modell gegebenen Weltzustand erfuellt ist. Es gibt mehrere moegliche Formelinterpretationen. // I* ist also eine Funktion, die von der Funktion I abhaengt. Eine // korrektere Schreibweise waere demnach *[I], wobei '*' das Symbol // der Formelinterpretations-Funktion darstellt und I den Index // bildet. Standard-Formelinterpretation bezueglich eines Modells I: Die Funktion I* mit * I*(v) = I(v) * I*(~psi) = 1-I*(psi) * I*(psi /\ phi) = min { I*(phi), I*(psi) } * I*(psi \/ phi) = max { I*(phi), I*(psi) } * I*(psi => phi) = I*(~psi \/ phi) * I*(true)=1 * I*(false)=0 Beispiel: I*(SC_ist_toll \/ AVZ_ist_schoen) = max(I*(SC_ist_toll), I*(AVZ_ist_schoen)) = max(I(SC_ist_toll), I(AVZ_ist_schoen)) = max( 1 , 0 ) = 1 Aequivalenz: Der Sachverhalt, dass zwei Formeln fuer alle Modelle dieselbe Interpretation haben: I*(W1) = I*(W2) fuer alle I Dieses entspricht der intuitiven Vorstellung der Aequivalenz zweier Formeln. Man schreibt: W1 <=> W2 Gueltigkeit einer Formel phi in einem Modell I: Die Tatsache, dass I*(phi)=1. // Man schreibt auch I |= phi. Diese Schreibweise halte ich // allerdings fuer ungluecklich aufgrund der Aehnlichkeit zu W|=phi Modell einer Formelmenge W: Ein Modell I, in dem alle Formeln aus W gueltig sind: I |= phi fuer alle phicher aus W Es handelt sich also um einen Weltzustand, in dem alle durch W gegebenen Bedingungen erfuellt sind. // Der Begriff "Modell einer Formelmenge W" ist fuer das Verstaendnis // dieser Zusammenfassung nicht noetig. erfuellbare Formel: Eine Formel phi, fuer die es ein Modell I gibt mit I*(phi)=1. semantische Folgerung aus einer Formelmenge W: Eine Formel phi, sodass W <=> W /\ phi Man schreibt W |= phi. Kalkuel: Regeln zum Umformen einer Formel. syntaktische Folgerung aus einer Formelmenge W: Eine Formel phi, die sich durch ein Kalkuel aus W ergeben hat. Man schreibt W |- phi Vollstaendiges Kalkuel: Ein Kalkuel, bei dem fuer alle Formelmengen W gilt Wenn W |= phi, dann W |- phi Wenn also eine Bedingung semantisch aus einer Bedingungsmenge folgt, so soll dieses auch in dem Kalkuel so sein. Korrektes Kalkuel: Ein Kalkuel, bei dem fuer alle Formelmengen W gilt Wenn W |- phi, dann W |= phi Wenn also eine Bedingung nach dem Kalkuel aus einer Bedingungsmenge folgt, so soll dieses auch in der Realitaet der Fall sein. Ziel ist ein korrektes und vollstaendiges Kalkuel mit W |- phi dann und nur dann wenn W |= phi ------------ crispe Wahrheitswerte, crispe Formeln -------------- Standard-Kalkuel: Das folgende Kalkuel auf crispen Wahrheitswerten und crispen Formeln: * ~(A /\ B) <----> ~A \/ ~B * ~(A \/ B) <----> ~A /\ ~B * A => B <----> ~ A \/ B * A <=> B <----> (A => B) /\ (B => A) * A /\ B <----> B /\ A * A \/ B <----> B \/ A * A \/ (B /\ C) <----> (A \/ B) /\ (A \/ C) * A /\ (B \/ C) <----> (A /\ B) \/ (A /\ C) * ~~A <----> A * A /\ true <----> A * A /\ false <----> false * A \/ true <----> true * A \/ false <----> A * A /\ ~A <----> false * A \/ ~A <----> true Das Standard-Kalkuel ist korrekt und vollstaendig. Beispiel: (~~A /\ (A => B)) = (A /\ (~A \/ B)) = ((A /\ ~A) \/ (A \/ B)) = (false \/ (A /\ B)) = (A /\ B) Literal: Ein String der Form "v" oder "~v", wobei v eine Variable ist oder der String "true". Konjunktive Normalenform einer crispen Formel: Eine aequivalente Formel der Form ( L[1][1] \/ L[1][2] ... ) /\ ( L[2][1] \/ L[2][2] ... ) ... wobei die L[i][j] Literale sind. Jede crispe Formel laesst sich durch Aequivalenzumformungen auf konjunktive Normalenform bringen. Klauselform einer crispen Formel phi: Die Menge der Mengen der \/-verknuepften Literale ihrer konjunktiven Normalenform. ( L[1][1] \/ L[1][2] ... ) /\ ( L[2][1] \/ L[2][2] ... ) ... ~~> { {L[1][1], L[1][2] ... } , { L[2][1], L[2][2] ... } ... } Es handelt sich lediglich um eine andere Schreibweise. Beispiel: (A => B) = (~A \/ B) = { {~A,B} } Klauselform einer Formelmenge: Die Vereinigung der Klauselformen aller ihrer Formeln. Dieses entspricht der Tatsache, dass zwischen den Formeln von W implizit ein /\ ("und") steht. Widerspruch: Die Klausel { false }. Eine widerspruechliche Klauselform ist nicht erfuellbar. konsistent: Ohne Widerspruch. Resolution: Das folgende Kalkuel auf crispen Wahrheitswerten und crispen Formeln: 1. Bestimme die Klauselform K der Formelmenge 2. While noch nicht alles durchprobiert 3. Waehle zwei Klauseln aus K, in denen ein Literal einmal negiert (d.h. mit "~") und einmal nicht negiert vorkommt 4. Bilde die Vereinigung der beiden Klauseln und loesche aus ihr das negative und das nicht negative Vorkommen des Literals 5. Ist die entstehende Klausel leer, so ist W nicht konsistent, Ende 6. Fuege die Klausel zu K hinzu 7. EndWhile 8. W ist konsistent. Die Resolution ist ein Unterverfahren zum Standard-Kalkuel, sie erfolgt nach dem Prinzip: { phi, ~L } { psi, L } ~~~~> { phi, psi } Welches gilt weil (phi \/ ~L) /\ (L \/ psi) <=> (phi /\ (L \/ psi)) \/ (~L /\ (L \/ psi)) <=> (phi /\ (L \/ psi)) \/ (~L /\ L) \/ (~L /\ psi) <=> (phi /\ (L \/ psi)) \/ false \/ (~L /\ psi) <=> (phi /\ (L \/ psi)) \/ (~L /\ psi) <=> (phi \/ (~L /\ psi)) /\ (L \/ psi \/ (~L /\ psi)) <=> (phi\/~L) /\ (phi\/psi) /\ (L \/ psi \/ ~L) /\ (L \/ psi) <=> (phi\/~L) /\ (phi\/psi) /\ true /\ (L \/ psi) <=> (phi\/~L) /\ (phi\/psi) /\ (L\/psi) // Fuer eine detaillierte Abhandlung siehe funclog.htm (franzoesisch) Ein Widerspruch aeussert sich in diesem Verfahren durch das Herleiten von false, d.h. das Herleiten einer leeren Klausel. Die Resolution ist vollstaendig und korrekt. Resolutionsbeweis einer crispen Formel phi aus einer Formelmenge W: Der folgende Algorithmus: 1. W := W /\ ~ phi 2. Wende die Resolution auf W an 3. Ist W konsistent, folgt phi nicht aus W Ist W inkonsistent, so folgt phi aus W, es gilt W |- phi Diesem Algorithmus liegt folgende Idee zugrunde: W ist konsistent. Nun nimt man an, dass phi falsch ist und fuegt es zum Weltmodell W hinzu. Dann leitet man Folgerungen ab und stoesst z.B. auf Inkonsistenz. Da W alleine ja erfuellbar war, muss die fehlende Erfuellbarkeit also an ~ phi liegen: Sei I ein Modell von W, d.h. I*(W) = 1 0 = I*(W /\ ~ phi) = min(I*(W),I*(~phi)) = min(1,I*(~phi)) = I*(~phi) = 1 - I*(phi) => I*(phi)=1 Also ist phi fuer jedes Modell von W erfuellt, die Formel ist bewiesen. Beispiel zum Beweis {A,C} {~A} {~C} von C aus {{A,C},{A}}: \ / ____/ {C} / \ / {} ------------ crispe Wahrheitswerte, Fuzzy-Formeln -------------- schwaches Notwendigkeitsmass: Eine Abbildung N, die einer boolschen Formel eine reelle Zahl aus [0;1] derart zuordnet, dass N(phi /\ psi) = min(N(phi), N(psi)) N(psi) = N(phi) fuer psi <=> psi Ein schwaches Notwendigkeitsmass gibt an, wie sehr eine Formel aus logischen Gruenden sowieso mindestens gelten muss. Notwendigkeitsmass: Ein schwaches Notwendigkeitsmass, bei dem zusaetzlich gilt: N(true) = 1 N(false) = 0 possibilistische Formel, Fuzzy-Formel: Eine crispe Formel phi, versehen mit einer reellen Zahl alpha aus [0;1]. Meist schreibt man einfach (phi, alpha) Die reelle Zahl gibt an, wie sehr die Formel tatsaechlich gilt. Sie heisst "Glaubwuerdigkeit" und ist so etwas wie ein kontingenter Wahrheitsgrad. Gueltigkeit einer possibilistischen Formel (phi, alpha) in einem crispen Modell I: Ihre Eigenschaft, dass N(phi) >= alpha und I*(phi)=1. Inkonsistenz eines crispen Modells I mit einer possibilistischen Klauselmenge zum Grad a: Der Sachverhalt, dass max({ alpha[i] | I*(phi[i])=false }) >= a D.h. man findet zunaechst diejenigen Formeln phi[i], die boolsch nicht erfuellt sind. Unter diesen bestimmt man das Maximum ihrer Glaubwuerdigkeiten. Ist dieser Wert groessergleich a, so ist das Modell (auch) zum Grad a inkonsistent. Kompatibles Modell zu einer possibilistischen Formelmenge W: Ein crispes Modell I mit I*(phi) >= alpha fuer alle (phi,alpha) aus W Inkonsistenz einer possibilistischen Klauselmenge W zum Grad alpha: Ihre Eigenschaft, dass alle crispen Modelle zum Grad alpha inkonsistent sind. Man schreibt: inc(W) >= alpha Jede possibilistiscxhe Klauselmenge ist damit zum Grad 0 inkonsistent. Man sucht daher immer den hoechsten Grad an Inkonsistenz, der noch zutrifft. Hat eine Klauselmenge ein kompatibles Modell, so ist ihre Inkonsistenz 0. Maximale Inkonsistenz einer possibilistischen Klauselmenge W: Der Wert max({ alpha | inc(W)>= alpha}). Diesen Inkonsistenzgrad kann man nach dem folgenden Schema berechnen: Variablen Formeln Inkonsistenz V1 V2 ... | phi1 phi2 ... | ---------------------------------------------------------- 0 0 ... | 0 alpha2 ... | Maximum der Zeile 1 0 ... | alpha1 alpha2 ... | Maximum der Zeile ... | ... | ... ---------------------------------------------------------- | Minimum der Spalte Dabei durchlaufen die Variablen alle moeglichen Belegungen (die Zeilen stellen alle moeglichen crispen Modelle dar) und in der 2. Spalte vermerkt man, ob die Formeln in dem Modell crisp erfuellt sind (null) oder nicht (zugehoeriges alpha). Das Maximum der Zeile gibt den Unerfuelltheitsgrad des Modells an, das Minimum der Spalte den minimalen Unerfuelltheitsgrad und damit die maximale Inkonsistenz. Alternative Berechnung: Man sortiert die Formeln phi nach ihren alphas (grosse alphas nach vorne) und schreibt: _________*_______ / \ phi1, alpha1 V[i]=Wert V[j]=Wert ... / \ phi2, alpha2 V[k]=Wert V[l]=Wert ... ... ... ... Dabei sagt jedes "V[i]=Wert" aus, welchen Wert die Variable i haben muss, damit die links stehende Formel erfuellt ist. Zur Erfuellung einer Formel gibt es meist mehrere Alternativen, die als Baumstruktur aufgezeichnet werden (im Beispiel V[i]=Wert oder V[j]=Wert zur Erfuellung der Formel phi1). Nun fuegt man die naechste Formel hinzu und sagt fuer jeden bisherigen Ast, welche zusaetzlichen Variablenbelegungen noetig sind, um die Formel zu erfuellen. Jeder Ast traegt dabei alle vorherigen Variablenbelegungen mit sich. Auch dabei kann es wieder Alternativen geben. Ist eine Formel fuer einen Ast gar nicht erfuellbar, so hoert man auf, den Ast weiter zu entwickeln. Das alpha derjenigen Formel, die den letzten Ast kaputt macht, ist die Inkonsistenz der Formelmenge. // Dieses Verfahren ist selbst gestrickt semantische Folgerung aus einer possibilistischen Formelmenge W: Eine possibilistische Klausel (phi, alpha), bei der gilt: inc(W \/ {(~phi, 1)}) >= alpha Dieses ist dasselbe wie I*(phi) >= alpha fuer alle kompatiblen Modelle I Man schreibt: W |= (phi, alpha) syntaktische Folgerung aus einer possibilistischen Formelmenge W: Eine possibilistische Klausel (phi, alpha) die sich durch ein possibilistisches Kalkuel ergeben hat. Man schreibt W |- (phi, alpha) Resposs, possibilistische Resolution: Das wie folgt modifizierte Resolutions-Kalkuel auf possibilistischen Formeln mit crispen Wahrheitswerten: Eine Herleitung einer neuen Klausel erfolgt nach dem Schema (phi, L, a) (psi, ~L, b) ~~~> (phi, psi, min(a,b)) Resposs ist fuer beliebiges schwaches Notwendigkeitsmass N korrekt: Sind (phi, L, a) und (psi, ~L, b) beide gueltig, so ist auch (phi, psi, min(a,b)) gueltig: N(phi \/ psi) >= min( N(phi \/ psi), N((phi \/ L) /\ (psi \/ L)) ) = N( (phi \/ psi) /\ (phi \/ L) /\ (psi \/ L) ) = N( (phi \/ L) /\ (psi \/ L) ) // nach obiger Aequivalenz = min(N(phi \/ L), N(psi \/ L)) >= min(a,b) Resposs ist auch vollstaendig: W |= (phi, alpha) <=> W \/ (~phi,1) ist zum Grad alpha inkonsistent <=> W/alpha \/ (~phi,1) ist zum Grad alpha inkonsistent wobei W/alpha diejenige Teilmenge von Formeln aus W ist, deren Glaubwuerdigkeit >=alpha ist <=> projPhi(W/alpha) /\ ~ phi ist inkonsistent wobei projPhi(W/alpha) die Menge der Formeln von W/alpha ist, ohne deren tatsaechlcihe Gueltigkeiten <=> projPhi(W/alpha) |- phi Da in ResPoss immer nur das Minimum der Glaubwuerdigkeiten den neuen Formeln zugewiesen wird, folgt => W/alpha |-resposs (phi, alpha') mit alpha'>alpha => W |- (phi, alpha) Beweis einer Variable V aus einer possibilistischen Formelmenge durch Resposs: Das Hinzufuegen von (~ V,1) zur Formelmenge und das Ausfuehren von Resposs. Ergibt sich ein Widerspruch mit Grad alpha, so ist V zum Grad alpha wahr. ------------ Fuzzy-Wahrheitswerte, Fuzzy-Formeln -------------- Standardinterpretation crispen Formel bezueglich eines Fuzzy-Modells I: Die Funktion I* mit * I*(v)=I(v) fuer alle Variablen v * I*(~psi) = 1-I*(psi) * I*(psi /\ phi) = T(I*(phi), I*(psi)) * I*(psi \/ phi) = C(I*(phi), I*(psi)) * I*(psi => phi) = I*(~psi \/ phi) Dabei sind T und C T-Norm und T-Conorm. eingeschraenkte possibilistische Formelmenge: Eine Menge, deren Elemente die folgende Form haben: (phi => V, alpha) wobei phi eine crispe Formel aus /\ und \/ ohne Negation ist und V eine Variable. kompatibles Fuzzy-Modell einer possibilistischen Formelmenge W: Ein Fuzzy-Modell I, sodass I*(phi) >= alpha fuer alle (phi, alpha) aus W Minimales Modell einer eingeschraenkten possibilistischen Formelmenge W: Das Fuzzy-Modell I[W] mit I[W](v) = ((v, alpha) in W) ? alpha : 0. I[W] ist nicht notwendigerweise ein kompatibles Modell. // Nach Konvention heisst I[W] auch W, was etwas unschoen ist und // deshalb in dieser Zusammenfassung keine Anwendung findet Maximales Modell eine eingeschraenkten possibilistischen Formelmenge W: Das Fuzzy-Modell I mit I(v)=1. Es ist in jedem Fall kompatibel. "Richtiges Modell einer eingeschraenkten possibilistischen Formelmenge W": Das kompatible Fuzzy-Modell I mit den kleinsten Werten fuer die Variablen. Diese Werte sind in jedem Fall groessergleich den Werten des minimalen Modells. Residuum bezueglich einer stetigen T-Conorm C: Die Funktion RC:[0;1]^2 -> [0;1], die zwei Zahlen a und b abbildet auf RC(a,b) = inf({c | C(a,c)>=b}) Das Residuum liefert also dasjenige zweite Argument der T-Conorm, welches mindestens noetig ist, um b zu erhalten. Zwischen den Residua einer T-Norm und der zugehoerigen T-Conorm besteht folgender Zusammenhang: // ja, welcher war's denn nochmal (?) Residuum bezueglich Cmax: Die Funktion RCmax(a,b) = (a>=b)?0:b. Residuum bezueglich Cprod: Die Funktion RCprod(a,b) = // was denn (?) Residuum bezueglich Cluka: Die Funktion RCluka(a,b) = (a>=b)?0:b-a. MPposs, Fuzzy-Modus-Ponens: Das folgende Kalkuel auf possibilistischen Formeln mit Fuzzy-Wahrheitswerten: (A => B, a) (A, b) ~~~> (B, RC(1-a,b)) Folgt aus A die Formel B, und weiss man, dass A gilt, so schliesst man auf A mit minimal noetiger Glaubwuerdigkeit. MPposs ist vollstaendig und korrekt fuer alle eingeschraenkten Formelmengen. Wendet man MPposs iteriert auf alle Formeln an, so steigen die Glaubwuerdigkeiten der Variablen monoton und naehern sich dem richtigen Modell. Um zu zeigen, dass eine Variable nicht zu einem noch hoeheren als dem abgeleiteten Grad wahr sein kann, findet man ein kompatibles Modell, indem die Variable eben genau diesen abgeleiteten Wert hat. Beispiel: A => B 0.3 A 0.8 --------------- ~~~~~> B RCmax(0.7,0.8) = 0.8 Ex falso quod libet: Das Prinzip, dass aus einer Fuzzy-Formelmenge, die zum Grad alpha inkonsisten ist, jede Formel zum Grad alpha abgeleitet werden kann. ------------ Fuzzymengen-Wahrheitswerte, crispe Formeln ------------- Fuzzymengen-Implikation: Eine Funktion, die zwei Fuzzymengen eine neue zweidimensionale Fuzzymenge zuordnet, die angibt, inwieweit die erste in der zweiten eingeschlossen ist. Mit der Fuzzy-Implikation ist es moeglich, auf Praedikaten zu rechnen, deren Wahrheitswerten komplette Fuzzymengen sind. Dieses findet vor allem in der Regelungstechnik Anwendung. "Quadratische Form einer Funktion f:X x X -> Y": Die Funktion g(x)=f(x,x). Fuzzymengen-Einschluss: Die quuadratische Form einer Fuzzymengen-Implikation auf zwei Fuzzymengen mit demselben Grundbereich. Das Ergebnis ist dann eine eindimensionale Fuzzymenge auf diesem Grundbereich, die angibt, inwieweit die eine Menge in der anderen liegt. S-Implikation bezueglich einer T-Conorm C: Die Fuzzymengen-Implikation, die zwei Fuzzymengen A und B die Fuzzymenge A=>B zuordnet, die gegeben ist durch Chi[A=>B](x,y) = C(1-Chi[A](x), Chi[B](y)) Kleene-Dienes-Implikation: Die S-Implikation bezueglich Cmax: Chi[A=>B](x,y) = max(1-Chi[A](x), Chi[B](y)) Lukasiewicz-Implikation: Die S-Implikation bezueglich CLuka: Chi[A=>B](x,y) = max(1, 1-Chi[A](x)+Chi[B](y)) Residuum bezueglich einer stetigen T-Norm T: Die Funktion RT:[0;1]^2 -> [0;1], die zwei Zahlen a und b abbildet auf RT(a,b) = sup({c | T(a,c) =< b}) Das Residuum liefert also dasjenige zweite Argument der T-Norm, welches mindestens noetig ist, um b zu erhalten. RT hat ein zugehoeriges RC, welches sich aus dem Zusammenhang zwischen T-Norm und T-conorm ergibt. Residuum bezueglich Tmin: Die Funktion RTmin(a,b) = (a =< b)?1:b Residuum bezueglich der prod-Norm: Die Funktion RTprod(a,b) = (a=B zuordnet, die gegeben ist durch Chi[A=>B](x,y) = RT(1-Chi[A](x), Chi[B](y)) Goedel-Implikation: Die Residuum-Implikation bezueglich Tmin. Gaines-Implikation: Die Residuum-Implikation bezueglich Tprod. T-Implikation bezueglich einer T-Norm T: Die Fuzzy-Implikation, die zwei Fuzzymengen A und B diejenige Fuzzymenge A=>B zuordnet, die gegeben ist durch Chi[A=>B](x,y) = T(Chi[A](x), Chi[B](y)) Diese Implikation folgt der Intuition, dass man nicht wirklich von "Einschluss" sprechen kann, wenn Chi[A](x)=0 ist. Mamdani-Implikation: Die T-Implikation bezueglich Tmin. Larsen-Implikation: Die T-Implikation bezueglich Tprod. Fuzzymengen-Formel: Eine boolsche Formel mit Fuzzymengen-Wahrheitswerten. Standardformelinterpretation bezueglich eines Fuzzymengen- Modells I: Die Funktion I* mit * I*(v)=Chi[v] fuer alle Variablen v * I*(~psi) = 1-I*(psi) * I*(psi /\ phi) = I*(phi) x I*(psi) Haben I*(phi) und I*(psi) denselben Grundbereich, so kann auch eine einfache T-Norm benutzt werden * I*(psi \/ phi) = ? * I*(psi => phi) = Chi[A=>B] ist eine Fuzzy-Implikation Dabei sind T und C T-Norm und T-Conorm. Compositional Rule of Inference, CRI: Das folgende Kalkuel auf Fuzzymengen-Formeln: (A => B) A' ~~~~> B' = (A=>B) o A' mit Chi[B'](y) = max({ min(Chi[A'](x),Chi[A=>B](x,y)) | x aus X}) wobei A und A' denselben Grundbereich X haben muessen. B' hat denselben Grundbereich wie B. Man erweitert zu (A1 /\ A2 /\ ... => B) (A1' /\ A2' /\ ...) ~~~~~~~> B' = (A1 /\ A2 /\ ... => B) o (A1' /\ A2' /\ ...) Abschneiden: Die Funktion, die eine Fuzzymenge A und eine Zahl a aus [0;1] abbildet auf die Fuzzymenge A', die gegeben ist durch Chi[A'](x) = min(a,Chi[A](x)) CRI mit Mamdani: Die Compositional Rule of inference, bei der sich Chi[A=>B] durch Mamdani-Implikation berechnet. In dem Schema (A => B) A' ~~~~> B' ergibt sich B' dann als die Fuzzy-Menge B, deren charakteristische Funktion abgeschnitten wurde bei dem Maximum von Chi[A/\A']. _^ A A' ^ B 1.0 _| /\ /\ | /\ 0.5 _| / \/..\..........|.../..\ 0.0 _|____/___/\___\___ |__/####\______ ^--- B' Aggregationsoperator: Eine Funktion agg:[0;1]^2->[0;1], fuer die gilt * agg(x,y) = agg(y,x) * agg(x, agg(y,z)) = agg(agg(x,y), z) * Wenn a= B[1] ... A[n] => B[n] A' wobei die A[i] und A' denselben Grundbereich haben und die B[i] untereinander ebenso ueber einen selben Grundbereich definiert sind. B' ist dann die Fuzzymenge, die gegeben ist durch Chi[B'](x) = agg(Chi[(A[1]=>B[1]) o A'](x), Chi[(A[1]=>B[1]) o A'](x), ... ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Fuzzy-Regelungstechnik ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Regelungssystem: Ein (physisches) System, bei dem Messgroessen bestimmt werden koennen und welches durch Stellgroessen beeinflusst werden kann. Ziel ist, das System so durch die Stellgroessen zu beeinflussen, dass die Messgroessen einen Sollwert annehmen. umgedrehtes Pendel: Ein Regelungssystem, bei dem eine stehenden Stange balanciert werden soll. Messgroessen sind ueblicherweise die Auslenkung zur Senkrechten und die Beschleunigung, Stellgroesse ist eine Kraft auf das Pendel. Kontrolle: Das Einstellen von Stellgroessen in einem Regelungssystem. Open-Loop-Control: Die Kontrolle durch Einstellen konstant im Vorhinein berechneter Stellgroessen. Closed-Loop-Control: Die Kontrolle durch stetiges Anpassen der Stellgroessen nach den Messgroessen. Regler: Eine automatische Open-Loop-Control, d.h. eine Abbildung von Messgroessen auf Stellgroessen. Die Stellgroesse zum Zeitpunkt t wird mit u(t) bezeichnet, die Messgroesse zum Zeitpunkt t mit x(t). Der Sollwert fuer x wird ohne Beschraenkung der Allgemeinheit mit 0 angenommen. Differentialgleichung: Eine Gleichung, die einen Zusammenhang zwischen einer Funktion und ihren Ableitungen ausdrueckt. P-Regler, Proportional-Regler: Ein Regler, bei dem sich die Stellgroesse berechnet als u(t) = -alpha*x(t) Dieser Regler wirkt also einer Entfernung vom Sollwert 0 linear entgegen. Die reelle Konstante alpha steuert dabei die Heftigkeit der Reaktion. Problem: Der P-Regler bewegt x immer ueber das Ziel 0 hinaus, die Werte schlingern um den 0-Punkt. PD-Regler, Proportional-Differential-Regler: Ein Regler, bei dem sich die Stellgroesse berechnet als u(t) = -alpha*x(t) - beta*x'(t) Der PD-Reglerbeachtet also auch die Aenderungsrate von x und wenn sich x schnell in Richtung 0 bewegt, faellt u(t) kleiner aus. PID-Regler, Proportional-Integral-Differential-Regler: Ein Regler, bei dem sich die Stellgroesse berechnet als u(t) = -alpha*x(t) - beta*x'(t) - gamma*INT 0->t x(T)dT Der PID-Regler kann auch mit konstanten Gegenkraeften umgehen, da sich eine staendige Auslenkung von x in einem positiven Integralwert aeussert, der u mitbeeinflusst. n-Punkt-Regler: Ein Regler, der den gesamten Definitionsbereiche von x in n aneinander anschliessende Intervalle aufteilt. Zu jedem Intervall hat er einen Stellwert u fest gespeichert. Hysterese: Das Verhalten eines Reglers, die Stellgroesse abhaengig vom vorhergehenden Wert der Stellgroesse zu machen. Beispiel: Eine automatische Gangschaltung schaltet erst bei 60 km/h vom 3. in den 4. Gang aber umgekehrt bei 50 km/h vom 4. in den 3. Wuerde immer bei einem fixen Punkt von 55 km/h geschaltet, so wuerde dauernd der Gang gewechselt, wenn man ungefaehr konstant 55 km/h faehrt. Kennlinienregler: Ein INF-Punkt-Regler, der zu jedem Messwert einen Stellwert gespeichert hat. Fuzzifizierung: Eine Funktion f, die eine relle Zahl abbildet auf eine Fuzzymenge, die diese Zahl in ihrer Toleranz hat. Singleton-Fuzzifizierung: Die Fuzzifizierung f(w) = A mit Chi[A](x) = x=w?1:0 Extensionale Fuzzifizierung: Die Fuzzifizierung, die einen Wert w auf die extensionale Huelle von {w} abbildet. Dreiecksfuzzifizierung: Die Fuzzifizierung, die w abbildet auf die Dreiecksmenge (w-eps,w,w+eps), wobei eps eine Konstante ist. Fuzzy-Regler: Ein Regler, der mit Fuzzygroessen arbeitet. Die Fuzzygroessen werden aus natuerlichsprachlichen Beschreibungen von Loesungsansaetzen gewonnen. Oft berechnet man fuer den Einsatz eines Fuzzyreglers fuer alle Messgroessen die Stellgroessen im Voraus und baut daraus einen Kennlinienregler. Typischer Fuzzy-Regler: Ein Regler, der * die Messgroesse fuzzifiziert * Fuzzy Stellgroessen mithilfe von Fuzzymengen-Formeln und der aggregierten CRI berechnet * diese Fuzzy Stellgroessen defuzzifiziert und ausgibt Mamdani-Regler: Ein typischer Fuzzy-Regler, der ueber Regeln der folgenden Form verfuegt: IF (x[1] in A[1][i]) AND (x[2] in A[2][i]) ... THEN (y aus Y[i]) Dabei sind die x[j] die Messgroessen (crisp), die A[j][i] sind Eingabe-Fuzzymengen ueber dem Grundbereich von x[j], y ist die Stellgroesse und Y[i] ist eine Ausgabe-Fuzzymenge ueber dem Grundbereich der Stellgroesse. Fuer Messgroessen x[1]...x[n] berechnet sich die Ausgabe als Abschneiden von Y[i] auf der Hoehe von min({ Chi[A[j][i]](x[j]) | j=1..n }) Die Fuzzymenge der Stellgroesse ergibt sich durch Aggregation der Ausgaben aller Regeln. // Eigentlich sollten doch die Messgroessen fuzzifiziert werden... Die durch einen Mamdani-Regler berechnete Funktion ist stetig, falls alle Elemente der Eingabegrundbereiche durch eine Regel erfasst werden und alle Fuzzymengen stetige charakteristische Funktionen haben. Beispiel fuer Regel IF (x1 in A1]) AND (x2 in A2) THEN (y aus Y): _^ A1 ^ A2 ^ Y 1.0 _| /\...........|......../\............|....../\...... 0.5 _| / |\ | / \...........|...../..\..... 0.0 _|____/__|_\______ |______/___|\_____ |____/####\____ x1 x2 # = y (Bild der naechsten Regel) (Ergebnis der naechsten Regel) ... ... ----------------------------------------------------------- (Gesamtergebnis durch Aggregation) Ueberlapp zweier Fuzzymengen: Der Support ihres Schnittes. Symmetrische Dreicksmenge: Eine Dreicksmenge der Form (a-eps,a,a+eps). Gleichmaessige Abdeckung eines Grundbereichs mit Fuzzymengen: Ein Tupel von symmetrischen Dreiecks-Fuzzymengen, sodass * die Vereinigung ihrer Supports den Grundbereich ergibt * jede Fuzzymenge mit ihrem rechten und linken Nachbarn etwas ueberlappt. Design-Regeln fuer Mamdani-Regler: * Alle relevanten Bereiche fuer Messwerte sollten durch mindestens 1 Regel abgedeckt sein * Ein Bereich sollte nicht mit mehr als 3 regeln abgedeckt werden, sonst wird das Verhalten undurchsichtig * Es ist sinnvoll, Bereiche gleichmaessig abzudecken. Mamdani-Regler mit monotoner Regelbasis: Ein Mamdani-Regler, bei dem die Eingabefuzzymengen aller Regeln fuer dieselbe Messgroesse eine gleichmaessige Abdeckung des Grundbereichs dieser Messgroesse bilden. Effekt des Ueberlapps der Eingabefuzzymengen eines Mamdani-Reglers mit monotoner Regelbasis: * Gar kein Ueberlapp: Schlecht, da es dann fuer Messwerte, die genau an den Grenzen der Eingabe-Fuzzymengen liegen, keine Regel gibt * Minimal-Ueberlapp: Die Ausgabe ist eine Treppenfunktion, da fuer eine Eingabe x[1] nur eine einzige Regel anwendbar ist. Die Aggregation ueber alle Regelausgaben ist also die abgeschnittene Ausgabefuzzymenge ebendieser Regel. Wird diese defuzzifiziert, so ergibt sich immer derselbe Ausgabewert. Sobald x[1] in den Bereich der naechsten Regel wandert, schlaegt nur diese an und die Ausgabe wechselt unstetig zu einem neuen Wert. * Grosser Ueberlapp: Die Treppenfunktion verschluert mehr und mehr. Diese gilt nur, falls die Eingabemengen symmetrische Dreiecksmengen sind. Es folgt ein Bildchen fuer zwei Regeln 1 und 2, die jeweils eine Eingabemenge A[1][1] bzw. A[1][2] haben. Die Eingabemengen wurden in dasselbe Diagramm gezeichnet. Rechts ist das aggregierte und defuzzifizierte Gesamtergebnis in Anhaengigkeit von der Messgroesse dargestellt: _^ A[1][1] A[2][1] ^ Y aggregiert & defuzzifiziert 1.0 _| /\ /\ | _______ 0.5 _| / \ / \ |_____ 0.0 _|____/____\/____\__ |______________ _^ ^ 1.0 _| /\ /\ | _______ 0.5 _| / \/ \ |____/ 0.0 _|____/___/\___\____ |______________ Effekt des Ueberlapps der Ausgabefuzzymengen eines Mamdani-Reglers mit monotoner Regelbasis: Nur ein sehr geringer. Approximationsvollstaendigkeit des Mamdani-Reglers: Da der Mamdani-Regler Treppenfunktionen einschliesst und Treppenfunktionen approximationsvollstaendig sind, ist auch der Mamdani-Regler approximationsvollstaendig. Takagi-Sugeno-Regler, TSC: Ein Fuzzy-Regler, der ueber Regeln der folgenden Form verfuegt: IF (x1 in A[1][i]) AND (x2 in A[2][i]) ... THEN y[i] = f[i](x1,x2,...) Dabei sind die A[1][i Fuzzymengen ueber dem Grundbereich der Messgroessen und f[i] ist eine reelle Funktion. Die Ausgabe berechnet sich zu u = SUM i=1..n alpha[i]*f[i](x) / SUM i=1..n alpha[i] wobei alpha[i] = min({Chi[A[1][i](x1), Chi[A[2[i](x2), ... }) Es handelt sich also um ein gewichtetes Mittel der Funktionswerte der f[i]. // Hat man eine einzige Eingabe und haben die A[j][i] Gaussfunktionen // als charakteristische Funktionen und sind die f[i] konstant, so hat // man ein Radiale-Basis-Funktionen-Netz, siehe nn.txt Stabilitaet eines Fuzzy-Reglers: Seine Eigenschaft, dass die Messgroessen fuer beliebige Ausgangswerte immer gegen die Sollwerte streben. Systembeschreibungsfunktion: Eine Funktion f, die das Verhalten eines Regelungssystems wie folgt beschreibt: x'(t) = f(x(t),u(t)) Gegeben eine Messgroesse und eine Stellgroesse sagt diese Funktion aus, wie sich die Messgroesse veraendern wird (deswegen die Ableitung), wenn die Stellgroesse angewandt wird. Verifikation eines Fuzzy-Reglers: Der Beweis, dass der Fuzzyregler stabil ist. Dazu benoetigt man im Allgemeinen eine Systembeschreibungsfunktion. positiv definite Funktion: Eine reelle Funktion f, sodass f(x)>0 und f(x)=0 nur im Falle x=0. negativ definite Funktion: Eine reelle Funktion f, sodass f(x)<0 und f(x)=0 nur im Falle x=0. Lyapunov-Funktion: Eine positiv definite Funktion, die eine Messgroesse x(t) als Eingabe hat und deren Ableitung nach der Zeit t negativ definit ist. Lyapunov-Methode: Das folgende Verfahren zur Verifikation eines Fuzzy-Reglers: Man sucht eine Lyapunov-Funktion V. Gibt es diese, so werden aufgrund der negativen Ableitung die Werte V(x(t)) fuer fortlaufendes t immer kleiner, bis irgendwann ab einem Zeitpunkt nur noch V(x(t))=0 gilt. Dann aber heisst dies, dass x(t)=0: Das System hat sich in den Sollzustand eingependelt. Problem: Es ist sehr schwer, eine Lyapunov-Funktion zu finden. Zustandsraum-Analyse: Das folgende Verfahren zur Verifikation eines Fuzzy-Reglers: Man unterteilt den Bereich der Messgroesse(n) in gleichgrosse Intervalle ("Raster") und berechnet exemplarisch fuer jeden Rastermittelpunkt x die zugehoerige Stellgroesse u. Fuer jedes Raster vermerkt man das Ergebnis der Systembeschreibungsfunktion x' = f(x,u). Diese Ableitung zeigt, in welche Richtung sich x bewegen wird, man kann daraus das Raster bestimmen, in dem x als naechstes liegen wird. Nun klappert man alle Raster ab und zeigt, dass, egal in welchem Raster x startet, x am Ende immer in 0 zu liegen kommt. Problem: Dieses Verfahren ist sehr aufwaendig. Gewinnung eines Mamdani-Reglers durch Fuzzy-Clustering: Die Erstellung eines Mamdani-Reglers aus einer Datenmenge aus Messwert/Stellwert-Paerchen. Dazu clustert man die Datenmenge zunaechst mit Fuzzy k-means. Fuer jede Gruppe fuehrt man dann eine Regel ein, deren Eingabefuzzymenge sich aus der Projektion der Gruppenmitglieder auf die Messgroessen ergibt. Die Ausgabefuzzymenge ergibt sich durch Projektion der Gruppenmitglieder auf die Stellgroesse. Damit ist gemeint: Alle Mitglieder einer Gruppe haben aehnliche Messwerte. Man konstruiert nun eine Fuzzymenge, zu der jeder Messwert x die Zugehoerigkeit hat, die der zu x naechstgelegene Datenpunkt zur Gruppe hat. Falls x also nahe beim Gruppenmittelpunkt liegt, so ist Chi(x)=1. Falls x weiter weg liegt, so sinkt Chi(x). Aehnlich verfaehrt man fuer die Stellgroesse. Problem: Dieses Verfahren macht alle Gruppen rechteckig, d.h. es sind keine beliebig verschmierten Gruppenzugehoerigkeiten moeglich. ^ * = Beschreibung von Stellgroesse |- * Stellwert/Messwert- |-- + * Paar |- * * + = Zentroid | | | |_______|||_________________ Messgroesse Die angedeuteten Fuzzymengen links und unten sind Eingabe- und Ausgabemenge der zum Zentroid gehoerigen Mamdani-Regel. Neuro-Fuzzy-Verfahren: Die Umwandlung eines Fuzzy-Regler in ein neuronales Netz, welches dieselbe Funktion berechnet. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Optimierung ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ s.a. ia.txt ("Intelligence artificielle", auf franzoesisch) fuer eine detaillierte Beschreibung der Optimierungsalgorithmen Optimum einer Menge: Ihr Minimum oder Maximum, je nach Zielsetzung. Schreibweise hier: opt(A)=x. (lokales) Optimum einer Funktion: Ein (lokales) Minimum oder (lokales) Maximum, je nach Zielsetzung. Optimierung einer Funktion: Das Finden eines Optimums. Man geht davon aus, dass die Funktion einstellig ist, als Definitionsbereich R^n hat und als Wertebereich R. Einfache Optimierung einer Funktion: Das Suchen der Optima in der Menge der Nullstellen der Ableitung. Gradientensuche: Der folgende Algorithmus zur Optimierung einer Funktion f: 1. x=zufaelliger Wert 2. While f(x) noch nicht gut genug 3. Berechne ein neues x aus x und f'(x) 4. EndWhile Fuer Schritt 3 gibt es eine Unmenge an Verfahren, siehe nn.txt. Simplex im Raum der Dimension n: Ein Tupel aus n+1 Punkten, wobei alle Teilmengen aus n Punkten linear unabhaengig sind. Beispiel: In R^2 ein Dreieck. Simplex-Search: Der folgende Algorithmus zum Optimieren einer Funktion f : 1. Sei (x[1],...x[n+1]) ein zufaellig initialisiertes Simplex 2. While true 3. Berechne f(x[i]) fuer i=1..n+1 4. Sei best der Index mit f(x[best]) = opt({ f(x[i]) | i=1..n}) 5. Falls f(x[best]) schon optimal genug ist, Ende 6. Sei worst der Index mit f(x[worst]) = -opt({ -f(x[i]) | i=1..n}) 7. Sei secbest der Index mit f(x[secbest]) = opt({ f(x[i]) | i=1..n, i!=best}) 8. Berechne den Schwerpunkt des Simplex ohne x[worst]: sx = ((SUM i=1..n+1 x[i]) - x[worst]) / n 9. Berechne die Spiegelung von x[worst] bezueglich sx: x* = 2*sx - x[worst] 10. Teste, ob Spiegelung besser als bester: If f(x*) besser als f(x[best]) Then x[worst] = 3*sx - 2*x[worst], weiter bei 15 11. Teste, ob Spiegelung besser als Zweitbester: If f(x*) besser als f(x[secbest]) Then x[worst] = x*, weiter bei 15 12. Teste, ob 3/4 der Strecke besser als Zweitbester If f(3*sx/2-x[worst]/2) besser als f(x[secbest]) Then x[worst] = 3*sx/2-x[worst]/2, weiter bei 15 13. Teste, ob 1/4 der Strecke besser als Zweitbester If f(sx/2-x[worst]/2) besser als f(x[secbest]) Then x[worst] = sx/2-x[worst]/2, weiter bei 15 14. Das Dreieck muss verkleinert werden For i=1..n+1 x[i]=x[i]-(x[i]-x[best])/2 EndFor 15. EndWhile Dieser Algorithmus laesst also ein Simplex in die guten Richtungen "ertasten" und zieht das Simplex dann um das Optimum herum zusammen. Beispiel: Simplex im R^2, die Zahlen sagen aus, an welche Position x[worst] bewegt werden wuerde, wenn der entsprechende Schritt des obigen Algorithmus zum Einsatz kaeme: x[secbest] Bei Schritt 14: /| / | x[worst]/13| 12 11 10 /| \ | / | \ | \ | \| \| x[best] Kontinuierliche Menge: Eine Menge reeller Zahlen, bei der es zwischen zwei Werten immer einen Wert gibt, der in der Menge ist. // Stimmt das (?) Diskrete Menge: Eine Menge, die nicht kontinuierlich ist. Diskrete Funktion: Eine Funktion in die reellen Zahlen, deren Definitionsbereich diskret ist. Man kann eine nicht diskrete reelle Funktion durch Beschraenkung auf bestimmte (interessante) Eingabewerte diskret machen. Nachbar-Menge eines Eingabewertes x einer diskreten Funktion: Eine Menge anderer Eingabewerte, die in irgendeiner Weise "nahe" an x liegen. Man schreibt N(x). Iterative Optimierung: Der folgende Algorithmus zum Finden eines Optimums einer diskreten Funktion f: 1. Initialisiere x als zufaelligen Eingabewert fuer f 2. xbest = x 3. While f(xbest) ist noch nicht gut genug 4. x = ein Element aus N(x) 5. If f(x) besser als f(xbest) Then xbest=x 6. EndWhile Fuer Schritt 4 gibt es verschiedene Strategien. ^ + * = zu maximierende Funktion | * * # = lokales Optimum | # *** * + = globales Optimum | * *** * |__*______|________*_________ <- x -> suchendes x Exploration: Das Verhalten einer Iterativen Optimierung, viele Eingabewerte zu pruefen. Exploitation: Das Verhalten einer Iterativen Optimierung, gute Eingabewerte zu bevorzugen. Es sollten sich Exploitation (zur Verbesserung des Eingabewertes) und Exploration (zum Finden bisher unbesuchter Eingabewerte) die Waage halten. Hillclimbing: Die folgende Strategie fuer die iterative Optimierung einer Funktion f: Waehle xneu, sodass f(xneu)=opt({f(x') | x' aus N(x)/\{x}}) Hillclimbing nimmt also immer den besten Nachbarn. Problem: Es faengt sich in lokalen Optima. Iterative improvement: Die folgende Strategie fuer die iterative Optimierung einer Funktion f von x aus: Waehle xneu aus N(x), sodass f(xneu) besser als f(x) Iterative improvement nimmt also immer irgendeinen besseren Nachbarn. Problem: Es faengt sich in lokalen Optima. Random search: Die folgende Strategie fuer die iterative Optimierung einer Funktion f von x aus: Waehle xneu irgendwie aus N(x) Random Search nimmt also immer einfach irgendeinen Nachbarn. Da Random Search bei eine lange genug andauernden Suche und endlichem Definitionsbereich alle Eingabewerte abklappert, findet es garantiert das Optimum (dauert dann halt nur etwas :-). Oft wird Random Search mit anderen Strategien kombiniert. Sintflut-Algorithmus: Die folgende Strategie fuer die iterative Optimierung einer Funktion f von x aus: Waehle xneu aus N(x), so dass f(xneu) besser als t t ist dabei eine reelle Zahl die von 0 startet und erhoeht wird (fuer suche nach Maxima) oder andersrum (fuer Suche nach Minima). Das x wandert also zufaellig herum und je weiter die Zeit fortschreitet, desto eher konzentriert sich die Strategie auf bessere Werte. Wenn t nur langsam genug veraendert wird, findet der Sintflut-Algorithmus das Optimum, da er dann Random Search ist. ^ * * = zu maximierende Funktion | * * * | * ****** * |~~~~*~~~~~~~|~~~~*~~~~~~~~~~ ~ = Wasserspiegel |__*_________|_____*_________ <- x -> suchendes x proportionale Wahl aus einer Menge M: Die Wahl eines Elementes aus M unter dem folgenden Kriterium: Jedes Element x[i] aus M ist mit einem reellen Wert p(x[i]) versehen. Nun stellt man sich vor, eine solche Wahl wuerde unendlich oft wiederholt. Sei n(x[i]) die Anzahl der Wahlen, in denen x[i] gewaehlt wurde. Dann soll sich n(x[i]) zur Summe aller n(x[j]) so verhalten, wie sich p(x[i]) zur Summe aller p(x[j]) verhaelt: n(x[i]) / SUM j=1..|M| n(x[j]) = p(x[i]) / SUM j=1..|M| p(x[j]) Metropolis-Algorithmus: Die folgende Strategie fuer die iterative Optimierung einer Funktion f von x aus: Waehle xneu aus N(x) proportional zu (f(xneu) besser als f(x)) ? 1 : g(f(x)-f(xneu)) Dabei ist g:R->[0;1] eine monoton fallende Funktion. Dadurch werden also schlechtere Eingabewerte mit geringer Wahrscheinlichkeit eingemischt. Simulated Annealing: Der Metropolis-Algorithmus mit g(x) = e^(x/T) (Bei Suche nach Minimum) g(x) = e^(-x/T) (Bei Suche nach Maximum) T heisst dabei "Temperatur" und wird waehrend der Iterativen Optimierung kontinuierlich verringert. Dadurch sinkt im Verlaufe des Algorithmus die Wahrscheinlichkeit, dass ein schlechterer Eingabwert gewaehlt wird. Tabu-Suche: Die folgende Strategie fuer die iterative Optimierung einer Funktion f von x aus: Waehle xneu aus N(x), sodass f(xneu)=min({f(x') | x' aus N(x), x' nicht in L}) Dabei ist L eine sogenannte Tabu-Liste, in die alle gewaehlten x aufgenommen werden. Meist loescht man die hintere Elemente der Tabu-Liste nach Ablauf einer bestimmten Schrittzahl. Tabu-Suche nimmt also immer den besten Nachbarn, der auch schlechter als x sein kann. Dabei wird durch die Tabu-Liste vermieden, dass man in einer Schleife gefangen wird. Problem: Dieser Algorithmus kann in einer Sackgasse ohne gueltige Nachfolger gefangen werden. Dann braucht man eine "Escape-Strategie", die einen anderen Schritt erlaubt. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Ameisen-Algorithmen ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Ant Colony Organization, ACO, Ameisenalgorithmus: Ein Algorithmus zur Bestimmung eines kurzen Weges in einem Graphen, der das Verhalten von Ameisen imitiert. Wenn Ameisen von ihrem Ameisenhuegel aus auf Futtersuche gehen, so streunen sie zunaechst einfach nur umher. Dabei hinterlassen sie Spuren des Duftstoffes "Pheromon". Die Ameisen haben die Tendenz, Wege zu bevorzugen, auf denen bereits viel Pheromon vorhanden ist. Erreicht nun eine Ameise eine Futterquelle, so kehrt sie zum Ameisenhuegel zurueck. Hat eine Ameise einen kurzen Weg zum Futter entdeckt, so wird sie ihn oefter ablaufen koennen, als eine Ameise, die einen langen Weg zum Futter entdeckt hat. Also hinterlaesst sie auf dem kurzen Weg mehr Pheromon als die andere Ameise auf dem langen Weg. Damit erhoeht sie die Wahrscheinlichkeit, dass die anderen Ameisen diesen Weg waehlen, noch mehr Pheromon wird verteilt und schliesslich nehmen alle Ameisen den kuerzesten Weg. Oft halten sich Ameisenalgorithmen nicht genau an dieses Schema, sie sind jedoch ein robustes Mittel zur Loesung mancher Graphenprobleme. Ziel | kurzer Weg, / \___________ langer Weg, oft in kurzer / \ Ameisen brauchen laenger, Zeit rennbar \ ___________/ rennen ihn weniger haeufig in => viel Phero \ / derselben Zeit => weniger Pheromon | Start Daemon-Aktion: Ein Algorithmus, der in einem ACO jedesmal ausgefuehrt wird, nachdem alle Ameisen einen Schritt gemacht haben. Diese Algorithmen dienen beispielsweise der Vor-Auswahl bestimmter Wege oder dem Tracken von Schritten. ACO fuer kuerzeste Wege: Der folgende Ameisenalgorithmus, der in einem Graphen G=(K,R) den kuerzesten Weg von einem Ausgangsknoten start zu einem Zielknoten ziel findet: // Pheromon auf den Verbindungen 1. Waehle einen reellen Pheromonstartwert pherostart 2. Waehle einen reellen Pheromonupdatewert epsilon 3. Waehle ein Verduftungsverhaeltnis v aus [0;1] 4. phero = Matrix der Groesse |K| * |K| 5. For i=1..|K| 6. For j=1..|K| 7. phero[i][j] = pherostart 8. EndFor 9. EndFor // Ameisen mit Position und Zustand 10. Waehle eine Anzahl n von Ameisen 11. p = Array der Laenge n ueber K 12. z = Array der Laenge n ueber {satt, hungrig} 13. For i=1..n 14. p[i]=start 15. z[i]=hungrig 16. EndFor 17. While noch nicht alle denselben Weg rennen 18. For i=1..n 19. If p[i]=ziel Then z[i]=satt 20. If p[i]=start Then z[i]=hungrig 21. If z[i]=hungrig Then 22. Waehle j aus { j' | R(p[a],j') } proportional zu phero[p[a]][j] 23. phero[p[a]][j] = phero[p[a]][j] + epsilon 24. Else 25. Waehle j aus { j' | R(j',p[a]) } proportional zu phero[j][p[a]] 26. phero[j][p[a]] = phero[j][p[a]] + epsilon 27. EndIf 28. EndFor 29. For i=1..|K| 30. For j=1..|K| 31. phero[i][j] = phero[i][j]*v 32. EndFor 33. EndFor 34. EndWhile Der Weg, den alle rennen, ist der kuerzeste (gilt leider nur bei Ameisen). Dieser Algorithmus setzt vorraus, dass es von jedem Knoten einen Weg zum Ziel und einen Weg zum Start gibt. Ausserdem darf der Graph nicht zyklisch sein. Es gibt bereits effiziente Algorithmen fuer kuerzeste Wege in einem Graphen (Dijkstra-Algorithmus, siehe gc.txt "Graphes et complexite", auf franzoesisch), aber der Ameisen- Algorithmus passt sich auch Graphveraenderungen an. Barbara-ACO: Der folgende Ameisenalgorithmus, der in einem Graphen G=(K,R), der auch zyklisch sein darf, den kuerzesten Weg von einem Ausgangsknoten start zu einem Zielknoten ziel findet: 1. - 9. wie ACO fuer kuerzeste Wege 10. Waehle eine Anzahl n von Ameisen 11. p = Array der Laenge n ueber K 12. w = Array der Laenge n ueber Listen von K 13. For i=1..n 14. p[i]=start 15. w[i]=(start) 16. EndFor 17. While noch nicht alle denselben Weg rennen 18. For i=1..n 19. If p[i]=ziel Then 20. For j=1..dim(w[i])-1 21. phero[j][j+1] = phero[j][j+1] + epsilon / dim(w[i]) 22. EndFor 23. p[i]=start 24. w[i]=(start) 25. Else 26. Waehle p[i] aus { j' | R(p[a],j') } proportional zu phero[p[a]][j] 27. w[i] = w[i] mit p[i] 28. EndIf 29. EndFor 30. For i=1..|K| 31. For j=1..|K| 32. phero[i][j] = phero[i][j]*v 33. EndFor 34. EndFor 35. EndWhile Der Weg, den alle rennen, ist der kuerzeste. Hier haben die Ameisen also ein Mini-Gehirn w, in dem sie sich den gelaufenen Pfad merken. Das Pheromon wird erst versprueht, wenn das Ziel gefunden ist und die Ameisen werden dann sofort auf start zurueck gebeamt. Travelling-Salesman-Problem, Travelling-Saleswoman-Problem, Travelling- Salesperson-Problem, TSP: Die Aufgabe, in einem voll verbundenen Graphen mit Distanz den kuerzesten Zyklus zu finden, der alle Knoten enthaelt. Die Analogie ist eine Handelsreisende/ein Handlungsreisender, der eine Anzahl von Staedten mit moeglichst wenig Wegkosten besuchen will und am Ende wieder in die Ausgangsstadt zurueck will. ACO fuer das TSP: Ein Ameisenalgorithmus, der ein TSP loest, indem er einen Graphen definiert, in dem die Knoten Tupel von Staedten sind. Jedes dieser Tupel definiert eine (partielle) Rundreise. Die Knoten sind verbunden, wenn man eine Reise zu einer anderen Reise durch Anfuegen einer Stadt erweitern kann. Die Ameisen suchen nun in diesem Graphen, bis sie eine totale Rundreise gefunden haben. Die Wahl des naechsten Knotens wird dabei nicht nur vom Pheromon abhaengig gemacht, sondern auch von der Distanz der letzten Stadt im alten Tupel zur letzten Stadt im neuen Tupel: p[i] = (stadt[1],...stadt[k]) Waehle den Knoten (stadt[1],...stadt[k],stadt[k+1]) proportional zu phero[i][j]^alpha/dist(stadt[k],stadt[k+1])^beta alpha und beta sind Parameter des Verfahrens, beta wird im Laufe der Zeit verringert. Am Anfang ist beta gross und die Wahrscheinlichkeit, dass die Ameisen einen langen Weg waehlen ist gering. Spaeter ist beta klein und die Ameisen achten mehr darauf, Pheromon-bestueckte Wege zu waehlen. (NY) --------- (NY, Washington) ------- (NY, Washington, Osna) | ----------- (NY, Philadelphia) ----- (NY, Phildelphia,Miami) Quadratic Assignment-Problem, QAP: Die Aufgabe, n Industrien auf n Orte so zu verteilen, dass Gueter minimale Wege zurueck legen muessen. Dazu hat man eine n x n Matrix d, die den Abstand zwischen zwei Staedten angibt. Eine n x n Matrix f gibt die Groesse des Gueterflusses zwischen zwei Industrien an. Ziel ist eine Zuordnung der Industrien i zu den Orten ort(i), sodass die Summe der Produkte aus Gueterfluss und zugehoerigen Abstaenden minimal ist: SUM d[ort(i)][ort(i')]*f[i][i'] minimal Das TSP ist ein Spezialfall des QAP, wenn gilt f[i][j] = (j == i+1)?1:0 ACO fuer QAP: Ein Ameisenalgorithmus, der ein QAP loest, indem es einen Graphen definiert, in dem die Knoten Tupel von Industrien und Orten sind. Diese Tupel haben die Form (ort[1],industrie[1],ort[2],industrie[2],...ort[k],industrie[k]) Einem solchen Tupel kann man die Zuordnung von Industrien zu Orten entnehmen. Ist n die Anzahl der Orte, so ist ein Tupel der Laenge 2*n eine Loesung. Zwei Tupel sind in dem Graphen verbunden, wenn man durch Hinzufuegen einer Industrie oder eines Ortes von dem einen zum anderen kommen kann. Die Ameisen waehlen eine Verbindung proportional zum Pheromon und anti-proportional zum entstehenden Gueterfluss. Network Routing problem: Die Aufgabe, in einem Graphen mit Distanz die kuerzesten Wege von jedem Knoten zu jedem anderen Knoten zu finden. Dieses Problem stellt sich im Versenden von Datenpaketen im Internet. ACO fuer das Network Routing Problem: Ein Ameisenalgorithmus, der das Network Routing Problem loest, indem er Pheromonvektoren benutzt. Jeder Verbindung von Knoten zu Knoten wird also nicht ein einziger Pheromonwert zugewiesen, sondern ein Tupel von Pheromonwerten, deren i-ter Eintrag von Ameisen benutzt wird, die zum i-ten Knoten im Graphen unterwegs sind. Fuer jede Start-Ziel-Kombination werden speziell trainierte Ameisen eingesetzt. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Genetische Algorithmen ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Individuum [im Sinne Genetischer Algorithmen]: Ein Tupel. Bitstring-Individuum: Ein Individuum aus Einsen und Nullen. Crossover: Die Generierung eines neuen Individuum aus mehreren Individuen. Die beteiligten Individuen heissen "Eltern" des neuen Individuums. Standard-Crossover: Die Generierung der zwei folgenden Individuen aus zwei Individuen x und y: (x[1],x[2],...x[k],y[k+1],...y[n]) (y[1],y[2],...y[k],x[k+1],...x[n]) Dabei ist k eine zufaellige Stelle. Mutation: Die Veraenderung einer oder mehrerer Komponenten eines Individuums. Switchen: Die Umwandlung einer 1 in eine 0 oder andersrum. Standard-Mutation:Das Switchen einer zufaellig ausgewaehlten Komponente eines Bitstring-Individuum. Population: Eine Menge von Individuen. Fitness: Eine Funktion, die ein Individuum auf eine positive reelle Zahl abbildet. Selektion von N Individuen aus einer Population P: Die Auswahl von N Individuen proportional zu ihrer Fitness aus P. Dabei kann auch mehrmals dasselbe Individuum selektiert werden. Ausfuehren einer Handlung mit Wahrscheinlichkeit P: Das Ausfuehren oder Nichtausfuehren der Handlung, sodass, wenn dieses unendlich oft wiederholt wird, sich die Anzahl der Ausfuehrungen zur Anzahl der Nichtausfuehrungen verhaelt wie P/(1-P). Genetischer Algorithmus: Der folgende Algorithmus zum Findes eines Individuums mit maximaler Fitness f: 1. Erstelle eine zufaellige Population P aus n Individuen O O o o P = { | | | | } / \ /_\ / /_\ 2. Waehle eine Zahl N o o / \ /_\ | | 8. Mutiere die entstandenen N Individuen mit Wahrscheinlichkeit Pm o o O . | | ~~~~~~~> | | 9. EndWhile Unter bestimmten Bedingungen naehert sich dadurch die Fitness des fittesten Individuums von P der maximalen Fitness an. Schema: Ein Tupel, dessen Elemente Nullen, Einsen oder Sterne sind. Ein solches Schema ist ein Muster fuer Bitstring-Individuen, wobei der Stern fuer eine irrelevante Position steht. Laenge eines Schemas S: Die Breite des Bereichs der Einsen und Nullen in S d(S) = max({i | S[i]!='*'}) - min({i | S[i]!='*'}) Beispiel: d([*,*,1,*,0,1,*,*,*,*])= 6-3 = 3 |-----| Ordnung eines Schemas S: Die Anzahl der Einsen und Nullen in S. o(S) = | {i | S[i]!='*'} | Matchendes Individuum fuer ein Schema S: Ein Bitstring-Individuum, welches dort Einsen hat, wo das Schema Einsen hat und dort Nullen hat, wo das Schema Nullen hat. Wo das Schema Sterne hat, ist es egal, welchen Eintrag das Individuum an dieser Komponente hat. Kurz fuer Prologfreaks: matcht([],[]). matcht([_|IR], [*|SR]) :- matcht(IR,SR). matcht([X|IR], [X|SR]) :- matcht(IR,SR). Kurz fuer funktionale Freaks: matcht(I,S,index=1) := (index=dim(I)+1) \/ (S[index]='*') ? matcht(I,S,index+1) : (S[index]=I[index]) /\ matcht(I,S,index+1) Menge eines Schemas S: Die Menge aller auf S matchenden Individuen. Erwartungswert einer Variable: Der Mittelwert ihrer Werte, die sie fuer alle moeglichen Umgebungszustaende annimmt. Es handelt sich also um so etwas wie den "wahrscheinlichen Mittelwert". Schematheorem: Die Aussage, dass in einem GA mit Bitstring-Individuen gilt E(m(H,t+1)) >= û(H,t)/fm(t) * m(H,t) * (1 - Pc*d(H)/(n-1)) * (1-Pm)^o(H) wobei gilt * H ist ein Schema * t ist die Nummer des Schleifendurchlaufs des GA * m(H,t) ist die Anzahl der auf H matchenden Individuen in t * û(H,t) ist der Mittelwert der Fitnesswerte aller auf H matchenden Individuen in t * fm(t) ist der Mittelwert der Fitnesswerte aller Individuen in t Sind alle Schema-unabhaengigen Werte als konstant vorrausgesetzt, so ist der Erwartungswert der Anzahl der auf H matchenden Individuen umso groesser, je kleiner o(H) ist und je kleiner d(H) ist. Das Schematheorem besagt also, dass kurze und Sternchen-lastige Schemata die meisten Individuen um sich sammeln werden. Der Beweis des Theorems baut darauf auf, dass die Wahrscheinlichkeit, dass ein matchendes Individuum auch im naechsten Schritt matcht, sinkt, wenn das Individuum mutiert wird oder an einem Crossover teilnimmt. Jeder der obigen Faktoren traegt dabei einer Operation des GA (Selektion, Mutation, Crossover) Rechnung. Die Schwaeche dieses Theorems ist, dass nur die negativen Effekte von Mutation und Crossover beruecksichtigt werden. Buildingblock-Hypothese: Die Annahme, dass sich Fitness-Funktionen ueber Bitstring-Individuen, deren Maxima durch kurze Stuecke in den Individuen gekennzeichnet sind, am besten von einem GA optimiert werden koennen. Wenn die Funktion also nur von einigen Komponenten des Individuums abhaengt und diese Komponenten dicht nebeneinander liegen, dann findet der GA die optimalen Individuen. Folgerungen aus dem Schema-Theorem: * Building-Block-Hypothese * Ein GA ist implizit parallel, da ein Individuum der Laenge n gleichzeitig 2^n Schemata angehoert * Individuen mit Komponenten aus {0,1} sind Individuen mit Komponenten aus {0,1,...k} ueberlegen, denn ein solches Individuum gehoert auch gleichzeitig 2^n Schemata an, benoetigt aber mehr Speicherplatz * Es gibt eine Menge Pseudo-Mathematik zu GAs Gefangenen-Dilemma, Prisoners' Dilemma: Die Frage, ob ein Gefangener A gegen seinen ebenfalls gefangenen Komplizen B aussagen soll, wenn das Strafmass in Jahren wie folgt bemessen ist: A schweigt sagt aus B schweigt A:2,B:2 A:0,B:5 sagt aus A:5,B:0 A:4,B:4 Das Dilemma, nicht zu wissen, ob jemand anders sich kooperativ verhalten wird oder nicht, tritt in vielerlei Situationen auf, weshalb das Gefangenendilemma gern fuer Gesellschaftsmodelle verwendet wird. Iterated Prisoners' Dilemma, Wiederholtes Gefangenen-Dilemma: Die Frage, ob ein Gefangener des Gefangenen-Dilemmas nach k Gefangenen-Dilemmas mit demselben Komplizen gegen diesen aussagen soll oder nicht. Dabei koennen sich die Gefangenen nicht absprechen, wissen aber, wie der andere im letzten Mal entschieden hat. Das Problem, dass die beiden aufgrund der geringen Lebenserwartung in Gefangenschaft im schlechtesten Fall nur ca. 10-mal an dem Dilemma teilhaben koennen, wird ignoriert. Verlauf eines Iterated Prisoners' Dilemmas, History eines Iterated Prisoners' Dilemmas: Eine Folge 2-Tupeln, deren Elemente aus {schweigt,sagt_aus} stammen. Das k-te Tupel eines Verlaufs sagt aus, wie sich beim k-ten Dilemma der erste Gefangene verhalten hat (1. Komponente des Tupels) und wie der zweite (2. Komponente des Tupels). Strategie eines Iterated Prisoners' Dilemmas fuer einen der beiden Gefangenen: Eine Funktion, die zu einem Verlauf eine Entscheidung aus {schweigt,sagt_aus} liefert. Eine Strategie gibt also eine Entscheidung fuer einen der beiden Gefangenen an, die davon abhaengt, wie dieser selbst und sein Komplize sich in den letzten Runden verhalten haben. TIT4TAT: Eine Strategie, die so entscheidet, wie der Komplize beim letzten Mal. Diese entspricht dem klassischen "Wie Du mir, so ich dir"-Verhalten. Uniform-Crossover: Ein Crossover, welches ein neues Individuum erzeugt, in dem jede Komponente zufaellig von einem Elternteil gewaehlt wird. Beispiel: X1 X2 X3 X4 Y1 Y2 Y3 Y4 \ / X1 X2 Y3 X4 GA fuer das Iterated Prisoners' Dilemma: Ein GA, der durch folgendes gekennzeichnet ist: Individuen: Jedes Individuum verkoerpert eine Strategie Man entscheidet sich fuer eine Rueckblicklaenge k (die angibt, wie nachtragend der Gefangene ist). Fuer ein Iterated Prisoners' Dilemma von k Runden gibt es 4^k verschiedene Verlaeufe. Jedes Individuum bekommt 4^k Komponenten, von denen jede fuer einen moeglichen Verlauf steht. Die i-te Stelle enthaelt eine 1 fuer "Aussagen" und eine 0 fuer "Schweigen". Fitness: Je mehr Haftjahre, desto weniger Fitness. Man waehlt zB. eine Funktion, die ein Individuum auf die Differenz aus einer grossen Konstanten und die Summe seiner Haftjahre abbildet. Mutation: Standard-Mutation Crossover: * Standard-Crossover oder * Uniform Crossover Nun laesst man einen GA laufen, in dem am Ende nur diejenigen Individuen ueberleben, deren Strategien zu moeglichst geringen Haftstrafen gefuehrt haben. Das durch den GA entstehende Phaenomen dient als Modell einer Gesellschaft, in der zunaechst Anarchie gilt (jeder sagt aus, um das eigene Strafmass zu reduzieren), und in der sich dann Normen herausbilden (es zeigt sich, dass schweigende Individuen besser ueberleben), die aber bei der naechsten Gelegenheit wieder verschwinden (sobald einer aussagt, bricht das Schweigeuebereinkommen). Repair-Strategie: Ein Verfahren, welches aus einem ungueltigen Individuum (welches beispielsweise durch Crossover entstanden ist), ein gueltiges macht. GA fuer das TSP: Ein GA, der durch folgendes gekennzeichnet ist: Individuen: Die Individuen stellen Rundfahrten dar. Jede Komponente ist dabei ein Stadtname oder eine Stadt-Nummer und jede Stadt kommt nur einmal in jedem Individuum vor. Fitness: Je laenger die Rundfahrt, desto geringer die Fitness. Man waehlt zB eine Funktion, die ein Individuum auf die Differenz aus einer grossen Konstanten und der Laenge der Tour abbildet. Crossover: * kein Crossover oder * Austauschen von Teilstuecken bei den Eltern mit den gleichen Staedten oder * Standard-Crossover Beim Crossover muss aufgepasst werden, dass keine Stadt doppelt vorkommt (Repair-Strategie oder Individuum loeschen). Mutation: * Zufaelliger Tausch zweier Staedte oder * Umkehrung eines Teils der Rundfahrt oder * Mutation unter Zuhilfenahme von Iterativer Optimierung Vehicle-Routing-Problem: Die Aufgabe, eine Anzahl von Objekten auf eine Anzahl von Fahrzeugen zu verteilen und jedem Fahrzeug eine Streckenbeschreibung zuzuordnen, sodass jedes Objekt unter Einhaltung einer spezifischen Zeit eine spezifische Zielstadt erreicht. GA fuer das Vehicle-Routing-Problem: Ein GA, dem folgende Ueberlegung zu Grunde liegt: Sollen die Fahrzeuge die Objekte in optimaler Zeit abliefern, so ist es wahrscheinlich, dass sich ihre abgefahrenen Strecken zu einer TSP-Tour minmaler Laenge zusammensetzen. Deshalb waehlt man wie folgt: Individuen: Wie beim TSP Rundfahrten Aus einer solchen Rundfahrt ergibt sich eine Verteilung auf die Fahrzeuge wie folgt: Man nimmt den ersten Teil der TSP-Tour als Strecke fuer das erste Fahrzeug. Diesen Teil macht man so lang, wie das Fahrzeug die Ablieferungszeiten gerade noch einhaelt. Fuer den naechsten Teil der Strecke nimmt man das naechste Fahrzeug (?) usw. Ist kein Fahrzeug mehr vorhanden, so waehlt man das Fahrzeug, was der noch zu bedienenden Stadt am naechsten liegt. Fitness: Je groesser die Zeitlimitiueberschreitungen, desto kleiner die Fitness. Man waehlt zB. die Differenz aus einer grossen Konstante und die Summe der durch den Plan entstehenden Zeitlimitueberschreitungen. VLSI-Design-Problem: Die Aufgabe, Rechtecke so aneinanderzulegen, dass die Gesamtflaeche minimal ist. Dieses Problem tritt zB beim Design einer Platine auf, auf dem Chips so platziert werden sollen, dass die Platine moeglichst klein ist. GA fuer das VLSI-Design-Problem: Ein GA, der wie folgt gekennzeichnet ist: Individuen: binaere Baeume, die eine Platzierung der Rechtecke symbolisieren. Die Blaetter des Baumes sind die anzuordnenden Rechtecke und die Struktur des Baumes gibt an, wie sie nebeneinanderzulegen sind. Fitness: Je groesser die Gesamtflaeche, desto geringer die Fitness. Man waehlt zB. die Differenz aus einer grossen Konstante und der Gesamtflaeche. Mutation: Vertauschungen oder Drehungen von Unterbaeumen Crossover: Unterbaeume der Elternbaeume kombinieren oder austauschen. Dabei muss darauf geachtet werden muss, dass nicht dasselbe Rechteck zweimal auftaucht (Repair-Strategien oder Loeschen des Individuums) Multimodale Funktion: Eine Funktion mit mehreren optimalen Werten. GA fuer numerische Optimierung: Ein GA, der ein Optimum einer mehrstelligen reellen Funktion finden soll. Er ist wie folgt gekennzeichnet: Individuen: Eingabe-Vektoren Fitness: Der Funktionswert des Individuums (entsprechend angepasst und verschoben, sodass alle Werte positiv sind und gute Werte gross sind). Crossover: zB. Linearkobinationen der Eltern Mutation: zB Addition von kleinen Werten zu einzelnen Komponenten GAs dieser Art werden oft fuer multimodale Funktionen benutzt. GP, Genetic Programming, Genetisches Programmieren: Die Verwendung eines GAs zum Erzeugen eines Algorithmus. Dabei werden Algorithmen als Baeume dargestellt, deren Unterbaeume Anweisungen sind. Der GA ist wie folgt gekennzeichnet: Individuen: Algorithmen in Baumform Fitness: Nuetzlichkeit eines Algorithmus Probleme sind die Definition der Fitnessfunktion (die im Prinzip die Algorithmen fuer alle denkbaren Faelle durchtesten muss) und die Unstetigkeit von Programmen (kleine syntaktische Unterschiede rufen grosse semantische Unterschiede hervor, wie jeder weiss, der schonmal Java mit dem VI programmieren musste). Aufgaben-Problem: Die Fragestellung, wie man N Aufgaben, von denen jede die Belastung b[i] mit sich bringt, auf k Leute verteilt, so dass jeder moeglichst die gleiche Belastung hat. GA fuer das Aufgaben-Problem: Ein GA, der wie folgt gekennzeichnet ist: Individuen: Vektoren, deren i-te Komponente die Nummer der Person ist, die die Aufgabe Nr. i macht. Fitness: Je naeher die Belastung der Individuen an der mittleren Belastung liegt, desto groesser die Fitness. Es sei #Aufgaben die Anzahl der Aufgaben und #Personen die Anzahl der Personen. Dann ist mittlereBelastung = SUM a=1..#Aufgaben b[a] / #Aufgaben Belastung[person](indiv) = SUM a=1..#Aufgaben (indiv[a]==person)?b[a]:0 Fitness(indiv) = SUM p=1..#Personen (Belastung[p](indiv) - mittBel)^2 // Diese Formel ist selbst gestrickt, die aus der Vorlesung habe ich // nicht verstanden Probleme Genetischer Algorithmen: * Genetic drift: Da die Population im Allgemeinen klein ist, koennen sich irrelevante oder unerwuenschte Individuen durchsetzen. Aussagen wie das Schema-Theorem gelten naemlich erst bei hinreichend grosser (unendlicher) Population. * Premature convergence: Es setzen sich Individuen durch, die zwar nicht schlecht sind, aber nur ein lokales Optimum ausmachen. * Diversification: Auch wenn das Ziel schon nah ist, mutieren die Individuen noch ziellos um das Optimum herum * Hitchhiking: Komponenten, die eigentlich irrelavent sind, setzen sich durch, weil sie zufaellig immer in guten Individuen auftreten. * Epistasis: Der Einfluss einer guten Komponente auf die Fitness des Individuums wird von einer anderen Komponente verhindert. Dadurch geht die ansich richtige Komponente verloren. * Deception: Ein Optimum kann nur ueber Mutation durch eine schlechte Stelle hindurch erreicht werden. Solche Mutationen sterben aber sofort aus.