Genetic Algorithm (GA)¶

Autor: Rodrigo S. Cortez-Madrigal
web: https://roicort.github.io
github: https://github.com/roicort/MetaZoo
docs: https://roicort.github.io/MetaZoo/

Objetivo¶

Implementar un Algoritmo Genético (AG) que incorpore elitismo y compare el desempeño de distintos operadores de selección: Ruleta, Muestreo Estocástico Universal (SUS) y Torneo. El propósito es analizar y contrastar sus efectos sobre convergencia, calidad de solución y estabilidad.

Requisitos de implementación¶

Elitismo (obligatorio)
- Integre un esquema de elitismo y especifique cuál utiliza:
  - Mejor individuo (p. ej., 1 élite).
  - Porcentaje de mejores (p. ej., 5–10% de la población).
  - Total (todos los individuos élite pasan sin alteración)

Para esta implementación se utiliza un porcentaje de mejores (configurable por el usuario). Ver Implementación

Operadores de selección (obligatorios)
- Implemente y ejecute el AG con cada uno de los siguientes:
  - Ruleta. Ver Implementación
  - SUS (Stochastic Universal Sampling). Ver Implementación
  - Torneo: (indique el tipo de torneo utilizado) Ver Implementación
    - Se implementó un tamaño del torneo (k) configurable por el usuario.
    - Con o sin reemplazo, según se especifique.
    - Determinístico (el mejor siempre gana) o probabilístico (el mejor gana con cierta probabilidad).
Línea base (sugerida) Incluya Selección Aleatoria (uniforme) como testigo para ilustrar presión de selección baja y sus implicaciones en convergencia. Implementada como un operador de selección Ver Implementación

Implementación y Experimentos¶

In [1]:

Copied!





from metazoo.bio.evolutionary import GeneticAlgorithm
from metazoo.bio.evolutionary.operators import selection, mutation, crossover
from metazoo.gym.mono import Function

import plotly.io as pio
#pio.renderers.default = "jupyterlab"
pio.renderers.default = "png"

import pandas as pd
from rich.progress import track
import numpy as np
import plotly.express as px
from metazoo.bio.evolutionary import GeneticAlgorithm
from metazoo.bio.evolutionary.operators import selection, mutation, crossover
from metazoo.gym.mono import Function

import plotly.io as pio
#pio.renderers.default = "jupyterlab"
pio.renderers.default = "png"

import pandas as pd
from rich.progress import track
import numpy as np
import plotly.express as px

Las funciones de rastringin, ackley y sphere nos sirve en este caso para comparar los operadores de selección y el elitismo dado que sus minimos se encuentran en el origen (0,0) y son funciones bien conocidas en el ámbito de la optimización.

In [2]:

Copied!





targets = ['Rastrigin',
'Ackley',
'Sphere'
]
targets = ['Rastrigin',
'Ackley',
'Sphere'
]

In [3]:

Copied!

from metazoo.bio.utils import encoding
from metazoo.bio.utils import encoding

Control de variables¶

Ejecutamos para cada entorno de prueba los tres operadores de selección con y sin elitismo. Mantenemos constantes (para cada entorno de prueba) la población, número de generaciones, cruza, mutación y otros parámetros que correspondan, para aislar el efecto de la selección y del elitismo.

            crossover_function=crossover.onepoint,
            mutation_function=mutation.flip_bit,
            population_size=100,
            mutation_rate=0.01,
            crossover_rate=0.7,
            precision=3,

In [4]:

Copied!





from functools import partial

# Torneo de tamaño 5, tipo proporcional, con reemplazo
tournament = partial(selection.tournament, K=5, type='proportional', replace=True)

selection_operators = [
    selection.uniform,
    selection.roulette,
    selection.stochastic_universal_sampling,
    selection.rank,
    tournament
]

results = []

np.random.seed(42)

