Resumen aplicación de apoyo a la gestión de horarios para




descargar 136.41 Kb.
títuloResumen aplicación de apoyo a la gestión de horarios para
página3/4
fecha de publicación09.03.2016
tamaño136.41 Kb.
tipoResumen
b.se-todo.com > Documentos > Resumen
1   2   3   4

2.3 Representación del Problema.


La población esta conformado por un número de individuos o cromosomas. Cada cromosoma esta formado por un conjunto de genes, que son la unidad más pequeña de información. La representación elegida utiliza un gen como unidad de información básica, que llevado a la práctica representaría un módulo. De esta forma, el módulo número 1 del día lunes es un gen y éste almacena la información de la asignatura y el profesor que la dicte, así como se muestra en la Ilustración.


 

Lunes

Martes



1

Módulo1 = Gen1

Módulo11 = Gen11

 

2

 

 

 

3

 

 

 

4

 

 

 

5

 

 

 

6

 

 

 

7

 

 

 

8

Módulo8 = Gen8

Módulo17 = Gen17

 

9

 

 

 

10

 

 

 


Ilustración 2: Representación de un Módulo y Gen.
La solución usa una representación de cromosoma para los horarios. En la ilustración, se muestra de qué manera es implementada esta representación.


Ilustración 3: Representación de Cromosoma para los Horarios.
La Ilustración muestra también, que se utilizarán cromosomas pares para la representación general de las soluciones. Esto significa, que por cada módulo de un horario existen dos genes, uno en un cromosoma Asignatura y otro en un cromosoma Profesor. Ambos tienen la misma longitud y por cada gen de uno de ellos existe otro asociado al mismo módulo de un horario de un curso. También se muestra que las soluciones de varios cursos son parte del gran cromosoma u horario general. Así encontraremos en los cromosomas solución (asignaturas y profesores), toda la información relacionada con cada curso. Otro punto importante que destacar, es el hecho, que la posición dentro del cromosoma está relacionado con la posición dentro de un horario. De esta manera, se obtienen varias ecuaciones que permiten saber: el curso, día de la semana y módulo dentro del día en un cromosoma, como se muestra en la Tabla.


Nombre

Descripción

Fórmula

ParteEntera

Parte entera de una división

 

Residuo

Residuo de una división

 

DxS

Días por semana

Definida por el usuario

MxD

Módulos por Día

 Definida por el usuario

MxS

Módulos por Semana

DxS * MxD

NG

Número del Gen

 

C

Número del Curso

ParteEntera( NG / MxS ) + 1

DS

Día de la Semana

( ( NG - ( C * MxS ) ) / MxD ) + ( 1 - Residuo( ( ( NG - ( C * MxS ) ) / MxD ) / 1 ) )

MD

Módulo del Día

NG - ( ( C * MxS ) + ( ( DS - 1 ) * MxD ) )


Tabla 1: Definición de formulas a utilizar

La Función Evaluación, F(X), entrega el grado de optimización del cromosoma con respecto a lo esperado. Cada cromosoma tiene una evaluación tanto por las restricciones duras como por las restricciones suaves. La función evaluación trabaja como se indica a continuación:

  • La evaluación dura, funciona simplemente verificando si existen o no conflictos con las restricciones duras. Así, se determinará si el cromosoma es válido como una solución. De no ser así, la función, retornará un valor inválido que indicará que dicho cromosoma no cumple con lo esperado.

  • La evaluación suave, funciona ponderando los conflictos con las restricciones suaves. Cada conflicto tendrá un costo dependiendo de cual restricción suave fue quebrantada, resultando en una evaluación más baja, pero válida, del cromosoma. Retorna un valor que denota el costo de no cumplir con las restricciones suaves.


Una función de comparación es necesaria para comparar cromosomas y evaluar así, cual de ellos es más apto. Hacer esto, consiste en elegir el individuo con la mejor evaluación dura. La mejor evaluación significa un valor menor en la función evaluación.
La función solución determina si un cromosoma ha cumplido o no con los límites definidos para ser solución. Así, por ejemplo, si se determina que una solución requiere que un cromosoma tenga una evaluación menor o igual a un X número, entonces, la función solución dirá si un cromosoma es igual o menor en la evaluación que ese X.

