Tema 6

Optimización II

Algoritmos genéticos
 Índice
Esquema 3

Ideas clave 4
6.1. Introducción y objetivos 4
6.2. Estructura de un algoritmo genético 5
6.3. Modelos de algoritmos genéticos 8
6.4. Representación de la información 10
© Universidad Internacional de La Rioja (UNIR)

6.5. Operadores de selección 11

6.6. Operadores de cruce 16
6.7. Operadores de mutación 23
6.8. Estrategias de reemplazamiento 26
6.9. Cuaderno de ejercicios 27
6.10. Referencias bibliográficas 38
 © Universidad Internacional de La Rioja (UNIR)

Tema 6. Esquema
Optimización II
Esquema

3
 Ideas clave

6.1. Introducción y objetivos

Los algoritmos genéticos fueron desarrollados en EE. UU. en los años 70 por Holland,
DeJong y Goldberg. Originalmente, fueron aplicados a la optimización discreta o
combinatoria (binaria). Son algoritmos de optimización que pueden ser pensados
como métodos de búsqueda global. La idea del algoritmo es replicar el proceso de
selección natural para encontrar las soluciones más aptas. Esto es, el algoritmo
consiste en, dada una población de individuos, hacerla evolucionar mediante
cambios aleatorios en sus genes y luego seleccionar a los mejores individuos de la
población para que puedan perpetuarse. En el marco de un problema de
optimización, las posibles soluciones conforman la población y la función de costo
sirve para seleccionar a los individuos más aptos.

Hemos dicho que los cambios en los genes son aleatorios. Sin embargo, el grado de
aleatoriedad está controlado (interviene en una pequeña parte del algoritmo). Así,
los algoritmos genéticos son mucho más eficientes que las búsquedas locales
específicas, generando soluciones completamente aleatorias, y también que las
búsquedas exhaustivas. Por otra parte, estos algoritmos no necesitan prácticamente
ninguna hipótesis adicional del problema. Por ejemplo, no se ven afectados por la
falta de derivabilidad (o continuidad) del problema.

Comenzaremos dando una breve noción recordatoria acerca de la estructura general

de un algoritmo genético y terminaremos proporcionando a los estudiantes el
conocimiento necesario para que ellos mismos sean capaces de llevar a cabo sus
propias implementaciones y puedan resolver problemas reales. Con este objetivo,
estudiaremos implementaciones de algoritmos genéticos que nos permitan trabajar
con tres tipos de representación de información: información binaria, real y

Optimización II
4
Tema 6. Ideas clave
secuencial. Además, para cada tipo de representación, estudiaremos cómo
implementar los operadores asociados.

Algunos de los objetivos que podemos plantear inicialmente en este tema son:

 Comprender la base de un algoritmo genético. Esto lo haremos en términos de

establecer la combinación que nos permita obtener la mejor elección de la
población disponible y bajo los requerimientos dados.

 Determinar cada una de las etapas de un algoritmo genético y discriminar su uso

de forma adecuada.

 Implementar los algoritmos genéticos en distintas situaciones.

6.2. Estructura de un algoritmo genético

Los algoritmos genéticos están inspirados en los procesos biológicos, razón por la cual
se suele utilizar una terminología propia de la biología para designar los elementos
que componen estos métodos. Podemos, pues, establecer una equivalencia entre la
terminología que hemos venido utilizando hasta ahora y la nueva, la que hace
referencia a los conceptos propios de la biología. Así, las funciones objetivo (o de
costo) se llaman, en el contexto de los algoritmos genéticos, funciones de aptitud (o
simplemente aptitud o idoneidad). Comúnmente, la función de aptitud no coincide
con la función objetivo, es decir, es una modificación de la función objetivo adaptada
para que verifique ciertas hipótesis.

Las soluciones candidatas para resolver el problema se llaman fenotipos y están

codificadas a través de cromosomas. Un conjunto de cromosomas determina un
fenotipo, de la misma manera que un conjunto de dígitos determina un número.
Evaluando los fenotipos en la función de aptitud, uno puede seleccionar qué

Optimización II
5
Tema 6. Ideas clave
candidatos son los que se adaptan mejor a su entorno. Por ejemplo, en un problema
de minimización, aquellos fenotipos cuya imagen sea menor por la función de
aptitud. Cada iterado del algoritmo produce una nueva generación. Esto es, los
fenotipos tienen descendencia. En la nueva generación, se introducen cambios
aleatorios en sus cromosomas, esto es, se producen mutaciones.

En este tema, iniciamos el estudio de los algoritmos evolutivos, a saber, aquellos

algoritmos pertenecientes al marco de la computación bioinspirada y cuya finalidad
es la de imitar la teoría de la evolución. Nos centraremos, entonces, en estudiar en
profundidad los algoritmos evolutivos más simples: los algoritmos genéticos. En este
apartado, primero veremos su estructura general y, en los siguientes, cómo podemos
implementar y construir nuestro propio algoritmo genético.

Los algoritmos genéticos necesitan de la especificación de los siguientes métodos y

características (Duarte, Pantrigo, Gallego, 2007):

 Población inicial: suele estar formada por una generación aleatoria de soluciones
