Verslag Opdracht 4: Magische Vierkanten

Verslag Opdracht 4: Magische Vierkanten Stefan Schrama, Evert Mouw, Universiteit Leiden 2007-08-14

Inhoudsopgave 1 Inleiding

2

2 Uitleg probleem

2

3 Theorie

2

4 Aanpak

2

5 Implementatie

4

6 Experimenten

4

7 Resultaten

4

8 Conclusie

6

9 Referenties

6

10 Appendix: broncode

6

1

1

Inleiding

Dit is de vierde opdracht van het college Kunstmatige Intelligentie 2007 (zie [1]), genaamd Magische Vierkanten.

2

Uitleg probleem

Het is de bedoeling om met behulp van een genetisch algoritme een magisch vierkant te maken van grootte n · n. Dit betekent dus dat er vanuit een random verzameling vierkanten door middel van mutatie en samenvoeging een magisch vierkant moet worden gemaakt.

3

Theorie

Een magisch vierkant is een vierkant van grootte n · n waarbij iedere afzonderlijke rij, kolom en diagonaal allen optellen tot eenzelfde magisch getal. Dit magische getal is (n · n · n + n)/2. Er bestaan magische getallen voor n=1 en voor n>2. Voor n=1 is het magische getal 1, voor n=3 is dat 15 en voor n=4 is het 34. Een vierkant dat willekeurig gevuld wordt met de getallen 1 t/m n is doorgaans geen magisch vierkant [3]. Dat zou wel erg onwaarschijnlijk zijn! Maar wel kan berekend worden in welke mate zo’n willekeurig vierkant op een magisch vierkant lijkt. Dat noemen we ook wel de f itness. De fitness berekenen we door voor alle rijen en kolommen en de twee diagonalen te berekenen of hun som gelijk is aan het magisch getal. Elke rij, kolom of diagonaal die daaraan voldoet levert de f itness score een punt op. Door het magisch vierkant willekeurig te veranderen oftewel muteren kan de fitness groter of kleiner worden. Een methode om gestructureerd zulke mutaties door te voeren met behulp van een hoeveelheid kandidaat vierkanten (een populatie) heet een genetisch algoritme [2]. Zo’n algoritme kruist en muteert de vierkanten uit de populatie en heeft een voorkeur voor vierkanten met een hogere fitness. Na voldoende kruisen en muteren is het te verwachten dat er vierkanten “geboren” worden met een hogere fitness, en uiteindelijk misschien zelfs een volledig magisch vierkant.

4

Aanpak

Bij de start worden er een aantal (per experiment een ander aantal) random vierkanten gemaakt, bestaande uit alle getallen van 1 tot en met n2 . Vervol2

gens wordt de fitness van elk vierkant berekend en worden ze gesorteerd op fitness. Met zoveel vierkanten in de queue is er een redelijke kans op enkele vierkanten die een aardige beginfitness hebben, en mogelijke kanshebbers worden ook niet snel vergeten. Dat is belangrijk omdat de willekeurige mutaties de ranking ingrijpend kunnen veranderen, dus vierkanten laag in de queue zijn niet zomaar af te schrijven. Daarna gaat het kruisen of samenvoegen beginnen, net zolang tot het maximaal aantal samenvoegingen is bereikt. Er vinden steeds 3 samenvoegingen plaats, #1 met #2, #2 met #3 en #1 met #3. Dit samenvoegen heeft twee doelen: zoveel mogelijk veelbelovende rijen van de ouders behouden en ook om het kind zoveel mogelijk op de “vader” (het hoogste vierkant in de queue) te laten lijken, zodat het kind waarschijnlijk ook weer een hoge fitness heeft. Een willekeurige recombinatie van vader en moeder maakt een grote kans om zelf geen grote fitness te hebben; beter is het als het kind vooral op de vader of op de moeder lijkt. In de praktijk gaat dit volgens de volgende methode. Eerst worden van de beide ouders, maar eerst van de vader, alle rijen genomen die tot het magisch getal sommeren. Van deze verzameling wordt een nieuw kind samengesteld. Als het vierkant dan nog niet compleet is worden de resterende niet-magische rijen van de vader genomen. Om het kind meer kans op overleving te geven wordt er ook een herstelprocedure gehanteerd, waarbij getallen die tweemaal of vaker voorkomen willekeurig gemuteerd worden zodat alle getallen van 1 t/m n slechts n maal voorkomen in het vierkant. Dat is immers een eis aan een geldig magisch vierkant. Tevens is er na iedere reeks van samenvoegingen kans op een mutatie van het tweede en het derde vierkant. Deze vierkanten zijn immers niet voor niets nog niet op de eerste plaats in de queue, en misschien kan een willekeurige mutatie wel een vierkant met een hogere fitness opleveren die meteen aan de top kan gaan concurreren. De mutatie wordt bewerkstelligd door het omwisselen van twee willekeurige posities in het vierkant. (Het alleen veranderen van een willekeurige waarde in het vierkant zou niet goed samengaan met de herstelprocedure.) Deze mutatie is afhankelijk van een van te voren in te stellen mutatiekans. Het eerste vierkant wordt gespaard omdat het meest succesvolle vierkant niet beschadigd mag worden. Tenslotte wordt het onderste gedeelte van de queue verwijderd, omdat deze waarschijnlijk weinig kans maken. De queue blijft dus steeds even groot als het aantal vierkanten waarmee begonnen werd.

