Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Lokalt søk og optimering, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En funksjon som gir hver tilstand en verdi, og som lokalt søk prøver å maksimere. Skal noe minimeres, kalles den ofte en kostnadsfunksjon, og problemet er det samme med motsatt fortegn (objective function).
Et bilde av problemet der tilstandene ligger langs bakken og verdien til målfunksjonen er høyden. Lokalt søk beveger seg i landskapet ved å gå fra en tilstand til en nabo (state-space landscape).
En tilstand som er høyere enn alle naboene, men lavere enn det globale maksimumet, som er den høyeste tilstanden i hele landskapet (local maximum, global maximum).
Et flatt område i landskapet der naboene har samme verdi. Er det lavere på begge sider, er det et flatt lokalt maksimum; fortsetter landskapet oppover på én side, er det en skulder (plateau, shoulder).
En rekke lokale maksima som stiger skrått i forhold til retningene søket kan bevege seg i. Fra hver topp på ryggen går alle tilgjengelige trekk nedover, selv om ryggen som helhet stiger (ridge).
Lokalt søk som går til den beste naboen så lenge den er strengt bedre enn den nåværende tilstanden, og ellers stopper. Kalles også bratteste stigning (steepest-ascent hill climbing).
Et trekk til en nabo med samme verdi, slik at bakkeklatring kan krysse en skulder. Antallet på rad må begrenses, ellers kan søket vandre for alltid på et flatt lokalt maksimum (sideways move).
Bakkeklatring som velger tilfeldig blant nabotrekkene som går oppover. Førstevalgsvarianten trekker naboer tilfeldig og tar den første som er bedre (stochastic hill climbing, first-choice hill climbing).
Bakkeklatring som starter på nytt fra en tilfeldig tilstand hver gang den står fast, og beholder den beste tilstanden. Den er fullstendig med sannsynlighet som går mot 1 (random-restart hill climbing).
Lokalt søk som trekker en tilfeldig nabo, tar trekket hvis det er bedre, og ellers tar det med sannsynlighet . Temperaturen senkes over tid (simulated annealing).
Regelen for hvordan temperaturen i simulert avkjøling senkes over tid, for eksempel geometrisk med (schedule).
Lokalt søk som holder tilstander, genererer alle etterfølgerne til alle sammen og beholder de beste av dem til sammen (local beam search).
Et stokastisk strålesøk der nye individer lages ved å velge foreldre etter fitness, krysse dem og mutere barna. Individene er ofte bitstrenger (genetic algorithm).
Målfunksjonen i en genetisk algoritme: et tall for hvor godt et individ er. Med fitnessproporsjonal seleksjon må den være ikke-negativ (fitness function).
Et barn lages ved å ta begynnelsen av én forelder fram til et kryssingspunkt og resten fra den andre forelderen (crossover).
Hver posisjon i et barn endres tilfeldig med en liten sannsynlighet, for eksempel ved at en bit snus. Mutasjon er den eneste måten å få inn en bitverdi som mangler på en plass i hele populasjonen (mutation).
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Akseptsannsynligheten
Simulert avkjøling tar et dårligere trekk med denne sannsynligheten; et bedre trekk tas alltid. er ny verdi minus gammel når vi maksimerer. Vanlig feil: å sette inn positiv , som gir et tall over 1.
Fitnessproporsjonal seleksjon
Sannsynligheten for at individ velges som forelder i en genetisk algoritme. Summen går over hele populasjonen, og alle må være ikke-negative.
Forventet antall forsøk og omstarter
For tilfeldig omstart der hvert forsøk lykkes med sannsynlighet . Omstarter er forsøkene etter det første. Vanlig feil: å svare med antall forsøk når oppgaven spør etter omstarter.
Gradientsteget
Gradientstigning i kontinuerlige rom: et steg i retningen der øker raskest. For minimering brukes minus. For stor steglengde gir hopp forbi toppen.
Konfliktheuristikken for dronninger
Målfunksjonen som minimeres i n-dronninger: par på samme rad eller diagonal. To dronninger står på samme diagonal når radforskjellen og kolonneforskjellen er like store (i absoluttverdi). er en løsning.
Kodesnutter
Kodesnutter fra kapittelet, vist literal.
Bakkeklatring med omstart på n-dronninger
import random n = 8 # @param 4..10omstarter = 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, Nonefor 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 breakprint(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}")Prøv: øk omstarter fra 1 til 30 og se at linja Løst i omstart nr.: går fra «ikke løst» til et tall, mens Totalt antall trekk: viser hva omstartene koster.
Simulert avkjøling hundre ganger
import mathimport randomimport matplotlib.pyplot as plt T0 = 0.5 # @param 0.1..10 0.1avkjoling = 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()Prøv: sett T0 til 10 og avkjoling til 0.99, og se at linja Andel av 100 kjøringer som fant toppen: stiger fra 0 % til over 80 %.
Genetisk algoritme for ladestasjoner
import random mutasjonsrate = 0.00 # @param 0.00..0.30 0.01 random.seed(4)N = 12 # mulige plasser for ladestasjoner langs veien def fitness(bits): # 1 = stasjon; hver stasjon dekker sin egen plass og naboene dekket = {j for i, b in enumerate(bits) if b for j in (i - 1, i, i + 1) if 0 <= j < N} return len(dekket) - sum(bits) pop = [[random.randint(0, 1) for _ in range(N)] for _ in range(20)]funnet = Nonefor gen in range(1, 41): vekter = [fitness(p) + 0.01 for p in pop] # fitnessproporsjonal seleksjon nye = [max(pop, key=fitness)] # elitisme: den beste går videre uendret while len(nye) < len(pop): mor, far = random.choices(pop, weights=vekter, k=2) punkt = random.randint(1, N - 1) # kryssing i ett punkt barn = mor[:punkt] + far[punkt:] nye.append([1 - b if random.random() < mutasjonsrate else b for b in barn]) pop = nye if funnet is None and max(map(fitness, pop)) == 8: # optimum: 4 stasjoner dekker alt funnet = genprint(f"Beste fitness i siste generasjon: {max(map(fitness, pop))}")print(f"Generasjoner til optimum: {funnet if funnet else 'ikke nådd'}")Prøv: øk mutasjonsrate fra 0.00 til 0.02 og se at linja Generasjoner til optimum: går fra «ikke nådd» til et tall, fordi bare mutasjon kan lage en bitverdi som mangler på en plass i hele populasjonen.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Gjenkjenn lokalt maksimum, globalt maksimum, platå, skulder og rygg i et tilstandslandskap
- 02Spor bratteste stigning med og uten sidelengs trekk, og forklar hvorfor den stopper når ingen nabo er strengt bedre
- 03Regn ut akseptsannsynligheten i simulert avkjøling og forklar effekten av temperaturplanen
- 04Utfør én generasjon av en genetisk algoritme med fitnessproporsjonal seleksjon, kryssing og mutasjon
- 05Regn ut forventet antall forsøk og omstarter for tilfeldig omstart
- 06Sammenlign bakkeklatring, simulert avkjøling, lokal strålesøk og genetiske algoritmer, og ta et gradientsteg i et kontinuerlig rom