\documentclass[11pt]{article}

\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}



\usepackage{times}


\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
            linkcolor = blue,
            urlcolor  = blue,
            citecolor = blue,
            anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
  \errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother






\renewenvironment{abstract}
  {{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
  {\bigskip}

\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}


\usepackage{authblk}


\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%

\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}

\usepackage[utf8]{inputenc}
\usepackage[ngerman,english]{babel}








\newcommand{\msun}{\,\mathrm{M}_\odot} 

\begin{document}

\title{Estudio Comparativo de Algoritmos Evolutivos Bioinspirados y
Trayectoriales para la soluci\selectlanguage{ngerman}ón de los problemas agente viajero y
programación de horarios\selectlanguage{english}}



\author[1]{Marlene Lopez}%
\author[1]{Gustavo López}%
\affil[1]{Instituto Tecnológico de León, Maestría en Ciencias de la Computación}%


\vspace{-1em}



  
  \date{May 05, 2024}


\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup





\selectlanguage{english}
\begin{abstract}
En el presente trabajo se muestran los resultados obtenidos tras la
comparaci\selectlanguage{ngerman}ón de los Algoritmos Metahurísticos Bioinspirados; Algoritmo
Genético (GA) , Memético (MA) y Sistema Inmune (ISA). La instancia
tomada como prueba fue el Problema OneMax o Conteo de Bits, para
poblaciones de 500, 1,000, 2,000 y 5,000. El objetivo establecido fue
observar el comportamiento de los mismos; los parámetros que influyen en
sus resultados, así como determinar el de mejor desempeño. Bajo pruebas
estadísticas empleadas, el algoritmo MA obtuvo mejores resultados
déspues el algoritmo ISA y GA respectivamente, siendo evaluados con
distintas configuraciones cada uno.~%
\end{abstract}\selectlanguage{ngerman}%



\sloppy


\selectlanguage{ngerman}\section { Introducción}
La optimiz  ación es un problema matemático comunmente encontrado en todas las disciplinas de ingeniería. Esta, literalmente significa encontrar la mejor solución posible / deseable. Los  algoritmos de optimización pueden ser de naturaleza determinista o estocástica. Los métodos anteriores para resolver problemas de optimización requieren enormes esfuerzos computacionales, que tienden a fallar a medida que aumenta el tamaño del problema. Esta es la motivación para emplear algoritmos de optimización estocástica bio-inspirados como alternativas computacionalmente eficientes al enfoque determinista. Las metaheurísticas se basan en la mejora de una población de soluciones o una única solución y emplean mayormente aleatorización (Algoritmo Genético,GA) y búsqueda local (Algoritmo Memético, MA) para resolver el problema dado.
Los algoritmos metahurísticos gozan de una buena reputación para resolver problemas de optimización como Traveling Salesman Problem y Timetabling. Algunos de estos algoritmos se consideran como trayectoriales debido a la forma en que buscan dirigir un solo individuo hacia el óptimo global.

En el presente trabajo se muestra la implementación de algoritmos metaheurísticos poblacionales: Algoritmo Genético, Memético y Sistema Inmune así como, algoritmos trayectoriales: Recocido Simulado y Búsqueda Local Iterada, para la resolución de los  problemas OneMax, Traveling Salesman Problem y Timetabling. 

\section{Antecedentes}

Los Algoritmos Evolutivos son sistemas computacionales diseñados para solucionar problemas altamente no-lineales, tomando ideas del proceso avolutivo y de adaptación de la naturaleza, las cuales se grupan bajo la denominada teoría Neo-Darwiniana de la evolución \cite{Fogel_2005,Fogel}.

Gran parte de la terminolóigia utilizada en los algoritmos evolutivos se ha tomado prestada de los conceptos biológicos en los que se inspira (por ejemplo, cromosoma, alelos, etc.).

Una característica notable de los algoritmos evolutivos es que son poblacionales, lo que significa que manipulan simultáneamente un conjunto de soluciones potenciales al problema y no una solución única, como suelen hacer las técnicas clásicas de optimización. El uso de una población de soluciones potenciales a un problema hace a los algoritmos evolutivos menos suceptibles de quedar atrapados en óptimos locales \cite{Cortes2004}.

