Spark of Life

In het Java Magazine van april 2015 heeft Bas in een artikel toegelicht hoe Evolutionaire Algoritmen oplossingen kunnen vinden voor lastige problemen (zie www.nljug.org/databasejava/evolutionaire-algoritmen/). Met behulp van een implementatie in Java werd het Traveling Salesman Problem gebruikt om aan te tonen hoe effectief en efficiënt Evolutionaire Algoritmen zijn in het vinden van (sub)optimale routes voor dit ogenschijnlijk simpele probleem. Na het lezen van dit artikel dacht Niels (terecht): dit kan beter… met Spark!

Evolutionaire Algoritmen

Om hetzelfde vertrekpunt te hebben, lichten we kort toe wat de strekking van het oorspronkelijke artikel was. De natuur is altijd al een grote bron van inspiratie geweest voor (software) engineers en de basis van Evolutionaire Algoritmen begint bij evolutie. Evolutie komt voort uit een aantal zeer krachtige mechanismen, die je als software engineer ook kunt gebruiken. Wat zijn die krachtige mechanismen ook alweer en hoe gebruiken we ze in Evolutionaire Algoritmen?

Natuurlijke selectie is één van de drijfveren achter evolutie en vindt plaats op het moment dat een groep levensvormen met de drang tot voortplanting moet concurreren om een beperkte hoeveelheid resources in dezelfde omgeving. Natuurlijke selectie houdt in dat de individuen, die het best concurreren voor de resources in de omgeving (degenen die de beste fitness hebben) lang genoeg overleven om te kunnen reproduceren.

Tijdens het reproduceren vindt recombinatie plaats. Dit houdt in dat beide ouders de helft van hun DNA doorgeven, dat vervolgens gecombineerd wordt en het DNA vormt van het kind. De combinatie van eigenschappen van de ouders kan ervoor zorgen dat het kind beter of minder kan concurreren voor de resources dan de ouders. Tijdens het recombinatie-proces kan ook een "foutje" optreden (mutatie), waardoor er een ander stuk DNA wordt doorgegeven dan één van de ouders gaf. Dit kan desastreuze gevolgen hebben voor het kind, omdat het ervoor zorgt dat het kind niet meer levensvatbaar is. Anderzijds kan het ook de fitness van het kind positief beïnvloeden door het ontstaan van een goede, nieuwe eigenschap.

Door de combinatie van deze mechanismen zorgt evolutie over tijd ervoor dat individuen steeds beter aangepast zijn aan de omgeving. Zie de omgeving als het probleem en het individu als een (suboptimale) oplossing voor dat probleem. Evolutie kan dan gebruikt worden om de populatie (en dus de individuen) te laten evolueren naar betere oplossingen. Hierdoor kunnen we complexe problemen voor ons laten oplossen. Een voorbeeld van zo’n complex probleem is het Traveling Salesman Problem.

 

Use case: Pakketbezorging als Traveling Salesman Problem

Het Traveling Salesman Problem behoeft enige vorm van verbeelding. Om dat makkelijker te maken, nemen we het voorbeeld van een pakketbezorger. Die moet een uitzonderlijk lange route afleggen in een enkele werkdag. Hij wil dus graag de kortste route nemen, die alle huizen aandoet waar pakketjes bezorgd moeten worden. Als je n huizen moet bezoeken, dan zijn er (n-1)! mogelijke routes, die je kunt nemen. Bij vier huizen valt dit nog mee (3 x 2 x 1 = 6), maar bij 31 huizen heb je het al over ongeveer 100.000.000.000.000.000.000.000.000.000.000 mogelijke routes.

Pseudo-code Evolutionaire Algoritmen

Eigenlijk is de pseudo-code achter Evolutionaire Algoritmen niet meer dan je in Listing 1 kunt vinden. Het oorspronkelijke artikel geeft zowel uitleg over de pseudo-code als een voorbeeld implementatie in Java. Aangezien dit artikel vooral gaat over de Spark implementatie beperken we ons hier even tot een korte samenvatting van de uitleg.

 


