06. Agente viajero: selección

Publicado por

Bienvenido otra vez a esta serie de notas sobre algoritmos genéticos, en esta temporada estamos abordando el problema del agente viajero, si eres nuevo en el sitio te recomiendo leer esta serie desde el inicio.

En esta nota construiremos el método de selección que ayudará a elegir a los individuos de la población más aptos para que se reproduzcan, hay que considerar que de forma natural también los individuos menos aptos tienen esta posibilidad.

Aquí te menciono dos de los métodos más utilizados y simples de implementar.

Método de selección por ruleta

Existe un método de selección que consiste en simular una ruleta, como en los juegos de azar y cumple con las siguientes características:

  • Las rebanadas de la ruleta deben de ser de distintos grosores, estos deben representar los valores de sus aptitudes de forma proporcional.
  • Para que este método funcione los valores de las aptitudes deben estar representados con valores positivos.

Funcionamiento

El funcionamiento de este método es el siguiente:

  1. Obtener la aptitud de cada individuo de la población.
  2. Realizar una suma de las aptitudes obtenidas la cual puede ser llamada como aptitud total.
  3. Obtener la probabilidad de cada individuo de la población.
  4. Obtener las probabilidades acumuladas por cada individuo de la población, es decir, la sumatoria de las probabilidades calculadas para cada individuo.
  5. Generar un número entre 0.0 y 1.0 de forma aleatoria, este número permitirá saber cuando un individuo es apto para ser elegido como parte de la nueva generación, comparando si la probabilidad acumulada del individuo es mayor o igual al número aleatorio entonces este es seleccionado.
  6. Repetir estos pasos hasta obtener la cantidad de individuos deseados en la población.

Método de selección por torneo

Otro de los métodos más utilizados para los algoritmos genéticos es el de selección por torneo, el cual implementaremos para el problema del agente viajero, si tu lo deseas puedes implementar cualquiera de los dos métodos. Este método cumple con las siguientes características:

  • Los individuos a seleccionar son comparados entre ellos para determinar cuál es el más apto.
  • Puede ser determinista o probabilística esta selección.

Funcionamiento

El funcionamiento de este método es el siguiente:

Versión determinística

Seleccionar al azar un número de individuos que por lo general son 2, estos se comparan y se elige al más apto para la nueva generación.

Versión probabilística

Generar un número aleatorio entre 0 y 1, para decidir al azar cuál de los dos individuos es el más apto, usualmente se utiliza como el más apto aquel que obtiene un rango de valores entre 0.5 y 1, y el menos apto el que tiene valores menores.

Método para agregar en la clase cromosoma

#selecciona
def selecciona(poblacion, pobtam):
    p = list(poblacion)
    p.sort()
    return p[:pobtam]

Función de selección por torneo

La implementación de esta función esta basada en la versión probabilística del método de selección por torneo.

Es necesario agregar este segmento de código en el que hemos estado utilizando en las notas anteriores, para la creación de la población de las siguientes generaciones.

#Método de selección por torneo.
def selecciont(poblacion, tampob):
    selec = list()
    for k in (1,2):
        participantes = list(poblacion)
        if len(participantes)%2 == 1:
            if k == 1:
                participantes.pop(aleatorio(0, len(participantes)))
            else:
                participantes.append(participantes[aleatorio(0, len(participantes))])
        while participantes:
            a = participantes.pop(aleatorio(0, len(participantes)))
            b = participantes.pop(aleatorio(0, len(participantes)))
            ganador= a if a<b else b
            selec.append(ganador)
    selec.sort()
    return selec[:tampob]

Toma en cuenta que el método de selección es muy importante para el éxito de un algoritmo genético, por lo que se deben explorar diversos métodos y considerar el tipo de problema que se desea resolver. La selección permite acotar la búsqueda y reducirla conforme se realiza cada iteración del algoritmo genético, sin embargo, no siempre esta es la mejor opción pues también limita el área de exploración y a veces es necesario tener una visión más amplia de todo el plano donde habitan los individuos.

Ya estamos cerca de terminar cada componente del algoritmo genético, en la siguiente entrega construiremos la población inicial. ¡Hasta entonces!

14 comments

  1. Estoy interesado en saber si existe un capitulo 7 de este problema, donde se implemente la creación y de población y el resto de cosas necesarias para correr la el programa completo. Muy buen trabajo, saludos.

  2. Excelente tutorial, mi felicitación por tu trabajo, pero como han dicho otras personas anteriormente, esto deseando ver tu próxima publicación para terminar este problema.
    Gracias por tu esfuerzo y dedicación.

    1. ¡Hola!

      Gracias por el interés en estas notas, disculpen la demora. Trabajaré en ello este fin de semana, esperando publicarla la siguiente semana.

      Saludos.

Responder a Miriam García Cancelar respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *