ga-staff - genetisk algoritm för bemanning

En lite lurig "bugg".

ga-tsp lagrade sin population av lösningar i en map med sträckan för en rundtur som nyckel. Det var bra för då lagras lösningarna automatiskt sorterade och två identiska lösningar med exakt samma sträcka kan inte lagras. Eftersom sträckan är en double bestående av en summa av en massa kvadratrötter är det osannolikt att två olika lösningar har exakt samma sträcka. Det innebär att kopior av exakt samma lösningar inte lagras i populationen och man undviker därför "inavel" som gör att den genetiska algoritmen fungerar dåligt.

I ga-staff används summor av heltal istället för summor av kvadratrötter. Det innebär att sannolikheten är mycket hög att två olika lösningar har samma poäng. Men eftersom de lagras i en map så accepteras bara en enda lösning med en viss poäng. Istället kommer sämre lösningar, med sämre poäng, att lagras i populationen. Det får den genetiska algoritmen att fungera dåligt. Tanken är att ta vara på bra lösningar och rekombinera dem för att hitta ändå bättre lösningar.

Fix:
Jag kan antingen gå över till en multimap eller göra om poängen till double på ett sätt som gör att olika lösningar sällan kan ha exakt samma poäng.

Jag kommer att testa med att göra poängen till double. Det kommer jag att göra genom att lägga till ett litet värde till varje specificerad heltalspoäng. Kanske mellan 0,001 till 0,01. Och jag gör det på ett sätt som innebär att de första avdelningarna och de första personerna får en liten aning företräde. Det gör också att det inte längre är sannolikt att många lösningar är lika bra. Det blir en kontinuerlig rankning av lösningar. Men fortfarande kan inte lösningar exakt samma poäng lagras i map, men nu är sannolikheten för att lösningar med exakt samma poäng är identiska mycket lägre.

Skickades från m.sweclockers.com