INITIALISEER populatie met willekeurige kandidaat oplossingen
EVALUEER elke kandidaat
WHILE ( TERMINATIE CONDITIE niet bereikt) {
            1. SELECTEER ouders
            2. RECOMBINEER ouderparen
            3.  MUTEER kinderen (met een bepaalde kans)
            4. EVALUEER nieuwe kandidaten
            5. SELECTEER kandidaten voor de volgende generatie
}

Listing 1

Het algoritme begint met het initialiseren van een populatie met random kandidaten en een evaluatie van elke kandidaat in die populatie. Kandidaten zijn in het geval van het Traveling Salesman Problem mogelijke routes, die de bezorger kan nemen. Hiermee is de populatie effectief een lijst met routes. We beginnen dus met een lijst met willekeurige routes. De evaluatie van een kandidaat (de fitness) is simpelweg de totale afstand, die de route oplevert, bijvoorbeeld 42 km.

Die willen we graag minimaliseren. Grote kans dat de optimale route niet tussen de initiële populatie zit, dus we moeten nog iets meer doen. Daar kunnen we de concepten uit de Evolutie voor gebruiken, die aan het begin van dit artikel staan beschreven: fitness (evaluatie), recombinatie, mutatie en natuurlijke selectie. Die komen in het algoritme in Listing 1 terug en wat er effectief gebeurt is het volgende.

Zolang we willen dat ons algoritme doorgaat (de while; dit kan aantal iteraties zijn of bijv. tijd):

?Selecteren we de ouders die mogen paren (ouderselectie);

  • Recombineren we deze;

?Laten met een bepaalde kans mutatie optreden bij de nieuwe kandidaten;

  • Evalueren onze nieuwe kandidaten;

?Selecteren uiteindelijk welke kandidaten uit de gehele nieuwe populatie door mogen naar de volgende ronde (natuurlijke selectie).

Door de recombinatie en mutatie stappen krijgen we nieuwe kandidaten, die potentieel beter zijn dan hun ouders. Als we hier lang genoeg mee doorgaan, kunnen we de optimale route (op een relatief snelle manier) benaderen.

Vervolgstap

In het oorspronkelijke artikel werd een Java implementatie toegelicht, die single threaded door dit algoritme liep. Voor de rest van dit artikel is het minder belangrijk om te weten hoe deze afzonderlijke concepten zijn geïmplementeerd in Java, maar dat je een beeld hebt bij hoe het algoritme conceptueel werkt. Als je toch graag meer wilt weten, kun je het oorspronkelijke artikel er nog eens bij pakken (www.nljug.org/databasejava/evolutionaire-algoritmen/). De oorspronkelijke implementatie werkte goed en snel, zeker bij routes tot zo’n 25-30 huizen, maar als we echt wil schalen dan hebben we zwaarder geschut nodig.

Concurrent Traveling Salesman

Met het immer groeiende aantal locaties in Nederland is het de hoogste tijd om de performance van onze implementatie onder de loep te nemen. Ons single threaded algoritme maakt op dit moment gebruik van slechts een enkele core. De server van onze pakketbezorger heeft de beschikking over veel meer cores en het is zonde dat deze niet allemaal gebruikt worden. Onze volgende taak is dus het voor meerdere threads geschikt maken van het algoritme.

Zoals beschreven werkt het algoritme in iteraties met een top-X lijst van routes (de populatie). Als we dit op een parallelle manier willen uitvoeren, zullen we een manier moeten vinden om meerdere threads op deze lijst met routes te laten werken. We willen elke thread zelf het selecteren van ouders, recombineren van ouderparen, muteren van kinderen, maken van ‘verse’ willekeurige combinaties en evalueren, sorteren en selecteren van de nieuwe combinaties, sorteren uit laten voeren.

Omdat wij willen voorkomen dat de threads elkaar in de weg gaan zitten (door te inserten in een synchronized list bijvoorbeeld) gebruiken wij het fork-join model:

 

Afbeelding 1 (Bron: Wikipedia Commons)

 

Dit model houdt in dat het werk verdeeld wordt in ‘werkpakketjes’, die uitgezet worden over een aantal threads. Als deze threads voor een bepaalde tijd aan het pakketje gewerkt hebben, wordt de tussenstand verzameld en samengevoegd door de master thread. Daarna wordt dit werk wederom uitgezet, verwerkt, verzameld en samengevoegd. Onze implementatie werkt op dezelfde manier, maar in iteraties:

 

