Computational Intelligence

Practicum 1

In het eerste practicum dient in Python een programma gemaakt te worden dat het volgende doet:

een willekeurige graaf genereren en opslaan
een graaf inlezen
het oplossen van een optimalisatieprobleem op deze graaf
grafen visualiseren

Grafen genereren

Gegeven een aantal knopen, is een random graaf een graaf waarbij de knopen op willekeurige wijze met elkaar verbonden zijn. Een voorbeeld zijn de Erdos-Renyi grafen, die als volgt gegenereerd worden voor een gegeven aantal knopen n:

de n knopen worden aanvankelijk zonder takken in een lege grafe gestopt;
voor elk paar knopen (x,y) wordt onafhankelijk met dezelfde kans p bepaald of ze met elkaar verbonden worden.

In dit proces is p een parameter. Als p=1 zijn alle knopen met elkaar verbonden; als p=0 zijn geen van de knopen met elkaar verbonden.

Maak nu een Python programma dat gegeven n en p een graaf genereert; dit programma dient een klasse voor de graaf te bevatten, een functie die de graaf willekeurig initialiseert, en een functie die ze wegschrijft in een tekstbestand; dit tekstbestand moet een lijst van takken bevatten: elke regel bevat twee getallen, die de verbonden knopen aangeven.

Grafen inlezen

Je programma moet in staat zijn om grafen in te lezen. Naast de bovenstaande, opgeslagen grafen, moet het ook in staat grafen in te lezen zoals deze te vinden zijn op deze website. In het bijzonder dien je de European economic regions dataset te downloaden en in te lezen.

Optimalisatie

Schrijf een functie die het volgende probleem exact oplost (dat gekend is als het probleem van het vinden van de kleinste vertex cover).

Gegeven graaf G

Vind een deelverzameling knopen V van de knopen in G

Zodanig dat

V zo klein mogelijk is
elke tak van G grenst aan minimaal 1 knoop in V

Dit probleem kan gezien worden als een facility allocation probleem: we willen evoor zorgen dat voor elk paar aangrenzende gebieden, ten minste eentje ervan een gewenste faciliteit heeft, terwijl we het aantal faciliteiten willen minimaliseren.

Het probleem moet exact opgelost worden: dit wil zeggen dat je programma de best mogelijke oplossing moet vinden. Een algoritme dat niet zo'n garantie geeft, is niet voldoende voor deze opgave.

De functie moet werken op de klasse van de vorige opgave. Breid hiertoe de klasse van de vorige opgave uit en plaats deze klasse in een aparte module. Aan het einde van deze stap heb je dus:

een bestand dat je graaf-klasse bevat
een script dat de graaf-klasse gebruikt om een graaf te genereren en op te slaan (parameters op de command line: p, n en een bestandsnaam)
een script dat de graaf-klasse gebruikt om het facility allocation probleem op te lossen (de parameter op de command line is de bestandsnaam)

Je dient je optimalisatieprogramma toe te passen op ten minste twee kleine, willekeurig gegenereerde grafen (5 en 10 knopen); probeer daarnaast je programma uit te voeren op de European economic regions dataset.

Theoretische opgave: een alternatief probleem is het dominating set probleem. Dit is het volgende probleem:

Gegeven graaf G

Vind een deelverzameling knopen V van de knopen in G

Zodanig dat

V zo klein mogelijk is
elke knoop in G ofwel in de gekozen verzameling V zit, ofwel grenst aan een knoop in V

Geen een voorbeeld van een graaf waarvoor de oplossing voor het dominating set probleem kleiner is dan dat voor het vertex cover probleem.

Visualisatie

Schrijf een programma voor het visualiseren van de gegenereerde graaf en de gevonden verzameling knopen. Tip: kijk hiervoor naar PyDot. Enkele voorbeelden van visualisatie door middel van Python zijn hier te vinden.

Inleveren

Je dient je code, alsmede de twee willekeurig gegenereerde grafen, per mail in te leveren. De deadline is vrijdag 23 september 2016. Het e-mail adres is s.nijssen@liacs.leidenuniv.nl.