144 lines
5.2 KiB
Org Mode
144 lines
5.2 KiB
Org Mode
|
#+TITLE: Práctica 2
|
||
|
|
#+SUBTITLE: Metaheurísticas
|
||
|
|
#+AUTHOR: Amin Kasrou Aouam
|
||
|
|
#+DATE: 2021-06-22
|
||
|
|
#+PANDOC_OPTIONS: template:~/.pandoc/templates/eisvogel.latex
|
||
|
|
#+PANDOC_OPTIONS: listings:t
|
||
|
|
#+PANDOC_OPTIONS: toc:t
|
||
|
|
#+PANDOC_METADATA: lang=es
|
||
|
|
#+PANDOC_METADATA: titlepage:t
|
||
|
|
#+PANDOC_METADATA: listings-no-page-break:t
|
||
|
|
#+PANDOC_METADATA: toc-own-page:t
|
||
|
|
#+PANDOC_METADATA: table-use-row-colors:t
|
||
|
|
#+PANDOC_METADATA: colorlinks:t
|
||
|
|
#+PANDOC_METADATA: logo:/home/coolneng/Photos/Logos/UGR.png
|
||
|
|
#+LaTeX_HEADER: \usepackage[ruled, lined, linesnumbered, commentsnumbered, longend]{algorithm2e}
|
||
|
|
* Práctica 2
|
||
|
|
|
||
|
|
** Introducción
|
||
|
|
|
||
|
|
En esta práctica, usaremos distintos algoritmos de búsqueda, basados en poblaciones, para resolver el problema de la máxima diversidad (MDP). Implementaremos:
|
||
|
|
|
||
|
|
- Algoritmo genético
|
||
|
|
- Algoritmo memético
|
||
|
|
|
||
|
|
** Algoritmos
|
||
|
|
|
||
|
|
*** Genético
|
||
|
|
|
||
|
|
Los algoritmos genéticos se inspiran en la evolución natural y la genética. Generan un conjunto de soluciones inicial (i.e. población), seleccionan un subconjunto de individuos sobre los cuales se opera, hacen operaciones de recombinación y mutación, y finalmente reemplazan la población anterior por una nueva.
|
||
|
|
|
||
|
|
El procedimiento general del algoritmo queda ilustrado a continuación:
|
||
|
|
|
||
|
|
\begin{algorithm}
|
||
|
|
\KwIn{A list $[a_i]$, $i=1, 2, \cdots, n$, that contains the population of individuals}
|
||
|
|
\KwOut{Processed list}
|
||
|
|
|
||
|
|
$P(t) \leftarrow initializePopulation()$
|
||
|
|
$P(t) \leftarrow evaluatePopulation()$
|
||
|
|
|
||
|
|
\While{$\neg stop condition $}{
|
||
|
|
$t = t + 1$
|
||
|
|
|
||
|
|
$parents \leftarrow selectParents(P(t-1))$
|
||
|
|
|
||
|
|
$offspring \leftarrow recombine(parents)$
|
||
|
|
|
||
|
|
$offspring \leftarrow mutate(offspring)$
|
||
|
|
|
||
|
|
$P(t) \leftarrow replacePopulation(P(t-1), offspring)$
|
||
|
|
|
||
|
|
$P(t) \leftarrow evaluatePopulation()$
|
||
|
|
}
|
||
|
|
\KwRet{$P(t)$}
|
||
|
|
\end{algorithm}
|
||
|
|
|
||
|
|
Procedemos a la implementación de 4 variantes distintas, según 2 criterios:
|
||
|
|
|
||
|
|
**** Criterio de reemplazamiento
|
||
|
|
- *Generacional*: la nueva población reemplaza totalmente a la población anterior
|
||
|
|
- *Estacionario*: los dos mejores hijos reemplazan los dos peores individuos en la población anterior
|
||
|
|
**** Operador de cruce
|
||
|
|
- *Uniforme*: mantiene las posiciones comunes de ambos padres, las demás se eligen de forma aleatoria de cada padre (requiere reparador)
|
||
|
|
- *Posición*: mantiene las posiciones comunes de ambos padres, elige el resto de elementos de cada padre y los baraja. Genera 2 hijos.
|
||
|
|
|
||
|
|
*** Memético
|
||
|
|
|
||
|
|
Los algoritmos meméticos surgen de la hibridación de un algoritmo genético, con un algoritmo de búsqueda local. El resultado es un algoritmo que posee un buen equilibrio entre exploración y explotación.
|
||
|
|
|
||
|
|
El procedimiento general del algoritmo queda ilustrado a continuación:
|
||
|
|
|
||
|
|
\begin{algorithm}
|
||
|
|
\KwIn{A list $[a_i]$, $i=1, 2, \cdots, n$, that contains the population of individuals}
|
||
|
|
\KwOut{Processed list}
|
||
|
|
|
||
|
|
$P(t) \leftarrow initializePopulation()$
|
||
|
|
$P(t) \leftarrow evaluatePopulation()$
|
||
|
|
|
||
|
|
\While{$\neg stop condition $}{
|
||
|
|
\If{$certain iteration$}{
|
||
|
|
$P(t) <- localSearch(P(t-1))$
|
||
|
|
}
|
||
|
|
$t = t + 1$
|
||
|
|
|
||
|
|
$parents \leftarrow selectParents(P(t-1))$
|
||
|
|
|
||
|
|
$offspring \leftarrow recombine(parents)$
|
||
|
|
|
||
|
|
$offspring \leftarrow mutate(offspring)$
|
||
|
|
|
||
|
|
$P(t) \leftarrow replacePopulation(P(t-1), offspring)$
|
||
|
|
|
||
|
|
$P(t) \leftarrow evaluatePopulation()$
|
||
|
|
}
|
||
|
|
\KwRet{$P(t)$}
|
||
|
|
\end{algorithm}
|
||
|
|
|
||
|
|
Procedemos a la implementación de 3 variantes distintas:
|
||
|
|
- Búsqueda local sobre todos los cromosomas
|
||
|
|
- Búsqueda local sobre un subconjunto aleatorio de cromosomas
|
||
|
|
- Búsqueda local sobre un el subconjunto de los mejores cromosomas
|
||
|
|
|
||
|
|
** Implementación
|
||
|
|
|
||
|
|
La práctica ha sido implementada en /Python/, usando las siguientes bibliotecas:
|
||
|
|
|
||
|
|
- NumPy
|
||
|
|
- Pandas
|
||
|
|
|
||
|
|
*** Instalación
|
||
|
|
|
||
|
|
Para ejecutar el programa es preciso instalar Python, junto con las bibliotecas *Pandas* y *NumPy*.
|
||
|
|
|
||
|
|
Se proporciona el archivo shell.nix para facilitar la instalación de las dependencias, con el gestor de paquetes [[https://nixos.org/][Nix]]. Tras instalar la herramienta Nix, únicamente habría que ejecutar el siguiente comando en la raíz del proyecto:
|
||
|
|
|
||
|
|
#+begin_src shell
|
||
|
|
nix-shell
|
||
|
|
#+end_src
|
||
|
|
|
||
|
|
** Ejecución
|
||
|
|
|
||
|
|
La ejecución del programa se realiza mediante el siguiente comando:
|
||
|
|
|
||
|
|
#+begin_src shell
|
||
|
|
python src/main.py <dataset> <algoritmo> <parámetros>
|
||
|
|
#+end_src
|
||
|
|
|
||
|
|
Los parámetros posibles son:
|
||
|
|
|
||
|
|
| dataset | algoritmo | parámetros |
|
||
|
|
| Cualquier archivo de la carpeta data | genetic | uniform/position generation/stationary |
|
||
|
|
| | memetic | all/random/best |
|
||
|
|
|
||
|
|
También se proporciona un script que ejecuta 1 iteración de cada algoritmo, sobre cada uno de los /datasets/, y guarda los resultados en una hoja de cálculo. Se puede ejecutar mediante el siguiente comando:
|
||
|
|
|
||
|
|
#+begin_src shell
|
||
|
|
python src/execution.py
|
||
|
|
#+end_src
|
||
|
|
|
||
|
|
*Nota*: se precisa instalar la biblioteca [[https://xlsxwriter.readthedocs.io/][XlsxWriter]] para la exportación de los resultados a un archivo Excel.
|
||
|
|
|
||
|
|
* Análisis de los resultados
|
||
|
|
|
||
|
|
Desafortunadamente, debido a un tiempo de ejecución excesivamente alto (incluso tras ajustar los metaparámetros) no podemos proporcionar resultados de la ejecución de los algoritmos.
|