3

5

Implementatie

Zoals gewoonlijk is ook dit programma geschreven in C++. De vierkanten zijn gewone integer arrays en worden in een priority queue gezet, waarbij het vierkant met de hoogste fitness bovenaan staat.

6

Experimenten

Voor de experimenten zijn de initieel aangemaakte vierkanten en de kans op mutatie als variabelen gebruikt. Er zijn voor n=3 drie verschillende queuegroottes gebruikt, namelijk 50, 100 en 200. Voor n=3 zijn alleen initieel 50 en 100 vierkanten aangemaakt. Ook is de mutatiekans gevarieerd tussen 0 en 9.

7

Resultaten

Voor n=3 blijkt het door ons ontworpen genetische algoritme goed te werken. Ook het muteren is voor n=3 essentieel: pas als die kans hoger is dan 0,3 wordt een magisch vierkant relatief snel (<10000 iteraties) gevonden, ongeacht de hoeveelheid initi¨ele vierkanten. Voor n=4 geldt een ander verhaal. Daar lijkt het variren van de mutatiegraad nauwelijks invloed te hebben om het aantal benodigde iteraties om tot een magisch vierkant te komen. Die hoeveelheid schommelt sterk rond een miljoen iteraties, dat is een factor 100 meer dan voor n=3. Zie ook figuur 1 en 2.

4

Figuur 1: n=3

Figuur 2: n=4

5

8

Conclusie

Het lijkt er sterk op dat de mutatiegraad een belangrijke rol speelt in het sneller tot stand komen van een magisch vierkant. De cijfers bij n=4 lijken niet zoveel te zeggen, maar dit komt vooral door de maximum iteraties van 2.000.000. Die hebben wij ingesteld om de rekentijd in te perken, daar het experiment anders onuitvoerbaar zou worden (we hebben een Core 2 Duo al een heel weekeind laten rekenen voor de huidige resultaten). De cijfers voor n=3 zeggen eigenlijk al genoeg: hoe groter de kans op mutatie, hoe sneller het magische vierkant gemiddeld wordt gevonden. Dat ligt natuurlijk ook voor de hand, omdat een vierkant dat nog geen magisch vierkant is nu eenmaal moet muteren om mogelijk een magisch vierkant te worden. Een mogelijk vervolgonderzoek zou zich dan ook kunnen richten op het slimmer toepassen van mutaties, bijvoorbeeld het agressief muteren van vierkanten die lager in de queue zijn beland. Als daarmee winst geboekt kan worden, dan zouden magische vierkanten voor n=4 ook sneller gevonden moeten kunnen worden. Ons huidige gemiddelde van een miljoen iteraties voor die categorie is namelijk wel wat aan de hoge kant.

9

Referenties

[1] Website coll ege Kunstmatige Intelligentie, Universiteit Leiden: http://www.liacs.nl/\~kosters/AI [2] Stuart J. Russell en Peter Norvig: Artificial intelligence, A modern approach (second edition, Prentice Hall, 2003). Met name pagina 116-119 over genetische algorithmen. [3] Meer over magische vierkanten op Wikipedia: http://nl.wikipedia.org/wiki/Magisch_vierkant

10

Appendix: broncode

Dit is de broncode van het gebruikte programma: // // // //

magisch.cpp magisch vierkant maken van n bij n met behulp van genetische algoritmen leeropdracht bij Kunstmatige Intelligentie

// Leiden Institute for Advanced Computer Science // 2007-05-10

6

