lcs_variant.tex

\chapter{XCS Varianten}\label{lcs_variants:cha}

\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.6\textwidth}
\begin{flushright} \tiny
\emph{I'm working to improve my methods, and every hour I save is an hour added to my life.} \\
Ayn Rand\\
~\\
~\\
\end{flushright}
\end{minipage}

Nach der allgemeinen Einführung in XCS im letzten Kapitel wird hier nun die eigentliche Frage der Arbeit beantwortet, nämlich wie sich eine Umsetzung von XCS auf einem Überwachungsszenario gestaltet und welche konkreten Änderungen dafür am Algorithmus notwendig sind. Hierzu war es notwendig, die XCS Implementierung vollständig nachzuvollziehen. Dadurch war es möglich, für jeden Bestandteil entscheiden zu können, welche Rolle er bezüglich eines solchen Szenarien spielt.\\

Dazu werden zuerst allgemeine Anpassungen des Algorithmus und der Implementierung besprochen (siehe Kapitel~\ref{allgemeine_anpassungen:sec}) um dann auf die konkreten Veränderungen der einzelnen XCS Varianten einzugehen. Zum einen wird der XCS Algorithmus selbst in Kapitel~\ref{standardxcs:sec} vorgestellt, dort wird insbesondere die Behandlung des Neustarts einer Probleminstanz diskutiert. Zum anderen wird eine an Überwachungsszenarien angepasste Variante (SXCS) vorgestellt, welche unter dem Gesichtspunkt des Problems einer kontinuierlichen Überwachung eines Zielobjekts entwickelt wird. Abschließend wird in Kapitel~\ref{verzoegerter_reward:sec} eine erweiterte SXCS Variante (DSXCS) vorgestellt, die es explizit erlaubt, \emph{reward} Werte erst mit einiger Verzögerung den jeweiligen \emph{action set} Listen zuweist. Sie soll lediglich als Ausblick für weitere Verbesserungen dienen. Schließlich stellt das Kapitel~\ref{communication:cha} eine Variante mit Kommunikation mit anderen Agenten vor, die allerdings nur als Ausblick zu sehen ist.\\


\section{Allgemeine Anpassungen von XCS}\label{allgemeine_anpassungen:sec}

Eine Anzahl allgemeiner Änderungen an der Implementierung und am Algorithmus waren notwendig, um XCS in einem Überwachungsszenario laufen zu lassen. Unter anderen sind dies:

\begin{itemize}
\item Die Berechnung der Summe der \emph{numerosity} Werte wurden neu organisiert und ein Fehler bei der Aktualisierung des \emph{numerosity} Werts in der Implementierung korrigiert (siehe Kapitel~\ref{corrected_numerosity_function:sec}).

\item Der genetische Operator verwendet hier zwei feste, anstatt zufällige Schnittpunkte für das \emph{two point crossover} (siehe Kapitel~\ref{genetische_operatoren:sec}).

\item Die Qualität des Algorithmus wird zu jedem Zeitpunkt und nicht nur in der \emph{exploit} Phase gemessen, da ein fortlaufendes Problem und kein statisches Szenario betrachtet wird (siehe Kapitel~\ref{exploreexploit:sec}).

\item Mehrere XCS Parameter wurden angepasst (siehe Kapitel~\ref{cha:parameter}).

\item Das Erreichen des Ziels wurde für das Überwachungsszenario neu verfasst, wie auch der Neustart von Probleminstanzen neu geregelt wurde (siehe Kapitel~\ref{bewertung:sec}).

\item Die Reihenfolge bei der Bewertung, Entscheidung und der Aktion in einem Multiagentensystem auf einem diskreten Torus musste überdacht werden (siehe Kapitel~\ref{ablauf_lcs:sec}).

\end{itemize}



\section{XCS \emph{multi step} Verfahren}\label{standardxcs:sec}

Idee dieses Verfahrens ist, dass der \emph{reward} Wert, den eine Aktion (bzw. der jeweils zugehörigen \emph{action set} Liste und die dortigen \emph{classifier}) erhält, vom erwarteten \emph{reward} Wert der folgenden Aktion abhängen soll. Das wird dadurch erreicht, dass \emph{classifier} jeweils ein Schritt lang gespeichert werden und dann einen Teil der \emph{reward prediction} Werte der jeweils nächsten \emph{match set} Liste weitergegeben wird. Dadurch ist es möglich, dass ein beim Ziel vergebener \emph{base reward} Wert über eine ganze Kette von Schritten durchgereicht wird.\\

Da bei der Standardimplementierung von XCS die Probleminstanz beim Erreichen eines positiven \emph{base reward} Werts jeweils neu gestartet wird, benötigt diese Weitergabe ein ganze Anzahl von Probleminstanzen. Dabei gilt die Annahme, dass durch mehrfache Wiederholung des Lernprozesses sich ein Regelsatz ergibt, mit dem das Ziel mit höherer Wahrscheinlichkeit bzw. mit einer geringeren Schrittzahl gefunden wird.\\

Dies entspricht dem aus \cite{butz01algorithmic} bekannten XCS \emph{multi step} Verfahren. Der wesentliche Unterschied zur Implementierung in dieser Arbeit ist, dass das Szenario bei einem positiven \emph{base reward} Wert nicht neu gestartet wird. Algorithmisch ist die Implementierung ansonsten identisch. Dies zeigt sich in Programm~\ref{multistep_calc_reward:pro} (Zeilen 22-27). Zwar wird hier die \emph{action set} Liste gelöscht, das Szenario selbst läuft aber weiter. In der originalen Implementierung in~\cite{Butz_xcsclassifier} wird an dieser Stelle im Algorithmus die aktuelle Probleminstanz abgebrochen (in \emph{XCS.java} in der Funktion \emph{doOneMultiStepProblemExploit()} bzw. \emph{doOneMultiStepProblemExplore()}). Liegt kein positiver \emph{base reward} Wert vor, so wird lediglich der für diesen Schritt erwartete \emph{reward} Wert (nämlich der \emph{maxPrediction} Wert) an die letzte \emph{action set} Liste gegeben.\\

In den Programmen~\ref{multistep_collect_reward:pro} und \ref{multistep_calc_move:pro} finden sich, neben Anpassungen an den Simulator, keine wesentlichen Änderungen. In Programm~\ref{multistep_collect_reward:pro} wird der ermittelte \emph{base reward} Wert zusammen mit dem ermittelten \emph{maxPrediction} Wert an die Aktualisierungsfunktion der jeweiligen \emph{action set} Liste weitergegeben. Im Programm~\ref{multistep_calc_move:pro} wird dann eine Aktion daraus ausgewählt und entsprechende \emph{match set} und \emph{action set} Listen erstellt.\\


\section{XCS Variante für Überwachungsszenarien (SXCS)}\label{sxcs_variant:sec}

Die Hypothese bei der Aufstellung dieser XCS Variante ist im Grunde dieselbe wie beim XCS \emph{multi step} Verfahren selbst, nämlich dass die Kombination mehrerer Aktionen zum Ziel führt. Beim \emph{multi step} Verfahren besteht die wesentliche Verbindung zwischen den \emph{action set} Listen jeweils nur zwischen zwei direkt aufeinanderfolgenden \emph{action set} Listen über den \emph{maxPrediction} Wert. Dadurch kann in einer statischen Umgebung über mehrere (identische) Probleme hinweg eine optimale Einstellung (des \emph{fitness} und \emph{reward prediction} Werts) für die \emph{classifier} gefunden werden, sofern das damit zusammenhängende Problem eine Markow-Kette darstellt~\cite{butz01algorithmic}, also bei dem Problem "`die zukünftige Entwicklung des Prozesses nur von dem zuletzt beobachteten Zustand abhängt und von der sonstigen Vorgeschichte unabhängig ist"'~\cite{Waldmann}.\\

Die Idee für SXCS ist nun, eine ähnliche Implementierung zu wählen, wie beispielsweise in~\cite{lanzi99optimal} vorgestellt. Dort kann eine Aktion eines Agenten sowohl äußere als auch innere Auswirkungen haben, wodurch eine Art Speicher realisierbar ist und somit in die Markow-Eigenschaft teilweise wiederhergestellt werden kann. Für SXCS soll dagegen direkt die aktivierten \emph{action set} Listen gespeichert werden, bis ein sogenanntes Ereignis (siehe Kapitel~\ref{sec:events}) auftritt.\\

Bei der hier besprochenen SXCS Variante (\emph{Supervising eXtended Classifier System}) wird in Kapitel~\ref{umsetzung_sxcs:sec} zuerst die Umsetzung dieser Idee diskutiert werden. Sie baut auf sogenannten "`Ereignissen"' auf, die mit einer Änderung des \emph{base reward} Werts einhergehen (siehe Kapitel~\ref{sec:events}). Die Implementierung selbst wird dann in Kapitel~\ref{sxcs_implementation:sec} vorgestellt.\\


\subsection{Umsetzung von SXCS}\label{umsetzung_sxcs:sec}

Bei der SXCS Variante soll die Verbindung zwischen den \emph{action set} Listen direkt durch die zeitliche Nähe zur Vergabe des \emph{base reward} Werts gegeben sein. Es wird in jedem Schritt die jeweilige \emph{action set} Liste gespeichert und aufgehoben, bis ein neues Ereignis (siehe Kapitel~\ref{sec:events}) eintritt und dann in Abhängigkeit des Alters mit einem entsprechenden \emph{reward} Wert aktualisiert.\\

In der Standardimplementierung von XCS wurde der \emph{reward} Wert bei der Weitergabe jeweils mit einem Faktor \(\gamma\) multipliziert. Dieses Verhalten soll ungefähr nachgebildet werden, allerdings mit einer Funktion die sich über ein Ereignis erstreckt und einen Nullpunkt besitzt. Dies wird beispielsweise durch die quadratische Funktion erfüllt.\\

Bezeichne \(r(a)\) den \emph{reward} Wert für die \emph{action set} Liste mit Alter \(a\), bei quadratischer Verteilung des \emph{base reward} Werts ergibt sich dann:

$$
r(a) = \left\{ \begin{array}{rl}
  \frac{{a}^{2}}{{\mathrm{size(\emph{action set})}}^{2}} &\mbox{ falls \emph{base reward} = $1$} \\
  \frac{{(1 - a)}^{2}}{{\mathrm{size(\emph{action set})}}^{2}} &\mbox{ falls \emph{base reward} = $0$}
       \end{array} \right.
$$

Der Vergleich der linearen Vergabe, der quadratischen Vergabe und der Vergabe bei XCS über 10 Schritte ist in Abbildung~\ref{quadratisch_reward:fig} dargestellt.\\

\begin{figure}[htbp]
\centerline{	
\includegraphics{quadratisch_reward.eps}
}
\caption[Vergleich verschiedener Arten der Weitergabe des \emph{reward} Werts] {Vergleich verschiedener Arten der Weitergabe des \emph{reward} Werts}
\label{quadratisch_reward:fig}
\end{figure}

In Tests ergab sich für die quadratische Verteilung im Vergleich zur linearen Verteilung des \emph{base reward} Werts nur minimale Unterschiede. In Tests wurden keine wesentlichen Unterschiede zwischen der linearen und quadratischen Verteilung festgestellt, weitere Untersuchungen und womöglich eine Modifikation der Verteilungsfunktion wäre ein möglicher Ansatzpunkt für weitere Forschungen.\\

In Abbildung~\ref{positive_negative_reward:fig} ist dies dargestellt. Weitere Grafiken beschränken sich auf die lineare Verteilung des \emph{base reward} Werts, während in den Simulationen die quadratische Vergabe des \emph{base reward} Werts benutzt wird.\\


\begin{figure}[htbp]
\centerline{	
\includegraphics{positive_negative_reward.eps}
}
\caption[Schematische Darstellung der Verteilung des \emph{reward} Werts an \emph{action set} Listen] {Schematische Darstellung der (quadratischen) Verteilung des \emph{reward} Werts an gespeicherte \emph{action set} Listen bei einem positiven bzw. negativen Ereignis}
\label{positive_negative_reward:fig}
\end{figure}


\subsection{Ereignisse}\label{sec:events}

In XCS wird lediglich die jeweils letzte \emph{action set} Liste aus dem vorherigen Schritt gespeichert. In der neuen Implementierung werden dagegen eine ganze Anzahl (bis zum Wert \emph{maxStackSize}) von \emph{action set} Listen gespeichert. Die Speicherung erlaubt zum einen eine Vorverarbeitung des \emph{reward} Werts anhand der vergangenen Schritte und auf Basis einer größeren Zahl von \emph{action set} Listen und zum anderen die zeitliche Relativierung einer \emph{action set} Liste zu einem Ereignis. Die \emph{classifier} werden dann jeweils rückwirkend anhand des jeweiligen \emph{reward} Werts aktualisiert, sobald bestimmte Bedingungen eingetreten sind.\\

Von einem positiven bzw. negativen Ereignis spricht man, wenn sich der \emph{base reward} Wert im Vergleich zum vorangegangenen Schritt verändert hat (siehe Abbildung~\ref{saved_rewards:fig}). Mit der in Kapitel~\ref{bewertung_ueberwachungszenario:sec} vorgestellten \emph{reward} Funktion hieße das, dass sich entweder das Zielobjekt gerade in Sichtweite bzw. aus ihr heraus bewegt hat oder, dass der jeweilige Agent die Sicht zu anderen Agenten verloren hat bzw. sich gerade erst wieder in Sicht eines anderen Agenten bewegt.\\

Bei der Benutzung eines solchen Stacks entsteht eine Zeitverzögerung, d.h. die \emph{classifier} erhalten jeweils Informationen, die bis zu \emph{maxStackSize} Schritten zu alt sein können. Tritt beim Stack ein Überlauf auf, gab es also \emph{maxStackSize} Schritte lang keine Änderung des \emph{base reward} Werts mehr, dann wird abgebrochen und die \(\frac{maxStackSize}{2}\) ältesten Einträge werden vom Stack genommen. Alle diese Einträge werden dabei vorher mit einem \emph{reward} Wert aktualisiert, der diesem \emph{base reward} Wert entspricht.\\

Abbildung~\ref{neutral_reward:fig} zeigt die Bewertung bei einem solchen neutralen Ereignis, bei dem nach einem Überlauf die erste Hälfte mit \(1\) bewertet wurde. Außerdem ist dort der maximale Fehler dargestellt, welcher eintreten würde, wenn direkt beim Schritt nach dem Abbruch eine Änderung des \emph{base reward} Werts auftritt. Im dargestellten Fall würde sich also der \emph{base reward} Wert beim aktuellen Zeitpunkt auf \(0\) verändern.\\

\begin{figure}[H]
\setbox0\vbox{\small
Ein Ereignis tritt also auf bei:
\begin{itemize}
\item Änderung des \emph{base reward} Werts von 0 auf 1 (Zielobjekt war im letzten Schritt nicht in Überwachungsreichweite bzw. der letzte Agent hat die Sicht im letzten Schritt verlassen) \(\Rightarrow\) {\bf positives Ereignis},
\item Änderung des \emph{base reward} Werts von 1 auf 0 (Zielobjekt war im letzten Schritt in Überwachungsreichweite bzw. ein Agent hat gerade die Sicht betreten) \(\Rightarrow\) {\bf negatives Ereignis},
\item Überlauf des Stacks (kein positives oder negatives Ereignis in den letzten \emph{maxStackSize} Schritten), Zielobjekt ist in Überwachungsreichweite bzw. keine Agenten sind in Sicht \(\Rightarrow\) {\bf neutrales Ereignis} (mit \emph{base reward} = \(1\)) oder bei
\item Überlauf des Stacks (kein positives oder negatives Ereignis in den letzten \emph{maxStackSize} Schritten), Zielobjekt ist nicht in Überwachungsreichweite bzw. mindestens ein Agent ist in Sicht \(\Rightarrow\) {\bf neutrales Ereignis} (mit \emph{base reward} = \(0\)).
\end{itemize}
}
\centerline{\fbox{\box0}}
\end{figure}


\begin{figure}[htbp]
\centerline{	
\includegraphics{saved_rewards.eps}
}
\caption[Schematische Darstellung der zeitlichen Verteilung des \emph{reward} Werts an und der Speicherung von \emph{action set} Listen] {Schematische Darstellung der zeitlichen Verteilung des \emph{reward} Werts an \emph{action set} Listen nach mehreren positiven und negativen Ereignissen und der Speicherung der letzten \emph{action set} Liste}
\label{saved_rewards:fig}
\end{figure}

\begin{figure}[htbp]
\centerline{	
\includegraphics{neutral_reward.eps}
}
\caption[Schematische Darstellung der Bewertung von \emph{action set} Listen bei einem neutralen Ereignis] {Schematische Darstellung der Bewertung von \emph{action set} Listen bei einem neutralen Ereignis (mit \emph{base reward} = 1)}
\label{neutral_reward:fig}
\end{figure}


\subsection{Größe des Stacks (\emph{maxStackSize})}\label{groesse_stack:sec}

Offen bleibt die Frage nach der Größe des Stacks. Mangels theoretischem Fundament muss man zwischen den drei wirkenden Faktoren einen Kompromiss finden. Große Werte für \emph{maxStackSize} können zu folgenden Schwierigkeiten führen:

\begin{itemize}

\item Durch die Verwendung eines Stacks gibt es eine Verzögerung zu Beginn der Probleminstanz und insbesondere zu Beginn eines Experiments (also bei einer wesentlichen Änderung des Szenarien). Es kann u.U. bis zu \(\frac{maxStackSize}{2}\) Schritte dauern, bis das erste Mal ein \emph{classifier} aktualisiert wird. 

\item Ein zu großer Stack führt womöglich dazu, dass Aktionen positiv (oder negativ) bewertet werden, die an der Erreichung des \emph{base reward} Werts nicht oder nur unbedeutend beteiligt waren, vor allem, wenn es sich um kurze lokale Entscheidungen handelt. 

\end{itemize}



Umgekehrt, wählt man den Stack zu klein, dann kann es zu folgenden Problemen kommen:

\begin{itemize} 

\item Durch die geringere Größe des Stacks kann es zu einem Überlauf und so zu dem in Kapitel~\ref{sec:events} beschriebenen Fehler bei der Bewertung kommen. 

\item Zum Erreichen des Ziels können eine ganze Reihe von Schritten notwendig sein. Passen sie nicht alle in den Stack, dann werden sie verworfen. Bei XCS wird dies durch Weitergabe der \emph{reward} Werte von \emph{action set} zu \emph{action set} vermieden.

\end{itemize}


Der optimale Wert für \emph{maxStackSize} muss also einen Kompromiss zwischen diesen Faktoren darstellen und ist somit abhängig vom Szenario. Optimal wäre eine Anpassung des \emph{maxStackSize} Werts während des Durchlaufs. Die Untersuchung hier wird sich auf eine empirische Ermittlung eines ausreichend guten Werts für die betrachteten Szenarien beschränken.\\

Wie Abbildung~\ref{max_stack_size:fig} zeigt, spielt der Wert eher eine geringe Rolle, die erreichten Qualitäten unterscheiden sich im betrachteten Wertebereich kaum voneinander. Nur im Umfeld von \emph{maxStackSize}~\( = 8\) sind deutliche Unterschiede sichtbar. Für den Fall mit der Torusgröße von 32x32 in Abbildung~\ref{max_stack_size2:fig} sieht man dagegen nur eine leichte Steigerung für größere Werte. Auch das schwierige Szenario scheint hier eher von größeren Werten zu profitieren. Dies unterstreicht, dass der optimale Wert vom Szenario (bzw. der durchschnittlichen Zeit bis zum Erreichen des nächsten positiven \emph{base reward} Werts) abhängt, dies bedarf jedoch weiterer Forschung. Für diese Arbeit wird im weiteren Verlauf im Allgemeinen ein Wert für {\bf \emph{maxStackSize} von \(8\)} und in Kapitel~\ref{xcs_difficult_scenario:sec} wird in einem Fall {\bf \(32\)} benutzt.\\


\begin{figure}[htbp]
\centerline{	
\includegraphics{max_stack_size.eps}
}
\caption[Vergleich verschiedener Werte für \emph{maxStackSize}] {Vergleich verschiedener Werte für \emph{maxStackSize} (Säulenszenario, SXCS Agenten, \emph{tournament selection}, $p = 0,84$))}
\label{max_stack_size:fig}
\end{figure}

\begin{figure}[htbp]
\centerline{	
\includegraphics{max_stack_size2.eps}
}
\caption[Vergleich verschiedener Werte für \emph{maxStackSize} (spezielle Szenarien)] {Vergleich verschiedener Werte für \emph{maxStackSize} (spezielle Szenarien, SXCS Agenten, \emph{tournament selection}, $p = 0,84$)}
\label{max_stack_size2:fig}
\end{figure}


\subsection{Implementierung von SXCS}\label{sxcs_implementation:sec}

Im Wesentlichen entspricht die Implementierung von SXCS der bekannten Implementierung von XCS (siehe Kapitel~\ref{standardxcs:sec}). Als Unterschiede sind festzuhalten:\\

\begin{itemize}

\item In der Funktion \emph{calculateReward()} in Programm~\ref{sxcs_calc_reward:pro} bei der Berechnung des \emph{reward} Werts wird zwischen zwei Fällen unterschieden. Zum einen gibt es die Behandlung negativer und positiver Ereignisse (Zeile 19-23) und zum anderen die Behandlung des Überlaufs des Stacks (Zeile 29-35), während bei der Implementierung von XCS in Programm~\ref{multistep_calc_reward:pro} in fast jedem Schritt unabhängig von Ereignissen eine Aktualisierung stattfindet.

\item In der Funktion \emph{collectReward()} in Programm~\ref{sxcs_collect_reward:pro} werden nicht nur die aktuelle bzw. letzte \emph{action set} Liste aktualisiert, sondern eine ganze Reihe aus dem gespeicherten Stack. Insbesondere werden dort die auf- bzw. absteigenden \emph{reward} Werte nach einem positiven bzw. negativen Ereignis berechnet (Zeile 31-33). Bei der Berechnung der nächsten Aktion hingegen (Funktion \emph{calculateNextMove()} in Programm~\ref{sxcs_calc_move:pro}) wurde lediglich die Behandlung des Stacks hinzugefügt (Zeile 40-44).

\end{itemize}


\section{SXCS Variante mit verzögerter \emph{reward} (DSXCS)}\label{verzoegerter_reward:sec}

Die Struktur der besprochenen XCS Variante SXCS erlaubt, ermittelte \emph{reward} Werte erst bis zu \emph{maxStackSize} Schritte später an die \emph{classifier} weiterzugeben. Während diese Verzögerung dort lediglich als notwendiges Übel gesehen wurde, kann dies auch wesentliche Vorteile erbringen. Erst einmal kann eine Verzögerung dazu führen, dass ein ermittelter \emph{reward} Wert nicht sofort eine Auswirkung auf die Bewegungsart des jeweiligen Agenten hat, der Agent also noch auf Basis seiner alten Konfiguration seiner \emph{classifier set} Liste handelt. Würde ein Agent beispielsweise zu Beginn nach Westen gehen und dort das Zielobjekt sehen, dann würden in den nächsten Schritten nach Westen gerichtete Schritte besonders bevorzugt, obwohl in den meisten Fällen speziell zu Beginn ein eher exploratives Verhalten von Vorteil ist. Zweiter und wesentlich wichtigerer Punkt ist, dass aufgrund der Verzögerung zum Zeitpunkt der Vergabe des \emph{reward} Werts eine viel größere Anzahl an Werten zur Verfügung steht (die \emph{reward} Werte der letzten \emph{maxStackSize} Schritte), anhand derer entschieden werden kann, mit welchem Wert die einzelnen \emph{classifier} aktualisiert werden sollen.\\

Offen bleibt die Frage nach einer Funktion, die dies vorteilhaft ausnutzt. Zwar konnte im Rahmen dieser Arbeit noch keine solche Funktion gefunden werden, prinzipiell erscheint es aber sehr wahrscheinlich, dass eine existiert. Für DSXCS ohne eine solche Funktion, also mit einer reinen Verzögerung, wird später in Kapitel~\ref{dsxcs_analysis:sec} gezeigt, dass es von der Qualität her ähnlich SXCS ist.\\

Im Folgenden wird zwar, neben dem Aufbau einer solchen, speziell auf Verzögerungen ausgelegte, SXCS Variante DSXCS (\emph{Delayed Surveillance eXtended Classifier System}), auf zwei solche Funktionen eingegangen, wie später in Kapitel~\ref{dsxcs_analysis:sec} aber gezeigt wird, erreichen diese aber keine besseren sondern eher schlechtere Werte für ihre Qualität. Durch die am Ende im Ausblick (Kapitel~\ref{ausblick:sec}) besprochenen möglichen Erweiterungen der hier besprochenen Modellierung könnten die Ansätze sich jedoch als nutzbringend erweisen, hier ist weitere Forschung nötig.\\


\subsection{Aktualisierungsfaktor}\label{aktualisierungsfaktor:sec}

Als eine mögliche Erweiterung bietet sich an, Ereignisse bzw. deren \emph{reward} Werte mit einem Faktor zu erweitern, der bei der Aktualisierung der \emph{action set} Listen eine Rolle spielt. Hier kann der Faktor entweder dazu dienen, mit der Lernrate \(\beta\) multipliziert die Rolle von \(\beta\) zu ersetzen und somit eine geringeren Einfluss des \emph{reward} Werts zu erreichen, oder der \emph{reward} Wert kann direkt mit dem Faktor multipliziert werden und somit den Faktor als eine Art Strafe verwenden. Ein Aktualisierungsfaktor von beispielsweise \(1,0\) hätte also keine Änderungen zur Folge, ein Faktor von \(0,5\) würde dagegen die Lernrate für den zugehörigen \emph{reward} Wert bzw. den \emph{reward} Wert selbst halbieren.\\

Motivation zur Einführung des Faktors war, dass man bestimmten \emph{reward} Werten eine gewisse Genauigkeit zuweist um bestimmte Ereignisse weniger einflussreich zu machen bzw. um sie überhaupt zu bewerten. Beispielsweise könnte man durch eine Erweiterung mit kommunikativen Fähigkeiten dadurch externe Ereignisse (siehe Kapitel~\ref{externe_ereignisse:sec}) einen niedrigeren Wert zuweisen. Im Folgenden wird der Aktualisierungsfaktor mit "`\emph{factor}"' bezeichnet.\\


\subsection{Zeitgleiche Ereignisse}\label{zeitgleiche_ereignisse:sec}

Durch die Struktur von DSXCS ist es desweiteren möglich, mehrere zeitgleiche Ereignisse bzw. deren zugehörige \emph{reward} und \emph{factor} Werte sinnvoll zu verarbeiten. Zeitgleiche Ereignisse können zwar im bisher verwendeten System nicht auftreten, aber eine Erweiterung des Systems durch eine Form der Kommunikation würde es möglich machen, dass z.B. ein Agent den eigenen \emph{reward} Wert, die eigenen Sensordaten oder andere Informationen an einen anderen Agenten als externes Ereignis weitergibt (siehe Kapitel~\ref{externe_ereignisse:sec}).\\ 

Während bei SXCS das Auftreten mehrerer gleichzeitiger \emph{reward} Werte dazu geführt hätte, dass die \emph{classifier} der jeweiligen \emph{action set} Listen nacheinander mit den jeweiligen Werten aktualisiert worden wären, kann sich ein auf DSXCS basierender Agent alle bisher gesammelten \emph{reward} und \emph{factor} Werte erst einmal näher ansehen und beispielsweise nur den höchsten \emph{reward} Wert für die Aktualisierung benutzen. Auch hier ist wieder offen, wie die Funktion aussieht, die einen Wert auswählt bzw. berechnet.\\


\subsection{Implementierung}

Die Funktion \emph{calculateReward()} ist identisch mit der in Kapitel~\ref{sxcs_implementation:sec} besprochenen Funktion (Programm~\ref{sxcs_calc_reward:pro}) bei der SXCS Variante ohne verzögerter Bewertung. Ebenso ist die Funktion \emph{calculateNextMove()} (siehe Programm~\ref{dsxcs_calc_move:pro}) fast identisch mit der dort besprochenen Funktion, nur bei der Behandlung des Stacks wird hier beim Überlauf der erste Eintrag nicht einfach gelöscht, sondern mit der Funktion \emph{processReward()} zuerst noch verarbeitet. In der Verarbeitung werden alle bisher gespeicherten \emph{reward} und \emph{factor} Werte berücksichtigt, um jeweils den \emph{reward} und \emph{factor} Wert für den ersten Eintrags zu berechnen und die \emph{classifier} der zugehörigen \emph{action set} Liste zu aktualisieren.\\

Zur Berechnung selbst gibt es verschiedene Möglichkeiten. Die einfachste Variante ist in Programm ~\ref{process_reward_dsxcs1:pro} dargestellt, dort werden einfach alle zeitgleich abgespeicherten Werte nacheinander auf das \emph{action set} angewendet. Eine Erweiterung ist in Programm~\ref{process_reward_dsxcs2:pro} dargestellt. Dort werden jeweils nur die Einträge mit dem größten Produkt aus den \emph{reward} und \emph{factor} Werten für die Aktualisierung benutzt. Noch komplexere Berechnungen sind denkbar, beispielsweise könnten alle Werte aller Einträge der \emph{historicActionSet} Liste mit in die Berechnung einer jeden einzelnen Aktualisierung der \emph{action set} Listen miteinbezogen werden.\\