La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | julius-maximilians-universitat_wurzburg |
Publié le | 01 janvier 2008 |
Nombre de lectures | 38 |
Langue | Deutsch |
Poids de l'ouvrage | 6 Mo |
Extrait
Global Optimization Methods
based on Tabu Search
Dissertation zur Erlangung des
naturwissenschaftlichen Doktorgrades
der Julius-Maximilians-Universität Würzburg
vorgelegt von
Svetlana Stepanenko
aus Ivanovo
Würzburg 2008
Eingereicht am: 30.10.2008________________________________________________
bei der Fakulät für Chemie und Pharmazie
1. Gutachter: Prof. Dr. Bernd Engels_______________________________________
2. Gutachter: PD Dr. Reinhold Fink________________________________________
der Dissertation
1. Prüfer: Prof. Dr. Bernd Engels_______________________________________
2. Prüfer: PD Dr. Reinhold Fink________________________________________
3. Prüfer: Prof. Dr. Christoph Sotriffer___________________________________
des Öffentlichen Promotionskolloquiums
Tag des Öffentlichen Promotionskolloquiums: 05.12.2008_________________________
Doktorurkunde ausgehändigt am: __________________________________
dedicated to the memory of my father,
Nikolay Valentinovich Kuznetsov
Die vorliegende Arbeit wurde unter Anleitung von Prof. Dr. Bernd Engels von Mai 2004 bis
Oktober 2008 am Institut für Organische Chemie der Julius-Maximilians-Universität
Würzburg angefertigt.
333,338Teilergebnisse dieser Arbeit waren Gegenstand von Publikationen sowie von Postern
und Kurzvorträgen.
Acknowledgements
The preparation of this thesis would not have been succeeded the way it did without
the support of many people contributed directly or indirectly. First of all, I extend my
gratitude and appreciation to my supervisor, Prof. Dr. Bernd Engels, whose suggestions, help,
valuable insights, motivation, and encouragement helped me in all the time of research and
writing of this thesis, whose comments and criticism ensure the quality of it. My sincerest
thanks also go to Priv.-Doz. Dr. Reinhold Fink, who kindly accepted the task of reviewing the
present thesis, for his inspiring conversations, for the time he invested in helping me with all
sorts of theoretical chemistry problems. I thank Prof. Dr. K. Baumann for fruitful discussions.
My additional thanks go to all members of the group (past and current) for all their help,
support, interest and helpful hints, for a friendly and humorous climate.
Ongoing financial support by the Deutsche Forschungsgesellschaft in the framework
of the SPP 1178 and the SFB 630 is gratefully acknowledged.
Finally, I would like to express my dearest thanks to my parents, Nikolay Kuznetsov
and Nadezhda Kuznetsova, who supported me for better for worse, for guidance in sending
me down the right path in my education and in life, for their continuous love, encouragement,
and understanding during my life. I wish to thank my family, Oleg and Vladimir Stepanenko
for their insight, support, and patience, which allowed me to concentrate and finish my work
on this thesis. Thank you for always standing by my side in all situations and believing in me
when I didn’t believe in myself.
“Die Phantasie arbeitet in einem schöpferischen Mathematiker nicht weniger als in einem
erfinderischen Dichter.“
Jean-Baptist le Rond D'Alembert (1717 - 1783)
“Es ist nicht genug, zu wissen, man muß auch anwenden; es ist nicht genug, zu wollen, man
muß auch tun.“
Johann Wolfgang von Goethe (1749-1832)
Table of Contents
Chapter 1 Introduction ...................................................................................................... 3
1.1 Global Optimization (GO) Problem........................................................................... 4
1.2 Heuristics.................................................................................................................... 6
1.2.1 Metaheuristic Features ....................................................................................... 7
1.2.2 Population metaheuristic.................................................................................. 10
1.2.2.1 Swarm methods............................................................................................ 10
1.2.2.1.1 Ant Colony Optimization (ACO)............................................................. 11
1.2.2.1.2 Particle Swarm Optimization (PSO) ........................................................ 14
1.2.2.2 Genetic Algorithms (GAs) ........................................................................... 18
1.2.2.3 Scatter Search (SS) 22
1.2.3 Simulated Annealing (SA) ............................................................................... 25
1.2.4 Variable Neighbourhood Search (VNS) .......................................................... 30
1.2.5 Tabu Search (TS) ............................................................................................. 37
1.3 Conclusions .............................................................................................................. 46
Chapter 2 TS based methods........................................................................................... 48
2.1 Gradient Tabu Search............................................................................................... 48
2.1.1 Algorithm description ...................................................................................... 48
2.1.1.1 Modest Ascent and Local Search Strategy................................................... 50
2.1.1.2 Diversification Strategy................................................................................ 55
2.1.2 TS Memory Elements....................................................................................... 56
2.1.3 Implementation and Experiments..................................................................... 59
2.1.3.1 Parameters .................................................................................................... 60
2.1.3.2 Numerical Results ........................................................................................ 63
2.1.4 Conclusions ...................................................................................................... 70
2.2 TSPA and GOTS 70
2.2.1 Description of algorithms................................................................................. 71
2.2.2 Investigation of the efficiency of the new approaches..................................... 75
2.2.2.1 Parameters .................................................................................................... 76
2.2.2.2 Tests of the efficiency .................................................................................. 80
2.2.3 Conclusions 91
2.3 Conclusions .............................................................................................................. 92
-1-
Chapter 3 Application and Discussion ........................................................................... 94
3.1 Introduction .............................................................................................................. 94
3.1.1 Conformational search techniques ................................................................... 95
3.2 GOTS application................................................................................................... 106
3.2.1 Variable choice and numbering rules............................................................. 106
3.2.2 Adaptation of the GOTS to the conformational search.................................. 109
3.2.3 Comparing the influence of different parameters .......................................... 115
3.3 Experimental results............................................................................................... 117
3.3.1 Conformational studies of amino acids.......................................................... 121
3.3.2 Conformational studies of acetylcholine....................................................