que es la programacion genetica
Diagrama de flujo.

¿Qué Es La Programación Genética?

La programación genética es una técnica de inteligencia artificial en la que se utilizan algoritmos evolutivos para generar automáticamente programas informáticos. Basándose en los principios de selección natural y genética, una población de programas se somete a operaciones como el cruce, la mutación y la selección para evolucionar y mejorar con el tiempo. Esta técnica es parte de la “computación evolutiva”, una rama de la inteligencia artificial que utiliza algoritmos basados en la evolución natural para resolver una amplia gama de problemas. Su importancia radica en su capacidad para resolver problemas de alta complejidad y para explorar soluciones que podrían no ser inmediatamente evidentes para los humanos.

El objetivo final de la programación genética es generar automáticamente programas que puedan resolver un problema en concreto. Esto se logra evaluando un conjunto de programas generados previamente para determinar cuál o cuáles son los más adecuados para la resolución del problema. La selección se utiliza para crear la próxima generación de programas, que también se evaluarán y seleccionarán si es pertinente, repitiendo el proceso tantas veces como sea necesario. La programación genética se puede utilizar para generar programas basados en lenguajes como Java o Python, y la complejidad de estos dependerá de la complejidad del problema y de las restricciones presentes en el espacio de producción.

¿Cómo Funciona La Programación Genética?

La programación genética implica el uso de un conjunto de operaciones genéticas para hacer evolucionar una población de programas a lo largo del tiempo. Los principales pasos en el proceso son:

1. Inicialización

Se genera e inicializa -de manera aleatoria- un conjunto (o población) de programas denominados “cromosomas” – término tomado de la biología que aquí se refiere a una entidad que porta información para resolver el problema. Estos cromosomas se representan de diversas formas como estructuras de árbol, cadenas carbonadas o redes.

2. Evaluación

Cada programa que compone la población se evalúa, con el fin de determinar si es idóneo para la resolución de la tarea o problema planteado. Esta evaluación se realiza de múltiples formas; si por ejemplo el objetivo es optimizar el rendimiento de un algoritmo de aprendizaje automático, se evaluará en base a la precisión de las predicciones expuestas por dicho algoritmo.

3. Selección

Los programas más válidos para la función requerida se seleccionan según el puntuaje obtenido en la fase de evaluación. Hay una variedad de formas de optimizar este proceso:

  • Seleccionando aleatoriamente los programas y eligiendo el más apto.
  • Estableciendo la probabilidad de que sea seleccionado mediante la puntuación obtenida en la evaluación.

4. Gestión & Manipulación

Los programas seleccionados se someten a procesos de cruce, mutación y reproducción para crear una nueva generación de programas. Los procesos consisten en lo siguiente:

  1. En el cruce, se toman dos programas y se combinan para crear uno nuevo.
  2. En la mutación se realizan cambios en el código del programa, generalmente mediante la alteración de valores.
  3. En la reproducción, se utilizan los programas más aptos para generar los programas de la nueva generación.

Estas operaciones genéticas permiten la introducción de nuevas ideas y soluciones en la población, manteniendo al mismo tiempo un cierto grado de diversidad.

Además, para que la población no se vuelva excesivamente homogénea -es decir, que sea diversa- se hace uso de las siguientes técnicas:

  • Elitismo: donde solamente se preservan los programas más aptos de la población.
  • Preservación de nichos: donde se mantiene -de manera forzada y no siempre conveniente- la diversidad entre el conjunto de programas.

5. Repetición

El proceso se repite continuamente hasta encontrar una solución satisfactoria o alcanzar el número de iteraciones deseado. A través de la repetición, la población evolucionará y mejorará progresivamente.

Ejemplo Reproducible Con Python

El siguiente código configura y ejecuta una evolución genética, intentando encontrar una ecuación que se evalúe al número objetivo. Utiliza operaciones matemáticas básicas y constantes aleatorias, evolucionando la población durante 40 generaciones con una población inicial de 300 individuos.

Cada individuo es una ecuación, y se seleccionan y combinan según su aptitud, que se mide por la diferencia entre el valor evaluado de la ecuación y el número objetivo. Las ecuaciones que estén más cerca del objetivo serán más aptas.

