Optimalisering

Et typisk problem i informatikk går ut på at man skal optimalisere løsningen av et problem (finne beste løsning), og at man har en del parametere man kan tweake for å prøve å finne en bedre løsning.

Vi skal her se på en versjon av et slikt problem, der vi bare har to parametere vi skal tweake, og der vi ganske enkelt kan sjekke hvor bra en "tweaking" er. Det eneste som gjør dette vanskelig er at det er kostbart å sjekke hvor bra et sett med parametere er, slik at vi har et begrenset antall med sjekk.

Problemet er slik:

• Vi står i et landskap som er et rutenett med en viss størrelse
• Landskapet har på hvert punkt en høyde og vi antar at det finnes en rekke høyder og at disse er noenlunde "smoothe" (altså ikke bare random støy)
• Å sjekke høyden på et punkt er kostbart (se for deg at det kan tilsvare å kjøre en full simulering av løsningen på et problem), og vi kan derfor ikke sjekke høyden over alt. Anta at vi har N sjekk vi har lov til å gjøre.
• Målet er i løpet av N sjekk å finne en posisjon på brettet som gir så høy score som mulig.
• Landskapet kan f. eks se noe slikt ut i 3 dimensjoner:

Mulige strategier

• Man kan prøve alle mulige posisjoner: Dette går ikke fordi vi bare har N sjekk
• Man kan velge N tilfeldige lokasjoner og returnere den med høyest score: Det er stor sjanse for at ingen av disse gir den beste scoren
• Man kan velge noen lokasjoner og prøve å bevege seg oppover: Gå i den retningen som ser ut til å gi bedre score

Oppgave

Last ned denne filen. Du trenger å ha installert numpy og matplotlib (for å plotte landskapet).

Filen inneholder en klasse landskap som gjør at du kan lage et landskap:

from landskap import Landskap
landskap = Landskap(30, 30)  # 30x30 ruter stor
landskap.lag_landskap()  # lag landskapet
landskap.plott_3d()  # plott i 3d (krever matplotlib)

score = landskap.hent_score(4, 3)  # henter scoren på en rute, man har maks 1000 slike kall

Skriv kode som gitt et landskap returnerer den posisjonen man tror gir høyest score. Du kan f. eks lage en funksjon eller klasse som tar et landskap.

En mulig approach er å lage en klasse Person. Vi ser for oss at en Person er et individ som befinner seg i landskapet og som prøver å finne høyeste punkt. Om man setter ulike personer ut i landskapet på forskjellige random plasser, kan man la disse søke lokalt og så kan man til slutt sjekke hvilken person som fant den høyeste peaken.