source: liacs/ai/graaf/report.tex@ 32

%
% $Id: report.tex 614 2008-05-14 11:58:06Z tsteenbe $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage{graphicx}
\usepackage{url}
\usepackage{multicol}
\usepackage{fancybox}
\usepackage{amssymb,amsmath}
\parindent0ex 

\author{Rick van der Zwet & Thomas Steenbergen, Universiteit Leiden}
\title{Kunstmatige Intelligentie  2008 --- opdracht 4 \\
\large{Genetische algoritmen}}
\author{Rick van der Zwet~~~~~Thomas Steenbergen \\
  \texttt{hvdzwet@liacs.nl}~~~~\texttt{tsteenbe@liacs.nl}\\
  \\
  LIACS\\
  Leiden University\\
  Niels Bohrweg 1\\
  2333 CA Leiden\\
  The Netherlands}
\date{\today}

\begin{document}

\maketitle

\section{Inleiding}
Dit verslag gaat over de vierde opdracht~\cite{assignment} voor het
vak Kunstmatige Intelligentie~\cite{course}, welke over genetische
algoritmen gaat als besproken in het collegeboek~\cite{aibook}.
Een \emph{Genische Algoritme} is een zoek techniek dat gebruikt maakt
van Darwin's evolutietheorie~\cite{darwin} om complexe problemen op te
lossen.  Darwin's theorie stelt dat ontwikkeling van elke soort levend
organisme op aarde word bepaald door natuurlijke selectie. Diegenen die
zich het best aanpassen aan hun omgeving en daardoor overleven zullen
een groter aandeel krijgen in genetische variatie van een populatie,
simpel gezegd voor elke organisme geldt 'surival of the fittest'.  In
het genetische algoritme van deze opdracht wordt dit mechnisme gebruikt
om vanuit een populatie van mogelijke probleem oplossingen uiteindelijk
te evolueren naar een correct antwoord.

\section{Probleem}
Gegeven een graaf, schrijf een genetisch algoritme dat in een
coordinatenstelsel \emph{X, Y} de knopen van deze graaf zo plaats dat er
zo min mogelijke kruisende takken zijn en zodat de schaal tussen de
knopen zo goed mogelijk behouden blijft.

\begin{table}
\begin{center}
\begin{tabular}{c c c c}
    4 &   &   &   \\
    0 & 8 & 0 & 3 \\
    8 & 0 & 2 & 5 \\
    0 & 2 & 0 & 0 \\
    3 & 5 & 0 & 0 \\
\end{tabular}
\end{center}
\caption{Voorbeeld van input graaf in adjacency-matrix representatie
\label{tab:example-graph}}
\end{table}

\noindent
Bovenstaand Tabel~\ref{tab:example-graph} bevat een eenvoudige representie van 
een graaf. De eerste regel heeft het aantal knopen dat de graaf heeft,
in dit geval $4$.
De adjacency-matrix er onder geeft aan of er een tak tussen de knoop $i$
en $j$ zit en wat hiervan de lengte is. $0$ betekend geen tak.  In de
$i$-de rij / $j$-de kolom staat dat er dan een tak tussen knopen $i$ en
$j$ is met een afstand gelijk aan het getal. 
Tevens is er gegeven dat de graaf geen lussen bevat en dat alle
afstanden tussen de knopen positieve gehele getallen zijn.

\section{Theorie}
%XXX: Wiskundige uitleg genetische algoritmen 
% -> zoveel wiskunde komt er ook weer niet bij kijken
Een genetisch algoritme is gebaseerd op de evolutie theorie en gebruikt 
natuurlijke selectie om optimalisatie- en zoekproblemen op te lossen.
Een genetisch algoritme doorloopt de volgende stappen generatie op generatie
om tot een oplossing te komen of totdat het een stopconditie heeft bereikt:

\subsection{Initialisatie}
De eerste stap in elk genetisch algoritme is om een ouder generatie te
cre\"{e}eren, welke uit een voorafgesproken grootte bestaat.
Deze generatie bestaat in de meeste implementaties uit sets van
willekeurige getallen waarbij elke set een mogelijke oplossing voor het
probleem bevat.

