Lokalt søk og optimering

I mange problemer er veien uinteressant. Plasserer du ladestasjoner langs en vei eller dronninger på et sjakkbrett, er det bare sluttilstanden som teller. Da trenger du ingen søketre. En målfunksjon (objective function) $f$ gir hver tilstand en verdi, og målet er å finne en tilstand med høyest mulig verdi. Skal noe minimeres, for eksempel en kostnad eller antall konflikter, er det samme oppgave med motsatt fortegn. Formuleringen kalles ofte komplett tilstand: hver tilstand er et fullstendig forslag til løsning, og søket forbedrer forslaget i stedet for å bygge det opp bit for bit.

Lokalt søk husker bare den nåværende tilstanden. Minnet er konstant, og søket virker i enorme og til og med uendelige tilstandsrom. Prisen er at søket ikke er systematisk: det kan gå glipp av den beste tilstanden og er generelt verken fullstendig eller optimalt.

Et tilstandslandskap (state-space landscape) har tilstandene langs bakken og verdien som høyde. Globalt maksimum er det høyeste punktet. Et lokalt maksimum (local maximum) er høyere enn alle naboene, men ikke høyest totalt. Et platå (plateau) er et flatt område: er det lavere på begge sider, er det et flatt lokalt maksimum, men fortsetter landskapet oppover på den ene siden, kalles det en skulder (shoulder). En rygg (ridge) er en rekke lokale maksima som stiger skrått i forhold til retningene søket kan gå i. Fra hver topp på ryggen går alle tilgjengelige trekk nedover, selv om ryggen som helhet går oppover.

Landskapet under har 26 tilstander i en rekke, og naboene til en tilstand er de to ved siden av.

Med n-dronninger er tilstanden én dronning i hver kolonne, og verdien er ƒkonfliktheuristikken for dronninger, som skal minimeres:

En nabo flytter én dronning til en annen rad i sin egen kolonne, så hver tilstand har $n(n-1)$ naboer.

Bakkeklatring (steepest-ascent hill climbing) ser på alle naboene, går til den beste og gjentar. Søket stopper når ingen nabo er strengt bedre enn den nåværende tilstanden. En nabo med samme verdi er altså ikke nok. Derfor stopper bakkeklatring på den første toppen eller det flate partiet den møter: på et lokalt maksimum, på et flatt lokalt maksimum eller på en skulder. Ved en rygg står den fast fordi ingen enkelt nabo er bedre.

Algoritmen er rask når den først kommer i gang, men på n-dronninger med tilfeldig start stopper den oftere i en tilstand med én eller to konflikter igjen enn i en løsning. Tre varianter retter på dette:

• •Et sidelengs trekk (sideways move) går til en nabo med samme verdi, slik at søket kan krysse en skulder. Antallet på rad må begrenses, ellers vandrer søket for alltid fram og tilbake på et flatt lokalt maksimum.
• •Stokastisk bakkeklatring (stochastic hill climbing) velger tilfeldig blant nabotrekkene som går oppover. Førstevalgsvarianten (first-choice) trekker naboer tilfeldig til den finner én som er bedre, og passer når hver tilstand har tusenvis av naboer.
• •Tilfeldig omstart (random-restart hill climbing) starter på nytt fra en tilfeldig tilstand når søket står fast, og beholder den beste tilstanden.

Hvilken variant som lønner seg, avhenger av landskapet. Mange platåer taler for sidelengs trekk, mange naboer for førstevalg, og mange lokale maksima for omstart. Omstart er dessuten fullstendig med sannsynlighet som går mot 1: hvert forsøk har en sjanse for å starte i bakken under det globale maksimumet.

Lykkes hvert forsøk med sannsynlighet $p$, gir ƒforventet antall forsøk og omstarter:

Landskapet under har en skulder på vei opp mot en topp som ikke er den høyeste.

Koden under kjører bratteste stigning på n-dronninger og starter på nytt fra en tilfeldig tilstand hver gang søket står fast.

import random

