% % $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}