Los operadores genéticos básicos son los siguientes:
\begin{itemize}
\item \textbf{Selección:} Consiste de un mecanismo (probabilístico o determinista) que permite elegir a los individuos que fungirán como padres de la siguiente generación.
\item \textbf{Cruza o Recombinación:} Se refiere al intercambio de información (material genético) entre dos padres que han sido seleccionados con base en su aptitud.
\item \textbf{Mutación:} Consiste en hacer pequeñas perturbaciones a los individuos recién creados para la nueva población con la finalidad de explorar zonas del espacio de búsqueda que la cruza no pueda alcanzar.

\end{itemize}



Sin embargo, también existen algoritmos evolutivos que son considerados
como trayectoriales dado que para encontrar las soluciones óptimas
parten de un punto específico y dirigen la exploración a través de la
inspección de soluciones vecinas siguiendo aquellas que resultan ser más
aptas. La necesidad de proveer a estos algoritmos de los aspectos tanto
exploratorio como explotatorio, i.e. la capacidad de realizar una
búsqueda suficientemente amplia y específica del espacio de búsqueda,
implica dotarlos de algún mecanismo que controle la probabilidad de
aceptar soluciones peores conforme el espacio de solución es explorado.~

\section{Métodos}
\subsection{Algoritmos Poblacionales}
\subsubsection{Algoritmo Genético (GA)}
El algoritmo genético es un algoritmo inspirado en la evolución biológica y su base genético-molecular, que simula la  progresión temporal de una población de individuos sometiéndola a una serie de transformaciones aleatorias y selecciones semejantes a las que ocurren en la naturaleza evolutiva biológica\cite{Holland1975}. Los GAs buscan dentro de un conjunto los individuos más aptos, en cuyos cromosomas codifican la información de una posible solución al problema usualmente representada como una cadena de números; en cada paso del ciclo iterativo se evolucionan los individuos y se evalúan con alguna medida de aptitud hasta que alguna condición de paro se cumple. La evolución se logra aplicando repetidamente sobre los individuos los operadores généticos de selección, cruza, mutación y reemplazo.

La selección consiste en determinar los individuos de la población que serán propicios para cruzar, a través de algún criterio específico. Entre estos figuran la selección por k-torneo\cite{miller} y la selección Vasconcelos\cite{kuri}. La cruza es la acción de combinar los individuos seleccionados para obtener nuevos individuos; existen criterios de cruza como el \textit{single-point crossover} que divide los padres en un cromosoma específico y los recombina a partir de ello. La mutación consiste en realizar sutiles modificaciones aleatorias sobre el código genético de un individuo, con baja probabilidad de ocurrencia, para introducir variaciones estocásticas sobre la población. El reemplazo ocurre al obtener una nueva generación de individuos generados a partir de la generación anterior. En la figura 1 se denota el algoritmo genético como un diagrama de flujo.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.98\columnwidth]{figures/Figura-1-Diagrama-de-flujo-de-un-algoritmo-genetico-simple/Figura-1-Diagrama-de-flujo-de-un-algoritmo-genetico-simple}
\caption{\selectlanguage{ngerman}{Diagrama de flujo del Algoritmo Genético
{\label{592472}}%
}}
\end{center}
\end{figure}\selectlanguage{ngerman}

Con estos mecanismos se busca que la población de individuos presente iterativamente una mejora en la evaluación de sus aptitudes, para determinar eventualmente aquellos que representen soluciones lo más cercano posible a la solución óptima.

En este trabajo se determinaron dos variaciones del algoritmo genético para dar solución al problema  de Onemax. Dichas configuraciones incluyen la selección de heurísticas como se indica en la tabla \ref{confGA}.\selectlanguage{english}
\begin{table}[]
\centering
\caption{\selectlanguage{ngerman}{Configuraciones para el Algoritmo Genético}}
\label{confGA}
\begin{tabular}{@{}ccccccc@{}}
\hline
\textbf{Algoritmo} & \selectlanguage{ngerman}\textbf{\begin{tabular}[c]{@{}c@{}}Máximo\\   Generaciones\end{tabular}} & \selectlanguage{ngerman}\textbf{\begin{tabular}[c]{@{}c@{}}Máximo de\\   llamadas a función\end{tabular}} & \textbf{\begin{tabular}[c]{@{}c@{}}Probabilidad de\\   muta\end{tabular}} & \textbf{\begin{tabular}[c]{@{}c@{}}Porcentaje de\\   elitismo\end{tabular}} & \selectlanguage{ngerman}\textbf{Selección} & \textbf{Cruza} \\ \midrule
GA1                & 3,000                                                                    & 1,000,000                                                                         & 0.05                                                                      & 0.3                                                                         & k-tournament       & Single point   \\
\hline
\end{tabular}
\end{table}


