Cross-over de un punto. Se genera un número aleatorio menor a
la longitud del cromosoma, el cual será la posición de cross-over.
Los genes que se encuentran antes de dicha posición son toma-
dos del primer padre y los genes que están después se toman del
segundo padre.
Cross-over uniforme. Se genera un patrón aleatorio de 1s y 0s,
y se intercambian los genes de los dos cromosomas que coinci-
dan donde hay un 1 en el patrón. O bien, se genera un número
aleatorio para cada gen, y si supera una determinada probabilidad
(típicamente 0.5), se intercambia entre los dos cromosomas.
El cross-over es el principal operador genético, hasta el punto
que se puede decir que no es un algoritmo genético si no tiene
cross-over y, sin embargo, puede serlo perfectamente sin muta-
ción (Holland, 1992).
4)
Mutación. Se produce un nuevo individuo, modificando
ligeramente, al azar, a uno ya existente.
La mutación asegura que todos los posibles valores para un cro-
mosoma pueden ser alcanzados. Si un valor para un gen no se
generó en la población inicial, con el cross-over no podrá gene-
rarse. La mutación opera seleccionando cualquier posición de gen
y modificando su valor.
En la evolución natural la mutación es un suceso poco común,
sucede aproximadamente en una de cada mil replicaciones. En la
mayoría de los casos las mutaciones son fatales para el individuo
afectado, pero contribuyen a la diversidad genética de la especie.
En un algoritmo genético tendrán el mismo papel e, igualmente,
una frecuencia muy baja.
Restricciones duras, las cuales se tienen que cumplir forzosamente:
1.
En un paquete no podrán existir dos clases el mismo día a
la misma hora.
2. No deben haber horas libres entre grupos.
3. Un maestro no puede dar más de una clase el mismo día a
la misma hora.
Restricciones suaves, que corresponden a preferencias:
+
Que un maestro prefiera dar clase de 08:00 a 09:00 horas, en
lugar de 9:00 a 10:00 horas.
Debe estructurarse el cromosoma para cumplir las restricciones. La me-
jor manera de hacerlo es generar una serie de números consecutivos que re-
presentarán las horas de un paquete para determinado día. Como no se sabe
cuál clase debe ir primero y cuál después, se desordena la cadena aleatoria-
mente. Cada una de estas cadenas formará un gen, y cada uno representará
un día de cada paquete dentro del horario.
Para darle significado a cada cadena, ésta se coloca en una tabla planti-
lla. El cromosoma completo irá en el último renglón de una tabla. Los otros
renglones indicarán qué paquete, qué grupo y qué día es la hora que quedó
en cada columna. Cada símbolo significa una hora del día como se muestra
en Tabla 1.
No es conveniente abusar de la mutación. Es cierto que es un
mecanismo generador de diversidad, y, por tanto, una solución
cuando un algoritmo genético está estancado, pero también es
cierto que reduce el algoritmo genético a una búsqueda aleatoria.
Siempre es más conveniente usar otros mecanismos de genera-
ción de diversidad, como aumentar el tamaño de la población o
garantizar la aleatoriedad de la población inicial.
5)
Reemplazo. Si un nuevo individuo es mejor que el peor
individuo de la población, el nuevo individuo toma el lugar del
menos apto.
C) CONDICIÓN DE TERMINACIÓN
El proceso termina cuando la población (o algún individuo) alcanzan
una puntuación preestablecida, o cuando se alcanza un determinado núme-
ro de generaciones.
Diseño de la solución propuesta
Inicialización y codificación
Para el caso particular estudiado se presentan las siguientes restriccio-
nes:
104
Revista Científica
Tabla 1. Codificación del cromosoma
Números hexadecimales a horas.
En la Tabla 2 se muestra un cromosoma ejemplo, acomodado en la tabla
plantilla para su decodificación:
Ejemplo:/AB9C8/A9B8/89ACB/A89BC/9A
8B/3124/31542/1324/43251/51342//
En la inicialización de la población se escogió una estructura que im-
pidiera que se formen los resultados prohibidos de las restricciones duras
número 1 y número 2. Posteriormente se deberá agregar una condición en
la etapa de evaluación para monitorear los resultados prohibidos de la res-
tricción dura número 3.