
\documentstyle[bk11,dina4,german]{article}

\hbadness=2500     \vbadness=3500
\clubpenalty9500   \widowpenalty9500
\tolerance=9999    \spaceskip=0.38em plus 0.3em minus 1pt

\textheight=22cm
\footskip=3\baselineskip
\hyphenation{ }

\newcommand{\yeah}{$\stackrel{^\circ \imath ^\circ}{_\smile}$}



\begin{document}


\title{	EPO V0.5\\
	 Der evolution�re Parameter-Optimierer \\
	Anleitung zur Shareware-Version }

\author{ (C) 4/94 ~~ Petra Roosen\\
	Petra\_Roosen$@$ac3.maus.de }

\date{\today}

\maketitle

\begin{abstract}

EPO ist als allgemeines Parameter-Optimierungsprogramm anpa�bar an fast beliebige Problemstellungen. Es arbeitet auf Basis eines naturanalogen Algorithmus und ben�tigt keinen Einblick in die mathematischen Zusammenh�nge des zu optimierenden Systems. Stattdessen wird implizit eine eigenst�ndige Modellierung im Verlaufe eines Optimierungslaufes aufgebaut, indem aus Erfolgen und Mi�erfolgen von Tastschritten nach dem Modell der biologischen Evolution gelernt wird. Deshalb kann EPO insbesondere mit eigenst�ndigen Simulationsprogrammen zusammenarbeiten, die zun�chst �berhaupt nicht auf eine Optimierungsproblematik hin erstellt wurden.

Der evolution�re Grundalgorithmus erh�ht die Stabilit�t und Konvergenzsicherheit gegen�ber deterministisch arbeitenden Optimierungssystemen erheblich. EPO ist daher insbesondere bei schwierigen Fragestellung einsetzbar.

In der vorliegenden Shareware-Version k�nnen bis zu f�nf Parameter gleichzeitig bearbeitet werden, w�hrend die Vollversion nur durch den Hauptspeicherplatz beschr�nkt wird. Spezialisierte Versionen, die nicht durch ein allgemeines Schema abgedeckt werden k�nnen, sind auf Nachfrage erstellbar.

EPO setzt als Baukastensystem zu seiner Anwendung Programmierkenntnisse bei der Anbindung des externen oder neu zu programmierenden Simulators voraus. Beigelegte Programmschablonen (C-Quelltext) vereinfachen diese Aufgabe erheblich, so da� sich der Nutzer auf den wesentlichen Teil seiner Arbeit, die korrekte Simulation des zu optimierenden Systems, beschr�nken kann.

EPO setzt ein multitasking-f�higes Betriebssystem voraus. In der vorliegenden Version ist es f�r OS/2-PCs gedacht; eine Unix-Version wird momentan auf m�glichst viele Plattformen portiert. (Nein, eine Portierung auf DOS ist {\em nicht} vorgesehen!)

\end{abstract}

\newpage

\tableofcontents

%===================================================================
\vspace*{2cm}

\section{Einleitung: Naturanaloges Optimieren in der Technik}

\subsection{Optimierungsverfahren}
Damit ein Ding oder eine Methode in der Praxis eingesetzt oder angewendet werden kann, mu� es den Zweck, der seiner Entwicklung zugrunde lag, in einem hinreichenden Ma�e erf�llen. Wenn auch oft bei der Einf�hrung neuer Verfahren oder Ger�te deren Funktion noch nicht ganz ausgereift ist, wird sie doch im Laufe der Weiterentwicklung immer weiter verbessert, nicht zuletzt durch den Konkurrenzdruck alternativer L�sungsans�tze --- wobei wir schon fast bei der zugrundeliegenden Idee des hier beschriebenen Programmsystems w�ren, wenn auch in einem etwas anderen Zusammenhang.

Diese Verbesserung, ab jetzt Optimierung genannt, l��t sich mittels verschiedener Verfahren erreichen:
%
\begin{itemize}
	\item Man durchschaut als Entwickler eines neuen Verfahrens oder Ger�tes die zugrundeliegenden Zusammenh�nge und w�hlt kurz und genial die beste Vorgehensweise zum Erreichen des gew�nschten Ziels. Diese Art von Optimierung wird zwar in der Regel angestrebt, ist in der Praxis aber eher selten realisierbar.
	\item Man entwickelt zun�chst einen Prototyp des Ger�tes, testet diesen und �berlegt sich eine Reihe von Detailverbesserungen, die dann schrittweise am Prototyp ausprobiert werden. Dies d�rfte einer der meistgenutzten Vorgehensweisen bei einfachen und billigen Produkten sein.
	\item Man simuliert das Verhalten eines Systems rechnerisch und kann aufgrund der bekannten mathematischen Zusammenh�nge zwischen den das Verhalten bestimmenden Variablen mathematisch-analytisch die optimale Parameterkonstellation ermitteln. Einfachste Beispiele hierf�r sind die ber�hmt-ber�chtigten Minimum-Maximum-Aufgaben der Mathematikleistungskurse im Gymnasium.
	\item Eine analytische L�sung ist trotz mathematischer Modellierung nicht mehr m�glich, vielleicht, weil die gesuchte Zielfunktion (die zu optimierende Gr��e) nicht mehr als geschlossener Ausdruck angegeben werden kann. Bei dieser in vielen praktischen F�llen auftretenden Situation ist  man auf Suchverfahren angewiesen ist. �blicherweise werden diese aus der analytischen Extremwertsuche abgeleitet. Solche Verfahren werden in vielen Standardwerken des Operations Research und der allgemeinen Optimierungsmethodik diskutiert, z.B. auch in~\cite{ HoffHof} und~\cite{ Zach}.
	\item Man verzichtet auf die analytische Behandlung der Extremwertsuche und setzt Zufallsverfahren ein, um sich dem Optimum zu n�hern. Dies kann insbesondere dann interessant sein, wenn sich die interessierende Eigenschaft des zu optimierenden Systems verschiedene relativ gute Parameterkonstellationen besitzt (Suboptima) oder allgemein in komplizierter Form von den Parametern abh�ngen. In solchen F�llen laufen die aus der Analysis abgeleiteten Optimierungsverfahren h�ufig in die Irre und konvergieren nicht am Optimum, wie Praktiker sicher aus eigener Erfahrung best�tigen k�nnen.\\
Eine besondere Klasse von Verfahren kopiert die Vorgehensweisen der Natur und wird daher auch ``naturanaloge Optimierungsverfahren'' genannt. Hier finden sich verschiedene Ideen umgesetzt --- angefangen vom ``simulierten Ausgl�hen'', einem aus der Physik der Erstarrungsph�nomene abgeleiteten Paradigma~\cite{ Otto:SimAn}, bis hin zu den aus der Biologie entlehnten, sich an die Evolutionstheorie anlehnenden Verfahren~\cite{ Rieck:ModellNatur, Schwef:Opti}.
\end{itemize}

Zur letzteren Klasse der Optimierungsverfahren geh�rt auch der Algorithmus, der dem vorliegenden Optimierungsprogrammsystem zugrunde liegt und allgemein als Evolutionsstrategie bezeichnet wird. Er wird insbesondere durch die beiden Begriffe ``(zuf�llige) Mutation'' und ``(deterministische) Selektion'' beherrscht.

Er setzt nat�rlich voraus, da� das zu bearbeitende System in einer rechnersimulierbaren Form vorliegt. Es wurden jedoch auch schon F�lle in der Literatur diskutiert, in denen er in rein experimentell-praktisch durchgef�hrten Optimierungen eingesetzt wurde~\cite{ Rechen:Evolut}.



\subsection{Grundlegende Ideen des naturanalogen Optimierens}

Bevor weiter unten die Systembestandteile und die praktische Arbeit mit EPO beschrieben werden, m�chte ich kurz auf die Ideen der naturanalogen Optimierungsverfahren eingehen, da sie sich grundlegend von denen herk�mmlicher Verfahren unterscheiden.

Die biologischen Organismen haben sich zweifellos in faszinierender Weise im Laufe der Jahrmillionen von einfachsten Urformen zu fast unvorstellbarer Komplexit�t entwickelt. Trotz dieses enormen Komplexit�tszuwachses hat die Funktionalit�t in diesem Entwicklungsproze� stetig zugenommen --- fast im Gegensatz zu technischen Systemen, die bei wachsendem Komplexit�tsgrad meist zunehmend fehleranf�lliger werden%
\footnote{Jedem Leser d�rften hinl�nglich Beispiele aus dem eigenen Umfeld 
bekannt sein. \yeah}. %
Eine von naturwissenschaftlich-technischen L�sungsans�tzen ausgehende Erkl�rungsweise steht demnach vor einem zun�chst nicht aufl�sbaren Widerspruch.

