Tema 7

Optimización II

Estrategias de
exploración-explotación
del espacio para
algoritmos genéticos
 Índice
Esquema 3

Ideas clave 4
© Universidad Internacional de La Rioja (UNIR)

7.1. Introducción y objetivos 4

7.2. Exploración vs. explotación 5
7.3. Algoritmo CHC 12
7.4. Problemas multimodales 18
7.5. Cuaderno de ejercicios 22
7.6. Referencias bibliográficas 39
 © Universidad Internacional de La Rioja (UNIR)

Tema 7. Esquema
Optimización II
Esquema

3
 Ideas clave

7.1. Introducción y objetivos

Los algoritmos genéticos son un tipo de algoritmo de búsqueda de propósito general,

es decir, de búsqueda global, cuyas componentes pueden establecer un equilibrio
entre exploración y explotación. Teniendo en cuenta que todo algoritmo de
búsqueda necesita establecer un equilibrio entre estos dos factores aparentemente
contrapuestos:

 La exploración del espacio de soluciones realiza una búsqueda en amplitud,

localizando así zonas prometedoras o de aparente abundancia.

 La explotación del espacio de búsqueda hace una búsqueda en profundidad en

dichas zonas, obteniendo así las mejores soluciones.

Durante este tema, nuestro objetivo principal es la comprensión de los principales

retos a los que los algoritmos genéticos se enfrentan y qué técnicas pueden aplicarse
para su correcta superación. En consecuencia, nos centraremos, sobre todo, en
estudiar los siguientes puntos:

 Comprensión de la diferencia entre los conceptos de óptimo local y óptimo global.

 Cómo podemos evitar caer en óptimos locales que proporcionen malas soluciones
haciendo una correcta exploración-explotación del espacio.

 Algoritmo CHC: una implementación de algoritmos genéticos que lleva a cabo una
exploración-explotación del espacio compensada.

Optimización II
4
Tema 7. Ideas clave
 Aplicación de métodos que permitan a los algoritmos genéticos converger en
varios óptimos locales al mismo tiempo.

7.2. Exploración vs. explotación

Es muy importante que los algoritmos bioinspirados guarden una buena relación
exploración-explotación del espacio, pero ¿qué significa esto exactamente? ¿Qué
pasa si esa buena relación no se da? A lo largo de este tema veremos a qué retos se
enfrentan los algoritmos genéticos durante su proceso de exploración y explotación
del espacio de soluciones y qué metodologías pueden utilizarse para salir airosos de
ellos.

Antes de nada, pasemos a ver con más detalle en qué consiste exactamente la
exploración y explotación del espacio.

Exploración

Los espacios de soluciones sobre los que trabajan los algoritmos genéticos pueden
ser muy amplios y la mejor solución puede estar localizada en cualquier parte. Por
tanto, es muy importante que los algoritmos genéticos sean capaces de estudiar y
comprobar soluciones pertenecientes a zonas del espacio que se encuentren muy
distantes entre sí. Gracias a la exploración, podemos ser capaces de encontrar zonas
del espacio prometedoras que nos den resultados de gran calidad.

Optimización II
5
Tema 7. Ideas clave
 Figura 1. Espacio de soluciones. Fuente: elaboración propia.

Explotación

La explotación consiste en estudiar concienzudamente una zona prometedora del

espacio de soluciones con el objetivo de encontrar la mejor solución perteneciente a
esa zona. La explotación es muy importante, ya que nos permite obtener el óptimo
local de una determinada zona prometedora. En la mayoría de los casos, la solución
óptima de una zona determinada dentro del espacio de búsqueda está rodeada por
soluciones muy similares a ella que van decreciendo en idoneidad conforme nos
alejamos del punto óptimo. Un ejemplo de esto lo podemos ver en la función 𝑥 .

Figura 2. Gráfica de 𝑓(𝑥) = 𝑥 en [−5,5]. Fuente: elaboración propia.

Optimización II
6
Tema 7. Ideas clave
En esta función, el mínimo local se localiza en 𝑥 = 0 y, conforme nos alejamos de ese
valor, las soluciones obtenidas son cada vez de mayor magnitud. Por tanto, es muy
importante obtener el óptimo local de una zona determinada ya que, al hacerlo,
podemos mejorar sustancialmente la mejor solución obtenida hasta el momento con
un esfuerzo de búsqueda relativamente bajo.

Figura 3. Escogencia de la mejor solución. Fuente: elaboración propia.

Definición de óptimo local: el óptimo local es el mejor valor de una zona concreta
del espacio. Puede ser una solución mala si otras zonas del espacio agrupan
soluciones mucho mejores.

Definición de óptimo global: el óptimo global es la mejor solución de todo el espacio

de soluciones y encontrarlo implica encontrar la mejor solución posible al problema.

Figura 4. Representación de óptimos locales y globales. Fuente: elaboración propia.

Optimización II
7
Tema 7. Ideas clave
Como ya comentamos, encontrar el óptimo global en problemas de gran envergadura
puede llegar a convertirse en una tarea casi imposible. Los algoritmos genéticos y,
globalmente, los algoritmos bioinspirados fueron desarrollados para ser capaces de
encontrar buenas soluciones, aunque estas no fueran el óptimo global del problema.
Sin embargo, para obtener buenas soluciones es necesario configurar los algoritmos
y aplicar técnicas que nos permitan encontrar buenos óptimos locales.

Imaginemos que tenemos el siguiente espacio de búsqueda en donde queremos

encontrar la 𝑥 que nos proporciona el valor más bajo de 𝑦:

Figura 5. Gráfica de una función objetivo con espacio de búsqueda. Fuente: elaboración propia.

Como podemos ver, la mejor solución o el óptimo global se encuentra en 𝑥 = 7. En

la gráfica, podemos ver que hay otros óptimos locales situados en los valores 𝑥 = 3
y 𝑥 = 9, por ejemplo.