\subsection{Selectie}
Voor elk item uit de ouder generatie wordt met behulp van een
\emph{fitnessfunctie} bepaald hoeveel deze ouder afwijkt van de eisen
die we aan de probleemoplossing hebben gesteld. Deze fitnessfunctie is
te zien als maatstaf van de kwaliteit. Vervolgens worden de twee beste
ouders geselecteerd en deze gaan na kruising of mutatie door naar
de volgende generatie.

\subsection{Kruising}
De twee ouders worden in deze kruising of ook wel \emph{crossover} stap
gerecombineerd zodat er twee unieke kinderen uit ontstaan. Hiervoor zijn
verschillende crossover methodes beschikbaar, onder andere
\emph{single-point} of \emph{two-point} of \emph{uniform} kruising
gebruiken.  Bij \emph{single-point} of \emph{two-point} wordt elke ouder
op respectievelijk \'{e}\'{e}n of twee plaatsen opgesplist en daarna
worden de delen zo hergecombioneerd dat er twee nieuwe kinderen ontstaan
met dezelfde lengte als de ouders. Bij \emph{uniform}  crossover wordt
er per element in \'{e}\'{e}n  van de twee ouders met een bepaalde kans
bekeken of dit element met het corresponderende element in de andere
ouder verwisseld dient te worden.  Kruising zorgt voor meer spreiding in
de ouder generatie, positieve eigenschappen van verschillende ouders
komen bij elkaar.

\subsection{Mutatie}
De kinderen die ontstaan zijn uit de kruising worden gemuteerd om de diversiteit
van de kinderen te bevorderen. De waarde van elk element in een ouder wordt met 
een bepaald kans veranderd naar een willekeurige waarde. Om bepaalde
positieve eigenschappen die misschien nog niet in de ouder generatie
zaten toe te voegen aan de generatie wordt mutatie toegepast.

\subsection{Stopconditie}
In tegenstelling tot evoluatie in de natuur die oneindig voortduurt dienen bij
genetische algoritmen het eveolutie process op een gegeven moment te stoppen om
conclusies te kunnen trekken.
Het is een goed moment om te stoppen als de fitness waarde gedurende een lange
periode gelijk blijft of langzaam naar een bepaalde waarde toe convergeerd.
Het simpelweg stoppen van de berekening na een vooraf vastgesteld aantal
generaties is een andere stopconditie die veel wordt gebruikt vanwege
praktische redenen, bijvoorbeeld als men een beperkte rekentijd heeft op een
supercomputer.


\section{Aanpak}
%XXX: Welke keuzes zijn genomen en met welke reden, wat is de
%achterliggende gedachte
Er is gekozen gebruik te maken van het voorbeeld implementatie raamwerk gegeven
in de sheet\cite{aisheet} tijdens het college kunstmatige
intelligentie welke een pseudo beschrijving geeft voor het programmeren
van een genetisch algoritme.
\pagebreak
\begin{verbatim}
Initialiseer populatie
Evalueer populatie
while not klaar do
      Selecteer ouders
      Genereer met crossover kinderen (recombineer)
      Muteer kinderen
      Evalueer kinderen
      Bepaal nieuwe populatie
return beste element uit populatie
\end{verbatim}
\noindent
Er is gekozen om te beginnen met populatie van een vooraf gedefineerde
grootte, deze wordt tijdens de initialisatie  gevuld met grafen met
random gekozen punten.

De evaluatie van de populatie wordt gedaan met behulp van een fitness
functie, welke de fitheid van elke graaf berekend aan de hand van twee criteria;
het aantal kriuisende takken en de lengte van de takken ten opzichte van
de invoer adjacency-matrix.
Om het aantal kruisende takken te bepalen dienen we de snijpunten tussen elke
bestaande tak in de adjency-matrix en alle andere takken uit te
rekenen, dit wordt gedaan door de lijn vergelijkingen op te lossen en
daarna te controleren of de gevonden oplossing in het vlak ligt welke
bekeken wordt. Als voorbeeld implementatie is het topcoder
artikel~\cite{line-intersect} gebruikt, welke in de opdracht als
referentie wordt gemeld.

