Categorie archief: Algoritmes

Zwaartekracht

In het nieuwe examenprogramma natuurkunde, voor VWO is er aandacht voor sterrenkunde. Een goede zaak, want het antwoord op veel fundamentele vragen in de natuurkunde is te vinden in de sterren. Door de blik naar boven te richten en de straling van sterren en sterrenstelsels te onderzoeken krijgen we inzicht in de fysische processen in extreme situaties zoals hoge temperaturen en dichtheden, en in de bewegingen van de hemelobjecten.

Inzicht in sterrenkunde kan niet zonder inzicht in de zwaartekracht, de kracht die er voor zorgt dat dingen naar de aarde vallen, dat de aarde in een baan om de zon blijft en dat ons zonnestelsel om het centrum van de melkweg cirkelt. Het mooie is dat we door de introductie van sterrenkunde meteen een goed platform hebben om het te hebben over die zwaartekracht. Velen associeren zwaartekracht met sommen over kogelbanen en ballen die van torens worden geworpen.Het nadeel daarvan is dat alles uiteindelijk op aarde terechtkomt. Het is veel interessanter om situaties te onderzoeken waarin de zwaartekracht haar bindende rol in het heelal kan spelen.

Ik werd gevraagd door Jaap Vreeling, coordinator onderwijs van NOVA, of ik mee wilde denken over een simulatie die gebruikt kan worden in het onderwijs. Hij regelde een afspraak met Simon Portegies Zwart, hoogleraar computationele astronomie in Leiden. Ik kon niet laten er na dit gesprek mee te beginnen. Met behulp van algoritmes en datasets van Simon (www.nbabel.org) en de database van Jet Propulsion Lab van NASA, met de posities en snelheden van alle bekende objecten in het zonnestelsel heb ik een eerste vingeroefening gedaan. Het resultaat staat hieronder. Of klik hier voor een full screen versie.

De simulatie bevat een aantal voorbeelden: een systeem met de zon, aarde en maan, niet op schaal. Interessant is te zien dat de zon een klein beetje waggelt en dat de baan van de maan sterk varieert onder invloed van de zon. Het hele zonnestelsel is wel op schaal, tenminste, de afstanden van de objecten zijn dat. Als ik de afmetingen van de planeten ook op schaal zou maken zouden ze onzichtbaar zijn. De startposities van de planeten zijn die op 1 december, de dag dat ik ze uit de database heb gehaald. Mooi is om een planeet, bijvoorbeeld de aarde centraal te zetten en vorm van de baan te laten plotten. De lussen die je ziet verklaren waarom planeten soms in omgekeerde richting lijken te bewegen:

Je kunt zelfs zien dat Mars helderder wordt tijdens de terugbeweging, logisch, want hij staat dan dichterbij.

In de zonnestelselsimulatie heb ik ook de baan van een planetoïde opgenomen. Niet geheel toevallig die van de planetoïde “Marieke Baan“, de persvoorlichter van NOVA. Tot slot heb ik een aantal simulaties van sterrenhopen toegevoegd, gedownload van nbabel.org. Als je goed kijkt zie je dat soms een ster wegschiet, en dat er kleine deelgroepjes van sterren ontstaan.

Ik ben niet van plan de simulatie helemaal te gaan bouwen,en heb nog wel een wensenlijstje: een real-time koppeling met JPL, plotten van de baan van de voyagersondes, en meer interactiviteit, zodat leerlingen bijvoorbeeld een reis naar Mars kunnen plannen.Het zou dus mooi zijn als dit op de een of andere manier verder opgepikt wordt.

Genetische algoritmen

Het was een beetje stil op deze blog. Ondertussen ben ik aan de gang gegaan met Coffeescript, een taal die het mogelijk maakt je programma’s voor webpagina’s heel compact en toch leesbaar op te schrijven. Als je geïnteresseerd bent kun je de broncode van het programma hieronder bekijken. In dat geval weet je vast ook hoe.

