[Algoritme] Detectie tijd optimalisatie

[El_kingo]

Beste mede-tweakers!

Ik zit met het volgende probleem:
(ik heb het originele probleem even omgeschreven naar iets dat (wellicht) interessanter is om hier te bespreken, maar de strekking blijft hetzelfde)

Stel ik heb een lijst van computers in een (gesloten) netwerk en ik weet van elke computer hoe lang het duurt tot deze besmet is met een virus (gemeten vanaf het tijdstip dat het virus voor het eerst op het netwerk aanwezig was (de index-case)). Deze lijst is tot stand gekomen d.m.v. simulaties van zo'n computer netwerk.
Stel ik heb in totaal 5 simulaties van een netwerk van 5 computers dan zou dat bestand er als volgt uit kunnen zien:
(eerste rij is de computer ID, elke volgende rij is een simulatie, de getallen stellen de tijd voor tot besmetting (een 0 betekend een index case)

comp ID:  1  2  3  4  5  
          2  0  4  1  2
          3  4  5  0  1
          9  6  0  2  4
          2  4  3  5  0
          0  1  3  4  9

Stel dat we maar een x aantal computers zouden kunnen monitoren, dan is het belangrijk om te weten welke computers ik dan het beste (in termen van minimaliseren van de detectie tijd) aan mijn lijstje van te monitoren computers zou moeten toevoegen.

Nu wil ik weten voor x = 1 tot N computers (N=totaal aantal computers in netwerk, 5 in dit geval) in mijn lijst wat de beste volgorde is om computers toe te voegen aan mijn monitor-lijst om zo de detectietijd te minimaliseren.

Voor het gegeven bestand is het makkelijk te doen:
De eerste computer die we toevoegen is diegene die gemiddeld (over alle simulaties) de kortste infectietijd heeft, dat is dus computer 4 (gem. tijd = 2.4)
Daarna moet de computer worden toegevoegd die tezamen met de al toegevoegde computer(s) de detectie tijd minimaliseert: per simulatie bekijk ik welke van de 2 tijden het kleinst is, deze tijd stop ik in een tijdelijke nieuwe lijst, en bereken de gemiddelde detectie tijd,en ik herhaal dit voor alle overgebleven computers en vind zo de beste combinatie.

Toegepast op de voorbeeld data:
we hebben al computer 4, stel ik voeg daar computer 1 aan toe dan neem ik het telkens het minimum van:

min(1,2) = 1
min(0,3) = 0
min(2,9) = 2
min(5,2) = 2
min(3,0) = 0

mijn nieuwe gemiddelde tijd voor de ze combi is dus: 1. ((1+0+2+2+0)/5)
Dit kun je doen voor de combi's 4&1 (hierboven), 4&2, 4&3 en 4&5. De beste oplossing is dan de combi 4&1 (de overige gemiddelden zijn: 1.4,1.4,2.4,1.4).
Dit kun je daarna herhalen voor de overgebleven computers en uiteindelijk is je detectie tijd 0 als alle computers zijn toegevoegd (uitgaande van perfecte detectie enz. enz).
(de uiteindelijke beste volgorde is (4,1,3,5,2) mocht iemand het willen narekenen)

Voor kleine aantallen is dit allemaal prima door te rekenen (tot N=2000 en 520000 simulaties gaat het nog), maar voor grotere aantallen duurt dit gewoon ontzettend lang aangezien het een brute force methode is om een globaal optimum te vinden. (alles is geprogrammeerd in c++, maar dat doet verder niet zo ter zake).

En dat is dus het punt waar ik jullie hulp kan gebruiken!
Kan ik dit verder optimaliseren?
(ook totaal andere algoritmes zijn welkom, zolang de uitkomst maar hetzelfde is)

Bij voorbaat dank ! (In ieder geval al voor het lezen van de hele tekst!)

[pedorus]

Even een ander voorbeeld, met de data van pc 1 en 2 wat aangepast:

comp ID:  1  2  3  4  5  
          0  9  4  1  2
          9  0  5  0  1
          9  9  0  2  4
          9  0  3  5  0
          0  9  3  4  9

Makkelijk om te zien dat je nog steeds computer 4 als eerste toevoegt. Maar stel dat je 3 computers kan monitoren, waarom zou je dan computer 4 willen monitoren?

[NMe]

Interessanter dan een gemiddelde is in dit geval, denk ik, een mediaan. Stel het duurt voor een bepaalde computer steeds 1 <eenheid> maar er is één test waarin hij 1000 <eenheden> nodig heeft. Het gemiddelde is dan 200 terwijl de mediaan gewoon 1 is.

Dat gezegd hebbende: in welke vorm heb je deze data? Gezien de aantallen die je noemt heb je vast een database. Daar kun je toch redelijk eenvoudig gemiddelden (en zelfs die mediaan) uit halen? Vervolgens heb je één simpele sortfunctie nodig die gewoon in O(n) kan.

[El_kingo]

pedorus schreef op dinsdag 05 november 2013 @ 17:39:
Even een ander voorbeeld, met de data van pc 1 en 2 wat aangepast:

comp ID:  1  2  3  4  5  
          0  9  4  1  2
          9  0  5  0  1
          9  9  0  2  4
          9  0  3  5  0
          0  9  3  4  9

Makkelijk om te zien dat je nog steeds computer 4 als eerste toevoegt. Maar stel dat je 3 computers kan monitoren, waarom zou je dan computer 4 willen monitoren?

Ok, laat ik mij anders proberen uit te drukken:
elke computer die je moet monitoren kost geld, dus dan wil je graag gaan optimaliseren, om dit inzichtelijk te maken kun je bijvoorbeeld kijken naar een grafiek met op de x-as het aantal computers dat je toevoegt aan je lijst en op de y-as de detectie tijd als je x computers toevoegd. Mijn algoritme is op zoek naar de beste volgorde van die lijst.

Is dit duidelijker?

NMe schreef op dinsdag 05 november 2013 @ 17:50:
Interessanter dan een gemiddelde is in dit geval, denk ik, een mediaan. Stel het duurt voor een bepaalde computer steeds 1 <eenheid> maar er is één test waarin hij 1000 <eenheden> nodig heeft. Het gemiddelde is dan 200 terwijl de mediaan gewoon 1 is.

Dat gezegd hebbende: in welke vorm heb je deze data? Gezien de aantallen die je noemt heb je vast een database. Daar kun je toch redelijk eenvoudig gemiddelden (en zelfs die mediaan) uit halen? Vervolgens heb je één simpele sortfunctie nodig die gewoon in O(n) kan.

Ja, je hebt gelijk, de mediaan kan veel interessanter zijn, maar voor dit probleem is het minder van belang of ik de mediaan of het gemiddelde gebruik voor de eerste computer.

Wat betreft de vorm van de data: het is een csv file. Uiteraard kan die gemakkelijk in database vorm gegoten worden. Maar het gaat mij niet om de gemiddelden per computer, het is een soort van "greedy algoritme" wat steeds de beste combinatie zoekt als er een computer toegevoegd wordt.
M.a.w. als er een computer aan de al bestaande lijst toegevoegd zou mogen worden, welke is dan het beste om de gemiddelde detectie tijd te minimaliseren?

Mocht het nog niet duidelijk zijn kan ik wel het eerste voorbeeld helemaal uitwerken...

[NMe]

Hoe is de tabel in die CSV geroteerd? Krijg je één rij per test met daarin een kolom per computer? Of krijg je één rij per computer met daarin een kolom per tekst? In het laatste geval kun je natuurlijk meteen een sortering uitvoeren tijdens het inlezen van de file.

Het probleem dat je hebt is dat je niet kan bepalen welke computer dé beste keus is zonder alle gemiddelden te berekenen en de computers op volgorde te zetten. De enige afkortingen die je daar gaat kunnen maken zijn door het nemen van shortcuts d.m.v. best guesses, en daarvoor moet je je data al snel in een dermate andere vorm gieten dat je net zo goed meteen de "goeie" manier kan toepassen.

[Grijze Vos]

Hoe goed doet jouw berekening het t.o.v. gewoon de gemiddeldes nemen van alle machines en de machines met de beste gemiddeldes te nemen?

Wat je ook zou kunnen doen is naast een X aantal (zegge 25%) machines met het beste gemiddelde te nemen, en dat aan te vullen met machines met een acceptabel gemiddelde, maar een hoge variantie. Dat zou ook best eens goede resultaten kunnen geven.

Wat ook stiekem best wel eens goede resultaten zou kunnen geven is een gerandomised algoritme, maar dan moet je wel geen historische gegevens willen bijhouden, dan heb je niks aan zoiets.

Uiteraard voor alle opties geldt: uitrekenen.

[pedorus]

El_kingo schreef op dinsdag 05 november 2013 @ 18:11:
Ok, laat ik mij anders proberen uit te drukken:
elke computer die je moet monitoren kost geld, dus dan wil je graag gaan optimaliseren, om dit inzichtelijk te maken kun je bijvoorbeeld kijken naar een grafiek met op de x-as het aantal computers dat je toevoegt aan je lijst en op de y-as de detectie tijd als je x computers toevoegd. Mijn algoritme is op zoek naar de beste volgorde van die lijst.

Is dit duidelijker?

Dit lijkt me niet fair. Uit je grafiek lijkt het dan in mijn voorbeeld dat je 4 of 5 computers moet monitoren om supersnel te zijn, terwijl het echte optimum al bij 3 computers bereikt kan worden.

Er bestaat namelijk geen 'optimale volgorde', welke computers je het beste kan selecteren is afhankelijk van hoeveel computers je mag selecteren. Beter zou dus een grafiek op basis van zo goed mogelijke selecties van computers zijn voor bepaalde waarden van x. (Vanwege overeenkomsten met het set cover probleem zijn die selecties waarschijnlijk alleen mogelijk op basis van benadering.)

Afgezien daarvan lijkt het me meer een implementatie issue; opslaan van tussenberekeningen zoals huidige som per computer, goede volgorde in arrays hanteren, profiler gebruiken, wellicht helpt een fibonacci heap, e.d.

[Verwijderd]

pedorus schreef op dinsdag 05 november 2013 @ 19:37:

Er bestaat namelijk geen 'optimale volgorde', welke computers je het beste kan selecteren is afhankelijk van hoeveel computers je mag selecteren.

Precies dit, ja.

Zoals ik het lees lijkt het alsof de topicstarter het idee heeft dat je eerst 'de beste' computer uit kiest, en vervolgens de 'op een na beste' computer.

Maar dit is een flawed aproach. Stel dat je een webshop hebt in nederland, en je wilt 1 warenhuis neerzetten waar vanaf je onderdelen kan versturen met minimale transport tijd. Waar zet je dat warenhuis neer? In Utrecht natuurlijk. Maar stel nu dat je 2 warenhuizen neer kon zetten, zou je dan nog steeds één warenhuis in Utrecht plaatsen?

Dit probleem staat bekend als het wharehouse location problem, Wikipedia: Facility location op wikipedia. Dat is een NP-hard probleem, en vertoont gelijkenissen met wat jij wilt bereiken.

[KopjeThee]

Een optimale combinatie van computers vinden is een lastig probleem. Ik ken de concrete situatie niet, maar misschien helpt het als je in het begin alle computers verwijdert waarvoor geldt dat er een andere computer is die in alle simulaties eerder (of gelijk) was. Die wil je nooit selecteren.

Daarna kan je natuurlijk allerlei optimalisatie technieken uit de kast halen. Misschien een genetisch algoritme o.i.d. Elk individu is een combinatie van computers. De fitness is eenvoudig te bepalen. De operatoren zijn eenvoudige mutaties in de samenstelling van de set van computers van een individu, of je pakt 2 individuen en wisselt onderling computers uit.

[ Voor 47% gewijzigd door KopjeThee op 08-11-2013 09:26 ]