El óptimo local situado cerca de 𝑥 = 5 es el que más se asemeja al óptimo global,

pero el óptimo local situado en 𝑥 = 3 es una mala solución, ya que proporciona una
solución de baja calidad al problema planteado. Es fácil ver que, si nuestro algoritmo
genético se centra en explorar soluciones únicamente dentro del intervalo [0,4],
entonces convergería a 𝑥 = 3, dando una mala solución.

Optimización II
8
Tema 7. Ideas clave
Sin embargo, si se exploran diferentes zonas del espacio, podría fácilmente converger
a cualquiera de los otros óptimos, encontrando el óptimo global o una buena
solución. Este es el motivo por el que una buena exploración del espacio en busca de
zonas prometedoras es crítica para poder obtener buenos resultados.

Imaginemos ahora, usando la misma gráfica de la Figura 5, que nuestro algoritmo va

escogiendo valores de 𝑥 lejanos entre sí dentro del rango total del espacio de
búsqueda [0, 16] con el objetivo de realizar una buena exploración del espacio.
Durante el tiempo en que iteramos, el algoritmo prueba los valores siguientes:
[3, 5, 9, 11] y determina que la mejor solución es 𝑥 = 9. En este caso, la solución
encontrada tampoco es óptima. Esto se debe a que no se ha estudiado la zona
prometedora en donde se encuentra el valor 𝑥 = 9 y no se ha podido encontrar el
valor óptimo del área que está localizado en 𝑥 = 7.

Advertencia: el algoritmo se ha conformado con una solución relativamente

mala cuando, mediante un proceso de explotación que no habría llevado
muchas iteraciones, podría haberse encontrado el óptimo global.

Si analizamos un poco esta situación, puede verse que la mejor metodología que
puede seguir un algoritmo de optimización para encontrar los mejores resultados en
el menor tiempo posible dentro del espacio de soluciones es el siguiente:

 Fase 1 - Exploración del espacio: exploramos el espacio en profundidad con la

finalidad de identificar aquellas zonas susceptibles de contener buenas soluciones.
Interesa cubrir el espacio lo mejor posible para no dejar zonas sin comprobar. Si el
tiempo establecido o los recursos no lo permiten, trataremos de movernos por
zonas que se encuentren alejadas entre sí.

Optimización II
9
Tema 7. Ideas clave
 Fase 2 - Explotación del área o mejores áreas encontradas: una vez explorado el
espacio, explotamos las mejores soluciones encontradas con el objetivo de
encontrar el óptimo local de cada una de esas zonas prometedoras. Conforme
vaya avanzando el proceso de explotación, las zonas que demuestren ser las
menos prometedoras se irán descartando y, finalmente, se convergerá al óptimo
local encontrado que proporcione la mejor solución.

Figura 6. Explotación del espacio de búsqueda. Fuente: elaboración propia.

Es importante tener en cuenta que el óptimo local final en donde se converge puede
no ser el óptimo global. De hecho, es posible que el óptimo global diste mucho de la
solución encontrada. Sin embargo, el procedimiento descrito permite encontrar
varios de estos óptimos locales y quedarnos con el mejor, con lo que las posibilidades
de encontrar el óptimo global o una buena solución aumentan.

Tal y como hemos podido observar, los algoritmos genéticos convergen a una única
solución, pero ¿y si queremos conocer todos los óptimos locales posibles que tiene
una función? Analizando la estructura de los algoritmos genéticos podemos ver
cómo, aplicando ciertas técnicas, sería posible configurar los algoritmos genéticos
para que encontraran varios óptimos a la vez. A este tipo de problemas se les llama:
problemas multimodales.

Optimización II
10
Tema 7. Ideas clave
Dos factores contrapuestos influyen sobre la efectividad de un AG (algoritmo
genético):

 Provocar la convergencia: este punto se centra en la búsqueda en regiones

prometedoras, mediante la presión selectiva, procesos de competición entre
padres e hijos, etc. La presión selectiva permite que los mejores individuos sean
seleccionados para reproducirse. Es necesaria para que el proceso de búsqueda
no sea aleatorio.

 Provocar la diversidad: esto lo conseguimos evitando la convergencia prematura,

es decir, la rápida convergencia hacia zonas que no contienen el óptimo global,
esto se hace introduciendo diversidad en la población.

Figura 7. Convergencia vs diversidad. Fuente: elaboración propia.

La diversidad está asociada a las diferencias entre los cromosomas en la población,

donde la falta de diversidad genética determina que todos los individuos en la
población son parecidos y, en consecuencia, la falta de diversidad implica, de manera
directa, la convergencia prematura a óptimos locales.

Optimización II
11
Tema 7. Ideas clave
Las soluciones propuestas a estos problemas pueden ser:

 La inclusión de mecanismos de diversidad en la evolución (mencionaremos

algunas propuestas para diversidad).

 La reinicialización cuando se produce convergencia prematura; esto en función de

que el resultado es irreversible (esto se propone en el algoritmo CHC).

El algoritmo CHC (Eshelman, 1991), es un algoritmo genético clásico que introduce

técnicas que permiten una correcta exploración-explotación del espacio. Se pueden
aplicar ciertas estrategias sobre los algoritmos genéticos para que estos puedan
resolver problemas multimodales de forma eficaz.

7.3. Algoritmo CHC

El algoritmo CHC es un algoritmo genético clásico que trabaja con información

binaria. Es muy conocido, ya que proporciona unos resultados muy buenos y
competitivos. Su secreto está en el correcto equilibrio entre exploración-explotación
del espacio, que le permite encontrar muy buenas soluciones en poco tiempo. En
efecto, es una de las primeras propuestas de AG que introduce un equilibrio entre
diversidad y convergencia.

Para ello, el algoritmo CHC implementa las siguientes estrategias:

 Selección elitista.
 Cruce uniforme HUX.
 Prevención del incesto.
 Reinicialización.
 Eliminación del operador de mutación.