Die Komplexit�t der biologischen Organismen hat viele dazu gef�hrt, die Welt als durch ein h�heres Wesen gesch�pft zu sehen. In der Tat l��t sich beispielsweise durch eine rein kombinatorische Rechnung nachweisen, da� die Wahrscheinlichkeit, das menschliche Erbmaterial in Form der Desoxyribonukle\"ins�uresequenzen durch reinen Zufall zu erzeugen, in naturwissenschaftlichen Ma�st�ben identisch null ist%
\footnote{Auf die Angabe einer ``exakten'' Zahl und eine mathematische Herleitung wird verzichtet, da sie im Zusammenhang dieser Arbeit uninteressant und in vielen biologischen und auch popul�rwissenschaftlichen Ver�ffentlichungen zu finden ist.}%
. Diese Betrachtungsweise ist jedoch nicht der Sache angemessen. Aus der gro�en Zahl unterschiedlicher Erbmaterialien ist zu erkennen, da� nicht nur genaue eine Sequenz die Auspr�gung brauchbarer Eigenschaften kodiert, sondern auch Variationen m�glich sind.

Weiterhin hat sich seit ihrer ersten Formulierung durch Darwin die Vorstellung einer Abstammungslehre, bedingt durch den Vorgang der Evolution, in der Biologie allgemein durchgesetzt. Ihre Richtigkeit wird heute nicht mehr in Zweifel gestellt, da im Laufe der Zeit �berzeugende Belege f�r ihre Richtigkeit gefunden wurden. In Verbindung mit der Entwicklungsphysiologie und der Genetik entstand in den letzten Jahrzehnten ein weitgehend l�ckenloses Erkl�rungsschema f�r die Vielf�ltigkeit unserer heutigen Welt~\cite{ Hoppe:Biophysik}.

Die grundlegende Fortentwicklung der biologischen Systeme geschieht demnach durch die Evolution, also durch das `Ausprobieren' neuer Varianten von Lebewesen, die sich meist nur in geringen Details von ihren Vorfahren unterscheiden. Da diese in unmittelbarer Konkurrenz zu den vorhandenen Ausf�hrungen der gleichen Spezies und den anderen Lebewesen stehen, sorgt eine nat�rliche Auslese (letztlich: Unterschiede in der Wahrscheinlichkeit, �berlebensf�hige Nachkommen in der Welt zu etablieren) daf�r, da� auf lange Sicht die jeweils bessere Auspr�gung einer speziellen Eigenschaft erhalten wird.

Darwin und seine unmittelbaren Nachfolger standen vor dem Problem, die von Generation zu Generation erfolgenden Modifikationen erkl�ren zu m�ssen. Der Mechanismus sowohl der �bertragung der unver�nderten wie auch der modifizierten Information von den Eltern auf ihre Nachkommen konnte erst seit der Kl�rung des Kodierungsverfahrens vererbungsdeterminierter Eigenschaften durch Watson, Crick und Nachfolger~\cite{ Hoppe:Biophysik} schl�ssig belegt werden.

Seit diesen grundlegenden Untersuchungen ist bekannt, da� sich wesentliche Teile der Evolution durch die Entwicklung und Weitergabe einer stetig komplizierter und umfangreicher werdenden Informationssequenz verstehen lassen. Damit lassen sich aber gewisse Parallelen zu mathematisch-kombinatorischen Problemen erkennen, die ebenfalls durch evolutionsstrategische Ans�tze l�sbar wurden, obwohl nachweisbar �hnliche Wahrscheinlichkeiten, die jeweiligen L�sungen `durch Zufall' zu finden, existierten wie in der oben angesprochen biologischen Problemstellung. Beispiele sind in gro�er Zahl in der Literatur zu finden, z.B.\ das ``Problem des Handlungsreisenden''~\cite{ Muehle:EvoAlgs}.

Die Idee der H�herentwicklung durch Evolution ausgef�hrter Systeme wird durch entsprechende Algorithmen auf technische Systeme �bertragen. Dieser Weg wurde in Deutschland erstmals Ende der sechziger Jahre von Rechenberg et.~al~\cite{ Rechen:Evolut}. beschritten. Insbesondere Schwefel und Mitarbeiter~\cite{ Kursaw:Vektor, Handelsreis, Schwef:Opti, Schwef:DirectSearch, Schw88, PPSN:1990} erweiterten den grundlegenden Algorithmus und entwickelten die urspr�nglichen Verfahren weiter.



\subsection{Grundlegende algorithmische Struktur der Evolutionsstrategie}

Entsprechend dem Vorbild der Natur betrachten Evolutionsverfahren nicht ein einzelnes zu optimierendes Ger�t/Verfahren, sondern �blicherweise eine {\em Population\/}  aus diesen. Eine solche Population wird aus {\em Individuen}, also ausgef�hrten Beispielen des Ger�tes/Verfahrens zusammengestellt, die sich in ihrem Genom, also den das Verhalten bestimmenden ``Erbanlagen'' voneinander unterscheiden.

Ein Beispiel mag diese vielleicht befremdlich anmutende Begriffsbildung erl�utern:

Will ich etwa die Energiekosten eines Hauses minimieren, kommen als (die Kosten) beeinflussende und (bei der Auslegung) beeinflu�bare Parameter unter anderen Mauerst�rke, Mauermaterial, Fensterverglasung, Heizungssystemauslegung, Fugendichtigkeit und Dachmaterialwahl in Betracht. Diese sechs Parameter stellen f�r ein einzelnes Baukonzept, also mein Individuum, die Erbanlagen dar und beeinflussen den hieraus resultierenden Zielfunktionswert ``Energiekosten''%
\footnote{Man beachte, da� ich hier bewu�t nicht den Energie-{\em verbrauch\/} des Hauses als Zielfunktion verwendet habe: Das Ergebnis einer Optimierung w�re trivial, es erg�be sich n�mlich jeweils das bestm�glich d�mmende Material. Durch die Ber�cksichtigung des Kostenaspekts wird sich aber ein praktisch verwertbares, nicht-triviales Ergebnis einstellen: Es bringt bei guter D�mmung praktisch keine Energieeinsparung mehr, die D�mmung weiter zu verbessern, kostet aber eine Menge Geld.} .%

In der Population sind nun unterschiedliche Individuen, d.h.\ unterschiedliche Zusammenstellungen der sechs Parameter vertreten, die hierdurch auch unterschiedliche Zielfunktionswerte besitzen. Als Analogie zu einem Tastschritt der deterministischen Optimierungsverfahren tritt bei den evolutionsstrategischen Verfahren die Bildung einer neuen {\em Generation.\/} Hierzu werden die (hinsichtlich Zielfunktionswert $Z$) $n$ besten Individuen ausgew�hlt und aus ihnen $m$ Nachkommen durch ein dem biologischen Rekombinationsproze� nachgebildetes Verfahren und zus�tzlicher zuf�lliger Variation der Parametereinstellungen erzeugt.

Je nach gew�hlter Strategievariante werden entweder die Eltern vollst�ndig verworfen (sog.\ Kommastrategie~\cite{ Schwef:Opti}) und bei der Auswahl der Eltern f�r die darauffolgende Generation ausschlie�lich die neuen Nachkommen ber�cksichtigt, oder die Eltern bilden mit den Nachkommen eine Gesamtpopulation, aus der nach Sortierung die neuen Eltern gewonnen werden(sog.\ Plusstrategie).

Wenn auch die Konvergenzqualit�t der Kommastrategie auf den ersten Blick fraglich erscheint --- werden doch einmal erreichte Optimierungserfolge u.U. durch Nicht-Weitergabe an die Nachkommen wieder Zunichte gemacht --- hat sie sich insbesondere in Verbindung mit der Selbstadaption der Suchschrittweiten als die bessere herausgestellt. In EPO ist daher derzeit nur diese Kommastrategie implementiert.

\bigskip

Ein Hinweis zum Schlu� dieser Einf�hrung: Auch EPO kann nicht zaubern und ist keine Wunderwaffe bei Optimierungsproblemen! Es wird F�lle geben, wo auch EPO nicht zum bestm�glichen Ergebnis f�hrt oder eine Optimierung einfach zu viel Zeit beansprucht, bevor sie zu einem sinnvollen Ergebnis f�hrt.

Dies ist dann aber nicht ein Fehler des Programms oder des Algorithmus, sondern einfach in der T�cke des Objekts bedingt. Und praktische Optimierungsprobleme sind oft t�ckisch $\ldots$

