Optimality testing in stochastic and heuristic algorithms

Abstract

In this paper we consider the application of order statistics to establish the optimality in stochastic and heuristic optimization algorithms. We suggest a method for the estimation of confidence intervals of minimum using order statistics which is implemented for optimality testing and stopping in stochastic approximation and Simulated Annealing algorithms. The efficiency of this approach is discussed using the results of application to continuous optimization and Bin‐packing problem.

Stochastinių ir euristinių algoritmų optimalumo tyrimas

Santrauka. Sudarant stochastinius ir euristinius algoritmus, dažnai tenka spręsti algoritmų optimalumo testavimo ir stabdymo problemas. Statistines išvadas apie minimalią (maksimalią) funkcijos reikšmę galime rasti literatūroje (V. Bartkutė, L. Sakalauskas (2004); Žilinskas A., Žygliavskij A. (1991)). Šiame straipsnyje nagrinėjamas pozicinių statistikų taikymas stochastinių ir euristinių algoritmų optimalumui tirti. Sudarytas metodas leidžia įvertinti minimalios reikšmės pasikliautinąjį intervalą, naudojant pozicines statistikas, ir pritaikyti šį įvertį optimalumui testuoti bei algoritmams stabdyti. Tarkime, turime seką { } 1 N Η = η η , ..., , kurios elementai yra optimizavimo metu gautos funkcijos reikšmės. Norėdami įvertinti minimalios reikšmės pasikliautinąjį intervalą sekoje H, išrenkame tiktai k +1 pozicinių statistikų (V. Bartkute, L. Sakalauskas (2004)). Kompiuterinio modeliavimo būdu tiriamas tikslo funkcijos minimalios reikšmės įverčių taikymas stochastinės aproksimacijos ir modeliuojamojo atkaitinimo algoritmuose. Gautos teorinės išvados ir kompiuterinio modeliavimo rezultatai parodė, kad tikslo funkcijos ekstremalios reikšmės pasikliautinąjį intervalą galima vertinti reikiamu tikslumu, kai iteracijų skaičius didėja. Straipsnio pabaigoje aptariamas šio metodo taikymas rūšiavimo (bin-packing) ir tvarkaraščių sudarymo (schedulling) problemoms spręsti.

Reikšminiai žodžiai: stochastiniai ir euristiniai algoritmai, optimalumas, pasikliautinasis intervalas.

First Published Online: 21 Oct 2010

Keyword : order statistics, Monte-Carlo simulation, continuous optimization, Simulated Annealing, Stochastic approximation