Optimización II
12
Tema 7. Ideas clave
Selección elitista

Incluye una estrategia de reemplazamiento elitista. De esta forma, los mejores

individuos de una población pasan siempre a la siguiente. Se seleccionan los 𝑁
mejores cromosomas entre padres e hijos y los 𝑁 mejores elementos encontrados
hasta el momento permanecerán en la población actual.

El número de individuos conservados se establece previamente antes de comenzar

la ejecución del algoritmo. Como ya vimos, la selección elitista es una técnica que
aumenta la convergencia y explotación de buenas soluciones. Además, permite que
las mejores soluciones obtenidas hasta el momento no se pierdan de una generación
a otra.

Figura 8. Selección elitista en CHC. Fuente: elaboración propia.

Cruce uniforme HUX

Intercambia la mitad de los bits (alelos) en los que los padres difieren. De esta forma,
los hijos siempre son lo más diferente posible de ambos padres, pero, a su vez, se
conservan aquellos valores en que los padres son idénticos. Gracias al cruce uniforme
HUX, se generan nuevas soluciones que permiten una correcta exploración del
espacio de soluciones. Nótese que este tipo de cruce genera hijos muy diferentes

Optimización II
13
Tema 7. Ideas clave
cuando los padres son muy diferentes e hijos más parecidos a los padres cuando estos
son muy parecidos.

De esta manera, cuando el algoritmo empieza a converger a una determinada

solución, se realizará un proceso más encaminado a la explotación que en las
primeras iteraciones. La mejor estrategia de búsqueda consistía en realizar una
exploración del espacio de soluciones en las primeras iteraciones y luego la
explotación en las zonas más prometedoras encontradas.

Figura 9. Cruce uniforme HUX. Fuente: adaptado de

File:Computational.science.Genetic.algorithm.Crossover.Half.Uniform.Crossover.svg, 2021.

Prevención del incesto

El algoritmo CHC implementa técnicas denominadas para prevención del incesto. La

idea de estas técnicas consiste en evitar que dos soluciones se crucen si son muy
parecidas. Al cruzar dos soluciones muy parecidas siempre obtendremos hijos muy
parecidos a los padres, con lo que explotamos, pero no exploramos el espacio.

Optimización II
14
Tema 7. Ideas clave
Previniendo el incesto, cruzamos padres que se diferencian mucho entre sí y
generamos soluciones muy dispares que nos permiten realizar una correcta
exploración del espacio. Para llevar a cabo este proceso debe definirse el umbral de
cruce, 𝜇, que indica el número de bits en que deben diferenciarse dos soluciones para
ser susceptibles de cruzarse.

Se forman 𝑁/2 parejas con los elementos de la población. Sólo se cruzan las parejas
cuyos miembros difieren en un número determinado de bits (umbral de cruce). El
umbral se inicializa a:

𝐿 Longitud del cromosoma

𝜇= =
4 4

Si durante una serie de ejecuciones no se crean descendientes que sean mejores a

los de la población actual, entonces se decrementa el umbral con el objetivo de
aumentar la cantidad de soluciones que pueden cruzarse entre sí. Es decir, si en 𝑋
iteraciones no se mejora la solución actual, entonces:

𝜇 ⟻𝜇−1

Como podemos observar, conforme el algoritmo va avanzando en número de

iteraciones, la prevención del incesto se va volviendo menos restrictiva hasta que
llega un punto en que desaparece cuando 𝜇 = 0.

Advertencia: dado que la prevención del incesto es un mecanismo de

exploración del espacio, es bueno no tenerlo en cuenta cuando queramos que
el algoritmo explote las áreas prometedoras del espacio de soluciones.

Optimización II
15
Tema 7. Ideas clave
Reinicialización

Cuando el umbral 𝜇 de prevención del incesto vale cero, entonces reinicializamos el

algoritmo CHC. De esta forma, aprovechamos al máximo el número de iteraciones
disponibles. La reinicialización puede hacerse de dos formas distintas:

 Guardamos la mejor solución encontrada y generamos el resto de los miembros

de forma aleatoria (35 % de variación aleatoria e incluyendo una copia suya). Este
sistema es el que permite una mayor exploración del espacio, ya que
prácticamente toda la población ha sido generada desde cero.

 Guardamos la mejor solución y generamos el resto de las soluciones de forma que

todas contengan un tanto por ciento bajo de genes copiados de la mejor solución.
Este método tiene una componente algo peor en exploración del espacio, pero
trata de explotar y sacar partido a las buenas soluciones conseguidas en la
iteración anterior.

Figura 10. Reinicialización. Fuente: elaboración propia.

Eliminación del operador de mutación

El algoritmo CHC carece de operador de mutación. Esto es debido a que, con las
técnicas ya vistas, el componente explorador y explotador del espacio de soluciones
es suficientemente bueno. Por tanto, no es necesario el uso del operador de
mutación que, al no aportar ninguna mejora, solo consumiría un tiempo de cómputo
que puede dedicarse a otras tareas.

Optimización II
16
Tema 7. Ideas clave
 Figura 11. Esquema para algoritmo CHC. Fuente: elaboración propia.

Es posible realizar una implementación del algoritmo CHC que trabaje con
información real realizando los siguientes cambios al algoritmo CHC original:

 Uso del operador BLX − 𝛼 como operador de cruce.

 Utilizamos el operador de reinicialización que almacena la mejor solución y genera

el resto de los valores de forma aleatoria (ver Figura 10).

 Codificación de la información real en binario para la aplicación del operador de

incesto. Debe utilizarse el mismo número de bits para cada solución para que el
operador pueda aplicarse correctamente.

Observación: como un paso más en el desarrollo de algoritmos de aplicación

