臺灣博碩士論文加值系統

No-Free-Lunch(NFL)定理指出當對所有問題作平均時，所有最佳化演算法的表現都是一致的，意即各個最佳化演算法的總體效能並無法定義孰優孰劣。然而NFL定理並不意味著泛用型最佳化演算法(general-purpose optimizers)無用武之地，只要問題存在有可供演算法利用的結構，仍有可能找到一最佳化演算法在某一問題集合上具有優勢。這份論文提出了一個問題的集合，稱之為離散化Lipschitz函數集合(discrete Lipschitz class，DLC)，且此一集合可視為透過規範搜尋空間鄰近區域的差值來模擬連續性。此論文探討了DLC和NFL定理間之關係，並證明一最佳化演算法subthreshold-seeker之推廣形式可在DLC上效能勝於random search。同時，此論文也設計了一抽樣測試法透過實驗驗證在一更實際之架構下subthreshold-seeker在DLC上之表現明顯優於random search。因此，這份論文說明了儘管最佳化演算法並無法同時對所有問題都有優異的效能，但仍然有可能在一廣泛且深具意義的問題集合上取得優勢。

The No-Free-Lunch theorem states that all algorithms have the identical performance on average over all functions and there is no algorithm able to outperform others on all problems. However, such a result does not imply that search heuristics or optimization algorithms are futile if we are more cautious with the applicability of these methods and the search space. In this paper, within the No-Free-Lunch framework, we firstly introduce the discrete Lipschitz class by transferring the Lipschitz functions, i.e., functions with bounded slope, as a measure to fulfill the notion of continuity in discrete functions. We then investigate the properties of the discrete Lipschitz class, generalize an algorithm called subthreshold-seeker for optimization, and show that the generalized subthreshold-seeker outperforms random search on this class. Finally, we propose a tractable sampling-test scheme to empirically demonstrate the superiority of the generalized subthreshold-seeker under practical configurations. This study concludes that there exists algorithms outperforming random search on the discrete Lipschitz class in both theoretical and practical aspects and indicates that the effectiveness of search heuristics may not be universal but still general in some broad sense.

1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Research Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Road Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 A Brief Review of NFL 4
2.1 NFL Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 NFL Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Discrete Lipschitz Class 7
3.1 De‾nition of the Discrete Lipschitz Class . . . . . . . . . . . . . . . . . . . 7
3.2 DLC as Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2.1 Real-parameter Optimization Problems . . . . . . . . . . . . . . . . 8
3.2.2 Combinatorial Optimization Problems . . . . . . . . . . . . . . . . 9
3.3 DLC and NFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 DLC and Subthreshold-seeker 13
4.1 Generalized Subthreshold-seeker . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Subthreshold-seeker on DLC . . . . . . . . . . . . . . . . . . . . . . . . . . 14
iv
5 Sampling-test Scheme for PDLC 21
5.1 A Uniform Sampler for PDLC . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 Experimental Settings and Results . . . . . . . . . . . . . . . . . . . . . . 25
5.3 The Estimation of Median . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6 Toward Higher Dimensions 31
6.1 Accept-reject Sampler for Planar DLC . . . . . . . . . . . . . . . . . . . . 32
6.2 MCMC Sampler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6.3 Semi-planar DLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
7 Conclusions 40
7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.2 Main Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

[1] D. H. Wolpert, W. G. Macready, No free lunch theorems for search, Tech. Rep.
SFI-TR-95-02-010, Santa Fe Institute (1995).
[2] D. H. Wolpert, W. G. Macready, No free lunch theorems for optimization, IEEE
Transactions on Evolutionary Computation 4 (1997) 67-82.
[3] J. C. Culberson, On the futility of blind search: An algorithmic view of no free
lunch", Evolutionary Computation 6 (1998) 109-127.
[4] S. Droste, T. Jansen, I. Wegener, Perhaps not a free lunch but at least a free appe-
tizer, Tech. Rep. ISSN 1433-3325, Department of Computer Science, University of
Dortmund (1998).
[5] S. Droste, T. Jansen, I. Wegener, Optimization with randomized search heuristics -
the (a)n° theorem, realistic scenarios, and di±cult functions, Theoretical Computer
Science 287 (2002) 131-144.
[6] M. J. Streeter, Two broad classes of functions for which a no free lunch result does
not hold, in: Proceedings of the Genetic and Evolutionary Computation Conference
2003, 2003, pp. 1418-1430.
[7] S. Christensen, F. Oppacher, What can we learn from no free lunch? a first attempt
to characterize the concept of a searchable function, in: Proceedings of the Genetic
and Evolutionary Computation Conference 2001, 2001, pp. 1219-1226.
[8] D. Whitley, J. Rowe, Subthreshold-seeking local search, Theoretical Computer Sci-
ence 361 (2006) 2-17.
[9] C. Schumacher, M. D. Vose, L. D. Whitley, The no free lunch and problem description
length, in: Proceedings of the Genetic and Evolutionary Computation Conference
2001, 2001, pp. 565-570.
[10] R. Courant, F. John, Introduction to Calculus and Analysis, Vol. 1, Vol. 1, Springer-
Verlag, 1989.
[11] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms,
2nd Edition, The MIT Press, 2001.
[12] R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press,
1995.
[13] I. Rechenberg, Evolutionsstrategie '94, Frommann Holzboog, 1994.
[14] J. J�軻gersk�鈉pper, Algorithmic analysis of a basic evolutionary algorithm for continu-
ous optimization, Theoretical Computer Science 379 (3) (2007) 329-347.
[15] C. Robert, G. Casella, Monte Carlo Statistical Methods, Springer-Verlag, 1999.
[16] Y. S. Chow, H. Teicher, Probability theory: independence, interchangeability, mar-
tingales, 3rd Edition, Springer, 1997.
[17] W. Hoe��ding, Probability inequalities for sums of bounded random variables, Journal
of the American Statistical Association 58 (1963) 13-30.
[18] M. Mitzenmacher, E. Upfal, Probability and Computing: Randomized Algorithms
and Probabilistic Analysis, Cambridge University Press, 2005.
[19] A. Broder, Generating random spanning trees, in: Foundations of Computer Science
1989, 1989, pp. 442-447.
[20] R. Aleliunas, R. Karp, R. Lipton, L. Lovasz, C. Racko, Random walks, univer-
sal traversal sequences, and the complexity of maze problems, in: Foundations of
Computer Science 1979, 1979, pp. 218-233.
[21] A. Broder, E. Shamir, On the second eigenvalue of random regular graphs, in: Foun-
dations of Computer Science 1987, 1987, pp. 286-294.
[22] A. Broder, A. Karlin, Bounds on cover times, Journal of Theoretical Probability 2
(1989) 101-120.
[23] Z. F�鈉redi, J. Koml�鷬s, The eigenvalues of random symmetric matrices, Combinatorica
1 (1981) 233-241.
[24] R. Y. Rubinstein, D. P. Kroese, Simulation and the Monte Carlo Method, 2nd Edi-
tion, Wiley, 2007.