Genetisch algoritme voor samenstellen van teams

[NickThissen]

Ik heb een lijstje met 42 mensen (spelers) die ingeschreven zijn voor een spel. Elke speler heeft een bepaalde rating wat in principe zijn niveau aangeeft. Een rating is gewoon een getal van ~100 (zeer slecht) tot ~8000 (zeer goed). Ik wil deze lijst spelers indelen in 21 teams van elk 2 spelers, met behulp van een genetisch algoritme om de optimale combinatie van spelers in teams te vinden.

Wellicht is een genetisch algoritme niet de beste keuze, in dat geval hoor ik graag wat beter zou zijn, maar ik vind dit ook een leuk projectje om mijn (basis) kennis over genetische algoritmen wat te vergroten, aangezien ik merk dat ik al snel vast loop.

Probleem 1: het 'encoden' van een oplossing in een genome... Voor zover ik begrijp moet (meestal?) een oplossing van een GA te coderen zijn als een string van bitjes (0110101001110) of misschien andere getallen. Ik ben hier niet te lang over ingegaan en heb wellicht al meteen de verkeerde keuze gemaakt: mijn genome is simpelweg een lijstje van de spelers op een bepaalde volgorde. De volgorde bepaald ook de teams: speler 1 en 2 zitten in het eerste team, speler 3 en 4 in het tweede team, speler 5 en 6 in het volgende team, enz. Voordat ik begin krijgt elke speler een nummer (1 t/m 42) dus zou je een oplossing/genome kunnen zien als een lijstje van deze nummers, zoals (8,18,1,32,42,...,2,9). Dit geeft dan team combinaties (8,18) en (1,32) en (32,42) , ... , en (2,9).

Probleem 2: de fitness function.
Het indelen van teams gebeurt natuurlijk aan de hand van een (aantal) criteria waar zo goed mogelijk aan voldaan moet worden. Deze criteria moeten uiteraard vertaald worden naar een fitness functie die ik in het GA kan gebruiken om te bepalen hoe goed een oplossing (21 ingedeelde teams) is. Er zijn meerdere criteria maar ik wil het niet meteen te moeilijk maken dus ik zal beginnen met een simpele, en zal later uitleggen op welke manier het nog lastiger wordt.

Alleen naar rating kijken
De makkelijkste manier om de teams te verdelen is door te zorgen dat elk team zoveel mogelijk gelijk is (qua gemiddelde rating van de twee spelers) aan de andere teams. Met andere woorden: de standaard deviatie van de gemiddelde ratings van een team (vergeleken met de gemiddelde rating van alle teams) moet zo klein mogelijk zijn. Een oplossing waarbij er een team met een rating van 8000 is en een team met een oplossing van 200 is dus heel slecht, veel beter is alle teams gemiddeld tussen 3500 en 4500 bijvoorbeeld.
De fitness functie hiervoor leek voor de hand te liggen: ik gebruik de reciproke van de standaard deviatie direct als fitness. Hoe hoger de fitness, hoe lager de std dev, hoe beter de teams met elkaar gematched zijn.

Rekening houden met auto keuze
Het spel in kwestie is een race spel, en spelers kunnen een van twee beschikbare auto's kiezen om mee te spelen. Elk team moet uit een auto A en een auto B bestaan (dus niet teams met twee keer auto A of twee keer B ). Bij het inschrijven heeft iedereen zijn keuze aangegeven, echter was er ook een optie om aan te geven dat de keuze niet belangrijk is; in dat geval mag elke auto aan jou toegewezen worden.

Dit heb ik in de fitness functie proberen te bouwen door een fitness van 0 terug te geven wanneer de auto keuze van één van de gemaakte teams niet geldig is: dat wil zeggen als er een team is wat twee keer dezelfde auto heeft. Dit klinkt makkelijk maar ik zie hier wel 'gevaar' in: wellicht is er een oplossing die bijna optimaal is behalve dat een team twee keer dezelfde auto is. Deze oplossing wordt meteen weg gegooid en zal dus nooit meedoen met recombinatie. Het lijkt erop dat ik hiermee dus goeie oplossingen ga verliezen, klopt dat? Hoe voer ik dit criteria beter in?

