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 bogen 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 oplost (dat gekend is als het probleem van het vinden van de kleinste dominating set).

Gegeven graaf G

Vind een deelverzameling knopen V van de knopen in G

Zodanig dat

V zo klein mogelijk is
elke knoop van G ofwel in V zit ofwel grenst aan een knoop in V

Het problem dient exact opgelost te worden: je programma dient de kleinst mogelijke oplossing te vinden. Een benadering is niet voldoende. Het probleem kan gezien worden als een facility allocation probleem: als bijvoorbeeld de knopen in de graaf plaatsen in een geografisch gebied zijn en de bogen aangeven welke plaatsen elkaar eenvoudig kunnen bereiken, vraagt het bovenstaande probleem essentieel om een zo klein mogelijk aantal plaatsen te kiezen om het geografisch gebied te bedienen.

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.

Visualisatie

Schrijf een programma voor het visualiseren van de gegenereerde graaf en de gevonden verzameling knopen. Tip: kijk hiervoor naar PyDot, waarvan je een werkende versie van pydot.py hier kunt downloaden; vergeet dot_parser.py echter niet. 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. Beschrijf in het commentaar van je code kort wat de uitkomst is van je algoritme op de twee gegenereerde grafen en de EER data. Neem ook commentaar op dat een korte toelichting geeft op de werking van je eigen algoritme. De deadline is vrijdag 25 september 2015. Het e-mail adres is s.nijssen@liacs.leidenuniv.nl.