I algoritmer er lokalt søk en generell metode som brukes for å løse optimaliseringsproblemer , det vil si problemer der man søker den beste løsningen i et sett med kandidatløsninger. Lokalt søk består i å gå fra en løsning til en annen nær løsning i kandidatløsningenes rom ( søkeområdet ) til en løsning som anses som optimal blir funnet, eller den tildelte tiden overskrides.
Vi tar som et eksempel problemet med den omreisende selgeren , som består, gitt en liste over byer og avstandene mellom dem, i å finne en krets som går gjennom alle byene, og som er så kort som mulig. Med andre ord er settet med tillatte løsninger settet med kretsløp som går gjennom alle byene, og målet er å minimere lengden. Vi kan vurdere at vi er på en ikke-rettet graf, hvis hjørner er byer, og kantene er veier mellom byer.
En enkel lokal søkealgoritme, kalt 2-opt , er som følger: start fra hvilken som helst krets, og gjenta neste søk. Ta to kanter (A, B) og (C, D), og erstatt dem med kantene med (A, D) og (B, C). Hvis denne nye kretsen er kortere, behol den og fortsett, ellers tar du den forrige kretsen og prøver et annet par kanter.
Vi kan stoppe algoritmen når alle kantparene er testet. Løsningen som er oppnådd er garantert ikke optimal, men kan likevel være nyttig og av kvalitet.
En lokal søkealgoritme starter fra en kandidatløsning og flytter den iterativt til en naboløsning . Denne metoden gjelder bare hvis et begrep nabolag er definert i søkeområdet. For eksempel er nabolaget til et spennende tre et annet spennende tre som bare skiller seg etter en node. For SAT-problemet er naboene til en god oppgave vanligvis de oppdragene som bare avviker i verdien til en variabel. Det samme problemet kan ha flere forskjellige nabolagsdefinisjoner; lokal optimalisering med nabolag som begrenser endringer til k- komponenter i løsningen kalles ofte k -optimal.
Vanligvis har hver kandidatløsning mer enn én naboløsning; valget av det du skal flytte til tas ved å bare bruke informasjonen på løsningene nær den nåværende løsningen, derav det lokale søkeordet . Når valget av naboløsningen bare gjøres ved å ta den som maksimerer kriteriet, tar metauristikken navnet bakkeklatring .
Kriteriet for å stoppe det lokale søket kan være en tidsbegrensning. En annen mulighet er å stoppe når den beste løsningen funnet av algoritmen ikke har blitt forbedret for et gitt antall iterasjoner. Lokale søkealgoritmer er suboptimale algoritmer siden søket kan stoppe når den beste løsningen som algoritmen finner ikke er den beste av søkeområdet. Denne situasjonen kan oppstå selv om stoppet er forårsaket av umuligheten av å forbedre den nåværende løsningen fordi den optimale løsningen kan bli funnet langt fra nabolaget til løsningene som algoritmen krysser.
Lokale søkealgoritmer brukes mye i vanskelige optimaliseringsproblemer, for eksempel beregningsproblemer (spesielt kunstig intelligens ), matematikk , operasjonsforskning , ingeniørfag og bioinformatikk .
Følgende problemer egner seg godt til å bruke lokalt søk :
Mange problemer kan formuleres på flere måter når det gjelder forskningsrom og formål. For eksempel for det reisende selgerproblemet kan en løsning være en syklus, og kriteriet som skal maksimeres er kombinasjonen av antall noder og lengden på syklusen. Men en løsning kan også være en sti, og å gjøre det om til en syklus kan være en del av målet.