for function in track(targets, description="Processing functions..."):
    fitness_function = Function(function, reverse=False)
    encoder = encoding.Binary(precision=3, bounds=fitness_function.bounds)
    for elitism in [None, 0.1, 0.3, 1.0]:
        for selection_ in [selection.uniform, selection.roulette, selection.stochastic_universal_sampling, selection.rank, selection.tournament]:
            aux_results = []
            aux_best_individual = []
            for _ in range(10):  # 10 runs per configuration
                ga = GeneticAlgorithm(
                    fitness_function=fitness_function,
                    crossover_function=crossover.onepoint,
                    mutation_function=mutation.flip_bit,
                    selection_function=selection_,
                    population_size=100,
                    mutation_rate=0.01,
                    crossover_rate=0.7,
                    encoder=encoder,
                    elitism=elitism,
                    minimize=True
                )
                ga.run(generations=100, verbose=False)
                aux_results.append(ga.best_fitness)
                aux_best_individual.append(ga.best_individual)
            mean_best_fitness = sum(aux_results) / len(aux_results)
            best_individual = np.min(np.array(aux_best_individual), axis=0)
            result = {
                "func": function,
                "elitism": elitism,
                "selection": selection_.__name__,
                "best_fitness_mean": mean_best_fitness,
                "best_individual": best_individual
            }
            results.append(result)
from functools import partial

# Torneo de tamaño 5, tipo proporcional, con reemplazo
tournament = partial(selection.tournament, K=5, type='proportional', replace=True)

selection_operators = [
    selection.uniform,
    selection.roulette,
    selection.stochastic_universal_sampling,
    selection.rank,
    tournament
]

results = []

np.random.seed(42)

for function in track(targets, description="Processing functions..."):
    fitness_function = Function(function, reverse=False)
    encoder = encoding.Binary(precision=3, bounds=fitness_function.bounds)
    for elitism in [None, 0.1, 0.3, 1.0]:
        for selection_ in [selection.uniform, selection.roulette, selection.stochastic_universal_sampling, selection.rank, selection.tournament]:
            aux_results = []
            aux_best_individual = []
            for _ in range(10):  # 10 runs per configuration
                ga = GeneticAlgorithm(
                    fitness_function=fitness_function,
                    crossover_function=crossover.onepoint,
                    mutation_function=mutation.flip_bit,
                    selection_function=selection_,
                    population_size=100,
                    mutation_rate=0.01,
                    crossover_rate=0.7,
                    encoder=encoder,
                    elitism=elitism,
                    minimize=True
                )
                ga.run(generations=100, verbose=False)
                aux_results.append(ga.best_fitness)
                aux_best_individual.append(ga.best_individual)
            mean_best_fitness = sum(aux_results) / len(aux_results)
            best_individual = np.min(np.array(aux_best_individual), axis=0)
            result = {
                "func": function,
                "elitism": elitism,
                "selection": selection_.__name__,
                "best_fitness_mean": mean_best_fitness,
                "best_individual": best_individual
            }
            results.append(result)

Output()

Resultados¶

Juntemos todos los resultados en una tabla para facilitar la comparación.

In [5]:

Copied!





df = pd.DataFrame(results)
df['best_fitness_mean'] = df['best_fitness_mean'].round(5)
df['best_individual'] = df['best_individual'].apply(lambda x: str([round(i, 5) for i in x]) if isinstance(x, list) else x)
df['elitism'] = df['elitism'].fillna(0).astype(str)
df = pd.DataFrame(results)
df['best_fitness_mean'] = df['best_fitness_mean'].round(5)
df['best_individual'] = df['best_individual'].apply(lambda x: str([round(i, 5) for i in x]) if isinstance(x, list) else x)
df['elitism'] = df['elitism'].fillna(0).astype(str)

In [6]:

Copied!

df
df

Out[6]:

	func	elitism	selection	best_fitness_mean	best_individual