Es wird auch manche F�lle geben, in denen ein deterministischer Optimierer mit seiner gezielten Suche nach der besten Fortschrittsrichtung im Laufe einer Problembearbeitung schneller zu einem guten Ergebnis kommen wird. In solchen F�llen m�ge man diesen Methoden den Vorzug geben. EPO wird aber gerade dort interessant, wo diese deterministischen Verfahren bekannterma�en versagen.

Insbesondere, wenn auf einen schon existierenden, in sich geschlossenen Simulator zur�ckgegriffen werden mu�, damit also die innere Modellbildung der Simulation dem Optimierer zwangsl�ufig verborgen bleibt, greift die Methodik der evolution�ren Optimierung besonders gut. Und diese F�lle d�rften gar nicht so selten sein!



\subsection{Umsetzung der Evolutionsstrategie in ein Programmsystem}

Die in den Individuen verwalteten ``Erbanlagen'' --- also die momentanen Parametereinstelldaten --- stellen die gesamte Information dar, die zur Qualit�tsbestimmung eines Ger�tes/Verfahrens erforderlich ist. Sie wird �ber den oben erl�uterten Vererbungsmechanismus an die Nachkommen in modifizierter Form weitergegeben.

Hierzu werden sie vom Hauptmodul des Systems, dem sogenannten ``Optimierer'' anfangs aus einem Konfigurationsfile gelesen und  w�hrend des Optimierungslaufs verwaltet und bearbeitet. Der Optimierer ist auch f�r die Interaktion mit dem Benutzer zust�ndig und erstellt die Ergebnis- bzw.\ Fortschritttsreports.

Die genaue Strategie des evolution�ren Algorithmus kann durch Festlegung verschiedener Steuerparameter ebenfalls per Konfigurationsfile beeinflu�t werden und so auf unterschiedliche Probleme (insbesondere hinsichtlich der Abw�gung zwischen Optimierungs-Fortschrittgeschwindigkeit und der Konvergenzsicherheit bei multimodalen Problemstellungen) angepa�t werden.

\bigskip

Die Bestimmung des Zielfunktionswertes bei einer gegebenen Parameterkonstellation hat mit dem evolutionsstrategischen Teil des System nichts zu tun. Daher wurde der ``Simulator''-Teil komplett von diesem getrennt. Er kommuniziert mit dem Optimierer lediglich durch �bergabe von Daten- und Nachrichtenfiles.

Je nach konkreter Aufgabenstellung bieten sich verschiedene Wege zur Einbindung des Simulators an:
%
\begin{itemize}
	\item Der Simulator mu� als Programm neu erstellt werden:\\
F�r diesen Fall ist eine Programmschablone im Paket enthalten, das die gesamte Kommunikation mit dem Optimierer abwickelt und einen Unterprogrammrumpf namens \verb+rechne()+ bereitstellt, in dem die zu formulierende Simulation eingebracht werden kann. Der Zugriff auf alle Parameterwerte und deren Bezeichnungen ist hierbei gegeben.
	\item Es existiert ein fertiger Simulator f�r das zu optimierende System:\\
Hier sind �blicherweise Aufrufkonventionen des Simulatorprogramms zu beachten (z.B. �bergabe von speziell aufbereiteten Datenfiles, �bergaben per Kommandozeile, usw.). Auch f�r diesen Fall liegt eine Programmschablone bei die f�r den jeweiligen Anwendungsfall recht einfach angepa�t werden kann. Wiederum �bernimmt die Schablone die Kommunikation mit dem Optimierungsteil und stellt die aktuellen Parametereinstellungen bereit. Die Ansteuerung des externen Simulators mu� der interessierte Anwender dann noch im Unterprogramm \verb+rufe()+ hinzuf�gen.
\end{itemize}

Das Arbeiten mit diesen Systembestandteilen wird weiter unten, in Abschnitt~\ref{Arbeitsweise} und~\ref{Praxis} noch genauer erl�utert.



\section{Systembestandteile}

Wenn auch verschiedentlich von Anwendungen der naturanalogen Verfahren bei technischen Fragestellungen berichtet wird~\cite{ Doerin:Filter, Muelle:EvoBeisp,  Schmie:Mikrowelle}, ist mir bisher kein Anwendersystem bekannt, das sich relativ einfach und flexibel an konkret gegebene Problemstellungen anpassen l��t. Diesem Mi�stand soll mit EPO als modularem Optimierungssystem auf Basis der Evolutionsstrategie begegnet werden.

Im Sinne einer einfachen Anpa�barkeit an immer neue Problemstellungen wurde EPO modular aufgebaut. In der Shareware-Version sind alle Module der Vollversion enthalten, damit Sie die Flexibilit�t des Systems ausprobieren und absch�tzen k�nnen.

Das Programm ist so angelegt, da� es auf beliebige rechnersimulierbare Probleme anwendbar ist, solange das Betriebssystem des Zielrechners ein gleichzeitiges Abarbeiten von Simulations- und Optimierungsprogramm erlaubt. Auf der PC-Schiene bietet sich hierzu OS/2 als Betriebssystem an, jedoch ist das Programm praktisch ohne �nderung auf Unixmaschinen lauff�hig --- nat�rlich in einer umkompilierten Version! Ich bin zur Zeit dabei, EPO auf unterschiedlichste Unix-Plattformen zu portieren%
\footnote{Entsprechend sollten diese im Laufe der Zeit auf entsprechenden FTP-Servern auftauchen. Bei unmittelbarem Bedarf auf einer derzeit nicht unterst�tzten Plattform bitte ich darum, mich unmittelbar anzusprechen --- e-mail-Adresse siehe oben!}.

Zum Einstieg in die praktische Optimierungsarbeit sind dem Paket Problembeispiele beigelegt, die als Funktionstest des installierten Systems verstanden werden k�nnen.In Abschnitt~\ref{Praxis} wird noch ausf�hrlich erkl�rt, wie eigene Problemstellungen mit diesem Programmsystem bearbeitet werden k�nnen. Dies setzt eine gewisse Programmiererfahrung voraus, weil eine definierte Schnittstelle zwischen dem Optimierungsmodul und dem das Problem beschreibenden Simulator eingehalten werden mu�. Diese ist aber so einfach gehalten, da� keine allzugro�en Schwierigkeiten bei der Implementation auftreten d�rften.

\bigskip

Kern des Systems ist das Programm SHOPTI.EXE%
\footnote{SHOPTI.EXE ist der Name der OS/2-Version. Entsprechende Unix-Executables sind entsprechend SHOPTI genannt. Im folgenden gilt f�r diese Module das gleiche, was f�r die OS/2-Version gesagt wird, es sei denn, es wird explizit auf Unterschiede hingewiesen}, %
das durch einen RENAME-Aufruf aus der Datei SHOPTI.BIN erzeugt wird. 

Ich gebe zu, das diese Vorgehensweise vielleicht ein wenig hinterh�ltig ist. Ich m�chte aber um Verst�ndnis f�r diesen Weg bitten, weil ich nicht glaube, da� irgendjemand ohne Lesen dieser Anleitung mit dem Programmsystem irgendetwas anfangen kann. Und bevor sinn- und kontextlos eine .EXE-Version aufgerufen wird, wollte ich den potentiellen Benutzer auf diese Weise an diesen Anleitungstext heranf�hren.

SHOPTI.EXE ist das eigentliche Optimierungsmodul, das die gesamte Steuerung �bernimmt und den Ergebnisreport generiert. Es enth�lt den wesentlichen, evolutionsstrategischen Algorithmus.

In der Shareware-Version erlaubt EPO eine Maximalzahl von 5 Variablen. Dies ist eine Einschr�nkung der Funktionalit�t --- gewi�! Aber bevor nun der Ruf ``{\em Crippleware!}'' erschallt: Es gibt sehr viele Optimierungsprobleme, die trotz geringer zu bearbeitender Parameterzahl f�r deterministische Optimierer eine harte Nu� darstellen und die mit EPO gel�st werden k�nnen! Au�erdem m�chte ich am Einsatz von EPO bei gr��eren Problemen auch gerne etwas verdienen. Zum Test der M�glichkeiten und der Funktionsweise wird die vorliegende Version auf jeden Fall ausreichen.

\bigskip

Das Programm SIMU.EXE ist gleicherma�en aus der Datei SIMU.BIN zu erzeugen. Es bildet den Gegenpart zum Optimierungsmodul SHOPTI.EXE und ist ein ausgef�hrter Simulatorkern f�r ein Musterproblem. Als Beispiel wurde die Suche nach dem Minimalwert einer multidimensionalen quadratischen Funktion eingebaut.