Afbeelding 2

 

Wat betreft het ‘klaar’ zijn met het werk; er zijn meerdere manier om dit in te richten. Factoren hierin zijn het aantal generaties, de verstreken tijd en of het algoritme nog met nieuwe oplossingen komt. In onze implementatie gebruiken wij, omdat er hier geen ‘beste’ keuze is, een combinatie van factoren en hebben wij een maximum gezet aan het aantal generaties en de te besteden tijd (naarmate de lijst steden langer wordt, duurt een enkele generatie berekenen ook langer). Daarnaast is er een harde limiet gezet op het aantal generaties dat geen nieuw resultaat oplevert.

Deployen op Spark

Aangezien de oplossing van onze pakketbezorger natuurlijk generiek genoeg is om als product in de markt gezet te worden, is hij hiermee de boer op gegaan. De Amerikaanse wederhelft van onze pakketbezorger, “US Parcels” (USP), heeft buitengewoon veel interesse in onze oplossing. Ook wil USP gebruik maken van hun state-of-the-art Apache Spark cluster.

Parallel processing voorbeeld

Voordat we tonen hoe we ons Traveling Salesman algoritme werkend krijgen binnen Spark zullen we eerst een simpeler voorbeeld laten zien. De “hello world” wat betreft het doen van berekeningen in parallel in Spark is het maken van een benadering van Pi:

 


JavaSparkContext sc = new JavaSparkContext("local[4]", "PiSample");


int slices = sc.defaultParallelism();

int n = 100000 * slices;

List<Integer> l = new ArrayList<>(n);

for (int i = 0; i < n; i++) {

    l.add(i);

}



JavaRDD<Integer> dataSet = sc.parallelize(l, slices);



int count = dataSet.map(i -> {

    double x = Math.random() * 2 - 1;

    double y = Math.random() * 2 - 1;

    return (x * x + y * y < 1) ? 1 : 0;

}).reduce((i1, i2) -> i1 + i2);



double pi = 4.0 * (double)count / (double)n;

System.out.println("Pi is roughly " + pi);

Listing 2

 

Wat het algoritme doet, is in essentie vergelijkbaar met het willekeurig gooien van dartpijltjes op een rond dartbord, waarbij de pijltjes alleen op het bord of in de hoeken daar net buiten (maar binnen het omvattende vierkant) terecht komen. Door het aantal pijltjes binnen de cirkel te tellen weet je het percentage ‘hits’ en dus de oppervlakte van het board.

In het voorbeeld hierboven maken wij een lijst, die wij parallelliseren. Dit levert in Spark-termen een Resilient Distributed Dataset (RDD) op. Dit is te vergelijken met een Java 8 stream: een immutable stream aan elementen waar wij operaties op uit kunnen voeren. En zoals wij een Java 8 stream kunnen parallelliseren, is dit ook hier het geval, want onderhuids gebruikt Spark hier een aantal threads voor.

Het werk wordt uitgevoerd binnen de map. Er wordt een pijl gegooid op een willekeurige x/y coördinaat. Valt deze binnen de unit circle, dan tellen wij hem mee (de map returned 1). Daarna worden in de reduce de aantallen geteld. Dit is het percentage van het totaal n, dat binnen de cirkel valt

 

Traveling Salesman op Spark

Ditzelfde principe kunnen wij toepassen op onze Traveling Salesman solver. De Spark specifieke code is nog korter dan het vorige voorbeeld:

 


Work work = Work.forCities(cities, maxDuration);
double start = work.shortest().getDistance();



for(int i = 0; i < iterations;i++) {

    double iterStart = work.shortest().getDistance();

    JavaRDD<Work> dataSet =          sc.parallelize(work.fork(sc.defaultParallelism()));



    work = dataSet.map(Work::solve).reduce(Work::combine);



    LOG.info("Iteration {} result: {}", i, formatDistance(work.shortest().getDistance()));

    if(iterStart == work.shortest().getDistance()) {

        LOG.info("No change; terminating.");

        break;

    }

}