# Instalamos DEAP
# https://deap.readthedocs.io/en/master/
# En caso de no usar notebooks, eliminar '!'
!pip install deap

import operator
import math
import random
import numpy

from deap import algorithms
from deap import base
from deap import creator
from deap import tools
from deap import gp
def protectedDiv(left, right):
    """
    Función que realiza una división segura.
    Inputs:
        - left: Dividendo (float).
        - right: Divisor (float).
    Output:
        - Resultado de la división, o 1 si el divisor es 0 (float).
    """
    try:
        return left / right
    except ZeroDivisionError:
        return 1
# Definimos un conjunto primitivo de operaciones que se pueden usar para construir la ecuación.
pset = gp.PrimitiveSet("MAIN", 1)
pset.addPrimitive(operator.add, 2)
pset.addPrimitive(operator.sub, 2)
pset.addPrimitive(operator.mul, 2)
pset.addPrimitive(protectedDiv, 2)
pset.addPrimitive(operator.neg, 1)
pset.addPrimitive(math.cos, 1)
pset.addPrimitive(math.sin, 1)
pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))
pset.renameArguments(ARG0='x')

# Definimos el tipo de individuo y la función de fitness.
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("compile", gp.compile, pset=pset)
def evalSymbReg(individual, points):
    """
    Función que evalúa el error cuadrado medio entre la ecuación y el objetivo.
    Inputs:
        - individual: árbol de operaciones y terminales que representa la ecuación (deap.gp.PrimitiveTree).
        - points:lLista de puntos en los que evaluar la ecuación (list).
    Output:
        - Error cuadrado medio entre la ecuación y el objetivo (tuple).
    """
    func = toolbox.compile(expr=individual)
    sqerrors = ((func(x) - target)**2 for x in points)
    return math.fsum(sqerrors) / len(points),
toolbox.register("evaluate", evalSymbReg, points=[x/10. for x in range(-10,10)])
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("mate", gp.cxOnePoint)
toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
toolbox.register("mutate", gp.mutUniform, expr=toolbox.expr_mut, pset=pset)

toolbox.decorate("mate", gp.staticLimit(key=operator.attrgetter("height"), max_value=17))
toolbox.decorate("mutate", gp.staticLimit(key=operator.attrgetter("height"), max_value=17))
def main():
    """
    Función principal que configura y ejecuta la evolución genética.
    Inputs: Ninguno.
    Outputs: 
        - Población final después de la evolución (list).
        - Logbook con estadísticas de la evolución (deap.tools.Logbook).
        - Mejor individuo encontrado en la evolución (deap.tools.HallOfFame).
    """
    random.seed(318)

    pop = toolbox.population(n=300)
    hof = tools.HallOfFame(1)

    stats_fit = tools.Statistics(lambda ind: ind.fitness.values)
    stats_size = tools.Statistics(len)
    mstats = tools.MultiStatistics(fitness=stats_fit, size=stats_size)
    
    mstats.register("avg", numpy.mean)
    mstats.register("std", numpy.std)
    mstats.register("min", numpy.min)
    mstats.register("max", numpy.max)

    pop, log = algorithms.eaSimple(pop, toolbox, 0.5, 0.1, 40, stats=mstats,
                                   halloffame=hof, verbose=True)

    print("El mejor individuo es: ", hof[0], hof[0].fitness.values)
    
    return pop, log, hof
target = 42
if __name__ == "__main__":
    main()

# Obtendremos una tabla similar a la siguiente:

----------------------------------------------------------------------------------------------------------------------------------------------

   	      	                    fitness                    	                      size                     
   	      	-----------------------------------------------	-----------------------------------------------
