Algoritmo Genético personalizado: Programación de horarios¶

Se necesita programar horarios de personal médico en la posta de San Jerónimo, Cusco, Perú, en función a las siguientes especificaciones:

  • Se debe cubrir el horario de una semama (7 días).
  • Los turnos tienen una duración de 8 horas, dividido en: mañana (6-14 hrs), tarde (14-22 hrs), y noche (22-6 hrs).
  • Se cuenta con 5 médicos (1: Juan, 2: Miriam, 3: Mirtha, 4: Alberto, 5: Mónica)
  • Los horarios asignados a los médicos, deben ser lo más equilibrado posible.
  • Se debe garantizar que un médico debe descanzar 24 horas depués de un turno.

Importación de liberías¶

In [ ]:
import pandas as pd
import numpy as np
from collections import Counter
from ag_lbpt.ag import AlgoritmoGenetico

Implementación de la Función de aptitud¶

$$ Aptitud = \sum_{i=1}^{Nodos} {Penaliza Desequilibrio_i + Penaliza Descanso_i} $$
In [ ]:
def AptitudHOR(Ruta):
    
    # Calcula la frecuencia de aparicion médicos
    Frec = Counter(Ruta)
    
    # Penaliza el desequilibrio de asignación de turnos
    PenalizaDesequilibrio=0
    for _, valor in Frec.items():
        if (valor < 4 or valor > 5):
            PenalizaDesequilibrio = PenalizaDesequilibrio + 1
    
    # Calcula por medico la posición de los turnos asignados
    Pos_Ind = {}
    for indice, valor in enumerate(Ruta):
        Pos_Ind.setdefault(valor, []).append(indice)
    
    # Penaliza por turnos consecutivos < 24 horas (< 4 turnos)
    PenalizaDescanso = 0
    for _, valores in Pos_Ind.items():
        for k in range(len(valores)-1):
            if ( (valores[k+1] - valores[k]) < 4 or (valores[k+1] - valores[k]) > 6):
                PenalizaDescanso = PenalizaDescanso + 1
    
    return PenalizaDesequilibrio + PenalizaDescanso

Configuración y ejecución del Algoritmo Genético¶

In [ ]:
AG = AlgoritmoGenetico(
    Iteraciones=25,             # Cantidad de iteraciones del AG
    Generaciones=150,            # Cantidad de generaciones del AG
    Poblacion=100,              # Cantidad de población
    ProbMutacion=0.1,           # Probabilidad de mutación
    TipoMutacion='Permuta',     # Tipo de mutación ['Permuta', 'UnPunto']
    TipoCruce='UnPunto',        # Tipo de cruce ['Complemento', 'UnPunto']
    GenUnico=False,             # True: Los genes no usan valores repetidos
    InicioFijo=False,           # True: El 1er gene siempre es '0'
    InicioFinFijo=False,        # True: El 1er gen = '0'; ultimo gen = 'N-1'
    N=21,                       # Cantidad de ciudades
    MinCromosoma=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], # Min valor de genes
    MaxCromosoma=[4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4], # Máx valor de genes
                                # Tipo de datos de genes
    TipoDato=['int','int','int','int','int','int','int','int','int','int','int',
              'int','int','int','int','int','int','int','int','int','int'],
    PobElite=3,                 # Cantidad de individuos de la élite
    FunAptitud=AptitudHOR       # Función de aptitud implementado externamente
)

Solucion, Costo = AG.Ejecutar()
print('Solucion : ', Solucion)
print('Costo    : ', Costo)

Solucion :  [1, 3, 4, 1, 2, 3, 4, 1, 1, 2, 4, 3, 1, 2, 4, 3, 2, 1, 4, 2, 3]
Costo    :  5

Evolución del costo¶

In [ ]:
AG.GraficaCosto()

Visualización del Horario solución¶

In [ ]:
# Diccionarios
Dic_Medico = {1: 'Juan', 2: 'Miriam', 3: 'Mirtha', 4: 'Alberto', 5: 'Mónica'}
Dic_DSem = {0: 'LUNES', 1: 'MARTES', 2: 'MIÉRCOLES', 3: 'JUEVES', 4: 'VIERNES', 
            5: 'SÁBADO', 6: 'DOMINGO'}
Dic_Hora = {0: 'MAÑANA', 1: 'TARDE', 2: 'NOCHE'}

# coloca en el dataframe los datos, cabcera e indice
Hor_Sem = pd.DataFrame(np.array(Solucion).reshape(7, 3).transpose(), 
                       columns=Dic_DSem.values(), index=Dic_Hora.values())

# Cambiar indice de médicos por nombres
Hor_Sem = Hor_Sem.replace(Dic_Medico.keys(), Dic_Medico.values())

display(Hor_Sem)
LUNES MARTES MIÉRCOLES JUEVES VIERNES SÁBADO DOMINGO
MAÑANA Juan Juan Alberto Miriam Juan Mirtha Alberto
TARDE Mirtha Miriam Juan Alberto Miriam Miriam Miriam
NOCHE Alberto Mirtha Juan Mirtha Alberto Juan Mirtha

Luis Beltran Palma Ttito, luis.palma@unsaac.edu.pe (autor)

Dennis Iván Candia oviedo, dennis.candia@unsaac.edu.pe (coautor)

Carlos Ramón Quispe Onofre, carlos.quispe@unsaac.edu.pe(coautor)

Willian Zamalloa Paro, willian.zamalloa@unsaac.edu.pe(coautor)

José Mauro Pillco Quispe, jose.pillco@unsaac.edu.pe(coautor)