適度-距離相關性分析之研究

A Study on Fitness-Distance Correlation Analysis

徐浩騰(Hao-Teng Hsu)

指導教授 ： 吳建文

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2010年)

摘要

由於適度-距離相關性分析是驗證演算法成效、分析搜尋空間結構的一個很有用的工具。因此，本研究撰寫出適度-距離相關分析的程式，使用和Stutzle一樣的二次指派問題測試範例來證明程式的正確性。除此之外，本研究將適度-距離相關分析應用在訂單排序的問題上，也證明了適度-距離相關性分析的有效性。

關鍵字

適度-距離相關性分析 ； 區域搜尋 ； 二次指派問題 ； 訂單排序問題

並列摘要

The Fitness-Distance Correlation (FDC) analysis is a very useful tool to verify the effectiveness of algorithms and to analyze search space structure. This study designs the FDC analysis programs and uses the same test samples of Quadratic Assignment Problem (QAP) as Stutzle used to demonstrate the correctness of the programs. Moreover, the study applies FDC analysis approach on Order Sequence Problem to prove that the FDC analysis can be applied to other issues effectively.

並列關鍵字

FDC analysis ； Local search ； QAP ； Order Sequence Problem

參考文獻

[2] T. Stutzle,” Iterated local search for the quadratic assignment problem,” European Journal of Operational Research, vol. 174, no. 3, 2006, pp. 1519-1539.

[4] E.D. Weinberger,” Correlated and uncorrelated fitness landscapes and how to tell the difference,” Biological Cybernetics, vol. 63,no. 5, 1990, pp. 325-336

[8] K.D. Boese, A.B. Kahng, S. Muddu,” A new adaptive multi-start technique for combinatorial global optimizations,” Operations Research Letters, vol. 16, 1994, pp. 101–113.

[13] E. Balas and M.C. Carrera,”A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering,” OPERATIONS RESEARCH, vol. 44, no.2, 1996, pp.875-890.

[16] M. Tomassini, L. Vanneschi, P. Collard, M. Clergue,” A study of fitness distance correlation as a difficulty measure in genetic programming,” Evolutionary Computation, vol. 13, no. 2, 2005, pp. 213-239.