orientada a inteligencia artificial, se puede hablar de algoritmos de clustering. Para
saber más, en el vídeo Algoritmos de Clustering se puede encontrar una explicación
sobre el desarrollo de algoritmos de aplicación orientada a inteligencia artificial.

Optimización II
17
Tema 7. Ideas clave
7.4. Problemas multimodales

Los problemas multimodales son aquellos en los que, en vez de querer obtener el
óptimo global de una función, nos interesa obtener la localización de todos los
óptimos locales. Por ejemplo, si buscamos valores máximos en la siguiente función
dentro del intervalo [0,17]:

Figura 12. Localización de óptimos locales. Fuente: elaboración propia.

Entonces podemos observar cómo, en dicho intervalo, los óptimos locales los forman
el conjunto de puntos {3, 7, 12, 15}, siendo 𝑥 = 15 el máximo global. Si utilizamos un
algoritmo genético normal, lo más seguro es que converja a uno de los cuatro
óptimos locales disponibles en vez de encontrarlos todos. Para evitar esto y poder
localizarlos todos, pueden aplicarse diversas técnicas.

Por lo general, las técnicas disponibles pueden clasificarse en dos grandes grupos:

 Estrategias secuenciales: conllevan varias ejecuciones del mismo algoritmo

genético. En cada ejecución debe convergerse a una solución distinta, por lo que
se introducen técnicas que tratan de evitar que todas las ejecuciones converjan a
la misma solución.

Optimización II
18
Tema 7. Ideas clave
 Figura 13. Estrategia secuencial. Fuente: elaboración propia.

 Estrategias paralelas: dentro de esta categoría se enmarcan aquellos métodos

que encuentran todos los óptimos locales en una misma ejecución del algoritmo
genético. De esta manera, se introducen técnicas que permiten a las soluciones de
una misma población converger hacia varias soluciones en vez de una.

Figura 14. Paralelismo. Fuente: elaboración propia.

Nota: dentro de las estrategias secuenciales, la más conocida es el

denominado método secuencial.

El método secuencial realiza, iterativamente, ejecuciones de un algoritmo genético.

Al final de cada iteración, se almacena la mejor solución obtenida y se penalizan, en
posteriores ejecuciones, aquellas soluciones que estén dentro de las zonas del
espacio de soluciones que ya hayan sido exploradas.

La idea consiste en ir reduciendo el espacio de búsqueda disponible en cada iteración

a aquellas zonas no explotadas en profundidad y encontrar, de esta manera, todos
los óptimos posibles. Detallamos a continuación el proceso que este método sigue:

 Ejecución de un algoritmo genético.

Optimización II
19
Tema 7. Ideas clave
 Almacenamos la solución obtenida en el vector de soluciones encontradas.

 Ejecutamos otro algoritmo genético con la siguiente condición: las soluciones que
sean cercanas a las almacenadas en el vector de soluciones obtienen un bajo valor
de idoneidad.

 ¿La solución encontrada en esta ejecución del algoritmo genético es muy inferior
a las almacenadas en el vector de soluciones?
• Sí: la solución se descarta.
• No: la solución se almacena en el vector de soluciones encontradas.

 ¿Se cumple la condición de parada?

• Sí: termina el algoritmo.
• No: vamos al paso 3.

Figura 14. Método secuencial. Fuente: elaboración propia.

Optimización II
20
Tema 7. Ideas clave
Dentro de las estrategias paralelas, las más conocidas son:

 Método de sharing: el objetivo es formar pequeños subconjuntos dentro de la

población que converjan a zonas distintas del área de soluciones. Para ello, se
penaliza la calidad de aquellos individuos que se encuentren en zonas del espacio
que estén ocupadas por una alta cantidad de soluciones. De esta manera, las
soluciones que se encuentran en zonas densamente pobladas pasan a convertirse
en malas soluciones y son descartadas por el operador de cruce. Al no penalizarse
el valor de calidad de aquellas soluciones que se encuentran lejos de las demás, el
algoritmo trabaja con ellas y se permite así la convergencia en varios puntos del
espacio al mismo tiempo.

 Método de clearing: consiste en eliminar soluciones que se encuentren muy

cercanas unas a otras y que, además, tengan un valor de idoneidad más bajo que
el de sus vecinos.

Los pasos que sigue este método son los siguientes:

 Para cada una de las soluciones:

• Se realiza un proceso de comparación con aquellas que se encuentran a una

distancia menor a un cierto umbral.

• Si el valor de idoneidad de esa solución es menor que el de la solución actual

que estamos comprobando, dicha solución se elimina del proceso de selección.
En caso de ser mayor, se mantiene.

 Una vez que tenemos los elementos dominantes de cada nicho, realizamos el
proceso de selección utilizando únicamente dichas soluciones.

Optimización II
21
Tema 7. Ideas clave
El método de clearing realiza un proceso similar al de sharing, pero es mucho más
restrictivo, ya que elimina soluciones del proceso de selección en vez de modificar
su valor de idoneidad.

Uno de los aspectos que no se ha discutido es la eficacia de los algoritmos de

optimización. Esto se aborda en el vídeo Algoritmos de optimización: eficacia, donde
se discute sobre cómo probar algoritmos y darlos a conocer.

7.5. Cuaderno de ejercicios

Ejercicio 1

Considere la siguiente implementación didáctica de un algoritmo genético básico en

MATLAB. Identifique las reglas de selección, cruce, mutación, reemplazamiento y
criterio de paro.

%% DEFINICIÓN DEL PROBLEMA %%

syms f(u) g(u) % definición de funciones simbólicas
f(u) = u.*u-4*u+5; % función a optimizar
D = [-30,30]; % dominio de restricción
g(u) = piecewise(D(1) <= u & u <= D(2),0,1); % función de restricciones
F(u) = 1./(1+f(u).*f(u)+1000*g(u)); % función de idoneidad

itersNum = 5; % número de iteraciones