al problema dado.

 Representación: constituye una correspondencia entre las soluciones factibles

(fenotipo) y la codificación de las variables (genotipo). Originalmente, se usaban
cadenas binarias. Siendo más específicos, cada fenotipo se codifica en un vector
de parámetros numéricos (los cromosomas). La dimensión de este vector,
supongamos que es 𝑁, es la que determina la dimensionalidad del problema. Esto
es, un fenotipo que vendrá codificado como 𝑔 = [𝑓 , 𝑓 , . . . , 𝑓 ]. Aquí, 𝑓 es el valor
numérico del cromosoma 𝑖. Es decisión del programador elegir cómo se codifican
las posibles soluciones de un problema en cromosomas. Por ejemplo, si uno quiere
codificar un número real, es típico expresarlo mediante su base binaria. Así, cada
solución se codifica como un vector de 1 y 0. Evidentemente, hay total libertad a
la hora de elegir de qué manera se codifican los fenotipos. Dicho esto, una mala
codificación, puede dar lugar a soluciones que no sean óptimas y un mal
comportamiento del algoritmo.

Optimización II
6
Tema 6. Ideas clave
 Función de evaluación: nos permite saber la calidad de los individuos de una
población. Habitualmente, es una función monótona creciente que asigna un
valor mayor cuanto mejor es el individuo.

 Selección: es el mecanismo que nos permite elegir, de entre la población, aquellos

individuos a los que se les aplicará el operador de cruce para crear nuevas
soluciones.

 Operadores genéticos: son métodos probabilísticos que obtienen nuevos

individuos. Suelen depender de la representación. Por lo general, se utilizan los
siguientes operadores:

• Operador de cruce: consiste en la sustitución de un conjunto de genes de un

padre por los genes correspondientes del otro padre para generar un nuevo
individuo hijo.

• Operador de mutación: consiste en el cambio aleatorio de parte de un

individuo. La mutación se usa como mecanismo para preservar la diversidad de
las soluciones y explorar nuevas zonas del espacio de soluciones.

 Reemplazamiento: los individuos elegidos pasan a formar parte de la nueva

población, reemplazando a individuos ya existentes.

Podemos ver un esquema de cómo funcionan este tipo de algoritmos en el siguiente

gráfico:

Optimización II
7
Tema 6. Ideas clave
 Figura 1. Esquema de un algoritmo genético. Fuente: elaboración propia.

6.3. Modelos de algoritmos genéticos

Distinguimos modelos diferentes de algoritmos genéticos:

 Modelo estacionario: en cada iteración, se escogen dos padres que generan un

hijo. Este hijo sustituye a uno de los individuos de la población actual.

Figura 2. Modelo estacionario. Fuente: elaboración propia.

 Modelo generacional: mediante el cruce de individuos, en cada iteración se crea

una población completa que sustituye a la antigua.

Optimización II
8
Tema 6. Ideas clave
 Figura 3. Problema multiobjetivo. Fuente: elaboración propia.

Es importante determinar cuándo queremos que el algoritmo termine ya que, a

priori, no hay una regla clara de cuándo debemos dejar de iterar y de crear nuevas
generaciones. Los criterios de parada más comunes son los siguientes:

 Se alcanza el valor óptimo: si el valor óptimo de la solución se conoce, es posible

indicar que el algoritmo no pare hasta que lo encuentre. Obviamente, lo normal
es que esta condición vaya acompañada de alguna de las dos siguientes ya que, en
caso de que el algoritmo no fuera capaz de encontrar el óptimo, se entraría en un
bucle infinito.

 Máximo número de iteraciones: se establece, a priori, un número máximo de

iteraciones. Este criterio nos ayuda a determinar durante cuánto tiempo, como
máximo, queremos que el algoritmo se esté ejecutando. El número de iteraciones
debe ser lo suficientemente alto para permitir que el algoritmo converja. Otra
posibilidad que suele usarse es establecer un número máximo de consultas a la
función objetivo. Normalmente, evaluar la función objetivo es el paso más
costoso.

 𝑵 iteraciones sin mejora: podemos determinar que el algoritmo ha convergido a

una determinada solución si, durante una serie de iteraciones, no se consigue
ninguna mejora. El número 𝑁 de iteraciones sin mejora debe ser alto para estar
realmente seguros de que una mejora no es posible. Aun así, siempre hay
posibilidades de que estemos deteniendo el algoritmo antes de tiempo.

Optimización II
9
Tema 6. Ideas clave
 Nota: las dos últimas opciones pueden usarse solas o combinarse entre ellas y
con la primera opción presentada.

6.4. Representación de la información

En la descripción general del algoritmo genético hemos dejado muchas cuestiones

(que tienen que ver con operaciones genéticas) en el aire, sin detallar, excusándonos
en que dependían del problema. De hecho, parte de la utilidad de los algoritmos
genéticos radica en la facilidad para adaptarse a distintas situaciones.

En esta sección abordaremos un caso concreto que es tremendamente importante:

