Klausurplan automatisiert erstellen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
EmaNymton
User
Beiträge: 174
Registriert: Sonntag 30. Mai 2010, 14:07

Hallo,
ich habe eine Idee für ein Programm, dass ich gerne schreiben möchte, jedoch habe ich noch nicht die Idee, wie ich starten soll bzw. mit welchen Techniken ich das geschickt umsetze. Hier hoffe ich auf Leute, die mehr Erfahrung haben als ich oder ggf. sowas schonmal gemacht haben.
Ich versuche das Problem mal so gut es geht zu beschreiben:

Wir müssen an unserer Schule für jedes Halbjahr einen Klausurplan erstellen, was bisher immer von Hand geschieht. Dabei kommen natürlich auch nicht so optimale Lösungen heraus, mit denen Schüler und Kollegen unzufrieden sind. Diese Klausurplanerstellung würde ich gerne automatisieren und optimieren, da sie jedes Schuljahr ansteht.
Folgende Rahmenbedingungen sind gegeben:
Ein Halbjahr besteht aus 2 Quartalen, in jedem Quartal ist der Klausurzeitraum fest vorgegeben und es gibt immer mal wieder Tage in diesem Zeitraum, an denen keine Klausuren geschrieben werden dürfen.
In einem Kurs werden pro Halbjahr entweder 1 (1. oder 2. Quartal) oder 2 Klausuren (je Quartal 1) geschrieben. Die Klausuren sollen zu den Zeiten stattfinden, in denen der Kurs jeweils vormittags Unterricht hat. Ist dies nicht möglich (weil z.B. der Kurs nur nachmittags unterrichtet wird), wird die Klausur in einen anderen Block verlegt. Es dürfen maximal drei Klausuren pro Woche geschrieben werden. Die LK-Blöcke schreiben in der Regel relativ zu Beginn der Quartale.

Jetzt kommen die Optimierungen, die ich gerne hätte:
  • zwei Klausuren im selben Kurs sollen zwischen den Quartalen möglichst weit auseinander liegen.
  • die Schüler sollen ihre Klausurtermine möglichst gut verteilt haben.
  • unterrichtende Kollegen sollen ihre Klausurtermine auch möglichst gut über das Halbjahr verteilt haben, damit die Korrekturbelastung gleichmäßig verteilt wird.
Die Daten, welcher Schüler in welchem Kurs Klausur schreibt bzw. welcher Kurs wann stattfindet und von welchem Kollegen dieser unterrichtet wird, kann ich aus unserer Schulverwaltungssoftware als CSV-Dateien auslesen.

Mein Problem ist, dass ich nicht genau weiß, wie ich anfangen soll. Das fängst schon bei der Datenstruktur an und hört bei der Optimierung auf. Für die drei Optimierungen müsste man ja im Prinzip jeweils einen Wert vergeben, der die Summe der Zeitabstände beinhaltet und die Lösung suchen, bei der alle drei Summen minimal sind.

Hat jemand schonmal ein ähnliches Problem gelöst und kann mir ggf. ein paar Starthilfen/Stichwörter geben.
nezzcarth
User
Beiträge: 1634
Registriert: Samstag 16. April 2011, 12:47

Wenn's mehr um die Lösung, als die eigentlich Aufgabe geht, wäre es vielleicht eine Überlegung wert, das statt mit Python mit Prolog zu versuchen. Gehen wird's mit Python aber natürlich auch.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

EmaNymton hat geschrieben:Hallo,
Hat jemand schonmal ein ähnliches Problem gelöst und kann mir ggf. ein paar Starthilfen/Stichwörter geben.
Ein Freund von mir hat so etwas ähnliches mal für einen Fachbereich einer FH implementiert. Dabei hatte er erst einen Ansatz über ein Flussnetzwerk mit maximalen Fluss gewählt. Die Komplexität wurde dabei jedoch dermaßen hoch, dass er sich dann für den Ansatz einer Heuristik entschieden hat. Ich vermute mal, dass das letztlich das ist, worauf es bei Dir hinauslaufen wird.

Die Datenstruktur würde ich erst einmal "naiv" versuchen, aus den Gegebenheiten abzuleiten. Du hast Also bestimmte Klausuren, Zeitslots der Fächer und dazu noch mögliche Tage. Das komplizierte ist es jetzt wohl, wie man die Constraints modelliert. Sind das eigene Objekte? Oder werden sie durch Attribute / Properties von anderen Objekte repräsentiert?

Ich denke, da musst Du einmal selber ein wenig experimentieren! Zudem vermute ich mal, dass man im Netz dazu doch das ein oder andere finden kann.
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
EmaNymton
User
Beiträge: 174
Registriert: Sonntag 30. Mai 2010, 14:07

