臺灣博碩士論文加值系統

加強版基因遺傳演算法(competent genetic algorithms) 透過各式各樣不同的機制來辨識基因之間是否存在鏈結(linkage) 並建立模型以解決問題。它們在真實世界中有著不少的應用，但是它們建立出來的模型是否為基因遺傳演算法真正所想要的卻不得而知。本論文提出以適應度函數的計算次數(number of function evaluation, Nfe) 作為評比模型效能的指標，並定義以最少Nfe 解決問題者為最佳模型。組成該模型的建構模塊(building blocks, BBs) 則定義為正確的建構模塊，且定義每一對屬於同一建構模塊的基因之間存在鏈結。基於以上的定義，我們檢視了一些現存用於偵測鏈結的指標函式，像是非線性(non-linearity)、熵(entropy)、同步性(simultaneity) 以及DMC。我們發現，這些指標函式先天上無法辨識某些問題的正確鏈結。於是本論文設計了一個新的指標函式：eNFE ，以補足它們的缺憾。eNFE 是根據建構模塊的新定義而設計，它藉由現存的基因遺
傳演算法理論來估測鏈結所需要的適應度函數計算次數。實驗證實eNFE 成功地幫助現存的指標函式辨識了之前無法正確辨識的鏈結。這個結果提供了一個探討模型建立與鏈結辨識的全新觀點。

Competent genetic algorithms (competent GAs) identify linkages between genes and build models via various mechanisms to solve problems. They have been applied
for real world applications, but whether the models given by them match what are really preferred to solve the problems is yet unknown. This thesis proposes using the number of function evaluation (Nfe) to measure the performance of models and defines the optimal model to be the one that consumes the fewest Nfe for GAs to solve a specific problem. Then the building blocks (BBs) that construct the optimal model are defined as the correct BBs, and correct linkages exist between any two genes which locate in the same BB. The capabilities of existing linkage-identification metrics, including non-linearity, entropy, simultaneity and DMC, are compared based on this definition. We find that all these metrics fail to identify
correct linkages for some typical problems intrinsically. This thesis then proposes a new metric, named eNFE, directly based on the idea of Nfe to enhance the existing
linkage-identification metrics. Experiment results show that eNFE is able to identify correct linkages for examined problems. The preliminary success suggests another view on learning linkage.

Acknowledgement i
摘要ii
Abstract iii
Contents iv
List of Figures vi
List of Tables viii
List of Abbreviations ix
List of Symbols x
1 Introduction 1
2 Genetic Algorithm 3
2.1 General GA Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 New Method to Search Minimum NFE . . . . . . . . . . . . . . . . . 8
3 Competent GA 14
3.1 Building Block Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Linkage-identification Metrics . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 A Practical View on Building Blocks: the fewest NFE 20
4.1 New Definition for BBs . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 B-trap: the problem developed from B′ezier curve . . . . . . . . . . . 25
4.3 Non-linearity and Dependency . . . . . . . . . . . . . . . . . . . . . . 28
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5 Proposed Metric: eNFE 35
5.1 Assumption and Designing Ideas . . . . . . . . . . . . . . . . . . . . 36
5.2 Convergence Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.3 Supplies of Correct Schemata . . . . . . . . . . . . . . . . . . . . . . 38
5.4 Ensure Converging to Correct Schemata . . . . . . . . . . . . . . . . 39
5.5 To Link or Not to Link . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6 Experiments and Discussions 44
6.1 DSMGA with Non-linear Models + eNFE . . . . . . . . . . . . . . . 45
6.2 Another Meaning of eNFE: Model-switching Time . . . . . . . . . . . 47
6.3 DMC + eNFE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.4 DSMGA + eNFE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7 Conclusions 53
Bibliography 55