\selectlanguage{ngerman}\subsubsection{Algoritmo Memético (MA)}
El Algoritmo Memético representa una sinergización con el Algoritmo Genético o con cualquier enfoque de algoritmos poblacionales en el que se utilizan aprendizaje individual o procedimientos para mejora local para el problema de búsqueda. Está inspirado tanto en los principios de la evolución natural de Charles Darwin, como en la noción de Clinton Richard Dawkins del \textit{meme} como una idea, comportamiento o estilo que se esparce de persona a persona en una cultura. El término fue introducido por Moscato \cite{moscato1989}.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/f0107112/f0107112}
\caption{\selectlanguage{ngerman}{Seudocódigo del Algoritmo Memético
{\label{547143}}%
}}
\end{center}
\end{figure}\selectlanguage{ngerman}\selectlanguage{english}
\begin{table}[]
\centering
\caption{\selectlanguage{ngerman}{Configuraciones para el Algoritmo Memético}}
\label{my-label}
\begin{tabular}{@{}ccccccccc@{}}
\hline
  \multicolumn{1}{p{1.2cm}}{\textbf{Algoritmo}} & \multicolumn{1}{p{1.2cm}}{\textbf{ No. Max.Genrcs.}} & \multicolumn{1}{p{1.2cm}}{\textbf{CallsFunction}} & \multicolumn{1}{p{1.2cm}}{\textbf{Prob. muta}} & \multicolumn{1}{p{1.2cm}}{\textbf{\% Elitismo}} & \selectlanguage{ngerman}\multicolumn{1}{p{1.2cm}}{\textbf{Selección}}  & \selectlanguage{ngerman}\multicolumn{1}{p{1.2cm}}{\textbf{Búsquedas locales}} & \selectlanguage{ngerman}\multicolumn{1}{p{1.2cm}}{\textbf{Perturbación}}\\ 

\midrule
MA1                & 3,000                                                                    & 1,000,000                                                                         & 0.05                                                                      & 0.3                                                                         & k-tournament         & 7                                                                      & kflip 5       \\
\hline
\end{tabular}
\end{table}\\

\subsubsection{Algoritmo Sistema Inmune (ISA)}

El AIS se basa en el funcionamiento del sistema inmune humano, que es capaz de reconocer en una forma muy eficiente cualquier agente pat\selectlanguage{ngerman}ógeno. Esta es una teoría inmune clásica para entender el sistema inmunológico como un sistema que identifica a self (agente propio) o a non self(agente patógeno) \cite{li2015negative}.\selectlanguage{english}
\begin{table}
\begin{center}
    \caption{{Configuraciones para el algoritmo Sistema Inmune.}}
    \begin{tabular}{c c c c c c }
    \hline
         \multicolumn{1}{p{1.5cm}}{\textbf{Algoritmo}} & \selectlanguage{ngerman}\multicolumn{1}{p{1.5cm}}{\textbf{ Máximo de generaciones}} & \selectlanguage{ngerman}\multicolumn{1}{p{1.5cm}}{\textbf{Maximo de llamadas a función}} & \multicolumn{1}{p{1.5cm}}{\textbf{Elitismo}} & \multicolumn{1}{p{1.5cm}}{\textbf{No. de Clones}} & \selectlanguage{ngerman}\multicolumn{1}{p{1.5cm}}{\textbf{Perturbación}}\\ 
    \hline
    ISA1&3,000&1,000,000&0.3&3&K-flip 8\\ 
    
\hline
    \end{tabular} 
    \label{confISA}
\end{center}
\end{table}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.42\columnwidth]{figures/IS/IS}
\caption{\selectlanguage{ngerman}{\protect\cite{li2015negative}Diagrama de flujo del algoritmo de optimización ISA
{\label{718750}}%
}}
\end{center}
\end{figure}\selectlanguage{ngerman}



\subsection{Algoritmos Trayectoriales}