Der Quelltext zu diesem Modul ist ebenfalls beigelegt und unter SIMU.C zu finden. Darin besteht die M�glichkeit, eine eigene Problemstellung in Form eines C-Unterprogramms im Austausch gegen das Beispiel zu formulieren, ohne sich um die �bergabe der Parameter- und Ergebnisdatei an das Optimierungsmodul k�mmern zu m�ssen. Der Zugriff auf die Parameter-Datenstrukturen wird anhand des Beispiels vorf�hrt und sollte beim Umschreiben auf eigene Zielfunktionen kein Problem darstellen.

\bigskip

Zur Ansteuerung komplett unabh�ngiger, eigenst�ndiger Simulatorprogramme sind dessen Eigenarten zu ber�cksichtigen, insbesondere bez�glich der Aufbereitung der zu �bergebenden Parameter. Grunds�tzlich ist dies auch �ber eine entsprechende Modifikation von SIMU.C zu erreichen. Ich m�chte Ihnen das Leben jedoch noch etwas einfacher machen und stelle hierzu eine weitere Schablone zur Verf�gung: TRANS.C bzw.\ als fertiges Kompilat TRANS.EXE, das auch wieder durch ein Rename aus TRANS.BIN zu erzeugen ist.

Es steuert in der vorliegenden Form den ``Simulator'' GAUSSFIT.EXE (ja, sie haben es schon erraten$\ldots$) an, der die bezogene Fehlerquadratsumme einer gefitteten Gau�glockenfunktion an eine Me�datenschar berechnet. Hierzu sind GAUSSFIT.EXE f�nf Kommandozeilen-Parameter beim Aufruf zu �bergeben:
%
\begin{enumerate}
	\item Der Name einer Datei, in der die Me�punkteschar in der Form \{x-Wert, y-Wert\} jeweils in einer Zeile beschrieben ist (Maximalzahl 99 Me�punkte). Sie finden eine solche Me�daten-Beispieldatei unter dem Namen REIN.
	\item Die H�he der vorgeschlagenen Fit-Gau�glocke.
	\item Der Mittenwert der vorgeschlagenen Fit-Gau�glocke.
	\item Die Standardabweichung der vorgeschlagenen Fit-Gau�glocke.
	\item Der Name einer Ausgabedatei, in der GAUSSFIT.EXE (unter anderem) die berechnete Fehlerquadratsumme ablegt.
\end{enumerate}

F�r diesen vielleicht etwas exotisch anmutenden Programmaufruf stellt nun das beigelegte TRANS.* die Anpassung der Durchrechen-Anforderung des Optimierers dar, indem die erforderlichen Parameter aus dem vom Optimierer geschriebenen �bergabefile entnommen werden, und mit den (den Optimierer nicht interessierenden) Details zu einem Simulatoraufruf zusammengestellt werden. Schlie�lich wird nach fertiger Bearbeitung des eigentlichen Simulatorlaufs die R�ckgabedatei nach der interessierenden Fehlerquadratsumme durchsucht und diese in die an den Optimierer zu verschickende Datenstruktur �bertragen.

\bigskip

Des weiteren sind Steuerdateien vorhanden: STRATEG.DAT und CONDITIO.DAT
Deren Bedeutung wird weiter unten ausf�hrlich beschrieben.

Da das Programmsystem mit dem EMX-Compiler erstellt wurde, erfordert es EMX.DLL im Libpath. Auch diese Datei ist im Paket enthalten, wenn auch die meisten Anwender bereits eine Version haben sollten.

Bei Produktionl�ufen des Optimierungssytems werden noch weitere Dateien erzeugt, deren Bedeutung und Namen weiter unten diskutiert werden. Sie sind in der Regel nicht umfangreich (typischerweise Tempor�rdateien $<$ 2 kB, Ergebnisdateien $<$ 200 kB) und sollten die Plattenkapazit�t wohl nicht vor Probleme stellen.



\section{Kurzeinf�hrung in die Arbeitsweise}
\label{Arbeitsweise}

\subsection{Allgemeiner Ablauf eines Optimierungslaufs}

Das Vorgehen bei der Bearbeitung eines Optimierungsproblems ist grunds�tzlich immer gleich. Zun�chst mu� das Simulatormodul �ber eine �bergabeschnittstelle an das Optimierungsmodul angeschlossen werden, z.B.\ in Form einer direkten Formulierung des Simulationsteils im Unterprogramm \verb+rechne()+ des beigelegten SIMU.C

Steht bereits ein fertiger Simulator zur Verf�gung, der sich durch ein Kommando starten l��t und dann ohne interaktive Eingriffe bis zu einem Endergebnis durchl�uft, mu� dieser durch ein die Parameter�bergabe aufbereitendes Mittlerprogramm angesprochen werden. Hierzu kann TRANS.C als Schablone dienen.

Auch die Extraktion der R�ckgabewerte und ggf.\ der daraus zu ermittelnde, eigentliche Zielfunktionswert sind vom Mittlermodul zu leisten, das hierzu auf das Erscheinen des Simulator-Ergebnisfiles warten mu�. Auch diese Funktionalit�t ist in TRANS.C bereits vorgesehen.

Schlie�lich sind die Randbedingungs- und die Strategieparameter-Datei dem Probem anzupassen. Dies ist ausf�hrlich in den nachfolgenden Kapiteln geschildert.

\bigskip

Nachdem diese Vorbereitungen getroffen sind, wird der Optimierer durch Anklicken oder Kommandozeilen-Aufruf gestartet. Er meldet sich mit einer Einschaltmeldung und ruft seinerseits den (im Strategiefile angegebenen) gew�nschten Simulator als eigenst�ndig laufenden Proze� auf.  Auch der Simulator gibt in seinem Fenster (ggf.\ nach vorne holen!) eine Einschaltmeldung aus und kann f�r Kontrollausgabezwecke nach Einbau entsprechender Ausgabetexte zur Sichtkontrolle dienen.

Insbesondere der Optimierer gibt durch eine Reihe von Kontrollausgaben an, ob er die Startdateien korrekt eingelesen hat. Im Lauf der Optimierung werden pro Generation die gew�nschte Anzahl von Besten aus der Bestenliste angezeigt. Daran ist der Fortschritt der Optimierung unmittelbar zu erkennen.

Zwischen Optimierer und Simulator werden st�ndig Dateien transferiert --- jeweils eine Daten-Datei (O2S.DAT bzw. S2O.DAT, je nach Richtung) und eine Flag-Datei (*.MSG), die sicherstellt, da� das wartende Programm erst auf die Datendatei zugreift, wenn sie fertig geschrieben ist%
\footnote{Leider scheint unter den Multitasking-Betriebssystemen OS/2 und Unix unter gewissen Umst�nden das Schlie�en einer Datei druch den schreibenden Proze� nicht immer mit deren Verf�gbarkeit f�r einen Leseproze� einherzugehen, wie sich insbesondere bei gr��eren Transferdateien gezeigt hat. Daher wurde gegen�ber EPO 0.1 eine Validit�tspr�fung eingebaut, die adaptiv arbeitet und jeweils die minimal erforderliche Verz�gerungszeit f�r st�rungsfreie Interaktion von Optimierer und Simulator einstellt.}. %
Die Flag-Dateien haben keinen Inhalt, nur ihre Existenz ist von Bedeutung.

\bigskip

Der Optimierer kann interaktiv angehalten werden, indem bei aktivem Optimiererfenster die Taste ``q'' gedr�ckt wird. Diese Tastatureingabe wird jedoch nur am Ende einer Simulatorberechnung ausgewertet, so da� das tats�chliche Beenden des Programms, je nach Laufzeit des Simulators, erst einige Zeit nach Dr�cken der Taste stattfindet.

In der Unix-Version ist eine Tastatureingabe nach Verbannen des Optimierers in den Hintergrund und vor�bergehenden Verlassens des Systems nicht mehr m�glich. Daher wird dort statt der Tastatur das Vorhandensein eines Files namens ``stop'' im Arbeitsverzeichnis des Optimierers abgefragt, dessen Existenz als Abbruchbedingung interpretiert wird. Er kann �ber eine zus�tzliche Kommandozeile z.B. durch den Befehl ``touch stop'' erzeugt werden. Hierbei ist aber darauf zu achten, da� die Datei im Arbeitsverzeichnis des Optimierers erzeugt werden mu�.

Wird der Optimierer auf diese Weise geordnet verlassen, wird auch der Simulator automatisch beendet, und es werden noch verbliebene �bergabefiles entfernt, so da� Betriebs- und Dateisystem in einem ges�uberten Zustand hinterlassen werden.

