Development of Heuristic Algorithms for Branching and Nested Factor Design of Computer Experiment

應用於分支與內含因子電腦實驗設計之啟發示演算法

沈建豪(Chen-Hao Shen)

指導教授 ： 蘇哲平

國立清華大學/工學院/工業工程與工程管理學系/碩士(2010年)

https://doi.org/10.6843/NTHU.2010.00124

摘要

Engineering design problems are often too expensive to conduct physical experiments. To cope with this challenge, computer simulation is used to conduct preliminary design. However, when the simulation model is very complex, it might take days or even weeks to run a single setting. Hence, how to properly design the experiments is an important issue. In this paper, we develop a framework to design experiments which are suitable for computer simulation. The contributions of this paper are five folds. First, we construct a new objective function by combining the design principles of maximum minimum-inter-site distance and minimum linear correlation. Second, three heuristic algorithms based on Genetic Simulated Annealing (GSA)、Threshold Tabu Search (TTS) and Particle Swarm Optimization (PSO) are developed to solve the problem. The contribution is especially significant in the development of PSO algorithm. PSO traditionally is used to solve the problem with continuous decision variables. In this paper, we develop a new PSO algorithm that can be used to solve problems with discrete decision variables. Three algorithms are compared in various situations. The result shows that new PSO algorithm gives the best solution. Third, we use the PSO algorithm combine with the new objective function to generate designs. These designs are compared in two bench mark problems with other designs in the literature. The results shows this approach outperform other designs in the bench mark problems. Fourth, this design approach can take nested and branching factor as well as their interaction into account. Nested factors are those who exist only within the level of another factor. Branching factors are factors within which other factors are nested. Last but not least, we use an inventory management problem with branching and nested factors to show that by integrating the design method proposed by this paper and regression, we can construct an accurate approximation model

關鍵字

實驗設計 ； 粒子群最佳化演算法 ； 電腦實驗 ； 電腦模擬

並列摘要

無資料

並列關鍵字

Design of Experiment ； Particle Swarm Optimization ； Computer Experiment ； Computer Simulation

參考文獻

Box, G., Bisgaard, S.and Fung, C. “An Explanation and Critique of Taguchi's Contributions to Quality Engineering”, Quality and Reliability Engineering International, 4, 123-131, (1988).

Bratley, P., Fox, B.L. “Algorithm 659. Implementing Sobol’s Quasirandom Sequence Generator.”, ACM Transactions on Mathematical Software, 14, 88–100, (1988).

Butler, N. A. “Optimal and Orthogonal Latin hypercube Designs for Computer Experiments”, Biometrika, 88, 847-857, (2001).

Cheng, R., Gen, M. and Tsujimura, Y. “A Tutorial Survey of Job-shop Scheduling Problems Using Genetic Algorithms, Part II: Hybrid Genetic Search Strategies”, Computers & Industrial Engineering, 36, 343-364, (1999).

Crisfield, M.A. “Non-linear Finite Element Analysis of Solids and Structures.”, 1,Wiley, NewYork, (1991).