Algoritmo Genético

Representacion de soluciones para el algoritmo genetico

Representacion:

Se tomará como representación de la solución a una lista de profesores , cada uno compuesto por una lista de los horarios posibles que se le asigno.

Ejemplo :

Profesor 1 -> Horario1 - Horario 2 - Horario 3 - Horario 4 ..

Profesor 2 -> Horario 5 - Horario 6

En donde los horarios son compuestos de un turno ( Hora Inicio , Hora Fin ) y una frecuencia( dias en los que esta disponible ese horario ; ejemplo : Lunes , Martes , Viernes ).

Se toma esta representacion ya que nos ayudará a crear soluciones dentro del espacio de busqueda de una manera natural , y en caso de que se produsca una solución fuera del espacio de busqueda( solucion que viola alguna restriccion ) se puede aplicar un algoritmo de reparacion para hacer que cumpla todas las restricciones requeridas.

Operadores :

Crossover :

Se tomaran 2 representaciones cromosomaticas y se tomara un subconjunto de profesores de cada una , generando así una nueva solucion.

En caso de que se generen horarios sin profesores asignados o con mas de 1 profesor asignado, se correra una heruistica de correccion , para volver a asignar todos los horarios libres.

Ejemplo :

C1 =

P1 - > H1 -> H2 -> H3

P2 -> H4 -> H5

P3 -> H6

C2 =

P1 -> H6 - H4

P2 -> H2 -> H1

P3 -> H3 -> H5

Hijo =

P1 -> H1 - H2 - H3

P2 -> H2 - H1

P3 -> H3 -> H5

Sin usar : H4 H6

duplicados : H2 - H1 -H3

reparado =

P1 -> H1 - H2 - H3

P2 -> H6 - H4

P3 -> H5

* asumiendo que los horarios son independientes , no hay colision entre los turnos y frecuencias de los horarios.

Mutacion :

En el caso de mutacion se seleccionan 2 profesores diferentes y se escoge

una hora

...