Ganz eilige k�nnen nat�rlich auch Optimierer und Simulator jeweils per <Ctrl-C> einzeln abbrechen, m�ssen dann jedoch selbst f�r das Aufr�umen im Dateisystem sorgen. Insbesondere f�hren nicht korrekt gel�schte Parameter- bzw.\ R�ckgabedateien zu einem Versatz zwischen den zur Berechnung an den Simulator �bergebenen Variablens�tzen und den dazu zuzuordnenden Ergebnissen, die zu einer St�rung des Systems f�hren. Au�erdem kann bei erneutem Start der Optimierung eine versehentlich verbliebene Nachrichtendatei zum sofortigen Abbruch des Simulators f�hren.

Die Optimierungsergebnisse werden zur nachfolgenden Analyse in zwei Dateien festgehalten, die in Kap.~\ref{strateg.dat} erl�utert werden.



\subsection{Steuerung durch die Variablen-Definitionsdatei CONDITIO.DAT}
\label{conditio}

Die Datei CONDITIO.DAT enth�lt die f�r die Definition des Optimierungsproblems wesentlichen Informationen �ber Zahl und Anfangswert der Variablen, sowie explizite Definitionsbereichsgrenzen.

\bf
Es ist sehr wichtig, da� die Eintr�ge dieser Datei in der korrekten Reihenfolge und vollst�ndig eingegeben werden. EPO Version~0.5 enth�lt keine automatische �berpr�fung, ob die eingegebenen Daten korrekt eingetragen wurden. 
\rm

Die Daten werden mit einfachen String- bzw.\ Zahlen-Einleseroutinen in C gelesen. Dementsprechend ist die Anzahl der Leerstellen zwischen den Eintr�gen unwichtig, genauso wie die Anzahl der Leerzeilen. In der vorliegenden Form des Optimierers erfolgt keine Validit�tspr�fung. Das Optimierungsmodul gibt lediglich eine Statusmeldung �ber die eingelesenen Daten auf dem Bildschirm aus, an der der Benutzer die Eingabedaten-Interpretation �berpr�fen kann.

Ein typischer Dateiaufbau ist folgender (die Zeilennummerierung ist im Original wegzulassen und dient hier nur der Erkl�rung):

\begin{verbatim}
1:   Example-1
2:   Para_number   3
3:   Name        Value   L.Limit   U.Limit
4:   Variable1   20     -1        50.45
5:   Variable2   13.5   -5        25
6:   Variable3   -4.3   -10       25.4
\end{verbatim}

Zeile 1 enth�lt den Namen des Optimierungsproblems (ein Wort ohne Leerzeichen). Er wird als ein Wort eingelesen und sp�ter in den Ausgabedateien als Kennzeichnung vermerkt.

Zeile 2 enth�lt das Kennwort ``Variablenzahl'' und die entsprechende Zahl (als Ganzzahl). Diese Anzahl von Zeilen wird eingelesen, nachdem in $\ldots$

Zeile 3 die �berschriften der entsprechenden Spalten als Erinnerungsst�tze erwartet, aber �berlesen werden.

Zeilen 4 bis 6 enthalten schlie�lich die Variablendefinitionen. In der ersten Spalte ist wiederum ein einzelnes Wort als Name einzutragen, in der zweiten Spalte der Anfangswert. Spalte 3 und 4 sind schlie�lich Unter- und Obergrenze der jeweiligen Variablen. Soll ein Definitionsbereich unbegrenzt sein, sind entsprechend gro�e positive bzw.\ negative Zahlen einzugeben. (Bitte denken Sie daran, da� in der Shareware-Version maximal f�nf Variable bearbeitet werden k�nnen. Sie k�nnen zwar weitere eintragen, doch werden sie nicht ber�cksichtigt.)


\subsection{Steuerung durch die Strategie-Definitionsdatei STRATEG.DAT}
\label{strateg.dat}

Die Datei STRATEG.DAT enth�lt die f�r die Ablaufsteuerung des Optimierungsmoduls wesentlichen Informationen �ber die Wahl des Simulators, Populationsgr��e, Gr��e der Bestenliste, Art der Fortpflanzung, Wahl der Ergebnis- und Transferfiles, sowie zwei weitere Strategieparameter, die weiter unten noch besprochen werden.

\bf
Es ist sehr wichtig, da� die Eintr�ge in der korrekten Reihenfolge und vollst�ndig eingegeben werden. EPO Version~0.5 enth�lt keine automatische �berpr�fung, ob die eingegebenen Daten korrekt eingetragen wurden. 
\rm

Die Daten werden mit einfachen String- bzw.\ Zahlen-Einleseroutinen in C gelesen. Dementsprechend ist die Anzahl der Leerstellen zwischen den Eintr�gen unwichtig, genauso wie die Anzahl der Leerzeilen. Eine Validit�tspr�fung der eingelesenen Daten findet in EPO Version~0.5 nicht statt. Das Optimierungsmodul gibt lediglich eine Statusmeldung �ber die eingelesenen Daten auf dem Bildschirm aus, an der der Benutzer die Eingabedaten-Interpretation �berpr�fen kann.

Ein typischer Dateiaufbau ist folgender (die Zeilennumerierung ist im Original wegzulassen und dienen hier nur der Erkl�rung):

\begin{verbatim}
 1: EPO-0.5
 2: minimize
 3: simulator_name     simu
 4: optidelay          400
 5: individual_number  30
 6: best               5
 7: inbreeding         1
 8: display            5
 9: result_file        Erg1.out
10: history_file       Gra1.out
11: transfer_dir       g:\
12: tau0               0.3
13: tau1               2
14: init_var         0.1
15: auto_stop          300
\end{verbatim}

Zeile 1 enth�lt das Wort EPO-0.5 als Kennung, da� es sich um eine Strategieparameterdatei zur richtigen Version von EPO handelt.

In Zeile 2 k�nnen die Schl�sselw�rter ``maximize'' oder ``minimize'' eingetragen werden. Entsprechend wird im Optimierungslauf nach maximalem oder minimalem Wert sortiert.

In Zeile 3 wird der gew�nschte Simulator angegeben, der automatisch vom Optimierer aus gestartet wird. Der Name mu� so eingetragen werden, wie er als Programmstart-Aufruf in einer Kommandozeile geschrieben werden m��te. Da �blicherweise der Simulator im gleichen Verzeichnis wie der Optimierer liegt, reduziert sich in diesem Fall der Eintrag schlicht auf den Namen des Simulators ohne zus�tzliche Pfadangaben.

Der Eintrag in Zeile 4 definiert die Pause, die der Optimierer nach einem erfolglosen Leseversuch des Nachrichtenfiles vom Simulator einlegt. Die Angabe erfolgt in Millisekunden%
\footnote{In der Unix-Version steht typischerweise kein Millisekunden-Timer zur Verf�gung, sondern ein Sekunden-Timer. Daher wird in dort die Millisekundenangabe in eine Sekundenangabe umgesetzt: z.B. 2340~ms $\rightarrow$ 2~s).}. %
Insbesondere bei langlaufenden Simulatorprogrammen ist es verschwendete (Rechen-)Zeit, den Optimierer pausenlos nachschauen zu lassen. Selbst bei kurzlaufenden Simulatorprozessen ist eine Wartezeit von ca. 0.5~s sinnvoll.

In Zeile 5 wird nach dem Kennwort die Anzahl der Individuen in der Population eingetragen; Zeile 6 enth�lt die Angabe der Anzahl bester Individuen, die als Elternpopulation in die n�chste Generation �bernommen werden. Im vorliegenden Beispiel werden also pro Generation die f�nf besten Individuen �bernommen und weitere 25 Individuen neu erzeugt.

In Zeile 7 wird angegeben, ob Nachkommen ausschlie�lich aus einer Rekombination zweier unterschiedlicher Individuen entstehen d�rfen (inbreeding 0) oder auch durch die (zuf�llige) Wahl des selben Individuum, somit durch reine Mutation (inbreeding 1) gebildet werden k�nnen.

In Zeile 8 wird die Anzahl der pro Generation darzustellenden Bestenzahl eingetragen. W�rde die angezeigte Individuenzahl immer gleich der Gr��e der Bestenliste gesetzt, k�nnte bei einer umfangreichen Bestenliste und einem kleinen Anzeigefenster gerade der interessierende Kopfbereich beim Anzeigen zu schnell aus dem Blickfeld verschwinden. Der Eintrag einer kleinen Zahl in dieser Zeile verhindert dies.

Zeile 9 enth�lt den Dateinamen, in den die jeweils beste Parameterkonstellation, sozusagen als Denkmal, abgelegt wird. Der Eintrag wird als komplette Pfadangabe verstanden und kann daher auch eine explizite Laufwerksangabe beinhalten.

Zeile 10 enth�lt den Namen der Datei, an die jeweils bei einer absoluten Verbesserung eine Zeile mit Nummer der Generation und dem Bestwert der Zielfunktion angeh�ngt wird. Er wird wie der Eintrag in Zeile 9 interpretiert. Hiermit ist im Nachhinein der Optimierungsfortschritt im Laufe der Generationen nachzuvollziehen.