n = 8  # @param 4..10
omstarter = 10  # @param 1..50

random.seed(4)


def konflikter(rad):  # antall par som angriper hverandre (samme rad eller diagonal)
    return sum(rad[a] == rad[b] or abs(rad[a] - rad[b]) == b - a
               for a in range(n) for b in range(a + 1, n))


trekk, beste, losning = 0, None, None
for forsok in range(1, omstarter + 1):
    rad = [random.randrange(n) for _ in range(n)]  # én dronning per kolonne
    while True:
        naboer = [rad[:k] + [r] + rad[k + 1:] for k in range(n) for r in range(n) if r != rad[k]]
        nabo = min(naboer, key=konflikter)
        if konflikter(nabo) >= konflikter(rad):
            break  # ingen nabo er strengt bedre: lokalt minimum
        rad, trekk = nabo, trekk + 1
    if beste is None or konflikter(rad) < konflikter(beste):
        beste = rad
    if konflikter(rad) == 0:
        losning = forsok
        break
print(f"Løst i omstart nr.: {losning if losning else 'ikke løst'}")
print(f"Konflikter i beste tilstand: {konflikter(beste)}")
print(f"Totalt antall trekk: {trekk}")

Bakkeklatring går aldri nedover, og blir derfor stående på det første lokale maksimumet den finner. En helt tilfeldig vandring finner før eller siden alt, men bruker uendelig lang tid på det. Simulert avkjøling (simulated annealing) blander de to. Søket trekker en tilfeldig nabo. Er den bedre, tar søket trekket. Er den dårligere, med $\Delta E=f(\text{nabo})-f(\text{na˚})<0$, tas trekket bare med sannsynlighet gitt av ƒakseptsannsynligheten:

Temperaturen $T$ styrer hvor villig søket er til å gå nedover. Ved høy $T$ er $\Delta E/T$ nær null, og nesten alle trekk godtas, så søket vandrer fritt. Når $T$ går mot 0, går sannsynligheten mot 0, og søket oppfører seg som bakkeklatring. Et lite fall godtas også oftere enn et stort. En temperaturplan (schedule) senker $T$ over tid, for eksempel geometrisk med $T\leftarrow \alpha T$. Senkes temperaturen langsomt nok, finner søket et globalt maksimum med sannsynlighet som går mot 1, men i praksis velges planen ved å prøve seg fram. Starttemperaturen bør stå i forhold til de typiske verdiendringene: er $\Delta E$ vanligvis rundt 1, gir $T=10$ nesten fri vandring og $T=0,1$ nesten ren bakkeklatring.

Siden søket også tar dårlige trekk, kan det ende lavere enn det var underveis. Implementasjoner holder derfor rede på den beste tilstanden som er sett, og returnerer den. Tilfeldig omstart og simulert avkjøling løser altså samme problem på to måter: den ene hopper til et nytt startpunkt, den andre tar små steg nedover. Under er det samme slags landskap som bakkeklatring stopper i, med en dal mellom en lav og en høy topp.

Koden kjører simulert avkjøling hundre ganger på et landskap der en lav topp ligger rett ved starten.

import math
import random
import matplotlib.pyplot as plt

T0 = 0.5  # @param 0.1..10 0.1
avkjoling = 0.90  # @param 0.80..0.99 0.01

random.seed(4)
f = [2, 4, 5, 4, 3, 2, 2, 3, 5, 7, 9, 10, 9, 7, 5, 4, 3, 2]  # vi maksimerer f(x)


def kjor():
    x, T, beste, sti = 1, T0, 1, [1]
    for _ in range(200):
        y = min(len(f) - 1, max(0, x + random.choice([-1, 1])))  # tilfeldig nabo
        dE = f[y] - f[x]
        if dE > 0 or random.random() < math.exp(dE / T):  # dårligere trekk: e^(ΔE/T)
            x = y
            sti.append(x)
        beste = x if f[x] > f[beste] else beste
        T = T * avkjoling
    return beste, sti