So, hatte jetzt mal wieder ein wenig mehr Zeit mich dem Problem zu widmen. Ich bin jetzt mal naiv an die Sache rangegangen, komme aber jetzt an meine Grenzen ;)

Vielleicht erläutere ich kurz, was ich bisher gemacht habe:
Ich habe mir aus dem Schulverwaltungsprogramm die notwendigen Daten importiert. Daraus habe ich mir erstmal eine Liste "kurse" der Kurse erstellt, in denen überhaupt Klausurschreiber sind, so dass alle anderen Kurse schon aus den Berechnungen rausfliegen. Die Elemente der Liste "kurse" sind Objekte der Klasse

Code: Alles auswählen

class Kurs():
    def __init__(self, name, schueler, stunden):
        self.name = name
        self.schueler = schueler
        self.stunden = stunden # dict nach A/B-Woche
        self.noch_nicht_gesetzt = True

    def __str__(self):
        return self.name

    def schueler_ok(self,datum):
        for schueler in self.schueler:
            if not schueler.klausur_setzen_ok(datum):
                return False
        return True

    def datum_ok(self,datum):
        woche = ('B' if datum.isocalendar()[1] % 2 else 'A')
        if str(datum.isoweekday()) in self.stunden[woche]:
            return True
        else:
            return False

    def setzen(self):
        self.noch_nicht_gesetzt = False

    def rausnehmen(self):
        self.noch_nicht_gesetzt = True
self.schueler ist wiederum eine Liste der Schüler des Kurses und sind Objekte der Klasse

Code: Alles auswählen

class Schueler():
   ''' Schueler, die ihre schriftlichen Kurse haben
       In wochenbelegung wird gespeichert, wie viele Klausuren bereits in der
       jeweiligen Woche geschrieben werden (max. 3)'''

   def __init__(self, name, kurse, termine):
       self.name = name
       self.kurse = kurse
       self.kursverteilung = {}
       for kurs in kurse:
           self.kursverteilung[kurs] = ''
       self.wochenbelegung = {}
       for tage, _ in termine:
           if tage.isocalendar()[1] not in self.wochenbelegung:
               self.wochenbelegung[tage.isocalendar()[1]]=0
       
   def setze_klausur(self, kursname, datum):
       self.kursverteilung[kursname]=datum
       self.wochenbelegung[datum.isocalendar()[1]] += 1

   def loesche_klausur(self, kursname, datum):
       self.kursverteilung[kursname]=''
       self.wochenbelegung[datum.isocalendar()[1]] -= 1

   def klausur_setzen_ok(self, datum):
       return self.wochenbelegung[datum.isocalendar()[1]] < 3
self.stunden ist ein Dictionary der Form:

Code: Alles auswählen

GE L1 {'A': {'1': ['R208', '1', '2'], '3': ['R208', '1', '2'], '4': ['R208', '7', '8']}, 'B': {'1': ['R208', '1', '2'], '3': ['R208', '1', '2']}}
Da wir in geraden (A-Woche) und ungeraden (B-Woche) leicht unterschiedliche Stundenpläne haben, ist das dict folgendermaßen zu lesen:
Der Geschichts-LK 1 hat z.B. in der A-Woche am Montag('1') in Raum 208 die 1.+2.Stunde Unterricht.

Außerdem generiere ich ein dict "termine", dass als keys alle Wochentage in einem vorgegebenen Zeitraum als datetime-Objekte enthält und die values eben Listen sind, in die die Kurse geschrieben werden, die an dem jeweiligen Tag Klausur schreiben.

Mein erster Versuch war es mit einem Backtracking Algorithmus anzusetzen, jedoch scheitere ich schon daran wirklich alle Möglichkeiten zu erzeugen, zumal es bei ca. 50 Kursen auf 60 Tage wohl auch zu viel Möglichkeiten geben wird, also die Rechenzeit nicht innerhalb des Quartals, in dem die Klausuren geschrieben werden sollen, ausreicht ;)

Wie sähe denn so eine Heuristik aus? Zufällige Verteilungen erzeugen und nach einer vorgegebenen Zeit abbrechen?
Ich könnte die Sache ggf. noch vereinfachen, in dem ich die Kurse, die in einem Block unterrichtet werden, auch zwangsweise am gleichen Termin Klausur schreiben lassen. So wird es nämlich im Moment per Hand gemacht. Das wollte ich aber eigentlich vermeiden, da das System so relativ starr wird (aber dafür wahrscheinlich berechenbar.)

Hat jemand noch andere Ideen?
BlackJack

@EmaNymton: Anmerkungen zum bisherigen Code:

`Kurs.schueler_ok()` wäre mit `all()` ein Einzeiler.

Wenn bei ``if``/``else`` auf Basis einer Bedingung nur `True` oder `False` zurück gegeben wird, dann kann man auch gleich das Ergebnis der Bedingung selbst zurück geben, denn das ist ja selbst schon ein Wahrheitswert.