Rekening houden met teamgenoot keuze
Ten slotte konden spelers aangeven als ze een voorkeur voor teamgenoot hadden. Hiermee hoeft niet absoluut rekening mee gehouden te worden, als het niet lukt dan hebben de spelers pech en krijgen ze een andere teamgenoot. Maar een oplossing waarbij aan alle teamgenoot keuzes voldaan is zou wel een hogere fitness moeten hebben dan eentje waarbij dit niet het geval is. Hier weet ik ook weer niet hoe ik dit in een fitness functie ga stoppen...


Probleem 3: recombinatie...
Ten slotte het belangrijkste probleem: ik heb geen idee hoe ik een recombinatie van twee oplossingen ga doen om twee nieuwe 'kinderen' te maken. Het typische voorbeeld wat ik tegenkom is dat twee genomes (weergegeven door bitjes) op een willekeurige plek 'splicen' en elkaar vervangen (ik neem aan dat jullie weten wat ik bedoel). Dit werkt echter totaal niet voor mijn genome (lijstje van spelers), als ik twee willekeurige lijstjes halverwege met elkaar ga verwisselen dan krijg ik hoogstwaarschijnlijk twee ongeldige oplossingen terug omdat er spelers 2 keer voorkomen en spelers helemaal niet meer voorkomen..?
Simpel voorbeeldje met 4 spelers ( | symbool geeft punt van recombinatie aan)

123|4
432|1
------- Resultaat:
1231 (ongeldig)
4324 (ongeldig)

Hoe ga ik twee lijstjes van spelers recombineren zodat er (1) twee geldige oplossingen uitkomen en (2) de kans 'groot' is dat de kinderen beter zijn dan de ouders (dus dat de goeie eigenschappen behouden blijven)?

Mijn recombinatie is momenteel niks anders dan random een van de twee ouders terug geven Dat wil zeggen dat er niks genetisch aan mijn algoritme is waardoor het ook niet echt goed werkt (het is nu meer een algoritme dat 10,000 random oplossingen maakt en hopelijk toevallig een goeie overhoudt).


Nogal een lange post, misschien is het wat te algemeen maar ik kom er niet meer uit. Ik snap dat het coderen van het genome en design van de fitness functie de hele clue van een GA is maar wellicht hebben jullie wat tips waarmee ik verder kan... Alvast bedankt!

[Daedalus]

offtopic:
FYI: met een pool van 42 spelers en een teamgrootte van 2, heb je in totaal 861 combinaties van spelers, iets wat makkelijk brute force door te rekenen is

[NickThissen]

Daedalus schreef op zaterdag 20 juli 2013 @ 00:36:

offtopic:
FYI: met een pool van 42 spelers en een teamgrootte van 2, heb je in totaal 861 combinaties van spelers, iets wat makkelijk brute force door te rekenen is

Daar heb je wel gelijk in ja Maar overkill is altijd leuk

Dan nog zit ik met probleem 2 natuurlijk, ik ga in ieder geval niet 861 combinaties met de hand nakijken

[GlowMouse]

Daedalus schreef op zaterdag 20 juli 2013 @ 00:36:

offtopic:
FYI: met een pool van 42 spelers en een teamgrootte van 2, heb je in totaal 861 combinaties van spelers, iets wat makkelijk brute force door te rekenen is

Neenee, het is veel meer.

code:

>> a=1; for i = 42:-2:2, a=a*nchoosek(i,2); end; a

a =

  6.6996e+044

edit: en dan nog delen door 21! dus.

[ Voor 4% gewijzigd door GlowMouse op 20-07-2013 12:05 ]

[Struikrover]

Het lijkt erop dat een genetisch algoritme zich niet heel goed leent voor jouw probleem, aangezien de filosofie erachter juist is om geen constraints te stellen en te kijken welk nageslacht het beste presteert op de door jou gestelde criteria, door een evolutionaire aanpassing van de parameters welke je zelf niet zou kunnen beredeneren.

Al kun je inderdaad een fitheitsfunctie zo definiëren dat je het als grotere fitheid beschouwd als de aangegeven voorkeuren terugkomen in je oplossing, het voelt voor mij niet als een natuurlijke oplossing voor je probleem.

