臺灣博碩士論文加值系統

電子產品在產品製作的過程中，都會使用相關的測試儀器與設備來監測產品品質，而產品內部印刷電路板上的測試點即是方便機器檢測的關鍵點。如何將測試的涵蓋率提昇到最大，以及花費最少的製作費用，使整個製造與測試過程更有效率的執行，將是重要的議題，而此議題與組合性最佳化的問題有關。本論文研製之目的是期望對於印刷電路板的測試點規劃，以最大測試涵蓋率並且為最低價格為績效準則，以強化型混合免疫基因演算法與其他求解方法如基因演算法比較，嘗試以不同的參數與條件設定進行反覆驗證，結果證明強化型混合免疫基因演算法，確實能成為印刷電路板測試選取問題，可有效的計算與適切找出，接近最佳解的近似解的方法之一。

In the manufacture process of electronic products, some test facilities are usually used to monitor the quality of products. The test points on PCB (Printed Circuit Board) are the key issues to make the test procedure much easier. It’s important to achieve the maximum coverage rate with least costs for the selected test points on PCB. Therefore, the main purpose of this thesis focused on the way to select test points on PCB that can satisfy the criteria. We propose the Enhanced Hybrid Immune and Genetic Algorithm (EHIGA) to find the suitable test points on PCB. According to the experimental results, it shows that the proposed Enhanced Hybrid Immune and Genetic Algorithm can be used to find the test points on PCB effectively.

書名頁………………………………………………………………………………...….i論文口試委員審定書.……………………………………………...…………………...ii授權書………………………………………………………………...………………...iii中文摘要…………………………………………………....…………..……………....iv英文摘要…………………………………………………………………………...……v誌謝………………………………………………………………………...………...…vi目錄………………………………………….………………………………..………..vii表目錄.............................................................................................................................ix圖目錄..............................................................................................................................x第一章 緒論 ……………...…………………………….………...…………….……...1
1.1 研究背景與動機……………………........…..…………………….…………1
1.2 研究目的..………………...…………………………...………..……………3
1.3 研究架構與流程..…………………………………………….............…...…3
第二章 文獻探討……......………………………………..…......……...........................6
2.1 印刷電路板測試點……………………...…….………………..….……….…6
2.1.1 測試點相關資訊介紹…………………………………………....………….6
2.1.2 測試點選取與限制……………………………………………..………...…9
2.1.3 測試點涵蓋率與成本計算…………………..………………….…………10
2.2 基因演算法……………………………………...….…..…………….…...…11
2.2.1 基因演算法的特性…………………………….……………………..……13
2.2.2 基因演算法的流程…………………………….……………………..……14
2.2.3 基因演算法之相關研究……………………….……………………..……21
2.3 類免疫演算法……………………………………..….………..……….……22
2.3.1 類免疫演算法的特性…………………………….…………………..……26
2.3.2 類免疫演算法的流程…………………………….…………………..……27
2.3.3 類免疫演算法之相關研究……………………….…………………..……29
第三章 研究方法…………………………………………………..…………….……32
3.1 EHIGA演算法流程…………………………….……………………….……33
3.2 EHIGA演算法之特性………………………….……………………….……37
第四章 實驗結果與分析……………………………………………………..….……38
4.1 其他比較之演算法…………….…………………………………………….38
4.2問題定義與介紹………………...………………..……………………...……39
4.2.1 測試點選取原則……………...……………….…………………………...40


4.2.2 測試點選取之績效衡量準則…………………………………….…..……40
4.2.3 測試點選取案例………………………………………………….…..……40
4.2.4 測試點選取之範圍限制與假設………………………………….…..……41
4.2.5 測試點選取的求解方法…………...………………………………………41
4.3 實驗參數設定…………………………………………………….…….....…42
4.4實驗結果比較…………...……………..…………………………...…………42
4.4.1 非主機板的附屬卡類印刷電路板測試點選取實驗結果……………...…42
4.4.2 其他類型問題的印刷電路板測試點選取實驗結果…………………...…44
4.4.3 各種不同參數設定對於實驗結果的影響結果…………………….…..…58
4.4.3.1 不同的Crossover rate參數設定對於實驗結果的影響結果……………59
4.4.3.2 不同的Mutation rate參數設定對於實驗結果的影響結果…………..…63
4.4.3.3 不同的Population參數設定對於實驗結果的影響結果……………..…67
第五章 結論………………………......……………………………….………………71
5.1研究成果……………………………………..……………..…………………77
5.2未來展望……………………………………..……………..…………………72
參考文獻……………………………………..………….……..………………………73

