臺灣博碩士論文加值系統

目前在科學、工程以及生物等各種不同領域中，有許多問題需要透過演化式
計算的方法來達成最佳化的目標，如在藥物設計的過程中，改變化合物不同的構
形，來達成能量穩定的嵌合狀態，做為藥物設計的樣版，或是建立人體運動模型，
來預測人類的運動行為。然而，在許多的研究成果中，演化式計算對於最佳化的
效能有著相當顯著的提升。因此，在本論文中，將介紹一種模擬鳥群覓食行為的
演化式演算法－「粒子群最佳化演算法」，並研究粒子間的行為模式對於整體效
能所造成影響並加以探討，在演化過程中發現，粒子經常會陷入局部最佳解造成
提早收斂，通常是因為粒子在飛行過程中，未能準確擊中目標，導致粒子朝相反
方向移動，為了改善這個問題，本論文提出了－「彌因型粒子群演算法」，將傳
統的粒子群演算法，結合了一個根據成功機率動態調整的移動策略－「Solis and
Wets 的局部搜尋算子」，讓移動的粒子可以更仔細的觀察周遭是否有更佳的解
來進行取代。
為了驗證本論文所提方法的搜尋能力，分別進行兩個實驗，實數型數學參數
最佳化函式，以及蛋白質與彈性化合物嵌合，經由實驗結果得知 ，本論文所提
之方法較傳統的粒子群演算法能獲得較佳的解答。

Many scientific, engineering and biological problems involve the optimization of
a set of parameter. These problems include examples like minimizing the affinity
between the moleculars in the process of the drug design by finding the suitable
conformation of the led compound, or training a human model for predicting the
behavior of human. Numerical optimization algorithms have been proposed to
solve these problems, with varying degrees of success. The Particle Swarm Optimization
(PSO) is relatively new technique that has been empirically shown to
perform well on many kinds of optimization problems. However, some important
situations that often occur in PSO is overshooting, which is a key issue to the premature
convergence and essential to the performance of PSO. Therefore, in this
thesis, a variant particle swarm optimization, named memetic particle swarm optimization
algorithm (MeSwarm), is proposed for tackling the overshooting problem
in the movement of PSO.
MeSwarm integrates the standard PSO with the Solis and Wets local search
strategy to avoid the overshooting problem. Based on the recent probability of
success, the Solis and Wets local search strategy can efficiently generate a new
candidate solution around the current particle. Thus, an accurate moving behavior
can be ensured and the overshooting problem can be prevented. In this thesis, a
real-world optimization problem, flexible protein-ligand docking, and six numerical
test functions optimization are used to validate the performance of MeSwarm. The
experimental results indicate that MeSwarm outperforms the standard PSO and
several evolutionary algorithms in terms of solution quality.

Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Chapter 2 Background . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 No Free Lunch Theorem . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Evolutionary Computing . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5 Evolutionary Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.6 Evolutionary Programming . . . . . . . . . . . . . . . . . . . . . . 10
2.7 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.7.1 Chromosome and Fitness . . . . . . . . . . . . . . . . . . . . 10
2.7.2 Selection, Crossover, and Mutation . . . . . . . . . . . . . . 12
2.8 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . 14
2.8.1 Particle Swarm Optimization Algorithm . . . . . . . . . . . 14
2.8.2 Difference Between PSO and GA . . . . . . . . . . . . . . . 17
Chapter 3 Memetic Particle Swarm Optimization . . . . . . . . . 18
3.1 The Concept of the Meme . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Memetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 The Drawback of the PSO Movement . . . . . . . . . . . . . . . . . 19
3.4 Overshooting of Particle . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 Solis and Wets Local Search Strategy . . . . . . . . . . . . . . . . . 22
v
3.6 The Concept of MeSwarm . . . . . . . . . . . . . . . . . . . . . . . 25
Chapter 4 Experiment with the Numerical Functions . . . . . . 27
4.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1.1 Experiment Setting and Results . . . . . . . . . . . . . . . . 30
4.2 Comparing with other GA-based algorithms . . . . . . . . . . . . . 34
4.2.1 Experiment Setting and Results . . . . . . . . . . . . . . . . 34
Chapter 5 Flexible Protein-Ligand Docking . . . . . . . . . . . . 37
5.1 Relate Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2.1 Parameters of Ligand Conformation . . . . . . . . . . . . . . 38
5.2.2 Energy Function . . . . . . . . . . . . . . . . . . . . . . . . 39
5.3 Experimental and Results . . . . . . . . . . . . . . . . . . . . . . . 39
5.3.1 Implementation and Data Preparation . . . . . . . . . . . . 40
5.3.2 Highly Flexible Ligand . . . . . . . . . . . . . . . . . . . . . 42
5.3.3 Docking Accuracy . . . . . . . . . . . . . . . . . . . . . . . . 42
Chapter 6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.3 Main Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Vita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