beste, sti = kjor()
treff = sum(f[kjor()[0]] == max(f) for _ in range(99)) + (f[beste] == max(f))
print(f"Beste x: {beste}")
print(f"Beste verdi: {f[beste]}")
print(f"Fant globalt maksimum: {'ja' if f[beste] == max(f) else 'nei'}")
print(f"Andel av 100 kjøringer som fant toppen: {treff} %")
plt.plot(range(len(f)), f)
plt.plot(sti, [f[s] for s in sti], "o", alpha=0.3)
plt.xlabel("tilstand x")
plt.ylabel("f(x)")
plt.show()

Lokal strålesøk (local beam search) holder $k$ tilstander i stedet for én. I hvert steg genereres alle etterfølgerne til alle $k$, og de $k$ beste av dem til sammen går videre. Det er noe annet enn $k$ uavhengige omstarter: lover én tilstand mye, får den flere etterkommere, og søket flytter innsatsen dit. Ulempen er at alle $k$ kan havne i samme område. Stokastisk strålesøk velger derfor etterfølgerne tilfeldig, med sannsynlighet som øker med verdien.

En genetisk algoritme (genetic algorithm) er et stokastisk strålesøk der etterfølgerne lages av to foreldre. Tilstandene, kalt individer, er strenger, for eksempel biter. En fitnessfunksjon (fitness function) gir hvert individ en verdi, og ƒfitnessproporsjonal seleksjon velger foreldre med sannsynlighet proporsjonal med fitness:

Ved kryssing (crossover) velges et kryssingspunkt, og barnet får begynnelsen av den ene forelderen og resten av den andre. Ved mutasjon (mutation) snus hver bit med en liten sannsynlighet. Kryssing kan sette sammen gode deler fra to foreldre når posisjonen i strengen betyr noe, mens bare mutasjon kan lage en bitverdi som mangler på en plass i hele populasjonen. Hvor godt en genetisk algoritme virker, avhenger derfor av kodingen: biter som henger sammen i problemet, bør stå nær hverandre i strengen, slik at kryssing sjelden river dem fra hverandre. Mange varianter beholder også de beste individene uendret til neste generasjon (elitisme), slik at den beste løsningen aldri går tapt.

Tabellen viser én generasjon for åtte mulige plasser for ladestasjoner langs en vei.

En genetisk algoritme er ingen garanti. Den har like mange innstillinger som den har deler (populasjonsstørrelse, seleksjon, kryssing, mutasjonsrate), og på mange problemer gjør bakkeklatring med omstart like stor nytte. Styrken viser seg når gode løsninger er bygd av uavhengige byggeklosser som kryssing kan sette sammen. Koden kjører en hel genetisk algoritme på samme problem med tolv plasser, der bare mutasjonsraten kan endres.

Er tilstanden en vektor av reelle tall, for eksempel koordinatene til tre ladestasjoner, har hver tilstand uendelig mange naboer. Én løsning er å dele rommet i et rutenett og bruke metodene over. En annen er å bruke gradienten $\nabla f$, som peker i retningen der $f$ øker raskest. ƒGradientsteget tar et steg den veien:

Steglengden $\alpha$ avgjør resten. Er den for liten, kryper søket. Er den for stor, hopper det forbi toppen og kan svinge eller gå ut av kurs. På toppen er gradienten null, og steget blir null av seg selv. Gradienten er like lokal som en nabo i et rutenett: også i kontinuerlige rom finnes lokale maksima, og omstart fra flere startpunkter hjelper på samme måte. Skal $f$ minimeres, går steget motsatt vei, med minus i stedet for pluss. Finnes ingen formel for gradienten, kan den anslås ved å endre hver koordinat litt og se på endringen i $f$. Ofte har problemet også begrensninger, for eksempel at stasjonene må stå langs veien eller innenfor kommunegrensen. Da må hvert steg holdes innenfor det lovlige området, og toppen kan ligge på kanten av området i stedet for der gradienten er null.

Funksjonen under har én topp, og punktet kan flyttes langs x-aksen.