gen	nevals	avg    	gen	max 	min    	nevals	std    	avg    	gen	max	min	nevals	std    
0  	300   	1751.25	0  	1936	1594.46	300   	56.7527	3.54667	0  	7  	2  	300   	1.49482
1  	151   	1724.43	1  	2679.15	1596.34	151   	74.9067	3.72   	1  	12 	1  	151   	1.74974
2  	155   	1700.09	2  	1923.09	1600   	155   	48.1738	4.07333	2  	14 	1  	155   	1.91519
3  	170   	1697.96	3  	1936   	1600   	170   	56.0824	4.67   	3  	14 	1  	170   	2.17894
4  	159   	1684.61	4  	2256   	1600   	159   	63.7234	5.40667	4  	14 	1  	159   	2.46061
5  	159   	1671.12	5  	1923.09	1521   	159   	65.2714	6.05   	5  	17 	1  	159   	2.57698
6  	159   	1657.31	6  	1936   	1521   	159   	69.2923	5.98   	6  	16 	1  	159   	2.59736
7  	182   	1645.17	7  	1927.27	1521   	182   	72.2271	6.30333	7  	16 	1  	182   	2.73581
8  	156   	1626.26	8  	1936   	1521   	156   	67.0837	6.77667	8  	17 	3  	156   	2.9978 
9  	158   	1612.29	9  	1849   	1444   	158   	77.0652	7.31333	9  	19 	1  	158   	3.40125
10 	168   	1602.53	10 	1849   	1444   	168   	83.9299	7.93333	10 	23 	1  	168   	3.52073
11 	147   	1577.26	11 	1849   	1444   	147   	85.3056	8.89667	11 	24 	1  	147   	3.63492
12 	179   	1561.35	12 	2025   	1444   	179   	83.6129	9.93667	12 	29 	1  	179   	4.20943
13 	158   	1547.25	13 	2007.8 	1369   	158   	92.5802	10.8   	13 	25 	1  	158   	4.10934
14 	162   	1531.19	14 	1919.74	1296   	162   	93.8127	12.0567	14 	31 	1  	162   	4.80695
15 	171   	1522.36	15 	1911.74	1296   	171   	103.859	13.3067	15 	31 	1  	171   	5.21657
16 	168   	1495.77	16 	1995.05	1240.1 	168   	106.414	14.2267	16 	31 	3  	168   	5.19891
17 	172   	1476.41	17 	1936   	1225   	172   	124.85 	14.7133	17 	34 	3  	172   	5.81875
18 	173   	1465.61	18 	8116.24	1202.5 	173   	403.261	16.3233	18 	38 	3  	173   	6.19452
19 	158   	1417.19	19 	1936   	1152.05	158   	136.734	18.4533	19 	38 	1  	158   	6.37347
20 	151   	1375.1 	20 	2414.4 	1089   	151   	144.448	20.79  	20 	37 	3  	151   	6.06404
21 	144   	1322.16	21 	1849   	979.271	144   	130.712	23.2833	21 	41 	1  	144   	5.78069
22 	180   	1321.08	22 	5576.86	964.228	180   	291.249	25.0067	22 	58 	7  	180   	6.38905
23 	153   	1276.54	23 	5019.51	964.228	153   	266.514	25.4933	23 	60 	1  	153   	7.44782
24 	185   	1256.48	24 	2291.18	741.791	185   	198.644	26.4433	24 	56 	5  	185   	8.14863
25 	158   	1225.99	25 	8389.61	625.957	158   	528.746	29.3233	25 	60 	2  	158   	9.00401
26 	170   	1144.14	26 	7325.71	625.957	170   	506.571	32.86  	26 	64 	7  	170   	9.39044
27 	166   	196593 	27 	5.86625e+07	625.957	166   	3.38117e+06	38.4   	27 	66 	7  	166   	11.2425
28 	180   	969.483	28 	2728.31    	532.604	180   	268        	44.38  	28 	88 	5  	180   	13.726 
29 	195   	1021.01	29 	21436.6    	488.879	195   	1267.11    	50.6367	29 	99 	1  	195   	15.3175
30 	159   	882.293	30 	9324.81    	462.66 	159   	689.491    	56.22  	30 	106	1  	159   	13.9921
31 	157   	9247.49	31 	2.52795e+06	197.926	157   	145666     	61.4233	31 	121	5  	157   	12.9344
32 	163   	110714 	32 	3.29977e+07	181.099	163   	1.9019e+06 	64.2967	32 	124	2  	163   	13.2122
33 	159   	110666 	33 	3.29959e+07	181.099	159   	1.9018e+06 	68.0733	33 	115	25 	159   	13.8661
34 	175   	441028 	34 	1.32133e+08	100.515	175   	7.61593e+06	73.2533	34 	121	7  	175   	15.8769
35 	164   	556.172	35 	15133.2    	100.515	164   	872.803    	80.6867	35 	166	7  	164   	19.1778
36 	165   	828.686	36 	52762      	67.4395	165   	3548.68    	87.83  	36 	166	10 	165   	21.0679
37 	172   	659.891	37 	31101.7    	1.11459	172   	2240.55    	93.5233	37 	171	7  	172   	24.7109
38 	160   	442.732	38 	15133.2    	1.11459	160   	1373.84    	102.887	38 	184	12 	160   	22.455 
39 	153   	427.455	39 	58297.3    	0.345872	153   	3356.41    	104.037	39 	198	2  	153   	25.0747
40 	185   	482.955	40 	47731.2    	0.345872	185   	3732.89    	107.507	40 	198	8  	185   	25.9003