0	Rastrigin	0.0	uniform	28.02633	[-3.8524226332173592, -1.1241311115180372]
1	Rastrigin	0.0	roulette	1.67473	[-2.001684673136788, -1.9841836049563573]
2	Rastrigin	0.0	stochastic_universal_sampling	1.18913	[-1.0009985961057195, -1.0003735579564186]
3	Rastrigin	0.0	rank	0.40321	[-0.0034377098211564316, -0.005312824269059213]
4	Rastrigin	0.0	tournament	0.67447	[-0.9897479094182993, -1.0403759995116895]
5	Rastrigin	0.1	uniform	0.23599	[-0.02531404504669421, -1.0003735579564186]
6	Rastrigin	0.1	roulette	0.44115	[-0.9922480620155039, -0.00031251907465090767]
7	Rastrigin	0.1	stochastic_universal_sampling	0.33942	[-0.9953732527620094, -0.9953732527620094]
8	Rastrigin	0.1	rank	0.46986	[-0.9953732527620094, -0.9947482146127085]
9	Rastrigin	0.1	tournament	0.67228	[-0.00031251907465090767, -0.9947482146127085]
10	Rastrigin	0.3	uniform	0.26449	[-0.9947482146127085, -0.9953732527620094]
11	Rastrigin	0.3	roulette	0.34686	[-0.9597460782518468, -0.010938167612769334]
12	Rastrigin	0.3	stochastic_universal_sampling	0.27787	[-0.04031496062992179, -0.010313129463468407]
13	Rastrigin	0.3	rank	0.15794	[-0.015938472807178528, -0.015313434657876712]
14	Rastrigin	0.3	tournament	0.35325	[-1.0003735579564186, -1.0003735579564186]
15	Rastrigin	1.0	uniform	4.28441	[-1.9773081853140453, -0.9841225660745891]
16	Rastrigin	1.0	roulette	5.64048	[-2.101690777024965, -2.035436733199048]
17	Rastrigin	1.0	stochastic_universal_sampling	5.82186	[-1.1135054629799184, -2.1860709271806145]
18	Rastrigin	1.0	rank	5.86880	[-2.0210608557651226, -2.0048098638832936]
19	Rastrigin	1.0	tournament	5.76165	[-1.996059329793078, -2.0754391747543184]
20	Ackley	0.0	uniform	7.83876	[-1.8461209790636635, -4.418299456753952]
21	Ackley	0.0	roulette	0.08564	[-0.09308429469572133, -0.00518830495025302]
22	Ackley	0.0	stochastic_universal_sampling	0.16966	[-0.024720747115912545, -0.15656473173411456]
23	Ackley	0.0	rank	0.10201	[-0.09308429469572133, -0.019837636574497886]
24	Ackley	0.0	tournament	0.06294	[-0.07843496307147646, -0.00518830495025302]
25	Ackley	0.1	uniform	0.03630	[-0.0015259720441918034, -0.003967527314899577]
26	Ackley	0.1	roulette	0.01176	[-0.005798693767929741, -0.0003051944088383607]
27	Ackley	0.1	stochastic_universal_sampling	0.00288	[-0.0027467496795461344, -0.0003051944088383607]
28	Ackley	0.1	rank	0.02190	[-0.0015259720441918034, -0.01129219312702201]
29	Ackley	0.1	tournament	0.09156	[-0.04303241164621863, -0.07843496307147646]
30	Ackley	0.3	uniform	0.01301	[-0.011902581944698731, -0.0009155832265150821]
31	Ackley	0.3	roulette	0.01608	[-0.020448025392174607, -0.0003051944088383607]
32	Ackley	0.3	stochastic_universal_sampling	0.01751	[-0.00518830495025302, -0.006409082585607351]
33	Ackley	0.3	rank	0.08056	[-0.00518830495025302, -0.07843496307147646]
34	Ackley	0.3	tournament	0.08064	[-0.020448025392174607, -0.04669474455227984]
35	Ackley	1.0	uniform	2.66572	[-1.1533296710004275, -0.8481352621619971]
36	Ackley	1.0	roulette	2.12939	[-1.0031740218519198, -0.15534395409876112]
37	Ackley	1.0	stochastic_universal_sampling	2.68577	[-0.9140572544710981, -1.1447842275529512]
38	Ackley	1.0	rank	2.65859	[-0.7449795519746081, -1.1478361716413357]
39	Ackley	1.0	tournament	2.45682	[-0.23835683330281388, -0.42513581151193325]
40	Sphere	0.0	uniform	9.45913	[-1.9666825367759264, -4.138690105597266]
41	Sphere	0.0	roulette	0.12805	[-0.3903363242385396, -0.08094244033449272]
42	Sphere	0.0	stochastic_universal_sampling	0.01929	[-0.3203320515168162, -0.09531831776841848]
43	Sphere	0.0	rank	0.00348	[-0.02156381615088776, -0.04031496062992179]
44	Sphere	0.0	tournament	0.00053	[-0.04031496062992179, -0.00031251907465090767]
45	Sphere	0.1	uniform	0.00001	[-0.00031251907465090767, -0.001562595373252762]
46	Sphere	0.1	roulette	0.00069	[-0.08031740218519268, -0.00031251907465090767]
47	Sphere	0.1	stochastic_universal_sampling	0.00068	[-0.010313129463468407, -0.00031251907465090767]
48	Sphere	0.1	rank	0.00033	[-0.020313739852285906, -0.005312824269059213]
49	Sphere	0.1	tournament	0.00028	[-0.02906427394250155, -0.001562595373252762]
50	Sphere	0.3	uniform	0.00090	[-0.04093999877922183, -0.015313434657876712]
51	Sphere	0.3	roulette	0.00018	[-0.041565036928523647, -0.0028126716718546163]
52	Sphere	0.3	stochastic_universal_sampling	0.00011	[-0.02156381615088776, -0.00031251907465090767]
53	Sphere	0.3	rank	0.00020	[-0.011563205762070261, -0.04031496062992179]
54	Sphere	0.3	tournament	0.00026	[-0.0028126716718546163, -0.005312824269059213]
55	Sphere	1.0	uniform	0.20793	[-0.5309699078312882, -0.7209815052188251]
56	Sphere	1.0	roulette	0.24257	[-0.505968381859244, -0.5690972349386563]
57	Sphere	1.0	stochastic_universal_sampling	0.40132	[-0.30845632668009504, -0.7209815052188251]
58	Sphere	1.0	rank	0.28634	[-0.6991051699932855, -0.6784789110663496]
59	Sphere	1.0	tournament	0.28168	[-0.5159689922480624, -0.6053494475981198]