// Evert Mouw || S 0332291 || [email protected] | [email protected] // Stefan Schrama || S 0305715 || [email protected] #include #include #include using namespace std; // magisch vierkant van n bij n #define n 4 int magisch(){ return ( n*n*n + n ) /2; } class bordje { public: int velden[n][n]; int fitness; bordje * vorige; bordje * volgende; void calcfitness(); bool isgezondgen(int rij); void print(); void vulrandom(); void muteer(); int genees(); void hersorteer(); bordje(); // constructor bordje(const bordje& b); };

// copy constructor

bordje * beginvanqueue; bordje::bordje() { // CONSTRUCTOR // voor de zekerheid alle velden op nul zetten int hori, vert; for (vert=0; vert
7

for (hori=0; horifitness = -1; hulp->vorige = NULL; hulp->volgende = NULL; // beginpunt instellen beginvanqueue = hulp; } void bordjetoevoegen(bordje * toetevoegen) { // GA BORDJE INVOEGEN, HOOGSTE FITNESS BLIJFT BOVENAAN bordje * kopie = new bordje(* toetevoegen); bordje * huidig; bordje * vorige; bordje * volgende; huidig = beginvanqueue; if ( kopie->fitness > beginvanqueue->fitness ) { kopie->volgende = huidig; kopie->vorige = NULL; beginvanqueue = kopie; huidig->vorige = kopie; } else { while ( kopie->fitness <= huidig->fitness ) { vorige = huidig; huidig = huidig->volgende; } vorige->volgende = kopie; kopie->volgende = huidig; huidig->vorige = kopie; kopie->vorige=vorige; } } int bordje::genees() { // GENEESPOGING VOOR EEN BESCHADIGD VIERKANT // MUTEERT DUBBELE GETALLEN // als een getal meerdere keren voorkomt, laat de eerste instantie dan staan // (want die is waarschijnlijk afkomstig van een succesvol gen na het // vrijen) maar muteer alleeropvolgende instanties in een willekeurig getal int i, vert, hori, teller, r; int pillen = 0; // aantal keer dat er iets gemuteerd is for (i=1; i<=n*n; i++) { teller = 0; for (vert=0; vert1) { // ga muteren // verkrijg random getal tussen 1 en n^2 r = rand() % (n*n) + 1; velden[hori][vert] = r;

8

pillen++; } } } } } return pillen; } void vrijen(bordje * vader, bordje * moeder) { // MAAKT EEN KIND UIT TWEE OUDERS int gezondgen[2*n]; // een gezond gen is een horizontale reeks die int i, j, hori; // het magisch getal oplevert int aantal = 0; bordje * kind = new bordje; // eerst de gezonde genen bepalen for (i=0; iisgezondgen(i)) { gezondgen[aantal] = i; aantal++; } if (moeder->isgezondgen(i)) { gezondgen[aantal] = i+n; aantal++; } } // nu eerst de gezonde genen recombineren if (aantal>n) aantal=n; for (i=0; ivelden[j][i] = vader->velden[j][gezondgen[i]]; } } else { // neem van de moeder for (j=0; jvelden[j][i] = moeder->velden[j][gezondgen[i]-n]; } } } // tenslotte, als het kind nog niet compleet is, ook defecte // genen recombineren, neem de genen van de vader for (i=aantal; i<(n); i++) { for (j=0; jvelden[j][i] = vader->velden[j][i]; } } // het kind helemaal genezen na de bevalling while ( kind->genees() > 0 ); // het bordje aan de queue toevoegen kind->calcfitness(); bordjetoevoegen(kind); } void bordje::vulrandom() { // VUL EEN BORDJE MET RANDOM GETALLEN int i, r; int hori, vert; bool opnieuw; int algebruikt[n*n]; // al gebruikte getallen

9

int aantal = 0; // aantal al ingevulde velden for (i=0;i
10

// door twee getallen om te wisselen int hori1, vert1; int hori2, vert2; int hulp; // verkrijg random getal tussen 0 en n hori1 = rand() % n; vert1 = rand() % n; hori2 = rand() % n; vert2 = rand() % n; hulp = velden[hori1][vert1]; velden[hori1][vert1] = velden[hori2][vert2]; velden[hori2][vert2] = hulp; // de fitness waarde is nu natuurlijk ook anders calcfitness(); // ook de plaats in de queue moet nu anders hersorteer(); } void bordje::print() { // DRUK EEN BORDJE AF int hori, vert; cout << "fitness: " << fitness << endl; for (vert=0; vertvolgende != NULL && stop<=aantal ) { cout << "node {" << teller << "}" << endl; hulp->print(); hulp = hulp->volgende; cout << endl; if (aantal!=0) stop++; teller++; } } int aantalnodesinqueue() { // TEL HET AANTAL NODES IN DE QUEUE int teller = 0; bordje * pointer = beginvanqueue; // doorloop eerst de toegestane nodes while (pointer != NULL) { pointer = pointer->volgende; teller++; } return teller; } void bordje::hersorteer() { // EEN BORDJE WEER JUIST IN DE QUEUE ZETTEN // BIJVOORBEELD NA EEN MUTATIE()

11

// stel visueel voor volgorde A=B=C=D bordje * A; bordje * B; bordje * C; bordje * D; int beginaantal = aantalnodesinqueue(); // indien een HOGERE fitness, beweeg dan omhoog while (vorige != NULL && vorige->fitness < fitness ) { A = vorige->vorige; B = vorige; C = this; D = volgende; if ( A != NULL ) A->volgende = C; C->volgende = B; B->volgende = D; if ( D != NULL ) D->vorige=B; B->vorige=C; C->vorige=A; if ( A == NULL ) beginvanqueue = C; } // indien een LAGERE fitness, beweeg dan omlaag while ( volgende != NULL && volgende->fitness > fitness ) { A = vorige; B = this; C = volgende; D = volgende->volgende; if ( A != NULL ) A->volgende = C; C->volgende = B; B->volgende = D; if ( D != NULL ) D->vorige=B; B->vorige=C; C->vorige=A; } // test om te zien of we niets kwijt geraakt zijn if ( beginaantal != aantalnodesinqueue() ) { cout << "HERSORTEER() RAAKT NODES KWIJT !!!!!!!!!!!!" << endl; } } void purgequeue(int queuelengte) { // VERWIJDER DE ONDERSTE, KANSLOZE NODES UIT DE QUEUE // WANT ANDERS LOOPT HET RAM HELEMAAL VOL // ALLEEN DE EERSTE queuelengte NODES MOGEN BLIJVEN int i; bordje * pointer; bordje * hulp; pointer = beginvanqueue; // doorloop eerst de toegestane nodes for (i=0; ivolgende; } } // nu gaan we opschonen

12

if (pointer != NULL) { while (pointer->volgende != NULL) { hulp = pointer->volgende; pointer->vorige->volgende = hulp; hulp->vorige = pointer->vorige; delete pointer; pointer = hulp; } } } int main() { cout << "De magische som is: " << magisch() << endl; int maxfit = n+n+2; cout << "De maximale fitness is: " << maxfit << endl; cout << "De mutatiekans is (0-9): "; int inv; cin >> inv; cout << endl; int i, r; bordje * test = new bordje; int maxaantal = 2000000; int mutatiekans = inv; // getal tussen 0 en 9, 0=geen, 9=altijd int initieleborden = 50; // aantal random borden waarmee begonnen wordt // random initialisatie srand((unsigned)time(0)); maakqueue(); for (i=0;ivulrandom(); test->calcfitness(); bordjetoevoegen(test); } cout << "Aantal initiele random vierkanten gemaakt: " << i << endl; i=0; while ( beginvanqueue->fitness < maxfit && i < maxaantal) { // paren, paren, paren vrijen(beginvanqueue,beginvanqueue->volgende); //nr 1 & 2 vrijen(beginvanqueue->volgende,beginvanqueue->volgende->volgende); //nr 2 & 3 vrijen(beginvanqueue,beginvanqueue->volgende->volgende); //nr 1 & 3 // er is kans op mutatie van het bord op de 2e plek in de queue r = rand() % 10 + 1; // verkrijg random getal tussen 1 en 10 if (r>=10-mutatiekans) beginvanqueue->volgende->muteer(); // er is kans op mutatie van het bord op de 3e plek in de queue r = rand() % 10 + 1; // verkrijg random getal tussen 1 en 10 if (r>=10-mutatiekans) beginvanqueue->volgende->volgende->muteer(); // schoon de queue op purgequeue(initieleborden); // hou het aantal iteraties bij i++; } cout << "Aantal iteraties: " << i << endl; cout << "(Bij " << maxaantal << " stopt ie, anders duurt het te lang.)" << endl;

13

cout << endl; cout << "--------------------------------------------------------------------" << endl; cout << "QUEUE NA EVOLUTIE (toon alleen eerste 4 van de " << aantalnodesinqueue() << ")" << endl << endl; printqueue(3); delete test; return 0; }

14