Zeile 11 gibt das Verzeichnis an, in dem die zwischen dem Simulator und dem Optimierer ausgetauschten Transferfiles abgelegt werden. Steht eine RAM-Disk im System zur Verf�gung, kann diese sinnvollerweise hierzu eingesetzt werden --- die Transfergeschwindigkeit wird so maximiert, die Festplattenaktivit�t minimiert. Die eingetragene Zeichenkette wird den Dateinamen der Transferfiles vorangestellt und ist dementsprechend zu w�hlen.

Zeilen 12 und 13 enthalten zwei Steuerparameter, die f�r ein Fein-Tuning des Optimierungsfortschritts eingesetzt werden k�nnen. Werte f�r beide Parameter $tau0$ und $tau1$ zwischen 0.2 und 2.0  sind generell empfehlenswert. Bei wiederholtem Durchrechnen gleicherma�en gestalteter Optimierungsprobleme kann durch Variation eine gewisse Konvergenzbeschleunigung erreicht werden, allerdings unter Umst�nden auf Kosten der Konvergenzsicherheit bei multimodalen Problemen.

In Zeile 14 wird die anf�ngliche Variationsbandbreite der neu zu erstellenden Population angegeben. Der hier einzutragende Wert ist als als relative Abweichung gegen�ber den Anfangswerten der Variablen, definiert in CONDITIO.DAT (siehe Abschnitt~\ref{conditio}), zu verstehen. Es ist nur eine globale Angabe m�glich, die f�r alle Variablen gleicherma�en gilt.

Zeile 15 enth�lt schlie�lich eine Angabe �ber die maximale Anzahl von Generationen, in denen nacheinander keine Verbesserung erreicht wurde. Wird diese Zahl �berschritten, beendet der Optimierer seine Arbeit und stoppt auch den Simulator.



\section{Erste Versuche mit beigelegten Beispielproblemen}

Einen ersten Einstieg in die Funktionsweise von EPO erhalten Sie mit den beigelegten Beispielproblemen:

\begin{itemize}
	\item {\bf Erstes Beispiel: Programmierter Simulator --- Mehrdimensionale Quadratsummen-Minimierung}
	\item Bennenen Sie alle Dateien mit der Endung BIN in solche gleichen Namens, aber mit der Endung EXE um. (Also z.B.: \verb+ren shopti.bin shopti.exe+)
	\item Schauen Sie Sich die Dateien CONDITIO.DAT und STRATEG.DAT an. Versuchen Sie, anhand der obigen Erl�uterungen die Eintr�ge zu verstehen. In den Beispieldateien werden drei Variablen mit relativ begrenzten Definitionsbereichen behandelt. Als �bergabe-Verzeichnis dient das aktuelle Arbeitsverzeichnis. Als Simulator ist SIMU(.EXE) voreingestellt.
	\item Starten Sie den Optimierer SHOPTI.EXE.
	\item Beobachten Sie dessen Ausgabefenster: Nach der Einschaltmeldung werden die eingelesenen, zu bearbeitenden Variablen zur Kontrolle angezeigt.
	\item Zun�chst wird eine erste Elterngeneration gebildet, erkennbar an der entsprechenden Kontrollausgabe.
	\item Dann beginnt die sich immer wiederholende Schleife: Erzeugung neuer Individuen, Verschicken an den Simulator, R�cknahme der Ergebnisse, Sortierung der Individuen nach Zielfunktionswert, ggf.\ Schreiben neuer Ergebnisdateien, Anzeige des momentanen Optimierungsstandes.
	\item Brechen Sie den Programmlauf wahlweise durch Eingabe von ``q'' ab oder warten Sie, bis die angegebene Zahl von Generationen (im Beispiel: f�nf) keine weitere Verbesserung mehr erreicht wurde und der Optimierer von selbst stoppt.
	\item Schauen Sie Sich die Ergebnisdatei (im Beispiel: ERG1.OUT) an, um die beste gefundene Einstellung der Variablen abzufragen. In der Historiendatei (im Beispiel: GRA1.OUT) k�nnen Sie die Entwicklung des Zielfunktionswertes nachvollziehen: Bei jeder absoluten Verbesserung wird jeweils eine Eintragszeile hinzugeschrieben, in der Generation und Wert notiert werden. Durch einen Datenplotter (z.B. GnuPlot) kann diese Datei sehr einfach in eine graphische Darstellung des Optimierungsfortschrittes umgesetzt werden.
	\item {\bf Zweites Beispiel: Aufruf eines externen Simulators --- Gau�fit}
	\item �ndern Sie in der Datei STRATEG.DAT den Eintrag ``simu'' in ``trans'' um.
	\item �ndern Sie dort auch die Eintr�ge ERG1.OUT und GRA1.OUT in Ihnen genehme Dateinamen um (sonst werden die alten Dateien �berschrieben bzw.\ verl�ngert).
	\item Starten Sie erneut den Optimierer.
	\item Holen Sie das Fenster von TRANS.EXE nach vorne und beobachten Sie die von GAUSSFIT im Fenster von TRANS erzeugten Kontrollausgaben (eingelesene Me�werte, dazu berechnete Gau�glockenwerte entsprechend den �bergabeparametern, Fehlerquadratsumme, schlie�lich bezogene Fehlerquadratsumme als R�ckgabewert.)
	\item Beobachten Sie wieder die Entwicklung des Optimierungserfolges im SHOPTI-Fenster und brechen Sie den Lauf nach Wunsch ab.
\end{itemize}

Beim regul�ren Abbruch des Programmlaufs (durch ``q'' oder Erreichen der Abbruchbedingung) wird eine weitere Datei erzeugt: STATUS.ERG. Sie ist strukturell gleich der Ergebnisdatei, enth�lt aber den bei Abbruch vorliegenden Stand der Population. Sie kann gelegentlich f�r einen Vergleich mit den absoluten Bestwerten herangezogen werden.



\section{Aus der Praxis: Anpassung an ``echte'' Problemstellungen}
\label{Praxis}
	
Die Anwendung von EPO auf reale Problemstellungen erfordert prinzipiell einen geringen Programmieraufwand. Um diesen zu minimieren, habe ich die beiden Schablonen SIMU.C und TRANS.C beigelegt, die bereits die Interaktion von Simulator und Optimierer �bernehmen und beispielhaft den Aufruf eines externen, komplett eigenst�ndigen Simulators �bernehmen.

Alle Programmteile wurden mit dem EMX-System von E. Mattes erstellt und auf Funktionst�chtigkeit �berpr�ft. Dies nicht zuletzt, weil der zugrundeliegende C-Compiler mittlerweile zu einem Standardcompiler in der Unix-Welt avanciert ist und somit eine gute Grundlage zur Portierung auf andere Plattformen darstellt.

Nat�rlich k�nnen auch andere Compilersysteme verwendet werden, nur sind dann ggf.\ die INCLUDE-Dateien einer anderen Bibliotheksstruktur anzupassen. Ich habe mich aber bem�ht, nach M�glichkeit nur einfachste Grundoperationen zu verwenden, die in allen Systemen zur Verf�gung stehen sollten.

Beim Gnu-C-Compiler (Sparc) und dem EMX-System (OS/2) ist beim Linken des Simulators eine explizite Angabe der Mathe-Bibliothek erforderlich. Schauen Sie ggf.\ in den zugeh�rigen Handb�chern nach!



\subsection{Direkte Programmierung eines Simulators}

Bei erforderlicher Neuprogrammierung eines Simulators kann SIMU.C als Basis verwendet werden und �bernimmt die gesamte Kommunikation mit dem Optimierer. Der neu zu programierende Simulatorkern ersetzt dann das Beispielproblem im Unterprogramm \verb+rechne()+.

Die Anzahl der zu bearbeitenden Parameter steht in der Variablen \verb+Parazahl+ zur Verf�gung.

Die aktuellen Variablenwerte werden im der Struktur \verb+Indi+ als \verb+Indi.koeff[i]+ zur Verf�gung gestellt. Das Simulatorergebnis ist bei Verlassen von \verb+rechne()+ in der Variablen \verb+Indi.Ergebnis+ zum R�ckversand an den Optimierer bereitzustellen.

Auch die weiteren Eintr�ge von \verb+Indi+ werden durch die Informationen aus dem Optimierer initialisiert, doch sind diese teilweise historisch bedingt bzw.\ werden in einer kommenden Version verwendet werden, die echtes Multi-Processing auf verschiedenen PCs gleichzeitig unterst�tzen wird. Daher bitte diese Eintr�ge nicht benutzen, aber auch nicht �ndern, da sie an den Optimierer zur�ckgegeben werden.

