Share:


Optimality testing in stochastic and heuristic algorithms

    Vaida Bartkutė Affiliation
    ; Graûvydas Felinskas Affiliation
    ; Leonidas Sakalauskas Affiliation

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.


First Published Online: 21 Oct 2010


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

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

How to Cite
Bartkutė, V., Felinskas, G., & Sakalauskas, L. (2006). Optimality testing in stochastic and heuristic algorithms. Technological and Economic Development of Economy, 12(1), 4-10. https://doi.org/10.3846/13928619.2006.9637715
Published in Issue
Mar 31, 2006
Abstract Views
21
PDF Downloads
27
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.