Objective Function Effect Based Pattern Search—Theoretical Framework Inspired by 3D Component Layout

Abstract

Though pattern search algorithms have been successfully applied to three-dimensional (3D) component layout problems, a number of unanswered questions remain regarding their parameter tuning. One such question is the scheduling of patterns in the search. Current pattern search methods treat all patterns similarly and all of them are active from the beginning to the end of the search. Observations from 3D component layout motivate the question whether patterns should be introduced in some different order during the search. This paper presents a novel method for scheduling patterns that is inspired by observations from 3D component layout problems. The new method introduces patterns into the search in the decreasing order of a priori expectation of the objective function change due to the patterns. Pattern search algorithms based on the new pattern schedule run 30% faster on average than conventional pattern search based algorithms on 3D component layout problems and general 2D multimodal surface minimization problems. However since determining the expected change in objective function value due to the patterns is expensive, we explore approximations using domain information.