Exploring the effectiveness of various patterns in an extended pattern search layout algorithm

摘要

Automated synthesis of product layout has the potential of substantially reducing design cycle time while allowing for quick check of interference, clearance, scale and fit prior to the building of physical prototypes. The search for optimal positions and orientations of parts in the layout typically requires a huge number of iterations. An extended pattern search layout algorithm based on coordinate search was introduced in an earlier paper and shown one-to-two orders of magnitude improvement in speed over a robust simulated annealing-based layout algorithm. Coordinate search is a simple and straightforward way of implementing the pattern search method in the layout problem. However, it is not taking advantage of the wide variety of heuristics admissible in pattern search methods for identifying promising search directions. By introducing various search patterns and exploring their effectiveness in the layout problem, we will address the question of whether complex tactics can do better than the basic coordinate pattern search. We present in this paper four different heuristics for generating pattern directions in the extended pattern search layout algorithm: the conjugate direction method, the modified gradient method, the rank ordering method, and the simplex method. These heuristics are utilized to identify promising search directions and update the set of pattern directions used in the algorithm over iterations. The performance of the different heuristics is compared to that of the basic coordinate pattern search layout approach.