En la tabla generada, se observa en la columna ‘fitness’ que tanto el promedio como los valores mínimos y máximos de fitness disminuyen con el tiempo, lo cual es una señal positiva. Esto significa que el algoritmo está encontrando soluciones que están cada vez más cerca del objetivo (en este caso, una función que evalúa a 42). En particular, el valor mínimo de fitness es la métrica más importante en este caso, ya que representa la mejor solución (es decir, la más cercana a 42) que el algoritmo ha encontrado hasta ahora. En la generación 40, vemos que el valor mínimo de fitness es extremadamente cercano a cero, lo que indica que el algoritmo encontró una solución muy precisa.

En la columna ‘size’, vemos que el tamaño medio de los individuos (que en este contexto representa la complejidad de las soluciones) aumenta constantemente a lo largo de las generaciones. Esto da a entender que, aunque el algoritmo está encontrando soluciones cada vez mejores, estas soluciones se están volviendo más complejas. En la generación 40, el tamaño promedio es de alrededor de 107, con un tamaño máximo de 198.

Este aumento en la complejidad podría ser un problema si estuviéramos buscando soluciones simples y ‘elegantes’ al problema. Aún así, se ha de tener en cuenta que es una característica común de los algoritmos genéticos que pueden generar soluciones cada vez más complejas a medida que se esfuerzan por encontrar la mejor solución posible.

Ver también

Por último, obtenemos la siguiente combinación de operaciones matemáticas y constantes que se seleccionaron y organizaron a través de la programación genética:

El mejor individuo es: add(sub(sub(sub(sub(protectedDiv(1, add(sub(-1, sub(neg(-1), sub(-1, 1))), add(sub(-1, 1), -1))), add(-1, -1)), sub(-1, 1)), -1), sub(-1, sub(sub(sub(sub(sub(sub(sub(sub(sub(sub(protectedDiv(1, protectedDiv(0, 0)), add(-1, -1)), sub(-1, 1)), add(-1, -1)), add(-1, -1)), sub(-1, 1)), add(-1, -1)), sub(-1, sub(sub(protectedDiv(cos(-1), 0), add(-1, -1)), sub(-1, mul(x, 1))))), sub(-1, 1)), add(-1, 1)), sub(-1, sub(protectedDiv(sub(1, sub(-1, sub(neg(-1), sub(-1, 1)))), sub(1, cos(sin(1)))), sin(neg(add(-1, -1)))))))), protectedDiv(neg(neg(x)), x)) (0.3458723538739451,)

La última parte (0.3458723538739451,) es el valor de fitness de ese mejor individuo, el cual no produce exactamente el número 42, pero tiene el menor error cuadrado medio entre todos los individuos de la población. Esto podría mejorarse aumentando el tamaño de la población, ejecutando el algoritmo durante más generaciones, y/o ajustando las tasas de cruce y mutación.

