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

Article type: Research Article

Authors: Brunato, Mauro | Battiti, Roberto^{; *}

Affiliations: Department of Information Engineering and Computer Science, University of Trento, Italy. E-mails: [email protected], [email protected]

Correspondence: [*] Corresponding author.

Abstract: 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.

Keywords: global optimization, reactive search optimization, algorithm portfolios

Journal: Informatica, vol. 27, no. 2, pp. 299-322, 2016