aquellos problemas en que hay que optimizar funciones de aptitud definidas en
cadenas binarias. Esto es, los fenotipos de esta sección se codifican como un vector
de unos y ceros: 𝑔 ∈ {0, 1} . Como todo número real, puede ser aproximado
mediante una representación binaria finita. Entonces, los problemas de optimización
de funciones de variables reales (con el número de variables que sea) se pueden
reducir al tipo de problema que tratamos en esta sección.

Ahora bien, los métodos de representación de información más comunes son:

 Representación binaria: es la representación más tradicional. Cada solución está

formada por un vector de unos y ceros. Por tanto, para usarla, es necesario
transformar las soluciones del problema a este tipo de representación. Por lo
general, todas las soluciones tendrán el mismo número de bits.

Figura 4. Representación binaria. Fuente: elaboración propia.

Optimización II
10
Tema 6. Ideas clave
 Representación real: cada solución está formada por un vector de números reales.
Para poder usar esta representación es necesario que la función objetivo sea capaz
de obtener, a partir de un vector de números reales, un valor de idoneidad
asociada a dicha solución.

Figura 5. Representación real. Fuente: elaboración propia.

 Representación de orden: cada solución es un vector ordenado de valores. Esta

es la representación típica que suele usarse para resolver problemas de
secuenciación, tales como el viajante de comercio. En el caso de haber
restricciones acerca del orden de los valores, es necesario introducir mecanismos
que nos ayuden a comprobar que la solución está en el marco de soluciones
válidas del problema.

Figura 6. Representación de orden. Fuente: elaboración propia.

6.5. Operadores de selección

Nos ayudan a escoger qué individuos deben reproducirse para generar nuevas
soluciones. Por lo general, interesa que los individuos con mejor función de
evaluación se reproduzcan, ya que estos son los que tienen el código genético que
alberga las mejores soluciones.

Este operador también es elegido con libertad por el programador. Eso sí, es
imprescindible que los fenotipos más aptos, tengan una mayor probabilidad de
reproducirse, aunque la definición de más apto pueda sufrir modificaciones.

Optimización II
11
Tema 6. Ideas clave
Veamos algunos operadores de selección:

 Selección por torneo.

 Orden lineal.
 Selección aleatoria.
 Emparejamiento variado inverso.
 Selección por muestreo universal estocástico – Baker, 1987 – Ruleta.
 Selección proporcional al ranking del individuo.

Selección por torneo

Se escoge aleatoriamente un número determinado de individuos y, a continuación,

se elige nuevo padre aquel que albergue la mejor solución. Este operador guarda un
equilibrio entre la exploración del espacio y el refinamiento de buenas soluciones ya
que no asegura que la mejor solución sea escogida para el operador de cruce. Sin
embargo, siempre trata de escoger soluciones relativamente buenas ya que escoge
la mejor solución de entre un subconjunto de soluciones.

Figura 7. Selección por torneo con 𝑘 = 3. Fuente: elaboración propia.

Optimización II
12
Tema 6. Ideas clave
En este caso, se elige el tamaño 𝑘 del torneo (habitualmente 𝑘 = 2). Luego, se escoge
al azar 𝑘 individuos de la población con o sin reemplazamiento. Finalmente, la idea
consiste en seleccionar el mejor individuo de este conjunto y repetir el proceso hasta
que tengamos el número de individuos deseado para ser progenitores. Una se vez se
ha calculado la aptitud de los distintos genotipos de una población, hay que calcular
los individuos de la siguiente población.

Orden lineal

Todas las soluciones disponibles se ordenan de mayor a menor según su valor de

idoneidad y se establece una probabilidad diferente para cada una. De esta manera,
cuanto mejor sea una solución, más probable es que se escoja para la fase de cruce.
Este operador tiene una componente exploratoria del espacio menor y una
convergencia mayor que el operador de selección por torneo. Esto es debido a que
hay más probabilidad de que se escojan, para el operador de cruce, aquellas
soluciones que tengan un valor de idoneidad más alto.

Figura 8. Selección por orden lineal. Fuente: elaboración propia.

Supongamos que queremos maximizar la función 𝑓 y que esta es no negativa.

Podemos determinar la probabilidad de reproducción del fenotipo 𝑔 con la siguiente
fórmula:

𝑓(𝑔 )
𝑝 = 𝑃(𝑔 ) =
∑ 𝑓(𝑔 )

Optimización II
13
Tema 6. Ideas clave
Donde 𝑝 es la probabilidad de que el individuo 𝑘 − ésimo sea seleccionado como
padre y tomando 𝑁 para denotar el número total de fenotipos. La hipótesis que
hemos adoptado sobre la función de aptitud, que es no negativa, nos obligará a
modificar la función objetivo. En este caso:

 Se muestrea tantas veces como sea necesario.

 Se puede reconsiderar el reemplazamiento.
 En general, esta selección converge a los superindividuos.

Notemos que, después de resolver el problema de optimización para la función de

aptitud, tendremos que traducir la solución al problema de optimización original
deshaciendo el cambio.

Selección aleatoria

Los padres se seleccionan de forma aleatoria. Todas las soluciones tienen la misma
posibilidad de ser escogidas. Este operador es el que realiza una mayor exploración
del espacio y el que más evita la convergencia. Sin embargo, no proporciona ningún
mecanismo que permita a las mejores soluciones cruzarse entre sí, lo que hace que
se pierda la oportunidad de mejorar las buenas soluciones ya obtenidas.

