Lokalna pretraga (optimizacija)

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.

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 .

Literatura

• Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN 978-0-387-09623-0. Архивирано из оригинала 2012-03-16. г. 
• Hoos, H.H. and Stutzle, T. (2005) Stochastic Local Search: Foundations and Applications, Morgan Kaufmann.
• Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit, (2004): Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal of Computing 33(3).
• Juraj Hromkovič: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics (Springer)
• Wil Michiels, Emile Aarts, Jan Korst: Theoretical Aspects of Local Search (Springer)