El método de evolución es la función principal de la población. Define la estrategia para generar una nueva población partiendo por cromosomas padres, utilizando mutaciones, cruces o propagación. Comúnmente, la nueva población se genera iterativamente (nuevos cromosomas se generan uno por uno a partir de cromosomas padres). Este método, se implementa de la siguiente forma:

  • El algoritmo parte con una población inicial de 10 cromosomas. Los cuales son creados aleatoriamente.

  • La población se evalúa con la función evaluación, f(x).

  • Se selecciona aleatoriamente de esta población dos cromosomas que se cruzan con un patrón intercalado de genes.

  • El cromosoma hijo es evaluado e ingresado en la población.

  • Cada cierta cantidad de cruces se procede a provocar una mutación en el cromosoma hijo. Se muta una determinada cantidad de genes seleccionados en forma aleatoria de cromosoma.

  • Luego se procede a compactar la población, al llegar a un número determinado de individuos. Este proceso de compactación selecciona un porcentaje determinado de los individuos con mejor evaluación y los utiliza en una nueva población como individuos iniciales. El resto de los cromosomas no seleccionados son eliminados.

  • El proceso se repite hasta que se encuentre un cromosoma que se ajuste a la función solución o si el proceso ha superado un tiempo límite.


El porcentaje de individuos seleccionados en el proceso de compactación como el tiempo límite y las mutaciones, para la encontrar la solución, será determinado por los usuarios finales al parametrizar el software construido.

En los cruces se utilizan diversos tipos de patrones. Estos patrones indican la manera en la cual se mezclarán los genes de un padre con otro para formar un cromosoma hijo. El patrón utilizado en la implementación de la solución es intercalado. En la Ilustración 9 se muestra el patrón clásico de cruce y en la Ilustración se muestra el patrón intercalado de cruce utilizado.


Patrón

1

1

1

1

0

0

0

0




























Cromosoma Padre 1

A

B

C

D

E

F

G

H




























Cromosoma Padre 2

I

J

K

L

M

N

O

P




























Cromosoma Hijo

A

B

C

D

M

N

O

P


Ilustración 4: Patrón Clásico de Cruce.



Patrón

1

0

1

0

1

0

1

0




























Cromosoma Padre 1

A

B

C

D

E

F

G

H




























Cromosoma Padre 2

I

J

K

L

M

N

O

P




























Cromosoma Hijo

A

J

C

L

E

N

G

P


Ilustración 5: Patrón Intercalado de Cruce.
Dentro de los métodos de selección tradicionales propuesto en los algoritmos genéticos existen varias tendencias. Algunas utilizan sistemas ultra elitistas, donde los cromosomas menos aptos no tienen posibilidad de participar en los cruces. También están los participativos donde los cromosomas menos aptos participan en los cruces y sobreviven en sus descendencias.

Al realizar prueba de ambos métodos y patrones de cruce con un grupo de pruebas pequeños, en la mayoría de los casos el método participativo fue el de mejor rendimiento, siendo seleccionado para construir la solución final.

La mutación altera un gen único de un cromosoma. Se analizaron dos métodos:

  • El trueque de dos genes aleatorios del cromosoma. [Galiasso, Wainwright].

  • Se crea un método experimental el cual elije aleatoriamente un gen y lo reemplaza con otro gen con información válida y nueva al cromosoma.


La mutación supone introducir un cambio aleatorio en la población actual. Esta es necesaria con el fin de impedir que la población se concentre en una zona pequeña, convergiendo al óptimo local en vez de convergir al óptimo global (es decir la solución óptima). Ambos métodos son válidos, se seleccionó el método experimental, pues éste ingresa información nueva al cromosoma, evitando la convergencia al óptimo local.
1   2   3   4

similar:

Resumen aplicación de apoyo a la gestión de horarios para iconResumen Para contextualizar la gestión de los procesos de formación...

Resumen aplicación de apoyo a la gestión de horarios para iconResumen la Norma iso 18000 es un Sistema de Gestión de la Seguridad...

Resumen aplicación de apoyo a la gestión de horarios para iconResumen El presente trabajo es un estudio sobre las necesidades detectadas...

Resumen aplicación de apoyo a la gestión de horarios para iconDesarrollo e implementación de estrategias multimedia como material...

Resumen aplicación de apoyo a la gestión de horarios para iconNormas complementarias para la aplicación y fiscalización de la cuota...

Resumen aplicación de apoyo a la gestión de horarios para iconManual de Procedimientos para la Gestión Integral de Residuos Hospitalarios...

Resumen aplicación de apoyo a la gestión de horarios para iconManual de apoyo para Distribuidores

Resumen aplicación de apoyo a la gestión de horarios para iconDirectrices para un adecuado reconocimiento y apoyo

Resumen aplicación de apoyo a la gestión de horarios para iconAula Horarios Clases Teóricas

Resumen aplicación de apoyo a la gestión de horarios para iconAula Horarios Clases Teóricas




Todos los derechos reservados. Copyright © 2019
contactos
b.se-todo.com