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 endre 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 endre, og der vi ganske enkelt kan sjekke hvor bra en variasjon 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 vi kan sjekke.

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 jevne (altså ikke bare tilfeldig 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 verdi 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 posisjoner og returnere den med høyest verdi: Det er stor sjanse for at ingen av disse gir maksimalverdien
• Man kan velge noen posisjoner 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)

verdi = landskap.hent_verdi(4, 3)  # henter vierdien til en, man har maks 1000 slike kall

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

En mulig fremgangsmåte 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 høyden.