Code: Alles auswählen

    def schueler_ok(self, datum):
        return all(s.klausur_setzen_ok(datum) for s in self.schueler)
    
    def datum_ok(self, datum):
        woche = 'B' if datum.isocalendar()[1] % 2 else 'A'
        return datum.isoweekday() in self.stunden[woche]
Die leere Zeichenkette/Datum-Kombination bei `Schueler.kursverteilung` finde ich unsauber. Typen sollte man nicht auf diese Weise mischen. Für "nichts" gibt es den `NoneType` mit `None` als Wert.

Die beiden Wörterbücher in der Klasse hätte man auch mit `dict.fromkeys()` erstellen können. Ungetestet:

Code: Alles auswählen

        self.kursverteilung = dict.fromkeys(kurse, None)
        self.wochenbelegung = dict.fromkeys(
            (t.isocalendar()[1] for t, _ in termine), 0
        )
Vielleicht bringt es etwas Schüler nach Kursbelegungen zu partitionieren? Solche die jeweils die gleichen Kursauswahlen haben, braucht man ja nicht unbedingt einzeln im Programm führen.
EmaNymton
User
Beiträge: 174
Registriert: Sonntag 30. Mai 2010, 14:07

Danke für die Codeverbesserungen, werde ich übernehmen.

Die Idee mit den Schülern partitionieren ist mit Sicherheit eine Vereinfachung, was die Datenmenge angeht, wobei ich mal checken müsste, wie da überhaupt die Schnittmenge aussieht.
nezzcarth
User
Beiträge: 1634
Registriert: Samstag 16. April 2011, 12:47

EmaNymton hat geschrieben: Wie sähe denn so eine Heuristik aus? Zufällige Verteilungen erzeugen und nach einer vorgegebenen Zeit abbrechen?
Vielleicht wäre das eine interessante Anwendung für genetische Algorithmen, oder andere aus der Natur entlehnte Verfahren. So auf den ersten Blick scheint dieser Ansatz in der Vergangenheit zumindest für Studenplanerstellungen verfolgt worden zu sein.
Benutzeravatar
pillmuncher
User
Beiträge: 1484
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

Ein paar Anmerkungen:

Zum Stil:

Code: Alles auswählen

class Foo():
...
Die Klammern hier bewirken grade mal gar nichts. Du kannst sie weglassen. Oder, falls du Python < 3 verwendest, lass sie stehen und schreib das Wort object dazwischen. Dann bekommst du eine New Style Class. Vermutlich möchtest du das.

Accessor-Methoden sind nicht pythonisch. Also dies hier:

Code: Alles auswählen

    def __init__(self, name, schueler, stunden):
        ...
        self.noch_nicht_gesetzt = True

    def setzen(self):
        self.noch_nicht_gesetzt = False

    def rausnehmen(self):
        self.noch_nicht_gesetzt = True
Na gut, es sind nicht wirklich Accessoren, da ja kein Wert übergeben oder abgefragt wird. Ich bezweifle trotzdem den Wert dieser Art der Programmierung. Für mich sieht sowas immer danach aus, als wolle jemand eine Art Haut oder Isolierschicht um die Interna einer Klasse wickeln, um diese vor der bösen Welt zu bewahren. Ich persönlich finde das - gerade in Python - unnötig. Es verkompliziert die Programmlogik, ohne wirklichen Gewinn, da ja folgendes immer noch möglich ist:

Code: Alles auswählen

k = Kurs(...)
k.noch_nicht_gesetzt = 'hallo'
Außerdem finde ich es immer etwas sonderbar, wenn ich Code mit Verneinungen im Namen lesen muss. Oder anders ausgedrückt: warum beim Namen stehen bleiben? Man kann sie wunderbar zur code obfuscation benutzen:

Code: Alles auswählen

If not self.noch_nicht_gesetzt != False:
    ...
Da muss man viel zu viel nachdenken. Mach es lieber so:

Code: Alles auswählen

    def __init__(self, name, schueler, stunden):
        ...
        self.gesetzt = False
Solltest du irgendwann einmal feststellen, dass bei jeder Zuweisung mehr Code (zB. zur Validierung oä.) benötigt wird, ändere es mittels property:

Code: Alles auswählen

    def __init__(self, name, schueler, stunden):
        ...
        self._gesetzt = False  #  der Unterstrich an Anfang markiert es als privates Attribut.

    @property
    def gesetzt(self):
        return self._gesetzt

    @gesetzt.setter
    def gesetzt(self, value):
        if value in (True, False):
            self._gesetzt = value
        else:
            raise ValueError('Mann Alter, hier werden nur boolean values akzeptiert, aber nicht %s!!!' % str(value))
