In de 3e practicumopgave zullen we verschillende methoden vergelijken voor het oplossen van Sudoku puzzles, met aan de ene kant een complete methode (een CP systeem) en aan de andere kant een heuristische methode (een evolutionair algoritme). Voor beide methoden maken we gebruik van bestaande bibliotheken in Python; de focus ligt op het vergelijken van de verschillende methoden en het verkrijgen van een beter inzicht in de verhoudingen tussen deze methoden. Voor CP zullen we opnieuw gebruik maken van Numberjack; voor EAs gebruiken we de inspyred Python bibliotheek.

Downloaden en installeren bibliotheken

Voor het gebruik van Numberjack kunnen de instructies van de vorige practicumopgave gevolgd worden. Ga als volgt te werk om ook inspyred geinstalleerd te krijgen:

• Zorg ervoor dat je PYTHONPATH goed is ingesteld in .tcshrc: setenv PYTHONPATH ~/python/

  Je kunt hier het PYTHONPATH van een eerdere opgave gebruiken.

• Voer het commando easy_install --install-dir ~/python/ inspyred uit om inspyred te installeren. Gebruik hier de PYTHONPATH uit het .tcshrc bestand.
• Probeer een voorbeeld programma uit te voeren:

  from random import Random
  from time import time
  import inspyred
  
  prng = Random()
  prng.seed(time()) 
      
  problem = inspyred.benchmarks.Binary(inspyred.benchmarks.Schwefel(2), 
                                       dimension_bits=30)
  ea = inspyred.ec.GA(prng)
  ea.terminator = inspyred.ec.terminators.evaluation_termination
  final_pop = ea.evolve(generator=problem.generator,
                        evaluator=problem.evaluator,
                        pop_size=100,
                        maximize=problem.maximize,
                        bounder=problem.bounder,
                        max_evaluations=3000, 
                        num_elites=1)
                            
  best = max(final_pop)
  print('Best Solution: \n{0}'.format(str(best)))
  

Constraint Programming

Voor het exact zoeken naar oplossingen gebruiken we de Numberjack bibliotheek in combinatie met een CP solver. De volgende code illustreert een probleem met een all different constraint. De code maakt gebruik van de Mistral solver.

from Numberjack import *

vars = [Variable(1,4) for val in range(3)]
model = Model() 
model.add ( AllDiff ( vars ) )
solver = model.load('Mistral')

print solver.solve()
print ' '.join([str(v) for v in vars])

Maak eerst een programma dat een Sudoku puzzle inleest en een oplossing hiervoor berekent door middel van CP. Sudoku puzzles kunnen van Project Euler gedownload worden. Zorg ervoor dat je het bestand sudoko.txt kunt inlezen en dat je gemakkelijk een puzzle in dit bestand kunt selecteren.

Evolutionaire Algoritmen

Als alternatieve methode maken we gebruik van een genetische algoritme. Dit betekent dat je verschillende uitdagingen aan moet pakken:

• de representatie van puzzle oplossingen in een genome
• de berekening van de fitness van een puzzle
• de keuze van een evolutionair proces om deze oplossingen aan te passen

Je moet hierbij gebruik maken van de inspyred bibliotheek. Je vindt een uitvoerige handleiding van deze bibliotheek op de webpagina van de bibliotheek. Om zelf een probleem op te lossen zul je tenminste de evolve functie aan moeten roepen met een eigen:

• generator, die een populatie initialiseert
• evaluator, die een populatie evalueert
• bounder, die ervoor zorgt dat genen beperkt blijven tot acceptabele waarden.

Je kunt best dit voorbeeld aandachtig doornemen om een idee te krijgen hoe je een EA maakt met deze bibliotheek (het voorbeeld is voor het traveling salesman probleem, dat gerelateerd is aan het Hamiltonkring probleem). Ook kan kan het nuttig zijn elementen van de online tutorial door te nemen of de voorbeelden te bekijken.

Opgave

Naast de CP zoek strategie, dien je drie verschillende evolutionaire algoritmen naar eigen keuze te implementeren. Je mag zelf bepalen welke drie variaties je kiest: verschillende fitness functies, selectie, crossover... inspyred biedt vele mogelijkheden.

Naast de broncode, dien je ook een verslag te maken waarin je voor 10 Sudoku puzzles in het eerder genoemde bestand aangeeft hoe de 4 gekozen methoden zich hierop gedragen (runtime, en of een oplossing gevonden wordt). Voor elk van de 10 problemen moet je aangeven of je dit een moeilijk of makkelijke puzzle vindt - je moet kunnen argumenteren dat tenminste 4 puzzles redelijkerwijs moeilijk zijn en 4 redelijkerwijs makkelijk. Probeer een verklaring te geven voor de gevonden resultaten; motiveer de keuzes die je gemaakt hebt bij implementeren van je evolutionaire algoritmen. Vermeldt tenslotte nadrukkelijk welke parameters je gekozen hebt en hoe je tot die keuze gekomen bent.

Beoordelingscriteria voor de opgave zijn:

• de netheid van de code
• de correctheid van de code
• de diepgang van de experimenten
• de aangedragen motivaties in het verslag
• de kwaliteit van de geschreven tekst -- ook al hoeft dit niet een compleet artikel te zijn

Inleveren

Lever zowel de code als een kort verslag in. De deadline is 7 december.