Als je toch in de A.I. richting wilt programmeren, heb je al eens naar Constraint Satisfaction Problems gekeken? Deze PDF komt bijvoorbeeld uit de "a.i. bijbel" AIMA (A.I.: A Modern Approach) en beschrijft een principe dat volgens mij je probleem veel geschikter op een slimme manier kan oplossen

[Sendy]

offtopic:
Onzin

[ Voor 105% gewijzigd door Sendy op 20-07-2013 01:26 ]

[pedorus]

Ik snap sowieso niet hoe jullie op dat soort lage aantallen komen

GlowMouse schreef op zaterdag 20 juli 2013 @ 00:44:
[...]

Neenee, het is veel meer.

code:

>> a=1; for i = 42:-2:2, a=a*nchoosek(i,2); end; a

a =

  6.6996e+044

Ik snap deze berekening ook niet? Volgens mij is het 42!/2^21/21! = 13113070457687988603440625 = 1.3113E+25 (met 42! het aantal mogelijke coderingen in het eerste stukje TS dat ik gelezen heb, 2^21 een correctie voor geen volgorde binnen groepjes van 2, en 21! een correctie voor geen volgorde van de groepjes zelf.)
Rekening houdend met auto A/B maakt de volgorde binnen de groepjes wel uit, dus dan zijn er 2.750E+31 mogelijkheden.

Voor probleem 3 uit de TS, zie de verschillend opties voor een Ordered crossover en Google daar even op door, en gebruik eventueel gewoon bestaande implementaties. Kan me voorstellen dat er voor het specifieke probleem van een het indelen van personen in groepjes van 2 al volledige papers/programma's zijn.

Voor probleem 2: Afhankelijk van het doel zou ik mensen gewoon lekker zelf partners laten kiezen. Mensen die dat niet doen handmatig wat matchen op van karaktereigenschappen, daarna ranking (en daarna autovoorkeur). Eventueel kun je met handicaps werken als er te goede teams ontstaan, of (beter) gewoon soortgelijke teams tegen elkaar laten spelen. Alle problemen in een keer opgelost

[Daedalus]

pedorus schreef op zaterdag 20 juli 2013 @ 01:29:
Ik snap sowieso niet hoe jullie op dat soort lage aantallen komen

[...]

Ik snap deze berekening ook niet? Volgens mij is het 42!/2^21/21! = 13113070457687988603440625 = 1.3113E+25 (met 42! het aantal mogelijke coderingen in het eerste stukje TS dat ik gelezen heb, 2^21 een correctie voor geen volgorde binnen groepjes van 2, en 21! een correctie voor geen volgorde van de groepjes zelf.)
Rekening houdend met auto A/B maakt de volgorde binnen de groepjes wel uit, dus dan zijn er 2.750E+31 mogelijkheden.

