\chapter{Podstawowe pojęcia}

\section{Algorytmy genetyczne}

Algorytm genetyczny jest to metaheurystyka zainspirowana teorią ewolucji
Charlsa Darwin'a. Algorytm odzierciedla zjawisko ewolucji biologicznej.
W procesie naturalnej selekcji najlepsze osobniki biorą udział w reprodukcji,
dając początek nowej, lepiej przystosowanej generacji.
% przecinek

Naturalna selekcja zaczyna się od doboru najdoskonalszych osobników z populacji.
Biorą one udział w reprodukcji przekazując część swoich genów potomkom. Nowa
generacja powinna być lepiej przystosowana niż rodzice, ponieważ jest
połączeniem genów, które zapewniły przeżycie rodzicom. W przypadku gdy wśród nowego
potomstwa znalazłyby się słabe
organizmy, to nie ma obawy, że ich geny przejdą do następnego pokolenia, ponieważ
najprawdobniej nie dożyją one okresu rozrodczego. W ten sposób każde kolejne
pokolenie jest lepsze niż poprzednie.
Powyższa wiedza, wynikająca z obserwacji praw natury, została przełożona na grut
matemtyki i informatyki tworząc algorytm genetyczny.
% przecinek
\newpage
\enlargethispage{12\baselineskip}
Na algorytm genetyczny składają się:
\vspace*{-1mm}
\begin{itemize}[noitemsep]
% \setlength\itemsep{0.005em}
\item inicjalizacja populacji,
\item funkcja przystosowania (stosowana przy ewaluacji i selekcji),
\item selekcja,
\item krzyżowanie,
\item mutacja.
\end{itemize}

\vspace*{-8mm}

\begin{figure}[h!]
\centering
\includegraphics[width=0.9\hsize]{overview_GA.png}
\caption{Schemat działania algorytmu genetycznego.}
\label{overview_ga_pic}
\end{figure}

\newpage
\subsection{Inicjalizacja populacji}
Algorytm zaczyna się od utworzenia zbioru osobników zwanych populacją. Każdy z
osobników jest rozwiązaniem problemu obliczeniowego. Osobnik reprezentowany jest
poprzez zbiór genów (parametrów) nazywanych chromosem.
Chromosom \newline jest najczęściej kodowany za pomocą:
\begin{itemize}
\item wektora genów, z których każdy reprezentowany jest przez liczbę całkowitą,
  a czasem nawet liczbę rzeczywistą,
\item drzewiastych struktur danych.
\end{itemize}


\begin{example}
\end{example}
\begin{figure}[tbh]
\centering
\includegraphics[width=0.7\hsize]{kodowanie.png}
\caption{Przykład osobników zakodowanych binarnie.}
\label{kodowanie_pic}
\end{figure}

\subsection{Funkcja przystosowania}
Funkcja przystosowania określa jak bardzo przystosowany jest osobnik (miara
jakości osobnika). Im bardziej będzie przystosowany dany osobnik tym bardziej będzie
faworyzowany w procesie selekcji. Funkcja przystosowania dobierana jest w
zależności od modelu rozwiązywanego problemu, zwykle algorytm genetyczny dąży \newline do
jej minializacji lub maksymalizacji.
\begin{example}
Dla problemu
komiwojażera algorytm genetyczny będzie premiował te rozwiązania (w tym wypadku cykle Hamiltona), których suma
wag krawędzi jest najbliższa minimalnej sumie wag krawędzi w cyklu Hamiltona.
\end{example}

\subsection{Selekcja}
\enlargethispage{6\baselineskip}
Z każdej generacji wybierany jest podzbiór populacji, który będzie brał udział
\newline w
rozmnażaniu, czyli w tworzeniu nowej generacji. Pojedyńcze osobniki wybierane
\newline są na
podstawie funkcji przystosowania. Im lepiej przystosowany dany osobnik tym
większe będzie miał szanse na wzięcie udziału w reprodukcji.

\noindent Wśród metod selekcji chromosomów wyróżniamy między innymi:
\vspace*{-3mm}
\begin{itemize}
\setlength\itemsep{0.005em}
\item metodę ruletki,
\item metodę rankingową,
\item metodę turniejową.
\end{itemize}

\begin{example}
\textbf{Metoda ruletki.} \newline
Niech $f(o_i)$ będzie przystosowaniem osobnika $o_i$ z populacji $P$, wtedy
prawdopodbieństwo wyboru $o_i$ wynosi:
\begin{equation*}
   p_i = \frac{f(o_i)}{\sum_{j=1}^N f(o_i)},
\end{equation*}
gdzie $N$ to rozmiar populacji $P$.
\end{example}
\vspace*{-3mm}
\begin{figure}[h!]
\centering
\includegraphics[width=0.7\hsize]{selekcja.png}
\caption{Przykład selekcji metodą ruletki. Losowana jest liczba $r$ z zakresu
  $(0,F)$. \newline W
tym wypadku wybrany został osobnik $o_4$.}
\label{selekcja_pic}
\end{figure}

\subsection{Krzyżowanie}
Krzyżowanie jest to metoda używana do tworzenia nowych osobników. Każdy nowy osobnik tworzony jest
z pary rodziców. Krzyżowanie polega na łączeniu dwóch
genotypów w jeden. Potomek rodziców ma zespół cech, które są kombinacją genotypów
rodziców.
\enlargethispage{4\baselineskip}

\begin{example}
\end{example}
\begin{figure}[h!]
\centering
\includegraphics[width=1\hsize]{krzyzowanie.png}
\caption{Przykładowe krzyżowanie osobników zakodowanych binarnie.}
\label{krzyzowanie_pic}
\end{figure}

\subsection{Mutacja}
Mutacja jest to operator genetyczny gwarantujący różnorodność osobników. Mutacja wprowadza do
genotypu losowe zmiany. Zazwyczaj mutacja zachodzi z bardzo niskim
prawdopodbieństwem - najczęściej około 1\%. Wyższe prawdopodbieństwo mogłoby
spowodobać, że rozwiązania psułyby się zamiast delikatnie zmieniały.

W zależności od kodowania mutację można przeprowadzić przykładowo na następujące sposoby:
\begin{itemize}
\item w przypadku kodowania binarnego można zanegować losowy bit,
\item w przypadku kodowania liczbami całkowitymi (rzeczywistymi) można losowy
  gen zamienić liczbą wylosowaną z ustalonego ręcznie zakresu liczb całkowitych (rzeczywistych).
\end{itemize}

\newpage
\begin{example}
\end{example}
\begin{figure}[th]
\centering
\includegraphics[width=0.3\hsize]{mutacja.png}
\caption{Mutacja poprzez zanegowanie losowego bitu.}
\label{mutacja_pic}
\end{figure}

\subsection{Kryterium stopu}
Proces generowania coraz to nowyszych pokoleń trwa aż do osiągnięcia kryterium stopu. Popularne kryteria to:
\begin{itemize}
\item z góry ustalona liczba iteracji,
\item znalezienie osobnika (rozwiązania), dla którego funkcja przystosowania
  \newline da
  wystarczająco dobry wynik,
\item wykorzystanie określonej liczby zasobów np. czasu pracy procesora lub pieniędzy,
\item przerwanie procesu, gdy kolejne iteracje nie tworzą lepszych rozwiązań,
\item osiągnięcie najlepszego rozwiązania.
\end{itemize}

\newpage
\section{Sieci neuronowe}