[1] C. Aporntewan and P. Chongstitvatana. Building-block identification by simultaneity
matrix. Proceedings of the Genetic and Evolutionary Computation
Conference (GECCO-2003), pages 1566–1567, 2003.
[2] T. B‥ack. Generalized convergence models for tournament- and (mu, lambda)-
selection. In ICGA, pages 2–8, 1995.
[3] S.-C. Chen and T.-L. Yu. Difficulty of linkage learning in estimation of distribution
algorithms. In GECCO, pages 397–404, 2009.
[4] C.-Y. Chuang and Y.-p. Chen. Likage identification by perturbation and decision
tree induction. In IEEE Congress on Evolutionary Computation, pages
357–363, 2007.
[5] E. D. de Jong, R. A.Watson, and D. Thierens. On the complexity of hierarchical
problem solving. In GECCO, pages 1201–1208, 2005.
[6] R. Etxeberria and P. Larra˝naga. Global optimization using bayesian networks.
Proceedings of the Second Symposium on Arti cial Intelligence Adaptive Sys-
tems, pages 332–339, 1999.
[7] K.-C. Fan, J.-T. Lee, T.-L. Yu, and T.-Y. Ho. Interaction-detection metric
with differential mutual complement for dependency structure matrix genetic
algorithm. In IEEE Congress on Evolutionary Computation, pages 3010–3017,
2010.
[8] D. E. Goldberg. Simple genetic algorithms and the minimal, deceptive problem.
Genetic Algorithms and Simulated Annealing, pages 74–88, 1987.
[9] D. E. Goldberg. Genetic algorithms in search, optimization and machine learn-
ing. Reading, MA: Addison-Wesley, 1989.
[10] D. E. Goldberg. The Design of Innovation: Lessons from and for Competent
Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, USA, 2002.
[11] D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the
sizing of populations. Complex Systems, vol. 6:333–362, 1992.
[12] D. E. Goldberg, K. Sastry, and T. Latoza. On the supply of building blocks. Pro-
ceedings of the Genetic and Evolutionary Computation Conference (GECCO-
2001), pages 336–342, 2001.
[13] W. J. Gordon and R. F. Riesenfeld. Bernstein-b′ezier methods for the computeraided
design of free-form curves and surfaces. J. ACM, 21(2):293–310, 1974.
[14] G. R. Harik. Finding multimodal solutions using restricted tournament selection.
In ICGA, pages 24–31, 1995.
[15] G. R. Harik. Linkage learning via probabilistic modeling in the ecga. IlliGAL
Report No. 99010, University of Illinois at Urbana-Champaign, Urbana, IL,
February 1999.
[16] G. R. Harik, E. Cantu-Paz, D. E. Goldberg, and B. L. Miller. The gambler’s
ruin problem, genetic algorithms, and the sizing of populations. Proceedings of
the IEEE International Conference on Evolutionary Computation, pages 7–12,
1997.
[17] G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm.
Proceedings of the IEEE International Conference on Evolutionary Computa-
tion, pages 523–528, 1998.
[18] J. H. Holland. Adaptation in natural and arti cial systems. Ann Arbor, MI:
University of Michigan Press, 1975.
[19] H. Kargupta. The performance of the gene expression messy genetic algorithm
on real test functions. In International Conference on Evolutionary Computa-
tion, pages 631–636, 1996.
[20] D. Knjazew and D. E. Goldberg. Omega - ordering messy ga: Solving permutation
problems with the fast genetic algorithm and random keys. In GECCO,
pages 181–188, 2000.
[21] J.-T. Lee, K.-C. Fan, and T.-L. Yu. The essence of real-valued characteristic
function for pairwise relation in linkage learning for edas. TEIL Report No.
2011002, National Taiwan University, Taipei, Taiwan, February 2011.
[22] M. Munetomo and D. E. Goldberg. Designing a genetic algorithm using linkage
identification by nonlinearity check. Technical report, 1998.
[23] M. Munetomo and D. E. Goldberg. Identifying linkage groups by
nonlinearity/non-monotonicity detection. Proceedings of the Genetic and Evo-
lutionary Computation Conference (GECCO-1999), pages 433–440, 1999.
[24] M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent
genetic algorithms. Proceedings of the Genetic and Evolutionary Computation
Conference (GECCO-2001), pages 511–518, 2001.
[25] M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. BOA: The bayesian optimization
algorithm. Proceedings of the Genetic and Evolutionary Computation
Conference (GECCO-1999), pages 525–532, 1999.
[26] M. Pelikan and H. M‥uhlenbein. The bivariate marginal distribution algorithm.
Technical report, 1999.
[27] C. R. Reeves and J. E. Rowe. Genetic Algorithms: Principles and Perspectives:
A Guide to GA Theory. Kluwer Academic Publishers, Norwell, MA, USA, 2002.
[28] G.-C. Rota. The number of partitions of a set. The American Mathematical
Monthly, 71(5):498–504, May 1964.
[29] C. E. Shannon. A mathematical theory of communication. The Bell System
Technical Journal, vol. 27:379–423, 1948.
[30] D. Thierens and D. E. Goldberg. Convergence models of genetic algorithm
selection schemes. In PPSN, pages 119–129, 1994.
[31] M. Tsuji, M. Munetomo, and K. Akama. Modeling dependencies of loci with
string classification according to fitness differences. Proceedings of the Ge-
netic and Evolutionary Computation Conference (GECCO-2004), pages 246–
257, 2004.
[32] D. Wolpert and W. G. Macready. No free lunch theorems for optimization.
IEEE Trans. Evolutionary Computation, 1(1):67–82, 1997.
[33] T.-L. Yu, D. E. Goldberg, A. Yassine, and Y.-P. Chen. Genetic algorithm design
inspired by organizational theory: Pilot study of a dependency structure matrix
driven genetic algorithm. In GECCO, pages 1620–1621, 2003.
[34] T.-L. Yu, K. Sastry, D. E. Goldberg, and M. Pelikan. Population sizing for
entropy-based model building in discrete estimation of distribution algorithms.
In GECCO, pages 601–608, 2007.