Voor het selecteren van de ouders is \emph{roulettewheel} selectie een
zeer geschikte methode, welke als eigenschap heeft dat een element dat
goed is meer kans heeft op gekozen te worden, omdat het een groter deel
van het `wiel' zal beslaan.

Voor de creatie van de nieuwe populatie wordt \emph{steady state}
gebruikt, dit houdt in dat steeds de beste van de ouders en de kinderen
doorgaan naar de volgende ronde.



\section{Implementatie}
%XXX: Versie nummers en eventuele hulptalen
Het genetisch algoritme is geschreven in C$\stackrel{++}{}$, gebruik
makend van struct op een instantie van een graaf te representeren en
dynamische arrays.

Om de executie-snelheid van het genetisch algoritme te verhogen is het
domein waarin de random punten gekozen kunnen worden te verminderen tot
\emph{aantal knopen} x \emph{grootst gevonden lengte van een tak} mits
dit een domein oplevert kleiner dan 1000 x 1000.

\section{Experimenten}
Tijdens de experimenten wordt er een random nummer generatie gebruikt,
welke het onmogelijk maakt waardes van experimenten te vergelijken. Door
een random initalisatie seed van $0$ te gebruiken kan in elke run
dezelfde random nummers gebruikt worden om in elke run dezelfde random
waardes te laten spelen. Er zijn 3 typen variaties in de parameters van
het genetisch algoritmes gemodificeerd om te onderzoeken wat deze voor
invloed hebben op de kwaliteit van de grafiek. Verder is er gebruik
gemaakt van een special typen grafiek. De cirkel grafiek, welke slechts
een domein heeft van 30 x 30 en 10 nodes grafiek met een domein van
200 x 200.
Als eerste de de loop duur gevarieerd en de tijd gemeten hoe lang het
programma uitvoerd, welke de resultaten in tabel~\ref{tab:loops}
oplevert.

\begin{table}
\begin{tabular}{c|c|c|c}
Loops $10^x$ & fitness cirkel & fitness 10 nodes \\
\hline
4 & 17 & 260 \\
5 &  2 & 260 \\
6 &  2 & 146 \\
7 &  2 & 118 \\
\end{tabular}
\caption{Experimenten met verschillende loop groottes \label{tab:loops}}
\end{table}

Om experimenten snel te laten verlopen is gekozen om de rest van de
experimenten met groottes $10^6$ uit te voeren. Er wordt gebruik gemaakt
van 2 fitness functies in het GA algoritme. De eerste is op basis van
afstandverschillen tussen de nodes, de tweede rekend het aantal
snijpunten uit. Om te kijken welke resultaten het oplevert als we de
fitness getallen in verschillende houdingen bij elkaar optellen, is de
code telkens aangepast en opnieuw gecompileerd. De resultaten hiervan
staan in tabel~\ref{tab:verhoudingen}. 
\begin{table}
\begin{tabular}{c|c|c|c}
gewicht snijpunt & gewicht afstand & fitness cirkel & fitness 10 nodes \\
\hline
1  &  1 & 2/0/2   & 18/128/146 \\
1  &  0 & 26/0/0  & 213/50/50  \\
1  &  2 & 0/15/15 & 64/117/245 \\
1  & 10 & 0/26/26 & 17/193/363 \\
2  &  1 & 0/0/0   & 66/77/214  \\
10 &  1 & 0/0/0   & 159/54/699 \\
\end{tabular}
\caption{Experimenten met verschillende fitness berekeningen fitness
weergegeven als fitness intersection/distance/overall 
\label{tab:verhoudingen}}
\end{table}

\begin{table}
\begin{tabular}{c|c|c}
$MUT\_LEVEL$ & fitness cirkel & fitness 10 nodes \\
\hline
 1 & 14/16/30 & 213/97/310 \\
10 & 0/4/4    & 79/114/193 \\
25 & 5/7/12   & 59/108/167 \\
50 & 0/2/2    & 18/128/146 \\
75 & 13/9/22  & 25/131/156 \\
90 & 10/8/18  & 29/112/141 \\
99 & 0/0/0    & 23/116/139 \\
\end{tabular}
\caption{Experimenten met verschillende mutatie niveaus weergegeven als
fitness intersection/distance/overall \label{tab:mutaties}}
\end{table}

Het derde experiment veranderd de mutatie snelheid van het algoritme,
dit is gedaan door de $MUT\_LEVEL$ aan te passen. \\De resultaten hiervan
zijn te vinden in tabel~\ref{tab:mutaties}.

Voor de visualisatie zijn de programma's graphviz~\cite{graphviz} en
imagemagick~\cite{imagemagick} gebruikt. Graphviz heeft door middel
van het subprogramma $neato$ een ingebouwd algoritme om het beste plaatje 
te plotten en kan tevens `dom' gemaakt worden met de vlag $-n2$ zodat onze
uitvoer geplot kan worden. \\
Imagemagick zorgt voor het samenvoegen van de
plaatjes en toevoegen van de labels. In figuur~\ref{fig:beste-cirkel} is de
beste uitvoer van $input-circular.txt$ geplot.
Figuur~\ref{fig:beste-10nodes} heeft de beste uitvoer van $input10.txt$.