Emparejamiento variado inverso

Este operador está orientado a generar una población diversa y, por tanto, a explorar
al máximo el espacio de soluciones. La primera solución para cruzar se escoge
aleatoriamente y, para la segunda, se escogen, de entre un determinado número de
soluciones al azar, aquella que es más diferente a la solución actual. Siguiendo este
proceso, se crean soluciones que son muy diferentes unas de otras, con lo que se
mejora la exploración del espacio de soluciones.

Optimización II
14
Tema 6. Ideas clave
 Figura 9. Selección por emparejamiento variado inverso. Fuente: elaboración propia.

Selección por muestreo universal estocástico – Baker, 1987 – Ruleta

Este operador de selección es parecido al del orden lineal. La principal diferencia es

que castiga más a las peores soluciones y proporciona un mecanismo que permite
una mayor probabilidad de cruce a las mejores soluciones. La selección por ruleta
asigna un valor de probabilidad a cada solución proporcional al valor de idoneidad
obtenido por cada solución. Se consideran sectores circulares proporcionales al valor
de función objetivo de cada individuo (inverso si estamos minimizando). En este caso,
se realiza un único giro de la ruleta.

Figura 10. Selección por Ruleta. Fuente: elaboración propia.

Los individuos son seleccionados a partir de marcadores igualmente espaciados y con

comienzo aleatorio. Esto suele resultar en convergencias más lentas, pero es más
sencilla de programar. El problema es la rápida convergencia a superindividuos.

Optimización II
15
Tema 6. Ideas clave
Selección proporcional al ranking del individuo

La idea aquí es justamente evitar problemas de convergencia a superindividuos,

basando las probabilidades de selección en fitness relativas en lugar del absoluto. Por
tanto, se asigna la probabilidad inversamente proporcional a su posición en el
ranking, que puede ser: lineal, exponencial, etc.

6.6. Operadores de cruce

Los operadores de cruce deben ser capaces de generar, a partir de dos soluciones
cualesquiera, una solución que herede características de ambos padres, asumiendo
que se necesitan dos individuos para procrear y generar un entrecruzamiento
cromosómico. Esto es, a partir de un par de fenotipos, se produce otro que comparte
muchos cromosomas de sus fenotipos paternos. La manera de aparejar los distintos
fenotipos puede variar según el problema. Por ello, es muy importante utilizar un
operador de cruce que sea adecuado al tipo de dato con el que estamos tratando.

Podría considerarse como una condición indispensable para que el algoritmo

funcione que aquellos fenotipos que tengan un mejor valor de la función de
adaptación tengan más posibilidades de aparejarse. Una cuestión importante es que,
para mantener el número de individuos constantes a lo largo de las sucesivas
generaciones, se asume que cada pareja dará lugar a dos hijos. Una vez se ha
generado la siguiente generación, el primer iterado se ha completado. Para ello, se
pueden hacer uso de distintos operadores. Las implementaciones para operadores
de cruce más comunes son los siguientes:

 Operador de cruce clásico binario (one point crossover).

 Operador de cruce clásico binario (m- point crossover).
 Operador de cruce uniforme (uniform crossover).
 Operador de cruce real.

Optimización II
16
Tema 6. Ideas clave
 Operador de cruce BLX−𝛼.
 Operador de cruce para representación de orden.

Operador de cruce clásico binario (one point crossover)

Este operador consiste en elegir una posición aleatoria común a ambos padres, para
luego dividirlos en este punto y crear dos hijos copiando la cabecera de los
cromosomas padres e intercambiando las colas. El operador de cruce clásico binario,
por tanto, sigue los siguientes pasos:

 Se divide cada individuo en dos realizando un corte aleatorio por algún punto del
vector binario de solución (posición 𝑛).

 Se unen los cuatro trozos de forma que se formen dos vectores distintos y cada
uno tiene una parte de cada padre.

 Cada uno de los vectores generados es un hijo formado a partir de los dos vectores
binarios originales.

Figura 11. One-point crossover con 𝑛 = 3. Fuente: elaboración propia.

Optimización II
17
Tema 6. Ideas clave
Operador de cruce clásico binario (𝒎 − point crossover)

Este operador consiste en elegir 𝑚 posiciones aleatorias comunes a ambos padres.

Luego, divide a los padres en estos puntos y crea dos hijos copiando alternativamente
las partes de los padres.

Figura 12. 𝑚 −point crossover con 𝑚 = 2. Fuente: elaboración propia.

 Observa que en la Figura 12 se ha realizado un cruce considerando dos cambios

aleatorios en las posiciones 2 y 5, lo que deja los dos primeros genes sin cambio.
Además, se cambia el tercer gen, los genes 4 y 5 no sufren cambios y se cambia el
sexto gen para dejar sin efecto los genes 7 y 8.

Operador de cruce uniforme (uniform crossover)

Para el primer hijo, se cambia cada gen con probabilidad 0.5. El segundo hijo será el
complementario del primero. Luego, se crean dos hijos copiando alternativamente
las partes de los padres.

