CoRSO (Collaborative Reactive Search Optimization): Blending Combinatorial and Continuous Local Search

摘要

We propose a heuristic global optimization technique which combines combinatorial and continuous local search. The combinatorial component, based on Reactive Search Optimization, generates a trajectory of binary strings describing search districts. Each district is evaluated by random sampling and by selective runs of continuous local search. A reactive prohibition mechanisms guarantees that the search is not stuck at locally optimal districts. The continuous stochastic local search is based on the Inertial Shaker method: candidate points are generated in an adaptive search box and a moving average of the steps filters out evaluation noise and high-frequency oscillations. The overall subdivision of the input space in a tree of non-overlapping search districts is adaptive, with a finer subdivision in the more interesting input zones, potentially leading to lower local minima. Finally, a portfolio of independent CoRSO search streams (P-CoRSO) is proposed to increase the robustness of the algorithm. An extensive experimental comparison with Genetic Algorithms and Particle Swarm demonstrates that CoRSO and P-CoRSO reach results which are fully competitive and in some cases significantly more robust.%Straipsnyje pasiūlytas euristinis globalios optimizacijos metodas, derinant kombinatorinę ir tolydžią paiešką. Kombinatorinė komponentė, pagrįsta reaktyvine optimizacine paieška (ROP), generuoja binarines eilutes, kuriomis apibrėžiama paieškos sričių trajektorija. Reaktyvus draudimo mechanizmas užtikrina, kad paieška neįstrigs lokaliai optimalioje srityje. Tolydi stochastinė lokali paieška yra pagrįsta inerciniu plakimo metodu: žingsniai generuojami adaptyviai parenkamoje dėžėje ir slenkančio vidurkio metodu filtruojamas triukšmas bei aukšto dažnio osciliacijos. Paieškos erdvė adaptyviai skaidoma j nepersidengiančių paieškos sričių medį tankiau skaidant įdomias sritis, taip ieškant geresnių lokalių minimumų. Algoritmo patvarumui užtikrinti naudojamas nepriklausomų ROP srautas. Išsamiais eksperimentais parodyta, kad ROP ir ROP srautas yra konkurencingi genetinių ir dalelių spiečių algoritmų atžvilgiu, ir kai kuriais atvejais žymiai patvaresni negu pastarieji.