Titlen på dette afsnit, Tabu, henviser bl.a. til den matematiske metode, Charlie omtaler som Tabusøgning (Tabu search). Desuden var der henvisninger til spilteori: minimax principper, spil med ufuldstændig information. Og (igen) noget om beslutninger og analyse af taktik udfra beslutnings analyse (da Charlie blev inspireret af en analogi med en sommerfugl).
Der var noget data, der blev vægtet med en Bayesiansk prior.
Der var noget fysik – her kan man se, hvordan man bygger Herons fontæne/springvand og her er en anden konstruktion, hvor de fysiske principper bag forklares. Der var meget mere fysik – Larry siger meget om analogier mellem Megans problemer og diverse fysik, men det lader jeg ligge.
Tabusøgning
Vil man læse rigtig meget om emnet, er bogen Tabu Search af Fred Glover og Manuel Laguna en ret omfattende kilde. Glover er, så vidt jeg kan finde ud af, ophavsmanden til Tabusøgning. En kortere kilde er A tutorial on Tabu search, Hertz, de Werra og Taillard.
En tabusøgning skal generelt løse et optimeringsproblem ved at søge struktureret iblandt mulige løsninger. Optimering kan i denne sammenhæng være
- find et skema, for en folkeskole for næste skoleår, hvor de små klasser ikke har mellemtimer, lærerne ikke skal stå i to klasseværelser på en gang, ingen klasser er i samme klasseværelse samtidigt, store klasser (og lærere)har få mellemtimer, klasserne har timerne nogenlunde jævnt fordelt over ugen etc.
- Planlæg valgfag for et gymnasium. Skemaerne skal passe, alle elever skal have passende antal valgfag etc. (Så vidt jeg kan se af denne artikel fra LMFK-bladet, bruger Lectio Tabusøgning til denne opgave. Det baseres på et speciale fra DTU)
- planlæg flytider/ruter for et flyselskab
- lav en rute for et handelsrejsende, der skal besøge byerne A,B,C,….,Y, som er kortest mulig, og hvor man ikke kommer tilbage til nogen af byerne. Man kender afstandene mellem hvert par af byer. Problemet kaldes Travelling Salesman Problem og er et klassisk grafteoretisk optimeringsproblem. Det er NP-fuldstændigt.
- “Classical Vehicle Routing Problem”, CVRP: Man har et antal lastbiler, som skal bringe varer ud fra et depot. Man kender kunderne og deres behov – hvor meget skal de bruge og hvor lang tid tager det at servicere dem (der skal læsses af, og måske skal der installeres noget). Lastbilerne har en maksimum kapacitet Q. Afstanden mellem kunderne parvis og mellem depotet er karakteriseret ved dels en omkostning (broafgifter, benzinforbrug,…) og et tidsforbrug. Opgaven er nu at finde ruter, så
- hver rute begynder og slutter ved depotet
- Hver kunde besøges præcis en gang
- Det samlede leverance på en rute er mindre end Q
- Den samlede varighed af hver rute (transporttid plus tid hos hver kunde) er ikke større end et fastsat maksimum (8 timer måske)
- Den totale omkostning er mindst mulig
Problemerne kan i en vis forstand overskues; man kan karakterisere de mulige løsninger. Eksempelvis kan man for den handelsrejsende kigge på alle mulige ruter A,C,B,U,X,M,… altså alle de måder, man kan skrive byerne i rækkefølge på. Og så vælge den, der er kortest. Men der er alt for mange muligheder. Eller mere præcist: Tilføjer jeg blot en enkelt by, vokser antallet af mulige ruter meget hurtigt. Med tre byer er mulighederne med start i A ABC, ACB (man tager tilbage til A til sidst, men det skriver jeg ikke på listen). Med fire er der ABCD, ABDC, ADBC, ACBD, ACDB, ADCB (for hver af de to, jeg havde, får jeg tre nye, ved at placere D de tre mulige steder) Fra ruten ABCD kan jeg tilføje E som ABCDE, ABCED, ABECD, AEBCD, så jeg får fire nye for hver, jeg havde i forvejen. Antallet af ruter vokser som 1,2,6,24,120,720 … eksponentielt. Man er nødt til at være smartere.
Man kan forestille sig, at man leder igennem løsningsforslag ved at starte med en løsning, som (formentlig) ikke er optimal. Dernæst ser man på alle de løsninger, der ligger “tæt på” – som man kan få ved at ændre den, man har, en lille smule: Byt om på to af byerne på ruten for den handelsrejsende. Er der en af de nye, der er kortere, tager man den og kigger igen på dens “naboer” – man kan vælge at tage den første, man møder, der er kortere, eller at se alle naboer igennem og vælge den korteste blandt naboerne. Det er nu fristende at tro, at man kan stoppe, når alle naboerne er længere – er dårligere løsninger, men man risikerer at snyde sig selv.
Optimeringsproblemer har ofte lokale maksima. Altså løsningsforslag, som er de bedste i forhold til naboerne, men som ikke er de bedste, hvis man sammenligner med alle andre. Man kan tænke på et landskab. Vi vil finde det højeste punkt ved at starte et sted og hele tiden gå opad. Står man på Himmelbjerget, er alt lige i nærheden lavere, men Mount Everest er jo højere.
Man skal altså kigge lidt længere end bare på naboerne. I en tabusøgning holder man styr på, hvor man allerede har været. Man vil forebygge, at man går i ring og går tilbage til steder, hvor man har været. Og helt fundamentalt skal man have fastlagt, hvad et nabolag overhovedet er.
Eksempelvis:
I CVRP har vi lavet et antal ruter, R1,…,R7 som opfylder betingelserne – kundernes samlede behov og tidsforbruget er ok for hver rute. Og alle kunder bliver besøgt en gang. Men vi vil jo have minimeret omkostningerne. Hvad er nu nabolaget for vores løsningsforslag- hvilke små modifikationer kan man lave på det løsningsforlag og få et nyt?
- Man kan flytte en kunde til et andet sted på samme rute eller til en anden rute, hvor der er ledig kapacitet (både tid og plads i lastbilen).
- Man kan bytte om på to kunder – fra to forskellige ruter (igen skal der være tid og plads)
- Man kan flytte en fra rute 1 til rute 2, en fra rute 2 til rute 3 og en fra rute 3 til rute 1
Der er mange muligheder.
Med nabolagsstrukturen fastlagt skal man bestemme en tabustruktur. Husk, ideen er, at man skal kunne komme væk fra et lokalt maksimum ved at gå lidt “ned ad bakke”. Og undgå at gå i ring.
Bemærk, at man måske har været i nærheden af Mount Everest og har valgt at gå op mod K2, fordi der umiddelbart så stejlest ud. Så man skal altså muligvis passere steder, hvor man har været. En tabustruktur forhindrer, at man går i små cirkler, men ikke store. Man husker lidt af fortiden, men ikke det hele.
For CVRP kunne man forbyde (erklære det for tabu) at flytte en kunde k1, der lige er flyttet fra R1 til R2, tilbage igen (i hukommelsen skal man have k1,R1,R2),. Et lidt stærkere tabu vil være at fobyde at flytte k1 tilbage til R1 overhovedet (man husker (k1,R1)) Eller endnu stærkere: Man forbyder at flytte k1 igen (hukommelsen har k1).
Man beholder sine tabuer et vist stykke tid – det er også en parameter i tabusøgningsalgoritmen.
Man husker naturligvis hele tiden
- den hidtil bedste løsning.
- Hvor god den er (i CVRP er det dens omkostninger),
- den løsning, vi lige nu ser på og hvor god den er
- dens nabolag
- dens tilladte nabolag – dem, der ikke er tabu.
For at undgå, at tabuerne spænder ben for en måske virkelig god løsning, vil man normalt kigge dem, der er tabuiseret i nabolaget igennem. Og hvis en af disse er bedre end den hidtil bedste løsning, tager man den med – husk, ideen er at gå nedad for at kunne gå endnu højere op senere.
CVRP og tilsvarende problemer er væsentlige, da computere med flere processorer vil distribuere opgaver til de forskellige processorer, og det er netop et problem af den type. Og det skal løses effektivt af en computer.
Spilteori:
Det er et stort emne, og vi har haft det på bloggen tidligere – om kageudskæring, Tit for Tat og fangernes dilemma, Cooperative Gametheory og Multiplayer og Mere overordnet om spilteoretiske problemer
Denne gang omtalte Charlie minimax strategier. Det er strategier, hvor man forsøger at minimere det maksimale tab, man kan have. En lidt pessimistisk strategi, hvor man hele tiden har øje for, hvor galt det kan gå.
Charlie nævner også spil med ufuldstændig information. I kryds og bolle og i skak har man fuld information – man kender modstanderens mulige træk. I poker har man ufuldstændig information – modstanderen har kort på hånden, som man ikke kender.
Man kan opdele spil efter, om spillerne har fuldstændig modstridende interesser – f.eks. hvis der er en samlet pulje, der skal deles. Eller spil, hvor det kan være gavnligt at samarbejde – f.eks. i fredsforhandlinger.
Der står rigtig meget om spilteori på Encyclopedia Britannica. Der er mange fine figurer om flere af de problemer, jeg har omtalt tidligere på bloggen.