Optimización II
18
Tema 6. Ideas clave
 Figura 13. Cruce uniforme con probabilidad 0.5. Fuente: elaboración propia.

Operador de cruce real

El operador de cruce real recombina aritméticamente los valores reales de cada una
de las posiciones de los dos vectores padre. El parecido de los padres a los hijos viene
dado debido a que los números generados son cercanos a los valores que manejaban
los padres. Pueden utilizarse muchas funciones para realizar este proceso de cruce.
Uno de los más comunes es el operador de media, por ejemplo, si tenemos los
individuos:

Figura 14. Operador de cruce real. Fuente: elaboración propia.

Podemos calcular un individuo hijo utilizando el operador de cruce real de media de

la siguiente forma:

𝐼 +𝐼 5.6 + 0.9 7.6 + 3.2 2.4 + 9.1 4.4 + 1.1 0.7 + 0.9
𝐻= = ⋯
2 2 2 2 2 2

Optimización II
19
Tema 6. Ideas clave
Obteniendo finalmente:

Figura 15. Solución final. Fuente: elaboración propia.

Usando este operador, todos los hijos tendrán un valor comprendido entre los
valores de cada posición de cada uno de los padres.

Operador de cruce BLX−𝜶

El operador de cruce BLX−𝛼 es otro operador para información real. Al contrario que
el anterior, que era totalmente determinístico, este operador genera valores
aleatorios dentro del rango de valores en que están localizados los padres. De esta
forma, el operador de cruce BLX−𝛼 genera dos hijos siguiendo el siguiente
procedimiento:

 Se buscan el mayor y menor valor de ambos padres 𝑆 ,𝑆 .

 Se generan dos hijos aleatoriamente dentro del intervalo:

[𝑆 − 𝐼 ∙ 𝛼, 𝑆 + 𝐼 ∙ 𝛼]

En donde 𝐼 = 𝑆 −𝑆 y 𝛼 es un valor que nos permite ajustar el intervalo.

Cuanto mayor sea 𝛼, más amplio será el intervalo. Podemos observar cómo el
intervalo generado por este operador abarca la zona intermedia entre el valor
mínimo y máximo de los padres, así como un rango de valores por debajo del mínimo
y otro por encima del máximo. El rango de valores por encima y por debajo del
mínimo de los padres es regulado por la variable 𝛼.

Optimización II
20
Tema 6. Ideas clave
Para mayor claridad, veamos cómo funciona este operador con un ejemplo.
Supongamos que tememos los dos padres reales del ejemplo anterior (véase Figura
14).

Los valores menores y mayores de estos dos valores son mente 0.9 y 9.1
respectivamente. De esta forma, los hijos generados por estos vectores deben ser
valores aleatorios localizados dentro del intervalo [0.9 − 8.2 ∙ 𝛼 , 9.1 + 8.2 ∙ 𝛼].
Ahora, es necesario determinar el valor de 𝛼. Cuanto mayor valor le demos a 𝛼,
mayor exploración del espacio, pero menor refinamiento y convergencia. No hay
una regla perfecta para fijar el valor de 𝛼.

Lo único que podemos afirmar es que, al interesarnos explorar en las primeras

iteraciones del algoritmo y refinar después, es bueno que 𝛼 tenga valores altos al
principio del algoritmo y bajos en las últimas iteraciones. En esta iteración,
imaginemos que 𝛼 = 0.5. Entonces, los valores que deben tener los vectores hijos
deben estar localizados en el rango [−3.2, 13.2].Tras generar los números aleatorios
necesarios, tenemos que los hijos son:

Figura 16. Ejemplo de Operador de cruce BLX−𝜶. Fuente: elaboración propia.

Nota: en cada ejecución de este operador, los resultados obtenidos son

distintos incluso usando los mismos padres en el proceso.

Optimización II
21
Tema 6. Ideas clave
Operador de cruce para representación de orden

En el caso de la representación de orden, es muy importante utilizar un operador de

cruce que no destruya completamente el orden entre los valores del vector. También
lo es que los hijos contengan trazas de los órdenes de valores seguidos en los padres
si queremos que nuestro algoritmo funcione de forma inteligente y no pierda buenas
soluciones. El operador de cruce para representación de orden más utilizado está
basado en el binario y lo que hace es mantener un subconjunto de elementos de un
padre y ordenar los demás valores como lo hace otro.

Veremos mucho más claro el funcionamiento de este operador con un ejemplo.

Imaginemos un problema del viajante de comercio con ocho nodos y las siguientes
dos soluciones:

Figura 17. Soluciones de un operador de cruce para representación de orden. Fuente: elaboración propia.

El operador decide mantener aleatoriamente los valores [3 2 4] y ordena el resto de

los valores, [5 6 1 7 8], tal y como lo hace 𝑰𝟐 . De esta forma, el segundo vector pasa
a ser [1 7 5 8 6]. Esto es debido a que en 𝑰𝟐 el 1 va antes que el 7, el 7 antes que el
5, el 5 antes que el 8, etc. A continuación, introducimos el segundo vector
—ordenado según el segundo padre— en el primero, sobrescribiendo todos los
valores menos los que hemos decidido mantener.

