09 - Algoritmos Evolutivos Flashcards
¿Qué son los algoritmos evolutivos? y los algoritmos genéticos?
-Se basan en los principios de la evoucion biologica.
-Se los conoce como métodos de optimizacion y busqueda de soluciones basados en los postulados de la evolucion biologica.
-Los algoritmos genéticos son un tipo particular de los algoritmos evolutivos con base en el principio de selección natural y supervivencia del mas apto.
Explicar que es la evolución biológica.
La evolución biológica es el proceso de cambio ocurrido a través de muchos siglos y milenios.
El principio de selección natural y supervivencia del más apto, planteado por charles Darwin en 1859, explica que pequeñas modificaciones heredadas refuerzan la aptitud de los individuos para vivir y reproducirse.
Ej. porque los osos polares son blancos?
¿Cuales son los elementos de un algoritmo genético computacional?
- Se necesita un población de individuos
-Los individuos están codificados a través de cromosomas constituidos por genes.
-Cada individuo es un vector de n elementos
-Cada elemento es un gen.
-El gen representa una característica del individuo.
-También hay una función de evaluación denominada fitness
¿Cómo es el funcionamiento de un algoritmo genético? cuales son las operaciones o operadores?
El funcionamiento tiene 3 pasos:
1 Inicialización
-Población inicial de individuos, todos codificados con un mismo cromosoma
-Durante cada ciclo se ejecutan las operaciones de selección, reproducción y mutación para dar origen a la siguiente generación.
2 Ciclos
Luego el algoritmo cicla dando origen a distintas generaciones.
3 Condición de fin
El final se puede alcanzar debido a que la función fitness alcanzo su máximo valor o porque se alcanzo una determinada cantidad de ciclos definidos previamente.
¿Cuál es la función del operador de selección?
Decide quienes son los individuos de la población que se apararean. Existen varias estrategias:
selección directa: es cuando se eligen a los mejores individuos (según la función fitness)
selección aleatoria: es cuando la elección es al azar, todos tienen igualdad de condición de ser elegidos.
¿Cuál es la función del Operador de reproducción o cruce?
Es el operador encargado de realizar el cruce de las cargas genéticas de los padres para dar origen a los hijos.
Generalmente, de una pareja de padres, salen dos hijos.
El fitness de los hijos puede resultar mayor, igual o menor que el de los padres.
¿Cuál es la función del Operador de mutación?
Es el encargado de realizar alguna mutación en la carga genética de los nuevos individuos.
Tiene una baja probabilidad de ocurrencia.
¿Que es la Estrategia destructiva o constructiva?
Al finalizar cada ciclo, debe definirse que individuos conformaran la nueva generación.
Se puede tomar una estrategia destructiva, que consiste en considerar solo los hijos que se han generado.
O una estrategia constructiva, dónde se evalúa padres e hijos por el fitness mas alto.
¿Qué hace la función fitness?
La función evalúa la bondad, ajuste o adaptación de cada individuo, es decir, define quién es el mejor individuo (al que elegirá para reproducir y heredar sus características a sus descendientes).
Dar un ejemplo real de aplicación de un algoritmo genético.
Un ejemplo concreto en el problema del viajante (TSP - Traveling Salesman Problem), un clásico de optimización.
Ejemplo: Optimización de la Ruta de un Viajante
Supongamos que un vendedor necesita visitar varias ciudades y regresar al punto de partida, minimizando la distancia total recorrida.
Cómo se aplica un Algoritmo Genético (AG)
Codificación de soluciones (Individuos)
Cada ruta posible se representa como un cromosoma, una secuencia de ciudades en un orden específico.
Ejemplo de cromosoma (ruta para 5 ciudades):
[A → C → B → E → D → A]
Función de aptitud (Fitness Function)
Se evalúa la calidad de cada ruta sumando las distancias entre ciudades. Cuanto menor sea la distancia total, mejor será la solución.
Selección de padres
Se eligen las mejores rutas de la población para reproducirse. Métodos comunes incluyen ruleta, torneo, o ranking.
Cruce (Crossover)
Se combinan dos rutas para generar nuevas soluciones. Un método típico es Order Crossover (OX), que mezcla partes de las rutas de los padres.
Ejemplo de cruce
Padre 1: [A → C → B → E → D → A]
Padre 2: [B → A → D → C → E → B]
Hijo: [A → C → D → B → E → A] (combinando segmentos de ambos padres).
Mutación
Se intercambian dos ciudades aleatoriamente para explorar nuevas soluciones y evitar quedarse en un óptimo local.
Ejemplo de mutación
[A → C → D → B → E → A] → [A → C → B → D → E → A] (intercambio de B y D).
Nueva generación
Se repite el proceso con nuevas soluciones, mejorando iterativamente la ruta hasta converger en una solución óptima o suficientemente buena.
Resultado Final
Después de varias generaciones, el AG encuentra una ruta cercana a la óptima con la menor distancia posible, optimizando el problema sin necesidad de evaluar todas las combinaciones posibles.
Este mismo enfoque se usa en problemas de logística, diseño de redes, programación de horarios y muchos otros escenarios de optimización.