R = D(2)-D(1); % tamaño del dominio
ibits = ceil(log(1+R)/log(2)); % bits para representar parte entera
M = 10000; % partes del dominio
prst = R/M; % precisión o diferencia mínima entre individuos
wbits = ceil(log(1+R/prst)/log(2)); % bits para representar un individuo

Optimización II
22
Tema 7. Ideas clave
T = numerictype(true,wbits,wbits-ibits); % características de la
representación binaria (true: con signo, wbits: tamaño de la representación,
wbits-ibits: número de bits de la representación dedicados a la parte
fraccionaria)
mp = 0.05; % probabilidad de mutación de un bit
mutat = true; % variable lógica para decidir aplicar mutación
%% ITERACIONES %%
N = 2^2; % tamaño de población
rng('shuffle'); % inicializa el generador de números aleatorios con el reloj
x = D(1)+R*rand(1,N); % población inicial
for i = 1:itersNum

% Seleccionar %
y = double(F(x));
p = y/sum(y);
P = [0,cumsum(p)];
P(end) = 1;
idx = 0:N;
pd = makedist('PiecewiseLinear','x',idx,'Fx',P);
idxs = ceil(icdf(pd,rand([1,N])));

% Cruzar %
b = fi(x(idxs),T);
j = 1;
while j < N
prnt1 = b(j);
prnt2 = b(j+1);
bitcut = randi(wbits-1);
ch11 = bitsliceget(prnt1,wbits,bitcut+1);
ch12 = bitsliceget(prnt1,bitcut,1);
ch21 = bitsliceget(prnt2,wbits,bitcut+1);
ch22 = bitsliceget(prnt2,bitcut,1);
ch1 = bitconcat(ch11,ch22);
ch1 = reinterpretcast(ch1,T);
ch2 = bitconcat(ch21,ch12);
ch2 = reinterpretcast(ch2,T);
b(j) = ch1;
b(j+1) = ch2;
j = j+2;
end

Optimización II
23
Tema 7. Ideas clave
 % Mutar %
if mutat
u = rand([N,wbits]);
[row,col] = find(u<mp);
for m = 1:length(row)
bitcplt = bitcmp(bitget(b(row(m)),col(m)));
b(row(m)) = bitset(b(row(m)),col(m),bitcplt);
end
end

% Reemplazar %
x = double(b);

end

% Salida %
[Fmax,imax] = max(double(F(x)));
disp('Mejor solución:');
xmax = x(imax)
fmax = double(f(x(imax)))

El código busca una solución aproximada al siguiente problema de optimización:

min 𝑓(𝑥) = 𝑥 − 4𝑥 + 5
∈ℝ
Sujeto a: −30 ≤ 𝑥 ≤ 30

Primero, encuentre la solución analítica al problema. Luego, usando el código con

una población inicial de cuatro individuos y después con una población de dieciséis
individuos, diga lo que observa en los resultados. También discuta lo observado al
cancelar la mutación o subirla al valor de 0.25 de probabilidad por bit.

Optimización II
24
Tema 7. Ideas clave
Solución

Las reglas que se han utilizado en algoritmo son:

 Selección: ruleta.
 Cruce: binario clásico.
 Mutación: por bit.
 Reemplazamiento: generacional.
 Criterio de paro: número de iteraciones.

La solución del problema de optimización se puede encontrar rápidamente al ver que

se trata de una función objetivo cuya gráfica es una parábola convexa. En efecto, si
se completa el trinomio cuadrado perfecto se obtiene que 𝑓(𝑥) = (𝑥 − 2) + 1, que
sería la traslación de la parábola 𝑝(𝑥) = 𝑥 , dos unidades a la derecha y una unidad
hacia arriba, quedando que el mínimo se alcanza en 𝑥 ∗ = 2 (eje de simetría) y el valor
mínimo es justamente: 𝑓(𝑥 ∗ ) = 1.

Al correr el código tres veces para una población de cuatro individuos, se obtienen
las tres soluciones dadas en las tablas adjuntas. Los resultados son de esperarse: una
población mayor nos entrega una mejor estadística.

Tabla 1. Resultados para 𝑁 = 4 y 𝑁 = 16. Fuente: elaboración propia.

Optimización II
25
Tema 7. Ideas clave
Dejando el tamaño de la población en dieciséis y omitiendo la mutación, al ejecutar
tres veces el código tenemos la tabla de la izquierda. Por otro lado, si se repite con
una probabilidad de mutación de 0.25, se obtiene la tabla de la derecha. La mutación
con un tamaño de población adecuado es benéfica para obtener un mejor
refinamiento, aunque, por supuesto, el tiempo de procesamiento y la convergencia
se demoran.

Tabla 2. Resultados para 𝑁 = 16. Fuente: elaboración propia.

Ejercicio 2

Realice las modificaciones al algoritmo del Ejercicio 1 para que se trabaje con la
representación real, utilizando un operador de cruce BLX − 𝛼 —con 𝛼 igual a 0.5,
una mutación con desviación estándar 𝜎 igual a un tercio del valor de precisión de la
representación— y un reemplazo elitista, manteniendo un cuarto de la población.

Solución

Una versión del código es la siguiente:

%% DEFINICIÓN DEL PROBLEMA %%

syms f(u) g(u) % definición de funciones simbólicas
f(u) = u.*u-4*u+5; % función a optimizar
D = [-30,30]; % dominio de restricción
g(u) = piecewise(D(1) <= u & u <= D(2),0,1); % función de restricciones
F(u) = 1./(1+f(u).*f(u)+1000*g(u)); % función de idoneidad

R = D(2)-D(1); % tamaño del dominio

Optimización II
26
Tema 7. Ideas clave
ibits = ceil(log(1+R)/log(2)); % bits para representar parte entera
M = 10000; % partes del dominio
prst = R/M; % precisión o diferencia mínima entre individuos
wbits = ceil(log(1+R/prst)/log(2)); % bits para representar todo el individuo
T = numerictype(true,wbits,wbits-ibits); % características de la
representación binaria

