In de 3e practicumopgave bouwen we andermaal voort op de vorige opgaven. In deze opgave is het echter de bedoeling een Evolutionair Algoritme te ontwikkelen voor het oplossen van het vertex cover probleem. We maken hiertoe gebruik van de inspyred Python bibliotheek.

Downloaden en installeren inspyred

Ga als volgt te werk om inspyred geinstalleerd te krijgen:

• Zorg ervoor dat je PYTHONPATH goed is ingesteld in .bashrc: export PYTHONPATH ~/python/

  Je kunt hier ook het PYTHONPATH van een eerdere opgave gebruiken.

• Download de inspyred bibliotheek van deze locatie.
• Voer het commando easy_install --install-dir ~/python/ inspyred-1.0.tar.gz uit om inspyred te installeren. Gebruik hier de PYTHONPATH uit het .bashrc bestand. Voer het commando uit in de directory waar je inspyred gedownload had.
• 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)))
  

Opgave

Om goede oplossingen te vinden zul je verschillende uitdagingen aan moet pakken:

• de representatie van een oplossing in een genoom
• de berekening van de fitness van een oplossing
• de keuze van een evolutionair proces om deze oplossingen aan te passen
• de keuze voor een methode om met constraints om te springen

Je moet hierbij gebruik maken van de mogelijkheden van de inspyred 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

Je dient drie verschillende evolutionaire algoritmen naar eigen keuze te implementeren. Je moet hierbij tenminste twee verschillende representaties van oplossingen uitproberen; dit kunnen twee verschillende bitvectorrepresentaties zijn, of een bitvectorrepresentatie en een representatie door middel van permutaties. Je mag daarnaast 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 de keuzes beschrijft en aangeeft wat voor elk van de gekozen methodes de best gevonden oplossing is voor de gehele kaart van Europa. Probeer een verklaring te geven voor de gevonden resultaten; motiveer de keuzes die je gemaakt hebt bij implementeren van je evolutionaire algoritmen. Vermeld 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 30 november.