Verwenden tut man es dann so:

Code: Alles auswählen

k = Kurs(...)
print k.gesetzt
k.gesetzt = True
print k.gesetzt
k.gesetzt = 'hallo'
Ergebnis:

Code: Alles auswählen

False
True
Traceback (most recent call last):
  File "stdplankurs.py", line 23, in <module>
    k.gesetzt = 'hallo'
  File "stdplankurs.py", line 14, in gesetzt
    raise ValueError('Mann Alter, hier werden nur boolean values akzeptiert, aber nicht "%s"!!!' % str(value))
ValueError: Mann Alter, hier werden nur boolean values akzeptiert, aber nicht "hallo"!!!
Verwende die Standard Lib, dafür ist sie da. Statt

Code: Alles auswählen

    def schueler_ok(self,datum):
        for schueler in self.schueler:
            if not schueler.klausur_setzen_ok(datum):
                return False
        return True
mach es lieber so:

Code: Alles auswählen

    def schueler_ok(self, datum):
        return all(schueler.klausur_setzen_ok(datum) for schueler in self.schueler)
Auch hier wird Verneinung vermieden: man muss nicht fragen, welche Eigenschaft allen Schüler nicht fehlt.


Nun zur Programmstruktur:

Kurs.__init__() erwartet eine Liste von Schülern, also von Objekten der Klasse Schueler, die folglich bereits erzeugt worden sein müssen, bevor ein Kurs-Objekt erzeugt werden kann. Schueler.__init__() erwartet eine Liste von Kursen, also Kurs-Objekten, die folglich bereits erzeugt worden sein müssen, bevor ein Schueler-Objekt erzeugt werden kann. Du siehst das Problem?

[EDIT] Gerade sehe ich, dass in Schueler.__init__() zwar eine Referenz auf die Liste der Kurse gespeichert wird, die Kurse aber erst später verwendet werden. Die Liste kann also zu diesem Zeitpunkt noch leer sein. Damit ist mein letzter Punkt hinfällig. Ich würde es trotzdem auslagern, so wie unten beschrieben. [/EDIT]

Die Lösung: m:n-Beziehungen als eigenständige Objekte verwalten, zB. als Menge von Paaren (Schueler, Kurs) oder einfach als Zuordnung von Schülern zur Liste der Kurse, die sie belegt haben:

Code: Alles auswählen

from collections import defaultdict

schueler_kurse = defaultdict(list)  #  Schueler --> Kurse
for schueler in schuelern:
    for kurs in kursen:
        if schueler hat diesen kurs belegt: # diese Daten irgendwo herholen
            schueler_kurs[schueler].append(kurs)
Das bringt einige Vorteile. ZB. den, dass man nicht mehr die Berechnungen für jeden einzelnen Schüler vornehmen muss, sondern bloß noch für die Fächerkombinationen, die die Schüler gewählt haben, wobei es ja sein kann, dass mehrere Schüler dieselben Kurse besuchen. Das kann man dann, das o.s. Programm vorausgesetzt, so machen:

Code: Alles auswählen

faecher_kombis = set(sorted(kurse) for kurse in schueler_kurse.itervalues())
Danach kann man dann für jedes Element dieser Menge alle Kombination von möglichen Terminen berechnen, die man dann bloß noch gegen jede andere Kombination von Terminen filtern muss, und was übrig bleibt, sind die global möglichen Termine aller Klausuren. Beachte bitte die Ironie, die in den Worten "bloß noch" oben steckt.

Ich habe bei alldem noch gar nichts von Klassen geschrieben, weil ich der Überzeugung bin, dass sich die statische Struktur eines Programms (Klassen und Module) nach den algorithmischen Erfordernissen richten sollte, nicht die Logik nach der Klassenstruktur.


Gruß,
Mick.
In specifications, Murphy's Law supersedes Ohm's.
EmaNymton
User
Beiträge: 174
Registriert: Sonntag 30. Mai 2010, 14:07

@pillmuncher u.a.: Danke für die Codeverbesserungen, ich bin da irgendwie immer noch sehr an Java orientiert und werde versuchen meinen Code pythonischer zu gestalten.

@nezzcarth: Danke für den Link, das sind glaube ich genau die Alternativen, die ich suche. Werde mich da mal einlesen.

Da heute unser Server in der Schule hardware-technisch abgeraucht ist, habe ich wohl erstmal jetzt wieder ne neue Aufgabe vor mir und damit eher weniger Zeit an diesem Projekt zu arbeiten :cry:

Wenn ich mich dann für eine Lösung entschieden habe und diese ans Laufen gebracht habe, werde ich mich aber nochmal melden.

Vielen Dank erstmal bis hierhin, finde das Forum hier von der Kompetenz unschlagbar!
Antworten