Dado que el problema del viajante de comercio es circular, es decir, el nodo donde
se empieza es en el que se acaba, se puede añadir la información tras los valores
mantenidos. De esta forma, cuando hayamos rellenado el último valor, comenzamos
desde el primero. Siguiendo este proceso, el vector hijo formado mediante este
operador es el siguiente:

Optimización II
22
Tema 6. Ideas clave
 Figura 18. Vector hijo. Fuente: elaboración propia.

Podemos ver el proceso llevado a cabo en este ejemplo gráficamente en la Figura 19:

Figura 19. Esquema de cruce en representación de orden. Fuente: elaboración propia.

6.7. Operadores de mutación

Al igual que ocurre para el operador de cruce, la implementación del operador de

mutación que se escoja debe ser acorde a la representación elegida para los
individuos de la población. A continuación, mostramos las implementaciones más
comunes según el tipo de representación escogida:

 Operador de mutación para información binaria – Bit-Flip.

 Operador de mutación para información real.
 Operador de mutación para información secuencial.

Optimización II
23
Tema 6. Ideas clave
Operador de mutación para información binaria – Bit-Flip

Es aquí donde se introduce la mutación aleatoria de algunos de los cromosomas,

alterando cada gen independientemente con probabilidad de mutación 𝑝 .
Habitualmente, 𝑝 se toma entre 1/tamaño de población y 1/longitud de
cromosoma. Conviene que 𝑝 sea baja, ya que, si es demasiado alta, se pierde la
información de los progenitores y, de usarse en exceso, se interrumpiría la
convergencia normal del algoritmo.

Para cada una de las posiciones de todas las soluciones disponibles, con una cierta
probabilidad muy baja, cambiamos un 1 por un 0 o un 0 por un 1. La idea de este
operador de mutación consiste en realizar pequeños cambios aleatorios sobre las
soluciones con el objetivo de comprobar si la idoneidad asociada mejora. Es
importante aplicar el operador de mutación con una probabilidad baja debido a que,
por ejemplo, si tenemos el vector solución [1 0 0 1 1 1 0], una mutación con
probabilidad menor o igual al 5 % en base a la tabla adjunta en la Figura 20 produce
la mutación [1 0 0 1 1 𝟎 1 0].

Figura 20. Mutación con probabilidad menor o igual al 5 %. Fuente: elaboración propia.

Optimización II
24
Tema 6. Ideas clave
Operador de mutación para información real

El operador de mutación para información real aplica, con una baja probabilidad, una
pequeña modificación sobre los valores reales del vector de soluciones de cada
individuo. Normalmente, se usa una distribución gaussiana o normal de media 0. De
esta forma:

𝒙 = 𝒙 + 𝑁(0, 𝜎)

Aquí, la desviación típica nos ayuda a regular la fuerza del cambio aplicado sobre cada
elemento del vector de soluciones. Podemos ver un ejemplo aplicado en la Figura 21.

Figura 21. Mutación con probabilidad menor o igual al 1 %. Fuente: elaboración propia.

Optimización II
25
Tema 6. Ideas clave
Operador de mutación para información secuencial

Cuando tratamos con información secuencial, el operador de mutación más típico

consiste en intercambiar dos posiciones del vector de soluciones al azar. Esta
operación se lleva a cabo con una probabilidad baja en cada una de las soluciones
disponibles. Podemos ver un ejemplo en la siguiente Figura 22:

Figura 22. Mutación por información secuencial. Fuente: elaboración propia.

6.8. Estrategias de reemplazamiento

El reemplazamiento de las antiguas soluciones por las nuevas puede implementarse

de diversas formas. En esta sección pasaremos a describir algunos de los métodos
más conocidos:

 Reemplazar al peor elemento de la población: se reemplazan a las peores

soluciones de la población. Esta estrategia genera una alta convergencia y elimina
la posibilidad de explorar en amplitud el espacio de soluciones. Es fácil que se
eliminen soluciones prometedoras a cambio de dejar soluciones que son muy
parecidas a la mejor solución encontrada hasta ese momento.

 Torneo restringido: se escoge aleatoriamente un subconjunto de soluciones y, de

entre ellas, se reemplaza la que se parece más a la solución obtenida. De esta
manera, mantenemos durante más tiempo una población diversa que nos permite
realizar una mejor exploración del espacio de soluciones.

Optimización II
26
Tema 6. Ideas clave
 Peor entre semejantes: se escogen, de entre la población, las 𝑥 soluciones más
parecidas a la generada y, de entre ellas, se elimina a la que tenga peor valor de
idoneidad. Este esquema busca mantener un equilibrio diversidad-convergencia,
ya que mantiene soluciones diferentes dentro de la población. A su vez, trata de
deshacerse de aquellas soluciones que aportan poca diversidad y tienen un valor
bajo de idoneidad.

 Algoritmo de crowding determinístico: el nuevo individuo reemplaza al individuo