Aplicaciones Destacables De La Programación Genética

  1. Aprendizaje automatico y el reconocimiento de patrones: la programación genética puede ser utilizada para mejorar los algoritmos de aprendizaje automático, permitiendo a los sistemas aprender y adaptarse de manera más eficiente.
  2. Finanzas, cadenas de montaje y optimización de estrategias comerciales: la programación genética se ha utilizado para desarrollar algoritmos de trading que pueden adaptarse y evolucionar con las condiciones cambiantes del mercado. Un caso notable es el desarrollo de sistemas de trading de alta frecuencia que se ajustan en tiempo real a las fluctuaciones del mercado.
  3. Biología y el descubrimiento de nuevos medicamentos: la programación genética permite la simulación de procesos biológicos y puede ayudar a descubrir nuevos medicamentos al permitir una búsqueda más efectiva en el espacio de posibles soluciones. Un ejemplo de esto es la optimización de la estructura de nuevos fármacos para maximizar su eficacia y minimizar los efectos secundarios.
  4. Diseños de motores aeronaúticos: algunas empresas han utilizado la programación genética para mejorar el diseño y la eficiencia de los motores aeronáuticos.

Ventajas & Desventajas De La Programación Genética

La programación genética tiene numerosas ventajas, que incluyen:

  • Posibilidad de dar soluciones a problemas complicados -o incluso imposibles- de resolver por humanos, gracias a la exploración de un amplio número de posibles soluciones las cuales un individuo cualquiera podría no haber considerado.
  • Flexibilidad y posibilidad de aplicación en un amplio rango de problemas, además de permitir su combinación con técnicas de machine learning y algoritmos de optimización para mejorar la precisión de los resultados.
  • Es un proceso altamente automatizado que rara vez requiere intervención manual.

Respecto a las desventajas, debemos tener en cuenta las siguientes dos:

  • El proceso puede requerir de mucho tiempo, además de consumir recursos computacionales significativos.
  • Posible dificultad de comprensión e interpretación de las soluciones propuestas por la programación genética. Esto puede crear problemas, especialmente en términos de explicabilidad y transparencia.

El Futuro De La Programación Genética

La mejora continua de las capacidades de hardware y software, junto con las investigaciones emergentes en inteligencia artificial, están abriendo nuevas vías para el desarrollo y la aplicación de la programación genética:

  • Avances Tecnológicos: los avances en la capacidad de procesamiento de los ordenadores permitirán la ejecución de algoritmos genéticos a una velocidad y escala nunca antes vistas. La posibilidad de llevar a cabo evaluaciones más rápidas y de manipular poblaciones de programas mucho más grandes, permitirá a la programación genética abordar problemas de una complejidad y tamaño en constante crecimiento.
  • Nuevas Utilidades: veremos cómo la programación genética se aplica en nuevas áreas como la robótica, donde los robots podrán evolucionar sus propios programas para adaptarse a su entorno y aprender nuevas tareas. En el campo de la biología sintética, la programación genética podría ser utilizada para diseñar organismos genéticamente modificados con características específicas. Es probable que también haya una mayor integración de la programación genética con otras técnicas de inteligencia artificial, como las redes neuronales y el aprendizaje profundo. Esta sinergia podría dar lugar a sistemas de inteligencia artificial más potentes y versátiles.
  • Ética & Regulación: la transparencia y la interpretación de las soluciones propuestas por la programación genética seguirá siendo un tema importante, especialmente en contextos donde la toma de decisiones basada en IA debe ser justificada o explicada. Además, el uso de la programación genética en ciertas aplicaciones, como la biología sintética o la robótica, plantea cuestiones éticas y regulativas que deberán ser abordadas.

Conclusión

La programación genética es una excelente técnica en machine learning que utiliza algoritmos evolutivos para generar programas automáticamente. Siendo útil para la resolución de problemas y también descubrir nuevas soluciones y conocimientos en una gran variedad de campos. Aún así, es importante asegurarse de que la programación genética sea útil para la problemática que deseemos resolver, ya que puede haber métodos más apropiados para ello. Actualmente se continúa desarrollando y refinando las técnicas y enfoques utilizados en la programación genética, resultado un campo muy prometedor de cara al futuro.