In [7]:

Copied!





# Grafiquemos 
fig = px.bar(df, x='func', y='best_fitness_mean', color='selection', barmode='group',
             facet_col='elitism', title='Best Fitness Mean by Function, Selection Operator, and Elitism',
             labels={'best_fitness_mean': 'Best Fitness Mean', 'func': 'Function', 'selection': 'Selection Operator', 'elitism': 'Elitism'})
fig.update_layout(height=300, width=1200)
fig.show()
# Grafiquemos 
fig = px.bar(df, x='func', y='best_fitness_mean', color='selection', barmode='group',
             facet_col='elitism', title='Best Fitness Mean by Function, Selection Operator, and Elitism',
             labels={'best_fitness_mean': 'Best Fitness Mean', 'func': 'Function', 'selection': 'Selection Operator', 'elitism': 'Elitism'})
fig.update_layout(height=300, width=1200)
fig.show()

No description has been provided for this image

Algunas observaciones interesantes:

La selección uniforme (aleatoria) tiende a tener un desempeño significativamente peor en comparación con los otros métodos de selección.
El elitismo mejora consistentemente el desempeño de todos los métodos de selección, pero su impacto es mayor en la selección por torneo y ruleta.
El elitismo total es la peor estrategia, probablemente porque reduce la diversidad de la población. Mientras que nada de elitismo es mejor que elitismo total, un elitismo moderado (10-30%) parece ofrecer un buen equilibrio entre preservar los mejores individuos y mantener la diversidad genética.

Exploremos las configuraciones de Selección por Torneo¶

In [8]:

Copied!





# Experimento adicional: variar K, reemplazo y tipo de torneo

tournament_results = []

np.random.seed(42)

Ks = [2, 3, 5, 10]
replacements = [True, False]
tournament_types = ['standard','proportional']  
elitism_values = [None, 0.1, 0.3, 1.0]

fitness_fn = Function('Ackley', reverse=False)

for K in track(Ks):
    for replace in replacements:
        for t_type in tournament_types:
            tournament_operator = partial(selection.tournament, K=K, type=t_type, replace=replace)
            for elitism in elitism_values:
                run_best_fitness = []
                run_best_individuals = []
                for _ in range(10):
                    ga = GeneticAlgorithm(
                        fitness_function=fitness_fn,
                        crossover_function=crossover.onepoint,
                        mutation_function=mutation.flip_bit,
                        selection_function=tournament_operator,
                        population_size=100,
                        mutation_rate=0.01,
                        crossover_rate=0.7,
                        encoder=encoder,
                        elitism=elitism,
                        minimize=True
                    )
                    ga.run(generations=100, verbose=False)
                    run_best_fitness.append(ga.best_fitness)
                    run_best_individuals.append(ga.best_individual)
                mean_fit = float(np.mean(run_best_fitness))
                idx_min = int(np.argmin(run_best_fitness))
                best_individual = run_best_individuals[idx_min]
                tournament_results.append({
                    "K": K,
                    "replace": replace,
                    "type": t_type,
                    "elitism": elitism,
                    "best_fitness_mean": mean_fit,
                    "best_individual": best_individual
                })
