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 en la cual se “parte” el horario , es decir , dada la hora H y los profesores p1 y p2 , antes de H se tiene un conjunto de horarios para p1 y p2

asi como despues de H se tiene otro conjunto de horarios para p1 y p2.

de por si estos horarios son independientes ( no existe interseccion ya que vienen de una solucion ) y unicos ( ya que como se saca una solucion no se permiten horarios con 2 profesores asignados ) por lo tanto se puede tomar

la primera parte de p1 y cambiarla con la primera parte de p2 o cambiar la segunda parte de p1 con la segunda parte de p2 con lo que se generarian una nueva solucion.

Lo mismo se puede aplicar pero cambiando horarios asignados a los profesores en la misma solucion.

Ejemplo:

P1 -> H1 - H2 - H 3

P2

...