\subsubsection{B\'usqueda Local Iterada}
La idea principal de búsqueda local iterativa es tratar de generar vecinos que nos generen pozos de atracción vecinos (o al menos diferentes)\cite{manzanares2004}. El paso clave es determinar el primer vecino que pertenece a otro pozo de atracción. Con esto, podríamos ir generando pozos de atracción vecinos.

Sin embargo, es un proceso computacionalmente muy costoso, por la cantidad de llamadas a búsqueda local que se requieren \cite{manzanares2004}.

En la imagen \ref{784974} se puede observar la serie de pasos para desarrollar el algoritmo de Búsqueda Local Iterada.
 
 En la tabla \ref{configILS} se pueden observar los parámetros establecidos para dos distintas configuraciones del algoritmo.\selectlanguage{english}
\begin{table}
\begin{center}
    \caption{\selectlanguage{ngerman}{Configuraciones para el algoritmo Búsqueda Local Iterada (ILS).}}
    \begin{tabular}{c c c c c c }
    \hline
         \multicolumn{1}{p{1.5cm}}{\textbf{Algoritmo}} & \selectlanguage{ngerman}\multicolumn{1}{p{1.5cm}}{\textbf{ Máximo de generaciones}} & \selectlanguage{ngerman}\multicolumn{1}{p{1.5cm}}{\textbf{Maximo de llamadas a función}} & \multicolumn{1}{p{1.5cm}}{\textbf{No. LS}} & \selectlanguage{ngerman}\multicolumn{1}{p{1.5cm}}{\textbf{Perturbación}}\\ 
    \hline
    ILS1&3,000&1,000,000&5&K-flip 1\\ 
    ILS2&3,000&1,000,000&9&Inversing\\ 
    
\hline
    \end{tabular} 
    \label{configILS}
\end{center}
\end{table}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.56\columnwidth]{figures/Screenshot-2018-5-22-Abrir-SA-ILS-pptx---Dropbox/Screenshot-2018-5-22-Abrir-SA-ILS-pptx---Dropbox}
\caption{{Algoritmo Busqueda Local Iterada
{\label{784974}}%
}}
\end{center}
\end{figure}

\subsubsection{Recocido Simulado}

El recocido simulado est\selectlanguage{ngerman}á inspirado en el proceso de recocido en la metalurgia, el cual implica una técnica que incluye el calentado y enfríado controlado de un material para aumentar el tamaño de sus cristales (arquitectura molecular interna) y así reducir sus defectos. 

Esta noción del cambio controlado de temperatura es interpretada como un descenso pequeño en la probabilidad de aceptar soluciones menos aptas a medida que el espacio de búsqueda es explorado, lo que implica una búsqueda extensiva.

A cada paso, el algoritmo seleccion aleatoriamente una solución cercana a la actual, mide su calidad, y después decide si moverse hacia ella o quedarse en la actual basado en alguna de las dos probabilidades entre las que escoje basado en el hecho de si la nueva solución es mejor o peor que la actual. Durante la búsqueda, el descenso en la temperatura se refleja en una mayor probabilidad de dirigirse siempre a la mejor solución, y en una menor probabilidad de dirijirse a soluciones menos aptas \cite{Semenovskaya:a24269}.

 En la tabla \ref{configAS} se pueden observar los parámetros establecidos para dos distintas configuraciones del algoritmo.\selectlanguage{english}
\begin{table}
\begin{center}
    \caption{{Configuraciones para el algoritmo Recocido Simulado (SA).}}
    \begin{tabular}{c c c c c c c}
    \hline
         \multicolumn{1}{p{1.2cm}}{\textbf{Algoritmo}} & \multicolumn{1}{p{1.2cm}}{\textbf{ Generaciones Max.}} & \selectlanguage{ngerman}\multicolumn{1}{p{1.2cm}}{\textbf{ Máximo Iter Temp}} & \multicolumn{1}{p{1.2cm}}{\textbf{Maximo FunCalls}} & \multicolumn{1}{p{1.2cm}}{\textbf{Prob. Acept}} & \multicolumn{1}{p{1.2cm}}{\textbf{Esquema Temp}}& \selectlanguage{ngerman}\multicolumn{1}{p{1.2cm}}{\textbf{Perturbación}}\\ 
    \hline
    SA1&3,000&100&1,000,000&1&2&K-flip 2\\ 
    SA2&3,000&100&1,000,000&1&2&K-flip 1\\ 
    
\hline
    \end{tabular} 
    \label{configAS}
\end{center}
\end{table}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/v11n21a12g1/v11n21a12g1}
\caption{{Algoritmo Recocido Simulado
{\label{140763}}%
}}
\end{center}
\end{figure}



\selectlanguage{ngerman}\section{Operadores Genéticos Básicos}

\subsection{Métodos de selección}