Volgens mij maakt volgorde juist niet uit. Zoals ik het begrijp zijn er 42 spelers. Elke speler heeft een rating, een autokeuze (A, B of don't care) en een gewenste teamgenoot (optioneel). Als je alleen kijkt naar hoe je 42 spelers in teams van 2 kunt verdelen, dan zijn er 42 over 2, oftewel 42!/(2! * (42-2)!) = 861 combinaties mogelijk.

Als je dit blind toepast op je lijst met deelnemers, krijg je teams met autokeuze AA of BB, die je er uit moet filteren. Met de teams die je overhoudt, kijk je welke het dichtst bij de gemiddelde rating zit. Als je nu meer dan 21 teams overhoudt (en hopelijk niet minder), dan kun je de teams selecteren waarbij wordt voldaan aan de gewenste teamgenoot van een of beide spelers.

Dat is in ieder geval hoe ik het zou oplossen, maar wellicht zie ik wat over het hoofd

[Henk007]

Daedalus schreef op zaterdag 20 juli 2013 @ 09:47:
[...]
Als je alleen kijkt naar hoe je 42 spelers in teams van 2 kunt verdelen, dan zijn er 42 over 2, oftewel 42!/(2! * (42-2)!) = 861 combinaties mogelijk.
...
Dat is in ieder geval hoe ik het zou oplossen, maar wellicht zie ik wat over het hoofd

Dat is toch echt onjuist, zoals in dit topic al vaker is aangegeven
Het uitkiezen van het eerste team kan op 42C2 manieren en dat is 861. Vervolgens moet je wel nog de overige 20 teams kiezen. Het tweede team kan op 40C2 manieren, enzovoort.
Vervolgens maakt de keuzevolgorde van de teams niet uit dus je deelt door 21!
Ik heb dit niet helemaal uitgewerkt, maar het aantal is in ieder geval te groot voor brute force
Zelf ben ik geen programmeur, maar als een first guess zou ik een op rating gesorteerde lijst nemen en daar vervolgens telkens de hoogste en de laagste rating uitpikken om een team te vormen. Van daaruit kun je waarschijnlijk in een eindig aantal iteraties naar een optimale verdeling komen.
Voor het gemak heb ik voor de notatie nCk =n!/(k!(n-k)!) gekozen

edit: even snel uitgewerkt en ik krijg 1.31E25 (zonder de autokeuze) hetzelfde antwoord als pedorus vond.

[ Voor 23% gewijzigd door Henk007 op 20-07-2013 10:09 ]

[Zoijar]

Zonder beperking der algemeenheid plaatsen we speler 1 in team 1 en moeten we nu een partner kiezen. Dat kan op 41 manieren. Vervolgens plaatsen we weer zonder beperking der algemeenheid de eerste speler in de lijst in team 2, en moeten we zijn partner kiezen op 39 manieren.

We moeten dit 21 keer doen.

41 * 39 * 37 * 35 * 33 * 31 * 29 * 27 * 25 * 23 * 21 * 19 * 17 * 15 * 13 * 11 * 9 * 7 * 5 * 3 * 1 = 1.31E25

Voor 21 teams.

Omdat te bewijzen moeten we aantonen dat:

- dit algoritme geen samenstelling twee keer produceert
- gegeven een willekeurige teamsamenstelling dit algoritme die samenstelling produceert

Dat is vrij makkelijk in te zien als je productie als boom opvat. De root heeft kinderen waar speler 1 steeds met een andere speler samen speelt. Ongeacht volgorde komen alle leaf nodes van elke subtree die begint bij een kind van de root niet voor in een andere subtree. De verzameling leaves van elke subtree zijn dus disjunct. We kunnen dit nu herhalen voor een niveau dieper. Bij elke subtree kiezen we steeds weer dezelfde eerste speler voor team 2, dus hetzelfde verhaal gaat op; i.e. geen leaf node is equivalent aan een andere in de boom.

Het tweede is ook goed in te zien. We zoeken in de willekeurige samenstelling het team waar speler 1 in zit. We bepalen zijn partner. We volgen dan het kind van de root node voor deze partner. Vervolgens gaan we een laag dieper en zoeken we weer het team met de volgende gekozen eerste speler. Die is altijd te vinden. Herhaal tot je bij een leaf node uitkomt.

qed

[ Voor 56% gewijzigd door Zoijar op 20-07-2013 10:57 ]

[NickThissen]

Bedankt voor de tip over ordered crossover, met behulp van dit voorbeeldje werkt het algoritme een stuk beter en inmiddels heb ik een goeie verdeling van teams weten te genereren

[Daedalus]

Henk007 schreef op zaterdag 20 juli 2013 @ 09:55:
[...]

Dat is toch echt onjuist, zoals in dit topic al vaker is aangegeven
Het uitkiezen van het eerste team kan op 42C2 manieren en dat is 861. Vervolgens moet je wel nog de overige 20 teams kiezen. Het tweede team kan op 40C2 manieren, enzovoort.
Vervolgens maakt de keuzevolgorde van de teams niet uit dus je deelt door 21!

Ah, dat had ik dus over het hoofd gezien Toch maar 'ns m'n boek discrete wiskunde maar weer 'ns uit de kast trekken. In dit geval is brute force inderdaad niet echt te doen.

[bomberboy]

Het is gewoon veel leuker (en leerzamer) om het zelf te doen, maar inspiratie rond types algoritmes kan je misschien hier vinden: Programming Contest Nieuwe Stijl: Contest 3 *uitslagen!*

Keuze van types algoritmes daar waar eerder richting simulated annealing en gelijkaardige technieken iirc. Naar specifieke code zou ik wel niet direct gaan kijken aangezien het om "wedstrijd-code" gaat (efficiëntie en snelheid boven schoonheid en onderhoudbaarheid met allerlei vuile optimalisatietruukjes tot gevolg)