%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% LATEX-Format-File from Marcus Hutter 13.05.91 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Document-Style % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentstyle[12pt,german]{article} \parskip=1.5ex plus 1ex minus 1ex \parindent=0ex \pagestyle{headings} \topmargin=0cm \oddsidemargin=0cm \evensidemargin=0cm \textwidth=16cm \textheight=24.5cm \setcounter{topnumber}{1} \renewcommand{\bottomfraction}{0.7} \sloppy %\makeindex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Macro-Definitions % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newif\ifall\alltrue %\allfalse % nur Teile compilieren %\nofiles % no .aux .toc ... files %\catcode`\"=12 \catcode`\Ž=13\defŽ{\"A} \catcode`\„=13\def„{\"a} \catcode`\™=13\def™{\"O} \catcode`\”=13\def”{\"o} \catcode`\š=13\defš{\"U} \catcode`\=13\def{\"u} \catcode`\á=13\defá{{\ss}} \catcode`\÷=13\def÷{{\approx}} %\catcode`\ì=13\defì{{\infty}} %\catcode`\ñ=13\defñ{{\pm}} %\def\ZG{Zufallsgr\"o\ss e} %\def\ZZ{Zufallszahl} %\def\GV{gleichverteilt} %\def\WK{Wahrscheinlichkeit} %\def\prop{proportional} \def\ff{\Longrightarrow} \def\gdw{\Longleftrightarrow} \def\toinfty#1{\stackrel{#1\to\infty}{\longrightarrow}} \def\nq{\hspace{-1em}} \def\look{\(\uparrow\)} \def\cpref#1{\ref{#1} auf Seite \pageref{#1}} \def\ignore#1{} \def\boxfig#1#2{ \begin{figure} \fboxsep=8mm \framebox[\textwidth]{\centerline{#1}} \vspace{-2ex} \caption{#2} \end{figure} } \newenvironment{listing}{\baselineskip=2.4ex\lineskiplimit=-9ex}{} \def\CFS{CFS} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Example-Structures (to Copy)% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Box in Textwidth with centered Text % \fbox{\vbox{\hfil #\hfil}} % \framebox[\textwidth]{\centerline{#} % Table-Format % \begin{table} % \begin{center}\begin{tabular}{|l|l|l|} \hline % \bf Col1 & \bf Col2 & \bf Col3 \\\hline\hline % Entry1 & Entry 2 & Entry3 \\\hline % ... % \end{tabular}\end{center} % \vspace{-3ex}\caption{Unterschrift}\end{table} \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Title-Page % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifall\begin{titlepage}\begin{center} \vspace*{2cm} {\LARGE Diplomarbeit} \\[2cm] {\Huge Thema: Implementierung eines \\ Klassifizierungssystems} \\ {\large (Programmbeschreibung)} \\[2cm] {\LARGE Bearbeiter: Marcus Hutter} \\[1cm] {\LARGE Betreuer: Gerhard Weiá} \\[2cm] {\large Abgabedatum: 15.~Mai 1991} \end{center}\end{titlepage}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Contents/Figures/Tables % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifall \tableofcontents \clearpage \listoffigures \listoftables \clearpage \fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Einleitung } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Ein Klassifizierungssystem (CFS, engl. {\sl Classifiersystem}) ist ein massiv paralleles regelbasiertes System, dessen Komponenten {\sl (Classifier)} Nachrichten {\sl (Messages)} austauschen k”nnen, dessen Verhalten von einem Lehrer beurteilt wird {\sl (Reinforcement)} und das mittels {\sl Credit-Assignment} und genetischen Algorithmen f„hig ist zu lernen. Fr eine einfhrende Darstellung muá auf die inzwischen sehr umfangreiche Literatur, insbesondere \cite{Goldberg}, verwiesen werden. Das Konzept des CFS wurde zuerst von Holland \cite{Holland} entwickelt, inzwischen gibt es aber eine Vielzahl von Varianten und Erweiterungen (\look\cite{Booker,Proc}). Bisher ist es nicht m”glich, diese Varianten in ihrer Performance zu vergleichen, eine Aussage ber die Gte der verschiedenen Ans„tze ist somit kaum oder berhaupt nicht m”glich. Das in dieser Diplomarbeit erstellte Programm gestattet erstmals bzgl.\ der wichtigsten Varianten einen {\it direkten} Vergleich. In den folgenden Kapiteln wird dieses Programm, bei dem besonders auf eine effiziente Implementierung geachtet wurde, beschrieben. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Grundfunktionen } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In diesem Kapitel sollen die Funktionalit„t und die Implementierung einiger elementarer Routinen beschrieben werden. Obwohl diese eher allgemeiner Natur und nicht unbedingt spezifisch fr CFS sind, sollen sie aus folgenden Grnden trotzdem n„her erl„utert werden: \begin{itemize} \item Nur eine genaue Kenntnis der Funktionalit„t der Grundfunktionen kann eine klare Vorstellung des gesamten CFS vermitteln und gezielte Experimente erm”glichen. \item Fr jemand, der dieses CFS erweitern oder als Motivation fr ein eigenes verwenden will, stellen die Grundfunktionen eine solide Basis dar. \end{itemize} % \subsection{ Selektion (Funktionalit„t) }\label{SelFkt} % ========================== Ein zentraler Punkt in CFS ist die Selektion. Darunter ist folgendes zu verstehen: \\ Aus einer (Multi)Menge $M$ von $n$ bewerteten Elementen, d.h. $M=\{(Id_1,Val_1),\ldots,(Id_n,Val_n)\}$ wird eine Teil(multi)menge $N=\{Id_{i_1},\ldots,Id_{i_k}\}$ von $k$ Elementen (die Bewertung wird weggelassen) in Abh„ngigkeit der Bewertungen $Val_i$ ausgew„hlt, wobei Einzelheiten vom Selektions-Modus abh„ngen. Generell kann man sagen, daá Elemente mit h”heren Bewertungen bevorzugt werden. Die verschiedenen Selektions-Modi existieren in je zwei Varianten: \begin{enumerate} \item Elemente k”nnen mehrfach selektiert werden, d.h. mehrfach in der Ziel\-(multi)\-menge auftreten. \item Elemente werden h”chstens einmal selektiert. Da die Elemente sequentiell selektiert werden (eines nach dem anderen), wird nach Auswahl eines Elements dieses einfach aus M gel”scht. \end{enumerate} Kommen wir nun zu den einzelnen Selektionsarten: \subsubsection{ Dummy-Selection ({\tt SelMode=1}) } % --------------------------------- Es werden beliebige (gleiche oder verschiedene) Elemente selektiert. \\ Diese Variante dient eigentlich internen Zwecken (wenn z.B. $k=N$), kann aber auch fr eigene Zwecke verwendet werden, wenn absolut egal ist, welche $k$ Elemente selektiert werden sollen, z.B. Reduktion einer Menge bei keinerlei (nicht einmal statistischer) Zusatzinformation. \subsubsection{ Probability-Selection ({\tt SelMode=2 oder 6}) } % ---------------------------------------------- Dies ist eine statistische Selektion der im wesentlichen die Bewertung der Elemente als Wahrscheinlichkeitsverteilung zugrunde liegt, d.h. $Id_i$ wird mit Wahrscheinlichkeit $Val_i / \sum_{j=1}^n{Val_j}$ selektiert. Dieses Verfahren wird $k$-mal (mit oder ohne L”schen der bereits selektierten Elemente aus $M$) wiederholt. {\tt SelMode=2} und {\tt SelMode=6} unterscheiden sich nur hinsichtlich ihrer Implementierung (\look\ref{SelImpl}). \subsubsection{ Best-Selection ({\tt SelMode=3}) } % -------------------------------- Es werden die $k$ (verschiedenen!) Elemente mit der gr”áten Bewertung selektiert. \\ $k$-mal das gleiche beste Element zu w„hlen macht nicht besonders viel Sinn und ergibt deshalb eine Warnung. \subsubsection{ Scaled-Selection ({\tt SelMode=4}) }\label{SclSelFkt} % ---------------------------------- Die skalierte Selektion kann auf zwei verschiedene Weisen interpretiert werden, deren Žuivalenz in \cpref{SclSelImpl} bewiesen wird. \begin{enumerate} \item Betrachte zwei Elemente und selektiere das h”her bewertete mit Wahrscheinlichkeit $p$ $(>0.5)$. \item Sortiere die Elemente nach ihrer Bewertung, nummeriere sie linear, d.h. mit $(s,s+k,s+2k,\ldots,s+nk)$ durch (Linearisierung) und selektiere mit Wahrscheinlichkeit proportional zu dieser Nummer (wie in {\tt SelMode=2}). \end{enumerate} \subsubsection{ Random-Selection ({\tt SelMode=5}) } % ---------------------------------- Selektiere gleichverteilt, d.h. unabh„ngig von der Bewertung wird ein Element mit Wahrscheinlichkeit $1/n$ selektiert. \\ Diese Methode dient zum Vergleich zwischen rein zuf„lligen und bewertungsabh„ngigen Selektionsarten. \subsection{ Selektion (Implementierung) }\label{SelImpl} % =========================== Da Selektion eine zentrale Funktion ist, wurde der effizienten Implementierung h”chste Aufmerksamkeit gewidmet. Der Mindestanspruch lag, wie auch bei allen anderen Routinen, keinen Algorithmus mit quadratischer Ordnung, sondern h”chstens Ordnung $O(n\log n)$ oder wenn m”glich sogar $O(n)$ zu verwenden. % Die Funktion {\tt Select} wird mit folgenden Parametern aufgerufen: \begin{description} \item[{\verb|TIdVal A[]|:}] {\tt A} ist ein Array von Tupeln, deren erste Komponenten Identifier ({\tt index=int}) der Elemente darstellen (z.B. {\sl Message}-Nummer) und deren zweite die Bewertung ({\tt fixp=int}) enthalten. \item[\tt int *NP:] {\tt *NP} gibt die Anzahle der Elemente in {\tt A} an und wird bei Selektion ohne Vielfachheit um {\tt k} vermindert. \item[{\verb|index B[]|:}] {\tt B} nimmt die selektierten Identifier auf. \item[\tt int k:] {\tt abs(k)} ist gleich der Anzahl der zu selektierenden Elemente. M”chte man mehrmals (zu versch.\ Zeitpunkten) Elemente aus {\tt A} selektieren, so muá {\tt A} zuvor mittels {\tt MultSelInit(A,N,Mode)} initialisiert werden und im folgenden {\tt sign(k)=-1} gew„hlt werden. Bei einmaliger Selektion ({\tt sign(k)=1}) initialisiert {\tt Select} automatisch. \item[\tt sbyte Mode:] {\tt abs(Mode)} ist der Selektions-Mode ($-$6 bis 6),\\ {\tt sign(Mode)} gibt an, ob mit ($-1$) oder ohne ($+1$) Vielfachheit selektiert werden soll. \end{description} % \paragraph{Beispiel:}\hfill\\ Skalierte Selektion aus {\tt A} der L„nge 10 ohne Vielfachheit.\\ Zuerst 3 Elemente, sp„ter noch einmal 2 Elemente. % \begin{verbatim} N=10; MultSelInit(A,N,4); Select(A,&N,B,-3,4); /* nun ist N=7 */ Select(A,&N,B,-2,4); /* nun ist N=5 */ \end{verbatim} \subsubsection{ Probability-Selection ({\tt SelMode=2}) }\label{ProbSelImpl} % -------------------------------------- Das Prinzip ist einfach: \\ Man denke sich einen Streifen aus lauter Stcken zusammengesetzt, deren L„ngen gerade den Bewertungen entsprechen. Der Gesamtstreifen hat so die L„nge $S=\sum_{i=0}^{n-1}{Val_i}$. Tippt man nun blind (gleichverteilt zuf„llig) auf den Streifen, so erwischt man ein Stck mit Wahrscheinlichkeit proportional zu seiner L„nge. Bei naiver Implementierung ben”tigt man im Mittel $n/2$ Additionen zur Selektion eines Elements, bei geschickterer (Zwischenspeichern der Partialsummen $\sum_{i=0}^k{Val_i}\quad\forall\;0\!\le\! k\!<\!n$ und {\sl Divide \& Conquere}) $\log n$ Vergleiche, aber weiterhin $n/2$ um ein Element zu l”schen. Dieses auch auf $\log n$ zu drcken macht die Sache etwas verzwickter. Die {\sl Divide \& Conquere} Idee wird beibehalten, aber die Partialsummen durch eine Baumstruktur ersetzt. Die Initialisierung von {\tt A} soll das Beispiel in Abbildung \ref{AInit} verdeutlichen. Bei Arrayl„ngen, die keine Zweierpotenz sind, kann man sich dieses durch Nullen auf die n„chste Zweierpotenz verl„ngert denken. \boxfig{ \unitlength=0.80mm \begin{picture}(170,125) \put(10,115){\framebox(10,10)[cc]{1}} \put(20,115){\framebox(10,10)[cc]{4}} \put(15,105){\circle{10}} \put(15,105){\makebox(0,0)[cc]{5}} \put(15,115){\vector(0,-1){5}} \put(25,115){\line(0,-1){10}} \put(25,105){\vector(-1,0){5}} \put(20,110){\makebox(0,0)[cc]{+}} \put(30,115){\framebox(10,10)[cc]{3}} \put(40,115){\framebox(10,10)[cc]{2}} \put(35,105){\circle{10}} \put(35,105){\makebox(0,0)[cc]{5}} \put(35,115){\vector(0,-1){5}} \put(45,115){\line(0,-1){10}} \put(45,105){\vector(-1,0){5}} \put(40,110){\makebox(0,0)[cc]{+}} \put(15,90){\circle{10}} \put(15,90){\makebox(0,0)[cc]{10}} \put(15,100){\vector(0,-1){5}} \put(35,100){\line(0,-1){10}} \put(35,90){\vector(-1,0){15}} \put(20,95){\makebox(0,0)[cc]{+}} \put(50,115){\framebox(10,10)[cc]{7}} \put(60,115){\framebox(10,10)[cc]{5}} \put(55,105){\circle{10}} \put(55,105){\makebox(0,0)[cc]{12}} \put(55,115){\vector(0,-1){5}} \put(65,115){\line(0,-1){10}} \put(65,105){\vector(-1,0){5}} \put(60,110){\makebox(0,0)[cc]{+}} \put(70,115){\framebox(10,10)[cc]{6}} \put(80,115){\framebox(10,10)[cc]{8}} \put(75,105){\circle{10}} \put(75,105){\makebox(0,0)[cc]{14}} \put(75,115){\vector(0,-1){5}} \put(85,115){\line(0,-1){10}} \put(85,105){\vector(-1,0){5}} \put(80,110){\makebox(0,0)[cc]{+}} \put(55,90){\circle{10}} \put(55,90){\makebox(0,0)[cc]{26}} \put(55,100){\vector(0,-1){5}} \put(75,100){\line(0,-1){10}} \put(75,90){\vector(-1,0){15}} \put(60,95){\makebox(0,0)[cc]{+}} \put(15,75){\circle{10}} \put(15,75){\makebox(0,0)[cc]{36}} \put(15,85){\vector(0,-1){5}} \put(55,85){\line(0,-1){10}} \put(55,75){\vector(-1,0){35}} \put(90,115){\framebox(10,10)[cc]{4}} \put(100,115){\framebox(10,10)[cc]{1}} \put(95,105){\circle{10}} \put(95,105){\makebox(0,0)[cc]{5}} \put(95,115){\vector(0,-1){5}} \put(105,115){\line(0,-1){10}} \put(105,105){\vector(-1,0){5}} \put(100,110){\makebox(0,0)[cc]{+}} \put(110,115){\framebox(10,10)[cc]{9}} \put(120,115){\framebox(10,10)[cc]{\it 0}} \put(115,105){\circle{10}} \put(115,105){\makebox(0,0)[cc]{9}} \put(115,115){\vector(0,-1){5}} \put(125,115){\line(0,-1){10}} \put(125,105){\vector(-1,0){5}} \put(120,110){\makebox(0,0)[cc]{+}} \put(95,90){\circle{10}} \put(95,90){\makebox(0,0)[cc]{14}} \put(95,100){\vector(0,-1){5}} \put(115,100){\line(0,-1){10}} \put(115,90){\vector(-1,0){15}} \put(100,95){\makebox(0,0)[cc]{+}} \put(130,115){\framebox(10,10)[cc]{\it 0}} \put(140,115){\framebox(10,10)[cc]{\it 0}} \put(135,105){\circle{10}} \put(135,105){\makebox(0,0)[cc]{\it 0}} \put(135,115){\vector(0,-1){5}} \put(145,115){\line(0,-1){10}} \put(145,105){\vector(-1,0){5}} \put(140,110){\makebox(0,0)[cc]{+}} \put(150,115){\framebox(10,10)[cc]{\it 0}} \put(160,115){\framebox(10,10)[cc]{\it 0}} \put(155,105){\circle{10}} \put(155,105){\makebox(0,0)[cc]{\it 0}} \put(155,115){\vector(0,-1){5}} \put(165,115){\line(0,-1){10}} \put(165,105){\vector(-1,0){5}} \put(160,110){\makebox(0,0)[cc]{+}} \put(135,90){\circle{10}} \put(135,90){\makebox(0,0)[cc]{\it 0}} \put(135,100){\vector(0,-1){5}} \put(155,100){\line(0,-1){10}} \put(155,90){\vector(-1,0){15}} \put(140,95){\makebox(0,0)[cc]{+}} \put(95,75){\circle{10}} \put(95,75){\makebox(0,0)[cc]{14}} \put(95,85){\vector(0,-1){5}} \put(135,85){\line(0,-1){10}} \put(135,75){\vector(-1,0){35}} \put(15,60){\circle{10}} \put(15,60){\makebox(0,0)[cc]{50}} \put(15,70){\vector(0,-1){5}} \put(95,70){\line(0,-1){10}} \put(95,60){\vector(-1,0){75}} \put(20,80){\makebox(0,0)[cc]{+}} \put(100,80){\makebox(0,0)[cc]{+}} \put(20,65){\makebox(0,0)[cc]{+}} \put(10,40){\framebox(10,10)[cc]{50}} \put(15,55){\vector(0,-1){5}} \put(20,40){\framebox(10,10)[cc]{4}} \put(25,55){\vector(0,-1){5}} \put(30,40){\framebox(10,10)[cc]{5}} \put(35,55){\vector(0,-1){5}} \put(40,40){\framebox(10,10)[cc]{2}} \put(45,55){\vector(0,-1){5}} \put(50,40){\framebox(10,10)[cc]{26}} \put(55,55){\vector(0,-1){5}} \put(60,40){\framebox(10,10)[cc]{5}} \put(65,55){\vector(0,-1){5}} \put(70,40){\framebox(10,10)[cc]{14}} \put(75,55){\vector(0,-1){5}} \put(80,40){\framebox(10,10)[cc]{8}} \put(85,55){\vector(0,-1){5}} \put(90,40){\framebox(10,10)[cc]{14}} \put(95,55){\vector(0,-1){5}} \put(100,40){\framebox(10,10)[cc]{1}} \put(105,55){\vector(0,-1){5}} \put(110,40){\framebox(10,10)[cc]{9}} \put(115,55){\vector(0,-1){5}} \put(120,40){\framebox(10,10)[cc]{\it 0}} \put(125,55){\vector(0,-1){5}} \put(130,40){\framebox(10,10)[cc]{\it 0}} \put(135,55){\vector(0,-1){5}} \put(140,40){\framebox(10,10)[cc]{\it 0}} \put(145,55){\vector(0,-1){5}} \put(150,40){\framebox(10,10)[cc]{\it 0}} \put(155,55){\vector(0,-1){5}} \put(160,40){\framebox(10,10)[cc]{\it 0}} \put(165,55){\vector(0,-1){5}} \put(10,0){\framebox(10,10)[cc]{1}} \put(20,0){\framebox(10,10)[cc]{4}} \put(30,0){\framebox(10,10)[cc]{3}} \put(40,0){\framebox(10,10)[cc]{2}} \put(50,0){\framebox(10,10)[cc]{7}} \put(60,0){\framebox(10,10)[cc]{5}} \put(70,0){\framebox(10,10)[cc]{6}} \put(80,0){\framebox(10,10)[cc]{8}} \put(90,0){\framebox(10,10)[cc]{4}} \put(100,0){\framebox(10,10)[cc]{1}} \put(110,0){\framebox(10,10)[cc]{9}} \put(120,0){\framebox(10,10)[cc]{\it 0}} \put(130,0){\framebox(10,10)[cc]{\it 0}} \put(140,0){\framebox(10,10)[cc]{\it 0}} \put(150,0){\framebox(10,10)[cc]{\it 0}} \put(160,0){\framebox(10,10)[cc]{\it 0}} \put(25,40){\line(0,-1){5}} \put(20,35){\line(0,-1){2}} \put(30,35){\line(0,-1){2}} \put(45,40){\line(0,-1){5}} \put(40,35){\line(0,-1){2}} \put(50,35){\line(0,-1){2}} \put(35,40){\line(0,-1){10}} \put(30,30){\line(0,-1){2}} \put(50,30){\line(0,-1){2}} \put(65,40){\line(0,-1){5}} \put(60,35){\line(0,-1){2}} \put(70,35){\line(0,-1){2}} \put(85,40){\line(0,-1){5}} \put(80,35){\line(0,-1){2}} \put(90,35){\line(0,-1){2}} \put(75,40){\line(0,-1){10}} \put(70,30){\line(0,-1){2}} \put(90,30){\line(0,-1){2}} \put(55,40){\line(0,-1){15}} \put(50,25){\line(0,-1){2}} \put(90,25){\line(0,-1){2}} \put(105,40){\line(0,-1){5}} \put(100,35){\line(0,-1){2}} \put(110,35){\line(0,-1){2}} \put(125,40){\line(0,-1){5}} \put(120,35){\line(0,-1){2}} \put(130,35){\line(0,-1){2}} \put(115,40){\line(0,-1){10}} \put(110,30){\line(0,-1){2}} \put(130,30){\line(0,-1){2}} \put(145,40){\line(0,-1){5}} \put(140,35){\line(0,-1){2}} \put(150,35){\line(0,-1){2}} \put(165,40){\line(0,-1){5}} \put(160,35){\line(0,-1){2}} \put(170,35){\line(0,-1){2}} \put(155,40){\line(0,-1){10}} \put(150,30){\line(0,-1){2}} \put(170,30){\line(0,-1){2}} \put(135,40){\line(0,-1){15}} \put(130,25){\line(0,-1){2}} \put(170,25){\line(0,-1){2}} \put(95,40){\line(0,-1){20}} \put(90,20){\line(0,-1){2}} \put(170,20){\line(0,-1){2}} \put(15,40){\line(0,-1){25}} \put(10,15){\line(0,-1){2}} \put(170,15){\line(0,-1){2}} \thicklines \put(20,35){\line(1,0){10}} \put(40,35){\line(1,0){10}} \put(30,30){\line(1,0){20}} \put(60,35){\line(1,0){10}} \put(80,35){\line(1,0){10}} \put(70,30){\line(1,0){20}} \put(50,25){\line(1,0){40}} \put(100,35){\line(1,0){10}} \put(120,35){\line(1,0){10}} \put(110,30){\line(1,0){20}} \put(140,35){\line(1,0){10}} \put(160,35){\line(1,0){10}} \put(150,30){\line(1,0){20}} \put(130,25){\line(1,0){40}} \put(90,20){\line(1,0){80}} \put(10,15){\line(1,0){160}} \put(0,120){\makebox(0,0)[lc]{A=}} \put(0,45){\makebox(0,0)[lc]{A1=}} \put(0,5){\makebox(0,0)[lc]{A=}} \end{picture} }{\label{AInit} Initialisierung von A ({\tt ProbSelInit}) } Selektiert wird ein Element wie folgt (siehe auch Abbildung \ref{ASel}): \begin{enumerate} \item Ziehen einer gleichverteilten Zufallszahl {\tt z} zwischen {\tt 0} und \verb|S=A1[0]-1|. \item Man denke sich {\tt z} von rechts abgetragen. Da \verb|A1[n/2]| die Summe der rechten H„lfte von Elementen aus {\tt A} enth„lt gilt: \begin{itemize} \item ist ${\tt z}<\verb|A1[n/2]|$, so liegt {\tt z} in der rechten H„lfte von {\tt A}. Betrachte im folgenden diese H„lfte als neues Array \verb|A2[0..n/2-1]=A1[n/2..n-1]|. \item ist ${\tt z}\ge\verb|A1[n/2]|$, so liegt {\tt z} in der linken H„lfte von {\tt A}. Betrachte im folgenden diese H„lfe als neues Array {\tt A2[0..n/2-1]=A[0..n/2-1]}. Da sich das rechte Ende ge„ndert hat, muá zur Korrektur {\tt A1[n/2]} von {\tt z} abgezogen werden. \end{itemize} \item Wiederhole Schritt 2 mit {\tt A2}, solange ${\tt n}>1$. \item Die Komponente, bei der man am Ende dieser Iteration angelangt ist wird selektiert. \end{enumerate} \boxfig{ \unitlength=0.80mm \begin{picture}(170,55) \put(10,45){\framebox(10,10)[cc]{50}} \put(20,45){\framebox(10,10)[cc]{4}} \put(30,45){\framebox(10,10)[cc]{5}} \put(40,45){\framebox(10,10)[cc]{2}} \put(50,45){\framebox(10,10)[cc]{26}} \put(60,45){\framebox(10,10)[cc]{5}} \put(70,45){\framebox(10,10)[cc]{14}} \put(80,45){\framebox(10,10)[cc]{8}} \put(90,45){\framebox(10,10)[cc]{14}} \put(100,45){\framebox(10,10)[cc]{1}} \put(110,45){\framebox(10,10)[cc]{9}} \put(120,45){\framebox(10,10)[cc]{\it 0}} \put(130,45){\framebox(10,10)[cc]{\it 0}} \put(140,45){\framebox(10,10)[cc]{\it 0}} \put(150,45){\framebox(10,10)[cc]{\it 0}} \put(160,45){\framebox(10,10)[cc]{\it 0}} \put(15,45){\vector(0,-1){10}} \put(25,45){\line(0,-1){10}} \put(25,35){\vector(-1,0){10}} \put(35,45){\vector(0,-1){10}} \put(45,45){\line(0,-1){10}} \put(45,35){\vector(-1,0){10}} \put(15,35){\vector(0,-1){10}} \put(35,35){\line(0,-1){10}} \put(35,25){\vector(-1,0){20}} \put(55,45){\vector(0,-1){10}} \put(65,45){\line(0,-1){10}} \put(65,35){\vector(-1,0){10}} \put(75,45){\vector(0,-1){10}} \put(85,45){\line(0,-1){10}} \put(85,35){\vector(-1,0){10}} \put(55,35){\vector(0,-1){10}} \put(75,35){\line(0,-1){10}} \put(75,25){\vector(-1,0){20}} \put(15,25){\vector(0,-1){10}} \put(55,25){\line(0,-1){10}} \put(55,15){\vector(-1,0){40}} \put(95,45){\vector(0,-1){10}} \put(105,45){\line(0,-1){10}} \put(105,35){\vector(-1,0){10}} \put(115,45){\vector(0,-1){10}} \put(125,45){\line(0,-1){10}} \put(125,35){\vector(-1,0){10}} \put(95,35){\vector(0,-1){10}} \put(115,35){\line(0,-1){10}} \put(115,25){\vector(-1,0){20}} \put(135,45){\vector(0,-1){10}} \put(145,45){\line(0,-1){10}} \put(145,35){\vector(-1,0){10}} \put(155,45){\vector(0,-1){10}} \put(165,45){\line(0,-1){10}} \put(165,35){\vector(-1,0){10}} \put(135,35){\vector(0,-1){10}} \put(155,35){\line(0,-1){10}} \put(155,25){\vector(-1,0){20}} \put(95,25){\vector(0,-1){10}} \put(135,25){\line(0,-1){10}} \put(135,15){\vector(-1,0){40}} \put(15,15){\vector(0,-1){10}} \put(95,15){\line(0,-1){10}} \put(95,5){\vector(-1,0){80}} \put(0,50){\makebox(0,0)[lc]{A1=}} \put(15,5){\line(0,-1){5}} \put(99,5){\circle{6}} \put(99,5){\makebox(0,0)[cc]{25}} \put(102,5){\makebox(0,0)[lc]{$>\!\!14$}} \put(59,15){\circle{6}} \put(59,15){\makebox(0,0)[cc]{11}} \put(62,15){\makebox(0,0)[lc]{$<\!\!26$}} \put(90,6){\vector(-4,1){25}} \put(79,9){\makebox(0,0)[rt]{$^{25-14}$}} \put(79,25){\circle{6}} \put(79,25){\makebox(0,0)[cc]{11}} \put(82,25){\makebox(0,0)[lc]{$<\!\!14$}} \put(65,18){\vector(2,1){8}} \put(89,35){\circle{6}} \put(89,35){\makebox(0,0)[cc]{11}} \put(89,32){\makebox(0,0)[ct]{$>\!\!8$}} \put(80,29){\vector(3,2){5}} \put(84,38){\vector(-1,1){6}} \put(120,5){\makebox(0,0)[cc]{25}} \put(120,5){\circle{6}} \put(123,5){\makebox(0,0)[lc]{=z=random(50)}} \end{picture} }{\label{ASel} Selektion ({\tt ProbSel}) } Um ein Element $k$ in {\tt A} zu ersetzen, bestimmt man die ursprngliche Bewertung und korrigiert alle in der Hierarchie h”her stehenden Elemente, indem man die neue minus die alte Bewertung hinzuaddiert (\look Abbildung \ref{AModBew}). \boxfig{ \unitlength=0.80mm \begin{picture}(170,60) \put(10,50){\framebox(10,10)[cc]{50}} \put(20,50){\framebox(10,10)[cc]{4}} \put(30,50){\framebox(10,10)[cc]{5}} \put(40,50){\framebox(10,10)[cc]{2}} \put(50,50){\framebox(10,10)[cc]{26}} \put(60,50){\framebox(10,10)[cc]{5}} \put(70,50){\framebox(10,10)[cc]{14}} \put(80,50){\framebox(10,10)[cc]{8}} \put(90,50){\framebox(10,10)[cc]{14}} \put(100,50){\framebox(10,10)[cc]{1}} \put(110,50){\framebox(10,10)[cc]{9}} \put(120,50){\framebox(10,10)[cc]{\it 0}} \put(130,50){\framebox(10,10)[cc]{\it 0}} \put(140,50){\framebox(10,10)[cc]{\it 0}} \put(150,50){\framebox(10,10)[cc]{\it 0}} \put(160,50){\framebox(10,10)[cc]{\it 0}} \put(15,50){\vector(0,-1){10}} \put(25,50){\line(0,-1){10}} \put(25,40){\vector(-1,0){10}} \put(35,50){\vector(0,-1){10}} \put(45,50){\line(0,-1){10}} \put(45,40){\vector(-1,0){10}} \put(15,40){\vector(0,-1){10}} \put(35,40){\line(0,-1){10}} \put(35,30){\vector(-1,0){20}} \put(55,50){\vector(0,-1){10}} \put(65,50){\line(0,-1){10}} \put(65,40){\vector(-1,0){10}} \put(75,50){\vector(0,-1){10}} \put(85,50){\line(0,-1){10}} \put(85,40){\vector(-1,0){10}} \put(55,40){\vector(0,-1){10}} \put(75,40){\line(0,-1){10}} \put(75,30){\vector(-1,0){20}} \put(15,30){\vector(0,-1){10}} \put(55,30){\line(0,-1){10}} \put(55,20){\vector(-1,0){40}} \put(95,50){\vector(0,-1){10}} \put(105,50){\line(0,-1){10}} \put(105,40){\vector(-1,0){10}} \put(115,50){\vector(0,-1){10}} \put(125,50){\line(0,-1){10}} \put(125,40){\vector(-1,0){10}} \put(95,40){\vector(0,-1){10}} \put(115,40){\line(0,-1){10}} \put(115,30){\vector(-1,0){20}} \put(135,50){\vector(0,-1){10}} \put(145,50){\line(0,-1){10}} \put(145,40){\vector(-1,0){10}} \put(155,50){\vector(0,-1){10}} \put(165,50){\line(0,-1){10}} \put(165,40){\vector(-1,0){10}} \put(135,40){\vector(0,-1){10}} \put(155,40){\line(0,-1){10}} \put(155,30){\vector(-1,0){20}} \put(95,30){\vector(0,-1){10}} \put(135,30){\line(0,-1){10}} \put(135,20){\vector(-1,0){40}} \put(15,20){\vector(0,-1){10}} \put(95,20){\line(0,-1){10}} \put(95,10){\vector(-1,0){80}} \put(56,41){\makebox(0,0)[lb]{-}} \put(54,40){\makebox(0,0)[rc]{21}} \put(56,31){\makebox(0,0)[lb]{-}} \put(54,30){\makebox(0,0)[rc]{7}} \put(60,25){\circle{8}} \put(60,25){\makebox(0,0)[cc]{$-4$}} \put(50,11){\framebox(10,8)[cc]{22}} \put(20,15){\circle{8}} \put(20,15){\makebox(0,0)[cc]{$-4$}} \put(10,1){\framebox(10,8)[cc]{46}} \put(0,55){\makebox(0,0)[lc]{A1=}} \put(105,10){\makebox(0,0)[lc]{ $\tt A[4]=7\rightarrow A[4]=3$ (in {\tt A1})}} \end{picture} }{\label{AModBew} Rekonstruktion und Modifikation einer Bewertung } Um ein Element $k$ in {\tt A} zu l”schen, ersetzt man dieses durch das Element $n-1$, l”scht das Element $n-1$ und verkrzt das Array um 1. Die Initialisierung ben”tigt $n-1$ Additionen, die Selektion und das L”schen eines Elements $O(\log n)$ Operationen. Damit ergibt sich die Gesamtkomplexit„t der Selektion von $k$ Elementen zu $O(n+k\log n)$. In der Praxis treten zus„tzliche Probleme bei der Initialisierung auf; da der integer-Bereich beschr„nkt ist, l„uft man Gefahr diesen bei der Summation zu berschreiten. Deshalb wurde jede Summe ({\tt a+b}) durch eine Mittelwertsbildung ({\tt (a+b)/2}) ersetzt und s„mtliche Routinen dieser Korrektur angepaát. Bei Verminderung der Arrayl„nge von $2^n+1$ auf $2^n$, nimmt dabei die Hierarchieebene von {\tt A[0]} um eins ab und {\tt A[0]} muá entsprechend korrigiert werden. Der Test auf eine Zweierpotenz kann im brigen leicht wie folgt implementiert werden: \hfil {\tt N} ist Zweierpotenz $\gdw$ \verb|N&(N-1)==0| (bitweises \verb|&|) \hfil % \subsubsection{ Probability-Selection ({\tt SelMode=6}) } % --------------------------------------- Funktional ist dieser Selektions-Modus identisch mit vorherigem, der Algorithmus ist aber wesentlich einfacher und unter gewissen Umst„nden sogar schneller. Das Prinzip ist auch hier wiederum einfach: Es wird eine gleichverteilte Zufallszahl $i$ zwischen 0 und $n-1$ wie in {\it Random-Selection} gezogen, allerdings wird das Element $i$ nur mit Wahrscheinlichkeit $A_i/K$ ($K$ konstant) akzeptiert. Wird das Element $i$ nicht akzeptiert,so wird nach diesem Verfahren weitergesucht. Damit $A_i/K\le 1$ fr alle $i$ ist, muá $K\ge \max(A_i)$ gew„hlt werden. Die mittlere Zahl an Zyklen, bis eine Zufallszahl akzeptiert wird, ist somit $$ C\; = \;{1\over <\!\!\!A_i/K\!\!\!>_i}\; = \; {K\cdot n\over \sum_{i=0}^{n-1}{A_i}}\quad .$$ Man w„hlt also $K$ zweckm„áigerweise m”glichst klein, also $K=\max(A_i)$. $C$ h„ngt somit wesentlich vom Verh„ltnis des Fl„cheninhalts des der Funktion umbeschriebenen Rechtecks und der Funktion selbst ab (\look Abbildung \ref{VertFkt}). \begin{figure}\begin{center} \unitlength=1mm \thicklines \begin{picture}(120,80) \put(0,0){\vector(0,1){80}} \put(0,0){\vector(1,0){120}} \put(0,0){\dashbox{5}(110,70)[cc]{}} \put(1,73){\makebox(0,0)[lb]{$A_i$}} \put(115,1){\makebox(0,0)[cb]{$i$}} \put(0,0){\line(5,1){10}}\put(0,0){\circle*{1}} \put(10,2){\line(6,1){10}}\put(10,2){\circle*{1}} \put(20,3.67){\line(3,1){10}}\put(20,3.67){\circle*{1}} \put(30,7){\line(1,0){10}}\put(30,7){\circle*{1}} \put(40,7){\line(3,1){10}}\put(40,7){\circle*{1}} \put(50,10.33){\line(1,0){10}}\put(50,10.33){\circle*{1}} \put(60,10.33){\line(1,1){10}}\put(60,10.33){\circle*{1}} \put(70,20.33){\line(6,1){10}}\put(70,20.33){\circle*{1}} \put(80,22){\line(1,0){10}}\put(80,22){\circle*{1}} \put(90,22){\line(5,4){10}}\put(90,22){\circle*{1}} \put(100,30){\line(1,4){10}}\put(100,30){\circle*{1}} \thinlines \put(108,32){\line(-1,1){4}} \put(108,22){\line(-1,1){7}} \put(108,12){\line(-1,1){12}} \put(108,2){\line(-1,1){18}} \put(98,2){\line(-1,1){18}} \put(88,2){\line(-1,1){16}} \put(78,2){\line(-1,1){11}} \put(68,2){\line(-1,1){7}} \put(58,2){\line(-1,1){6}} \put(48,2){\line(-1,1){4}} \put(38,2){\line(-1,1){3}} \end{picture} \caption{\label{VertFkt} Verteilung + einhllendes Rechteck} \end{center}\end{figure} Bei einigermaáen gleichverteilten Zufallsgr”áen ist $C$ klein und damit die Zeitkomplexit„t eine kleine Konstante, also der Implementierung fr {\tt SelMode=2} mit Komplexit„t $O(\log n)$ vorzuziehen. \subsubsection{ Best-Selection ({\tt SelMode=3}) } % -------------------------------- Bei iterierter Selektion wird $A$ mittels Quicksort ({\tt QSort}) zuerst aufsteigend sortiert und dann bei jedem Zugriff die obersten Elemente geliefert und gel”scht (Die L„nge von $A$ wird reduziert). Mittlere Gesamtkomplexit„t: $O(n\log n)$ Bei einmaliger Selektion der $k$ gr”áten Elemente aus $A$ kann auf das Sortieren verzichtet werden und durch einen quicksort-„hnlichen Algorithmus ({\tt QMax}) mit nur noch linerarer Rekursion ersetzt werden. W„hlt man wie in Quicksort ein Trennelement und sortiert die kleineren Elemente an den Anfang des Arrays und die gr”áeren an das Ende, so kann man wie folgt weiter argumentieren: % \begin{itemize} \item Liegen weniger als $k$ Elemente in der oberen H„lfte, so werden {\it diese} garantiert und noch {\it einige} der unteren H„lfte selektiert. Man muá also nur noch die untere H„lfte betrachten und {\tt QMax} (rekurviv) mit der restlichen Zahl zu selektierender Elemente aufrufen. \item Liegen mehr als $k$ Elemente in der oberen H„lfte, so werden {\it einige} dieser und garantiert {\it keine} der unteren H„lfte selektiert. Man betrachtet hier also nur noch die obere H„lfte und ruft {\tt QMax} (rekursiv) mit der oberen H„lfte und $k$ auf. \end{itemize} Dieser Prozess bewirkt ein sukzessives Verschieben der Grenze, bis diese ''paát''. Mittlere Gesamtkomplexit„t: $O(n)$ \subsubsection{ Scaled-Selection ({\tt SelMode=4}) }\label{SclSelImpl} % ---------------------------------- An dieser Stelle sollen die Žquivalenz der beiden in \cpref{SclSelFkt} angedeuteten Interpretationen bewiesen, einige weitere mathematische Untersuchungen angestellt und die Vorteile dieser Selektionsart behandelt werden. Die Implementierung der 1.~Interpretation ist trivial: Ziehe zwei gleichverteilte Zufallszahlen $i$ und $j$ zwischen 0 und $n-1$ und w„hle aus $\{A_i,A_j\}$ das gr”áere Element mit Wahrscheinlichkeit $p$ (entsprechend das kleinere mit Wahrscheinlichkeit $q=1-p$) (*). \paragraph{ Mathematische Analyse }\hfill\\ Seien $A_1,\ldots,A_n$ in aufsteigender Reihenfolge sortiert, d.h. $A_1\le\ldots\le A_n$. \footnote{ Man mache sich klar, daá die Nummerierung keinen Einfluá auf die Selektion hat (da gleichverteilt) und somit im Programm beliebig (also einfach die Array-Indizes) gew„hlt werden kann und nicht wie man vermuten k”nnte, das Array zuerst sortiert werden muá.} Seien $X_1$ und $X_2$ die zwei gleichverteilten Zufallsgr”áen, $Y$ die sich aus obigem Prozeá (*) fr das selektierte Element ergebende Zufallsgr”áe, d.h. $$ P(X_i=k)\;=\;1/n \quad\mbox{ fr }\quad k\in\{1,\ldots,n\}$$ % (*) mathematisch bersetzt: \begin{eqnarray*} & P(Y=k)\quad=\quad p\cdot P(\max(X_1,X_2)=k)+ q\cdot P(\min(X_1,X_2)=k) &\\ & \mbox{da } X_1k)\cdot P(X_2>k)} _{\mbox{\scriptsize unabh„ngig}}\Bigr]\quad= \\ &=& p\cdot {k\over n}\cdot{k\over n}+ q\cdot\Bigl[1-(1-{k\over n})\cdot(1-{k\over n})\Bigr]\quad= \\ &=& q{2k\over n}+(p-q)\Bigl({k\over n}\Bigl)^2 \end{eqnarray*} % und wieder als Wahrscheinlichkeit ausgedrckt: \begin{eqnarray*} P(Y=k) &=& P(Y\le k)-P(Y\le k-1)\quad= \\ &=& \biggl[ q{2k\over n}+(p-q)\Bigl({k\over n}\Bigl)^2\biggr] - \biggl[q{2(k-1)\over n}+(p-q)\Bigl({k-1\over n}\Bigl)^2 \biggr]\quad= \\ &=& q{2\over n}+(p-q){2k-1\over n^2}\quad=\quad {2(p-q)\over n^2}\cdot k+\biggl({2q\over n}-{p-q\over n^2}\biggr)\quad \\ \end{eqnarray*} % $$\ff\quad\fbox{ $\displaystyle P(Y=k)\;=\;ak+b\quad\mbox{mit}\quad a={2(p-q)\over n^2}\quad,\quad b={2q\over n}-{p-q\over n^2} $ } $$ $Y$ ist also eine linear verteilte Zufallsgr”áe, wie in \ref{SclSelFkt} behauptet wird. $(A_1,\ldots,A_n)$ zu sortieren und mit Wahrscheinlichkeit proportional zu $(a+b,a+2b,\ldots,a+nb)$ zu selektieren, ist also zu obiger Methode „quivalent. Frei ist noch der Parameter $p$, der z.B. so gew„hlt werden kann, daá die Selektions-Wahrscheinlichkeit des $\mbox{\scriptsize gr”áten}\over \mbox{\scriptsize kleinsten}$ Elements gleich $C$ ist, d.h. % \begin{eqnarray*} C&:=&{P(Y=n)\over P(Y=1)} \quad=\quad {an+b\over a+b} \quad=\quad {2(p-q)n+2qn-(p-q)\over 2(p-q)+2qn-(p-q)} \quad=\\ &=& {2n(2p-1)+2n(1-p)-(2p-1)\over (2p-1)+2n(1-p)} \quad=\\ &=& {2np-(2p-1)\over 2n(1-p)+(2p-1)} \quad\toinfty{n}\quad {p\over 1-p} \\[2ex] % &\gdw& [2n(1-p)+(2p-1)]\cdot C \quad=\quad 2np-(2p-1) \\ &\gdw& [2(1-n)p+(2n-1)]\cdot C \quad=\quad 2(n-1)p+1 \\ &\gdw& 2(1-n)p(C+1)+(2n-1)C \quad=\quad 1 \\ &\gdw& p\quad=\quad{(2n-1)C-1\over 2(n-1)(C+1)} \quad\toinfty{n}\quad {C\over C+1} \end{eqnarray*} \paragraph{Beispiel 1:}\hfill\\ $C=1$: Kein Element wird bevorzugt $\ff$ \\ $p={(2n-1)-1\over2(n-1)(1+1)}={1\over 2}$: Rein gleichverteilter Zufall (klar) $\ff$ \\ $P(Y=k)=1/n$: Jedes Element mit Wahrscheinlichkeit $1/n$ % \vspace{-3ex} \paragraph{Beispiel 2:}\hfill\\ $C=2$: Wahrscheinlichkeit des ${\mbox{\scriptsize gr”áten}\over \mbox{\scriptsize kleinsten}}=2 \quad\ff\quad p={4n-3\over 6n-6}\toinfty{n}{2\over 3}$ % \vspace{-3ex} \paragraph{Beispiel 3:}\hfill\\ $p=1\quad\ff\quad P(Y=k)={1\over n^2}(2k-1)\quad,\quad C=2n-1$: Sehr starke Selektion % \vspace{-3ex} \paragraph{Beispiel 4:}\hfill\\ $p=2/3\quad\ff\quad P(Y=k)={1\over 3n^2}(2k+2n-1)\quad,\quad C={4n-1\over 2n+1}\toinfty{n}2$ : (\look Beispiel 2) \paragraph{Vorteile:}\hfill\\ \begin{itemize} \item {\bf Einfache Implementierung:} \\ Linearisierung, ohne sortieren zu mssen (nicht zu verwechseln mit linerarer Skalierung, die h„ufig verwendet wird). \item {\bf Gute Skalierung:} \\ Linearisierung auch unangenehmer Funktionen (\look Abbildung \ref{VertFkt}). \item {\bf Biologische Plausibilit„t:} \\ Zwei Individuen (Elemente) k„mpfen ums šberleben (selektiert zu werden), und dasjenige mit h”herer Fitneá (Bewertung) siegt mit gr”áerer Wahrscheinlichkeit ($p>q$ !). \end{itemize} \subsubsection{ Random-Selection ({\tt SelMode=5}) } % ---------------------------- Selektiere gleichverteilt, d.h. unabh„ngig von der Bewertung wird ein Element mit Wahrscheinlichkeit $1/n$ selektiert. \subsection{ Tupelalgorithmen } % ================ Die Routine {\it Bid}, die aus den {\sl Matching-Tupels} die {\sl Bid-Tupels} erzeugt, muá u.a. folgendes berechnen: \\ Gegeben ist eine Menge $M$ von {\sl Messages}, wobei jede {\sl Message} eine Intensit„t besitzt, die durch $f\!:\!M\to\Re$ gegeben ist. Teilmengen $M_i\subseteq M$ {\sl matchen} den Bedingungsteil $i$ eines festen {\sl Classifiers}. Nun werden s„mtliche {\sl Matching-Tupels} $T=M_1\times\cdots\times M_r$ gebildet und hiervon die Gesamtintensit„t gleich dem {\sl Support} $$ S\quad:=\nq\sum\limits_{(m_1,\ldots,m_r)\in T}\nq f(m_1)+\cdots+f(m_r) $$ berechnet. Durch eine kleine Transformation k”nnen diese $|T|=|M_1|\cdot\ldots\cdot\ |M_r|$ Additionen auf $|M_1|+\ldots+|M_r|$ Additionen reduziert werden. % $$\mbox{Betrachte: } \sum_{(m_1,\ldots,m_r)\in T}\nq\!\!\! f(m_i)\;=\nq \sum_{(m_1,\ldots,m_{i-1},m_{i+1},\ldots,m_r) \atop \in M_1\times\cdots\times M_{i-1}\times M_{i+1}\times\cdots\times M_r} \sum_{m_i\in M_i}\!\!f(m_i)\;= $$ $$=\;|M_1\times\cdots\times M_{i-1}\times M_{i+1}\times\cdots\times M_r| \cdot\!\!\sum_{m_i\in M_i}\!\!f(m_i)\;= $$ $$=\;{|T|\over|M_i|}\cdot{\sum_{m_i\in M_i}\!\!f(m_i)}\;=\; |T|<\!\!f\!\!>_{M_i} $$ $$\ff\quad S\;=\nq\!\!\! \sum\limits_{(m_1,\ldots,m_r)\in T}\nq f(m_1)+\cdots+f(m_r)\;=\; |T|\left\{<\!\!f\!\!>_{M_1}+\cdots+<\!\!f\!\!>_{M_r} \right\} $$ Fr zwei Bedingungen ergibt sich: $$\fbox{ $\displaystyle \sum_{m_1\in M_1,m_2\in M_2}^{\rule{0ex}{1ex}}\nq\nq\; f(m_1)+f(m_2)\quad=\quad |M_2|\!\!\!\sum_{m_1\in M_1}\!\!\!f(m_1) \;+\; |M_1|\!\!\!\sum_{m_2\in M_2}\!\!\!f(m_2) $ } $$ % Diese Žquivalenz wird in der Routine {\it Bid} verwendet. \subsection{ Zufallszahlen-Generatoren } % ========================= \subsubsection{ Gleichverteilte Zufallszahlen } % ----------------------------- Erstaunlicherweise sind selbst im hochentwickelten Compiler TC 2.0 von Borland die angeblich gleichverteilten Zufallszahlen katastrophal ungleichverteilt. Aus diesem Grund wurde ein Einzeiler {\tt random2()} geschrieben, der {\tt random()} ersetzt (und funktioniert !). \subsubsection{ {\tt flip} } % ---------- {\tt flip(p)} liefert mit Wahrscheinlichkeit {\tt p} das Ergebnis {\tt TRUE}, wobei zu beachten ist, daá {\tt p} eine Fixpunktzahl ist (\look\ref{FixP}). \subsubsection{ Normalverteilung } % ---------------- Sehr schnell ist folgende Approximation der Normalverteilung, da: \begin{itemize} \item keine Flieákommazahlen verwendet werden, \vspace{-1ex} \item nur {\it eine} 16-Bit Zufallszahl gezogen wird, \vspace{-1ex} \item nur elementare (maschinennahe) Rechenoperationen ausgefhrt werden. \end{itemize} Es werden die 1-Bits (Bits, deren Wert gleich 1 ist) der 16-Bit Zufallszahl gez„hlt, durch 2 geteilt und 4 abgezogen. Da es 0 bis 16 1-Bits gibt ist die Zufallsgr”áe durch $\pm 4$ beschr„nkt. \paragraph{ Mathematische Analyse }\hfill\\ % Jedes Bit $i$ ist eine $\{0,1\}$ gleichverteilte Zufallsgr”áe $B_i$, d.h. 0 mit Wahrscheinlichkeit 1/2 und 1 mit Wahrscheinlichkeit 1/2. $$ \ff\quad E(B_i)=1/2\quad,\quad Var(B_i)=1/4 $$ $$ \mbox{Sei}\qquad N={1\over 2}\sum_{i=1}^{16}{B_i} -4 $$ $$ \ff\quad E(N)={1\over 2}\cdot 16\cdot {1\over 2} -4=0 \quad,\quad Var(N)=\Bigl({1\over 2}\Bigr)^2\cdot 16\cdot {1\over 4} =1 $$ Nach dem zentralen Grenzwert-Satz geht eine $n$-fach-Summe einer beliebigen Verteilung fr $n\to\infty$ gegen eine Normalverteilung. $\ff$ $N$ ist ungef„hr Standard-Normalverteilung ($n=16\;÷\;\infty$), wobei $N$ bei den Werten $\pm 4$ abgeschnitten ist. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Datenstrukturen } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{ Konventionen } % ============ \subsubsection{ Anfangsbuchstaben } % ----------------- Um die Variablennamen einerseits nicht zu lang, das Progamm aber andererseits nicht durch kryptische Namensgebung unleserlich zu machen, wurden einige ein- oder mehrbuchstabige Namenskonventionen so weit wie m”glich das ganze Programm durchgehalten. Mittels Tabelle \ref{AId} und \ref{KzId} drften die meisten Namensgebungen verst„ndlich werden. \begin{table}\begin{center} \begin{tabular}{|r@{ = }l|l|}\hline \tt S & Size of & Konstante fr den Compiler \\ \multicolumn{2}{|c|}{} & (z.B. physikalische Arrayl„nge) \\ \hline \tt M & Maximal & Maximaler Wert \\ \multicolumn{2}{|c|}{} & (z.B. gr”áter jemals benutzter Array-Index) \\ \hline \tt N & Number of & Anzahl, Zahl \\ \multicolumn{2}{|c|}{} & (z.B. gr”áter aktuell benutzter Array-Index) \\ \hline \tt T & Type of & Typen werden mit T begonnen \\ \hline \tt pr & print & Routinen, die etwas im Textmode anzeigen \\ \hline \tt in & input & Routinen, die Eingaben von der Tastatur erwarten \\ \hline \tt N & not/non & Verneinung der Bedeutung der folgenden Buchstaben \\ \hline \tt D & Default & Defaultwerte (Konstanten) \\ \hline \tt X & & Variablen, auf die nur indirekt ber Zeiger zugegriffen wird \\ \hline \tt P & Pointer & h„ufig auch als Endbuchstabe bei Ergebnisparametern \\ \multicolumn{2}{|c|}{} & (z.B. NP = Pointer auf N) \\ \hline \end{tabular}\end{center}\vspace{-3ex} \caption{Bedeutung der Anfangsbuchstaben von Identifikatoren\label{AId}}\end{table} \begin{table}\begin{center} \begin{tabular}{|r|l|}\hline \tt CFS & Classifier-System \\ \hline \tt M & matching \\ \hline \tt M & Message \\ \hline \tt MM & matching Message \\ \hline \tt C & Classifier \\ \hline \tt T & Tupel \\ \hline \tt B & Bid \\ \hline \tt H & Help... \\ \hline \end{tabular}\end{center}\vspace{-3ex} \caption{Abkrzungen in Identifikatoren\label{KzId}}\end{table} \subsubsection{ Konstanten und primitive Datentypen } % ----------------------------------- Einige zweckm„áige Definitionen von Konstanten und primitiven Datentypen, wie {\tt bool}, {\tt byte}, {\tt index} u.a. wurden eingefhrt und k”nnen dem Programmlisting entnommen werden. Im folgenden soll nur der Datentyp {\tt fixp},der {\tt float} ersetzt, n„her erl„utert werden. % \paragraph{ FixPunkt-Zahlen }\hfill\label{FixP} {\tt fixp} ist eine 2-Byte {\tt integer} Zahl, wobei ein Byte als Vorkommateil, der andere als Nachkommateil interpretiert wird. Eine FixPunkt-Zahl {\tt fp} ist also als reelle Zahl {\tt fp/256} zu interpretieren; umgekehrt kann eine reele Zahl {\tt r} mittels {\tt (int)(r*256)} in FixPunkt-Format verwandelt werden, zu dem das Makro {\tt FixP} zur Verfgung steht. Aus diesem Grund werden im {\tt EXAMPLE1.C}-File auch s„mtliche reelle Konstanten mittels \centerline{\tt fixp Name = FixP( xx.xx )} definiert. FixPunkt-Zahlen k”nnen wie {\tt int} mittels $+$ und $-$ addiert und subtrahiert werden. Zur Multiplikation, Division und Potenzierung stehen {\tt FPMult}, {\tt FPDiv} und {\tt FPPow} zur Verfgung, die entweder mit Fehlerabfragen ({\tt SpeedF=FALSE}) implementiert sind oder als schnelle Makros ({\tt SpeedF=TRUE}) zur Verfgung stehen. \paragraph{ Strings, Messages, Conditions und Actions }\hfill Eine Message ist eine Folge von 0en und 1en, deren L„nge mittels {\tt SStr} (Size of String) festgelegt ist. Die {\sl Condition-} und {\sl Action-}Teile von {\sl Classifiern} sind Folgen von 0en, 1en und \#en, deren L„ngen ebenfalls durch {\tt SStr} festgelegt sind. Zur Codierung von {\sl Messages}, {\sl Conditions} und {\sl Actions} wird als gemeinsamer Datentyp {\tt TString} verwendet, der je nach {\tt SStr} 1 bis 4 Bytes im Speicher belegt: \begin{table}[ht]\begin{center} \begin{tabular}{|l|l|l|}\hline \tt SStr &\tt TString &\tt Bytes \\ \hline\hline 1--8 &\tt byte & 1 \\ \hline 9--16 &\tt int & 2 \\ \hline 17--32&\tt long & 4 \\ \hline \end{tabular}\end{center}\vspace{-3ex} \caption{Der Datentyp {\tt TString}}\end{table} Eine 0/1-Stelle einer Message entspricht einfach einem Bit in {\tt TString}. Unbenutzte Bits sind im Normalfall 0. Zur Codierung von {\sl Conditions} werden zwei Variable (C und B) vom Typ {\tt TString} verwendet und eine 0/1/\#-Stelle in einem korrespondierenden Paar von Bits in C und B gespeichert, wobei C als {\sl Condition} und B als Maske bezeichnet wird. Bei einer spezifischen Stelle (0/1) wird in C (wie bei Messages) ein Bit auf 0/1 gesetzt, das korrespondierende in C auf 1. Bei einer unspezifischen Stelle (\#) werden in C und B die korrespondierenden Bits beide auf 0 gesetzt. {\sl Actions} werden analog behandelt. Diese Art der Codierung erlaubt ein effizientes {\sl Message-Condition-Matching} und ben”tigt, nebenbei bemerkt, nur wenig Speicher. \begin{table}[ht]\begin{center}\begin{tabular}{|rcl|}\hline \sl Condition & & Bit 15 \dotfill\ 0 \\ 01\#\#1101\#1 &$\gdw$& C=0000000100110101 \\ & & B=0000001100111101 \\ \hline \end{tabular}\end{center}\vspace{-3ex} \caption{Beispiel einer {\sl Condition}-Codierung}\end{table} \paragraph{ Der Datentyp {\tt TIdVal} }\hfill Ein zentraler Datentyp zur Selektion ist {\tt TIdVal} oder besser \verb|TIdVal[]|, ein Array von {\tt TIdVal}. \verb| typedef struct { index Id; fixp Val; } TIdVal;| {\tt TIdVal} ist eine Struktur, die aus 2 integer-Werten besteht, die im Normalfall folgende Bedeutung haben. {\tt Id :} Ein Array-Index, der als {\tt Id} dieses Elements gilt. \\ {\tt Val:} Eine FixPunkt-Bewertung. Da {\tt TIdVal} 4 Byte im Speicher belegt, kann {\tt TIdVal} auch als {\tt long} aufgefaát werden, was h„ufig vorteilhaft (vor allem beim Kopieren) im Programm Verwendung findet. \subsection{ Datenstruktur des Classifier-Systems } % ==================================== An dieser Stelle soll die gesamte Datenstruktur incl. deren Zugriff zu Referenzzwecken graphisch dargestellt werden, Dokumentation der einzelnen Strukturkomponenten findet man im Programmlisting. \begin{itemize} \item Eine mit {\tt x} beschriftete Linie bedeutet, daá der untere Datentyp eine Komponente des oberen ist, auf die mittels {\tt .x} zugegriffen werden kann. \item Eine mit {\tt x} beschrifteter Pfeil bedeutet, daá der obere Datentyp eine Pointerkomponente \verb|->x| besitzt, die auf den unteren zeigt. \item Eine unbeschriftete Kante zwischen zwei Komponenten deutet ihre Žquivalenz an. \end{itemize} % Mehrfachbeschriftungen sind als mehrfaches Auftreten von Komponenten gleichen Typs zu interpretieren. \boxfig{ \unitlength=1mm \begin{picture}(110,40) \put(55,35){\oval(20,10)[]} \put(55,35){\makebox(0,0)[cc]{TCS}} \put(40,5){\oval(20,10)[]} \put(70,5){\oval(20,10)[]} \put(100,5){\oval(20,10)[]} \put(10,5){\oval(20,10)[]} \put(49,30){\vector(-2,-1){40}} \put(53,30){\vector(-2,-3){13.33}} \put(57,30){\vector(2,-3){13.33}} \put(61,30){\vector(2,-1){39}} \put(10,5){\makebox(0,0)[cc]{TMessL}} \put(40,5){\makebox(0,0)[cc]{TCFL}} \put(70,5){\makebox(0,0)[cc]{TBidL}} \put(100,5){\makebox(0,0)[cc]{TTupL}} \put(39,25){\makebox(0,0)[rb]{MP}} \put(29,20){\makebox(0,0)[rb]{NP}} \put(19,15){\makebox(0,0)[rb]{OP}} \put(46,20){\makebox(0,0)[rb]{CP}} \put(43,15){\makebox(0,0)[rb]{EP}} \put(64,20){\makebox(0,0)[lb]{CP}} \put(67,15){\makebox(0,0)[lb]{EP}} \put(81,20){\makebox(0,0)[lb]{TP}} \put(91,15){\makebox(0,0)[lb]{UP}} \end{picture} }{Globale {\sl Classifier}-Datenstruktur TCS} \boxfig{ \unitlength=1mm \begin{picture}(110,78) \put(70,73){\oval(20,10)[]} \put(55,48){\oval(20,10)[]} \put(10,23){\oval(20,10)[]} \put(40,23){\oval(20,10)[]} \put(70,23){\oval(20,10)[]} \put(100,23){\oval(20,10)[]} \put(65,68){\vector(-2,-3){10}} \put(70,68){\vector(0,-1){15}} \put(75,68){\vector(2,-3){10}} \put(49,43){\line(-2,-1){31}} \put(53,43){\line(-3,-4){11.33}} \put(57,43){\line(3,-4){11.33}} \put(61,43){\line(2,-1){31}} \put(77,48){\makebox(0,0)[cc]{.....}} \put(58,58){\makebox(0,0)[rb]{B}} \put(70,58){\makebox(0,0)[rb]{C}} \put(82,58){\makebox(0,0)[lb]{E}} \put(70,73){\makebox(0,0)[cc]{TMessL}} \put(55,48){\makebox(0,0)[cc]{TMess}} \put(10,23){\makebox(0,0)[cc]{TString}} \put(40,23){\makebox(0,0)[cc]{TIntens}} \put(70,23){\makebox(0,0)[cc]{TCFId}} \put(100,23){\makebox(0,0)[cc]{int}} \put(28,33){\makebox(0,0)[rb]{M}} \put(45,33){\makebox(0,0)[rb]{I}} \put(65,33){\makebox(0,0)[lb]{CF}} \put(82,33){\makebox(0,0)[lb]{H}} \put(40,4){\oval(16,8)[]} \put(40,18){\line(0,-1){10}} \put(40,4){\makebox(0,0)[cc]{fixp}} \put(70,4){\oval(16,8)[]} \put(70,18){\line(0,-1){10}} \put(70,4){\makebox(0,0)[cc]{index}} \end{picture} }{{\sl MessageList}-Datenstruktur {\tt TMessL}} \boxfig{ \unitlength=1mm \begin{picture}(145,118) \put(75,113){\oval(20,10)[]} \put(60,88){\oval(20,10)[]} \put(70,108){\vector(-2,-3){10}} \put(75,108){\vector(0,-1){15}} \put(80,108){\vector(2,-3){10}} \put(82,88){\makebox(0,0)[cc]{.....}} \put(63,98){\makebox(0,0)[rb]{B}} \put(75,98){\makebox(0,0)[rb]{C}} \put(87,98){\makebox(0,0)[lb]{E}} \put(10,53){\oval(20,10)[]} \put(35,53){\oval(20,10)[]} \put(60,53){\oval(20,10)[]} \put(85,53){\oval(20,10)[]} \put(110,53){\oval(20,10)[]} \put(135,53){\oval(20,10)[]} \put(55,83){\line(-2,-1){50}} \put(57,83){\line(-1,-1){25}} \put(59,83){\line(0,-1){25}} \put(61,83){\line(3,-4){18.67}} \put(63,83){\line(3,-2){39}} \put(65,83){\line(3,-1){74}} \put(15,63){\makebox(0,0)[rb]{C2}} \put(25,68){\makebox(0,0)[rb]{C1}} \put(37,63){\makebox(0,0)[rb]{Sp}} \put(59,63){\makebox(0,0)[rb]{Act}} \put(76,63){\makebox(0,0)[lb]{S}} \put(80,72){\makebox(0,0)[lb]{Get}} \put(86,68){\makebox(0,0)[lb]{Pay}} \put(92,64){\makebox(0,0)[lb]{Tax}} \put(98,60){\makebox(0,0)[lb]{PSP}} \put(125,63){\makebox(0,0)[lb]{H}} \put(86,109){\makebox(0,0)[lb]{\tiny BidMode}} \put(88,107){\makebox(0,0)[lb]{\tiny SuppMode}} \put(90,105){\makebox(0,0)[lb]{\tiny BidTupSelMode}} \put(92,103){\makebox(0,0)[lb]{\tiny BidActSelMode}} \put(94,101){\makebox(0,0)[lb]{\tiny FireBidSelMode}} \put(96,99){\makebox(0,0)[lb]{\tiny FireTupSelMode}} \put(98,97){\makebox(0,0)[lb]{\tiny MBids}} \put(100,95){\makebox(0,0)[lb]{\tiny MAct}} \put(102,93){\makebox(0,0)[lb]{\tiny MFire}} \put(104,91){\makebox(0,0)[lb]{\tiny RiskFak}} \put(106,89){\makebox(0,0)[lb]{\tiny SpecPow}} \put(108,87){\makebox(0,0)[lb]{\tiny RelSuppPow}} \put(110,85){\makebox(0,0)[lb]{\tiny EBidPow}} \put(112,83){\makebox(0,0)[lb]{\tiny ESpecPow}} \put(114,81){\makebox(0,0)[lb]{\tiny ClaimMode}} \put(116,79){\makebox(0,0)[lb]{\tiny DisMode}} \put(118,77){\makebox(0,0)[lb]{\tiny SumMode}} \put(75,113){\makebox(0,0)[cc]{TCFL}} \put(60,88){\makebox(0,0)[cc]{TCF}} \put(10,53){\makebox(0,0)[cc]{TCond}} \put(35,53){\makebox(0,0)[cc]{fixp}} \put(60,53){\makebox(0,0)[cc]{TAct}} \put(85,53){\makebox(0,0)[cc]{fixp}} \put(110,53){\makebox(0,0)[cc]{fixp}} \put(135,53){\makebox(0,0)[cc]{int}} \put(10,23){\oval(20,10)[]} \put(35,23){\oval(20,10)[]} \put(60,23){\oval(20,10)[]} \put(85,23){\oval(20,10)[]} \put(10,23){\makebox(0,0)[cc]{TString}} \put(35,23){\makebox(0,0)[cc]{TCType}} \put(60,23){\makebox(0,0)[cc]{TString}} \put(85,23){\makebox(0,0)[cc]{TCType}} \put(10,48){\line(0,-1){20}} \put(15,48){\line(1,-1){20}} \put(60,48){\line(0,-1){20}} \put(65,48){\line(1,-1){20}} \put(10,38){\makebox(0,0)[rb]{C}} \put(10,33){\makebox(0,0)[rb]{B}} \put(30,33){\makebox(0,0)[lb]{T}} \put(60,33){\makebox(0,0)[rb]{B}} \put(60,38){\makebox(0,0)[rb]{A}} \put(80,33){\makebox(0,0)[lb]{T}} \put(84,110){\vector(1,-1){35}} \put(119.50,72){\oval(11,6)[]} \put(35,4){\oval(16,8)[]} \put(35,18){\line(0,-1){10}} \put(35,4){\makebox(0,0)[cc]{int}} \put(85,4){\oval(16,8)[]} \put(85,18){\line(0,-1){10}} \put(85,4){\makebox(0,0)[cc]{int}} \end{picture} }{{\tt ClassifierList- \& EffectorList}-Datenstruktur {\tt TCFL}} \boxfig{ \unitlength=1mm \begin{picture}(145,83) \put(75,78){\oval(20,10)[]} \put(60,53){\oval(20,10)[]} \put(70,73){\vector(-2,-3){10}} \put(75,73){\vector(0,-1){15}} \put(80,73){\vector(2,-3){10}} \put(82,53){\makebox(0,0)[cc]{.....}} \put(63,63){\makebox(0,0)[rb]{B}} \put(75,63){\makebox(0,0)[rb]{C}} \put(87,63){\makebox(0,0)[lb]{E}} \put(10,23){\oval(20,10)[]} \put(35,23){\oval(20,10)[]} \put(60,23){\oval(20,10)[]} \put(85,23){\oval(20,10)[]} \put(110,23){\oval(20,10)[]} \put(135,23){\oval(20,10)[]} \put(55,48){\line(-2,-1){40}} \put(57,48){\line(-1,-1){20}} \put(59,48){\line(0,-1){20}} \put(61,48){\line(1,-1){20}} \put(63,48){\line(2,-1){40}} \put(65,48){\line(3,-1){62}} \put(75,78){\makebox(0,0)[cc]{TBidL}} \put(60,53){\makebox(0,0)[cc]{TBid}} \put(25,33){\makebox(0,0)[rb]{CF}} \put(42,33){\makebox(0,0)[rb]{BV}} \put(59,33){\makebox(0,0)[rb]{EV}} \put(76,33){\makebox(0,0)[lb]{Tup}} \put(93,33){\makebox(0,0)[lb]{N}} \put(110,33){\makebox(0,0)[lb]{F}} \put(10,23){\makebox(0,0)[cc]{TCFId}} \put(35,23){\makebox(0,0)[cc]{fixp}} \put(60,23){\makebox(0,0)[cc]{fixp}} \put(85,23){\makebox(0,0)[cc]{TTupId}} \put(110,23){\makebox(0,0)[cc]{int}} \put(135,23){\makebox(0,0)[cc]{bool}} \put(10,4){\oval(16,8)[]} \put(10,18){\line(0,-1){10}} \put(10,4){\makebox(0,0)[cc]{index}} \put(47,10){\oval(44,10)[]} \put(47,10){\makebox(0,0)[cc]{long}} \put(85,4){\oval(16,8)[]} \put(85,18){\line(0,-1){10}} \put(85,4){\makebox(0,0)[cc]{index}} \end{picture} }{{\sl BidList}-Datenstruktur {\tt TBidL}} \boxfig{ \unitlength=1mm \begin{picture}(55,83) \put(40,78){\oval(20,10)[]} \put(25,53){\oval(20,10)[]} \put(35,73){\vector(-2,-3){10}} \put(40,73){\vector(0,-1){15}} \put(45,73){\vector(2,-3){10}} \put(47,53){\makebox(0,0)[cc]{.....}} \put(28,63){\makebox(0,0)[rb]{B}} \put(40,63){\makebox(0,0)[rb]{C}} \put(52,63){\makebox(0,0)[lb]{E}} \put(10,23){\oval(20,10)[]} \put(40,23){\oval(20,10)[]} \put(22,48){\line(-1,-2){10}} \put(28,48){\line(1,-2){10}} \put(14,33){\makebox(0,0)[rb]{M2}} \put(17,38){\makebox(0,0)[rb]{M1}} \put(35,35){\makebox(0,0)[lb]{S}} \put(40,78){\makebox(0,0)[cc]{TTupL}} \put(25,53){\makebox(0,0)[cc]{TTup}} \put(10,23){\makebox(0,0)[cc]{TMessId}} \put(40,23){\makebox(0,0)[cc]{fixp}} \put(10,4){\oval(16,8)[]} \put(10,18){\line(0,-1){10}} \put(10,4){\makebox(0,0)[cc]{index}} \end{picture} }{{\sl TupelList}-Datenstruktur {\tt TTupL}} \clearpage %\subsection{ Simulationsdynamik } % ================== %\boxfig{\input empty.PIC}{Dynamische \& Statische Beziehung} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \section{ Hauptzyklus } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % {\it Siehe die in Krze von Gerhard Weiá erscheinende % Benutzerbeschreibung \cite{Weiss}}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Benutzer-Oberfl„che } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{ Start des Klassifizierungs-Systems } % ================================== Es ist vorteilhaft (aber nicht zwingend notwendig) das \CFS\ unter einem C-Compiler mit integrierter Entwicklungsumgebung (IDE) oder von einem C-Debugger aus zu starten, da jene Umgebungen auch als Arbeitsumgebung des \CFS\ verwendbar sind. Hier soll die Benutzung des \CFS\ bei Verwendung des Turbo-C 2.0 oder Turbo-C++ Compilers beschrieben werden. Ben”tigt werden zwei C-Files: \begin{description} \item{\verb|CFSSIM.C |:} Das Klassifizierungs-System \item{\verb|EXAMPLEn.C|:} Die beispielspezifische Daten, wie Benutzer-Parameter \& Benutzer-Funktionen \end{description} % {\tt EXAMPLE1.C} enth„lt als Beispiel den 4:2-Decoder, der in \cite{Goldberg} und \cite{Wilson} beschrieben ist, auf das ich mich im folgenden beziehe. Da die Beispiele einige Parameter (die mit \verb|#define| definierten) enthalten, die den Objekt-Code von {\tt CFSSIM.OBJ} bestimmen, kann {\tt CFSSIM.C} nicht {\it einmal} vorweg compiliert werden. Daher wurde folgender Weg gew„hlt. {\tt EXAMPLE$n$.C} ist {\it ihr} Bezugsfile (Main-File) den Sie mit dem Turbo-C-Editor ggf. modifizieren und starten. Die \verb|#include|-Zeile bewirkt dann, daá {\tt CFSSIM.C} mit den aktuellen \verb|#define|-Paramtern compiliert wird. Bevor Sie das Programm starten sollten Sie unbedingt in die Zeile, in der \verb|BreakPoint()| steht, mit {\tt Ctrl-F8} einen Breakpoint setzen. Damit k”nnen Sie wie in \ref{ParMod} beschrieben wird jederzeit das \CFS\ kurz unterbrechen und in die IDE gelangen, Parameter modifizieren und das \CFS\ an der Unterbrechungsstelle fortsetzen. Die Schritte sind im einzelnen: \begin{center}\begin{tabular}{ll} \bf Eingabe & \bf Bedeutung \\[1ex] \tt{TC} o.„. & Aufruf von Turbo-C \\ \tt Alt-F L EXAMPLE1.C & Laden des Beispiels \\ ?? & Eventuell modifizieren \\ \tt Ctrl-F8 & Breakpoint in Zeile \verb|BreakPoint()| setzen \\ \tt Alt-R R & Start des \CFS\ \\ ?? & Verschiedene \CFS-Menu-Eingaben \ref{Menu} \\ \tt B & Rckkehr in die IDE von Turbo-C \\ \tt Ctrl-F4 \it Name=Wert & Modifikation von Paramtern \\ \tt Alt-R R & Fortsetzen der \CFS-Simulation \\ \ldots & \\ \end{tabular}\end{center} \subsection{ Menusteuerung }\label{Menu} % ============= Nachdem Sie das \CFS\ mittles {\tt Alt-R R} gestartet haben, erscheint in der 1.~Zeile eine Menu-Leiste. Die Groábuchstaben geben die den Menupunkt aktivierenden Tasten an, deren Bedeutung im einzelnen in \ref{Menu1} bis \ref{MenuN} erkl„rt wird. Unterhalb der Menu-Leiste erscheint die Simulationsberschrift, die auch ins Protokoll aufgenommen wird. Danach wird das Protokoll abgeschaltet und die Simulation gestartet (Initialisierung u.a.) und knapp vor Eintritt in den 1.~Zyklus unterbrochen. Danach erwartet das \CFS\ eine Menu-Eingabe (z.B. {\tt C} um die Simulation fortzusetzen). Solche Menu-Eingaben k”nnen auch sp„ter {\it jederzeit}, d.h. auch w„hrend die Simulation l„uft, erfolgen. \subsubsection{ Ausgabe ({\tt 0123}) ({\tt Display}) }\label{Menu1} % ------------------------------------ Mit der Taste \fbox D wird der aktuelle Status des \CFS\ angezeigt. Mit den Tasten \fbox 0 bis \fbox 3 wird die Ausfhrlichkeit s„mtlicher Ausgaben beeinfluát. Fr Details \look\ref{StStAus} und Anhang C. \subsubsection{ Einzelschritt-Abarbeitung ({\tt stEp}) ({\tt ESC}) ({\tt Cont}) } % --------------------------------------------------------------- Im {\tt SingleStep-Mode} wird die Simulation nach jedem Zyklus oder jeder Episode angehalten. Ist {\tt SingleStep=OFF}, so l„uft die Simulation solange, bis sie mit \fbox{ESC} (oder A oder B) unterbrochen wird. In beiden F„llen kann die Simulation mit \fbox C oder \fbox{\it space} fortgesetzt werden. Mit \fbox E kann der {\tt SingleStep-Mode} aus- und auch wieder eingeschaltet werden. \subsubsection{ Protokoll ({\tt Prot}) } % --------------------- Die šberschrift incl. Zeitpunkt des Simulationsstarts wird immer mitprotokolliert. Zu jedem Zeitpunkt kann man mit \fbox P die Protokollierung ein- und auch wieder ausschalten. Ist {\tt Protocoll=ON}, so wird {\it alles}, was auf dem Bildschirm erscheint auch an das File, deren Name in {\tt EXAMPLE$n$.C} durch {\tt ProtDev[]} angegeben wurde, {\it angeh„ngt}; d.h. ein evtl. bestehendes Protokoll wird nicht gel”scht, sondern erweitert. Žndert man den Protokollnamen w„hrend der Simulation, so ist zu beachten, daá dieser neue Name erst nach einmaligem Tastendruck \fbox P aktiviert wird. {\bf Tip:} Den Protokoll-File kann man einfach und schnell mit dem Turbo-Editor inspizieren und evtl. aufbereiten. \subsubsection{ Parameter-Modifikation ({\tt Break}) }\label{ParMod} % ------------------------------------ Parameter k”nnen nach Beendigung der Simulation mittels \fbox A im {\tt EXAMPLE$n$.C}-File modifiziert und das \CFS\ neu compiliert und gestartet werden. Wesentlich schneller kann man dies auch erreichen, indem man mit \fbox B die Simulation unterbricht (nur wenn der Breakpoint gesetzt wurde, da dieser aufgerufen wird !). Nun befinden Sie sich in der IDE (oder im Debugger) und drfen alles machen, was ihnen die IDE gestattet; nur den Source-File sollten Sie nicht modifizieren. Die h„ufigste Anwendung wird wohl die Einsichtnahme in oder die Modifikation von Benutzer-Parametern (\look Kapitel \ref{BenPar}) sein. Dies k”nnen Sie mittels \\[2ex] % \centerline{\tt Ctrl-F4 $Name$ \fbox{\it return} $bzw.$ Ctrl-F4 $Name=Wert$ } erreichen. Fr Details siehe Turbo-C-Beschreibung. Die Simulation k”nnen Sie mit \fbox{Alt-R} \fbox R fortsetzen, wollen Sie die Simulation neu starten, drcken Sie anschlieáend noch R (Restart). Auf keinen Fall sollten Sie den Neustart von der IDE aus z.B. mittels Alt-R P Alt-R R vornehmen, da diese ihre Parametermodifikationen rckg„ngig macht. \subsubsection{ Sonstige Menu-Befehle }\label{MenuN} % --------------------- Mit \fbox R (Restart) k”nnen Sie das \CFS\ neu starten. R ist in jeder Hinsicht ein absoluter Neustart, auch der Zufallszahlen-Generator wird wie beim Erstaufruf gesetzt. Somit lassen sich Simulationsl„ufe exakt reproduzieren. \\ Mit \fbox Z ({\tt rdZ}) kann der Zufallszahlen-Generator zuf„llig (nicht reproduzierbar) initialisiert werden. \\ Der Warnton bei Warnungen und Fehlern l„át sich mittels \fbox S (Sound) aus- und einschalten. \fbox T ({\tt Test}) ruft die Routine {\tt Test} auf, die sich in {\tt CFSSIM.C} befindet, aber auch nach {\tt EXAMPLE$n$.C} gelegt werden kann und bei Bedarf mit beliebigem Inhalt gefllt werden kann. \subsubsection{ Status- \& Statistik-Ausgabe }\label{StStAus} % ---------------------------- Neben Fehlermeldungen, Warnungen und anderem ''Kleinkram'' k”nnen der {\sl Classifier}status (CS) und die Statistik (ST) als Einzeiler oder ausfhrlich angezeigt werden. Dies erfolgt entweder mit der Taste D (Display) oder automatisch w„hrend der Simulation. Wie und wann was erscheint kann der Tabelle \ref{prmode} und dem Beispielprotokoll im Anhang C entnommen werden. \begin{table}[ht]\begin{center}\begin{tabular}{|c|c|c|c|}\hline \tt prMode &\bf Anzeige pro Schritt &\bf Anzeige pro Episode &\bf weiteres \\ \hline\hline 3 & CS ausfhrlich & CS \& ST ausfhrlich &\sl Warnings \& Errors \\ \hline 2 & CS einzeilig & CS \& ST ausfhrlich &\sl Warnings \& Errors \\ \hline 1 & --- & Stat einzeilig &\sl Warnings \& Errors \\ \hline 0 & --- & --- &\sl Errors \\ \hline \end{tabular} \caption{Ausgabe in den verschiedenen {\sl Print-Modes}\label{prmode}} \end{center}\end{table} Jeder Warnung ist die H„ufigkeit ihres bisherigen Auftretens vorangestellt. Dies hat folgenden Sinn: \\ Da manchmal Warnungen penetrant h„ufig auftreten, man deren Ursache aber erst sp„ter beheben m”chte, wird ab der vierten Warnung (eines Typs) diese nur noch stichprobenartig ausgegeben, und zwar im Laufe der Zeit immer seltener. An der Nummerierung erkennt man aber dennoch wie h„ufig die Warnung in der Zwischenzeit erzeugt wurde. Dieses Konzept hat den Vorteil, daá schon nach kurzer Zeit die Anzeige frei von l„stigen Warnungen bleibt. Es versteht sich von selbst, daá man sich trotzdem Gedanken darber machen sollte, ob eine Warnung nicht doch ihre Berechtigung hat. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \section{ Benutzer-Funktionen } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % {\it Siehe die in Krze von Gerhard Weiá erscheinende % Benutzerbeschreibung \cite{Weiss}.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Benutzer-Parameter }\label{BenPar} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newenvironment{CFSParTab}{\begin{center}\begin{tabular}{|l|l|l|} \hline \bf Name & \bf Bereich & \bf Beschreibung\\\hline\hline}% {\end{tabular}\end{center}\vspace{-3ex} } Eine ausfhrliche Beschreibung aller Benutzer-Parameter und deren Wirkungsweise findet man in \cite{Weiss}. Tabellarische šbersichten sind hier abgebildet. Zus„tzlich zu den theoretischen Bereichen ergeben sich noch Einschr„nkungen durch die physikalischen Datentypen, wie {\tt int}, {\tt long}, \ldots. \begin{table}\begin{CFSParTab} \tt SMessL & 1\ldots$\infty$ & Max. L„nge der {\sl Message}-Liste incl. Detektor-{\sl Message}. \\ \hline \tt SOutL & 1\ldots$\infty$ & Max. Anzahl von Aktionen {(\sl Output-Message)}. \\ \hline \tt SCFL & 1\ldots$\infty$ & Anzahl der {\sl Classifier}. \\ \hline \tt SEffL & 1\ldots$\infty$ & Anzahl der Effektoren. \\ \hline \tt SBidL & 1\ldots$\infty$ & Max. Anzahl von {\sl Bid's} bzw. {\sl Bid-Tupels}. \\ \cline{1-2} \tt STupL & 1\ldots$\infty$ & W„hlen Sie {\tt SBidL} und {\tt STupL} so groá wie m”glich. \\ \hline\hline \tt SStr & 1\ldots 32 & {\sl Message},{\sl Condition} \& {\sl Action}-L„nge, \\ & & d.h. Anzahl der 0/1/\#-Stellen. \\ \hline \tt TwoCond &\tt FALSE & {\sl Classifier} haben eine {\sl Condition}. \\ \cline{2-3} &\tt TRUE & {\sl Classifier} haben zwei {\sl Conditions}. \\ \hline \tt SpeedF &\tt FALSE & Evtl. auftretende Fehler werden berprft \\ & & und als {\sl Warning} oder {\sl Error} angezeigt. \\ \cline{2-3} &\tt TRUE & CFS ist auf Zeit optimiert. \\ \hline \end{CFSParTab}\caption{Array-Gr”áen und andere Compiler-Information}\end{table} \begin{table}\begin{CFSParTab} \tt StRate & 1\ldots$\infty$ & Episodenl„nge: Anzahl der Zyklen, nach denen und \\ & & fr die eine Statistik berechnet und angezeigt wird. \\ \hline \tt SclSel &50\%\ldots 100\% & Skalierungsfaktor bei {\tt SelMode=4} (\look\ref{SclSelImpl}). \\ \hline \tt ProtDev & & Protokoll-Filename als String.\\ \hline \tt DetMessTag& & {\it Tag's} fr Detektor-{\sl Message} als String \\ \hline \tt EffMessTag& & {\it Tag's} fr Effektor-{\sl Message} als String \\ \hline \end{CFSParTab}\caption{Allgemeine Variablen}\end{table} \begin{table}\begin{CFSParTab} \tt DetRate & 1\ldots$\infty$ & Detektor-Aufruf-Rate \\ \hline \tt MDetM & 1\ldots\tt SMessL& Max. Anzahl von \sl Detector-Messages \\ \hline \tt DefDetMI & 0.0\ldots 9.0 & \sl Default-Detector-Message-Intensity \\ \hline \tt DefStr & 0.0\ldots 9.0 & \sl Default-Classifier-Strength \\ \hline \tt DefStrDev & 0\ldots 25\% & \sl Default-Classifier-Strength-Deviation\\ \hline \end{CFSParTab}\caption{{\tt Detector}-Variablen}\end{table} \begin{table}\begin{CFSParTab} \tt DefNMI & 0.0\ldots 9.0 & {\sl Default-Non-Match-Intensity:} \\ & & {\sl Message-Intensity}-Ersatzwert bei negativen \\ & & {\sl Conditions} \\ \hline \tt Dev2 & 0\ldots 25\% & \sl EBid-Deviation \\ \hline \tt DelMessSelMode &-6\ldots 6 & {\sl Selection-Mode} bei zu vielen {\sl Messages} \\ & & in abh. der {\sl Intensity} \\ \hline \tt CleanHallF& \tt FALSE & {\sl Classifier} mit {\sl Detector-Tag} werden nicht gel”scht \\ & \tt TRUE & {\sl Classifier} mit {\sl Detector-Tag} werden gel”scht \\ \hline \tt EffRate & 1\ldots$\infty$ & Effektor-Aufruf-Rate \\ \hline \end{CFSParTab}\caption{{\tt Matching-, Bid-, Clean- \& Effector-}Variablen}\end{table} \begin{table}\begin{CFSParTab} \tt ReRate & 1\ldots$\infty$ & {\sl Reinforcement}-Aufruf-Rate \\ \hline \tt CreditMode& 1\ldots 4 & 1 = Expliziter {\sl Bucket-Brigade} \\ & & 2 = Impliziter {\sl Bucket-Brigade} (nicht impl.) \\ & & 3 = {\sl Profit-Sharing-Plan} (PSP) \\ & & 4 = Kein {\sl Credit-Assignment} \\ \hline \tt NMFrac & 0\ldots 100\% & Reduzierter {\sl Reinforcement / Credit} fr \\ & & {\sl Classifier} mit negativer {\sl Condition} \\ \hline \tt DetFrac & 0\ldots 100\% & Reduzierter {\sl Reinforcement / Credit} fr \\ & & {\sl Detector-Messages} \\ \hline \tt PSPFrac & 0\ldots 100\% & PSP-Reduktions-Konstante \\ \hline \tt PSPDisMode& 1\ldots 4 & PSP-{\sl Reinf.-Distr.} fr {\sl Classifier} ist prop. \\ & & 1 = eins \\ & & 2 = Anzahl der {\sl Bids} \\ & & 3 = maximalem {\sl Bid}-Wert \\ & & 4 = Summe der {\sl Bid}-Werte \\ \hline \end{CFSParTab}\caption{{\tt Credit}-Variablen}\end{table} \begin{table}\begin{CFSParTab} \tt HeadTax & 0.0\ldots 9.0 & {\sl Taxes} pro Zyklus \\ \hline \tt MessTax & 0.0\ldots 9.0 & {\sl Taxes} fr das Senden einer {\sl Message} \\ \hline \tt BidTax & 0.0\ldots 9.0 & {\sl Taxes} fr das Bieten ({\sl Bid}) \\ \hline \tt BidTaxMode& 1\ldots 2 & 2 = Zahle nur, falls Bieten nicht zum Feuern fhrte \\ & & 1 = Zahle immer \\ \hline \tt MultBidTaxF & \tt TRUE & Zahle fr jeden {\sl Bid} extra \\ \cline{2-3} & \tt FALSE & Zahle einmal fr alle {\sl Bids} \\ \hline \tt MultMessTaxF & \tt TRUE & Zahle fr jede gefeuerte {\sl Message} \\ \cline{2-3} & \tt FALSE & Zahle einmal fr alle gefeuerten {\sl Messages} extra \\ \hline \end{CFSParTab}\caption{{\tt Taxes}-Variablen}\end{table} \begin{table}\begin{CFSParTab} \tt MaxStr & 1.0\ldots 20.0 & Max. {\sl Classifier-Strength} \\ \hline \tt MinStr & 0.0\ldots 1.0 & Min. {\sl Classifier-Strength} \\ \hline \end{CFSParTab}\caption{{\tt StrUpDate}-Variablen}\end{table} \begin{table}\begin{CFSParTab} \tt GenRate & 1\ldots$\infty$ & Aufruf-Rate des genetischen Algorithmus' \\ \hline \tt NCFRepl & 0\ldots {\tt SCFL} & Anzahl der zu ersetzenden {\sl Classifier} \\ \hline \tt ReplSelMode& -6\ldots 6 & {\sl Selection-Mode} beim Ersetzen der {\sl Classifier} \\ & & in abh. von {1/\sl Strength} \\ \hline \tt NCFMut & 0\ldots {\tt SCFL} & Anzahl der zu mutierenden {\sl Classifier} \\ \hline \tt NMutate & 0\ldots {\tt SStr} & Mutationen pro {\sl Condition / Action} \\ \hline \tt MutSelMode& -6\ldots 6 & {\sl Selection-Mode} beim Mutieren der {\sl Classifier} \\ & & in abh. von {1/\sl Strength} \\ \hline \tt CondSp & 0\ldots 100\% & Spezifizit„t der {\sl Condition bzw. Action}, d.h. \\ \cline{1-2} \tt ActSp & 0\ldots 100\% & Wahrscheinlichkeit einer nicht-\#-Stelle \\ \hline \tt NegCondP & 0\ldots 100\% & Wahrscheinlichkeit einer negativen {\sl Condition} \\ \hline \end{CFSParTab}\caption{{\tt Genetic}-Variablen}\end{table} \begin{table}\begin{CFSParTab} \tt DelMessMode & 0\ldots 2 & 0 = l”sche keine {\sl Messages}. \\ & & 1 = l”sche {\sl Messages} mit {\sl Effector-Tag}. \\ & & 2 = l”sche alle {\sl Messages} \\ \hline \end{CFSParTab}\caption{{\tt ReInit}-Variablen}\end{table} \begin{table}\begin{CFSParTab} \tt BidMode & 1\ldots 4 & 1 = ein {\sl Bid} pro {\sl Classifier} \\ & & 2 = ein {\sl Bid} pro {\sl Matching-Tupel} \\ & & 3 = Wie 1 -- nur: Aktionsliste statt Tupel-Liste \\ & & 4 = Wie 2 -- nur: ein {\sl Bid} pro Aktion \\ \hline \tt SuppMode & 1\ldots 2 & 1 = Z„hle die {\sl Intensity} bei {\sl BidTupels} \\ & & \qquad mit zwei gleichen {\sl Messages} nur einfach \\ & & 2 = Addiere die {\sl Intensity} beider {\sl Messages} \\ \hline\hline \tt BidTupSelMode & -6\ldots 6 & Mode zum Selektieren von Tupeln in {\tt MatchBid} \\ \hline \tt BidActSelMode & -6\ldots 6 & Mode zum Selektieren von Aktionen in {\tt MatchBid} \\ \hline \tt FireBidSelMode& -6\ldots 6 & Mode zum Selektieren von {\sl Bids} in {\tt Fire} \\ \hline \tt FireTupSelMode& -6\ldots 6 & Mode zum Selektieren von Tupeln in {\tt Fire} \\ \hline\hline \tt MBids & 1\ldots$\infty$ & Max. Anzahl von {\sl Bids} pro {\sl Classifier} \\ \hline \tt MAct & 1\ldots$\infty$ & Max. Anzahl von {\sl Actions} pro {\sl Classifier} \\ \hline \tt MFire & 1\ldots$\infty$ & Max. Anzahl von gefeuerten {\sl Messages} pro {\sl Classifier} \\ \hline\hline \tt RiskFak & 0\ldots 100\% & Berechnung des (effektiven) {\sl Bids} mittels: \\ \hline \tt SpecPow & 0\ldots 2 & \\ \cline{1-2} \tt RelSuppPow& 0\ldots 2 & \raisebox{1.5ex}[-1.5ex] {$ Bid=RiskFak\cdot Strength\cdot Spec^{SpecPow}\cdot RelSupp^{RelSuppPow} $} \\ \hline \tt EBidPow & 0\ldots 2 & \\ \cline{1-2} \tt ESpecPow & 0\ldots 2 & \raisebox{1.5ex}[-1.5ex] {$ EffBid=[Bid+Noise(Bid\cdot Dev2)]^{EBidPow}\cdot Spec^{ESpecPow} $} \\ \hline\hline & & Modes fr expliziten {\sl Bucket-Brigade} \\ \hline \tt ClaimMode & 1\ldots 2 & Mehrfache Verwendung einer {\sl Message} wird dem Sender \\ & & 1 = nur einfach, 2 = mehrfach vergtet. \\ \hline \tt DisMode & 1\ldots 2 & 1 = {\sl Credit} ist unabh„ngig von der {\sl Message-Intensity} \\ & & 2 = {\sl Credit} ist prop. zur {\sl Message-Intensity} \\ \hline \tt SumMode & 1\ldots 3 & 1 = Teil des {\sl Reinf.} bzw. {\sl Bids} geht verloren ({\tt NMFrac}) \\ & & 2 = {\sl Reinf.} bzw. {\sl Bid} wird restlos aufgeteilt \\ & & 3 = Jeder {\sl Classifier} bekommt vollen {\sl Reinf.} bzw {\sl Bid} \\ \hline \end{CFSParTab}\caption{{\sl Classifier/Effector}-Variablen}\end{table} \clearpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Erg„nzungen und Ausblicke } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Das Programm ist so konzipiert, daá es in vielerlei Hinsicht erweitert werden kann. Dies betrifft sowohl programmspezifische Erweiterungen, wie z.B. % \begin{itemize} \item Menu-Punkte, um Simulations-Status auf Diskette abzuspeichern und von Diskette zu laden. \item Compileroptionen (besonders um {\sl Compiler-Warnings} zu unterdrcken) mittels \verb|#pragma warn| $xyz$ ins Programm aufnehmen. \item Per Menu ein- und ausschaltbare {\sl Warnings}. \item Flexible Skalierung von FixPunkt-Zahlen. \item Untersttzung von \CFS-Aufrufen durch {\sl Batch}-Prozesse. \end{itemize} % als auch Erweiterungen des CFS selbst, wie z.B. % \begin{itemize} \item Profit-Sharing-Plan ({\tt CreditMode=2}). \item Erweiteter genetischer Algorithmus (Kreuzung, H„ufung, getriggerter GA,\ldots) \look\cite{Goldberg} (Wird bis Ende '91 zur Verfgung stehen). \item Tree \& Food Beispiel von Wilson \cite{Wilson} (und andere Beispiele). \end{itemize} % Eine Benutzerbeschreibung des Klassifizierungs-Systems findet sich in \cite{Weiss} Abschlieáend sei noch darauf hingewiesen, daá fr die Fehlerfreiheit dieses Programms -- natrlich -- keine Garantie bernommen werden kann. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Was tun im Fehlerfall ? } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Im Folgenden werden eine Reihe von Warnungen und Fehlern beschrieben, die evtl. beim Simulationslauf auftreten k”nnen und deren Ursache meist in fehlerhaften oder kritischen Benutzer-Variablen oder Benutzer-Funktionen liegt. \subsection{ Warnungen } % ========= Warnungen sind im Normallfall ebenso wie Fehlermeldungen vom Benutzer ernst zu nehmen und bei der n„chsten Gelegenheit zu beheben. Allerdings wird bei Warnungen, im Gegensatz zu Fehlermeldungen, die Simulation fortgesetzt (\look\ref{StStAus}). % \begin{description} \item{\tt Warning 0: Unspecific Warning} \\ Programmfehler: Benachrichtigen Sie den Programmierer. \item{\tt Warning 1: Division underflow} \\ {\it Bei der Division wird eine Zahl derart klein, daá sie in der FixPunkt-Darstellung zu Null wird} \\ Tritt diese Warnung h„ufiger auf, und sind generell die FixPunkt-Werte, die in Status und Statistik angezeigt werden recht klein (alle kleiner als 5), so sollten Sie versuchen, alle Benutzer-Parameter {\sl (Taxes, Reinf, \ldots)} neu zu skalieren, d.h. alle mit einer Konstanten zu multiplizieren, was ja nichts an der Funktionalit„t „ndert. \item{\tt Warning 2: QMax called with k=0} \\ {\it{\tt QMax} sollte die Null gr”áten Elemente suchen} \\ Programmfehler: Benachrichtigen Sie den Programmierer. \item{\tt Warning 3: ProbSel called with N=0} \\ {\it{\tt ProbSel} sollte aus Null Elementen $k>0$ ausw„hlen} \\ Programmfehler: Benachrichtigen Sie den Programmierer. \item{\tt Warning 4: Tupellist is full} \\ {\it In der Liste der Bidtupels ist kein Platz mehr fr weitere Eintragungen} \\ Dimensionieren Sie die Tupelliste mit {\tt STupL} so groá wie m”glich (es Ihre Speicherkapazit„t zul„át). Haben Sie trotz eines relativ kleinen Beispiels (wenig {\sl Classifier} und {\sl Messages}) und groáer Tupelliste Schwierigkeiten, so sollten Sie in Betracht ziehen, {\tt MBids} bzw. {\tt MAct} zu verkleinern. Eine bervolle Tupelliste kann auch Ursache zu unspezifischer {\sl Classifier-Conditions} sein. Ist dies der Fall, so sollten Sie {\tt CondSp} erh”hen. \item{\tt Warning 5: Bidlist is full} \\ {\it In der Liste der Bids ist kein Platz mehr fr weitere Eintragungen} \\ Dimensionieren Sie die Bidliste mit {\tt SBidL} so groá wie m”glich (es Ihre Speicherkapazit„t zul„át). Eine bervolle Tupelliste kann auch Ursache zu unspezifischer Classifier-Conditions sein. Ist dies der Fall, so sollten Sie {\tt CondSp} erh”hen. \item{\tt Warning 6: Selection of Zero-Values} \\ {\it Bei einem Selektionsvorgang wurden Elemente mit Bewertung {(\tt Val)} Null ausgew„hlt, die meist Ursache vorangegangener Unterl„ufe sind} \\ Beachten Sie die unter Warning 1 angegebenen Hinweise. \item{\tt Warning 7: BestSelMode must be positive} \\ {\it Die k besten Elemente mit Wiederholung zu selektieren macht keinen Sinn} \\ Ersetzen Sie $x${\tt SelMode=-3} durch $x${\tt SelMode=+3}. \item{\tt Warning 8: Too many matching tuples} \\ {\it Es gibt {\rm einen} Classifier, den zu viele Tupels matchen} \\ Beachten Sie die unter Warning 4 angegebenen Hinweise. \end{description} \subsection{ Fehlermeldungen } % =============== \begin{description} \item{\tt Error 0: Unspecific Error} \\ Programmfehler: Benachrichtigen Sie den Programmierer. \item{\tt Error 1: Multiplication Overflow} \\ {\it šberlauf beim Multiplizieren zweier FixPunkt-Zahlen} \\ Sie sollten versuchen alle Benutzer-Parameter ({\sl Taxes, Reinf, \ldots}) neu zu skalieren, d.h. alle durch eine Konstante zu dividieren, was ja nichts an der Funktionalit„t „ndert. \\ {\sl Fortsetzung kritisch -- System f„ngt sich aber meist nach einigen Runden} \item{\tt Error 2: Division Overflow} \\ {\it šberlauf beim Dividieren zweier FixPunkt-Zahlen} \\ Beachten Sie die Hinweise unter Error 1. \\ {\sl Fortsetzung kritisch -- System f„ngt sich aber meist nach einigen Runden} \item{\tt Error 3: Wrong Selection-Mode} \\ {\it $x${\tt SelMode} ist auf ungltige Werte gesetzt (erlaubt sind -6..6)} \\ {\sl Fortsetzung nicht sinnvoll} \item{\tt Error 4: Select more than possible} \\ {\it Es sollten mehr (verschiedene) Elemente selektiert werden als vorhanden sind} \\ Programmfehler: Benachrichtigen Sie den Programmierer. \item{\tt Error 5: Wrong User-Classifier/Message} \\ {\it Das Format der vordefinierten User-Classifier / Message-Strings ist falsch} \\ šberprfen Sie {\tt MessSL}, {\tt CFSL} und {\tt EffSL}. Vielleicht ist die in {\tt SStr} angegebene L„nge inkonsistent besetzt. \\ {\sl Fortsetzung nicht sinnvoll} \item{\tt Error 6: Couldn't allocate Memory} \\ {\it Fehler in der Speicherreservierung fr die verschiedenen Listen} \\ W„hlen Sie die mit \verb|#define S|$x$ definierten Listenl„ngen kleiner oder compilieren Sie mit dem Compiler-Modell {\tt Compact}, um mehr als 64 KByte fr die Listen zur Verfgung zu haben. \\ {\sl Fortsetzung katastrophal (Absturzgefahr)} \item{\tt Error 7: Wrong BidMode} \\ {\it {\tt BidMode} ist auf ungltige Werte gesetzt (erlaubt sind 1..4)} \\ {\sl Fortsetzung nicht sinnvoll} \item{\tt Error 8: Wrong Credit-Assign-Mode} \\ {\it {\tt CreditMode} ist auf ungltige Werte gesetzt (erlaubt sind 1,3 und 4)} \\ {\sl Fortsetzung nicht sinnvoll} \item{\tt Error 9: prf is called with {\tt prMode=0}} \\ {\it Es wurde versucht etwas anzuzeigen, obwohl {\tt prMode} auf 0 gesetzt ist} \\ Programmfehler: Benachrichtigen Sie den Programmierer. \end{description} \ifall \begin{appendix} \clearpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Programmlisting {\tt CFSSIM.C} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{listing} \begin{verbatim} /****************************************************************/ /* */ /* C l a s s i f i e r - S y s t e m - S i m u l a t o r */ /* */ /****************************************************************/ /* in Turbo-C 2.0 on IBM-AT */ /* Diplomarbeit: Copyright 1991 by Marcus Hutter */ /* Stand: 13.05.1991 */ /****************************************************************/ /****************************************************************/ /* R e m a r k s */ /**************************************************************** - It is assumed, that 'int' is 16-bit and 'long' is 32-bit signed. - Use Compact-Model (instead of Small), if your CFS-Example is so large, that you get Errors about 'too many dynamic Variables' (Mess,CF,..) and ignore warnings about loosing digits. - Set an Breakpoint in and compile the EXAMPLE.C-File; this file is included. ****************************************************************/ /* D e f i n i t i o n s */ /****************************************************************/ /*------------------------------*/ /* Include-Files */ /*------------------------------*/ #include #include #include #include #include #include #include #include /*------------------------------*/ /* Definitions */ /*------------------------------*/ #define then /**/ /* if then else */ #define ESC 27 /* define the escape key */ #define FALSE 0 /* FALSE for bool */ #define TRUE 1 /* TRUE for bool */ #define MaxInt 32767 /* Maximal signed integer */ #define FOREVER for(;;) /* infinite loop */ #define PSize sizeof(*) /* Pointer-Size */ #define NScrL 50 /* # of Screen-Lines 25/43/50 */ #define STDCOL YELLOW /* Standard Color */ #define MMask (TString)~(~(long)0<Id) /* first half of long */ #define Val(x) (((TIdVal*)&(x))->Val) /* second " of long */ typedef struct /* CF-Condition */ { TString C; /* String ------------ */ TString B; /* #-Mask */ TCType T; } /* Type */ TCond; typedef struct /* CF-Action */ { TString A; /* String --------- */ TString B; /* #-Mask */ TCType T; } /* Type */ TAct; typedef struct /* Classifier */ { TCond C1; /* Condition---------- */ ifTC( TCond C2; ) /* Condition 2 */ TAct Act; /* Action */ fixp Sp; /* Specifity of Cond1 (& Cond2) */ fixp S; /* Strength */ fixp Get; /* Reinf + Pay from others */ fixp Pay; /* Pay to others */ fixp Tax; /* Taxes */ fixp PSP; /* Bid-Sums over Reinf-Expisode */ int H; } /* Help-Value */ TCF; typedef struct /* CF-List */ { TCF *B; /* Begin ------- */ TCF *C; /* Current End */ TCF *E; /* End of List */ byte BidMode; byte SuppMode; sbyte BidTupSelMode; sbyte BidActSelMode; sbyte FireBidSelMode; sbyte FireTupSelMode; int MBids; int MAct; int MFire; fixp RiskFak; byte SpecPow; byte RelSuppPow; byte EBidPow; byte ESpecPow; byte ClaimMode; byte DisMode; byte SumMode; } TCFL; typedef struct /* Message */ { TString M; /* String ------- */ fixp I; /* Intensity */ TCFId CF; /* Id of sending CF */ int H; } /* Help-Value */ TMess; typedef struct /* Message-List */ { TMess *B; /* ------------ */ TMess *C; TMess *E; } TMessL; typedef struct /* Bid */ { TCFId CF; /* Bidding CF --- */ fixp BV; /* Bid-Value */ fixp EV; /* Effective-Bid-Value */ TTupId Tup; /* Matching-Tuples */ int N; /* Number of Bid-Tuples */ bool F; } /* Fired-Flag */ TBid; typedef struct /* Bid-List */ { TBid *B; /* -------- */ TBid *C; TBid *E; } TBidL; typedef struct /* MessTupel */ { TMessId M1; /* Message 1 --------- */ ifTC( TMessId M2; ) /* Message 2 */ fixp S; } /* Support */ TTup; typedef struct /* MessTupel-List */ { TTup *B; /* -------------- */ TTup *C; TTup *E; } TTupL; typedef struct /* Classifier-System */ { TMessL *MP; /* Mess ================= */ TMessL *NP; /* New-Mess */ TMessL *OP; /* Output-Mess (from Eff) */ TCFL *CP; /* Classifier */ TCFL *EP; /* Effectors */ TBidL *BP; /* Bids */ TBidL *DP; /* Eff-Bids (same list) */ TTupL *TP; /* MessTupel */ TTupL *UP; } /* Eff-MessTupel (same list) */ TCS; typedef struct /* Statistic */ { long CycleC; /* Cycle-Counter--------- */ long ReVal; /* ä of Reinf */ long Str; /* ä of CF-Stregnth */ long NCFMinStr; /* # of CF with MinStr */ long NCFMaxStr; /* # of CF with MaxStr */ long MCF; /* # of NonMatched CF */ long MMess; /* # of NonMatched Mess. */ long NCF; /* # of CF */ long NBid; /* # of Bids */ long NTup; /* # of Tupels */ long NMess; } /* # of Messages */ TStat; \end{verbatim} \begin{verbatim} /*------------------------------*/ /* Variables */ /*------------------------------*/ TMessL XM,XN,XO; TBidL XB,XD; extern TCFL XC,XE; TTupL XT,XU; TStat cy,ep; TCS XCS = { &XM,&XN,&XO,&XC,&XE,&XB,&XD,&XT,&XU }; TCS *o = &XCS; long CycleC; /* Main-Cycle-Step-Counter */ fixp ReVal; /* Reinforcement-Value */ TString DetMTagC,DetMTagB; /* Detector-Tags */ TString EffMTagC,EffMTagB; /* Effector-Tags */ TMess *GMB; /* Global-Mess-Pointer */ TString *GStr; /* Global Strting-Pointer */ jmp_buf jmp; /* jump-label */ FILE *devP,*lpt1; /* Output-Device */ bool ProtF; /* Protocoll is Off/On */ bool SStepF; /* Single-Step-Mode */ bool prM1F; /* printmode 1 - first flag */ bool SoundF = TRUE; /* Sound On / Off */ byte prMode = 3; /* Print-Mode 0=No ... 3=All */ /*------------------------------*/ /* Constants */ /*------------------------------*/ char FName[14] = "CFSSIM.C"; /* File-Name (not needed) */ char *ErrMess[] = /* Error-Messages */ { "Unspecific Error", "Mutliplication Overflow", "Division Overflow", "Wrong Selection-Mode", "Select more than possible", "Wrong User-Classifier/Message", "Couldn't allocate Memory", "Wrong BidMode", "Wrong Credit-Assign-Mode", "pprint is call with prMode=0" }; char *WarnMess[] = /* Warnning-Messages */ { "Unspecific Warning", "Division Underflow", "QMax called with k=0", "ProbSel called with N=0", "Tupellist is full", "Bidlist is full", "Selection of Zero-Values", "BestSelMode must be positive", "Too many matching tuples" }; #define NWarn (sizeof(WarnMess)/sizeof(char*)) int WC[NWarn]; int WP[NWarn]; /*------------------------------*/ /* Test-Variables */ /*------------------------------*/ /*------------------------------*/ /* Externals */ /*------------------------------*/ /* Example-Specific variables and functions */ /* For explanation refer to Example1/2/... */ extern int StRate,DetRate,EffRate,ReRate,GenRate; extern int MDetM,MEqMess,NMutate,NCFMut,NCFRepl; extern fixp DefNMI,SclSel,DefDetMI,DefStr,DefStrDev; extern fixp Dev1,Dev2,NMFrac,DetFrac,HeadTax,MessTax,BidTax; extern fixp MaxStr,MinStr,CondSp,ActSp,NegCondP,PSPFrac; extern byte NMIMode,CreditMode,BidTaxMode,PSPDisMode; extern byte DelMessMode; extern sbyte DelMessSelMode,MutSelMode,ReplSelMode; extern bool CleanHallF,MultBidTaxF,MultMessTaxF; extern char DetMessTag[],EffMessTag[],ProtDev[]; extern char *CFSL[],*EffSL[]; extern InitEnv(),Detect(TMessL*,int),Effect(TMessL*); extern Display(); extern fixp Reinf(); /*------------------------------*/ /* Forward Declarations */ /*------------------------------*/ extern Menu(); extern main(); extern char event(); \end{verbatim} \begin{verbatim} /****************************************************************/ /* G e n e r a l P r o c e d u r e s */ /****************************************************************/ #define Sound(h,l) \ { if (SoundF) { sound(h); delay(l); nosound(); } } /*------------------------------*/ prf(int Col,char*fmt,...) /* printf to dev & devP */ /*------------------------------*/ { char str[999]; extern Error(int); if (Col!=0) then textcolor(Col); if (prMode>0) then { vsprintf(str,fmt,...); cprintf(str); if (ProtF) then fprintf(devP,str); } else Error(9); if (Col!=0) then textcolor(STDCOL); } /*------------------------------*/ Error(n) /* break with Error # 10+n */ /*------------------------------*/ { prMode++; textbackground(LIGHTRED); prf(WHITE,"Error #%d: %s\r\n",10+n,ErrMess[n]); textbackground(BLACK); clreol(); textbackground(LIGHTRED); prf(WHITE,"Press any Menu-Key, but its risky to continue !!\r\n"); textbackground(BLACK); clreol(); prMode--; Sound(500,100); Menu(); } /*------------------------------*/ Warning(n) /* write Warning # n */ /*------------------------------*/ { WC[n]++; if (WC[n]%((WP[n]>>2)+1)==0) /* /4 = Warning decay-Rate */ { if (prMode>0) then prf(LIGHTGRAY, "%d.Warning #%d: %s\r\n",WC[n],20+n,WarnMess[n]); WP[n]+=1+(WP[n]>>1); Sound(1000,5); } } /* Random-Number between 0 and n-1 */ #define random2(n) ((int)(((long)rand()*n)>>15)) /* TRUE with Prob. p (p is fixp. !) */ #define flip(p) ((p)>(rand()>>7)) /*------------------------------*/ char* ActTime() /* Actual Time in String */ /*------------------------------*/ { char *s; time_t t; /* Actual Time */ time(&t); s=ctime(&t); s[strlen(s)-1]='\0'; return(s); } /*------------------------------*/ memswap(P,Q,n) /* swap n Bytes from P and Q */ /*------------------------------*/ char *P,*Q; { char h,*E=P+n; while(P>8) #define FPDiv(x,y) (fixp)(((long)(x)<<8)/(y)) #else /*------------------------------*/ fixp FPMult2(x,y) /* Fix-Point-Mult with Test */ /*------------------------------*/ long x,y; { long h=(x*y)>>8; if ((h>0?h:-h)>MaxInt) then Error(1); return((fixp)h); } /*------------------------------*/ fixp FPDiv2(x,y) /* Fix-Point-Division with Test */ /*------------------------------*/ long x,y; { long h=(x<<8)/y; if ((h>0?h:-h)>MaxInt) then Error(2); if (x!=0&&h==0) then Warning(1); return((fixp)h); } /* secure Fix-Point-Operations */ #define FPMult(x,y) FPMult2((long)(x),(long)(y)) #define FPDiv(x,y) FPDiv2((long)(x),(long)(y)) #endif /*------------------------------*/ fixp FPPow(y,x,n) /* Fix-Point-Pow y*x^n */ /*------------------------------*/ fixp y,x; byte n; { int i; for(i=0; i>=1; } return(Dev*(c-(s=15-s)) >> 1); } else return(0); } /* Order-Functions must be Reflexive, that means InOrder(x,x) ! */ /*------------------------------*/ bool InStdOrd(x,y) /* Standard-Order-Function */ /*------------------------------*/ TIdVal x,y; { return(x.Val<=y.Val); } /*------------------------------*/ bool InMessOrder(x,y) /* Mess-Order-Function */ /*------------------------------*/ TIdVal x,y; { return(GMB[x.Id].M<=GMB[y.Id].M); } /*------------------------------*/ bool InStrOrder(x,y) /* String-Order-Function */ /*------------------------------*/ TIdVal x,y; { return(GStr[x.Id]<=GStr[y.Id]); } /*------------------------------*/ byte Count1s(s) /* Count # of 1 Bits */ /*------------------------------*/ TString s; { byte c=0; while(s) { if (s&1) then c++; s>>=1; } return(c); } \end{verbatim}% \begin{verbatim} /*------------------------------*/ Shuffle(A,N) /* Shuffle N El. of A */ /*------------------------------*/ long A[]; int N; { index m; long h; while(N>1) { m=random2(N); h=A[m]; A[m]=A[--N]; A[N]=h; } } /*------------------------------*/ #define QDivide() /* Used in QMax and QSort */ \ /*------------------------------*/ \ { d=*M; \ while(BM) then { B=B2; C2=C; } else break; } } /*------------------------------*/ QSort(B2,C2,InOrder) /* Sort A In-Order */ /*------------------------------*/ long *B2; /* Begin of Index-Array */ long *C2; /* End of Index-Array (B2+#El-1)*/ bool InOrder(long,long); /* Order-Criterium */ { long *B,*C; /* Actual Begin & End -Pointer */ long *M,d; /* Div.-Point & -Element of A */ long h; /* help-variable for exchange */ if (B2>1); QDivide(); QSort(B2,B,InOrder); QSort(C,C2,InOrder); } } /* TIdVal and long are used as synonyms */ /*------------------------------*/ int MaxVal(A,N) /* Maximal Value of A */ /*------------------------------*/ TIdVal A[]; /* Elements */ int N; /* Number of Elements */ { int i; int m=A[0].Val; for(i=1; im) then m=A[i].Val; } #define AL ((long*)A) /* long synonym for A */ \end{verbatim} \begin{verbatim} /*------------------------------*/ ProbSelInit(A,N) /* Init Probability-Selection */ /*------------------------------*/ TIdVal A[]; /* Elements */ int N; /* Number of Elements */ { index i,k; fixp m=MaxVal(A,N); if (m<8000 && m) then { m=16000/m; for(i=0; i>=1; } } /*------------------------------*/ index ProbSel(A,N) /* Probability-Selection */ /*------------------------------*/ TIdVal A[]; /* Elements */ int N; /* Number of Elements */ { index i,k=0; TIdVal z; z.Id=rand()<<1; z.Val=random2(A[0].Val); for(i=1; i>=1; i!=0; i>>=1) { *(long*)&z<<=1; if (i+k>=1; } p-=A[k].Val; for(; i>=1; } A[0].Val+=p; } /*------------------------------*/ ProbSelInit2(A,N) /* Init Probability-Selection */ /*------------------------------*/ TIdVal A[]; /* Elements */ int N; /* Number of Elements */ { index i,m=0; long h; if (N==0) then Warning(3); for(i=1; iA[m].Val) then m=i; h=AL[m]; AL[m]=AL[0]; AL[0]=h; } /*------------------------------*/ index ProbSel2(A,N) /* Probability-Selection */ /*------------------------------*/ TIdVal A[]; /* Elements */ int N; /* Number of Elements */ { index k; while(random2(A[0].Val)>=A[k=random2(N)].Val); return(k); } /*------------------------------*/ MultSelInit(A,N,Mode) /* Init Selection (for k<0) */ /*------------------------------*/ TIdVal A[]; /* Elements & Values */ int N; /* Number of Elements */ sbyte Mode; /* Selection-Mode */ { switch(abs(Mode)) { case 1: break; case 2: ProbSelInit(A,N); break; case 3: QSort(A,A+N-1,InStdOrd); break; case 4: break; case 5: break; case 6: ProbSelInit2(A,N); break; default:Error(3); } } \end{verbatim} \begin{verbatim} /*------------------------------*/ Select(A,NP,B,k,Mode) /* Select k of N Elements */ /*------------------------------*/ TIdVal A[]; /* Elements & Values */ int *NP; /* Number of Elements */ index B[]; /* Selected k Elements */ int k; /* Selection-Mode */ sbyte Mode; /* >0:different; <0:with repeat */ { index i,h,m,m2; int an; int N=*NP; bool once=(k>0); /* treat special cases */ k=abs(k); if (k==0) then return; if (k>N && (Mode>0 || N==0)) then { Error(4); Mode=-Mode; } if (k==N && Mode>0) then Mode=1; #if !SpeedF /* Test slows down execution */ for(i=h=0; i0?--N:0].Id; break; case 2: /* Probability-Selection */ if (once) then ProbSelInit(A,N); for(i=0; i0 && N>1) then { an=A[N-1].Val; for(h=N-1; !(h&1); h>>=1) an<<=1; ProbChg(A,N,m,an); ProbChg(A,N,N-1,0); A[m].Id=A[--N].Id; if (!(N&N-1)) then A[0].Val<<=1; } } N=*NP-k; break; case 3: /* Best-Selection (Different) */ if (Mode<0) then Warning(7); if (once) then QMax(A,N,k,InStdOrd); for(i=0; iA[m2].Val)^flip(SclSel)) then m=m2; B[i]=A[m].Id; if (Mode>0) then AL[m]=AL[--N]; } break; case 5: /* Random-Selection */ for(i=0; i0) then AL[m]=AL[--N]; } break; case 6: /* Prob2-Selection (simple vers) */ if (once) then m=0; else m=1; for(i=0; i0) then AL[m]=AL[--N]; } break; default: Error(3); } *NP=N; } #define pprFlag(F,S) \ prf(LIGHTMAGENTA,"%s %s\r\n",S,((F)==TRUE)?"ON":"OFF") #define SetSStep(F) pprFlag(SStepF=(F),"SingleStep") #define SetSound(F) pprFlag(SoundF=(F),"Sound") /*------------------------------*/ SetProt(F) /* Toggle Protocoll On/Off */ /*------------------------------*/ bool F; { if (F) then devP=fopen(ProtDev,"ab"); else fclose(devP); pprFlag(ProtF=F,"Protocoll"); } /*------------------------------*/ SetprMode(n) /* Set Print-Mode to 0,1,2 or 3 */ /*------------------------------*/ int n; { prM1F= (n==1||n==2); prf(LIGHTMAGENTA,"PrintMode = %d\r\n",prMode=n); } \end{verbatim} \begin{verbatim} /****************************************************************/ /* C F S - B a s i c - P r o c e d u r e s */ /****************************************************************/ /* Bits 0 to SStr-1 of M define 0 and 1 positions */ /* Corresponding Bits in C and B define CF-Cond/Action pos. */ /* (0,1)=0, (1,1)=1, (0,1)=(0,0)=# */ /* Does Message M match Condition (C,B) ? */ #define MatchMC(M,C,B) !((M^C)&B) /* for doc. look further */ /* Match Message M with Action (A,B) to result */ #define MatchMA(M,A,B) ((A&B)|(M&~B)) /*------------------------------*/ CalcSpec(C) /* Calculate Specifity */ /*------------------------------*/ TCF *C; { fixp Sp1,Sp2; Sp1=Count1s((long)C->C1.B); if (!(C->C1.T&2)) then Sp1=SStr-Sp1; ifnTC( C->Sp=FPDiv(Sp1,SStr); ) ifTC( Sp2=Count1s((long)C->C2.B); if (!(C->C2.T&2)) then Sp2=SStr-Sp2; C->Sp=FPDiv(Sp1+Sp2,SStr<<1); ) } #define CrSumM(n) M=MP->B+n; \ if (M->H>0 || ModeP->ClaimMode==2) then \ { M->H=-abs(M->H); /* Visited */ \ R= ModeP->SumMode==1 ? FixP(1) : -M->H; \ Sum+= ModeP->DisMode==1 ? R : FPMult(R,M->I); } /*------------------------------*/ long CrSum(TS,N,MP,ModeP) /* Calculate Credit-Sum */ /*------------------------------*/ TTup *TS; /* Start of Tupellist */ int N; /* # of Tupels to Check */ TMessL *MP; TCFL *ModeP; { TMess *M; TTup *T; fixp R; long Sum=0; if (ModeP->SumMode==3) then return(FixP(1)); for(T=TS; TM1); ifTC( CrSumM(T->M2); ) } return(Sum); } #define DistrM(n) M=MP->B+n; \ if (M->H<0 || ModeP->ClaimMode==2) then \ { M->H=abs(M->H); /* Visited */ \ R= FPMult(M->H,Val); \ R= ModeP->DisMode==1 ? R : FPMult(R,M->I); \ Sum+=R; CP->B[M->CF].Get+=R; } /*------------------------------*/ Distr(TS,N,MP,ModeP,CP,Val) /* Distribute Val. to CF */ /*------------------------------*/ TTup *TS; /* Start of Tupellist */ int N; /* # of Tupels to Check */ TMessL *MP; TCFL *ModeP,*CP; fixp Val; { TMess *M; TTup *T; fixp R,Sum=FixP(0); for(T=TS; TM1); ifTC( DistrM(T->M2); ) } return(Sum); } /*------------------------------*/ SetMFrac(MP) /* Set Mess.-Credit-Fraction */ /*------------------------------*/ TMessL *MP; { TMess *M; MP->B[-1].H=NMFrac; for(M=MP->B; MC; M++) M->H= (M->CF==DetId) ? DetFrac : FixP(1); } /*------------------------------*/ TString RandStr(p) /* Create Random-String */ /*------------------------------*/ fixp p; /* p/256 = Prob. for a 1-Bit */ { TString s=1; while(!(s&~MMask)) { s<<=1; if flip(p) then s|=1; } return(s&MMask); } /*------------------------------*/ RandMess(M) /* Create Random-Message */ /*------------------------------*/ TMess *M; { M->M=RandStr(FixP(0.5)); M->I=DefNMI; M->CF=NonId; } /*------------------------------*/ RandCF(C) /* Create Random-Classifier */ /*------------------------------*/ TCF *C; /* Pointer to CF */ { C->C1.T=flip(NegCondP) ? 4 : 6 ; C->C1.B=RandStr(CondSp); C->C1.C= C->C1.B & RandStr(FixP(0.5)); ifTC( C->C2.T=flip(NegCondP) ? 4 : 6 ; C->C2.B=RandStr(CondSp); C->C2.C= C->C2.B & RandStr(FixP(0.5)); ) C->Act.B=RandStr(ActSp); C->Act.A= C->Act.B & RandStr(FixP(0.5)); C->S=DefStr+Noise(FPMult(DefStr,DefStrDev)); C->Sp=CalcSpec(C); C->Get=C->Pay=C->Tax=C->PSP=FixP(0); } /*------------------------------*/ MutateCA(CP,BP,Sp) /* Mutate Cond/Act */ /*------------------------------*/ TString *CP,*BP; /* (*CP,*BP)= Cond/Act */ fixp Sp; /* Mean Specifity = 1- #Prob. */ { TString m; m=1<C1.T=4+'-'-*S++; S=StoCB(S,&C->C1.C,&C->C1.B); ifTC( C->C2.T=4+'-'-*S++; S=StoCB(S,&C->C2.C,&C->C2.B); ) S++; C->S=Str+Noise(FPMult(Str,Dev)); C->Sp=CalcSpec(C); S=StoCB(S,&C->Act.A,&C->Act.B); C->Get=C->Pay=C->Tax=C->PSP=FixP(0); if (*S) then Error(5); } /*------------------------------*/ StoM(S,MP) /* CharString to MessageString */ /*------------------------------*/ char *S; /* String like "010011" */ TMess *MP; { TString B; StoCB(S,&MP->M,&B); if (MMask^B) then Error(5); MP->CF=DetId; MP->I=DefDetMI; } /*------------------------------*/ char *CBtoS(C,B) /* Condition to CharString */ /*------------------------------*/ TString C,B; { static char S[SStr+1]; int i; S[SStr]=0; for(i=SStr-1; i>=0; i--) { S[i]= (B&1) ? (C&1?'1':'0') : (C&1?'*':'#'); B>>=1; C>>=1; } return(S); } /*------------------------------*/ pprInfo() /* Printf Help-Information */ /*------------------------------*/ { prf(LIGHTCYAN,"%s\r\n%s\r\n", "Press one of the upcase letters in Menu-Field ...", "For more information refer to documentation "); } /*------------------------------*/ pprCFL(CP) /* pprint Classifier-List */ /*------------------------------*/ TCFL *CP; { TCF *C; int i=0; prf(LIGHTGREEN, "CFId Str Get Pay Taxes Condion/Action\r\n"); for(C=CP->B; CC; C++) { prf(0,"%3d:%6.2f %6.2f %6.2f %6.2f %c%s", i++,C->S/256.0,C->Get/256.0,C->Pay/256.0,C->Tax/256.0, '-'-(C->C1.T&2),CBtoS(C->C1.C,C->C1.B)); ifTC( prf(0,"%c%s",'-'-(C->C2.T&2),CBtoS(C->C2.C,C->C2.B)); ) prf(0,"/%s\r\n",CBtoS(C->Act.A,C->Act.B)); } } /*------------------------------*/ pprMessL(MP) /* pprint Message-List */ /*------------------------------*/ TMessL *MP; { TMess *M; int i=0; prf(LIGHTGREEN,"MId Intens Sender Message\r\n"); for(M=MP->B; MC; M++) { prf(0,"%3d:%6.2f ",i++,M->I/256.0); if (M->CF==DetId) then prf(0," D "); else prf(0,"%3d ",M->CF); prf(0,"%s\r\n",CBtoS(M->M,MMask)); } } /*------------------------------*/ pprBidL(BP,TP) /* pprint Bid-List */ /*------------------------------*/ TBidL *BP; TTupL *TP; { TBid *B; TTup *T,*TS; int i=0; prf(LIGHTGREEN, "BidId CFId Bid EBid Fired BidTupel\r\n"); for(B=BP->B; BC; B++) { prf(0,"%3d: %3d %6.2f %6.2f %c {", i,B->CF,B->BV/256.0,B->EV/256.0,B->F?'F':'-'); for(T=TS=TP->B+B->Tup; TN; T++) { if (T->M1==NonId) then prf(0," N"); else prf(0," %d",T->M1); ifTC( if (T->M2==NonId) then prf(0,":N"); else prf(0,":%d",T->M2); ) } prf(0," }\r\n"); i++; } } /*------------------------------*/ pprCS(prMode,o) /* pprint whole CFS */ /*------------------------------*/ TCS *o; { extern pprStat(int,TStat*); Display(); switch(prMode) { case 3: prf(WHITE, "-------------- Cycle %ld --------------\r\n",CycleC); prf(LIGHTGREEN,"\r\nMessage-List:\r\n"); pprMessL(o->MP); prf(LIGHTGREEN,"\r\nClassifier-List:\r\n"); pprCFL(o->CP); prf(LIGHTGREEN,"\r\nBid-List:\r\n"); pprBidL(o->BP,o->TP); prf(LIGHTGREEN,"\r\nNew-Message-List:\r\n"); pprMessL(o->NP); if (CycleC%EffRate==0) then { prf(LIGHTGREEN,"\r\nEffector-List:\r\n"); pprCFL(o->EP); prf(LIGHTGREEN,"\r\nEff-Bid-List:\r\n"); pprBidL(o->DP,o->UP); prf(LIGHTGREEN,"\r\nOutput-Message-List:\r\n"); pprMessL(o->OP); } prf(0,"\r\n"); prM1F=TRUE; case 2: pprStat(1,&cy); break; } } /*------------------------------*/ pprStat(prMode,epp) /* Print Statistic */ /*------------------------------*/ int prMode; TStat *epp; { int n = (int)max(epp->CycleC,1); float ReVal = epp->ReVal/(256.0*n); float Str = epp->Str/(256.0*n*(o->CP->C-o->CP->B)); int NCFMinStr = (int)(epp->NCFMinStr/n); int NCFMaxStr = (int)(epp->NCFMaxStr/n); int MCF = (int)(epp->MCF/n); int MMess = (int)(epp->MMess/n); int NCF = (int)(epp->NCF/n); int NBid = (int)(epp->NBid/n); int NTup = (int)(epp->NTup/n); int NMess = (int)(epp->NMess/n); switch(prMode) { case 2: pprCS(3,o); /* no break; */ case 3: prf(LIGHTGREEN, "\r\n Statistic (Mean-Values) of Cycle %ld-%ld:\r\n", CycleC-n+1,CycleC); prf(0," External Reinforcement : %.3f\r\n",ReVal); prf(0," mean CF-Strength : %.3f\r\n",Str); prf(0," min/maximal Strength CF : %d/%d\r\n", NCFMinStr,NCFMaxStr); prf(0," (matched) Messages : (%d) %d\r\n",MMess,NMess); prf(0," (matched) Classifers : (%d) %d\r\n",MCF,NCF); prf(0," Bids (-Tupels) : %d (%d)\r\n",NBid,NTup); prf(0,"\r\n"); prM1F=TRUE; break; case 1: if (prM1F) then { prf(LIGHTGREEN,"%s\r\n%s\r\n", "Cycle-Cycle Reinf Strength Min Max Mch Mch Bid Tup", " Value Str Str CF Mess 's els"); prM1F=FALSE; } prf(0,"%5ld-%-5ld:%7.3f %7.3f %3d %3d %3d %3d %3d %3d\r\n", CycleC-n+1,CycleC,ReVal,Str,NCFMinStr, NCFMaxStr,MCF,MMess,NBid,NTup); break; case 0: break; default: Error(8); } } \end{verbatim} \begin{verbatim} /****************************************************************/ /* C F S - H i g h - P r o c e d u r e s */ /****************************************************************/ /* Support of Tupel (m1,m2) (used by MatchBid) */ #define TupSupp1(m1,m2) m1.Val \ ifTC(+ ((m1.Id==m2.Id && CP->SuppMode==1) ? 0 : m2.Val) ) /* Support of Tupel (m1,m2) (used by Fire) */ #define TupSupp2(m1,m2) (MP->B[m1].I \ ifTC(+ ((m1==m2 && CP->SuppMode==1) ? 0 : MP->B[m2].I) ) ) /*------------------------------*/ MatchBid(CP,MP,BP,TP) /* Create BidList */ /*------------------------------*/ TCFL *CP; TMessL *MP; TBidL *BP; TTupL *TP; { TMess *M; TIdVal M1[SMessL]; ifTC( TIdVal M2[SMessL]; TIdVal MM[SMessL+1]; long s1; long s2; ) TIdVal F[STupL]; index G[STupL]; int H[STupL]; /* Copy of A[].Val */ TString Str[SMessL]; TString as; int n1,n2=1,nn; TCF *C; int h,i,k,k2,N; bool mf; /* Matching Flag */ long s,ss=0; /* Support */ TBid *B,*BPB=BP->C; /* relevant beginning for this */ for(M=MP->B; MC; M++) M->H=FALSE; /* H=Matched */ for(C=CP->B; CC; C++) /* for all CF do *//*** Match CF ***/ { n1=0; ifTC( n2=nn=0; ) for(i=0; iC-MP->B; i++) /* for all Mess do */ { mf=FALSE; if (MatchMC(MP->B[i].M,C->C1.C,C->C1.B)) then { M1[n1].Id=i; M1[n1++].Val=MP->B[i].I; mf=TRUE; } ifTC( if (MatchMC(MP->B[i].M,C->C2.C,C->C2.B)) then { M2[n2].Id=i; M2[n2++].Val=MP->B[i].I; mf=TRUE; } if (mf) then { MM[nn].Id=i; MM[nn++].Val=MP->B[i].I; MP->B[i].H=TRUE; } ) } if (!(C->C1.T&2)) then { if (n1) then n1=0; else { M1[n1].Id=NonId; M1[n1++].Val=DefNMI; ifTC( MM[nn].Id=NonId; M1[nn++].Val=DefNMI; ) } } ifTC( if (!(C->C2.T&2)) then { if (n2) then n2=0; else { M2[n2].Id=NonId; M2[n2++].Val=DefNMI; if (MM[nn].Id!=NonId) then MM[nn].Id=NonId; MM[nn++].Val=DefNMI; } } ) if (n1&&n2) then { cy.MCF++; /* for Statistic */ if (CP->BidMode>2) then { for(i=0; iB[M1[i].Id].M,C->Act.A,C->Act.B); GStr=Str; QSort(M1,M1+n1-1,InStrOrder); for(i=k=0; iM1[h].Val) then h=i; } M1[k].Id=M1[h].Id; M1[k].Val=(int)min(s,MaxInt); } n1=k; ifTC( for(s=h=i=0; iM2[h].Val) then h=i; } M2[0].Id=M2[h].Id; M2[0].Val=(int)min(s,MaxInt); n2=1; ) } /*** Bid CF ***/ switch(CP->BidMode) { case 1: case 3: /* BidMode = 1 */ if (BP->C>=BP->E) then { Warning(5); goto Full; } BP->C->CF=C-CP->B; ifTC( if (CP->SuppMode==1) then /* SuppMode = 1 / 2 */ { for(s=i=0; iC->BV=s; /* Supp in .BV & .EV */ ss+=s; BP->C->N=n1*n2; /* Est-Calc will follow */ BP->C->Tup=TP->C-TP->B; for(i=0; iC>=TP->E) then { Warning(4); goto Full; } TP->C->M1=M1[i].Id; ifTC( TP->C->M2=M2[k].Id; ) TP->C++; } BP->C->F=FALSE; BP->C++; break; case 2: case 4: /* BidMode = 2 */ for(i=h=0; iSTupL) then { Warning(8); break; } } k=min(CP->MBids,h); if (k>(k2=TP->E-TP->C)) then { k=k2; Warning(4); } if (k>(k2=BP->E-BP->C)) then { k=k2; Warning(5); } Select(F,&h,G,k,CP->BidTupSelMode); /* normally h=n1*n2 */ for(h=0; hC->CF=C-CP->B; BP->C->BV=H[G[h]]; BP->C->N=1; BP->C->Tup=TP->C-TP->B; BP->C->F=FALSE; TP->C->M1=M1[G[h]/n2].Id; ifTC( TP->C->M2=M2[G[h]%n2].Id; ) BP->C++; TP->C++; } break; default: Error(7); } } } Full:; for(M=MP->B; MC; M++) /* matching statistic */ if (M->H) then cy.MMess++; /*** Calc BidVal ***/ for(B=BPB; BC; B++) /* for all Bids do */ { if (CP->BidMode==1) then /* BV is Supp */ B->BV=FPDiv(*(long*)&B->BV,ss); /* BV is RelSupp / Est */ C=CP->B+B->CF; B->BV=FPMult(FPPow(CP->RiskFak,B->BV,CP->RelSuppPow), FPPow(C->S,C->Sp,CP->SpecPow));/* BV is BidValue */ B->EV=B->BV+Noise(FPMult(B->BV,Dev2)); /* EV=BV+Noise */ B->EV=FPMult(FPPow(FixP(1),B->EV,CP->EBidPow), FPPow(FixP(1),C->Sp,CP->ESpecPow));/* Eff-Bid */ } } \end{verbatim} \begin{verbatim} /*------------------------------*/ Fire(CP,MP,BP,TP,NP) /* Fire Messages */ /*------------------------------*/ TCFL *CP; TMessL *MP; TBidL *BP; TTupL *TP; TMessL *NP; { TIdVal FB[SBidL],FT[STupL]; index S,GT[STupL]; int i,k,NT; TCF *C; TBid *B; TTup *T; int N=BP->C-BP->B; bool Stop=FALSE; int r=NP->E-NP->C; for(C=CP->B; CC; C++) C->H=CP->MFire; /* Fire-Counter */ for(i=0; iB[i].EV; } MultSelInit(FB,N,CP->FireBidSelMode); while(r>0 && N!=0) { Select(FB,&N,&S,-1,CP->FireBidSelMode); /* -1 = multiple sel*/ B=BP->B+S; C=CP->B+B->CF; NT=B->N; T=TP->B+B->Tup; k=min(NT,min(r,C->H)); if (k>0) then { for(i=0; iTup+i; FT[i].Val=TupSupp2(T->M1,T->M2); } Select(FT,&NT,GT,k,CP->FireTupSelMode); for(i=0; iC->M=MatchMA(MP->B[TP->B[GT[i]].M1].M, C->Act.A,C->Act.B); NP->C->I=B->BV; NP->C->CF=B->CF; NP->C++; } C->H-=k; r-=k; B->F=TRUE; } } } /*------------------------------*/ Clean(MP) /* Clean Message-List */ /*------------------------------*/ TMessL *MP; /* MessList to Clean MP --> MP */ { TMess H[SMessL],*HC=H; /* should and will be empty */ TIdVal F[SMessL+1],*F1=F; index G[SMessL]; int i; TString as; TMess *M; int N=MP->C-MP->B; TIdVal *F2,*FE=F+N; if (N>=MEqMess) then { GMB=MP->B; for(i=0; iId].M; for(F2=F1+1; F2Id].M==as; F2++); N=F2-F1; if (N>MEqMess) then { Select(F1,&N,G,MEqMess,DelMessSelMode); for(i=0; iId,sizeof(TMess)); } memcpy(MP->B,H,(HC-H)*sizeof(TMess)); MP->C=GMB+(HC-H); } if (CleanHallF) then { for(M=MP->B; MC;) if (MatchMC(M->M,DetMTagC,DetMTagB)) then memcpy(M,--MP->C,sizeof(TMess)); else M++; } } /*------------------------------*/ Credit(CP,EP,MP,NP,BP,DP,TP,UP) /* Credit-Assignment */ /*------------------------------*/ TCFL *CP,*EP; TMessL *MP,*NP; TBidL *BP,*DP; TTupL *TP,*UP; { index BidN; fixp Val; long Sum; TCF *C; TMess *M; TBid *B; switch(CreditMode) { case 1: /* Explicit Bucket-Brigade */ for(C=CP->B-1; CC; C++) /* Test */ C->Get=C->Pay=FixP(0); /* Set .H = +-Rate, - = Visited */ SetMFrac(NP); SetMFrac(MP); /* Distribute Reinforcement */ Sum=0; for(B=DP->B; BC; B++) if (B->F) Sum+=CrSum(UP->B+B->Tup,B->N,NP,EP); if (Sum) then { Val=FPDiv(ReVal,Sum); for(B=DP->B; BC; B++) if (B->F) Distr(UP->B+B->Tup,B->N,NP,EP,CP,Val); } /* Distribute Bids */ for(B=BP->B; BC; B++) if (B->F) then if (B->N) then { Sum=CrSum(TP->B+B->Tup,B->N,MP,CP); if (Sum) then { Val=FPDiv(B->BV,Sum); CP->B[B->CF].Pay=Distr(TP->B+B->Tup,B->N,MP,CP,CP,Val); } } break; case 2: Error(8); break; /* Implicit Bucket-Brigade */ case 3: /* Profit Sharing Plan */ for(B=BP->B; BC; B++) if (B->F) then { C=CP->B+B->CF; Val= (PSPDisMode<3) ? FixP(1) : B->BV; if (PSPDisMode&1) then C->PSP=max(C->PSP,Val); else if ((FixP(127)-C->PSP)PSP=FixP(127); else C->PSP+=Val; } if (CycleC%ReRate==0) then for(C=CP->B; CC; C++) if (C->PSP) then { C->Pay=FPMult(PSPFrac,C->PSP); C->Get=FPMult(PSPFrac,ReVal); C->PSP=FixP(0); } else { C->Pay=C->Get=0; } break; case 4: /* no Credit-Asignment */ default: Error(8); /* No Credit Assignment */} } \end{verbatim} \begin{verbatim} /*------------------------------*/ Taxes(CP,NP,BP) /* Tax-Payment */ /*------------------------------*/ TCFL *CP; TMessL *NP; TBidL *BP; { TCF *C; TMess *M; TBid *B; for(C=CP->B-1; CC; C++) { C->Tax=HeadTax; C->H=0; } for(M=NP->B; MC; M++) { C=CP->B+M->CF; if (!C->H || MultMessTaxF) then { C->Tax+=MessTax; C->H=1; } } for(B=BP->B; BC; B++) { C=CP->B+B->CF; if ((!(C->H&2) || MultBidTaxF) && (!(C->H&1) || BidTaxMode==1)) then { C->Tax+=BidTax; C->H|=2; } } for(C=CP->B; CC; C++) C->Tax=FPMult(C->S,C->Tax); } /*------------------------------*/ StrUpDate(CP) /* Strength-Update (Test !!) */ /*------------------------------*/ TCFL *CP; { TCF *C; for(C=CP->B; CC; C++) C->S=max(MinStr,min(MaxStr, C->S+C->Get-C->Pay-C->Tax)); } /*------------------------------*/ Genetic(CP) /* Genetic Operations */ /*------------------------------*/ TCFL *CP; { TIdVal F[SCFL]; index G[SCFL]; TCF *C; int i,k; int N=CP->C-CP->B; if (prMode>1) then prf(LIGHTBLUE, "%ld.genetic algorithm envocation\r\n",CycleC/GenRate); /* Replace CF (and Sender in MessL, not impl.) */ for(i=0; iB[i].S ? FPDiv(FixP(0.49),CP->B[i].S) : FixP(127); } Select(F,&N,G,NCFRepl,ReplSelMode); for(i=0; iB+G[i]); /* Mutate CF */ for(i=0; iB[i].S ? FPDiv(FixP(0.5),CP->B[i].S) : FixP(127); } Select(F,&N,G,NCFMut,MutSelMode); for(i=0; iB+G[i]; for(k=0; kC1.C,&C->C1.B,CondSp); ifTC( MutateCA(&C->C2.C,&C->C2.B,CondSp); ) MutateCA(&C->Act.A,&C->Act.B,ActSp); } } } /*------------------------------*/ ReInit(o) /* Re-Initialize */ /*------------------------------*/ TCS *o; { TMessL *h; TMess *M; memswap(o->MP,o->NP,sizeof(TMessL)); o->NP->C=o->NP->B; o->OP->C=o->OP->B; o->BP->C=o->BP->B; o->TP->C=o->TP->B; if (DelMessMode) then { for(M=o->MP->B; MMP->C;) if (DelMessMode==2 || MatchMC(M->M,EffMTagC,EffMTagB)) then memcpy(M,--o->MP->C,sizeof(TMess)); else M++; } } /*------------------------------*/ InitStat(stp) /* Initialize Statistic */ /*------------------------------*/ TStat *stp; { memset(stp,0,sizeof(TStat)); } /*------------------------------*/ UpdStat(o) /* Update Statistic */ /*------------------------------*/ TCS *o; { TCF *C; int i; cy.CycleC=1; cy.ReVal=ReVal; cy.NCFMinStr=cy.NCFMaxStr=cy.Str=0; for(C=o->CP->B; CCP->C; C++) { cy.Str+=C->S; if (C->S==MinStr) then cy.NCFMinStr++; if (C->S==MaxStr) then cy.NCFMaxStr++; } /* cy.MCF and cy.MMess are updated in MatchBid() */ cy.NCF =o->CP->C-o->CP->B; cy.NBid =o->BP->C-o->BP->B; cy.NTup =o->TP->C-o->TP->B; cy.NMess=o->MP->C-o->MP->B; for(i=0; iMP,MDetM); cy.MCF=cy.MMess=0; /* for Stat */ MatchBid(o->CP,o->MP,o->BP,o->TP); if (DelMessMode!=2) then o->NP->E-=MDetM; /* res. for DetMess */ Fire(o->CP,o->MP,o->BP,o->TP,o->NP); if (DelMessMode!=2) then o->NP->E+=MDetM; /* free reserved " */ Clean(o->NP); if (CycleC%EffRate==0) then { o->DP->B=o->DP->C=o->BP->C; /* because DP=BP,UP=TP */ o->UP->B=o->UP->C=o->TP->C; MatchBid(o->EP,o->NP,o->DP,o->UP); Fire(o->EP,o->NP,o->DP,o->UP,o->OP); /* maybe create EMess, if OP is Empty */ Effect(o->OP); } if (CycleC%ReRate==0) then ReVal=Reinf(o->OP); else ReVal=FixP(0); Credit(o->CP,o->EP,o->MP,o->NP,o->BP,o->DP,o->TP,o->UP); Taxes(o->CP,o->NP,o->BP); pprCS(prMode,o); StrUpDate(o->CP); if (CycleC%GenRate==0) then Genetic(o->CP); UpdStat(o); if (CycleC%StRate==0) then pprStat(prMode,&ep); if (SStepF && ((prMode>1)||(CycleC%StRate==0))) then Menu(); else event(); ReInit(o); } \end{verbatim} \begin{verbatim} /****************************************************************/ /* M e n u - C o n t r o l */ /****************************************************************/ /*------------------------------*/ char GetKey() /* Get a Key */ /*------------------------------*/ { char c=getch(); if (c==0) then c=128+getch(); } /*------------------------------*/ Menu() /* Wait for Key/Menu-Selection */ /*------------------------------*/ { char c; extern chdo(char c); do { c=GetKey(); if (c!=ESC) chdo(c); } while(!strchr("Cc ",c)); if (!SStepF) prf(LIGHTGREEN,"Simulation Continued\r\n"); } /*------------------------------*/ prMenu() /* Display Menu */ /*------------------------------*/ { window(1,1,80,1); textbackground(BLUE); clrscr(); cprintf("Retart ESC Cont Break Abort Prot stEp "); cprintf("Help Display Sound 0123 rdZ Test\r"); window(1,3,80,NScrL); textbackground(BLACK); } /*------------------------------*/ chdo(char c) /* Branch on Menu-Selection c */ /*------------------------------*/ { extern CFSMain(),CFSExit(),TestFunc(); switch(toupper(c)) { case 'R': CFSExit(); longjmp(jmp,1); /* ReStart CFS-Simul.*/ case 'B': BreakPoint(); /* Break to TC++ */ case ESC: prf(LIGHTGREEN, /* Interrupt Simul. */ "Simulation Interrupted in Cycle %ld\r\n",CycleC); Menu(); break; case 'C': case ' ': break; /* Continue Simul. */ case 'A': CFSExit(); exit(0); /* Abort to CFS */ case 'P': SetProt(!ProtF); break; /* Protocoll on/off */ case 'E': SetSStep(!SStepF);break; /* SingleStep on/off */ case 'H': case 187: pprInfo(); break; /* Printf Help-Info */ case 'D': pprCS(max(prMode,2),o); break; /* Print Status */ case '0': case '1': case '2': /* PrintMode 0123 */ case '3': SetprMode(c-'0'); break; case 'S': SetSound(!SoundF); break; /* Sound on/off */ case 'Z': randomize(); break; /* randomize */ case 'T': TestFunc(); break; /* Testfunction */ default : Sound(2500,10); /* Wrong Key */ } } /*------------------------------*/ char event() /* look for KeyBoard-Event */ /*------------------------------*/ { char c; if (!kbhit()) then return(0); c=GetKey(); chdo(c); return(c); } /****************************************************************/ /* T e s t - P r o c e d u r e s */ /****************************************************************/ /*------------------------------*/ TestFunc() /* Testfunction */ /*------------------------------*/ { int i; prf(LIGHTCYAN,"This is a test ...\r\n"); Error(0); } \end{verbatim} \begin{verbatim} /****************************************************************/ /* I n i t - E x i t - M a i n - P r o c e d u r e s */ /****************************************************************/ #define oalloc(P,S) \ P->B=malloc((S+1)*sizeof(*P->B)); \ if (P->B==NULL) then Error(6); \ P->B=P->C=P->B+1; P->E=P->B+S; /*------------------------------*/ InitMessL(MP,S) /* Init Mess-List */ /*------------------------------*/ TMessL *MP; int S; { MP->B=malloc((S+1)*sizeof(TMess)); if (MP->B==NULL) then Error(6); MP->B->M=0; MP->B->I=DefNMI; MP->B->CF=NonId; MP->B=MP->C=MP->B+1; MP->E=MP->B+S; } /*------------------------------*/ InitCFL(CP,S) /* Init CF-List */ /*------------------------------*/ TCFL *CP; int S; { CP->B=malloc((S+1)*sizeof(TCF)); if (CP->B==NULL) then Error(6); CP->B->S=FixP(1); /* ... */ CP->B=CP->C=CP->B+1; CP->E=CP->B+S; } /*------------------------------*/ CFSInit() /* Initialisierung */ /*------------------------------*/ { char **S; char T[SStr+1]; /* Other Initializations */ memset(WC,0,sizeof(WC)); memset(WP,0,sizeof(WP)); srand(12345); /* Create Arrays */ InitMessL(o->MP,SMessL); InitMessL(o->NP,SMessL); InitMessL(o->OP,SOutL); InitCFL(o->CP,SCFL); InitCFL(o->EP,SEffL); oalloc(o->BP,SBidL); memcpy(o->DP,o->BP,sizeof(TBidL)); oalloc(o->TP,STupL); memcpy(o->UP,o->TP,sizeof(TTupL)); /* Init Classifier & Effectors & Enviroment */ for(S=CFSL; *S; S++) StoCF(*S,o->CP->C++,DefStr,DefStrDev); while(o->CP->CCP->E) RandCF(o->CP->C++); for(S=EffSL;*S; S++) StoCF(*S,o->EP->C++,FixP(1),FixP(0)); InitEnv(); /* Read Detector/Effector-Tags */ memset(T,'#',SStr); T[SStr]='\0'; memcpy(T,DetMessTag,min(strlen(DetMessTag),SStr)); StoCB(T,&DetMTagC,&DetMTagB); memset(T,'#',SStr); T[SStr]='\0'; memcpy(T,EffMessTag,min(strlen(EffMessTag),SStr)); StoCB(T,&EffMTagC,&EffMTagB); /* Open Devices */ textmode(C4350); textcolor(YELLOW); devP=fopen(ProtDev,"ab"); CycleC=0; ProtF=TRUE; SStepF=FALSE; textbackground(BLACK); clrscr(); prMenu(); if (prMode>0) then { prf(LIGHTCYAN, "%s\r\n%s\r\n%s\r\n%s\r\n%s\r\n%s%s%s\r\n%s\r\n\n", "+---------------------------------------------------------+", "| C l a s s i f i e r - S y s t e m - S i m u l a t o r |", "|---------------------------------------------------------|", "| Copyright by Marcus Hutter 01.04.91 Vers. 1.0 |", "|---------------------------------------------------------|", "| Simulation Run (" , ActTime() , ") |", "+---------------------------------------------------------+"); } SetProt(FALSE); SetSStep(TRUE); } /*------------------------------*/ CFSMain() /* Main-Routinen */ /*------------------------------*/ { prf(LIGHTGREEN, "Press to continue ... or any other Menu-Key\r\n"); Menu(); FOREVER MainStep(o); } /*------------------------------*/ CFSExit() /* Exit-Routinen */ /*------------------------------*/ { fclose(devP); fclose(lpt1); free(o->TP->B-1); free(o->BP->B-1); free(o->EP->B-1); free(o->CP->B-1); free(o->OP->B-1); free(o->NP->B-1); free(o->MP->B-1); } /*------------------------------*/ main() /* Main-Program */ /*------------------------------*/ { setjmp(jmp); CFSInit(); CFSMain(); CFSExit(); /* not needed */ exit(0); /* not needed */ } \end{verbatim} \end{listing} \clearpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Beispiellisting {\tt EXAMPLE1.C} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{listing} \begin{verbatim} /****************************************************************/ /* C l a s s i f i e r - S y s t e m - E x a m p l e 1 */ /****************************************************************/ /* T e s t (c) by Marcus Hutter 01.04.1991 */ /****************************************************************/ /* USER-Variables are Model-dependend */ /* user-Variables are Program-Specific */ /*------------------------------*/ /* Variables */ /*------------------------------*/ /* Array-Sizes and other Compiler-Information */ #define SMessL 1 /* USER: # of Messages */ #define SOutL 1 /* USER: # of Mess prod. by Eff */ #define SCFL 100 /* USER: # of Classifiers */ #define SEffL 1 /* USER: # of Effectors */ #define SBidL 100 /* user: # of matching-mess */ #define STupL 100 /* user: # of matching-tuples */ #define SStr 6 /* USER: # of Bits per String */ #define TwoCond FALSE /* USER: two Conditions (or one)*/ #define SpeedF TRUE /* user: Optimize for Speed */ BreakPoint() {} /* Set a BreakPoint in this Line !! */ #include "D:\TC\MYPROGS\CFSSIM.C" /* Classifier-System-Sim. */ /* General - Variables */ int StRate = 100; /* USER: Statistic-Activ-Rare */ fixp SclSel = FixP(2/3); /* USER: Scale-Factor 50%-100% */ char ProtDev[30]="example1.lst";/* USER: Protocoll-Device */ char DetMessTag[] = "#"; /* USER: {0,1,#}* */ char EffMessTag[] = "##"; /* USER: {0,1,#}* */ /* Detector - Variables */ int DetRate = 1; /* USER: Det.-Sampling-Rate */ int MDetM = 1; /* USER: # of Det.Mess. */ fixp DefDetMI = FixP(1.0); /* USER: Detector-Mess-Intens. */ fixp DefStr = FixP(2.0); /* USER: DefaultStrength 0..9 */ fixp DefStrDev= FixP(0.1); /* USER: DefaultStrDev 0..25% */ /* Matching - Variables */ fixp DefNMI = FixP(1.0); /* USER: Default NonMatchIntens */ /* Bid - Variables */ fixp Dev2 = FixP(0.0); /* USER: EBid-Deviation 0..25% */ /* Clean - Variables */ int MEqMess = MaxInt; /* USER: # of Equal Mess. */ sbyte DelMessSelMode= 2; /* USER: DelMode -6..6 */ bool CleanHallF = FALSE; /* USER: Clean Hallunc.Mess. */ /* Effector - Variables */ int EffRate = 1; /* USER: Eff.-Sampling-Rate */ /* Credit - Variables */ int ReRate = 1; /* USER: Reinf.Act.Rate */ byte CreditMode= 1; /* USER: Credit-Assign-Mode */ fixp NMFrac =FixP(0.3); /* USER: NonMatchCreditFrac.in% */ fixp DetFrac =FixP(0.5); /* USER: DetectorCreditFrac.in% */ fixpPSPFrac =FixP(0.1); /* USER: PSP-Reduc.-Constant.in%*/ byte PSPDisMode= 4; /* USRR: PSP-Distr.-Mode 1..4 */ /* Taxes - Variables */ fixp HeadTax = FixP(0.00); /* USER: Head-Tax (CF-Tax) */ fixp MessTax = FixP(1.00); /* USER: Mess-Tax */ fixp BidTax = FixP(0.00); /* USER: Bid-Tax */ byte BidTaxMode = 2; /* USER: BidTaxMode 1..2 */ bool MultBidTaxF = FALSE; /* USER: Tax for each Bid */ bool MultMessTaxF = FALSE; /* USER: Tax for each Mess */ /* StrUpDate - Variables*/ fixp MaxStr = FixP(20.0); /* USER: Maximal Strength of CF */ fixp MinStr = FixP( 0.0); /* USER: Minimal Strength of CF */ /* Genetic - Variables */ int GenRate = 50; /* USER: Genetic-Activ.-Rate */ int NCFRepl = 50; /* USER: # of CF to Replace */ sbyte ReplSelMode= 3; /* USER: Replace-SelMode */ int NCFMut = 0; /* USER: # of CF to Mutate */ int NMutate = 1; /* USER: # of Mutations per CF */ sbyte MutSelMode= 3; /* USER: Mutation-SelMode */ fixp CondSp =FixP(0.50); /* USER: Mean Cond-Specifity % */ fixp ActSp =FixP(1.0); /* USER: Mean Act.-Specifity % */ fixp NegCondP =FixP(0.00); /* USER: Prob. of neg. Cond % */ /* ReInit - Variables */ byte DelMessMode = 2; /* USER: Del.Mess-Mode 0..2 */ \end{verbatim} \begin{verbatim} TCFL XC = { 0,0,0, /* Classifier-Parameters */ 2, /* USER: BidMode 1..4 */ 2, /* USER: SuppMode 1..2 */ 2, /* USER: BidTupSelMode -6..6 */ 2, /* USER: BidActSelMode -6..6 */ 3, /* USER: FireBidSelMode -6..6 */ 2, /* USER: FireTupSelMode -6..6 */ 5, /* USER: MBids 1..MaxInt */ MaxInt, /* USER: MAct 1..MaxInt */ MaxInt, /* USER: MFire 1..MaxInt */ FixP(1.0), /* USER: RiskFak FixP(0..1) % */ 1, /* USER: SpecPow 0..2 */ 1, /* USER: RelSuppPow 0..2 */ 1, /* USER: EBidPow 0..2 */ 0, /* USER: ESpecPow 0..2 */ 1, /* USER: ClaimMode 1..2 */ 1, /* USER: DisMode 1..5 */ 2 }; /* USER: SumMode 1..3 */ TCFL XE = { 0,0,0, /* Effector-Parameters */ 2, /* USER: BidMode 1..4 */ 2, /* USER: SuppMode 1..2 */ 2, /* USER: BidTupSelMode -6..6 */ 2, /* USER: BidActSelMode -6..6 */ 2, /* USER: FireBidSelMode -6..6 */ 2, /* USER: FireTupSelMode -6..6 */ 5, /* USER: MBids 1..MaxInt */ MaxInt, /* USER: MAct 1..MaxInt */ 1, /* Should be 1 (MFire) */ FixP(0.5), /* USER: RiskFak FixP(0..1) % */ 1, /* USER: SpecPow 0..2 */ 1, /* USER: RelSuppPow 0..2 */ 1, /* USER: EBidPow 0..2 */ 0, /* USER: ESpecPow 0..2 */ 1, /* USER: ClaimMode 1..2 */ 1, /* USER: DisMode 1..5 */ 2 }; /* USER: SumMode 1..3 */ char *MessSL[] = /* Predefined Messages */ { /* "1111", "1000", "1001", "0000", */ NULL }; char *CFSL[] = /* Predefined Classifiers */ { /* "+1###+#11#/01#1", "-0###-0###/111#", "+0###-0000/1###", */ NULL }; char *EffSL[] = /* Predefined Effectors */ { "+######/00000#", NULL }; typedef struct /* Enviroment */ { int inp; int out; bool success; /*...*/ } TEnv; TEnv Env; /* Current Enviroment */ /*------------------------------*/ InitEnv() /* Init Enviroment */ /*------------------------------*/ { memset(&Env,0,sizeof(Env)); } /*------------------------------*/ Detect(MP,N) /* Detect Messages */ /*------------------------------*/ TMessL *MP; /* Message-List */ int N; /* Max.# of Det.Mess */ { Env.inp=rand()&63; /* 2 Addr. & 4 Inp. Bits */ Env.out=(Env.inp>>(5-(Env.inp&3)))&1; MP->C->M = Env.inp; MP->C->I = DefDetMI; MP->C->CF= DetId; MP->C++; } /*------------------------------*/ Effect(OP) /* Effect Messages */ /*------------------------------*/ TMessL *OP; {/* Change Enviroment in dependence on MP */ /* prf(0,"Output-Mess = Env.Change:\n"); pprMessL(MP); */ } /*------------------------------*/ fixp Reinf(OP) /* Calculate Reinforcement */ /*------------------------------*/ TMessL *OP; { Env.success = (OP->C>OP->B) && (Env.out==(OP->B->M)); return(FixP((Env.success) ? 10 : 0 )); } /*------------------------------*/ Display() /* Display Information */ /*------------------------------*/ { if (prMode>1) then prf(LIGHTRED,"4to1Decoder: %s->%d %s\r\n", CBtoS(Env.inp,MMask),Env.out, (Env.success) ? "Success" : "Failure"); } /********************** End of Example 1 ************************/ \end{verbatim} \end{listing} \clearpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Beispielprotokoll {\tt EXAMPLE1.LST} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{listing} \begin{verbatim} +---------------------------------------------------------+ | C l a s s i f i e r - S y s t e m - S i m u l a t o r | |---------------------------------------------------------| | Copyright by Marcus Hutter 01.04.91 Vers. 1.0 | |---------------------------------------------------------| | Simulation Run (Sun May 12 09:01:02 1991) | +---------------------------------------------------------+ Protocoll ON 4to1Decoder: 101011->0 Failure -------------- Cycle 1 -------------- Message-List: MId Intens Sender Message 0: 1.00 D 101011 Classifier-List: CFId Str Get Pay Taxes Condion/Action 0: 1.71 0.00 0.00 0.00 +#0##0#/111011 1: 1.90 0.00 0.00 0.00 +10#01#/000000 2: 1.90 0.00 0.00 0.00 +#11#00/100100 3: 2.00 0.00 0.00 0.00 +1101#1/110110 4: 2.29 0.00 0.00 0.00 +##0#1#/000110 5: 1.80 0.00 0.00 0.00 +##000#/001010 6: 1.90 0.00 0.00 0.00 +0#1###/111111 7: 2.39 0.00 0.00 0.00 +11####/010001 8: 2.00 0.00 0.00 0.00 +0#10#0/010111 9: 2.10 0.00 0.00 0.00 +##10#0/110001 10: 2.20 0.00 0.00 0.00 +0#1101/011010 11: 1.90 0.00 0.00 0.00 +#0#01#/100000 12: 1.80 0.00 0.00 0.00 +#00#00/110101 13: 2.00 0.00 0.00 0.00 +##100#/111111 14: 2.00 0.00 0.00 0.00 +####1#/110000 15: 2.00 0.00 0.00 0.00 +000##1/010100 16: 1.80 0.00 0.00 0.00 +##0#10/100100 17: 1.90 0.00 0.00 0.00 +###1#0/110111 18: 2.10 0.00 0.00 0.00 +0###1#/001110 19: 1.71 0.00 0.00 0.00 +1#1###/011011 20: 1.80 0.00 0.00 0.00 +#01110/001101 21: 1.90 0.00 0.00 0.00 +#01#1#/011100 22: 1.51 0.00 0.00 0.00 +##0##1/111100 23: 2.10 0.00 0.00 0.00 +110###/000011 24: 2.10 0.00 0.00 0.00 +###1##/000010 25: 2.10 0.00 0.00 0.00 +10##1#/010010 26: 2.20 0.00 0.00 0.00 +1##11#/010110 27: 1.90 0.00 0.00 0.00 +##1#11/100000 28: 2.39 0.00 0.00 0.00 +###0##/000010 29: 1.90 0.00 0.00 0.00 +##001#/011100 30: 2.29 0.00 0.00 0.00 +0#0###/000101 31: 2.10 0.00 0.00 0.00 +#0#001/100000 32: 1.90 0.00 0.00 0.00 +#0##0#/001101 33: 1.90 0.00 0.00 0.00 +#0#100/100111 34: 1.90 0.00 0.00 0.00 +101#10/001100 35: 1.71 0.00 0.00 0.00 +######/011000 36: 2.10 0.00 0.00 0.00 +0#10#0/111010 37: 1.90 0.00 0.00 0.00 +100#1#/010100 38: 1.90 0.00 0.00 0.00 +##1#1#/011110 39: 1.71 0.00 0.00 0.00 +0#####/000111 40: 2.20 0.00 0.00 0.00 +10#00#/001010 41: 2.10 0.00 1.74 2.10 +10101#/100011 42: 2.20 0.00 0.00 0.00 +###01#/111010 43: 2.00 0.00 0.00 0.00 +1#####/000011 44: 2.20 0.00 0.00 0.00 +###0#0/011001 45: 2.00 0.00 0.00 0.00 +0#00##/010111 46: 2.10 0.00 0.00 0.00 +10####/110001 47: 1.90 0.00 0.00 0.00 +10####/001011 48: 1.32 0.00 0.00 0.00 +#0###1/000001 49: 1.90 0.00 0.00 0.00 +0000##/001101 50: 1.80 0.00 0.00 0.00 +#11###/000011 51: 2.10 0.00 0.00 0.00 +10#10#/011100 52: 2.00 0.00 0.00 0.00 +##010#/010111 53: 1.80 0.00 0.00 0.00 +#00##1/100100 54: 1.90 0.00 0.00 0.00 +1#1011/111001 55: 2.10 0.00 0.00 0.00 +00##1#/000110 56: 1.90 0.00 0.00 0.00 +1#1111/111111 57: 2.20 0.00 0.00 0.00 +10##0#/011111 58: 2.00 0.00 0.00 0.00 +0#11##/001100 59: 1.71 0.00 0.00 0.00 +#0#1#0/001010 60: 2.39 0.00 0.00 0.00 +####10/010111 61: 2.00 0.00 0.00 0.00 +11#0##/101000 62: 2.10 0.00 0.00 0.00 +0#00##/001100 63: 2.39 0.00 0.00 0.00 +##001#/101010 64: 1.71 0.00 0.00 0.00 +1##1#1/100000 65: 2.00 0.00 0.00 0.00 +11##01/001001 66: 2.29 0.00 0.00 0.00 +#10110/010011 67: 2.00 0.00 0.00 0.00 +1#11##/010000 68: 2.00 0.00 0.00 0.00 +10001#/011000 69: 2.10 0.00 0.00 0.00 +#11###/100100 70: 2.20 0.00 0.00 0.00 +##0001/111010 71: 2.00 0.00 0.00 0.00 +1##111/010111 72: 1.80 0.00 0.00 0.00 +###0##/001100 73: 2.00 0.00 0.00 0.00 +0##1#1/100010 74: 2.10 0.00 0.00 0.00 +0####0/101110 75: 2.00 0.00 0.00 0.00 +#110##/000010 76: 1.90 0.00 0.00 0.00 +#0##11/101101 77: 2.10 0.00 0.00 0.00 +##01#1/100101 78: 1.90 0.00 0.00 0.00 +1#####/100010 79: 1.90 0.00 0.00 0.00 +0#00#1/010001 80: 2.00 0.00 0.00 0.00 +##1##1/111110 81: 2.20 0.00 0.00 0.00 +#101#1/000101 82: 1.90 0.00 0.00 0.00 +00100#/100101 83: 2.10 0.00 0.00 0.00 +##0111/010100 84: 1.90 0.00 0.00 0.00 +00####/001010 85: 2.10 0.00 0.00 0.00 +1111#1/011001 86: 2.10 0.00 0.00 0.00 +#001#1/001000 87: 2.10 0.00 0.00 0.00 +1##1#0/100010 88: 2.39 0.00 0.00 0.00 +###0#0/110000 89: 1.90 0.00 0.00 0.00 +1###0#/001111 90: 2.00 0.00 0.00 0.00 +#0###1/001000 91: 1.80 0.00 0.00 0.00 +1####1/110100 92: 2.10 0.00 0.00 0.00 +##11#0/110100 93: 1.71 0.00 0.00 0.00 +0###1#/011011 94: 2.00 0.00 0.00 0.00 +100#11/000001 95: 1.41 0.00 0.00 0.00 +###10#/110111 96: 2.20 0.00 0.00 0.00 +##11##/111101 97: 2.00 0.00 0.00 0.00 +1#0###/101010 98: 1.90 0.00 0.00 0.00 +##01#0/001000 99: 2.10 0.00 0.00 0.00 +#0#10#/000111 Bid-List: BidId CFId Bid EBid Fired BidTupel 0: 1 1.26 1.26 - { 0 } 1: 11 0.95 0.95 - { 0 } 2: 14 0.33 0.33 - { 0 } 3: 19 0.57 0.57 - { 0 } 4: 21 0.95 0.95 - { 0 } 5: 25 1.05 1.05 - { 0 } 6: 27 0.95 0.95 - { 0 } 7: 28 0.39 0.39 - { 0 } 8: 35 0.00 0.00 - { 0 } 9: 38 0.63 0.63 - { 0 } 10: 41 1.74 1.74 F { 0 } 11: 42 0.73 0.73 - { 0 } 12: 43 0.33 0.33 - { 0 } 13: 46 0.70 0.70 - { 0 } 14: 47 0.63 0.63 - { 0 } 15: 48 0.43 0.43 - { 0 } 16: 54 1.58 1.58 - { 0 } 17: 72 0.29 0.29 - { 0 } 18: 76 0.95 0.95 - { 0 } 19: 78 0.31 0.31 - { 0 } 20: 80 0.66 0.66 - { 0 } 21: 90 0.66 0.66 - { 0 } 22: 91 0.60 0.60 - { 0 } New-Message-List: MId Intens Sender Message 0: 1.74 41 100011 Effector-List: CFId Str Get Pay Taxes Condion/Action 0: 1.00 0.00 0.00 0.00 +######/00000# Eff-Bid-List: BidId CFId Bid EBid Fired BidTupel 0: 0 0.00 0.00 F { 0 } Output-Message-List: MId Intens Sender Message 0: 0.00 0 000001 Cycle-Cycle Reinf Strength Min Max Mch Mch Bid Tup Value Str Str CF Mess 's els 1-1 : 0.000 0.000 0 0 24 0 0 0 PrintMode = 2 4to1Decoder: 011101->1 Failure Cycle-Cycle Reinf Strength Min Max Mch Mch Bid Tup Value Str Str CF Mess 's els 2-2 : 0.000 1.968 1 0 13 0 23 23 4to1Decoder: 011111->1 Failure 3-3 : 0.000 1.946 2 0 16 0 12 12 4to1Decoder: 111010->1 Success 4-4 : 0.000 1.926 3 0 19 0 15 15 4to1Decoder: 000110->0 Success 5-5 : 10.000 1.995 3 0 17 0 18 18 4to1Decoder: 011000->0 Failure 6-6 : 10.000 2.063 3 0 17 0 16 16 \end{verbatim} \begin{verbatim} PrintMode = 1 SingleStep OFF Simulation Continued Cycle-Cycle Reinf Strength Min Max Mch Mch Bid Tup Value Str Str CF Mess 's els 1-100 : 6.400 2.268 8 0 18 0 17 17 101-200 : 7.800 2.525 5 0 19 0 18 18 201-300 : 8.900 2.718 2 0 18 0 17 17 301-400 : 8.900 2.887 2 0 19 0 18 18 401-500 : 8.700 2.851 3 0 17 0 16 16 501-600 : 8.600 2.792 4 0 18 0 17 17 601-700 : 9.300 2.926 1 0 19 0 18 18 701-800 : 9.600 2.999 1 0 17 0 16 16 801-900 : 9.500 2.991 1 0 17 0 16 16 901-1000 : 9.700 3.042 0 0 18 0 17 17 1001-1100 : 9.300 3.101 1 0 17 0 16 16 1101-1200 : 9.800 3.156 0 0 16 0 15 15 1201-1300 : 9.600 3.100 0 0 16 0 15 15 1301-1400 : 9.600 3.094 1 0 17 0 16 16 1401-1500 : 9.900 3.145 0 0 17 0 16 16 1501-1600 : 9.900 3.165 0 0 18 0 17 17 1601-1700 : 9.900 3.174 0 0 17 0 16 16 1701-1800 : 9.900 3.163 0 0 16 0 15 15 1801-1900 : 10.000 3.204 0 0 17 0 16 16 1901-2000 : 10.000 3.207 0 0 16 0 15 15 2001-2100 : 10.000 3.195 0 0 16 0 15 15 Simulation Interrupted in Cycle 2151 PrintMode = 3 4to1Decoder: 111100->1 Success -------------- Cycle 2151 -------------- Message-List: MId Intens Sender Message 0: 1.00 D 111100 Classifier-List: CFId Str Get Pay Taxes Condion/Action 0: 6.01 0.00 0.00 0.00 +0#1#00/110010 1: 5.45 0.00 0.00 0.00 +011#01/000001 2: 6.01 0.00 0.00 0.00 +0#1#10/011001 3: 2.59 0.00 0.00 0.00 +110#11/111010 4: 1.80 0.00 0.00 0.00 +11####/101011 5: 2.49 0.00 0.00 0.00 +##11##/101111 6: 2.10 0.00 0.00 0.00 +01#10#/101010 7: 1.80 0.00 0.00 0.00 +##10##/110100 8: 2.10 0.00 0.00 0.00 +1####0/000010 9: 1.80 0.00 0.00 0.00 +000###/011111 10: 2.39 0.00 0.00 0.00 +0#10#0/011101 11: 1.90 0.00 0.00 0.00 +###0##/011111 12: 1.80 0.00 0.00 0.00 +1##000/101011 13: 6.67 0.00 0.00 0.00 +#1#10#/110111 14: 2.20 0.00 0.00 0.00 +#0#1##/011011 15: 1.90 0.00 0.00 0.00 +#01#00/110111 16: 1.80 0.00 0.00 0.00 +##00#0/011101 17: 2.49 0.00 0.00 0.00 +#0###1/111101 18: 1.80 0.00 0.00 0.00 +#####0/011111 19: 6.01 0.00 0.00 0.00 +1##000/101001 20: 2.00 0.00 0.00 0.00 +0#10##/110100 21: 2.39 0.00 0.00 0.00 +#101#1/101000 22: 2.59 0.00 0.00 0.00 +###011/000010 23: 5.46 0.00 0.00 0.00 +10#100/110011 24: 1.71 0.00 0.00 0.00 +##10##/101101 25: 1.51 0.00 0.00 0.00 +11##1#/111010 26: 6.67 0.00 0.00 0.00 +###111/011101 27: 2.10 0.00 0.00 0.00 +0##001/111101 28: 2.00 0.00 0.00 0.00 +#00#1#/100111 29: 2.49 0.00 0.00 0.00 +01#0#1/101110 30: 2.29 0.00 0.00 0.00 +0###1#/101001 31: 6.01 0.00 0.00 0.00 +#0#001/100000 32: 3.13 0.00 0.00 0.00 +010#10/011100 33: 6.01 0.00 0.00 0.00 +1#0#10/010010 34: 2.00 0.00 0.00 0.00 +####1#/101000 35: 1.90 0.00 0.00 0.00 +#1#01#/101110 36: 2.29 0.00 0.00 0.00 +#11##0/000110 37: 2.10 0.00 0.00 0.00 +0##100/011111 38: 2.49 0.00 0.00 0.00 +###1##/011101 39: 1.80 0.00 0.00 0.00 +0#1100/010001 40: 2.10 0.00 0.00 0.00 +010#1#/101101 41: 2.00 0.00 0.00 0.00 +00#0##/101000 42: 1.71 0.00 0.00 0.00 +###1#1/011001 43: 1.90 0.00 0.00 0.00 +1#0##1/010111 44: 2.49 0.00 0.00 0.00 +#11###/111011 45: 2.20 0.00 0.00 0.00 +#00010/110001 46: 1.80 0.00 0.00 0.00 +0##1#0/010110 47: 1.90 0.00 0.00 0.00 +#1#1#1/001101 48: 1.90 0.00 0.00 0.00 +##1###/101001 49: 2.49 0.00 0.00 0.00 +0##0#0/111000 50: 6.01 0.00 0.00 0.00 +10##01/100010 51: 2.20 0.00 0.00 0.00 +1###1#/010011 52: 2.10 0.00 0.00 0.00 +110##1/001110 53: 1.90 0.00 0.00 0.00 +##1000/110000 54: 2.10 0.00 0.00 0.00 +0#0#1#/110100 55: 5.45 0.00 0.00 0.00 +01#000/101100 56: 2.10 0.00 0.00 0.00 +###1#1/000111 57: 6.01 0.00 0.00 0.00 +00#00#/111110 58: 2.20 0.00 0.00 0.00 +#0####/010010 59: 1.71 0.00 0.00 0.00 +0##10#/100111 60: 7.51 0.00 0.00 0.00 +####10/010111 61: 2.10 0.00 0.00 0.00 +1#01##/000010 62: 2.49 0.00 0.00 0.00 +##1000/111110 63: 6.67 0.00 0.00 0.00 +##001#/101010 64: 2.49 0.00 0.00 0.00 +#10#0#/110101 65: 6.01 0.00 0.00 0.00 +11##01/001001 66: 2.00 0.00 0.00 0.00 +###100/010000 67: 2.59 0.00 0.00 0.00 +##1###/111011 68: 3.07 0.00 0.00 0.00 +10001#/011000 69: 6.67 0.00 0.00 0.00 +##10#1/010110 70: 2.00 0.00 0.00 0.00 +0###0#/111011 71: 2.39 0.00 0.00 0.00 +#1#1#0/100001 72: 2.59 0.00 0.00 0.00 +1##111/111100 73: 2.49 0.00 0.00 0.00 +0#1##1/100100 74: 2.49 0.00 0.00 0.00 +1#110#/001110 75: 2.00 0.00 0.00 0.00 +10#1#0/110000 76: 2.59 0.00 0.00 0.00 +0####1/010001 77: 2.49 0.00 0.00 0.00 +011#01/001101 78: 2.29 0.00 0.00 0.00 +1####0/000110 79: 2.49 0.00 0.00 0.00 +###0##/010010 80: 2.49 0.00 0.00 0.00 +010100/000101 81: 6.01 0.00 0.00 0.00 +#101#1/000101 82: 8.59 0.00 0.00 0.00 +0#####/111010 83: 2.59 0.00 0.00 0.00 +##1#1#/100101 84: 2.10 0.00 0.00 0.00 +#111#1/011011 85: 5.45 0.00 0.00 0.00 +1111#1/011001 86: 2.39 0.00 0.00 0.00 +##0##0/110001 87: 7.51 0.00 0.00 0.00 +##00##/001011 88: 2.39 0.00 0.00 0.00 +###0##/101110 89: 2.10 0.00 0.00 0.00 +001100/011111 90: 5.50 0.00 0.00 0.00 +00#101/100100 91: 6.67 10.00 3.33 6.67 +#11##0/110111 92: 1.90 0.00 0.00 0.00 +##1111/110011 93: 2.00 0.00 0.00 0.00 +10###0/100111 94: 2.29 0.00 0.00 0.00 +####01/010110 95: 6.67 0.00 0.00 0.00 +##1#01/110100 96: 6.01 0.00 0.00 0.00 +##0110/010110 97: 6.01 0.00 0.00 0.00 +0##100/001100 98: 1.80 0.00 0.00 0.00 +######/000001 99: 2.49 0.00 0.00 0.00 +1##011/001110 Bid-List: BidId CFId Bid EBid Fired BidTupel 0: 4 0.60 0.60 - { 0 } 1: 5 0.82 0.82 - { 0 } 2: 8 0.70 0.70 - { 0 } 3: 13 3.33 3.33 - { 0 } 4: 18 0.29 0.29 - { 0 } 5: 36 1.14 1.14 - { 0 } 6: 38 0.41 0.41 - { 0 } 7: 44 0.82 0.82 - { 0 } 8: 48 0.31 0.31 - { 0 } 9: 66 1.00 1.00 - { 0 } 10: 67 0.42 0.42 - { 0 } 11: 71 1.20 1.20 - { 0 } 12: 74 1.65 1.65 - { 0 } 13: 78 0.76 0.76 - { 0 } 14: 91 3.33 3.33 F { 0 } 15: 98 0.00 0.00 - { 0 } New-Message-List: MId Intens Sender Message 0: 3.33 91 110111 Effector-List: CFId Str Get Pay Taxes Condion/Action 0: 1.00 0.00 0.00 0.00 +######/00000# Eff-Bid-List: BidId CFId Bid EBid Fired BidTupel 0: 0 0.00 0.00 F { 0 } Output-Message-List: MId Intens Sender Message 0: 0.00 0 000001 Cycle-Cycle Reinf Strength Min Max Mch Mch Bid Tup Value Str Str CF Mess 's els 2151-2151 : 10.000 3.207 0 0 17 0 16 16 \end{verbatim} \end{listing} \end{appendix} \fi \clearpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Bibliography % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \addcontentsline{toc}{section}{Literatur} \begin{thebibliography}{9} \bibitem{Holland} {\bf Holland J.H.}: {\it Escaping Brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems}; {\rm Machine Learning Vol 2 Kaufmann Publ., 1986} \bibitem{Booker} {\bf Booker L.B., Goldberg D.E., Holland J.H.}: {\it Classifier systems and genetic algorithms}; {\rm Artificial Intelligence 40,235-282, 1989} \bibitem{Proc} {\it Proceedings of the third international conference on genetic algorithms}; {\rm Kaufmann Publ., 1989} \bibitem{Goldberg} {\bf Goldberg D.E.}: {\it Genetic algorithms in search, optimization machine learning}; {\rm Addison-Wesley, 1989} \bibitem{Wilson} {\bf Wilson S.W.}: {\it Classifier systems and the animat problem}; {\rm Kluwer Academic Publishers, Bosten, 1987} \bibitem{Weiss} {\bf Weiss G.}: {\it Benutzerbeschreibung zum Klassifizierungssystem} {\rm TU-Mnchen, 1991} % ... \end{thebibliography} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Index % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\addcontentsline{toc}{section}{Index} \end{document}