\subsubsection{Selección mediante Ruleta}
Es una técnica proporcional, lo que significa que la probabilidad de un individuo de ser seleccionado está en proporción a su aptitud. En esta selección se simula que a cada individuo se le asigna una porción de una ruleta, de forma que al girarla, los individuos con una porción mayor tienen mayor probabilidad de ser seleccionados. Sin embargo, debido a su naturaleza probabilística, este esquema permite que aún los individuos menos aptos tengan alguna probabilidad de ser seleccionados para reproducirse\cite{Cortes2004}. En la Fig. \ref{653784} se puede observar el comportamiento de está selección.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.21\columnwidth]{figures/ruleta/ruleta}
\caption{\selectlanguage{ngerman}{La selección por el método de ruleta es proporcional. En este caso, los
individuos que pertenecen a la zona roja y amarilla tienen mayor
probabilidad de ser elegidos respectivamente. Sin embargo el individuo
de la zona azul tambien puede ser seleccionado, aunque con una
probabilidad muy baja.
{\label{653784}}%
}}
\end{center}
\end{figure}\selectlanguage{ngerman}


\subsection{Cruza}
\subsubsection{Cruza a un punto}
En la cruza a un punto, dos padres se cruzan para generar dos hijos, y cada uno de ellos aporta un segmento de su cromosoma. El punto a partir del cual se realiza la cruza se define aleatoriamente. Cada hijo recibe un segmento de cada uno de los padres. La figura \ref{675505} muestra este mecanismo.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Figura-23-Operador-de-Combinacion-con-un-solo-punto-de-cruza/Figura-23-Operador-de-Combinacion-con-un-solo-punto-de-cruza}
\caption{\selectlanguage{ngerman}{Representación de la cruza en un punto. Dos padres generan dos hijos.
{\label{675505}}%
}}
\end{center}
\end{figure}\selectlanguage{ngerman}


\subsection{Muta}
\subsubsection{Muta Uniforme}
iforme consiste en cambiar el valor de cada bit de la cadena cromosómica con una probabilidad determinada, (se recomienda
que sea pequeña, entre 0.01 y 0.001). La finalidad de la mutación es explorar regiones del espacio de búsqueda que el operador de cruza no pudiera alcanzar\cite{Cortes2004}.

\subsubsection{Mutación Flip}

Basado en una mutación generada cromosoma, voltear un poco implica cambiar 0 a 1 y 1 a 0. Se considera un padre y una mutación el cromosoma se genera al azar. Por un 1 en cromosoma de mutación, el bit correspondiente en la matriz el cromosoma se voltea (0 a 1 y 1 a 0) y el hijo del cromosoma es producido. Se usa comúnmente en codificación binaria \cite{Soni2014}.

\subsubsection{Mutación Swap}
La mutación de intercambio funciona seleccionando al azar dos genes en el genotipo y cambiándolos entre si\cite{ramirez2010using}. Un ejemplo de mutación de intercambio se da en la Figura. \ref{281377}.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Captura-de-pantalla-de-2018-05-04-14-20-33/Captura-de-pantalla-de-2018-05-04-14-20-33}
\caption{\selectlanguage{ngerman}{Mutación Swap, los genes 3 y 8 fueron intercambiados.
{\label{281377}}%
}}
\end{center}
\end{figure}\selectlanguage{ngerman}

\subsubsection{Mutación Inversa}
La mutación inversa trabaja seleccionando un subconjunto de los genotipos e invirtiendo el orden de los genes. En la Figura puede verse un ejemplo de está muta\cite{ramirez2010using}.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.63\columnwidth]{figures/Captura-de-pantalla-de-2018-05-04-14-34-061/Captura-de-pantalla-de-2018-05-04-14-34-061}
\caption{\selectlanguage{ngerman}{Mutación Inversa, el subconjunto que va de 4 a 7~ fueron seleccionados y
su orden invertido.
{\label{440745}}%
}}
\end{center}
\end{figure}\selectlanguage{ngerman}

\section{Resultados}

\subsection{El problema TimeTabling}


\begin{itemize}
\item un conjunjo de eventos $ E = \{ e_1, e_2, ...,e_n\}$
\item un conjunto de intervalos de tiempo $ T = \{ t_1, t_2, ..., t_n\}$
\item un grafo $ G(E,L)$  con nodos $E$ y bordes $L \subseteq \{\{u,v\} | u,v \in E \}$. 
\end{itemize}