Falls erforderlich, stehen die Variablennamen �ber \verb+Limits[i].Name+  zur Verf�gung; die restlichen Eintr�ge in diesem Feld sind nicht initialisiert!



\subsection{Anbindung eines externen Simulators �ber beigelegtes Hilfsprogramm}

Steht bereits ein eigenst�ndiger Simulator f�r das zu optimierende System zur Verf�gung, kann TRANS.C als Basis f�r die Transferabwicklung zwischen Optimierer und Simulator verwendet werden. Auch hier ist die Kommunikation zwischen TRANS und SHOPTI bereits fertig implementiert, so da� nur der Aufrufteil f�r den externen Simulator nachbearbeitet werden mu�. Dies ist im Unterprogramm \verb+rufe()+ zu erledigen.

Die Bereitstellung der jeweils aktuellen Variablendaten erfolgt mit den gleichen Datenstrukturen und unter den gleichen Bedingungen wie im Programm SIMU.C, daher bitte dort das Procedere nachlesen.



\section{Fehlersuche}

Wegen der geringen Fehlertoleranz der Einleseroutinen von EPO sind durchaus Laufzeitfehler m�glich, die einen Optimierungslauf st�ren oder unm�glich machen. Da jedoch alle Schnittstellen zwischen den Programmodulen als ASCII-Textdateien ausgef�hrt sind, ist eine Fehleranalyse anhand der jeweiligen Eintr�ge m�glich.

Insbesondere empfiehlt es sich in einem solchen Fall, die Programme nach Bereitstellung der erforderlichen Datenfiles jeweils einzeln zu starten, um deren Verhalten und deren Antwortfile-Generierung beobachten zu k�nnen. Bei SHOPTI ist ein Einzelstart nicht ohne weiteres m�glich, da es ja automatisch den Simulator aufruft. Hier hilft es, einen nicht-existenten Namen als Simulatorbezeichnung in die STRATEG.DAT einzutragen. SHOPTI gibt dann beim mi�lungenen Startversuch des Simulators einen Fehler an, der aber auf den weiteren Ablauf keine Auswirkungen hat. Auf diese Weise endet die Arbeit von SHOPTI nach Schreiben der �bergabefiles, da keine R�ckmeldung erfolgen kann. Das Programm kann nun abgebrochen werden.

Die folgende �bersicht gibt an, welche Dateien bei Start eines Einzelprogramms vorhanden sein m�ssen, welche erzeugt werden und welche einen normalen Programmlauf evtl.\ st�ren k�nnen:

\vspace{1cm}

\begin{tabular}{|llll|}
\hline
Programm im Test	& notwendig		& erzeugt	& st�rend \\
\hline
SHOPTI		& STRATEG.DAT	& O2S.DAT	& S2O.DAT\\
			& CONDITIO.DAT	& O2S.MSG	& S2O.MSG\\
			&			& (ERG.OUT)	&	\\
			&			& (GRA.OUT)	&	\\
\hline
SIMU			& STRATEG.DAT	& S2O.DAT	& (falsches O2S.DAT) \\
			& O2S.MSG		& S2O.MSG	&\\
			& O2S.DAT		& 		& \\
\hline
TRANS			& STRATEG.DAT	& S2O.DAT	& (falsches O2S.DAT) \\
			& O2S.MSG		& S2O.MSG	&\\
			& O2S.DAT		& 		& \\
			&			&		& (Ausgabefile)\\
\hline
\end{tabular}

\vspace{1cm}

Bei SHOPTI werden die eingeklammerten Dateien nicht notwendigerweise erzeugt, bei SIMU und TRANS k�nnen falsche Eintr�ge in der O2S.DAT zu sofortigem Abbruch f�hren. In dem Fall ist zu pr�fen, ob als zu bearbeitende Parameterzahl eine ``0'' angegeben ist, was einem Ende-Befehl f�r das Simulator/Transferprogramm bedeutet.

Vorsicht bei der Einbindung eines externen Simulators �ber TRANS: Systembedingt kann ein vom externen Simulator an TRANS zur�ckgelieferter Datenfile nicht automatisch vom Optimierer mit aufger�umt/entfernt werden, weil ihm hierzu keine Informationen vorliegen! Entweder mu� der Anwender dies in TRANS an der entsprechenden Stelle einbauen (dort, wo die Abfrage auf gew�nschten Programmabbruch stattfindet) oder aber nach Beenden eines Optimierungslaufs die fragliche Datei von Hand l�schen.

Geschieht dies nicht, ergibt sich ein Versatz zwischen der dem externen Simulator zur Durchrechnung �bergebenen Parametereinstellung und dem von TRANS eingelesenen R�ckgabewert, der die Interpretierbarkeit des Ergebnisses zerst�rt. Dieses Problem ist generell nicht umgehbar, da --- im Gegensatz zum Datenaustausch zwischen TRANS und SHOPTI --- kein zus�tzlicher Nachrichtenfile die Synchronisierung der Parameter�bergabe �bernimmt.

Der Aufbau der zwischen SHOPTI und SIMU/TRANS ausgetauschten Datenfiles ist selbsterkl�rend und braucht hier nicht weiter diskutiert zu werden. 



\section{Versions-Logbuch und Ausblick}

Die Version 0.1 wurde im M�rz 1994 zun�chst nur lokal in einer Mailbox ver�ffentlicht und fast unmittelbar durch die Version 0.2 ersetzt.

Erg�nzungen und Korrekturen in EPO 0.2:
\begin{itemize}
	\item �bergabeproblem zwischen Optimierer und Simulator (tempor�re Inkonsistenz des Filesystems) wurde durch �berpr�fung der Anzahl korrekt gelesener Eintr�ge beseitigt.
	\item Erforderliche Wartezeit bis zur Konsistenz des Filesystems wird kontinuierlich adaptiv auf Minimalwert angepa�t.
	\item Es wurde eine in STRATEG.DAT definierbare Abfrage-Wartezeit f�r den Optimierer eingef�hrt, die ein unn�tiges, rechenzeitverbrauchendes Pollen im Filesystem verhindert.
	\item Einige kleinere Inkonsistenzen beim Schreiben der Ergebnisfiles wurden entfernt.
	\item Bei Verlassen des Optimierers durch eine normale Abbruchbedingung wird ein weiterer Ergebnisfile namens STATUS.ERG erzeugt, der den momentanen Stand dokumentiert, auch wenn er nicht der absolute Beststand ist.
\end{itemize}

EPO 0.3 und 0.4 waren interne Versionen.

Erg�nzungen und Korrekturen in EPO 0.5:
\begin{itemize}
	\item Festlegung der anf�nglichen Variationsbandbreite �ber die Definitionsbereichsgrenzen wurde durch eine benutzerdefinierbare Anfangs-Spannweitenangabe ersetzt, um eine Wiederaufnahme eines schon erfolgreichen Optimierungslaufes zu erm�glichen.
	\item Implementation der Unix-Version auf der Sparc-Platform
	\item Automatisches Entfernen des ``Stop''-Files in der Unix-Version.
	\item Versch�nerung (sic!) der Kontrollausgaben.
\end{itemize}

\bigskip

Die vorliegende Version 0.5 stellt eine sinnvoll lauff�hige und schon in der Praxis einsetzbare Vorversion von EPO~1.0 dar. Ich wollte diese wiederum so schnell wie m�glich herausgeben, um so schnell wie m�glich von Anwendern R�ckmeldungen f�r die Weiterentwicklung des Systems zu bekommen.

Wesentlicher Problempunkt d�rfte momentan die unfexible Eingabedaten-Einleseroutine sein, die eine sehr spezielle Formatierung und eine strenge Beachtung von Reihenfolge und Form der Eingabedaten erfordert. Hier soll ein fehlertoleranteres System eingebaut werden.

Als n�chstes ist eine automatische graphische Ausgabe des aktuellen Optimierungsstandes und der Historie des Vorgangs �ber das Programm GNUPLOT geplant, f�r das zur Zeit eine Ausgabeschnittstelle in den Optimierer eingebaut wird.

Des weiteren ist eine Umstellung der Informations�bergabe von Datenfiles auf die Verwendung von RAM-internen Pipes geplant, um den Kommunikations-Overhead so gering wie m�glich zu halten.

Insbesondere bei langen Simulatorl�ufen w�re es sinnvoll, mehrere Simulatoren parallel auf mehreren Maschinen laufen lassen zu k�nnen. Auch das ist in einer zuk�nftigen Version von EPO vorgesehen.