# Experimento adicional: variar K, reemplazo y tipo de torneo

tournament_results = []

np.random.seed(42)

Ks = [2, 3, 5, 10]
replacements = [True, False]
tournament_types = ['standard','proportional']  
elitism_values = [None, 0.1, 0.3, 1.0]

fitness_fn = Function('Ackley', reverse=False)

for K in track(Ks):
    for replace in replacements:
        for t_type in tournament_types:
            tournament_operator = partial(selection.tournament, K=K, type=t_type, replace=replace)
            for elitism in elitism_values:
                run_best_fitness = []
                run_best_individuals = []
                for _ in range(10):
                    ga = GeneticAlgorithm(
                        fitness_function=fitness_fn,
                        crossover_function=crossover.onepoint,
                        mutation_function=mutation.flip_bit,
                        selection_function=tournament_operator,
                        population_size=100,
                        mutation_rate=0.01,
                        crossover_rate=0.7,
                        encoder=encoder,
                        elitism=elitism,
                        minimize=True
                    )
                    ga.run(generations=100, verbose=False)
                    run_best_fitness.append(ga.best_fitness)
                    run_best_individuals.append(ga.best_individual)
                mean_fit = float(np.mean(run_best_fitness))
                idx_min = int(np.argmin(run_best_fitness))
                best_individual = run_best_individuals[idx_min]
                tournament_results.append({
                    "K": K,
                    "replace": replace,
                    "type": t_type,
                    "elitism": elitism,
                    "best_fitness_mean": mean_fit,
                    "best_individual": best_individual
                })

Output()

In [9]:

Copied!





tournament_df = pd.DataFrame(tournament_results)
tournament_df['elitism'] = tournament_df['elitism'].fillna(0).astype(str)
tournament_df['K'] = tournament_df['K'].astype(str)
tournament_df['best_fitness_mean'] = tournament_df['best_fitness_mean'].round(6)
tournament_df['best_individual'] = tournament_df['best_individual'].apply(
lambda x: str([round(float(v), 6) for v in x])
)

tournament_df = tournament_df.sort_values(by=["best_fitness_mean"]).reset_index(drop=True)
tournament_df
tournament_df = pd.DataFrame(tournament_results)
tournament_df['elitism'] = tournament_df['elitism'].fillna(0).astype(str)
tournament_df['K'] = tournament_df['K'].astype(str)
tournament_df['best_fitness_mean'] = tournament_df['best_fitness_mean'].round(6)
tournament_df['best_individual'] = tournament_df['best_individual'].apply(
lambda x: str([round(float(v), 6) for v in x])
)

tournament_df = tournament_df.sort_values(by=["best_fitness_mean"]).reset_index(drop=True)
tournament_df

Out[9]:

	K	replace	type	elitism	best_fitness_mean	best_individual
0	10	True	proportional	0.1	0.006836	[0.000313, 0.000313]
1	3	True	proportional	0.3	0.011534	[0.000313, 0.000313]
2	10	False	proportional	0.1	0.013504	[-0.000313, 0.000313]
3	5	True	proportional	0.1	0.017359	[-0.000313, -0.000313]
4	2	False	proportional	0.3	0.018458	[0.000313, -0.000313]
...	...	...	...	...	...	...
59	3	True	proportional	1.0	2.952478	[0.1972, 0.20095]
60	2	True	standard	1.0	2.956673	[0.027814, 0.158447]
61	3	True	standard	1.0	3.017606	[-0.314082, 0.059066]
62	5	True	standard	1.0	3.053137	[-0.04219, 0.321582]
63	2	True	proportional	1.0	3.246167	[-0.012813, 0.155947]

64 rows × 6 columns

In [10]:

Copied!