El grafo $G$ se conoce como grafo de conflicto. Dos eventos se llaman conflictivos si son adyacentes en G. Una tarea es definida por un par ordenado (e,t) tal que $ e \in E$ y $t \in T$ con la interpretación ``. Dos eventos $e_1, e_2$ se traslapan si $\{ e_1, e_2\} \in h_1$. Un horario es llamado ``libre de traslape'' 

Las instancias de prueba utilizadas para el desarrollo del experimento se observan en el siguiente listado. Estas instancias relacionan solo horarios con eventos, siendo estos los conjuntos que conforman el grafo de conflictos.

\begin{itemize}
\item 1
\item 2
\item 16
\item 17
\item 24
\item 25
\item 34
\item 35

\end{itemize}

\subsection{El problema TSP}

Las instancias de prueba utilizadas para el desarrollo del experimento se encuentran en \cite{reinelt1991tsplib} y se observan en el siguiente listado.

\begin{itemize}
\item KroA100
\item KroA150
\item KroA200
\item KroB100
\item KroB150
\item KroB200
\item KroC100
\item KroD100

\end{itemize}



\subsection{Comparativa de los algoritmos y su desempeño}

Las configuraciones establecidas para los algoritmos estan definidas en las tablas \ref{confGA} para el algoritmo Genético con las etiquetas GA1 y GA2. Para el algoritmo Memético \ref{my-label}. Finalmente para el algoritmo Sistema Inmune en la Tabla. \ref{confISA} con las etiquetas ISA1 e ISA2 para cada configuración.

\subsection{Solución al problema TSP}
En la fig \ref{203353} se observan los resultados obtenidos en 33 distintos experimentos realizados de cada algoritmo para la solución al óptimo encontrado en la instancia "KroA100". Las distintas instancias tuvieron un comportamiento muy parecido, las líneas de color rojo corresponden a los minimos encontrados dentro de cada generación mientras que la línea azul representa el promedio de la población, la esperanza dentro de ella. Podemos observar en la fig \ref{203353} a) al algoritmo genético en el cual el promedio y el minimo encontrado se encuentran bastante cercanos, debido a que la población se ve afectada en un porcentaje muy bajo, que a su vez puede o no presentarse entre cada generación, los cambios en el mínimo encontrado son pequeños y se mantienen por valgunas generaciones. En la fig \ref{203353} b) encontramos al algorimo memético, en este caso los saltos hacia un mínimo cada vez más cerca al óptimo son más grandes y se mantienen por más generaciones que el genético, en este caso el promedio de la población se ve directamente afectado ya que, los individuos mutan en cada generación. En el caso del sistema inmune el promedio y el mínimo encontrado tienen una separación menos pronunciada que en el genético, el sistema inmune tiene una velocidad de convergencia mayor debido a que la exploración del mejor uindividuo entre cada generación recurre a una explotación determinada por la clonación del minimo entontrado.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.91\columnwidth]{figures/graficas/graficas}
\caption{\selectlanguage{ngerman}{Gráficas del comportamiento de los algoritmos poblacionales~ en la
solución a una instancia del problema TSP.
{\label{203353}}%
}}
\end{center}
\end{figure}\selectlanguage{ngerman}

En la fig \ref{650384} se observa la tendencia de los algoritmos en cada una de las soluciones experimentales obtenidas, puediendose observar que, el ISA llego a encontrar minimos más pequeños que GA y MA respectivamente. En este caso se presentan 3 de las 10 instancias probpuestas de prueba, dichas graficas mantienen su comportamiento para cada una de las instancias.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.91\columnwidth]{figures/graficas2/graficas2}
\caption{{Medidas de tendencia de los experimentos realizados en las instancias a)
KroA100,b) KroA150 y c) KRoA200.
{\label{650384}}%
}}
\end{center}
\end{figure}

Tr\selectlanguage{ngerman}ás el desempeño de los algoritmos pobblacionales se puede observar el ISA como el algoritmo más fuerte de este experimento.



\subsection{Solución al problema TimeTabling}