itersNum = 10; % número de iteraciones

alp = 0.5; % parámetro de amplitud del método de cruza BLX
sig = prst/3;

%% ITERACIONES %%

N = 2^6; % tamaño de población

n = N/(2^2); % subpoblación élite
rng('shuffle'); % inicializa el generador de números aleatorios con el reloj
x = D(1)+R*rand([1,N]); % población inicial
xnew = zeros([1,N]);
for i = 1:itersNum
% Seleccionar %
y = double(F(x)); % valores de idoneidad
p = y/sum(y); % valores de probabilidad de los individuos
P = [0,cumsum(p)]; % probabilidades acumuladas comenzando en cero
P(end) = 1; % asegurar a pesar de la precisión que el último valor es uno
idx = 0:N; % índices para asociar con las probabilidades acumuladas
pd = makedist('PiecewiseLinear','x',idx,'Fx',P); % crear una distribución
de probabilidad
idxs = ceil(icdf(pd,rand([1,N]))); % obtener una muestra de índices según
sea más probables

% Cruzar %

selx = x(idxs); % indoviduos seleccionados

j = 1;
while j < N
% método BLX-alfa
prnt1 = selx(j);
prnt2 = selx(j+1);
pntmax = max([prnt1,prnt2]);
pntmin = min([prnt1,prnt2]);

Optimización II
27
Tema 7. Ideas clave
pntdiff = pntmax - pntmin;
ubound = pntmax + alp*pntdiff;
lbound = pntmin - alp*pntdiff;
bndrang = ubound - lbound;
ch1 = lbound + bndrang * rand;
ch2 = lbound + bndrang * rand;
xnew(j) = ch1;
xnew(j+1) = ch2;
j = j+2;
end

% Mutar %

xnew = xnew + sig*randn([1,N]);

% Reemplazar %
ynew = double(F(xnew)); % valores de idoneidad nuevos
[ynews,inews] = sort(ynew,"descend"); % ordena los valores de idoneidad
[ys,is] = sort(y,"descend"); % obten la permutación de índices del
ordenamiento de idoneidad
x = [xnew(inews(1:n)),x(is(1:(N-n)))]; % forma la nueva población
manteniendo la subpoblación élite
x = x(randperm(N)); % mezcla aleatoriamente los individuos

end

% Salida %

[Fmax,imax] = max(double(F(x)));
disp('Mejor solución:');
disp('x = '+string(x(imax)));
disp('f(x) = '+string(double(f(x(imax)))));

Optimización II
28
Tema 7. Ideas clave
Al ejecutar el código en tres ocasiones se obtiene:

Tabla 3. Ejecución del código. Fuente: elaboración propia.

Esto deja ver que tiene muy buena convergencia.

Ejercicio 3

Realice las modificaciones al algoritmo del Ejercicio 1 para que se convierta en un

algoritmo CHC y aplíquelo al mismo problema. Discuta las observaciones.

Solución

Las modificaciones necesarias son:

 Selección elitista: que, en nuestro caso, tomaremos el cuarto de población que

tenga mejor idoneidad.

 Cruce uniforme HUX: la mitad de aquellos bits en los que difieren los progenitores
se utilizan para un intercambio entre ellos

 Prevención del incesto: se define un número mínimo de bits en que deben diferir
los progenitores para que se dé apareamiento, que disminuirá cada vez que el
número de apareamientos sea pequeño.

 Eliminación de la mutación: simplemente se omitieron las líneas

correspondientes a esta operación en el código del Ejercicio 1.

Optimización II
29
Tema 7. Ideas clave
 Se introduce una operación de reinicio de ejecución del código un número de
veces predefinido (cada vez que el umbral de incesto ha llegado a cero y no hay
mejora considerable en el mejor individuo obtenido).

El código implementado se muestra a continuación:

%% DEFINICIÓN DEL PROBLEMA %%

syms f(u) g(u) % definición de funciones simbólicas
f(u) = u.*u-4*u+5; % función a optimizar
D = [-30,30]; % dominio de restricción
g(u) = piecewise(D(1) <= u & u <= D(2),0,1); % función de restricciones
F(u) = 1./(1+f(u).*f(u)+1000*g(u)); % función de idoneidad

itersNum = 15; % número máximo de iteraciones

execNum = 10; % número máximo de reinicializaciones
noimprvNum = 3; % número mínimo de iteraciones sin mejora en la solución

R = D(2)-D(1); % tamaño del dominio

ibits = ceil(log(1+R)/log(2)); % bits para representar parte entera
M = 10000; % partes del dominio
prst = R/M; % precisión o diferencia mínima entre individuos
wbits = ceil(log(1+R/prst)/log(2)); % bits para representar todo el individuo
T = numerictype(true,wbits,wbits-ibits); % características de la
representación binaria
mu = floor(wbits/4); % umbral de incesto (los progenitores deberán tener un
número de bits igual o superior a este para cruzarse)
N = 2^6; % tamaño de población par
n = N/(2^2); % subpoblación élite
rng('shuffle'); % inicializa el generador de números aleatorios con el reloj
x = D(1)+R*rand([1,N]); % población inicial
xi = zeros([1,itersNum+1]); % vector de soluciones por iteración
ofi = zeros([1,itersNum+1]); % vector de valores de la función objetivo
Fi = zeros([1,itersNum+1]); % vector de idoneidades por iteración
[Fmax,imax] = max(double(F(x))); % obtención de la idoneidad e índice de la
mejor solución en la población inical
xi(1) = x(imax); % obtención de la mejor solución inical
ofi(1) = double(f(x(imax))); % obtención del mejor valor objetivo inicial
Fi(1) = double(F(x(imax))); % obtención de la mejor idoneidad inicial