Ik heb coffeescript gebruikt om inzichtelijk te maken hoe genetische algoritmen werken. Dit zijn algoritmen die gebruikt worden om oplossingen te vinden voor problemen waarbij het aantal mogelijke oplossingen zeer groot is. Denk bijvoorbeeld aan het maken van een rooster voor een school. Als je -zeg- twintig klassen hebt, die elk les moeten krijgen in twaalf vakken verdeeld over achttien lokalen, in veertig mogelijke lesuren per week is het aantal mogelijkheden enorm groot. Wel kun je eenvoudig uitrekenen of een bepaalde oplossing aan alle voorwaarden voldoet, zoals geen lokaal of docent dubbel geboekt. Ook is het mogelijk iets te zeggen over de kwaliteit van een oplossing. Je kunt zo de voorkeur geven aan zo min mogelijk tussenuren voor klassen en docenten. Door het enorme aantal mogelijkheden is het vinden van de beste oplossing vrijwel onmogelijk, daarvoor zou je alle mogelijkheden moeten doorrekenen. Met genetische algoritmen kun je goede oplossingen vinden, hoewel die dus niet noodzakelijk de beste zijn.

Het werkt als volgt:

  1. Genereer een aantal willekeurige oplossingen
  2. Gebruik die oplossingen om nieuwe oplossingen te maken. Dat kan op twee manieren: combineer twee oplossingen tot één nieuwe (seksuele reproductie) of kopieer een oplossing en breng er een kleine wijziging in aan (aseksuele reproductie met mutatie)
  3. Bereken voor elke oplossing de kwaliteit.
  4. Houd de beste oplossingen (b.v. de beste 25%) en ga terug naar stap 2

Stappen 2-4 worden herhaald totdat je tevreden bent over de beste oplossing uit je verzameling oplossingen.

Screenshot 2013-10-22 14.42.42

Ik heb dit algoritme toegepast op het handelsreizigersprobleem. (Daar ben ik overigens niet origineel in). Dit probleem vraagt naar de kortste route voor een handelsreiziger die N steden precies één keer moet bezoeken en terugkeren naar zijn beginpunt. Het aantal mogelijke routes is N!, een aantal dat zeer snel oploopt met N, waardoor het onmogelijk wordt alle routes door te rekenen.

Hieronder kun je zien hoe een genetisch algoritme probeert een goede route te vinden. Klik in het witte vlak om steden te plaatsen. Als je minimaal twee steden hebt geplaatst kun je op start drukken om een route te vinden. Na elke generatie pauzeert het algoritme even en laat de tot dan toe beste oplossing zien. Als een generatie geen verbetering geeft stopt het. Als je nog niet tevreden bent, kun je met “Verder” het algoritme nog een schop geven om het nog wat langer te proberen. Soms helpt meerdere keren schoppen.

Voortplanting gebeurt op twee manieren: seksuele voortplanting gebeurt door het eerste deel van een oplossing te knippen, uit een andere de in dit deel al bezocht steden te verwijderen en de rest aan de nieuwe oplossing te plakken. Bij aseksuele voortplanting met mutatie wordt in de kopie één stad van plaats veranderd of worden twee steden verwisseld.

Mijn implementatie is niet ideaal, en stopt vaak te snel. Dat komt doordat ik relatief weinig “kinderen” laat genereren en doordat mijn mutaties misschien te conservatief zijn. Dat merk je vooral in situaties met veel steden. In onderstaand plaatje kreeg ik het algoritme niet meer verder ondanks het feit dat er op het oog zeker verbeteringen mogelijk zijn. Deze relatief zwakke implementatie laat denk ik juist goed de principes en beperkingen van genetische algoritmes zien.

Screenshot 2013-10-22 12.43.56

Ik hoop binnenkort een versie hier te plaatsen waarmee je met de parameters (aantal generaties, wijze van voortplanting) van het algoritme kunt stoeien en de effecten op het resultaat kunt zien.

 