En la fig \ref{952806} se observan los resultados obtenidos en 33 distintos experimentos realizados de cada algoritmo para la solución al óptimo encontrado en la instancia 1. Las distintas instancias tuvieron un comportamiento muy parecido, las líneas de color rojo corresponden a los minimos encontrados dentro de cada generación mientras que la línea azul representa el promedio de la población, la esperanza dentro de ella. Podemos observar en la fig \ref{952806} a) al algoritmo genético en el cual el promedio y el minimo encontrado se encuentran bastante cercanos, debido a que la población se ve afectada en un porcentaje muy bajo, que a su vez puede o no presentarse entre cada generación, los cambios en el mínimo encontrado son pequeños y se mantienen por valgunas generaciones. En la fig \ref{952806} b) encontramos al algorimo memético, en este caso los saltos hacia un mínimo cada vez más cerca al óptimo son más grandes y se mantienen por más generaciones que el genético, en este caso el promedio de la población se ve directamente afectado ya que, los individuos mutan en cada generación. En el caso del sistema inmune el promedio y el mínimo encontrado tienen una separación menos pronunciada que en el genético, el sistema inmune tiene una velocidad de convergencia mayor debido a que la exploración del mejor uindividuo entre cada generación recurre a una explotación determinada por la clonación del minimo entontrad, en este caso el criterio de paro para encontrar el mínimo fue el número de iteraciones o en su defecto, el fitness = 0. En la gráfica de Sistema inmune la diferencia en el número de iteraciones para encontrar el mínimo es bastante visible a comparacion del MA y GA respectivamente.
En la fig \ref{952806} d) esta diferencia en la batalla por encontrar el óptimo es significativamente visible.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/graficas3/graficas3}
\caption{\selectlanguage{ngerman}{Solución al problema TT, a)MA, b)GA,c)ISA, d) Tendencias.
{\label{952806}}%
}}
\end{center}
\end{figure}\selectlanguage{ngerman}

En la fig \ref{479593} se observa el comportamiento de los algoritmos trayectoriales y sus respectivas configuraciones a) ILS1, b) ILS2, c)SA1, d) SA2, de manera visual el algoritmo Recodido Simulado tiene un factor de convergencia al mínimo más pronunciado que el algoritmo ILS en ambas configuraciones.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/graficas4/graficas4}
\caption{{Algoritmos trayectoriales y sus respectivas configuraciones a) ILS1, b)
ILS2, c) SA1, d) SA2.
{\label{479593}}%
}}
\end{center}
\end{figure}

Las tendencias de estos algorimos puede verse en la fig \ref{424819}. En la cual se observa que el algoritmo SA en ambas configuraciones es mejor que la b\selectlanguage{ngerman}úsqueda local iterada.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.42\columnwidth]{figures/tendencias/tendencias}
\caption{{This is a caption
{\label{424819}}%
}}
\end{center}
\end{figure}



\selectlanguage{ngerman}\subsection{Pruebas no paramétricas}

Los algoritmos fueron sometidos a pruebas no paramétricas para determinar la existencia de diferencia estadísticamente significativa en el comportamiento entre cada uno. Las pruebas fueron realizadas mediante el software KEEL \cite{Alcala-Fdez2008}. El nivel de significancia establecido fue del 0.05.Donde, el resultado obtenido fue la existencia de diferencia en el comportamiento de los algoritmos propuestos, con p-valores de 0.00335, 0.067, 0.000034731 para Friedman, Friedman Alineado y Quadetest respectivamente en el problema TSP, en el cual la conslusión es que existe diferencia significativa entre el comportamiento de los algoritmos.\selectlanguage{english}
\begin{table}
\begin{center}
    \caption{\selectlanguage{ngerman}{Rankeo Obtenido a partir de la aplicación de las pruebas No Paramétricas para los Algoritmos Poblacionales.}}
    \begin{tabular}{c c c c c}
    \hline
         \multicolumn{1}{p{1.5cm}}{\textbf{Algoritmo}} & \multicolumn{1}{p{1.5cm}}{\textbf{ Friedman TSP}} & \multicolumn{1}{p{1.5cm}}{\textbf{QuadeTest TSP}} & \multicolumn{1}{p{1.5cm}}{\textbf{ Friedman TT}} & \multicolumn{1}{p{1.5cm}}{\textbf{QuadeTest TT}}\\ 
    \hline
        GA1&2&2 &2&9.5\\ 
    MA1&3&3&7.5&7.5\\ 
    ISA1&1&1&1&20.5\\ 
     
    
\hline
    \end{tabular} 
    \label{rankingP}
\end{center}
\end{table}

En el caso de la prueba para los algoritmos poblacionales y el problema timetabling los p valores obtenidos fueron 0.000335, 0.06937, 0.00001567 respectivamente, obteniendo diferencia estad\selectlanguage{ngerman}ísticamente significativa de nuevo.