de la población que más se le parezca. Este método es el que más promueve la
exploración del espacio ya que trata de mantener la población diversa evitando, a
toda costa, la convergencia a soluciones similares.

 Elitismo: se puede aplicar opcionalmente con las opciones anteriores. Consiste en

asegurarse de que la mejor solución o las 𝑥 mejores soluciones siempre
permanecen en la población. De esta manera, evitamos que se sustituyan y se
pierdan.

En el siguiente enlace podrás encontrar un problema relativo al problema de la

mochila, donde se especifican cada uno de los pasos del algoritmo genético.

6.9. Cuaderno de ejercicios

En este caso, procederemos a dar una explicación exhaustiva del problema de la

mochila con un desarrollo completo de cada etapa del algoritmo genético. En este
sentido, y dada la longitud de este, solo presentaremos un problema completo, pero
con la plena convicción de que, siguiendo los lineamientos descritos anteriormente,
se puedan construir problemas diversos.

Optimización II
27
Tema 6. Ideas clave
El problema de la mochila

Se desea colocar objetos en una mochila de forma tal que se maximice el valor de los
objetos sin exceder su capacidad máxima.

 Parámetros por definir: en principio, se debe definir lo que es una solución y la

función objetivo. De este modo:

• Una solución es un vector 𝒙 = [𝑥 , 𝑥 , . . . , 𝑥 ], donde 𝒙 = {0, 1} . En

consecuencia,
1 , si el objeto está en la mochila
𝑥 =
0 , si el objeto no está en la mochila
• Restricción: sea 𝐶max la capacidad máxima de la mochila.
• Conjunto de factibilidad: definimos el espacio de solución como:

Ω = [𝑥 , 𝑥 , ⋯ , 𝑥 ] ∶ 𝑥 ∈ {0,1} y 𝑝 ∙ 𝑥 ≤ 𝐶max

Donde 𝑝 es el peso del 𝑖 −ésimo objeto.

• La función objetivo a maximizar está definida por:

𝑓(𝑥 , 𝑥 , ⋯ , 𝑥 ) = 𝑣 ∙ 𝑥 = 𝑣 𝑥 + ⋯+ 𝑣 𝑥

Donde 𝑣 es el valor del 𝑖 −ésimo objeto.

Optimización II
28
Tema 6. Ideas clave
Ejercicio 1

Tenemos una mochila que tiene una capacidad de carga de 7 kg. y un conjunto de
paquetes que queremos llevar en ella. Cada paquete tiene un valor en euros y un
peso determinado por la Tabla 1:

Tabla 1. Problema de la mochila. Fuente: elaboración propia.

Se pide determinar la combinación de paquetes de forma que quepan en la mochila

y tengan el máximo valor posible.

Solución

 Paso 1. Parámetros del problema:

• Tamaño de la población: 𝑁 = 4. 𝒑𝒋 = 𝑝 , , 𝑝 , ,𝑝 , ,𝑝 , ,𝑝 , ↪ 𝑛 =5.

Generamos entonces, cuatro vectores binarios de forma aleatoria.
• Población inicial ↪ Aleatoria.

• Operador de selección de padres ↪ Torneo con 𝑘 = 2 .

• Operador de cruce ↪ One-point crossover.
• Mutación ↪ Bit-split con una probabilidad de 50 %.
• Operador de selección de la nueva generación ↪ Elitista, se eligen los cuatro
mejores.
• Criterio de parada ↪ Dos generaciones.

Optimización II
29
Tema 6. Ideas clave
 Paso 2. Población inicial:

Buscamos cuatro padres de partida de forma aleatoria. Por ejemplo, para seleccionar
a los cuatro padres, consideramos cuatro muestras aleatorias de cinco números cada
una en el intervalo (0, 1), lo cual nos genera una probabilidad en cada artículo. La
decisión de si consideramos el artículo o no estará sujeta a si esa probabilidad iguala
o supera el 40 %.

Tabla 2. Población inicial 𝑁 = 4. Fuente: elaboración propia.

Luego, la población inicial queda de la forma:

Figura 23. Población inicial. Fuente: elaboración propia.

Sabiendo que nuestra función de aptitud (fitness) está dada por:

𝑓 𝒑 = 𝑝 , ∙ 𝑣 =𝑝 , ∙7+𝑝 , ∙9+𝑝 , ∙ 10 + 𝑝 , ∙ 10 + 𝑝 , ∙8

Optimización II
30
Tema 6. Ideas clave
La población obtenida es justamente:

Figura 24. Población obtenida. Fuente: elaboración propia.

 Paso 3. Cruce:

De forma aleatoria, se eligen parejas dos a dos, para luego realizar el one-point
crossover con 𝑛 = 3 . Toda esta información aleatoria puede ser generada en:
AugeWeb, en Excel, en Matlab, en Python, etc.

Figura 25. One-point crossover. Fuente: elaboración propia.

Optimización II
31
Tema 6. Ideas clave
 Paso 4. Mutación:

Se generan en forma aleatoria números en (0, 1) y podríamos establecer que, si sale

menor a 0.5, entonces no muta y, si sale mayor, entonces cambia su valor. Por tanto,
por cada hijo 𝒉 , hay que generar cinco números aleatorios y ver si mutan entrada
por entrada.

