04. Agente viajero: mutación

Publicado por

En esta nota construiremos el método que se encargará de realizar la mutación de un cromosoma. Existen varios métodos para implementar la mutación; cuando el cromosoma está representado por una cadena binaria, es común cambiar por medio de una probabilidad algunos 0’s por 1’s, simulando el comportamiento que ocurre en la naturaleza. Sin embargo, recordemos que para la implementación de la solución del problema del agente viajero estamos utilizando una representación del cromosoma como una cadena de números enteros, por lo que utilizaremos el método que menciono a continuación.

Mutación por inversión

Este método consiste en elegir una subcadena aleatoria del cromosoma para después invertirla.

Supongamos que padre es el cromosoma elegido: padre = [8 9 7 5 4 6 2 1 3]

Y la subcadena elegida aleatoriamente es: subcadena = [5 4 6 2]

Entonces el nuevo cromosoma será: hijo = [8 9 7 2 6 4 5 1 3]

Nota que la sucadena [5 4 6 2] ahora está en otro orden [2 6 4 5]. Como se puede observar este cromosoma sigue siendo válido, pues no repite ninguna ciudad en su recorrido.

Nota: recuerda que la implementación la estamos realizando en Python.

Método para agregar en la clase cromosoma

#Método con el que un cromosoma muta.
#Mutación por inversión.

def mutar(self):
    lista = self.getciudades()
    mitad = len(lista)/2
    ini = aleatorio(0, mitad)
    fin = aleatorio(mitad, len(lista))
    a, b, c = lista[0:ini], lista[ini:fin], lista[fin:]
    b.reverse()
    del self.__ciudades
    self.__ciudades = a + b + c
    del a
    del b
    del c

Función para mutar una población

También agregamos a nuestro código esta función que utilizaremos en notas posteriores para la creación de nuestra población inicial.

#Invoca el método de mutación para algunos individuos de la población con
#cierta probabilidad.

def mutarpob( pob, pmuta ):
    for p in pob:
       if pmuta > random():
           p.mutar()

Una vez que se entiende el problema es realmente sencillo implementar un algoritmo genético. Con el método mutar será posible explorar otras áreas del espacio de soluciones y servirá para encontrar una solución al problema. Espero que este contenido haya sido claro, en caso de que tengas dudas puedes expresarlas en los comentarios y con gusto las atenderé. ¡Hasta la próxima!

2 comments

Responder a Miriam García Cancelar respuesta

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