Schlie�lich ist soll das Mensch-Maschine-Interface verbessert werden, das in der vorliegenden Version zugegebenerma�en eher steinzeitlich anmutet. Doch steht dieser Punkt bewu�t ganz hinten auf der Liste, weil mir die Funktion wichtiger ist als das Aussehen und der Programmlauf sowieso am sinnvollsten als Hintergrundproze� und damit ohne gro�e Benutzer-Interaktion stattfindet.



\section{Registrierungsmodalit�ten f�r Vollversion}

So, nun kommt der unangenehmste Teil der Benutzungseinf�hrung, n�mlich der, in dem es um Geld geht. Ich hoffe aber, diesen so angenehm wie m�glich gestaltet zu haben $\ldots$

Wie bei Shareware �blich, darf dieses Paket frei kopiert und weitergegeben werden, unter der Voraussetzung, da� keinerlei �nderungen daran gemacht werden. Die vorliegende, eingeschr�nkt nutzbare Version (bis zu f�nf zu optimierende Parameter) darf beliebig lange ohne Entrichtung von Nutzungsgeb�hren eingesetzt werden. Werden mit EPO praktisch nutzbare Ergebnisse erzielt, erwarte ich bei einer Ver�ffentlichung solcher Ergebnisse eine explizite Erw�hnung von EPO als eingesetztes Hilfsmittel. Dar�ber hinaus bin ich nat�rlich auch einer freiwilligen finanziellen Anerkennung meiner Programmierleistung nicht abgeneigt. 

Eine uneingeschr�nkt nutzbare Version mit bis zu mehreren hundert Variablen, die insbesondere auch eine Bearbeitung von Reihenfolgeproblemen und gemischt reellwertigen + diskreten Aufgabenstellungen erlaubt, steht sowohl f�r OS/2- wie auch f�r Unix-Systeme zur Verf�gung und ist direkt bei der Programmautorin zu erwerben. Der Preis richtet sich nach dem Umfang der zu bew�ltigenden Aufgabenstellungen und liegt typischerweise zwischen 200,--~DM und 2.000,--~DM.

Bei manchen komplexeren Optimierungsproblemen wird die vorliegende Programmstruktur nicht einsetzbar sein, obwohl eine evolutionsstrategische Vorgehensweise angeraten w�re. In diesen F�llen besteht die M�glichkeit, spezialisierte Programmversionen zu erstellen, die genau die Anforderungen erf�llen. Hierzu bitte die Programmautorin direkt ansprechen!



\section*{Danksagung}

An dieser Stelle m�chte ich es nicht vers�umen, meinem Bruder Dr.\ Peter Roosen f�r die �berlassung der ersten Internversionen des Evolution�ren Optimierers zu danken, auf dem diese Version aufbaut. Ich hoffe, mit der �berarbeitung dieser Quelle f�r OS/2-PCs und Unix-Workstations zu einer weiteren Verbreitung der Idee naturanaloger Optimierungsverfahren beizutragen und ihm ein Feed-Back f�r die systematisierte Entwicklung und Anwendung im Bereich der Verfahrenstechnik zu geben.

Ein gro�es Dankesch�n auch an Eberhard Mattes, der mir mit seinem EMX-C-Compilersystem die M�glichkeit gab, dieses Programmsystem unter OS/2 zu realisieren. H�tte ich einige hundert DM f�r einen kommerziellen Compiler ausgeben m�ssen, w�re es wohl nicht entstanden.

\bigskip
%\newpage

\noindent
Petra Roosen\\[3mm]
6.4.1994\\


%===================================================================

\newpage
\begin{thebibliography}{99}
\addcontentsline{toc}{section}{Literaturliste}

\bibitem{ Ablay:SdW} P.\ Ablay: Optimieren mit Evolutionsstrategien; 
Spektrum der Wissenschaft, Juli 1987, 104-114

\bibitem{ Doerin:Filter} J.\ D�hring, C.\ H�lsig: Filterentwurf nach dem Optimierungsprinzip der biologischen Evolution; 26. intern.Wiss.Koll. TH Ilmenau, Vortragsreihe `Schaltungstechnik und elektronische 
Me�technik',1981

\bibitem{ Eigen:Konvergenz} Global Convergence of Genetic Algorithms: an Infinite Markov Chain Analysis; PPSN, 1990, Dortmund

\bibitem{ HoffHof} U. Hoffmann, H. Hofmann: Einf�hrung in die Optimierung; Verlag Chemie, 1971, ISBN 3-527-2534-8

\bibitem{ Hollan:Adapt} J.H.\ Holland: Adaptaion; Progress in theoretical biology, 4(1976)263-293

\bibitem{ Hoppe:Biophysik} W. Hoppe, W. Lohmann, H. Markl, H. Ziegler: Biophysik; Springer, 1978

\bibitem{ Kursaw:Vektor} F.\ Kursawe: A Variant of Evolution Strategies for Vector Optimization; PPSN 1990, Dortmund

\bibitem{ Muehle:EvoAlgs} H.\ M�hlenbein, M.\ Gorges-Schleuter, O.\ Kr�mer: Evolution algorithms in combinatorial opimization; Parallel Computing 7(1988)65-85

\bibitem{ Muelle:EvoBeisp} K.D.\ M�ller: Optimieren mit der Evolutionsstrategie in der Industrie anhand von Beispielen; Diss. TU Berlin, 1986

\bibitem{ Otto:SimAn} T. Otto: Reiselust --- Travelling Salesman, eine neue Strategie f�r eine alte Aufgabe; c't, 1(1994)188--194

\bibitem{ Poeppl:Funktional} J.\ P�pplau: Funktionalminimierung mit Evolutionsstrategien unter Verwendung von finite Elemente Diskretisierungen; Mitteilung aus dem Institut f�r Str�mungslehre und Str�mungsmaschinen, Hochschule der Bundeswehr Hamburg, Heft Juli 1982

\bibitem{ Rechen:Evolut} I.\ Rechenberg: Evolutionsstrategie; Frommann-Holzboog, ISBN 3-7728-0-374

\bibitem{ Rechen:EvoDarw} I.\ Rechenberg: The evolution strategy. A mathematical model of Darwinian evolution; Berlin 1984

\bibitem{ Rechen:EvoStrat} I.\ Rechenberg: Evolution strategy: Nature's way of optimization; Lecture notes in Engineering, Vol. 47, Springer, 
Berlin 1989

\bibitem{ Rieck:ModellNatur} C. Rieck: Modell Natur --- Naturanaloge Verfahren in der Computersimulation; c't, 11(1993)201--208

\bibitem{ Riedel:Galvanik} H.J.\ Riedel: Einsatz rechnergest�tzter Optimierung mittels der Evolutionsstrategie zur L�sung galvanotechischer Probleme; Dissertation TU Berlin, 1984

\bibitem{ Handelsreis} G.\ Rudolph: Global Optimization by Means of 
Distributed Evolution Strategies; in H.-P.\ Schwefel und R.\ M�nner (Hrsg.): 
Parallel Problem Solving from Nature, Lecture Notes in Computer Science 496, 
S.\ 209--213, Springer Verlag, 1991

\bibitem{ Schmie:Mikrowelle} H.\ Schmiedel: Anwendung der Evolutionsoptimierung bei Mikrowellenschaltungen; Frequenz 35(1981)306-310

\bibitem{ Schwef:Opti} H.-P.\ Schwefel: Numerische Optimierungs von Computermodellen mittels der Evolutionsstrategie; Interdisciplinary Systems Research 26, Birkh�user 1977

\bibitem{ Schwef:DirectSearch} H.-P.\ Schwefel: Direct Search for Optimal Parameters within Simulation Models; Proc.\ of the 12$^{\rm th}$ Annual Simulation Symposium, Tampa, Florida, 1979

\bibitem{ Schw88} H.-P.\ Schwefel: Evolutionary Learning Optimum-Seeking on 
Parallel Computer Architectures; in A.\ Sydow, S.G.\ Tzafestas, R.\ 
Vichnevetsky (Hrsg.): Proceedings of the International Symposium on Systems 
Analysis and Simulation 1988, I: Theory and Foundations, S.\ 217--225, 
Akademie-Verlag, Berlin, September 1988

\bibitem{ PPSN:1990} H.-P.\ Schwefel und R.\ M�nner (Hrsg.): International 
Conference on ``Parallel Problem Solving from Nature'', Dortmund 1990; 
Lecture Notes in Computer Science 496, Springer Verlag, 1991

\bibitem{ Tschum:AllgBio} P.-A.\ Tschumi: Allgemeine Biologie; 
ISBN3-425-05659-X

\bibitem{ Zach} F. Zach: Technisches Optimieren; Springer, 1974, ISBN 0-387-81140-0
\end{thebibliography}

\end{document}