Optimización II
30
Tema 7. Ideas clave
dx = zeros([1,itersNum]); % definición del vector de diferencias
noimprv = 0; % contador de iteraciones sin mejora
nomatingnum = 0; % contador de cruzas no exitosas en una iteración
execount = 0; % contador de reinicializaciones

%% ITERACIONES %%
i = 1;
while i < itersNum && execount < execNum
% Seleccionar %
y = double(F(x)); % valores de idoneidad
p = y/sum(y); % valores de probabilidad de los individuos
P = [0,cumsum(p)]; % probabilidades acumuladas comenzando en cero
P(end) = 1; % asegurar a pesar de la precisión que el último valor es uno
idx = 0:N; % índices para asociar con las probabilidades acumuladas
pd = makedist('PiecewiseLinear','x',idx,'Fx',P); % crear una distribución
de probabilidad
idxs = ceil(icdf(pd,rand([1,N]))); % obtener una muestra de índices según
sea más probables

% Cruzar %
b = fi(x(idxs),T); % representación binaria
nomatingnum = 0; % contador de parejas no cruzadas por incesto
j = 1; % contador de parejas a cruzar
while j < N
pc1 = b(j); % obten el primer progenitor de la lista
pc2 = b(j+1); % obten el segundo progenitor de la lista
chrs = bin(bitxor(pc1,pc2)); % operador XOR sobre los bits de los
progenitores
chrs = chrs(end:-1:1); % ordena la cadena de bits de la comparación igual
que la posición de bits
indxs = 1:wbits; % índices de los bits de una representación
indxs = indxs(chrs == '1'); % índices de las posiciónes de bits diferentes
indxs = indxs(randperm(length(indxs))); % permutación aleatoria de los
índices del paso previo
m = floor(length(indxs)/2); % número de bits diferentes a intercambiar
if length(indxs) > mu % cruza si el número de bits diferentes supera el
umbral de incesto
for k = 1:m % proceso de cruza entre los bits diferentes
bitcplt = bitcmp(bitget(pc1,indxs(k)));
pc1 = bitset(pc1,indxs(k),bitcplt);

Optimización II
31
Tema 7. Ideas clave
 bitcplt = bitcmp(bitget(pc2,indxs(k)));
pc2 = bitset(pc2,indxs(k),bitcplt);
end
else
nomatingnum = nomatingnum+1;
end
b(j) = pc1; % sustitución de padres por hijos
b(j+1) = pc2;
j = j+2; % avanza el contador de parejas
end

% Reemplazar %
xnew = double(b); % nueva población obtenida en representación real
ynew = double(F(xnew)); % valores de idoneidad nuevos
[ynews,inews] = sort(ynew,"descend"); % ordena los valores de idoneidad
[ys,is] = sort(y,"descend"); % obten la permutación de índices del
ordenamiento de idoneidad
x = [xnew(inews(1:n)),x(is(1:(N-n)))]; % forma la nueva población
manteniendo la subpoblación élite
x = x(randperm(N)); % mezcla aleatoriamente los individuos

% Mejor solución %
[Fmax,imax] = max(double(F(x)));
xi(i+1) = x(imax);
ofi(i+1) = double(f(x(imax)));
Fi(i+1) = Fmax;

% Incesto %
if nomatingnum > n
noimprv = noimprv+1; % si el número de apareamientos fallidos es mayor al
número de la población elitista se incrementa en uno el contador de
iteraciones que no mejoran la solución obtenida
end
if mu > 0 % si el mínimo número de bits de diferenciación de los padres es
mayor a cero y no ha habido mejora en la solución un número de veces dado
entonces decrementa el umbral de incesto y reinicia el conteo de iteraciones
sin mejora
if noimprv > noimprvNum
mu = mu-1;
noimprv = 0;

Optimización II
32
Tema 7. Ideas clave
 end
else % en caso de haber llegado a umbral de incesto cero reinicializa la
ejecución del código
% Reinicialización %
[bestFmax,bestimax] = max(Fi(1:i));
xi(1) = xi(bestimax);
ofi(1) = fi(bestimax);
Fi(1) = bestFmax;
dx = zeros([1,itersNum]);
x(1) = xi(1);
x(2:end) = D(1)+R*rand([1,N-1]);
noimprv = 0;
execount = execount+1;
i = 1;
continue
end

i = i+1; % incremnta el contador de iteraciones

end

% Salida % % imprime la mejor solución encontrada de entre todas la

% iteraciones
[bestFmax,bestimax] = max(Fi);
disp('x = '+string(xi(bestimax)));
disp('f(x) = '+string(ofi(bestimax)));

Las soluciones encontradas de aplicar tres veces del código son:

Tabla 4. Soluciones encontradas. Fuente: elaboración propia.

Optimización II
33
Tema 7. Ideas clave
Ejercicio 4

Basado en las opciones que pueden elegirse para ejecutar el algoritmo genético de
Optimization Toolbox de MATLAB, proponga modificaciones al pequeño código del
Ejercicio 3, de tal suerte que se privilegie la explotación y convergencia para que,
dada una población en una subzona del dominio, explore solo esa zona y obtenga el
óptimo de ella.

Utilice la versión del algoritmo CHC genético para la representación real del Ejercicio
2. Proponga modificaciones al código de tal suerte que se privilegie la explotación y
convergencia, con la intención de que, dada una población en una subzona del
dominio, explore lo más posible solo esa zona y obtenga el óptimo en ella. Pruebe el
código generando una población inicial en el subdominio [−0.5,0.5] × [0.5,1.5], donde
se sabe, de la exploración de la gráfica, que el mínimo está en el punto (𝑥 = 0,
𝑦 = 1).

Considere el siguiente problema:

min 𝑓(𝑥) = 20 + 𝑥 − 10 cos(2𝜋𝑥)

∈ℝ
Sujeto a: −4.5 ≤ 𝑥 ≤ 4.5

