Lokalna pretraga (optimizacija)

(преусмерено са Local search (optimization))

U računarskoj nauci, lokalno pretraživanje je heuristički metod za rešavanje računarski teških problema optimizacije. Lokalna pretraga se može koristiti za probleme koji se mogu formulisati kao pronalaženje rešenja koje maksimizira kriterijum među brojnim kandidatima rešenjima. Lokalni algoritmi pretraživanja se kreću od rešenja do rešenja u prostoru kandidata rešenja (prostoru za pretragu) primenom lokalnih promena, sve dok se ne pronađe rešenje koje se smatra optimalnim ili dok ne protekne vremensko ograničenje.

Lokalni algoritmi pretraživanja se široko primenjuju na brojne teške računarske probleme, uključujući probleme iz računarske nauke (posebno veštačke inteligencije), matematike, operacionih istraživanja, inženjerstva i bioinformatike. Primeri algoritama lokalne pretrage su WalkSAT, algoritam sa 2 opcije za problem trgovačkog putnika i Metropolis–Hestingsov algoritam.[1]

Iako je ponekad moguće zameniti opadanje gradijenta za lokalni algoritam pretrage, opadanje gradijenta nije u istoj porodici: iako je to iterativni metod za lokalnu optimizaciju, on se oslanja na gradijent funkcije cilja, a ne na eksplicitno istraživanje prostora rešenja .

Reference

уреди

Literatura

уреди