The challenge of optimizing expensive black boxes: a scatter search/rough set theory approach

Abstract

There is renewed interest in the development of effective and efficient methods for optimizing models of which the optimizer has no structural knowledge. This is what in the literature is referred to as optimization of black boxes. In particular, we address the challenge of optimizing expensive black boxes, that is, those that require a significant computational effort to be evaluated. We describe the use of rough set theory within a scatter search framework, with the goal of identifying high-quality solutions with a limited number of objective function evaluations. The rough set strategies that we developed take advantage of the information provided by the best and diverse solutions found during the search, in order to define areas of the solution space that are promising for search intensification. We test our procedure on a set of 92 nonlinear multimodal functions of varied complexity and size and compare the results with a state-of-the-art procedure based on particle swarm optimization.

Keywords:

• black-box optimization
• simulation optimization
• scatter search
• rough sets

Acknowledgements

The first author is grateful for the financial support from the FEDER funds and the Spanish Ministry of Science (National Program of R&D ECO2008-06159/ECON). All other authors acknowledge the support from the Regional Government of Andalucía and the Spanish Ministry of Education and Science.

Notes

1 http://www.opttek.com