An extended pattern search algorithm for three-dimensional component layout

An extended pattern search algorithm is introduced for efficient component layout optimization. The algorithm is applicable to general layout problems, where component geometry can be arbitrary, design goals can be multiple and spatial constraint satisfactions can be of different types. Extensions to pattern search are introduced to help the algorithm to converge to optimal solutions by escaping inferior local minima. The performance on all of the test problems shows that the algorithm runs one-to-two orders of magnitude faster than a robust simulated annealing- based algorithm for results with the same quality. The algorithm is further extended to solve a concurrent layout and renting problem, which demonstrates the ability of the algorithm to apply new pattern strategies in search and to include different objective functions in optimization. [S1050-0472(00)01901-2].