Mondriaan meets Fractals.

Via twitter kwam ik deze wedstrijd tegen: http://elegant.setup.nl/, en ik voelde me uitgedaagd om een algoritme te schrijven om een Mondriaan te genereren. Hier is mijn inzending:

Hoe vang je een Mondriaan in een algoritme? Een mooie uitdaging. Ik besloot om niet te proberen de Victory Boogie-Woogie na te maken, maar te proberen vlakverdelingen te genereren die van Mondriaan zouden kunnen zijn. Daarnaast is het interessant om een kleine eigen touch aan het w erk te geven.  Niet om de meester te willen verbeteren, maar omdat het interessant en leuk is. Ik ben geen kenner, wel een liefhebber, en had geen tijd me te verdiepen in de literatuur. Ik ben dus puur op eigen indrukken van de schilderijen afgegaan.

Een Mondriaan, tenminste zijn latere werk, is in essentie een verdeling van het vlak in rechthoeken. In veel werk worden die vlakken gescheiden door duidelijke zwarte lijnen, in VBW niet, daar onderscheidt een vlak zich alleen door zijn kleur.

Belangrijk in een Mondriaan is de verhouding tussen de grootte van de vlakken. Vaak zijn de grotere vlakken excentrisch maar wel dicht bij het midden geplaatst, als een soort centrale pleinen. Naar de randen toe worden de vierkanten vaak kleiner en soms langwerpiger. Bij Victory Boogie-Woogie zijn er bovendien twee verdelingen die in andere schilderijen niet voorkomen. De eerste noem ik strips, geblokte banden die de functie van een grens lijken te hebben. De tweede zijn vlakken met een zwevend, kleiner, contrasterend vlak er in. Die rechthoeken zijn altijd dicht bij een vierkant. Lengte en breedte verschillen niet veel van elkaar.

i6

Op basis hiervan kwam ik tot een algoritme:

  1. Verdeel het vlak in negen delen. De centrale rechthoek plaats je excentrisch en wordt niet verder verdeeld.
  2. Voeg de 8 vakken rond de centrale vak samen tot vier rechthoeken. Dit kan op meerdere manieren, gebruik een toevalsgenerator om te kiezen hoe.
  3. Verdeel deze vier rechthoeken opnieuw op deze wijze, met de volgende uitzonderingen:
    1. Op basis van toeval wordt een deel van de rechthoeken niet verder verdeeld.
    2. Een langgerekte driehoek kan een strip worden
    3. Een kleine rechthoek die bijna vierkant is kan een vierkant worden met een kleiner zwevend vierkant er in.
  4. In een Mondriaan wordt meestal na 1 stap niet verder onderverdeeld, maar in principe kun je oneindig lang doorgaan. Het schilderij wordt dan een fractal, een figuur waarin je oneindig lang kunt inzoomen en steeds nieuwe structuren te zien. Omdat algoritmebouwers van recursie houden is dit een mooie twist voor deze opdracht.

i4Ik heb voor zowel de Mondriaans met lijnen en primaire kleuren, als voor de wat zachtere kleuren van de Victory Boogie-Woogie een aantal “schilderijen” gemaakt met dit algoritme. De resultaten staan verspreid op deze pagina. Hieronder staat de generator zelf:  Door op ‘go’ te klikken maak je een nieuw schilderij. Als het niet bevalt maak je gewoon een nieuwe. Je kunt kiezen voor het kleurenpallet, of er lijnen moeten worden getekend en voor de diepte: hoe vaak wil je dat het algoritme rechthoeken blijft opdelen? Als je op ‘save’ drukt opent een nieuw venster met daarin een PNG-afbeelding van het schilderij dat je kunt opslaan vanuit je browser.

De broncode van het algoritme is hier te downloaden. De afbeelding hieronder is een ‘diepere’ uitvoering en in groot formaat te downloaden. En oja, als je dit leuk vindt, stem dan op me bij de wedstrijd.

VBW groot