Listing 3

 

“Work” is een pakketje werk dat uitgezet wordt naar de Spark workers. Deze bevat de huidige lijst met routes, evenals een paar handige functies om te kunnen splitsen (fork) en te kunnen samenvoegen (combine).

We beginnen met het maken van een werkpakketje vanuit een lijst steden. Als parameter wordt ook de maximale iteratietijd meegegeven. USP wil graag binnen een afzienbare tijd een resultaat hebben, ook als dat niet de kortste route is.

Binnen de for-loop zetten we meerdere malen dit werkpakketje uit in het Spark cluster. Het “work” werkpakket wordt gesplitst in een lijst pakketjes, dat omgezet wordt in een Spark RDD; dataSet. De .map in de Spark RDD roept de ‘solve’ functie aan waarbinnen het Evolutionary Algorithm aan de slag gaat. Na een dergelijke iteratie worden de resultaten van de verschillende Spark workers weer via de .combine functie samengevoegd.

Het proces stopt als het maximaal aantal iteraties bereikt is, of als een iteratie geen korter pad oplevert. Een Evolutionair Algoritme is in principe oneindig en wij gaan ervan uit dat er geen significante verbetering meer te vinden is als volgende iteraties geen kortere routes opleveren.

Voorbeeld

Het runnen van de applicatie met de default settings geeft een goed beeld van het proces; als voorbeeld:

 


> mvn clean install
> java -jar target/spark-of-life.jar

Listing 4

 

De applicatie start met default settings voor 100 steden:

 


16:00:31.562 [main] INFO  c.n.e.s.s.SparkFacade - Solving for 100 cities in 10 iterations (8000 ms max iteration duration)

Listing 5

 

Na circa 2 minuten komt hij met een resultaat:

 


16:02:27.716 [main] INFO  c.n.e.s.s.SparkFacade - Final result: 235851.83 km -> 51098.11 km (21.67%)

Listing 6

 

Hier wordt getoond hoe de initiële afstand van 235 duizend kilometer teruggebracht wordt naar 51 duizend kilometer: 22% van de beste (willekeurige) start afstand. Let wel; dit is een route met 100 steden. Een brute force aanpak zou hiervoor 99! = 9.3 * 10155 (inderdaad, een getal met 155 nullen!) combinaties af moeten werken. Ter vergelijking: het aantal atomen in het zichtbare universum wordt geschat op ongeveer 1080. De kans dat wij de optimale route hebben is erg klein, maar voor onze use case is dit “goed genoeg”.

Bovenstaand resultaat is de route voor een enkele bezorger. Een groot Spark cluster kan prima tegelijkertijd meerdere routes berekenen. Zo kan USP voor iedere bezorger in parallel een eigen optimale route berekenen.

Conclusie

Traveling salesman heeft, naast de kracht van evolutionaire algoritmen aan te tonen, een flink aantal serieuze toepassingen. Naast bezorgroutes ook bijvoorbeeld container routeringen in de haven of het ontwerpen van electronic circuit boards. Big Data is niet langer (slechts) een hype, want steeds meer bedrijven (van e-commerce tot finance) zetten technologie als Spark in om meer waarde te halen uit hun immer groeiende databases.

Tools als evolutionaire algoritmen en Spark zijn voor een developer in deze tijd daarom enorm waardevol. Spark is daarbij voor een Java developer met een beetje Java 8 Streams / Lambda ervaring eenvoudig op te pikken. Het programmeermodel, welk stuk code draait waar, is een korte studie waard, maar het grootste deel van de complexiteit – het schedulen van het werk – wordt door Spark voor je geregeld.

Wij hopen je met dit artikel geïnspireerd te hebben eens met deze beide tools aan de slag te gaan! Fork gerust de repo om mee te experimenteren en natuurlijk zijn suggesties en pull requests altijd van harte welkom.

Links

?Code:https://github.com/nielsutrecht/spark-of-life

?Artikel van Bas over Evolutionaire Algoritmen: https://nljug.org/databasejava/evolutionaire-algoritmen/

?Code oorspronkelijke artikel: https://github.com/bknopper/TSPEvolutionaryAlgorithmsDemo