# Grafiquemos
fig2 = px.bar(tournament_df, x='K', y='best_fitness_mean', color='type', barmode='group',
             facet_col='elitism', facet_row='replace',
             title='Best Fitness Mean by Tournament Parameters and Elitism for Ackley',
             labels={'best_fitness_mean': 'Best Fitness Mean', 'K': 'K (Tournament)', 'type': 'Type', 'elitism': 'Elitism', 'replace': 'Replacement'})
fig2.update_layout(height=600, width=1000)
fig2.show()
# Grafiquemos
fig2 = px.bar(tournament_df, x='K', y='best_fitness_mean', color='type', barmode='group',
             facet_col='elitism', facet_row='replace',
             title='Best Fitness Mean by Tournament Parameters and Elitism for Ackley',
             labels={'best_fitness_mean': 'Best Fitness Mean', 'K': 'K (Tournament)', 'type': 'Type', 'elitism': 'Elitism', 'replace': 'Replacement'})
fig2.update_layout(height=600, width=1000)
fig2.show()

Igual aquí podemos observar que el tamaño del torneo (K) tiene un impacto significativo en el desempeño cuando no se utiliza elitismo y sobre todo cuando el tipo de torneo es proporcional.
Seguimos observando que el elitismo entre el 10-30% ofrece un buen desempeño.
Cuando no hay elitismo, el torneo proporcional tiene un desempeño menor. Esto podría ser debido a que el torneo proporcional introduce más aleatoriedad en la selección, lo que puede ser perjudicial cuando no se preservan los mejores individuos.
Usar remplazo parece tener un impacto pequeño en el desempeño, pero mejor que no usarlo.

Mejores parámetros y Análisis¶

De acuerdo con los resultados agrupados y ordenados por best_fitness_mean, la mejor combinación corresponde a los operadores de selección como torneo o rank junto con un elitismo de entre 0.1 y 0.3.

Esto tiene sentido gracias a que los operadores como torneo y rank ejercen mayor presión en la selección de la población, favoreciendo la supervivencia de los mejores individuos (como en la naturaleza). Esto ayuda a mantener la calidad de la población (con los mejores individuos) a lo largo de las generaciones.

Por otro lado, el elitismo entre 0.1 y 0.3 asegura que los mejores individuos no se pierdan, lo que ayuda a preservar soluciones de alta calidad a lo largo de las generaciones. Por otro lado, si el elitismo es muy alto (1.0) se pierde diversidad y la población se estanca rápidamente, lo que se traduce en perder capacidad de exploración.

Criterios¶

Criterio	W	Esperado	Done
1. Implementación de operadores de selección (Ruleta, SUS, Torneo)	20	Implementa los 3 operadores correctamente; documenta precisión de cada método; para Torneo especifica tipo, k, con/sin reemplazo y resolución de empates; Ruleta maneja aptitudes 0/negativas (normalización/shift) y SUS usa puntos equidistantes.	Torneo seleccionable, con y sin remplazo y resolución de empates.
2. Elitismo (tipo y parámetros)	20	Integra elitismo y declara explícitamente el tipo (mejor individuo / % mejores / total), el porcentaje/número, si saltan cruza/mutación, y el mecanismo de inserción en la siguiente generación; justifica su elección.	Elitismo con n% mejores como input.
3. Diseño experimental (control de variables + baseline)	15	Mantiene constantes población, generaciones, representación, fitness, cruza, mutación y tasas entre operadores; incluye baseline de Selección Aleatoria; detalla configuración.	En este reporte
5. Visualizaciones (consistencia y legibilidad)	15	Gráficas comparables, líneas de mejor y media, leyendas claras, títulos que incluyen operador y tipo de elitismo; figuras legibles.	En este reporte
6. Resultados y discusión	10	Identifica la mejor combinación (operador + elitismo) y razona causas (presión de selección, diversidad, estancamiento); discute trade-offs (velocidad vs. calidad), efectos de elitismo y del torneo; reconoce limitaciones.	En este reporte
7. Reproducibilidad (código)	10	Código limpio y modular; requisitos, comandos de ejecución, parámetros, es posible replicar todas las condiciones; estructura de carpetas clara.	En repositorio
8. Informe (PDF) claridad y estructura	10	Breve y claro: problema, AG (representación/fitness/cruza/mutación), operadores y tipo de torneo, elitismo (tipo y parámetros), setup experimental, resultados, gráficas y tabla resumen, conclusiones; redacción formal.	En este reporte