[1]P. Brucker, Sceduling algorithms, Springer, Berlin, 1998.
[2]R. Bellman, “Dynamic Programming and a New Formalism in the Calculus of Variations,” Proc Natl Acad Sci USA, 40(4), pp. 231-235, Apr. 1954.
[3]R. E. Gomory and W. J. Baumol, “Integer Programming and Pricing,” Econometrica, vol. 28, pp. 521-550, 1960.
[4] E. L. Lawler and D. E. Wood, Operations Research, vol. 14, no. 4 (Jul. - Aug., 1966), pp. 699-719.
[5]R. Gangadharan and C. Rajendran, “A Simulated Annealing Heuristic for Scheduling in a Flowshop with Bicriteria,” Computers &; Industrial Engineering, vol. 27, pp. 437-476, 1994.
[6]C. S. Sung, Y. H. Kim and S. H. Yoon, “A Problem Reduction and Decomposition Approach for Scheduling for a Flowshop of Batch Processing Machines,” European Journal of Operational Research, vol. 121, pp. 179-192, 2000.
[7]M. Widmer and A. Hertz, “A New Heuristic Method for the Flowshop Sequencing Problem,” European Journal of Operational Research, vol. 41, pp. 186-193, 1989.
[8]Z. Yong and N. Sannomiya, “An Improvement of Genetic Algorithms by Search Space Reductions in Solving Large-scale Flowshop Problems,” The Transactions of the Institute of Electrical Engineers of Japan, pp. 1010-1015, 2001.
[9]F. T. S. Chan, S. H. Chung, and P. L. Y. Chan, “Application of Genetic Algorithms with Dominant Genes in a Distributed Scheduling Problem in Flexible Manufacturing Systems,” International Journal of Production Research, vol. 44, pp. 523-543, 2006.
[10]M. Kubiak, “Distance Metrics and Fitness-Distance Analysis for the Capacitated Vehicle Routing Problem,” the 6th Metaheuristics International Conference, Vienna, Austria, 2005.
[11]V. R. Neppali, C. L. Chen, and J. N. D. Gupta, “Genetic Algorithms for the Two-stage Bicriteria Flowshop Problem,” European Journal of Operational Research, vol. 95, pp. 356-373, 1996.
[12]C. X Wang, et al, “A Novel Genetic Algorithm Based on Gene Therapy Theory,” Transactions of the Institute of Measurement and Control, vol. 28, pp. 253-262, 2006.
[13]S. Endoh, N. Toma, K. Yamada, “Immune algorithm for n-TSP,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, vol. 4, pp. 3844-3849, 1998.
[14]John Holland, “Adaptation in natural and Artificial System,” Ann Arbor: University of Michigan Press, 1975.
[15]N. Kubota, K. Shimojima, and T. Fukuda, “The Role of Virus Infection in Virus-Evolutionary Genetic Algorithm,” Proceedings of IEEE International Conference Evolutionary Computation, pp. 182-187, 1996.
[16]V. Valls, F. Ballestín, S. Quintanilla, “A Hybrid Ggenetic Algorithm for the Resource-constrained Project Scheduling problem,” European Journal of Operational Research, vol. 185, no. 2, pp. 495-508, 2008.
[17]P. C. Chang, S. H. Chen, and K. L. Lin, “Two Phase Subpopulation Genetic Algorithm for Parallel Machine Scheduling Problem,” Expert Systems with Applications, vol. 29, no. 3, pp. 705-712, 2005.
[18]D. Dasgupta, “Artificial Neural Networks and Artificial Immune Systems：Similarities and Differences,” Proceeding of the IEEE Transaction on Systems, Man and Cybernetics, vol. 1, pp. 873-878, 1997.
[19]D. Dasgupta, and N. Attoh-Okine, “Immunity-Based Systems：A Survey,” Proceeding of the IEEE International Conference on Systems, Man and Cybernetics, vol. 1, pp. 369-374, 1997.
[20]L. N. de Castro, and F. J. von Zuben, “The Clonal Selection Algorithm with Engineering Application,” Proceedings of the Genetic and Evolutionary Computation Conference, vol. 1, pp. 36-37, 2000.
[21]F. Gonzalez, and D. Dasgupta, “Artificial Immune Systems Research in the Last Five Years,” Proceedings of the Congress on Evolutionary Computation Conference, Canberra, pp. 8-12, 2003.
[22]C. A. Coello, D. C. Rivera, N. C. Cortes, “Use of an artificial immune system for job shop scheduling,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) vol. 2787, pp.1-10, 2003.
[23]O. Engin, and A. Doyen, “A New Approach to Solve Hybrid Flowshop Scheduling Problems by Artificial Immune System,” Future Generation Computer Systems 20 (6 SPEC. ISS.), pp. 1083-1095, 2004.
[24]M. Chandrasekaran, P. Asokan, S. Kumanan, T. Balamurugan, S. Nickolas, “Solving Job Shop Scheduling Problems Using Artificial Immune System,” International Journal of Advanced Manufacturing Technology, vol. 31, no. 5-6, pp. 580-593, 2006.
[25]R. Tavakkoli-Moghaddam, A.R. Rahimi-Vahed, A. H. Mirzaei, “Solving a Multi-objective No-wait Flow Shop Scheduling Problem with an Immune Algorithm,” International Journal of Advanced Manufacturing Technology, vol. 36, no. 9-10, pp. 969-981, 2008.
[26]施雅月，「智慧型決策」，交通大學資訊管理所博士班，2003。
[27]羅惠文，「以類免疫演算法求解流程型排程問題」，碩士論文，元智大學，2010。
[28]洪櫻慈，「基因演算法在向量量化之應用」，碩士論文，樹德科技大學，2005。
[29]吳鈴淳，「以兩階段基因免疫演算法改良生存策略求解流程型排程問題」，碩士論文，元智大學，2009。
[30]郭宏傑，「最大利潤機組排程與風險分析之研究」，碩士論文，中山大學，2010。
[31]徐浩軒，「以類免疫演算法為基礎之移動式機器人避障路徑規劃」，碩士論文，龍華科技大學，2004。
[32]張慶彬，「應用分散式類免疫演算法於 散熱片之最佳化設計」，碩士論文，大 同 大 學，2004。