References
[1] R. C. Eberhart and Y. Shi, “Comparing inertia weights and constriction factors
in particle swarm optimization,” in IEEE Internation Conference Evolutionary
Computation, vol. 1, 2000, pp. 84–88.
[2] T. Hendtlass, “Preserving diversity in particle swarm optimisation,” in Developments
in Applied Artificial Intelligence, ser. Lecture Notes in Artificial
Intelligence, 2003, vol. 2718, pp. 31–40.
[3] J. Kennedy, “The behavior of particles,” in Evolutionary Programming, V. W.
Porto, N. Saravanan, D. Waagen, and A. E. Eiben, Eds. Berlin, Germany:
Springer-Verlag, 1998, pp. 581–590.
[4] J. J. Liang, A. K. Qin, P. N. Suganthan, and S. Baskar, “Particle swarm
optimization algorithms with novel learning strategies,” in 2004 Internation
Conference on Systems, Man and Cybernetics, 2004.
[5] K. E. Parsopoulos and M. N. Vrahatis, “Initializing the particle swarm optimizer
using the nonlinear simplex method,” in Advances in Intelligent Systems,
Fuzzy Systems, Evolutionary Computation, A. Grmela and N. Mastorakis,
Eds. Interlaken, Switzerland: WSEAS press, 2002, pp. 216–221.
[6] Y. Shi and R. C. Eberhart, “A modified particle swarm optimizer,” in IEEE
Conference Evolutionary Computation, Anchorage, AK, 1998, pp. 69–73.
[7] Y. Shi and R. C. Eberhart, “Parameter selection in particle swarm optimization,”
in Evolutionary Programming, V. W. Porto, N. Saravanan, D. Waagen,
and A. E. Eiben, Eds. Berlin, Germany: Springer-Verlag, 1998, vol. 7, pp.
591–600.
[8] M. Lovbjerg, T. K. Rasmussen, and T. Krink, “Hybrid particle swarm optimiser
with breeding and subpopulations,” in Proceedings of the Genetic and
Evolutionary Computation Conference, 2001.
[9] T. Krink and M. Lovbjerg, “the life cycle model: combining particle swarm
48
optimization, genetic algorithms and hill climbers,” in Proceedings of Parallel
Problem Solving from Nature VII, 2002, pp. 621–630.
[10] F. van den Bergh and A. P. Engelbrecht, “A cooperative approach to particle
swarm optimization,” IEEE Transactions on Evolutionary Computation,
vol. 8, no. 3, pp. 225–239, 2004.
[11] P. Sunthiti, K. h. Saman, and S. Nirmala, “Optimized rule-based delay proportion
adjustment for proportional differentiated services,” IEEE Journal
on Selected Areas in Communications, vol. 23, no. 2, pp. 261–276, 2005.
[12] H. ER, Global Optimization Using Interval Analysis. Marcel Dekker, New
York, 1989.
[13] H. R. and T. H, Global Optimization V Deterministic Approaches.
MSpringer, New York, 1996.
[14] S. S. Rao, Engineering optimization-theory and practice. Wiley, 1996.
[15] H. P. Schwefel, Evolution and Optimum Seeking. Wiley, New York, 1995.
[16] F. van den Bergh, “An analysis of particle swarm optimizers,” Ph.D. dissertation,
Department of Computer Science, University of Pretoria, South Africa,
2002.
[17] D. H. Wolpert and W. G. Macready, “No free lunch theorems for optimization,”
IEEE Transactions on Evolutionary Computation, vol. 4, pp. 67–82,
1997.
[18] C. S. and F. Oppacher, “What can we learn from no free lunch ? a first
attempt to characterize the concept 0f a searchable function,” in Proceedings
of the Genetic and Evolutionary Computation Conference, 2001, pp. 1219–
1226.
[19] A. E. Eiben and S. J. E., Introduction to evolutionary computing. Springer,
2003.
[20] T. B`ack, D. B. Fogel, and Z. Michalewics, Handbook of evolutionary computation.
Institute of Physics Publishing, 1998.
[21] H.-G. Beyer and H.-P. Schwefel, “Evoultionary strategies: A comrehensive
introduction,” Natural Computing, vol. 1, pp. 3–52, 2002.
[22] J. H. Holland, Adaptation in natural and artificial systems. Ann Arbor, MI:
University of Michigan Press, 1975, iSBN: 0-262-58111-6.
49
[23] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine
Learning. Reading, MA: Addition-Wesley, 1989.
[24] J. E. Baker, “Adaptive selection methods for genetic algorithms,” Proceedings
of the International Conference on Genetic Algorithms and Their Applications,
pp. 101–111, 1985.
[25] J. J. Grefenstette and J. E. Baker, “How genetic algorithms work: A critical
look at implicit parallelism,” Proceedings of the Third International Conference
on Genetic Algorithms (ICGA-89), pp. 20–27, 1989.
[26] D. E. Goldberg, B. Korb, and K. Deb, “Messy genetic algorithms: Motivation,
analysis, and first results,” Complex Systems, vol. 3, no. 5, pp. 493–530, 1989.
[27] H. M¨uhlenbein and D. Schlierkamp-Voosen, “Predicitive models for the
breeder genetic algorithm: I. continuous parameter optimization,” Evolutionary
Computation, vol. 1, no. 1, pp. 25–49, 1993.
[28] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in IEEE
International Conference Neural Networks, vol. 4, Perth, Australia, 1995, pp.
1942–1948.
[29] J. X. Lu, Q. Shen, J. H. Jiang, G. L. Shen, and R. Q. Yu, “Qsar analysis of
cyclooxygenase inhibitor using particle swarm optimization and multiple linear
regression,” Journal of Pharmaceutical and Biomedical Analysis, vol. 35,
no. 4, pp. 679–687, 2004.
[30] Q. Shen, J. H. Jiang, C. X. Jiao, W. Q. Lin, G. L. Shen, and R. Q. Yu,
“Hybridized particle swarm algorithm for adaptive structure training of multilayer
feed-forward neural network: Qsar studies of bioactivity of organic
compounds,” Journal of Computational Chemistry, vol. 25, no. 14, pp. 1726–
1735, 2004.
[31] Z. L. Gaing, “A particle swarm optimization approach for optimum design
of pid controller in avr system,” Ieee Transactions on Energy Conversion,
vol. 19, no. 2, pp. 384–391, 2004.
[32] S. P. Ghoshal, “Optimizations of pid gains by particle swarm optimizations in
fuzzy based automatic generation control,” Electric Power Systems Research,
vol. 72, no. 3, pp. 203–212, 2004.
[33] M. Clerc and J. Kennedy, “The particle swarm-explosion, stability, and convergence
in a multidimensional complex space,” IEEE Transactions Evolu-
50
tionary Computation, vol. 6, pp. 58–73, 2002.
[34] M. M. Millonas, “Swarms, phase transitionsm and collective intelligence,” In
artificial life III, pp. 417–445, 1994.
[35] K. Parsopoulos and M. N. Vrahatis, “Recent approaches to global optimization
problems through particle swarm optimization,” Natural Computing, pp.
235–306, 2002.
[36] R. C. Eberhart and Y. Shi, “Comparison between genetic algorithms and
particle swarm optimization,” in The 7th International Conference on Evolutionary
Programming, San Diego, CA, USA, 1998, pp. 611–616.
[37] R. Dawkins, The Selfish Gene. Oxford: Oxford University Press, 1976.
[38] P. A. Moscato, “On evolution, search, optimization, genetic algorithms and
martial arts: Towards memetic algorithms,” Caltech Concurrent Computation
Program, Tech. Rep. C3P Report 826, 1989.
[39] P. A. Moscato, “Memetic algorithms: a short introduction,” New Ideas in
Optimization, pp. 219–234, 1999.
[40] F. J. Solis and R. J.-B. Wets, “Minimization by random search techniques,”
Mathematical Operations Research, vol. 6, pp. 19–30, 1981.
[41] E. G. Philip, M. Walter, and M. H. W., Practical optimization. Academic
Press, 1981.
[42] S. L.-S. Ho, S.-Y. and C. J.-H., “Intelligent evolutionary algorithms for large
parameter optimization problems,” IEEE Transactions Evolutionary Computation,
vol. 8, pp. 522–541, 2004.
[43] H.-L. H. S.-F. H. S.-Y. H. Bo-Fu Liu, Hung-Ming Chen, “Flexible proteinligand
docking using particle swarm optimization,” in The 2005 IEEE
Congress on Evolutionary Computation, 2005.
[44] D. W. Miller and K. A. Dill, “Ligand binding to proteins: The binding landscape
model,” Protein Science, vol. 6, no. 10, pp. 2166–2179, 1997.
[45] R. X. Wang, Y. P. Lu, and S. M. Wang, “Comparative evaluation of 11
scoring functions for molecular docking,” Journal of Medicinal Chemistry,
vol. 46, no. 12, pp. 2287–2303, 2003.
[46] D. S. Goodsell and A. J. Olson, “Automated docking of substrates to proteins
by simulated annealing,” Proteins: Structure, Function, and Genetics, vol. 8,
pp. 195–202, 1990.
51
[47] M. Liu and S. M. Wang, “Mcdock: A monte carlo simulation approach to the
molecular docking problem,” Journal of Computer-Aided Molecular Design,
vol. 13, no. 5, pp. 435–451, 1999.
[48] G. Jones, P. Willett, R. C. Glen, A. R. Leach, and R. Taylor, “Development
and validation of a genetic algorithm for flexible docking,” Journal of
Molecular Biology, vol. 267, no. 3, pp. 727–748, 1997.
[49] G. M. Morris, D. S. Goodsell, R. S. Halliday, R. Huey, W. E. Hart, R. K.
Belew, and A. J. Olson, “Automated docking using a lamarckian genetic
algorithm and an empirical binding free energy function,” Journal of Computational
Chemistry, vol. 19, no. 14, pp. 1639–1662, 1998.
[50] J. M. Yang and C. C. Chen, “Gemdock: A generic evolutionary method for
molecular docking,” Proteins-Structure Function and Bioinformatics, vol. 55,
no. 2, pp. 288–304, 2004.
[51] B. D. Bursulaya, M. Totrov, R. Abagyan, and C. L. Brooks, “Comparative
study of several algorithms for flexible ligand docking,” Journal of Computer-
Aided Molecular Design, vol. 17, no. 11, pp. 755–763, 2003.
[52] T. J. A. Ewing, S.Makino, A. G. Skillman, and I. D. Kuntz, “Dock 4.0: Search
strategies for automated molecular docking of flexible molecule databases,”
Journal of Computer-Aided Molecular Design, vol. 15, no. 5, pp. 411–428,
2001.
[53] M. Rarey, B. Kramer, T. Lengauer, and G. Klebe, “A fast flexible docking
method using an incremental construction algorithm,” Journal of Molecular
Biology, vol. 261, no. 3, pp. 470–489, 1996.
[54] A. Silva, A. Neves, and E. Costa, “Sappo: A simple, adaptable, predator
prey optimiser,” in Progress in Artificial Intelligence, ser. Lecture Notes in
Artificial Intelligence, 2003, vol. 2902, pp. 59–73.