\begin{center}
\begin{figure}
\includegraphics[width=\textwidth]{beste-cirkel.ps}
\caption{Beste uitvoer $input-circular.txt$, $fitness=0$}
\label{fig:beste-cirkel}
\end{figure}
\end{center}

\begin{center}
\begin{figure}
\includegraphics[width=\textwidth]{beste-10nodes.ps}
\caption{Beste uitvoer $input10.txt$, $fitness=139$}
\label{fig:beste-10nodes}
\end{figure}
\end{center}


\section{Conclusies}
De implementatie van het GA algoritme lijkt niet perfect te werken en te
selectief te werk te gaan, vanwege de optimatisatie is het mogelijk met
een hoger $MUT\_LEVEL$ nummer bijna alle oplossingen af te gaan waardoor
de optimale oplossing eruit komt vallen. Het zoeken naar betere
combinatie functies zou een oplossing kunnen bieden.

Verder valt op dat de generereerde plaatjes met een bepaalde belangrijke
eigenschap geen rekening is gehouden, namelijk om de afstand tussen elke
node zo groot mogelijk te maken. Hierdoor vallen nodes over elkaar geen
en is de grafische implementatie zeer slecht, terwijl de oplossing toch
als optimaal aangeboden worden.

De random seed is in alle gevallen hetzelfde gezet (namelijk $0$),
onderzocht kan worden of het wijzigen van de seed nog invloed heeft op
de resultaten.


\begin{thebibliography}{XX}

\bibitem{assignment}
W.A.~Kosters, Kunstmatige intelligentie Programmeer-opgave 4 van 2008
-- Genetische Algorithmen, \url{http://www.liacs.nl/home/kosters/AI/ga08.html}

\bibitem{course}
W.A.~Kosters, Kunstmatige intelligentie, \url{http://www.liacs.nl/home/kosters/AI.html}

\bibitem{darwin}
Darwin, Charles, On the Origin of Species by Means of Natural Selection,
or the Preservation of Favoured Races in the Struggle for Life, John
Murray, London, 1859,
\url{http://www.literature.org/authors/darwin-charles/the-origin-of-species/index.html}

\bibitem{aibook}
S.J. Russell en P. Norvig, Artificial Intelligence, A Modern Approach,
Second ediion, Prentice Hall, 2003.

\bibitem{aisheet}
W.A.~Kosters, Kunstmatige intelligentie College neurale netwerken 2008,
\url{http://www.liacs.nl/~kosters/AI/genetisch.pdf}

\bibitem{line-intersect}
lbackstrom, Geometry Concepts: Line Intersection and its Applications,
\url{http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2}

\bibitem{graphviz}
Graphviz, homepage, \url{http://graphviz.org}

\bibitem{imagemagick}
Imagemagick, homepage, \url{http://imagemagick.org}

\end{thebibliography}

\newpage
\advance\textwidth by 8cm
\advance\oddsidemargin by -3cm
\advance\evensidemargin by -3cm
\advance\topmargin by -2cm
\advance\textheight by 4cm
\advance\footskip by -4cm
\marginparwidth 0cm
\twocolumn
\section*{Appendix}
De GA code en de test arrays zagen er als volgt uit:
\newline
\tiny
%preformatted with `source-highlight -n -f latex bridge.cc`
\input{ga.cpp}
\input{input-circular.txt}
\input{input10.txt}
\onecolumn
\end{document}