<aside> 📢 Suelen utilizarse en problemas de combinatorias, que se resuelven en tiempos exponenciales, en donde las soluciones pueden ser codificadas.

</aside>

Definiciones:

• Fenotipo: problema a solucionar
• Cromosoma: cada una de las soluciones posibles, codificadas. Le vamos a aplicar ciertas operaciones:
  • Cruce
  • Mutación
  • Evaluación: Probar cada solución y obtener un puntaje (según la función de aptitud) que indique qué tan buena es.
  • Selección
• Gen: cada uno de los símbolos en el cromosoma
• Genotipo: si los símbolos son binarios
• Generación: cada iteración → nuevo conjunto de soluciones

Operadores

• Selección

  • Por Ruleta/Rango:

    Método azaroso pero las mejores soluciones tienen más probabilidad de ser elegidas. A cada cromosoma se le asigna una probabilidad según su utilidad y se le asigna una porción de la ruleta. Luego se tira la ruleta y se queda el cromosoma que ganó.

    

  • Selección elitista:

    Igual que el anterior pero además copiamos a los mejores en la siguiente generación para que no se pierdan en caso de no salir en la ruleta.

  • Otras selecciones**:** jerárquica, por torneo (se las hace competir a las soluciones), escalada, etc.

• Cruza

  • Crossover por 1 punto:

    Corto las soluciones en un punto elegido al azar y combino las partes obteniendo dos soluciones nuevas.

    

  • Crossover por 2 puntos:

    Corto las soluciones en dos puntos elegido al azar y combino las partes obteniendo dos soluciones nuevas.

    

  • Crossover aritmético:

    Ya no se realiza cortando en puntos, sino que se le aplican funciones a las soluciones que dependerán del problema a resolver. Por ejemplo, máscaras con operacion AND.

    

• Mutación

  No se debe abusar de las mutaciones, deben darse en un gen de una cantidad pequeña de la población, con muy baja probabilidad.

  Consiste en cambiar aleatoriamente un gen.

  

  Por ejemplo, cambiar un gen particular o intercambiar dos.

  

  Mutación vs cruza en árboles.

Variables

• Tamaño de la población: Es la cantidad de soluciones que vamos a tener. Si tenemos un tamaño excesivo al inicio, cada ciclo será más lento. Por otro lado, si es escasa tendremos una solución poco óptima, caigamos en un mínimo local (y no global).
• Probabilidad de cruce entre cromosomas (de 0 a 100%).
• Probabilidad de mutación de cromosomas (de 0 a 100%). Suele ser más chica que la de cruce.

Comenzamos con una población aleatoria inicial y a lo largo de los ciclos se llega a una población final que resuelve el problema.

Codificaciones