Tabla 3. Mutación. Fuente: elaboración propia.

En base a la Tabla 3, nos queda:

Figura 26. Resultados: hijos mutados. Fuente: elaboración propia.

Optimización II
32
Tema 6. Ideas clave
Ahora evaluamos a los hijos mutados en el fitness:

Figura 27. Hijos mutados en el fitness. Fuente: elaboración propia.

 Paso 5. Selección de nueva generación:

Ahora se seleccionan los cuatro mejores individuos de todos los obtenidos y medidos:

Figura 28. Mejores individuos. Fuente: elaboración propia.

Nota: cuando existen empates estos se resuelven viendo cuál de ellos pesa
menos, situación que justamente pasa con 𝑝 , ℎ′ , ℎ′ cuyos pesos
respectivos son: 6,5 kg, 8,5 kg y 10 kg.

Optimización II
33
Tema 6. Ideas clave
 Paso 6. Cruce:

Haremos one-point crossover con 𝑛 = 1 para el primer cruce y 𝑛 = 3 para el

segundo cruce.

Figura 29. One-point crossover 𝑛 = 1 y 𝑛 = 3. Fuente: elaboración propia.

 Paso 7. Mutación:

Para cada hijo 𝒉 , se generan cinco números aleatorios nuevos y vemos si mutan
entrada por entrada.

Tabla 4. Mutación para hijos ℎ . Fuente: elaboración propia.

Nota: podría darse el caso de usar la misma tabla de probabilidades de

mutación de la generación anterior, lo que, en este caso, hemos renovado.

Optimización II
34
Tema 6. Ideas clave
Luego, los hijos mutados en la primera generación están dados por:

Figura 30. Hijos mutados en la primera generación. Fuente: elaboración propia.

Ahora evaluamos a los hijos mutados en el fitness:

Figura 31. Valoración de hijos mutados en el fitness. Fuente: elaboración propia.

Optimización II
35
Tema 6. Ideas clave
 Paso 8. Selección:

Ahora se seleccionan los cuatro mejores individuos de ambas generaciones:

Tabla 32. Selección de los mejores individuos de ambas generaciones. Fuente: elaboración propia.

 Paso 9. Factibilidad:

Veamos si satisfacen las restricciones de peso de la mochila. Recordemos nuestra

función de peso:

𝑃 𝒑 = 𝑝 , ∙𝑝

= 𝑝 , ∙𝑝 +𝑝 , ∙𝑝 +𝑝 , ∙𝑝 +𝑝 , ∙𝑝 +𝑝 , ∙𝑝

Entonces:

Figura 33. Valoración y solución de hijos mutados. Fuente: elaboración propia.

Optimización II
36
Tema 6. Ideas clave
En consecuencia, la solución a nuestro problema es la generada por el primer padre
tomado que, para tener un valor total de 27 €, pone en la mochila los artículos 1, 3 y
4 con un peso total de 5,5 kg.

Notas importantes

 Si hubiese dos o más soluciones menores que siete, se escoge la de menor peso.

 Si todas fallan, no tiene sentido trabajar con un algoritmo donde las soluciones
son no factibles y cada vez que esto ocurra se sale del algoritmo.

 Se puede construir un algoritmo que, en cada generación, se evalúe el fitness y la

restricción y, por tanto, puede ir descartando y, si no sirve, entonces se reemplaza.

 Esto puede resultar muy costoso, pero permite diseñar algoritmos para solo
factibles.

Ejercicio 2

Código en Matlab para dar una solución simple al problema de la mochila.

Solución

function [maxValue, selectedItems] = problemaMochila(valores, pesos,

capacidadMochila)
n = length(valores) % Número de elementos

%% Inicializar matriz de memorización para almacenar los resultados

intermedios
memorizacion = zeros(n+1, capacidadMochila+1);

%% Calcular los valores óptimos utilizando programación dinámica

for i = 1:n
for j = 1:capacidadMochila

Optimización II
37
Tema 6. Ideas clave
 if pesos(i) > j
memorizacion(i+1, j+1) = memorizacion(i, j+1);
else
memorizacion(i+1, j+1) = max(memorizacion(i, j+1),
valores(i) + memorizacion(i, j-pesos(i)+1));
end
end
end
selectedItems = false(1, n); %% Recuperar los elementos seleccionados
j = capacidadMochila;
for i = n:-1:1
if memorizacion(i+1, j+1) ~= memorizacion(i, j+1)
selectedItems(i) = true;
j = j - pesos(i);
end
end
%% Calcular el valor total máximo
maxValue = memorizacion(n+1, capacidadMochila+1);
end

En el siguiente enlace podrás encontrar una implementación en Matlab del problema

de la mochila donde se especifican cada uno de los pasos del algoritmo genético
dentro de la implementación. En base a esta información, podrías generar una
implementación similar al problema planteado en el Ejercicio 1.

Optimización II
38
Tema 6. Ideas clave
6.10. Referencias bibliográficas

Duarte, A., Pantrigo, J. J. y Gallego, M. (2007). Metaheurísticas. Editorial Dykinson.

Optimización II
39
Tema 6. Ideas clave