Aquí, la función objetivo es una versión unidimensional de la función de Rastrigin,

que se verá en el siguiente ejercicio. Esta función cuenta con varios mínimos locales.
Grafique la función para poder visualizarlos. Utilice el código del Ejercicio 2 con una
población inicial aleatoria que se extienda en todo el dominio, después vuelva a
correr el código con una población inicial generada en el subdominio [−4.5, −3.5].

Optimización II
34
Tema 7. Ideas clave
Solución

La gráfica de la función objetivo se ve:

Figura 16. Función de Rastrigin unidimensional. Fuente: elaboración propia.

Se pueden apreciar nueve mínimos locales dentro del dominio [−4.5,4.5] y un mínimo
global justo en 𝑥 = 0.

Al ejecutar el código del Ejercicio 2 cambiando la función objetivo por la función de

Rastrigin unidimensional definida arriba, con una población inicial en el dominio
[−4.5,4.5], se obtuvo la solución (𝑥 = 0.0027, 𝑓(𝑥) = 10.0015), o sea, se encontró el

mínimo global. Mientras que, cuando se ejecutó con una población inicial dentro del
subdominio [−4.5, −3.5], se obtuvo (𝑥 = −3.9798, 𝑓(𝑥) = 25.9192), es decir, se
encontró el mínimo local que está más a la izquierda.

Optimización II
35
Tema 7. Ideas clave
De estos resultados se aprecia que el código del Ejercicio 2 tiene un comportamiento
de explotación, exploración y convergencia adecuado para utilizar un método
multimodal paralelo en la búsqueda de soluciones locales con subpoblaciones sobre
diferentes subregiones del dominio.

Ejercicio 5

Implementar un código utilizando el algoritmo genético en Optimization Toolbox de

MATLAB para encontrar el mínimo global de la función de Rastrigin definida como:

ras(𝑥, 𝑦) = 20 + 𝑥 + 𝑦 − 10(cos(2𝜋𝑥) + cos(2𝜋𝑦))

Donde (𝑥, 𝑦) ∈ ℝ . Esta función cuenta con infinidad de mínimos locales, pero tiene
su mínimo global en (𝑥 ∗ = 0, 𝑦 ∗ = 0) y su valor es evidentemente ras(𝑥 ∗ = 0, 𝑦 ∗ =
0) = 0.

Ejecute, al menos tres veces, el código dentro del dominio de restricción [−30,30]
para ver qué diferencias se observan en las soluciones obtenidas. Vuelva a correr el
código al menos tres veces, ahora en el dominio menor [−3,3] . Por último, grafique
la función en ambos dominios y discuta los resultados.

Solución

El código para aplicar el algoritmo genético de Optimization Toolbox de MATLAB (con

los parámetros por default) es muy sencillo y se puede ver a continuación:

%% Definición de la función de Rastrigin:

ras = @(x, y) 20 + x.^2 + y.^2 - 10*(cos(2*pi*x) + cos(2*pi*y));
% Parámetro para facilitar la definición del dominio:
hDSize = 30;
% Definición de la variable x y su dominio:
x = optimvar("x","LowerBound",-hDSize,"UpperBound",hDSize);
% Definición de la variable y y su dominio:

Optimización II
36
Tema 7. Ideas clave
y = optimvar("y","LowerBound",-hDSize,"UpperBound",hDSize);
% Construcción del contenedor del problema:
prob = optimproblem("Objective",ras(x,y),"ObjectiveSense","min");
% Inicializa el generador de números aleatorios con el tiempo del reloj:
rng('shuffle');
% Busca la solución en tres ocasiones con el algoritmo genético:
[sol,fval] = solve(prob,"Solver","ga")
[sol,fval] = solve(prob,"Solver","ga")
[sol,fval] = solve(prob,"Solver","ga")

% Grafica:
fsurf(ras,[-hDSize hDSize],"ShowContours","on")
title('Rastrigin in [-' + string(hDSize) + ',' + string(hDSize) + ']^2')
xlabel("x")
ylabel("y")

Al ejecutar el código se obtuvieron las siguientes soluciones:

Tabla 5. Ejecución del código. Fuente: elaboración propia.

Al volver a ejecutar el código, esta vez sobre [−3,3] , es decir, haciendo la variable
hDSize = 3, se obtienen las soluciones:

Tabla 6. Aplicación del código sobre [−3,3] . Fuente: elaboración propia.

Optimización II
37
Tema 7. Ideas clave
Las gráficas de la función sobre cada dominio se muestran abajo. Se puede ver que,
para el caso del dominio [−30,30] , la cantidad de mínimos entre los que buscar es
mucho mayor que para el dominio [−3,3] ; incluso en la gráfica del primer dominio
apenas se notan los mínimos. Esto hace que al algoritmo le cueste más trabajo
encontrar el mínimo global en [−30,30] que en [−3,3] , lo cual se puede corroborar
con las soluciones encontradas, pues las más precisas fueron del caso [−3,3] . De
hecho, los tiempos de ejecución fueron notablemente menores en este último.

Figura 17. Gráficas de la función de Rastrigin. Fuente: elaboración propia.

Optimización II
38
Tema 7. Ideas clave
7.6. Referencias bibliográficas

Eshelman, L. J. (1991). The CHC adaptive search algorithm: How to have safe search
when engaging in nontraditional genetic recombination. Foundations of Genetic
Algorithms, 1, 265-283.
https://www.sciencedirect.com/science/article/abs/pii/B9780080506845500203

File:Computational.science.Genetic.algorithm.Crossover.Half.Uniform.Crossover.svg
. (2021, septiembre 11. En Wikimedia Commons.
https://commons.wikimedia.org/wiki/File:Computational.science.Genetic.algorithm
.Crossover.Half.Uniform.Crossover.svg

Optimización II
39
Tema 7. Ideas clave