Lokalt optimum - Local optimum
I anvendt matematikk og informatikk er et lokalt optimum av et optimaliseringsproblem en løsning som er optimal (enten maksimal eller minimal ) i et nabosett av kandidatløsninger. Dette i motsetning til et globalt optimum , som er den optimale løsningen blant alle mulige løsninger , ikke bare de i et bestemt verdisamfunn.
Kontinuerlig domene
Når funksjonen som skal optimaliseres er kontinuerlig , kan det være mulig å bruke kalkulus for å finne lokale optima. Hvis det første derivatet finnes overalt, kan det likestilles med null; Hvis funksjonen har et ubegrenset domene , for at et punkt skal være et lokalt optimum, er det nødvendig at den tilfredsstiller denne ligningen. Da gir den andre deriverte testen en tilstrekkelig betingelse for at punktet skal være et lokalt maksimum eller lokalt minimum.
Søketeknikker
Lokale søk- eller bakkeklatremetoder for å løse optimaliseringsproblemer starter fra en initial konfigurasjon og går gjentatte ganger til en forbedring av nabokonfigurasjonen . Det genereres en bane i søkeområdet, som kartlegger et innledende punkt til et lokalt optimum, der lokalt søk sitter fast (ingen forbedrende naboer er tilgjengelige). Søkerommet er derfor delt inn i attraksjoner som hver består av alle innledende punkter som har et gitt lokalt optimum som sluttpunktet i den lokale søketrajecten. Et lokalt optimum kan isoleres (omgitt av ikke-lokalt optimale punkter) eller en del av et platå , et lokalt optimalt område med mer enn ett poeng med lik verdi.
Hvis problemet som skal løses har alle lokalt optimale punkter med samme verdi av funksjonen som skal optimaliseres, løser lokalt søk effektivt det globale problemet: å finne et lokalt optimum leverer en globalt optimal løsning.
Lokaliteten til det optimale er avhengig av nabolagets struktur som er definert av den lokale søkemetoden som brukes for å optimalisere funksjonen.
I mange tilfeller leverer lokale optima suboptimale løsninger på det globale problemet, og en lokal søkemetode må modifiseres for å fortsette søket utover lokal optimalitet; se for eksempel iterert lokalt søk , tabu-søk , reaktiv søkeoptimalisering og simulert annealing .