En la tabla \ref{rankingP} se pueden observar los lugares que ocupa cada algoritmo en el desempeño general. Siendo que, no se muestra el ranking obtenido por Friedman Alineado ya que la prueba no pudo determinar diferencia significativa al obtener un p-valor mayor al nivel de significancia. Se muestra que el Algoritmo Sistema Inmune obtuvó mejores resultados que el Algoritmo Memético y el Algoritmo Genético respectivamente.\selectlanguage{english}
\begin{table}
\begin{center}
    \caption{\selectlanguage{ngerman}{Rankeo Obtenido a partir de la aplicación de las pruebas No Paramétricas para los algoritmos trayectoriales.}}
    \begin{tabular}{c c c c c}
    \hline
         \multicolumn{1}{p{1.5cm}}{\textbf{Algoritmo}} & \multicolumn{1}{p{1.5cm}}{\textbf{ Friedman TSP}} & \multicolumn{1}{p{1.5cm}}{\textbf{QuadeTest TSP}} & \multicolumn{1}{p{1.5cm}}{\textbf{ Friedman TT}} & \multicolumn{1}{p{1.5cm}}{\textbf{QuadeTest TT}}\\ 
    \hline
        ILS1&1.9375&1.9861&1&1\\ 
        ILS2&1.0625&1.0139&2&2\\ 
    SA1&4&4&4&4\\ 
    SA2&3&3&3&3\\  
    
\hline
    \end{tabular} 
    \label{rankingT}
\end{center}
\end{table}

En la tabla \ref{rankingT} se pueden observar los lugares que ocupa cada algoritmo en el desempe\selectlanguage{ngerman}ño general. Siendo que, no se muestra el ranking obtenido por Friedman Alineado ya que la prueba no pudo determinar diferencia significativa al obtener un p-valor mayor al nivel de significancia. Se muestra que el Algoritmo Recocido Simulado obtuvo mejores resultados que el algoritmo de búsqueda local iterada.\selectlanguage{english}
\begin{table}
\begin{center}
    \caption{\selectlanguage{ngerman}{Rankeo Obtenido a partir de la aplicación de las pruebas No Paramétricas (Algoritmos Poblacionales vs Algoritmos Trayectoriales).}}
    \begin{tabular}{c c c c c}
    \hline
         \multicolumn{1}{p{1.5cm}}{\textbf{Algoritmo}} & \multicolumn{1}{p{1.5cm}}{\textbf{ Friedman TSP}} & \multicolumn{1}{p{1.5cm}}{\textbf{QuadeTest TSP}} & \multicolumn{1}{p{1.5cm}}{\textbf{ Friedman TT}} & \multicolumn{1}{p{1.5cm}}{\textbf{QuadeTest TT}}\\ 
    \hline
        GA&3.5&3.3889&20.125&4\\ 
    ISA&5&5&46.5&7\\
    MA&1.625&1.6667&15.5&2\\
    ILS1&3.1875&3.2917&12.875&1\\ 
        ILS2&1.6875&1.6528&17.5&3\\ 
    SA1&7&7&44.25&6\\ 
    SA2&6&6&42.75&5\\ 
    
\hline
    \end{tabular} 
    \label{rankingPvsT}
\end{center}
\end{table}


Finalmete las pruebas no param\selectlanguage{ngerman}étricas realizadas para ambas familias de algoritmos, bajo un nivel de significancia del 0.05, los p valores fueron 0.00025, 0.103826, 0. 
Siendo dos de tres pruebas de nuevo las que aceptaron la diferencia en el comportamiento de los algoritmos.

\section{Conclusiones}

El algoritmo ``Sistema Inmune'' (ISA) tiene un mejor resultado que el algoritmo ``Memético''(MA) y `Con el desarrollo de pruebas estadísticas con un nivel de significancia del 0.05, el Algoritmo Recocido Simulado SA1 y SA2 (con las configuraciones establecidas) obtuvo un mejor rendimiento que el algoritmo Búsqueda Local Iterativa ILS1 e ISL2 para los problemas TSP y TT, respectivamente. Los algortimos trayectoriales son más veloces en tiempo de ejecución no obstante el algoritmo ISA demostró ser mas robusto aunque la eficiencia del mismo afecta directamente los recursos de la computadora.



Como trabajo futuro queda pendiente la realización de las pruebas estadísticas pos'hoc para determinar el mejor algoritmo mediante pruebas estadísticas especializadas y no solo al rankeo de las pruebas ya realizadas.

\selectlanguage{english}
\FloatBarrier
\bibliographystyle{unsrt}
\bibliography{bibliography/converted_to_latex.bib%
}

\end{document}

