Implementación en Python de optimización de programación de cursos basada en algoritmo genético

La esencia del problema de programación de cursos es asignar cursos, profesores y estudiantes a aulas apropiadas y períodos de tiempo apropiados. Involucra muchos factores y es un problema de programación de cursos multiobjetivo que se denomina investigación de operaciones. para problemas de horarios (TTP). Considerando que hay n periodos de tiempo que se pueden programar en una semana, m profesores necesitan participar en la programación de clases, y cada profesor tiene que asistir a k clases por semana en promedio, sin considerar otras restricciones, se pueden plantear una variedad de combinaciones posibles introducido, por lo que la alta complejidad es insoportable para las computadoras actuales. Por lo tanto, muchos investigadores han propuesto otros algoritmos de programación, como el recocido simulado, la búsqueda de listas y la satisfacción de restricciones.

Github: /xiaochus/GeneticClassSchedule

El algoritmo genético es un modelo computacional del proceso de evolución biológica, que simula la selección natural y los mecanismos genéticos de Darwin. Un método de búsqueda de soluciones óptimas simulando el proceso de evolución natural. El proceso del algoritmo genético es el siguiente:

El algoritmo genético primero genera un conjunto de soluciones aleatorias para el problema a resolver, al que llamamos población. Cada individuo de la población es una solución al problema. Durante el proceso de optimización, el algoritmo calcula la función de costo de toda la población para obtener una secuencia de aptitud relacionada con la población. Como se muestra en la siguiente figura:

Para obtener una nueva población de próxima generación, primero se debe clasificar la población según su aptitud y se seleccionan los mejores individuos para unirse a la población de próxima generación. El proceso también se llama elección Elite. El resto de la nueva población se obtiene modificando los individuos de élite seleccionados.

El método de modificación de poblaciones se basa en el método evolutivo de DAN, que utiliza dos métodos generales: mutación y cruce. La mutación ocurre al realizar pequeños cambios aleatorios en una población. Si la solución está codificada en binario, 0 y 1 se mutan aleatoriamente entre sí en posiciones elegidas al azar; si la solución está codificada en decimal, la suma y la resta se eligen aleatoriamente en posiciones elegidas al azar; Cruzar consiste en seleccionar aleatoriamente dos individuos de la mejor población y utilizar una determinada posición como punto de intersección para sintetizar un nuevo individuo.

Después de la mutación y el cruce, obtendremos una nueva población (del mismo tamaño que la población anterior), y la nueva población repetirá el proceso anterior hasta que se complete el número de iteraciones (fallo) o la adaptación de la Se alcanza la solución Cuando el rendimiento cumple con nuestros requisitos (éxito), el algoritmo GA finaliza.

Implementación del algoritmo

Primero defina una clase de curso, que contiene varios atributos: curso, clase, profesor, aula, semana y hora. Los primeros tres atributos se pueden personalizar y el último. Es necesario optimizar algorítmicamente tres propiedades.

A continuación, defina una función de costos para calcular los conflictos entre grupos curriculares. Cuando los conflictos de planes detectados son 0, el plan es un plan conforme. La detección de conflictos sigue las siguientes reglas:

El proceso de optimización mediante algoritmos genéticos es el siguiente, que es el mismo que el proceso del diagrama de flujo de la sección anterior.

init_population: Inicializa aleatoriamente diferentes poblaciones.

Mutación: operación de mutación que agrega o resta aleatoriamente atributos mutables de un objeto de programación dentro del rango permitido.

Cruce: La operación de cruce intercambia aleatoriamente los atributos de dos objetos en diferentes ubicaciones.

Evolución: Inicia el algoritmo GA para optimización.

Resultados experimentales

Para probar los resultados de la programación, definimos las siguientes 3 clases, incluidos 6 cursos, profesores y 3 aulas.

Los resultados de la optimización son los siguientes. No hubo conflicto de programación en la iteración 68.

Seleccione el horario del curso de la Clase 1203 para visualizarlo. Como se muestra en la figura siguiente, el algoritmo organiza razonablemente los cursos correspondientes.