%%% ==================================================================== %%% BibTeX-file{ %%% author = "Pablo Moscato, Peter Merz, and Carlos Cotta", %%% version = "3.2", %%% date = "Jan 23, 2000", %%% time = "12:00:00 MDT", %%% filename = "memetic.bib", %%% address = "Departamento de Engenharia de Sistemas, %%% Faculdade de Engenharia El{\'e}trica, %%% Universidade Estadual de Campinas, %%% C.P. 6101, %%% Campinas, SP, CEP 13081-970, %%% BRAZIL", %%% telephone = "+55 ", %%% FAX = "+55", %%% URL = "http://www.densis.fee.unicamp.br/~moscato", %%% email = "moscato at densis.fee.unicamp.br", %%% %%% codetable = "ISO/ASCII", %%% keywords = "bibliography, BibTeX, memetic algorithms", %%% supported = "yes", %%% docstring = "This is a bibliography of publications %%% related to memetic algorithms, %%% %%% There is a World Web Wide site for %%% Memetic Algorithms at %%% %%% http://www.densis.fee.unicamp.br/~moscato/memetic_home.html %%% %%% than contains this file as well as %%% links to article abstracts, and subject and %%% author indexes, related web pages, etc. %%% %%% In the bibliography entries below, URLs point %%% to freely-accessible abstracts in HTML form. % Early Memetic Algorithms % % We designate as belonging to this category all MAs % that appear in the literature before the year 1989. @Article{Kase_Nishiyama_64, author = "S. Kase and N. Nishiyama", title = "{A}n {I}ndustrial {E}ngineering {G}ame {M}odel for {F}actory {L}ayout", journal = "The Journal of Industrial Engineering", volume = "XV", number = "3", pages = "148--150", year = "1964" } @article{Brady_85, title = "Optimization strategies gleaned from biological evolution", author = "R.M. Brady", journal = "Nature", volume = "317", pages = "804--806", year = "1985" } @article{Kauffman_Levin_87, author = "S.A. Kauffman and S. Levin", year = "1987", title = "Towards a General Theory of Adaptive Walks on Rugged Landscapes", journal = "Journal of Theoretical Biology", volume = "128", pages = "11-45" } @techreport{Moscato_1989a, author = "P. Moscato", title = "On Genetic Crossover Operators for Relative Order Preservation", type = "C3P Report", number = "778", organisation = "Caltech Concurrent Computation Program", institution = "California Institute of Technology", address = "Pasadena, CA 91125", year = "1989" } @TechReport{EPCC-SS92-11, author = "R. Hofmann", title = "Parallel Evolutionary Trajectories", institution = "Edinburgh Parallel Computing Centre", year = "1992", type = "Research Report", number = "SS92-11" } @inproceedings{Carrizo_Tinetti_Moscato_92, author = "J. Carrizo and F.G. Tinetti and P. Moscato", title = "A Computational Ecology for the Quadratic Assignment Problem", editors = "SADIO", booktitle = "Proceedings of the 21st Meeting on Informatics and Operations Research", publisher = "SADIO", address = "Buenos Aires", pages = "", year = "1992" } @techreport{Moscato_Tinetti_92, author = "P. Moscato and F. Tinetti", title = "Blending Heuristics with a Population-Based Approach: A Memetic Algorithm for the Traveling Salesman Problem", organisation = "CeTAD", institution = "Universidad Nacional de La Plata", type = "Report", number = "92-12", address = "C.C. 75, 1900 La Plata, Argentina", year = "1992" } @inproceedings{Duran_Coll_Moscato_95, author = "G. Dur\'an and P.E. Coll and P. Moscato", title = "A discussion on some design principles for efficient crossover operators for graph coloring problems", editors = "SOBRAPO", booktitle = "XXVII Simposio Brasileiro de Pesquisa Operacional", publisher = "Sociedade Brasileira de Pesquisa Operacional", address = "Rio de Janeiro", pages = "", year = "1995" } @incollection{Laguna_Moscato_96, author = "M. Laguna and P. Moscato", title = "Capitulo 3: Algoritmos Geneticos", editor = "B.A. Diaz", booktitle = "Las Nuevas T\'ecnicas Heur\'{\i}sticas y las Redes Neuronales", publisher = "Ed. Paraninfo", address = "Madrid", year = "1996", ISBN = "84-283-2269-4", pages = "67--103" } @Incollection{BurNewWea96, author = "E.K. Burke and J.P. Newall and R.F. Weare", title = "A Memetic Algorithm for University Exam Timetabling", booktitle = "The Practice and Theory of Automated Timetabling", year = "1996", pages = "241--250", series = "Lecture Notes in Computer Science", volume = "1153", editor = "E.K. Burke and P. Ross", publisher = "Springer-Verlag" } @Incollection{PaeCumNorLuch96, author = "B. Paechter and A. Cumming and M.G. Norman and H. Luchian", title = "Extensions to a {M}emetic Timetabling System", booktitle = "The Practice and Theory of Automated Timetabling", year = "1996", pages = "251--265", series = "Lecture Notes in Computer Science", volume = "1153", editor = "E.K. Burke and P. Ross", publisher = "Springer Verlag" } @Incollection{PaeRanCum98, author = "B. Paechter and R.C. Rankin and A. Cumming", title = "Improving a Lecture Timetabling System for University Wide Use", booktitle = "The Practice and Theory of Automated Timetabling II", year = "1998", pages = "156--165", series = "Lecture Notes in Computer Science", volume = "1408", editor = "E.K. Burke and M. Carter", publisher = "Springer Verlag" } @Incollection{Rankin96, author = "R.C. Rankin", title = "Automatic Timetabling in Practice", booktitle = "The Practice and Theory of Automated Timetabling", year = "1996", pages = "266--279", series = "Lecture Notes in Computer Science", volume = "1153", editor = "E.K. Burke and P. Ross", publisher = "Springer Verlag" } @article{BurJackKingWea97, title = "Automated Timetabling: The State of the Art", author = "E.K. Burke and K.S. Jackson and J.H. Kingston and R.F. Weare", journal = "The Computer Journal", volume = "40", number = "9", year = "1997", pages = "565--571" } @article{BurNewWea98, title = "Initialisation Strategies and Diversity in Evolutionary Timetabling", author = "E.K. Burke and J.P. Newall and R.F. Weare", journal = "Evolutionary Computation", volume = "6", number = "1", pages = "81--103", year ="1998" } @article{Burke_Newall_99, title = "A Multi-Stage Evolutionary Algorithm for the Timetable Problem", author = "E.K. Burke and J.P. Newall", journal = "IEEE Transactions on Evolutionary Computation", volume = "3", number = "1", year = "1999", note = "to appear" } @article{Burke_Smith_99b, title = "Hybrid Evolutionary Techniques for the Maintenance Scheduling Problem", author = "E.K. Burke and A.J.Smith", journal = "IEEE Power Engineering Society Transactions", volume = "", number = "", pages = "", year = "1999", note = "to appear" } @InProceedings{Burke_Smith_1997, author = "E.K. Burke and A.J. Smith", title = "A Memetic Algorithm for the Maintenance Scheduling Problem", booktitle = "Proceedings of the ICONIP/ANZIIS/ANNES '97 Conference", address="Dunedin, New Zealand", pages = "469--472", year ="1997", publisher = "Springer-Verlag" } @InProceedings{Burke_Newall_1997, author = "E.K. Burke and J.P. Newall", title = "A Phased Evolutionary Approach for the Timetable Problem: An Initial Study", booktitle = "Proceedings of the ICONIP/ANZIIS/ANNES '97 Conference", address ="Dunedin, New Zealand", pages = "1038--1041", year ="1997", publisher = "Springer-Verlag" } @InProceedings{burke1995, author = "E. K. Burke and D. G. Elliman and R. F. Weare", title = "A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems", booktitle = "Proceedings of the Sixth International Conference on Genetic Algorithms", pages = "605--610", year = "1995", publisher = "Morgan Kaufmann, San Francisco, CA", institution = "Department of Computer Science, University of Nottingham, UK", url = "ftp://ftp.cs.nott.ac.uk/ttp/Papers/ICGA95.ps", annote = "university room examination heuristic artificial intelligence" } @InProceedings{Burke_Smith_99, author = "E.K. Burke and A.J. Smith", title = "A Memetic Algorithm to Schedule Grid Maintenance", booktitle = "Proceedings of the International Conference on Computational Intelligence for Modelling Control and Automation, Vienna: Evolutionary Computation and Fuzzy Logic for Intelligent Control, Knowledge Acquisition and Information Retrieval", pages = "122--127", year ="1999", publisher = "IOS Press 1999" } @InProceedings{DeCausmaecker_VandenBerghe_Burke_99, author = "de Causmaecker, P. and van den Berghe, G. and Burke. E.K.", title = "Using Tabu Search as a Local Heuristic in a Memetic Algorithm for the Nurse Rostering Problem", booktitle = "Proceedings of the Thirteenth Conference on Quantitative Methods for Decision Making", address = "Brussels, Belgium", pages = "abstract only, poster presentation", year ="1999", publisher = "" } @InProceedings{Ozcan_Mohan_98, author = "E. Ozcan and C.K. Mohan", title = "Steady State Memetic Algorithm for Partial Shape Matching", booktitle = "Evolutionary Programming VII", editor = "V.W. Porto and N. Saravanan and D. Waagen", pages = "527--236", series = "Lecture Notes in Computer Science", year = "1998", publisher = "Springer, Berlin", volume = "1447" } @InProceedings{icga97*458, author = "Christine L. Valenzuela and L. P. Williams", title = "Improving Heuristic Algorithms for the {Travelling Salesman Problem} by Using a Genetic Algorithm to Perturb the Cities", pages = "458--464", ISBN = "1-55860-487-1", editor = "Thomas B{\"a}ck", booktitle = "Proceedings of the 7th International Conference on Genetic Algorithms", publisher = "Morgan Kaufmann", address = "San Francisco", year = "1997" } @InProceedings{rana.howe-1996:compaheuri:inbook:174, author = "Soraya Rana and Adele E. Howe and L. Darrell Whitley and Keith Mathias", title = "Comparing Heuristic, Evolutionary and Local Search Approaches to Scheduling", editor = "B. Drabble", booktitle = "Proceedings of the 3rd International Conference on Artificial Intelligence Planning Systems (AIPS-96)", year = "1996", publisher = "AAAI Press", pages = "174--181" } @InCollection{ling1992, author = "S. E. Ling", title = "Integrating Genetic Algorithms with a Prolog Assignment Program as a Hybrid Solution for a Polytechnic Timetable Problem", booktitle = "Parallel Problem Solving from Nature II", pages = "321--329", publisher = "Elsevier Science Publisher B. V.", year = "1992" } @InProceedings{icga95*122} author = "James Bowen and Gerry Dozier", title = "Solving Constraint Satisfaction Problems Using a Genetic/Systematic Search Hybrid That Realizes When to Quit", pages = "122--129", ISBN = "1-55860-370-0", editor = "Larry J. Eshelman", booktitle = "Proceedings of the 6th International Conference on Genetic Algorithms", publisher = "Morgan {K}aufmann Publishers", address = "San Francisco", year = "1995" } @InProceedings{icga95*174, author = "James M. Varanelli and James P. Cohoon", title = "Population-Oriented Simulated Annealing: {A} Genetic/Thermodynamic Hybrid Approach to Optimization", pages = "174--183", ISBN = "1-55860-370-0", editor = "Larry J. Eshelman", booktitle = "Proceedings of the 6th International Conference on Genetic Algorithms", publisher = "Morgan Kaufmann Publishers", address = "San Francisco", year = "1995" } @article{Ferreira_Zerovnik_93, author = "A.G. Ferreira and J. Zerovnik", title = "Bounding the probability of success of stochastic methods for global optimization", journal = "Computers \& Mathematics with Applications", pages ="1-8", year = "1993" } @article{Shonkwiler_VanVleck_94, title = "Parallel speed-up of Monte Carlo Methods for Global Optimization", author = "R. Shonkwiler and E. Van Vleck", journal = "Journal of Complexity", volume = "10", pages ="64-95", year = "1994" } @article{Verhoeven_Aarts_95, title = "Parallel Local Search", author = "M.G.A. Verhoeven and E.H.L. Aarts", journal = "Journal of Heuristics", volume = "1", pages = "43-65", year = "1995" } @Article{Pirlot_96, title = "General local search methods", author = "M. Pirlot", journal = "European Journal of Operational Research", volume = "92", number = "3", pages = "493--511", year = "1996", publisher = "Elsevier Science BV, Amsterdam" } @mastersthesis{Hofmann_thesis_93, author = "Reimar Hofmann", title = "Examinations on the Algebra of Genetic Algorithms", school = "Technische Universit{\"a}t M{\"u}nchen, Institut f{\"u} Informatik", year = "1993" } %% Peter Merz's publications %% First version, September 14, 1998 %% Updated, September, 2000. @mastersthesis{merz96, author = "Peter Merz", title = "Genetische Algorithmen f{\"u}r kombinatorische Optimierungsprobleme", school = "University of Siegen, Germany", year = "1996" } @InProceedings{fspm96:icec, author = "B. Freisleben and P. Merz", title = "{A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems}", booktitle = "Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan", publisher = "{IEEE Press}", year = "1996", pages = "616--621" } @InProceedings{fspm96:ppsn, author = "B. Freisleben and P. Merz", title = "{New Genetic Local Search Operators for the Traveling Salesman Problem}", booktitle = "Parallel Problem Solving from Nature IV", editor = "H.-M. Voigt and W. Ebeling and I. Rechenberg and H.-P. Schwefel", series = "Lecture Notes in Computer Science", volume = 1141, publisher = "Springer", pages = "890--900", year = "1996" } @InProceedings{pmfs97:icec, author = "P. Merz and B. Freisleben", title = "{Genetic Local Search for the TSP: New Results}", booktitle = "Proceedings of the 1997 IEEE International Conference on Evolutionary Computation", publisher = "{IEEE Press}", pages = "159--164", year = "1997" } @InProceedings{pmfs97:icga, author = "P. Merz and B. Freisleben", title = "{A Genetic Local Search Approach to the Quadratic Assignment Problem}", booktitle = "Proceedings of the Seventh International Conference on Genetic Algorithms", editor = "T. B{\"a}ck", publisher = "Morgan Kaufmann", pages = "465--472", year = "1997", address = {San Mateo, CA} } @InProceedings{Merz_Freisleben_BQP_99, title = "Genetic Algorithms for Binary Quadratic Programming", author = "P. Merz and B. Freisleben", booktitle = "Proceedings of the 1999 International Genetic and Evolutionary Compuation Conference", editor = "", publisher = "Morgan Kauffman", pages = "417--424", year = "1999" } @InProceedings{pmfs98:icec, author = "P. Merz and B. Freisleben", title = "{On the Effectiveness of Evolutionary Search in High--Dimensional $NK$-Landscapes}", booktitle = "Proceedings of the 1998 IEEE International Conference on Evolutionary Computation", publisher = "{IEEE Press}", pages = "741--745", year = "1998" } @InProceedings{pmfs98:ppsn, author = "P. Merz and B. Freisleben", title = "{Memetic Algorithms and the Fitness Landscape of the Graph Bi-partitioning Problem}", booktitle = "Parallel Problem Solving from Nature V", editor = "A.E. Eiben and T. Back and M. Schoenauer and H.-P. Schwefel", series = "Lecture Notes in Computer Science", volume = "1498", publisher = "Springer-Verlag", pages = "765--774", year = "1998" } @InProceedings{iceo96, author = "H. Bersini and M. Dorigo and S. Langerman and G. Seront and L. Gambardella", title = "{Results of the First International Contest on Evolutionary Optimisation (1st ICEO)}", booktitle = "Proceedings of the 1996 IEEE International Conference on Evolutionary Computation", address = "{Nagoya, Japan}", year = "1996", pages = "611--615" } @InProceedings{Moscato92, title = "{A Memetic Approach for the Traveling Salesman Problem Implementation of a Computational Ecology for Combinatorial Optimization on Message-Passing Systems}", author = "P. Moscato and M. G. Norman", editor = "M. Valero and E. Onate and M. Jane and J. L. Larriba and B. Suarez", booktitle = "Parallel Computing and Transputer Applications", publisher = "IOS Press", address = "Amsterdam", pages = "177--186", year = "1992" } @TechReport{Moscato89a, title = "A Competitive and Cooperative Approach to Complex Combinatorial Search", author = "M.G. Norman and P. Moscato", number = "Caltech Concurrent Computation Program, Report. 790", institution = "California Institute of Technology", address = "Pasadena, California, USA", note = "expanded version published at the Proceedings of the 20th Informatics and Operations Research Meeting, Buenos Aires (20th JAIIO), Aug. 1991, pp. 3.15--3.29", year = "1989" } @TechReport{Moscato89, title = "{On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms}", author = "P. Moscato", number = "Caltech Concurrent Computation Program, Report. 826", institution = "California Institute of Technology", address = "Pasadena, California, USA", year = "1989" } % ``Go with the winners'' algorithms @InProceedings{Aldous_Vazirani_94, author ="D. Aldous and U. Vazirani", title ="{``Go with the winners'' algorithms}", booktitle ="Proceedings of the 35th Annual Symposium on Foundations of Computer Science", year ="1994", publisher ="IEEE", address = "Los Alamitos, CA", pages = "492--501" } @InProceedings{Peinado_Lengauer_97b, author ="M. Peinado and T. Lengauer", title ="{Parallel ``go with the winners algorithms'' in the LogP Model}", booktitle ="Proceedings of the 11th International Parallel Processing Symposium", year ="1997", editor ="IEEE Computer Society Press", publisher ="Los Alamitos, California", pages = "656--664" } @InProceedings{Muehlenbein89genetic, author ="H. M{\"u}hlenbein", title ="{Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization}", booktitle ="Proceedings of the Third International Conference on Genetic Algorithms", year ="1989", editor ="Schaffer", publisher ="Morgan Kaufmann", keywords ="genetic algorithms", ref ="genetic", pages = "416--421" } @Article{Muehlenbein88combi, author ="H. M{\"u}hlenbein and M. Gorges-Schleuter and O. Kr{\"a}mer", title ="{Evolution Algorithms in Combinatorial Optimization}", journal ="Parallel Computing", year ="1988", ref ="combi", volume ="7", pages ="65--88" } @InProceedings{Muhlenbein91a:ga, author ="H. M{\"u}hlenbein", title ="{Evolution in Time and Space -- The Parallel Genetic Algorithm}", booktitle ="Foundations of Genetic Algorithms", pages ="316--337", editor ="Gregory J.E. Rawlins", publisher ="Morgan Kaufmann Publishers", year ="1991" } @InCollection{Mu91, author = "H. M{\"u}hlenbein", title = "{Parallel Genetic Algorithms in Combinatorial Optimization}", booktitle = "Computer Science and Operations Research", editor = "O. Balci, R. Sharda and S. Zenios", year = "1992", publisher = "Pergamon Press, New York", pages = "441--456" } @InProceedings{GorgesSchleuter91, author = "M. Gorges-Schleuter", title = "{Explicit Parallelism of Genetic Algorithms through Population Structures}", booktitle = "Parallel Problem Solving from Nature", editor = {H.-P. Schwefel and R. M\"anner}, year = "1991", publisher = "Springer-Verlag", pages = "150--159" } @InProceedings{GorgesSchleuter89, author = "M. Gorges-Schleuter", title = "{ASPARAGOS}: An Asynchronous Parallel Genetic Optimization Strategy", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", editor = "J. David Schaffer", pages = "422--427", publisher = "Morgan Kaufmann Publishers", year = "1989" } @InProceedings{GorgesSchleuter97, author = "M. Gorges-Schleuter", title = "{Asparagos96 and the Traveling Salesman Problem}", booktitle = "Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, Indianapolis, USA", editor = "T. Baeck and Z. Michalewicz and X. Yao ", publisher = "{IEEE Press}", pages = "171--174", year = "1997" } @InProceedings{Jog89, key ="ICGA", booktitle ="Proceedings of the Third International Conference on Genetic Algorithms", year ="1989", publisher ="Morgan Kaufman", author ="P. Jog and J.Y. Suh and D. Van Gucht", title ="{The Effects of Population Size, Heuristic Crossover and Local Improvement on a Genetic Algorithm for the Travelling Salesman Problem}", pages ="110--115" } @InProceedings{Liepins87, editor = "Grefenstette, J.J.", booktitle = "Proceedings of the Second International Conference on Genetic Algorithms and their Applications", address = "Cambridge, MA", month = jul, year = "1987", publisher = "Lawrence Erlbaum Associates", author = "G. E. Liepins and M. R. Hilliard", title = "{Greedy Genetics}", pages = "90--99" } @InProceedings{Suh87, editor = "Grefenstette, J.J.", booktitle = "Proceedings of the Second International Conference on Genetic Algorithms and their Applications", address = "Cambridge, MA", month = jul, year = "1987", publisher = "Lawrence Erlbaum Associates", author = "J. Y. Suh and Dirk Van Gucht", title = "{Incorporating Heuristic Information into Genetic Search}", pages = "100--107" } @InProceedings{Eshelman91, booktitle = "Proceedings of the 4th International Conference on Genetic Algorithms", year = "1991", publisher = "Morgan Kaufmann", author = "L. J. Eshelman and J. D. Schaffer", title = "{Preventing Premature Convergence in Genetic Algorithms by Preventing Incest}", pages = "115--122" } @InProceedings{Manderick91, key = "ICGA", booktitle = "Proceedings of the 4th International Conference on Genetic Algorithms", year = "1991", publisher = "Morgan Kaufmann", author = "B. Manderick and M. de Weger and P. Spiessens", title = "{The Genetic Algorithm and the Structure of the Fitness Landscape}", pages = "143--150" } @InProceedings{Braun91, author = "H. Braun", title = "{On Solving Traveling Salesman Problems by Genetic Algorithms}", editor = "H.-P. Schwefel and R. M{\"{a}}nner", volume = "496", series = "Lecture Notes in Computer Science", pages = "129--133", booktitle = "Parallel Problem Solving from Nature - Proceedings of 1st Workshop, PPSN I", year = "1991", publisher = "Springer", address = "Berlin, Germany" } @InProceedings{Dzubera94, author = "J. Dzubera and D. Whitley", title = "{Advanced Correlation Analysis of Operators for the Traveling Salesman Problem}", editor = "H.-P. Schwefel and R. M{\"{a}}nner", volume = "866", series = "Lecture Notes in Computer Science", pages = "68--77", booktitle = "Parallel Problem Solving from Nature - Proceedings of the Third Workshop, PPSN III", year = "1994", publisher = "Springer-Verlag, Berlin, Germany", address = "Dortmund, Germany" } @InProceedings{Ulder91, author = "N. L. J. Ulder and E. H. L. Aarts and H. -J. Bandelt and P. J. M. van Laarhoven and E. Pesch", title = "{Genetic Local Search Algorithms for the Traveling Salesman Problem}", editor = "H. -P. Schwefel and R. M{\"{a}}nner", volume = "496", series = "Lecture Notes in Computer Science", pages = "109--116", booktitle = "Parallel Problem Solving from Nature - Proceedings of 1st Workshop, PPSN I", year = "1991", publisher = "Springer", address = "Berlin, Germany" } @InProceedings{Mathias92, author = "K. Mathias and D. Whitley", title = "{Genetic operators, the Fitness Landscape and the Traveling Salesman Problem}", editor = "R. M{\"{a}}nner and B. Manderick", pages = "219--228", booktitle = "Parallel Problem Solving from Nature - Proceedings of 2nd Workshop, PPSN II", year = "1992", publisher = "Elsevier Science Publishers" } @InProceedings{Grefenstette87, author = "J. J. Grefenstette", title = "{Incorporating Problem Specific Knowledge into Genetic Algorithms}", editor = "L. Davis", pages = "42--60", booktitle = "Genetic Algorithms and Simulated Annealing", year = "1987", publisher = "Morgan Kaufmann Publishers", series = "Research Notes in Artificial Intelligence" } @PhDthesis{GorgesSchleuter91:thesis, author = "M. Gorges-Schleuter", title = "Genetic Algorithms and Population Structures - A Massively Parallel Algorithm", school = "University of Dortmund, Germany", year = "1991" } @InProceedings{Yamada96, author = "T. Yamada and R. Nakano", title = "{Scheduling by Genetic Local Search with Multi-Step Crossover}", booktitle = "Proceedings of the 4th Conference on Parallel Problem Solving from Nature - PPSN IV", editor = "Hans-Michael Voigt and Werner Ebeling and Ingo Rechenberg and Hans-Paul Schwefel", series = "Lecture Notes in Computer Science", volume = 1141, publisher = "Springer", pages = "960--969", year = "1996" } @InCollection{Eshelman91a, editor = "G. J. E. Rawlings", booktitle = "Foundations of Genetic Algorithms", publisher = "Morgan Kaufmann", year = "1991", author = "L.J. Eshelman", title = "{The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination}", pages = "265--283" } @InProceedings{Ronald95:icec, author = "Simon Ronald", title = "{Finding Multiple Solutions with an Evolutionary Algorithm}", booktitle = "Proceedings of the 1995 IEEE International Conference on Evolutionary Computation", publisher = "{IEEE Press}", pages = "641--646", year = "1995" } @InProceedings{Ronald97:icec, author = "Simon Ronald", title = "{Distance Functions for Order--Based Encodings}", booktitle = "Proceedings of the 1997 IEEE International Conference on Evolutionary Computation", publisher = "{IEEE Press}", pages = "49--54", year = "1997" } @InCollection{Eshelman97:foga, title = "{Convergence Controlled Variation}", author = "Larry Eshelman and K. Mathias and J. D. Schaffer", booktitle = "Foundations of Genetic Algorithms 4", year = "1997", editor = "Richard K. Belew and Michael D. Vose", publisher = "Morgan Kaufman", pages = "203--224" } @phdthesis{Niehaus_96, author = "William J. Niehaus", title = "Design of Maximum-Cardinality and Maximum-Weight Clique Heuristics with Applications", organisation = "School of Computer Science", school = "Carnegie Mellon University", type = "Ph.D. Thesis, CMU-CS-96-127", address = "Pittsburgh, PA, USA", year = "1996", note = "Niehaus and Balas presented a talk at the INFORMS conference in 1996 entitled: Genetic Algorithms for maximum clique. The abstract of the talk is available at: http://www.informs.org/Conf/WA96/TALKS/MC29.3.html" } @InProceedings{Radcliffe_formal_memetics, author = "N.J. Radcliffe and P.D. Surry", title = "{Formal Memetic Algorithms}", booktitle = "Evolutionary Computing: AISB Workshop", editor = "T. Fogarty", pages = "1--16", series = "Lecture Notes in Computer Science", year = "1994", publisher = "Springer-Verlag, Berlin", volume = "865", abstract = "A formal, representation-independent form of a memetic algorithm---a genetic algorithm incorporating local search---is introduced. A generalised form of $N$-point crossover is defined together with representation-independent patching and hill-climbing operators. The resulting formal algorithm is then constructed and tested empirically on the travelling sales-rep problem. Whereas the genetic algorithms tested were unable to make good progress on the problems studied, the memetic algorithms performed very well." } @InProceedings{Radcliffe_performance_prediction, author = "N.J. Radcliffe and P.D. Surry", title = "{Fitness Variance of Formae and Performance Prediction}", booktitle = "Proceedings of the Third Workshop on Foundations of Genetic Algorithms", pages = "51--72", editor = "L.D. Whitley and M.D. Vose", publisher = "Morgan Kaufmann", address = "San Francisco", year = "1994", abstract = " Representation is widely recognised as a key determinant of performance in evolutionary computation. The development of families of representation-independent operators allows the formulation of formal representation-independent evolutionary algorithms. These formal algorithms can be instantiated for particular search problems by selecting a suitable representation. The performance of different representations, in the context of any given formal representation-independent algorithm, can then be measured. Simple analyses suggest that fitness variance of formae (generalised schemata) for the chosen representation might act as a performance predictor for evolutionary algorithms. This hypothesis is tested and supported through studies of four different representations for the travelling sales-rep problem (TSP) in the context of both formal representation-independent genetic algorithms and corresponding memetic algorithms." } @book{Gen_Cheng_book, title = "Genetic Algorithms and Engineering Design", author = "M. Gen and R. Cheng", series = "Wiley Series in Engineering Design and Automation", publisher = "John Wiley \& Sons (Sd)", year = "1997", ISBN = "0471127418" } @article{Cheng_Gen_97, title = "Parallel machine scheduling problems using memetic algorithms", author = "R.W. Cheng and M. Gen", journal = "Computers \& Industrial Engineering", volume = "33", number = "3--4", pages = "761--764", year = "1997", document_type = "Article", language = "English", cited_references = "5", abstract = "In this paper, we investigate how to apply the hybrid genetic algorithms (the memetic algorithms) to solve the parallel machine scheduling problem. There are two essential issues to be dealt with for all kinds of parallel machine scheduling problems: job partition among machines and job sequence within each machine. The basic idea of the proposed method is that (a) use the genetic algorithms to evolve the job partition and then (b) apply a local optimizer to adjust the job permutation to push each chromosome climb to his local optima. Preliminary computational experiments demonstrate that the hybrid genetic algorithm outperforms the genetic algorithms and the conventional heuristics.", author_keywords = "parallel machine scheduling, hybrid genetic algorithms, memetic algorithms", addresses = " Cheng RW, Ashikaga Inst Technol, Dept Ind \& Syst Engn, Ashikaga 326, Japan. Ashikaga Inst Technol, Dept Ind \& Syst Engn, Ashikaga 326, Japan.", publisher = " PERGAMON-ELSEVIER SCIENCE LTD, OXFORD", ids_number = " YM357", issn = " 0360-8352" } @InProceedings{Mendes_et_al_99, author = "A.S. Mendes and F.M. Muller and P.M. {Fran\c{c}a} and P. Moscato", title = "Comparing Meta-Heuristic Approaches for Parallel Machine Scheduling Problems with Sequence-dependent setup times", booktitle = "Proceedings of the 15th International Conference on CAD/CAM Robotics \& Factories of the Future", address = "Aguas de Lindoia, Brazil", volume = "1", pages = "1-6", year ="1999", publisher = "", abstract = "The aim of this paper is to compare the performance of two meta-heuristic methods proposed for solving the identical parallel machine scheduling problem with sequence dependent setup times. The first algorithm is a tabu search based heuristic and the second a memetic approach, which combines population-based methods with local search procedures. As benchmarks for small-sized instances we use optimal solutions provided by a dichotomous search. For larger instances the comparisons rely on the best known solutions." } @InProceedings{Franca_Mendes_Moscato_99, author = "P.M. {Fran\c{c}a} and A.S. Mendes and P. Moscato", title = "Memetic algorithms to minimize tardiness on a single machine with sequence-dependent setup times", booktitle = "Proceedings of the 5th International Conference of the Decision Sciences Institute, Athens, Greece", pages = "1708-1710", year ="1999", publisher = "" } % set partitioning @InCollection{Levine_96, title = "A parallel genetic algorithm for the set partitioning problem", author = "D. Levine", booktitle = "Meta-Heuristics: Theory \& Applications", editor = "I.H. Osman and J.P. Kelly", pages = "23--35", publisher = "Kluwer Academic Publishers", year = "1996" } % set covering @article{Beasley_Chu_96, title ="A genetic algorithm for the set covering problem", author = "J. Beasley and P.C. Chu", journal = "European Journal of Operational Research", volume = "94", number ="2", pages = "393--404", year = "1996", abstract = "In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling. A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems. We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions." } % multidimensional knapsack @article{Beasley_Chu_98, title = "A genetic algorithm for the multidimensional knapsack problem", author = "J. Beasley and P.C. Chu", journal = "Journal of Heuristics", volume = "4", pages = "63--86", year = "1998", abstract = "In this paper we present a heuristic based upon genetic algorithms for the multidimensional knapsack problem. A heuristic operator which utilises problem-specific knowledge is incorporated into the standard genetic algorithm approach. Computational results show that the genetic algorithm heuristic is capable of obtaining high-quality solutions for problems of various characteristics, whilst requiring only a modest amount of computational effort. Computational results also show that the genetic algorithm heuristic gives superior quality solutions to a number of other heuristics." } % generalized assignment @article{Beasley_Chu_97, title = "A genetic algorithm for the generalised assignment problem", author = "P.C. Chu and J. Beasley", journal = "Computers \& Operations Research", volume = "24", pages = "17--23", year = "1997", abstract = "In this paper we present a genetic algorithm (GA)-based heuristic for solving the generalised assignment problem. The generalised assignment problem is the problem of finding the minimum cost assignment of $n$ jobs to $m$ agents such that each job is assigned to exactly one agent, subject to an agent's capacity. In addition to the standard GA procedures, our GA heuristic incorporates a problem-specific coding of a solution structure, a fitness-unfitness pair evaluation function and a local improvement procedure. The performance of our algorithm is evaluated on 84 standard test problems of various sizes ranging from 75 to 4,000 decision variables. Computational results show that the genetic algorithm heuristic is able to find optimal and near optimal solutions that are on average less than 0.01% from optimality. The performance of our heuristic also compares favourably to all other existing heuristic algorithms in terms of solution quality." } % Scheduling @article{Costa_NHL, author = "D. Costa", title = "An evolutionary tabu search algorithm and the {NHL} scheduling Problem", journal = "INFOR", volume = "33", number= "3", year = "1995", pages = "161--178" } % Graph Coloring References @InProceedings{Hogg_Williams_93, author = "Tad Hogg and Colin P. Williams", title = "Solving the Really Hard Problems with Cooperative Search", booktitle = "Proc. of AAAI93", pages = "231--236", publisher = "AAAI Press", address = "Menlo Park, CA", year = "1993", abstract = "We present and experimentally evaluate the hypothesis that cooperative parallel search is well suited for hard graph coloring problems near a previously identified transition between under- and overconstrained instances. We find that simple cooperative methods can often solve such problems faster than the same number of independent agents. " } @article{Costa_coloring, author = "D. Costa and N. Dubuis and A. Hertz", title = "Embedding of a sequential procedure within an evolutionary algorithm for coloring problems in graphs", journal = "Journal of Heuristics", volume = "1", number= "1", year = "1995", pages = "105-128" } @article{Fleurent_Ferland_96, title = "Genetic and hybrid algorithms for graph coloring", author = "C. Fleurent and J.A. Ferland", journal = "Annals of Operations Research", volume = "63", pages = "437--461", year = "1997", abstract ="Some genetic algorithms are considered for the graph coloring problem. As is the case for other combinatorial optimization problems, pure genetic algorithms are outperformed by neighborhood search heuristic procedures such as tabu search. Nevertheless, we examine the performance of several hybrid schemes that can obtain solutions of excellent quality. For some graphs, we illustrate that genetic operators can fulfill long-term strategic functions for a tabu search implementation that is chiefly founded on short-term memory strategies." } @InProceedings{Dorne_Hao_98, AUTHOR = {R. Dorne and J.K. Hao}, TITLE = {A New Genetic Local Search Algorithm for Graph Coloring}, editor = {Eiben, A.E. and B\"ack, Th. and Schoenauer, M. and Schwefel, H.-P.}, booktitle = {Parallel Problem Solving From Nature V}, year = {1998}, series = {Lecture Notes in Computer Science}, volume = {1498}, publisher = {Springer-Verlag}, address = {Berlin}, PAGES = {745-754}, } @ARTICLE{galinierhao98, AUTHOR = {P. Galinier and J.K. Hao}, TITLE = {Hybrid Evolutionary Algorithms for Graph Coloring}, JOURNAL = {Submitted to the Journal of Combinatorial Optimization}, YEAR = {1998} } @article{Bui_Moon_96, title = "Genetic algorithm and graph partitioning", author = "T.N. Bui and B.R. Moon", journal = "IEEE Transactions on Computers", volume = "45", number = "7", pages = "841--855", year = "1996", abstract = "Hybrid genetic algorithms (GAs) for the graph partitioning problem are described. The algorithms include a fast local improvement heuristic. One of the novel features of these algorithms is the schema preprocessing phase that improves GAs' space searching capability, which in turn improves the performance of GAs. Experimental tests on graph problems with published solutions showed that the new genetic algorithms performed comparable to or better than the multistart Kernighan-Lin algorithm and the simulated annealing algorithm. Analyses of some special classes of graphs are also provided showing the usefulness of schema preprocessing and supporting the experimental results." } @article{Bui_Moon_98, title ="{GRCA}: A hybrid genetic algorithm for circuit ratio-cut partitioning", author ="T.N. Bui and B.R. Moon", journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems", volume ="17", number = "3", pages ="193--204", year = "1998", abstract = "A genetic algorithm for partitioning a hypergraph into two disjoint graphs of minimum ratio cut is presented. As the Fiduccia-Mattheyses graph partitioning heuristic turns out to be not effective when used in the context of a hybrid genetic algorithm, we propose a modification of the Fiduccia-Mattheyses heuristic for more effective and faster space search by introducing a number of novel features. We also provide a preprocessing heuristic for genetic encoding designed solely for hypergraphs which helps genetic algorithms exploit clustering information of input graphs. Supporting combinatorial arguments for the new preprocessing heuristic are also provided. Experimental results on industrial benchmarks circuits showed visible improvement over recently published algorithms with a lower growth rate of running time." } % Bin Packing @article{Reeves_96, title = "Hybrid genetic algorithms for bin-packing and related problems", author = "C. Reeves", journal = "Annals of Operations Research", volume = "63", pages = "371--396", year = "1996", abstract = "The genetic algorithm (GA) paradigm has attracted considerable attention as a promising heuristic approach for solving optimization problems. Much of the development has related to problems of optimizing functions of continuous variables, but recently there have been several applications to problems of a combinatorial nature. What is often found is that GAs have fairly poor performance for combinatorial problems if implemented in a naive way, and most reported work has involved somewhat ad hoc adjustments to the basic method. In this paper, we will describe a general approach which promises good performance for a fairly extensive class of problems by hybridizing the GA with existing simple heuristics. The procedure will be illustrated mainly in relation to the problem of bin-packing, but it could be extended to other problems such as graph partitioning, parallel-machine scheduling and generalized assignment. The method is further extended by using problem size reduction hybrids. Some results of numerical experiments will be presented which attempt to identify those circumstances in which these heuristics will perform well relative to exact methods. Finally, we discuss some general issues involving hybridization: in particular, we raise the possibility of blending GAs with orthodox mathematical programming procedures." } % maximum independent set @article{Aggarwal_Orlin_Tai_97, title = "Optimized Crossover for the Independent Set Problem", author = "C.C. Aggarwal and J.B. Orlin and R.P. Tai", journal = "Operations Research", volume = "45", pages ="226--234", number = "2", year ="1997", abstract = "We propose a knowledge-based crossover mechanism for genetic algorithms that exploits the structure of the solution rather than its coding. More generally, we suggest broad guidelines for constructing the knowledge-based crossover mechanisms. This technique uses an optimized crossover mechanism, in which the one of the two children is constructed in such a way as to have the best objective function value from the feasible set of children, while the other is constructed so as to maintain the diversity of the search space. We implement our approach on a classical combinatorial problem, called the independent set problem, The resulting genetic algorithm dominates all other genetic algorithms for the problem and yields one of the best heuristics for the independent set problem in terms of robustness and time performance. The primary purpose of this paper is to demonstrate the power of knowledge based mechanisms in genetic algorithms." } @article{Hifi_97, title = "A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems", author = "M. Hifi", journal = "Journal of the Operational Research Society", volume = "48", number = "6", pages = "612--622", year = "1997", abstract = "In this paper we present a genetic algorithm-based heuristic especially for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization problems. We introduce several modifications to the basic genetic algorithm, by (i) using a crossover called two-fusion operator which creates two new different children and (ii) replacing the mutation operator by the heuristic-feasibility operator tailored specifically for the weighted independent set. The performance of our algorithm was evaluated on several randomly generated problem instances for the weighted independent set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results show that the proposed approach is able to produce high-quality solutions within reasonable computational times. This algorithm is easily parallelizable and this is one of its important features." } @article{Sakamoto_Liu_Shimamoto_97, title = "A genetic approach for maximum independent set problems", author = "A. Sakamoto and X.Z. Liu and T. Shimamoto", journal = "{IEICE} Transactions on Fundamentals of Electronics Communications and Computer Sciences", volume = "E80A", number = "3", pages = "551--556", year = "1997", abstract = "Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper we present a genetic algorithm for maximum independent set problem. We adopt a permutation encoding with a greedy de coding to solve the problem. The DIMACS benchmark graphs are used to test our algorithm. For most graphs solutions found by our algorithm are optimal, and there are also a few exceptions that solutions found by the algorithm are almost as large as maximum clique sizes. We also compare our algorithm with a hybrid genetic algorithm, called GMCA, and one of the best existing maximum clique algorithms, called CBH. The experimental mental results show that our algorithm outperformed two of the best approaches by GMCA and CBH in final solutions." } % (nonlinear) integer programming @article{Taguchi_Yokota_Gen_98, title = "Reliability optimal design problem with interval coefficients using Hybrid Genetic Algorithms", author = "T. Taguchi and T. Yokota and M. Gen", journal = "Computers \& Industrial Engineering", volume = "35", number ="1--2", pages = "373--376", year = "1998", abstract = "In this paper, we formulate an optimal design of system reliability problem as nonlinear integer programming (NIP) problem with interval coefficients! transform it into single objective NIP problem without interval coefficients, and solve it directly keeping the nonlinearity of the objective function based on Hybrid Genetic Algorithms (HGAs). Also, we demonstrate the efficiency of this method with Optimal Selection and Allocation problem of a System Reliability." } % chapters of the book New Ideas in optimization % 23 Feb. 1999 @book{NewMethods_99, title = "New Ideas in Optimization", author = "D. Corne and M. Dorigo and F. Glover", year = "1999", publisher = "McGraw-Hill" } @InCollection{Moscato_NewMethods_99, title = "Memetic Algorithms: A short introduction", author = "P. Moscato", booktitle = "New Ideas in Optimization", editor = "D. Corne and M. Dorigo and F. Glover", year = "1999", pages = "219--234", publisher = "McGraw-Hill" } @InCollection{Holstein_Moscato_NewMethods_99, title = "Memetic Algorithms using Guided Local Search: A case study", author = "D. Holstein and P. Moscato", booktitle = "New Ideas in Optimization", editor = "D. Corne and M. Dorigo and F. Glover", year = "1999", pages = "235--244", publisher = "McGraw-Hill" } @InCollection{Coll_Duran_Moscato_NewMethods_99, title = "On worst-case and comparative analysis as design principles for efficient recombination operators: A graph coloring case study", author = "P.E. Coll and G.A. Dur\'an and P. Moscato", booktitle = "New Ideas in Optimization", editor = "D. Corne and M. Dorigo and F. Glover", year = "1999", pages = "279--294", publisher = "McGraw-Hill" } @InCollection{Merz_Freisleben_NewMethods_99, title = "Fitness Landscapes and Memetic Algorithm Design", author = "P. Merz and B. Freisleben", booktitle = "New Ideas in Optimization", editor = "D. Corne and M. Dorigo and F. Glover", year = "1999", pages = "245--260", publisher = "McGraw-Hill" } @InCollection{Berretta_Moscato_NewMethods_99, title = "The Number Partitioning Problem: An open challenge for Evolutionary Computation~?", author = "R. Berretta and P. Moscato", booktitle = "New Ideas in Optimization", editor = "D. Corne and M. Dorigo and F. Glover", year = "1999", pages = "261--278", publisher = "McGraw-Hill" } @InProceedings{cacic98, author = "N. Krasnogor and P.A. Mocciola and D.A. Pelta and G. Ruiz and W.M. Russo", title = "A Runnable Functional Memetic Algorithm Framework", booktitle = "Proceedings of the Congreso Argentino de Ciencias de la Computacion, Vol. I", pages = "525--536", year = "1998", address = "Universidad Nacional del Comahue, Argentina" } % Evolution of Cooperation @article{Axelrod_Hamilton_81, title = "The Evolution of Cooperation", author = "R. Axelrod and W.D. Hamilton", journal = "Science", volume = "211", number = "4489", pages = "1390--1396", year = "1981" } @article{Hofstadter_83, title = "Computer Tournaments of the Prisoners-Dilemma Suggest How Cooperation Evolves", author = "D.R. Hofstadter", journal = "Scientific American", volume = "248", number = "5", pages = "16--23", year = "1983" } @article{Nowak_Sigmund_98, title = "Evolution of indirect reciprocity by image scoring", author = "M.A. Nowak and K. Sigmund", journal = "Nature", volume = "393", number = "6685", pages = "573--577", year = "1998" } @article{Nakamaru_Nogami_Iwasa_98, title = "Score-dependent fertility model for the evolution of cooperation in a lattice", author = "M. Nakamaru and H. Nogami and Y. Iwasa", journal = "Journal of Theoretical Biology", volume ="194", number ="1", pages = "101--124", year ="1998", Abstract = "The evolution of cooperation is studied in a lattice-structured population, in which each individual plays the iterated Prisoner's Dilemma game with its neighbors. The population includes Tit-for-Tat (TFT, a cooperative strategy) and All Defect (AD, a selfish strategy) distributed over the lattice points. An individual dies randomly, and the vacant site is filled immediately by a copy of one of the neighbors in which the probability of colonization success by a particular neighbor is proportional to its score accumulated in the game. This ``score-dependent fertility model'' (or fertility model) behaves very differently from score-dependent viability model (viability model) studied in a previous paper. The model on a one-dimensional lattice is analysed by invasion probability analysis, pair-edge method mean-held approximation, pair approximation, and computer simulation. Results are: (1) TFT players come to form tight clusters. When the probability of iteration w is large, initially rare TFT can invade and spread in a population, dominated by AD, unlike in the complete mixing model. The condition for the increase of TFT is accurately predicted by all the techniques except mean-field approximation; (2) fertility model is much more favorable for the spread of TFT than the corresponding viability model, because spiteful killing of neighbors is favored in the viability model but not in the fertility model; (3) eight lattice games on two-dimensional lattice with different assumptions are examined. Cooperation and defects can coexist stable in the models of deterministic state change but not in the models of stochastic state change." } @article{Nakamaru_Matsuda_Iwasa_98a, title = "The evolution of social interaction in lattice models", author ="M. Nakamaru and H. Matsuda and Y. Iwasa", journal = "Sociological Theory and Methods", volume ="12", number ="2", pages = "149--162", year ="1998", abstract = "The rationality of human behavior seems unable to explain the altruism and spite which gives the player a short-term cost. Recent study of evolutionary game theory succeed to explain the condition for these social interaction to appear, based on the dynamics of different behaviors in the population. The critical importance of the spatial structure as been revealed- if players interact locally, the society to evolve is very different from if they interact randomly over the whole population. In this article, we review the studies on the evolution of social interaction in lattice structured models (or cellular automata models). The analysis of lattice models have been restricted to direct computer simulations. Here we apply various mathematical analyses, including birth-and-death processes, pair-approximation, and the pair-edge method." } @article{Grim_97, title = "The undecidability of the spatialized prisoner's dilemma", author = "P. Grim", journal = "Theory and Decision", volume = "42", number = "1", pages = "53--80", year = "1997", abstract = "In the spatialized Prisoner's Dilemma, players compete against their immediate neighbors and adopt a neighbor's strategy should it prove locally superior. Fields of strategies evolve in the manner of cellular automata (Nowak and May, 1993; Mar and St. Denis, 1993a,b; Grim 1995, 1996). Often a question arises as to what the eventual outcome of an initial spatial configuration of strategies will be: Will a single strategy prove triumphant in the sense of progressively conquering more and more territory without opposition, or will an equilibrium of some small number of strategies emerge? Here it is shown, for finite configurations of Prisoner's Dilemma strategies embedded in a given infinite background, that such questions are formally undecidable: there is no algorithm or effective procedure which, given a specification of a finite configuration, will in all cases tell us whether that configuration will or will not result in progressive conquest by a single strategy when embedded in the given field. The proof introduces undecidability into decision theory in three steps: by (1) outlining a class of abstract machines with familiar undecidability results, by (2) modelling these machines within a particular family of cellular automata, carrying over undecidability results for these, and finally by (3) showing that spatial configurations of Prisoner's Dilemma strategies will take the form of such cellular automata." } % The following set of references have been cited in % % "Memetic Algorithms for molecular conformation and other % optimization problems", by P. Moscato, % appeared in the Newsletter No. 20, May-August, 1998, of the % International Union of Crystallography, % Newsletter of the Comission for Powder Diffraction. % % available from the Newsletter web site at % % http://www.dl.ac.uk/SRS/XRD/IUCR/Newsletters/no20summer1998/ @article{Moscato_93, author = "P. Moscato", title = "{An Introduction to Population Approaches for Optimization and Hierarchical Objective Functions: The Role of Tabu Search}", journal = "Annals of Operations Research", volume = "41", number= "1-4", year = "1993", pages = " 85-121", abstract = "Population approaches suitable for global combinatorial optimization are discussed in this paper. They are composed of a number of distinguishable individuals called ``agents'', each one using a particular optimization strategy. Periods of independent search follow phases on which the population is restarted from new configurations. Due to its intrinsic parallelism and the asynchronicity of the method, it is particularly suitable for parallel computers. Results on two test problems are presented in this paper. The individual search optimization strategies for each agent have been chosen having the basic characteristics of Tabu Search. This has been done in order to avoid mixing the hypothesized properties of these population approaches with those of more elaborate Tabu Search strategies, but remarking on its main characteristics. A set of four test problem ``landscapes'' is discussed and their use to improve and benchmark the results by using Tabu Search as the individual optimization strategy within a population heuristic is suggested and explored. The application of Tabu Search to new problem areas, like molecular biology, is also investigated." } @article{Glover_95, title="Scatter Search And Star-Paths - Beyond The Genetic Metaphor", author="F. Glover", journal="{OR} Spektrum", volume = "17", number = "(2-3)", pages = "125--137", year = "1995", Abstract = "Scatter search and genetic algorithms have originated from somewhat different traditions and perspectives, yet exhibit features that are strongly complementary. Links between the approaches have increased in recent years as variants of genetic algorithms have been introduced that embody themes in closer harmony with those of scatter search. Some researchers are now beginning to take advantage of these connections by identifying additional ways to incorporate elements of scatter search into genetic algorithm approaches. There remain aspects of the scatter approach that have not been exploited in conjunction with genetic algorithms, yet that provide ways to achieve goals that are basic to the genetic algorithm design. Part of the gap in implementing hybrids of these procedures may derive from relying too literally on the genetic metaphor, which in its narrower interpretation does not readily accommodate the strategic elements underlying scatter search. The theme of this paper is to show there are benefits to be gained by going beyond a perspective constrained too tightly by the connotations of the term ``genetic''. We show that the scatter search framework directly leads to processes for combining solutions that exhibit special properties for exploiting combinatorial optimization problems. In the setting of zero-one integer programming, we identify a mapping that gives new ways to create combined solutions, producing constructions called star-paths for exploring the zero-one solution space. Star-path trajectories have the special property of lying within regions assured to include optimal solutions. They also can be exploited in association with both cutting plane and extreme point solution approaches. These outcomes motivate a deeper look into current conceptions of appropriate ways to combine solutions, and disclose there are more powerful methods to derive information from these combinations than those traditionally applied." } @article{Huber_94, Title="Structural Optimization of Vapor-Pressure Correlations Using Simulated Annealing And Threshold Accepting - Application To R134A", Author ="M.L. Huber", Journal = "Computers \& Chemical Engineering", Volume = "18", Number = "(10)", Pages = "929--932", Year = "Oct. 1994", Abstract = "This paper reports the use of two methods, simulated annealing (SA) and threshold accepting (TA), to determine a set of optimal terms (the structure) of the vapor pressure correlation for the R134a. The SA algorithm with the Lundy and Mees annealing schedule, and the TA algorithm with the Aarts and VanLaarhoven schedule gave the best performance, based on minimal computational time for a given performance. SA and TA appear to be versatile, powerful and computationally simple methods for determining the structure of empirical correlations of thermophysical property data.", } @article{Glover_94, Title="Genetic Algorithms And Scatter Search - Unsuspected Potentials", Author = "F. Glover", Journal = "Statistics And Computing", Volume = "4", Number = "(2)", Pages = "131--140", Year = "1994", Abstract = "We provide a tutorial survey of connections between genetic algorithms and scatter search that have useful implications for developing new methods for optimization problems. The links between these approaches are rooted in principles underlying mathematical relaxations, which became inherited and extended by scatter search. Hybrid methods incorporating elements of genetic algorithms and scatter search are beginning to be explored in the literature, and we demonstrate that the opportunity exists to develop more advanced procedures that make fuller use of scatter search strategies and their recent extensions." } @article{Landree_97, Title="Multi-solution genetic algorithm approach to surface structure determination using direct methods", Author = "E. Landree and C. Collazo-Davila and L.D. Marks", Journal = "Acta Crystallographica Section B - Structural Science", Volume = "53", Pages = "916--922", Year = "1997", Abstract = "We show that it is possible to use a multi-solution genetic algorithm search method utilizing direct methods to solve surface structures from surface diffraction data. We suggest that the method is generally applicable and able to replace random searches of the solution space." } @article{Miller_96, Title="A genetic algorithm for the {\em ab initio} phasing of icosahedral viruses", Author = "S.T. Miller and J.M. Hogle and D.J. Filman", Journal = "Acta Crystallographica Section D - Biological Crystallography", Volume = "52", Pages = "235--251", Year ="1996", Abstract = "Genetic algorithms have been investigated as computational tools for the de novo phasing of low-resolution X-ray diffraction data from crystals of icosahedral viruses. Without advance knowledge of the shape of the virus and only approximate knowledge of its size, the virus can be modeled as the symmetry expansion of a short list of nearly tetrahedrally arranged lattice points which coarsely, but uniformly, sample the icosahedrally unique volume. The number of lattice points depends on an estimate of the non-redundant information content at the working resolution limit. This parameterization permits a simple matrix formulation of the model evaluation calculation, resulting in a highly efficient survey of the space of possible models. Initially, one bit per parameter is sufficient, since the assignment of ones and zeros to the lattice points yields a physically reasonable low-resolution image of the virus. The best candidate solutions identified by the survey are refined to relax the constraints imposed by the coarseness of the modeling, and then trials whose intensity-based statistics are comparatively good in all resolution ranges are chosen. This yields an acceptable starting point for symmetry-based direct phase extension about half the time. Improving efficiency by incorporating the selection criterion directly into the genetic algorithm's fitness function is discussed." } @article{Choi_98, Title="X-ray reflectivity analysis incorporated with genetic algorithm to analyze the Y- to X type transition in CdA LB film", Author ="J.W. Choi and K.S. Cho and H.W. Rhee and W.H. Lee and H.S. Lee", Journal = "Bulletin of the Korean Chemical Society", Volume = "19", Number ="5", Pages ="549--553", Year = "1998", Abstract = " The structure and layer distribution of cadmium arachidate Langmuir-Blodgett film were analyzed by the small angle X-ray reflectivity measurements using synchrotron radiation. Y- to X type transition was occurred during the 39th passage of deposition of cadmium arachidate. Based on the measurement of the consumed area of the monolayer, it was determined that about 27.5 layer was deposited. Using the synchrotron X-ray, the: reflectivity profile of cadmium arachidate LB Nm over the wide range of grazing angle was obtained. The X-ray reflectivity profile was analyzed using the recursion formula. By fitting the location and dispersion of the subsidiary maxima between the Bragg peaks of the measured reflectivity profile with that of the calculated reflectivity profile, the average thickness and the distribution of layer thickness were evaluated. The genetic algorithm was adopted to the fitting of reflectivity profile to evaluate the optimum value of the number distribution of layer. Based on the morphology measurement with an atomic force microscopy (AFM), the domain structure and mean roughness of LB films were obtained. The mean roughness value calculated based on the number of layer distribution obtained from the measurement by AFM is consistent with that obtained from X-ray reflectivity analysis.", } @article{Trinkunas_97, Title="Model for the excitation dynamics in the light-harvesting complex II from higher plants", Author = "G. Trinkunas and J.P. Connelly and M.G. Muller and L. Valkunas and A. R. Holzwarth", Journal = "Journal of Physical Chemistry B", Volume = "101", Number = "37", Pages = "7313--7320", Year = "1997", Abstract = "A model for the spectral characteristics, the transition dipole moment orientations, and the energy transfer properties of chlorophyll (Chl) a and b molecules in the light-harvesting complex (LHC) II is proposed on the basis of the results from femtosecond transient measurements and other spectroscopic data. The model uses the structural data (Kuhlbrandt; et al. Nature 1994, 367, 614) and is obtained using a genetic algorithm search of the large parameter space. Forster resonance transfer has been assumed as the mechanism of energy transfer. The spectral and orientational assignments of all twelve Chl molecules of a LHC II monomer are proposed. In the best fit model two of the seven Chl molecules that are proximal to the central luteins are Chl b. In contrast to prior assumptions, the basic feature of the model consists of an intermediately strong coupling (V < 100 cm(-1)) between the Chl a and b molecules in close pairs and the absence of substantial excitonic coupling between Chls a, thus indicating an overall limited influence of excitonic effects on spectra and kinetics. A theoretical estimation of exciton effects supports these model assumptions. Over most of the difference absorption spectrum good agreement between experimental and theoretical kinetics has been obtained. Energy transfer times in the symmetric LHC II trimer range from 90 fs to 5.1 ps. For the monomeric complexes only the longest lifetime is significantly affected and predicted to be just slightly longer (6.6 ps). The predicted transition dipole moment orientations result in weak coupling between the LHC II monomers. Several possible routes to improve both the data fitting and the reliability of the predictions in the future are discussed.", KeyWordsPlus=" TRANSIENT ABSORPTION-SPECTROSCOPY, ULTRAFAST ENERGY-TRANSFER, A/B PROTEIN COMPL EX, LHC-II, PHOTOSYSTEM-II, PHOTOSYNTHETIC SYSTEMS, CHLOROPHYLL-A, ELECTRON CRYSTALLOGRAPHY , CHLOROPLAST MEMBRANES, EXCITON MIGRATION" } @article{Zwick_96, Title="Global optimization studies on the 1-D phase problem", Author ="M. Zwick and B. Lovell and J. Marsh", Journal="International Journal of General Systems", Volume ="25", Number ="1", Pages ="47--59", Year ="1996", Abstract = "The Genetic Algorithm (GA) and Simulated Annealing (SA), two techniques for global optimization, were applied to a reduced (simplified) form of the phase problem (RPP) in computational crystallography. Results were compared with those of ''enhanced pair flipping'' (EPF), a more elaborate problem-specific algorithm incorporating local and global searches. Not surprisingly, EPF did better than the GA or SA approaches, but the existence of GA and SA techniques more advanced than those used in this study suggest that these techniques still hold promise for phase problem applications. The RPP is, furthermore, an excellent test problem for such global optimization methods.", AuthorKeywords =" phase problem, computational crystallography, global optimization, Genetic Algo rithm, simulated annealing" } @article{Jones_97, Title="Development and validation of a genetic algorithm for flexible docking", Author ="G. Jones and P. Willett and R.C. Glen and A.R. Leach and R. Taylor", Journal ="Journal of Molecular Biology", Volume ="267", Number ="3", Pages ="727--748", Year = "1997", Abstract = "Prediction of small molecule binding modes to macromolecules of known three-dimensional structure is a problem of paramount importance in rational drug design (the ''docking'' problem). We report the development and validation of the program GOLD (Genetic Optimisation for Ligand Docking). GOLD is an automated Ligand docking program that uses a genetic algorithm to explore the full range of ligand conformational flexibility with partial flexibility of the protein, and satisfies the fundamental requirement that the ligand must displace loosely bound water on binding. Numerous enhancements and modifications have been applied to the original technique resulting in a substantial increase in the reliability and the applicability of the algorithm. The advanced algorithm has been tested on a dataset of 100 complexes extracted from the Brookhaven Protein DataBank. When used to dock the ligand back into the binding site, GOLD achieved a 71% success rate in identifying the experimental binding mode.", AuthorKeywords="docking problem, genetic algorithm, molecular recognition, prot ein ligand docking", KeyWordsPlus =" REFINED CRYSTAL-STRUCTURE, X-RAY CRYSTALLOGRAPHY, ESCHERICHIA-COLI, DIHYDROFOLATE-REDUCTASE, 3-DIMENSIONAL STRUCTURE, CONFORMATIONAL-CHANGES, MOLEC ULAR RECOGNITION, ANGSTROM RESOLUTION, BINDING PROTEIN, BETA-LACTAMASE" } @article{Doll_96, Title="Global optimization in {LEED} structure determination using genetic algorithms", Author ="R. Doll and M.A. VanHove", Journal ="Surface Science", Volume ="355", Number ="1-3", Pages ="L393--L398", Year ="1996", Abstract = "By application of search algorithms, low energy electron diffraction (LEED) structure determination is now capable of solving relatively complicated systems. However, since LEED is a diffraction technique, the danger remains in identifying an incorrect structure because a local rather than a global minimum in the R-factor hypersurface was found. Recently it has been suggested that simulated annealing could be employed to circumvent this potential problem. In this Letter, using the Ir(110)-(1 x 2) missing row structure as an example, we demonstrate that genetic algorithms can also be used for a full structural analysis. Our results indicate that a rough global search using a genetic algorithm, followed by structural refinement using conventional steepest descent methods, should yield the correct structure within a typically tractable timescale.", AuthorKeywords ="electron-solid diffraction, iridium, low energy electron diffr action (LEED), low index single crystal surfaces, surface structure", KeyWordsPlus = "ENERGY-ELECTRON-DIFFRACTION, SURFACE-STRUCTURE DETERMINATION, TENSOR LEED, CRYSTALLOGRAPHY." } @article{MacKay_95, Title="Generalized Crystallography", Author ="A.L. MacKay", Journal ="THEOCHEM-Journal of Molecular Structure", Volume ="336", Number ="2--3", Pages ="293--303", Year ="1995", Abstract = "The paradigm of X-ray crystal structure analysis has provided the structures of some 200000 molecular, ionic and metallic substances. The disadvantage of the direct methods used in restoring the phases of the scattered waves is the necessary assumption that all unit cells in the crystals are the same. With the appearance of electron microscopy and scanning tunnelling microscopy, which do not lose the phases on recording, the imaging of more general objects has become possible. A sketch of some of the components which might comprise a generalisation of classical crystallography is attempted. In particular, it is suggested that a biological approach to inorganic:systems might provide new insight. The construction of an 'inorganic gene' as a computing device is proposed.", AuthorKeywords =" CRYSTALLOGRAPHY, GENETIC ALGORITHM, INORGANIC GENE, VORONOI" } @article{Chacon_98, Title="Low-resolution structures of proteins in solution retrieved from X-ray scattering with a genetic algorithm", Author ="P. Chacon and F. Moran and J.F. Diaz and E. Pantos and J.M. Andreu", Journal ="Biophysical Journal", Volume ="74", Number ="6", Pages ="2760--2775", Year = "1998", Abstract = "Small-angle x-ray solution scattering (SAXS) is analyzed with a new method to retrieve convergent model structures that fit the scattering profiles. An arbitrary hexagonal packing of several hundred beads containing the problem object is defined. Instead of attempting to compute the Debye formula for all of the possible mass distributions, a genetic algorithm is employed that efficiently searches the configurational space and evolves best-fit bead models. Models from different runs of the algorithm have similar or identical structures. The modeling resolution is increased by reducing the bead radius together with the search space in successive cycles of refinement. The method has been tested with protein SAXS (0.001 < S < 0.06 Angstrom(-1)) calculated from x-ray crystal structures, adding noise to the profiles. The models obtained closely approach the volumes and radii of gyration of the known structures, and faithfully reproduce the dimensions and shape of each of them. This includes finding the active site cavity of lysozyme, the bilobed structure of gamma-crystallin, two domains connected by a stalk in beta b2-crystallin, and the horseshoe shape of pancreatic ribonuclease inhibitor. The low-resolution solution structure of lysozyme has been directly modeled from its experimental SAXS profile (0.003 < S < 0.03 Angstrom(-1)). The model describes lysozyme size and shape to the resolution of the measurement. The method may be applied to other proteins, to the analysis of domain movements, to the comparison of solution and crystal structures, as well as to large macromolecular assemblies.", KeyWordsPlus =" SMALL-ANGLE SCATTERING, DIRECT SHAPE DETERMINATION, CURVE-FITTING PROCEDURE, NEUTRON-SCATTERING, SYNCHROTRON-RADIATION, MOLECULAR RECOGNITION, SECONDARY STR UCTURE, CRYSTAL-STRUCTURE, MYOSIN HEAD, MACROMOLECULES" } @article{Shankland_98, Title="Structure solution of Ibuprofen from powder diffraction data by the application of a genetic algorithm combined with prior conformational analysis", author ="K. Shankland and W.I.F. David and T. Csoka and L. McBride", journal ="International Journal of Pharmaceutics", volume ="165", number ="1", pages ="117--126", year ="1998", Abstract = "The crystal structure of Ibuprofen has been solved from synchrotron X-ray powder diffraction data using a genetic algorithm based model building method. The performance of the algorithm is enhanced if additional prior chemical information is incorporated in the form of hard limits on the values that can be assumed by flexible torsion angles within the molecule.", AuthorKeywords = "Ibuprofen, crystal structure solution, X-ray powder diffracti on, genetic algorithm", KeyWordsPlus = "STRUCTURE-FACTOR AMPLITUDES" } @article{Cui_98, Title="Protein folding simulation with genetic algorithm and supersecondary structure constraints", Author ="Y. Cui and R.S. Chen and W.H. Wong", Journal ="Proteins-Structure Function And Genetics", Volume ="31", Number ="3", Pages ="247--257", Year ="1998", Abstract = "We describe an algorithm to compute native structures of proteins from their primary sequences. The novel aspects of this method are: 1) The hydrophobic potential was set to be proportional to the nonpolar solvent accessible surface. To make computation feasible, we developed a new algorithm to compute the solvent accessible surface areas rapidly. 2) The supersecondary structures of each protein were predicted and used as restraints during the conformation searching processes, This algorithm was applied to five proteins. The overall fold of these proteins can be computed from their sequences, with deviations from crystal structures of 1.48-4.48 Angstrom for C-alpha atoms.", AuthorKeywords = " protein structure prediction, supersecondary structure, genetic algorithm, solv ent accessible surface area, hydrophobic potential", KeyWordsPlus ="ACCESSIBLE SURFACE-AREA, ANALYTICAL MOLECULAR-SURFACE, NEAR-NATI VE FOLDS, STRUCTURE PREDICTION, GLOBULAR-PROTEINS, X-RAY, VOLUME, ENERGY, PACKI NG, SOLVENT" } @article{Lorber_98, Title="Flexible ligand docking using conformational ensembles", Author ="D.M. Lorber and B.K. Shoichet", Journal ="Protein Science", Volume ="7", Number ="4", Pages ="938--950", Year ="1998", Abstract = "Molecular docking algorithms suggest possible structures for molecular complexes. They are used to model biological function and to discover potential ligands. A present challenge for docking algorithms is the treatment of molecular flexibility. Here, the rigid body program, DOCK, is modified to allow it to rapidly fit multiple conformations of ligands. Conformations of a given molecule are pre-calculated in the same frame of reference, so that each conformer shares a common rigid fragment with all other conformations. The ligand conformers are then docked together, as an ensemble, into a receptor binding site. This takes advantage of the redundancy present in differing conformers of the same molecule. The algorithm was tested using three organic ligand protein systems and two protein-protein systems. Both the bound and unbound conformations of the receptors were used. The ligand ensemble method found conformations that resembled those determined in X-ray crystal structures (RMS values typically less than 1.5 Angstrom). To test the method's usefulness for inhibitor discovery, multi-compound and multi-conformer databases were screened for compounds known to bind to dihydrofolate reductase and compounds known to bind to thymidylate synthase. In both cases, known inhibitors and substrates were identified in conformations resembling those observed experimentally. The ligand ensemble method was 100-fold faster than docking a single conformation at a time and was able to screen a database of over 34 million conformations from 117,000 molecules in one to four CPU days on a workstation.", AuthorKeywords ="conformation, flexibility, molecular docking, structure-based drug design", KeyWordsPlus="AUTOMATED DOCKING, DIHYDROFOLATE-REDUCTASE, MOLECULAR DOCKING, BE TA-LACTAMASE, DRUG DESIGN, 3-DIMENSIONAL STRUCTURE, LACTATE-DEHYDROGENASE, CRYS TAL-STRUCTURES, GENETIC ALGORITHM, ESCHERICHIA-COLI" } @article{Michaelian_98, Title="Evolving few-ion clusters of {Na} and {Cl}", Author ="K. Michaelian", Journal ="American Journal of Physics", Volume ="66", Number ="3", Pages ="231--240", Year ="Mar. 1998", Abstract = "The ground state configuration of a macroscopic quantity of Na and Cl ions is the well-known crystalline, face-centered cubic structure (table salt). However, when the number of ions is reduced to a handful, geometrically quite different and interesting ground state structures occur. Such configurations are realized in the early stages of crystal growth and are important in a growing number of physical applications. This article describes the application of a genetic algorithm to the difficult problem of the determination of the lowest-energy geometrical configurations of few-ion (less than or equal to 12) clusters of Na and Cl. The binding energy and the frequencies of vibration determined for these structures are compared to experimental data and to published results of other calculations. The advantages and limitations of the genetic algorithm as a tool for cluster physics are discussed.", KeyWordsPlus="LENNARD-JONES CLUSTERS, GENETIC ALGORITHMS, SEARCH, DYNAMICS, ENE RGY, MICROCLUSTERS, OPTIMIZATION, SIMPLICITY, MOLECULES, SURFACES", } article{Poirrette_97, Title="Comparison of protein surfaces using a genetic algorithm", Author ="A.R. Poirrette and P.J Artymiuk D.W. Rice and P. Willett", Journal ="Journal of Computer-Aided Molecular Design", Volume ="11", Number ="6", Pages ="557--569", Year = "Nov. 1997", Abstract = "A genetic algorithm (GA) is described which is used to compare the solvent-accessible surfaces of two proteins or fragments of proteins, represented by a dot surface calculated using the Connolly algorithm. The GA is used to move one surface relative to the other to locate the most similar surface region between the two. The matching process is enhanced by the use of the surface normals and shape terms provided by the Connolly program and also by a simple hydrogen-bonding descriptor and an additional shape descriptor. The algorithm has been tested in applications ranging from the comparison of small surface patches to the comparison of whole protein surfaces, and it has performed correctly in all cases. Examples of the matches are given and a quantitative analysis of the quality of the matches is performed. A number of possible future enhancements to the program are described which would allow the GA to be used for more complex surface comparisons.", AuthorKeywords="protein structure, molecular surfaces, structure comparison, bi nding sites, evolutionary computation", } @article{Bayley_98, Title="GENFOLD: A genetic algorithm for folding protein structures using {NMR} restraints", Author = "M.J. Bayley and G. Jones and P. Willett and M.P. Williamson", Journal = "Protein Science", Volume = "7", Number = "2", Pages = "491--499", Year = "1998", Abstract = "We report the development and validation of the program GENFOLD, a genetic algorithm that calculates protein structures using restraints obtained from NMR, such as distances derived from nuclear Overhauser effects, and dihedral angles derived from coupling constants. The program has been tested on three proteins: the POU domain (a small three-helix DNA-binding protein), bovine pancreatic trypsin inhibitor (BPTI), and the starch-binding domain from Aspergillus niger glucoamylase I, a 108-residue beta-sheet protein. Structures were calculated for each protein using published NMR restraints. In addition, structures were calculated for BPTI using artificial restraints generated from a high-resolution crystal structure. In all cases the fittest calculated structures were close to the target structure, and could be refined to structures indistinguishable from the target structures by means of a low-temperature simulated annealing refinement. The effectiveness of the program is similar to that of distance geometry and simulated annealing methods, and it is capable of using a very wide range of restraints as input. It can thus be readily extended to the calculation of structures of large proteins, for which few NOE restraints may be available." } @article{deSouza_98, Title="Automation of the analysis of {Mossbauer} spectra", Author = "P.A. de Souza and R. Garg and V.K. Garg", Journal ="Hyperfine Interactions", Volume ="112", Number ="1--4", Pages ="275--278", Year ="1998", Abstract = "In the present report we propose the automation of least square fitting of Mossbauer spectra, the identification of the substance, its crystal structure and the access to the references with the help of a genetic algorithm, Fuzzy logic, and the artificial neural network associated with a databank of Mossbauer parameters and references. This system could be useful for specialists and non-specialists, in industry as well as in research laboratories.", KeyWordsPlus = " ARTIFICIAL NEURAL-NETWORK, IDENTIFICATION", } @article{White_98, Title="A study of genetic algorithm approaches to global geometry optimization of aromatic hydrocarbon microclusters", Author ="R.P. White and J.A. Niesse and H.R. Mayne", Journal ="Journal of Chemical Physics", Volume ="108", Number ="5", Pages ="2208--2218", Year ="1998", Abstract = "We have carried out potential energy minimization calculations on benzene, naphthalene, and anthracene clusters using model potential energy functions. The primary purpose was to examine several techniques which use concepts from the field of genetic algorithms (GA). In particular, we compared the ``traditional GA'' in which the variables of the problem are coded into binary and genetic operations performed on these, and recent methods which use real-valued variables. Our primary technique, the ``space-fixed modified GA'' (SFMGA), also uses a conjugate gradient descent on the geometries generated by the GA. Our results show the convergence to the global minimum is greatly improved by the use of the descent minimization. In fact, it appears unlikely that the traditional GA's are useful for any but the very simplest clusters. We have also compared the SFMGA with simulated annealing (SA) and Wales and Doye's recent basin-hopping (BH) technique. We find our method to be superior to SA, and comparable to BH.", KeyWordsPlus = "LENNARD-JONES CLUSTERS, SMALL BENZENE CLUSTERS, SCHRODINGER-EQU ATION, CRYSTAL-STRUCTURES, ATOMIC CLUSTERS, MONTE-CARLO, MINIMUM, PREDICTION, S EARCHES" } @article{Kariuki_97, Title="The application of a genetic algorithm for solving crystal structures from powder diffraction data", Author ="B.M. Kariuki and H. Serrano-Gonzalez and R.L. Johnston and K.D.M. Harris", Journal ="Chemical Physics Letters", Volume ="280", Number ="3-4", Pages ="189--195", Year ="1997", Abstract = "We report the successful application of a genetic algorithm to tackle crystal structure solution from powder diffraction data in the case of a previously unknown structure - ortho-thymotic acid. In the structure solution calculation, the structural fragment was subjected to combined translation and rotation within the unit cell, together with variation of selected intramolecular degrees of freedom under the control of a genetic algorithm, in which a population of trial structures is allowed to evolve subject to well-defined procedures for mating, mutation and natural selection. Importantly, the genetic algorithm approach adopts the `direct-space' philosophy for structure solution, and implicitly avoids the problematic step of extracting the intensities of individual reflections from the powder diffraction data. The structure solution was found efficiently in the genetic algorithm calculation, and was then used as the initial structural model in Rietveld refinement calculations. The work reported in this Letter paves the way for the future application of the genetic algorithm approach to a much wider array of structural problems.", KeyWordsPlus = "MONTE-CARLO METHODS, X-RAY" } @article{Apostolakis_98, Title="Docking small ligands in flexible binding sites", Author ="J. Apostolakis and A. Pluckthun and A. Caflisch", Journal ="Journal of Computational Chemistry", Volume ="19", Number ="1", Pages ="21--37", Year ="Jan. 15, 1998", Abstract = "A novel procedure for docking ligands in a flexible binding site is presented. It relies on conjugate gradient minimization, during which nonbonded interactions are gradually switched on. Short Monte Carlo minimization runs are performed on the most promising candidates. Solvation is implicitly taken into account in the evaluation of structures with a continuum model. It is shown that the method is very accurate and can model induced fit in the ligand and the binding site. The docking procedure has been successfully applied to three systems. The first two are the binding of progesterone and 5 beta-androstane-3, 17-dione to the antigen binding fragment of a steroid binding antibody. A comparison of the crystal structures of the free and the two complexed forms reveals that any attempt to model binding must take protein rearrangements into account. Furthermore, the two ligands bind in two different orientations, posing an additional challenge. The third test case is the docking of N-alpha-(2-naphthyl-sulfonyl-glycyl)-D-para-amidino-phenyl-alanyl-piperidine (NAPAP) to human alpha-thrombin. In contrast to steroids, NAPAP is a very flexible ligand, and no information of its conformation in the binding site is used. All docking calculations are started from X-ray conformations of proteins with the uncomplexed binding site. For all three systems the best minima in terms of free energy have a root mean square deviation from the X-ray structure smaller than 1.5 Angstrom for the ligand atoms.", AuthorKeywords =" antisteroid antibody, progesterone, thrombin, NAPAP, flexible docking, MSNI, MCM, finite-difference Poisson-Boltzmann technique", KeyWordsPlus = "MONTE-CARLO-MINIMIZATION, COPY SIMULTANEOUS SEARCH, THROMBIN IN HIBITORS, 3-DIMENSIONAL STRUCTURE, MOLECULAR RECOGNITION, ELECTROSTATIC ENERGY, AUTOMATED DOCKING, GENETIC ALGORITHM, CONTINUUM MODEL, ALPHA-THROMBIN" } @article{Ikeda_97, Title="A new method of alloy design using a genetic algorithm and molecular dynamics simulation and its application to nickel-based superalloys", Author ="Y. Ikeda", Journal ="Materials Transactions Jim", Volume ="38", Number ="9", Pages ="771--779", Year ="1997", Abstract = "A new method of allay design was proposed using a genetic algorithm and molecular dynamics simulations. In this method, evaluations of physical quantities using molecular dynamics simulations and an efficient global search using a genetic algorithm allow optimization of an equilibrium composition for a multi-component alloy satisfying a given design rule. The ahoy design method was used to design nickel-based superalloys in the elemental systems simulating those of TMS-63 and CMSX-2. The obtained atom fractions in the gamma phase and gamma' phase, and atom fractions in the Ni and Al sublattices of the gamma' phase were compared with the experimental values. The comparisons showed that the global features of TMS-63 and CMSX-2 were reproduced well. Furthermore negative lattice misfits were of about 1% and positive elastic misfits for c(11) and c(12) were of about 10% for both alloys. Finally sources of the inaccuracies for the obtained atom fractions and possible improvements for the design method were discussed." } @article{Fleischer_97, Title="D-QSAR analysis and molecular modeling investigations of piritrexim and analogous", Author ="R. Fleischer and M. Wiese and R. Troschutz and M. Zink", Journal ="Journal of Molecular Modeling", Volume ="3", Number ="8", Pages ="338--346", Year ="1997", Abstract = "Quantitative structure-activity, relationships for piritrexim and analogues acting as inhibitors of tumour cell growth have been derived. First the Free-Wilson-method was used on a homologous training set of night derivatives. The selection of variables important for the biological activity of the compounds was carried out with different multivariate methods as multiple linear regression, the partial least squares method and a genetic algorithm. The derivation of three-dimensional structure activity relationships started with a systematic conformational analysis of all compounds. For the conformations having minimal energy and being in agreement with the crystal structure of piritrexim charges were calculated with the AM1 hamiltonian. For the superimposition of the derivatives two methods were used: maximal similarity of the common substructure or of the molecular fields. A Comparative Molecular Field Analysis with steric and electrostastic fields identified regions important for the activity of the studied compounds independent of the chosen alignment and also correctly predicted the activity of two nonhomologous compounds." } @article{Shankland_97, Title="Crystal structure determination from powder diffraction data by the application of a genetic algorithm", Author ="K. Shankland and W.I.F. David and T. Csoka", Journal ="Zeitschrift {Fur} Kristallographie", Volume ="212", Number = "8", Pages = "550--552", Year ="1997", Abstract = "A genetic algorithm (GA) based method for solving crystal structures directly from powder diffraction data has been developed. The method is based around fitting the diffraction data generated film trial structures against the measured diffraction data and has the ability to handle flexible molecules and multiple fragments. It is computationally highly efficient and takes full advantage of the implicit parallelism of the GA. The method is illustrated with the solutions of three crystal structures of varying complexity." } @article{Sahara_97, Title="A Monte Carlo simulation describing melting transition of Si-type structure in the condensed phase with BCC lattice model including many-body interactions", author ="R. Sahara and H. Mizuseki and K. Ohno and S. Uda and T. Fukuda and Y. Kawazoe", journal ="Science Reports of The Research Institutes Tohoku University Series A -Physics Chemistry And Metallurgy", volume ="43", number ="1", pages ="23--28", year =" Mar. 1997", Abstract = "A new lattice model is proposed for Si crystallization from molten state, which is based on Monte Carlo (MC) simulation. In this model, each atom is allowed to move only on BCC lattice sites, and the potential energy of atom depends on the configuration in the Ist nearest neighbors. With the parameter that only the atoms constructing tetrahedron have lower energy than others, the Ist-order phase transition between diamond and random structures is observed, including a hysteresis behavior. On the other hand, with using a parameter set which is defined as a function of the number of the Ist nearest neighbors and the bond angles, which is determined by using genetic algorithm, the state is continuously changed with temperature." } @article{Knegtel_97, Title="Molecular docking to ensembles of protein structures", Author="R.M.A. Knegtel and I.D. Kuntz and C.M. Oshiro", Journal ="Journal of Molecular Biology", Volume ="266", Number ="2", Pages ="424--440", Year ="Feb. 21, 1997", Abstract = "Until recently, applications of molecular docking assumed that the macromolecular receptor exists in a single, rigid conformation. However, structural studies involving different ligands bound to the same target biomolecule frequently reveal modest but significant conformational changes in the-target. In this paper, two related methods for molecular docking are described that utilize information on conformational variability from ensembles of experimental receptor structures. One method combines the information into an ``energy-weighted average'' of the interaction energy between a ligand and each receptor structure. The other method performs the averaging on a structural level, producing a ``geometry-weighted average'' of the inter-molecular force field score used in DOCK 3.5. Both methods have been applied in docking small molecules to ensembles of crystal and solution structures, and we show that experimentally determined binding orientations and computed energies of known ligands can be reproduced accurately. The use of composite grids, when conformationally different protein structures are available, yields an improvement in computational speed for database searches in proportion to the number of structures." } @article{Mikulin_97, Title="Fitting reflectivity data from liquid crystal cells using genetic algorithms", Author ="D.J. Mikulin and D.A. Coley and J.R. Sambles", Journal ="Liquid Crystals", Volume ="22", Number ="3", Pages ="301--307", Year ="Mar. 1997", Abstract = "The half-leaky guided mode technique for quantifying thin optical layers is here combined with a data fitting routine based on a genetic algorithm to provide an immensely powerful procedure for detailing the director profile in liquid crystal cells. This approach not only provides a full description of the optical parameters of the cell, but also gives quantitative uncertainties in these parameters. It is tested here, first by fitting to theoretically produced data and then applied to real experimental data." } @article{Li_97, Title="Refinement of the {NMR} solution structure of the gamma-carboxyglutamic acid domain of coagulation factor {IX} using molecular dynamics simulation with initial {Ca2+} positions determined by a genetic algorithm", Author = "L.P. Li and T.A. Darden and S.J. Freedman and B.C. Furie and B. Furie and J.D. Baleja and H. Smith and R.G. Hiskey and L.G. Pedersen", Journal ="Biochemistry", Volume ="36", Number ="8", Pages ="2132--2138", Year ="1997", Abstract = "A genetic algorithm (GA) successfully identified the calcium positions in the crystal structure of bovine prothrombin fragment 1 bound with calcium ions (bfl/Ca). The same protocol was then used to determine the calcium positions in a closely related fragment, the Gla domain of coagulation factor IX, the structure of which had previously been determined by NMR spectroscopy in the presence of calcium ions. The most frequently occurring low-energy structure found by GA was used as the starting structure for a molecular dynamics refinement. The molecular dynamics simulation was performed using explicit water and the Particle-Mesh Ewald method to accommodate the long-range electrostatic forces. While the overall conformation of the NMR structure was preserved, significant refinement is apparent when comparing the simulation average structure with its NMR precursor in terms of the N-terminal (Tyr1-N) network, the total number of hydrogen bonds, the calcium ion coordinations, and the compactness of the structure. It is likely that the placement of calcium ions in the protein is critical for refinement. The calcium ions apparently induce structural changes during the course of the simulation that result in a more compact structure." } @article{Gunn_97, Title="Sampling protein conformations using segment libraries and a genetic algorithm", Author ="J.R. Gunn", Journal ="Journal of Chemical Physics", Volume ="106", Number ="10", Pages ="4270--4281", Year ="1997", Abstract = "We present a new simulation algorithm for minimizing empirical contact potentials for a simplified model of protein structure. The model consists of backbone atoms only (including C-beta) with the phi and psi dihedral angles as the only degrees of freedom. In addition, phi and psi are restricted to a finite set of 532 discrete pairs of values, and the secondary structural elements are held fixed in ideal geometries. The potential function consists of a leak-up table based on discretized inter-residue atomic distances. The minimization consists of two principal elements: the use of preselected lists of trial moves and the use of a genetic algorithm. The trial moves consist of substitutions of one or two complete loop regions, and the lists are in turn built up using preselected lists of randomly-generated three-residue segments. The genetic algorithm consists of mutation steps (namely, the loop replacements), as well as a hybridization step in which new structures an created by combining parts of two ''parents'' and a selection step in which hybrid structures are introduced into the population. These methods are combined into a Monte Carlo simulated annealing algorithm which has the overall structure of a random walk on a restricted set of preselected conformations. The algorithm is tested using two types of simple model potential. The first uses global information derived from the radius of gyration and the rms deviation to drive the folding, whereas the second is based exclusively on distance-geometry constraints. The hierarchical algorithm significantly outperforms conventional Monte Carlo simulation for a set of test proteins in both cases, with the greatest advantage being for the largest molecule having 193 residues. When tested an a realistic potential function, the method consistently generates structures ranked lower than the crystal structure. The results also show that the improved efficiency of the hierarchical algorithm exceeds that which would be anticipated from tests on either of the two main elements used independently." } @article{Raymer_97, Title="Predicting conserved water-mediated and polar ligand interactions in proteins using a $K$-nearest-neighbors genetic algorithm", Author ="M.L. Raymer and P.C. Sanschagrin and W.F. Punch and S. Venkataraman and E.D. Goodman and L.A. Kuhn", Journal ="Journal of Molecular Biology", Volume ="265", Number ="4", Pages ="445--464", Year ="1997", Abstract = "Water-mediated ligand interactions are essential to biological processes, from product displacement in thymidylate synthase to DNA recognition by Trp repressor, yet the structural chemistry influencing whether bound water is displaced or participates in ligand binding is not well characterized. Consolv, employing a hybrid k-nearest-neighbors classifier/genetic algorithm, predicts bound water molecules conserved between free and ligand-bound protein structures by examining the environment of each water molecule in the free structure. Four environmental features are used: the water molecule's crystallographic temperature factor, the number of hydrogen bonds between the water molecule and protein, and the density and hydrophilicity of neighboring protein atoms. After training on 13 non-homologous proteins, Consolv predicted the conservation of active-site water molecules upon ligand binding with 75% accuracy (Matthews coefficient C-m = 0.41) for seven new proteins. Mispredictions typically involved water molecules predicted to be conserved that were displaced by a polar ligand atom, indicating that Consolv correctly assesses polar binding sites; 90% accuracy (C-m = 0.78) was achieved for predicting conserved active-site water or polar ligand atom binding. Consolv thus provides an accurate means for optimizing ligand design by identifying sites favored to be occupied by either a mediating water molecule or a polar ligand atom, as well as water molecules likely to be displaced by the ligand. Accuracy for predicting first-shell water conservation between independently determined structures was 61% (C-m = 0.23). The ability to predict water-mediated and polar interactions from the free protein structure indicates the surprising extent to which the conservation or displacement of active-site bound water is independent of the ligand, and shows that the protein micro-environment of each water molecule is the dominant influence.", } @article{vanKampen_96, Title="Lethalization, penalty and repair functions for constraint handling in the genetic algorithm methodology", Author=" A.H.C. vanKampen and C.S. Strom and L.M.C Buydens", Journal ="Chemometrics And Intelligent Laboratory Systems", Volume ="34", Number ="1", Pages ="55--68", Year = "1996", Abstract = "A genetic algorithm was designed to find low energy distributions of ions above a crystal surface. To solve this constrained optimization problem, several constrained handling techniques were applied, i.e., lethalization, penalty and repair functions. It was shown that the simple lethalization scheme performs very well, and was at least comparable to some of the penalty functions. This was unexpected because, in general, it is believed that a severe penalization (i.e., lethalization) leads to poor results. An analysis of the fitnesses of trial distributions that violated a constraint as a function of the time, suggested that the properties of genetic based search were responsible for this result. From this it was concluded that a genetic algorithm in combination with lethalization may be an good choice to solve constrained optimization problems if the design of optimal penalty functions is difficult or impossible." } @article{Meza_96, Title="A comparison of a direct search method and a genetic algorithm for conformational searching", author ="J.C. Meza and R.S. Judson and T.R. Faulkner and A.M. Treasurywala", journal ="Journal of Computational Chemistry", volume ="17", number ="9", pages ="1142--1151", year ="1996", Abstract = "We present results from the application of two conformational searching methods: genetic algorithms (GA) and direct search methods for finding low energy conformations of organic molecules. GAs are in a class of biologically motivated optimization methods that evolve a population of individuals in which individuals who are more ``fit'' have a higher probability of surviving into subsequent generations. The parallel direct search method (PDS) it a type of pattern search method that uses an adaptive grid to search for minima. Both methods found energies equal to or lower than the energy of the relaxed crystal structure in all cases, at a relatively small cost in CPU time. We suggest that either method would be a good candidate to find 3-D conformations in a large scale screening application.", KeyWordsPlus="SMALL MOLECULES" } @article{Dandekar_96, Title="Identifying the tertiary fold of small proteins with different topologies from sequence and secondary structure using the genetic algorithm and extended criteria specific for strand regions", Author ="T. Dandekar and P. Argos", Journal ="Journal of Molecular Biology", Volume ="256", Number ="3", Pages ="645--660", Year ="1996", Abstract = "Grid-free protein folding simulations based on sequence and secondary structure knowledge (using mostly experimentally determined secondary structure information but also analysing results from secondary structure predictions) were investigated using the genetic algorithm, a backbone representation, and standard dihedral angular conformations. Optimal structures are selected according to basic protein building principles. Having previously applied this approach to proteins with helical topology, we have now developed additional criteria and weights for beta-strand-containing proteins, validated them on four small beta-strand-rich proteins with different topologies, and tested the general performance of the method on many further examples from known protein structures with mixed secondary structural type and less than 100 amino acid residues. Topology predictions close to the observed experimental structures were obtaine d in four test cases together with fitness values that correlated with the similarity of the predicted topology to the observed struct ures. Root-mean-square deviation values of C-alpha atoms in the superposed predicted and observed structures, the latter of which had di fferent topologies, were between 4.5 and 5.5 Angstrom (2.9 to 5.1 Angstrom without loops). Including 15 further protein examples with uniq ue folds, root-mean-square deviation values ranged between 1.8 and 6.9 Angstrom with loop regions and averaged 5.3 Angstrom and 4. 3 Angstrom, including and excluding loop regions, respectively." } @article{Willett_95, Title="Genetic algorithms in molecular recognition and design", author ="P. Willett", Journal ="Trends in Biotechnology", Volume ="13", Number ="12", Pages ="516--521", Year ="1995", Abstract = "Genetic algorithms provide a novel tool for the investigation of combinatorial optimization problems. A genetic algorithm takes an initial set of possible starting solutions, and iteratively improves them by means of crossover and mutation operators that are related to those involved in Darwinian evolution. This approach is illustrated by reference to applications in molecular modelling, the docking of flexible ligands into protein active sites and de novo ligand design." } @article{May_95, Title="Improved genetic algorithm-based protein structure comparisons: Pairwise and multiple superpositions", Author ="A.C.W. May and M.S. Johnson", Journal ="Protein Engineering", Volume ="8", Number ="9", Pages ="873--882", Year ="1995", Abstract = "Three major improvements to a previously described method for automatic protein structure comparison are described. First, a limit to translations for the rigid-body superposition is now assigned according to the dimensions of the structures being compared. Second, examination of the effect of the gap penalty on the derivation of a sequence alignment corresponding to a given structure superposition has led to a method to evaluate alternative structure-based sequence alignments. Third, the pairwise procedure has been generalized to multiple structure alignment. This implementation of rigid-body superposition can recognize well documented distant relationships which hitherto have required consideration of additional features and properties as well as those relationships between proteins of different sizes. A much larger common scaffold or framework between six globins can be extracted than that obtained using a standard algorithm for multiple structure superposition." } @article{Tam_95, Title="{GAMATCH} - A Genetic Algorithm-Based Program For Indexing Crystal Faces", Author ="K.Y. Tam and R.G. Compton", Journal ="Journal of Applied Crystallography", Volume ="28", Pages ="640--645", Year = "1995", Abstract = "An intelligent genetic algorithm-based crystal-indexing program, GAMATCH, is described, by means of which the Miller indices of the relevant planes can be unambiguously identified using a set of interplanar angles. A two-step-divide-and-conquer strategy is employed and is found to speed up the convergence to the global solution. The program was tested using both hypothetical and centimetre-sized triphenylmethyl chloride crystals. The results obtained were compared to the expected indices and excellent agreement was noted." } @article{Lazar_97, title ="De novo design of the hydrophobic core of ubiquitin", author ="G.A. Lazar and J.R. Desjarlais and T.M. Handel", journal ="Protein Science", volume ="6", number ="6", pages ="1167--1178", year ="1997", Abstract ="We have previously reported the development and evaluation of a computational program to assist in the design of hydrophobic cores of proteins. In an effort to investigate the role of core packing in protein structure, we have used this program, referred to as Repacking of Cores (ROC), to design several variants of the protein ubiquitin. Nine ubiquitin variants containing from three to eight hydrophobic core mutations were constructed, purified, and characterized in terms of their stability and their ability to adopt a uniquely folded native-like conformation. In general, designed ubiquitin variants are more stable than control variants in which the hydrophobic core was chosen randomly. However, in contrast to previous results with 434 cro, all designs are destabilized relative to the wild-type (WT) protein. This raises the possibility that beta-sheet structures have more stringent packing requirements than alpha-helical proteins. A more striking observation is that all variants, including random controls, adopt fairly well-defined conformations, regardless of their stability. This result supports conclusions from the cro studies that non-core residues contribute significantly to the conformational uniqueness of these proteins while core packing largely affects protein stability and has less impact on the nature or uniqueness of the fold. Concurrent with the above work, we used stability data on the nine ubiquitin variants to evaluate and improve the predictive ability of our core packing algorithm. Additional versions of the program were generated that differ in potential function parameters and sampling of side chain conformers. Reasonable correlations between experimental and predicted stabilities suggest the program will be useful in future studies to design variants with stabilities closer to that of the native protein. Taken together, the present study provides further clarification of the role of specific packing interactions in protein structure and stability, and demonstrates the benefit of using systematic computational methods to predict core packing arrangements for the design of proteins." } @article{Dejarlais_95, title ="New Strategies in Protein Design", author ="J.R. Desjarlais and T.M. Handel", journal ="Current Opinion in Biotechnology", volume ="6", number = "4", pages = "460--466", year = "1995", Abstract = "Initially, it was hoped that very simple rules could be used to design proteins that embody all the characteristics of natural proteins. Indeed, with single-domain proteins as targets, it has been possible to design proteins that adopt the desired global fold. Yet, designed proteins with well defined structures and properties that mimic those of natural proteins remain elusive. Recent efforts in protein design have been directed toward addressing the basis for non-native characteristics in most protein designs. Although it is clear that specific tertiary interactions between all residues in a protein contribute to the final folded state, much attention has been placed on optimizing the packing of side chains in the hydrophobic core, with substantial success." } @article{Hirsch_95, Title="Fitting of Diffusion-Coefficients In A 3-Compartment Sustained-Release Drug Formulation Using A Genetic Algorithm", Author ="R. Hirsch and C.C. Mullergoymann", Journal ="International Journal of Pharmaceutics", Volume ="120", Number ="2", Pages ="229--234", Year ="1995", Abstract = "This article presents a method of fitting diffusion coefficients in a three-compartment drug formulation to data of concentration measurements. The volume of the central compartment is not constant, but increases with time up to a certain amount. The speed of growth is proportional to the actual distance from the final thickness. A model function based on Fick's second law of diffusion is used to describe the concentration with respect to location and time. In order to find the values of the diffusion coefficients they are encoded to data structures on which the mechanisms of evolution can be applied: mutation and selection. It is shown how the convergence speed is influenced by the optimization parameters: the more individuals are involved in the evolution process, the fewer the generations it takes the algorithm to fit the parameters. There are optimal values for the rate of mutation (m approximate to 0.008 bit(-1)) and the selection factor, which controls the influence of selection in the mating process. Its optimal value is less than unity, which means that the algorithm converges faster when sometimes the genetic information of the weaker of two individuals is passed on to the next generation.", AuthorKeywords = "DIFFUSION, FICKS 2ND LAW, LAMELLAR LIQUID CRYSTAL, SUSTAINED RELEASE, DIFFUSION COEFFICIENT, CURVILINEAR PARAMETER FITTING, GENETIC ALGORITH M" } @article{May_94, Title="Protein-Structure Comparisons Using A Combination of A Genetic Algorithm, Dynamic-Programming And Least-Squares Minimization", Author ="A.C.W. May and M.S. Johnson", Journal ="Protein Engineering", Volume ="7", Number ="4", Pages ="475--485", Year ="1994", Abstract = "We introduce a completely automatic and objective procedure for the comparison of protein structures. A genetic algorithm is used to search for a near optimal solution of the rigid-body superposition of two whole protein structures. The specification of an initial set of equivalences is not required. Topological equivalences in the final structural alignment are defined by a conventional dynamic programming routine, which is commonly used to compare protein sequences. A least-squares fitting algorithm is then used to optimize the fit between the final set of equivalences. We have applied our method to the comparison of ribonucleic acid structures, as well as protein structures. The structural alignments are generally consistent with those previously published. In fact, on most occasions our method defines at least the same number of topological equivalences as other procedures, but always with a lower r.m.s. distance between them." } @article{Hartke_93, Title="Global Geometry Optimization of Clusters Using Genetic Algorithms", Author ="B. Hartke", Journal ="Journal of Physical Chemistry", Volume ="97", Number ="39", Pages = "9973--9976", Year = "1993", Abstract = "A genetic algorithm is used to find the global minimum energy structure for Si4 on an empirical potential energy surface. Given a suitable encoding of the cluster geometry, and an exponential scaling of the potential energy values to obtain a fitness function, the genetic algorithm can successfully optimize all degrees of freedom. With the number of potential energy function evaluations as a measure, the genetic algorithm is more economical than either a set of traditional, local minimizations or a molecular dynamics simulated annealing approach." } @article{Zacharias_98, title="Combining genetic algorithm and simulated annealing: a molecular geometry optimization study", author ="C.R. Zacharias and M.R. Lemes and A.D. Pino", journal ="THEOCHEM-Journal of Molecular Structure", volume = "430", number ="29--39", year = "1998", abstract ="We introduce a new hybrid approach to determine the ground state geometry of molecular systems. Firstly, we compared the ability of genetic algorithm (GA) and simulated annealing (SA) to find the lowest energy geometry of silicon clusters with six and 10 atoms. This comparison showed that GA exhibits fast initial convergence, but its performance deteriorates as it approaches the desired global extreme. Interestingly, SA showed a complementary convergence pattern, in addition to high accuracy. Our new procedure combines selected features from GA and SA to achieve weak dependence on initial parameters, parallel search strategy, fast convergence and high accuracy. This hybrid algorithm outperforms GA and SA by one order of magnitude for small silicon clusters (Sib and Si lo) Next, we applied the hybrid method to study the geometry of a 20-atom silicon cluster. It was able to find an original geometry, apparently lower in energy than those previously described in literature. In principle, our procedure can be applied successfully to any molecular system." } @article{Fu_97, title = "Surface reconstruction of {Si} (001) by Genetic Algorithm and simulated annealing method", author ="R.T. Fu and K. Esfarjani and Y. Hashi and J. Wu and X. Sun and Y. Kawazoe", journal ="Science Reports of The Research Institutes Tohoku University Series A-Physics Chemistry And Metallurgy", volume ="44", number ="1", pages ="77--81", year = "Mar. 1997", Abstract ="The Genetic Algorithm (GA) is one of the most recently developed techniques to find the ''Global'' minimum of an energy functional. This technique combined with conjugated gradient or molecular dynamics has been demonstrated to be efficient for the ground-state configuration search in materials research, e.g. fullerene formation, in this paper, based on the generalized tight-binding molecular dynamics, we apply the GA to study the surface reconstruction of Silicon (001) for the first time. Up to 65 generations, the ''Global'' minimum or the ground-state configuration for the surface reconstruction of Si (001) was detected efficiently in our GA simulation. Id our tight-binding model, a perfect symmetry-dimer structure was found to be the most energetic while some defect asymmetry-dimer structure could coexist in the lists of candidate structures due to the thermal defect or charge transfer which was described with the smearing parameter empirically. We also perform the more traditional Simulated Annealing (SA) technique to deal with the same problem. The results in terms of efficiency, accuracy of the ground-state reconstructed surface and CPU time are compared." } @article{Clark_96, title="Evolutionary algorithms in computer-aided molecular design", author = "D.E. Clark and D.R. Westhead", journal ="Journal of Computer-aided Molecular Design", volume ="10", number = "4", pages ="337--358", year ="1996", Abstract = "In recent years, search and optimisation algorithms inspired by evolutionary processes have been applied with marked success to a wide variety of problems in diverse fields of study. In this review, we survey the growing application of these 'evolutionary algorithms' in one such area: computer-aided molecular design. In the course of the review, we seek to summarise the work to date and to indicate where evolutionary algorithms have met with success and where they have not fared so well. In addition to this, we also attempt to discern some future trends in both the basic research concerning these algorithms and their application to the elucidation, design and modelling of chemical and biochemical." } @article{Niesse_96, title = "Global geometry optimization of atomic clusters using a modified genetic algorithm in space-fixed coordinates", author = "J.A. Niesse and H.R. Mayne", journal ="Journal of Chemical Physics", volume ="105", number = "11", pages = "4700--4706", year = "1996", Abstract = "In a recent paper, Gregurick, Alexander, and Hartke [S. K. Gregurick, M. H. Alexander, and B. Hartke, J. Chem. Phys. 104, 2684 (1996)] proposed a global geometry optimization technique using a modified Genetic Algorithm approach for clusters. They refer to their technique as a deterministic/stochastic genetic algorithm (DS-GA). In this technique, the stochastic part is a traditional GA, with the manipulations being carried out on binary-coded internal coordinates (atom-atom distances). The deterministic aspect of their method is the inclusion of a coarse gradient descent calculation on each geometry. This step avoids spending a large amount of computer time searching parts of the configuration space which correspond to high-energy geometries. Their tests of the technique show it is vastly more efficient than searches without this local minimization. They report geometries for clusters of up to n = 29 Ar atoms, and find that their computer time scales as O(n(4.5)). In this work, we have recast the genetic algorithm optimization in space-fixed Cartesian coordinates, which scale much more favorably than internal coordinates for large clusters. We introduce genetic operators suited for real (base-10) variables. We find convergence for clusters up to n = 55. Furthermore, our algorithm scales as O(n(3.3)). It is concluded that genetic algorithm optimization in nonseparable real variables is not only viable, but numerically superior to that in internal candidates for atomic cluster calculations. Furthermore, no special choice of variable need be made for different cluster types; real Cartesian variables are readily portable, and can be used for atomic and molecular clusters with no extra effort." } @article{Deaven_95, title = "Molecular-Geometry Optimization With A Genetic Algorithm", author = "D.M. Deaven and K.O. Ho", journal = "Physical Review Letters", volume = "75", number = "2", pages = "288--291", year ="1995" } @article{Maddox_95, title = "Genetics Helping Molecular-Dynamics", author = "J. Maddox", journal = "Nature", volume = "376", number = "6537", pages = "209--209", year = "1995" } @article{Deaven_96, title ="Structural optimization of {Lennard-Jones} clusters by a genetic algorithm", author ="D.M. Deaven and N. Tit and J.R. Morris and K.M. Ho", journal ="Chemical Physics Letters", volume ="256", number ="1--2", pages ="195--200", year ="1996", Abstract = "We use a newly-developed genetic algorithm to determine the lowest energy atomic configurations of 2-100 atoms in the {Lennard-Jones} potential. Our method, which contains no bias to specific symmetries, yields structures which are identical to or are lower in energy than all previously published structures." } @article{Morris_96, title="Genetic-Algorithm Energy Minimization For Point Charges On A Sphere", author ="J.R. Morris and D.M. Deaven and K.M. Ho", journal ="Physical Review B-Condensed Matter", volume ="53", number ="4", pages ="R1740--R1743", year ="1996", Abstract ="We Demonstrate That A Recently Developed Approach For Optimizing Atomic Structures Is Very Effective For Attacking The Thomson Problem of Finding The Lowest-Energy Configuration of N Point Charges On A Unit Sphere. Our Approach Uses A Genetic Algorithm, Combined With A ''Cut And Paste'' Scheme of Mating, That Efficiently Explores The Different Low-Energy Structures. Not Only Have We Reproduced The Known Results For 10 Less Than Or Equal To N Less Than Or Equal To 132 , This Approach Has Allowed Us To Extend The Calculation For All N Less Than Or Equal To 200. This Has Allowed Us To Identify Series of ''Magic'' Numbers, Where The lowest-Energy Structures Are Particularly Stable. Most of These Structures Are Icosahedral, But We Also Find Low-Energy Structures That Deviate From Icosahedral Symmetry." } @article{Wacker_98, title ="Structures of medium-sized silicon clusters", author ="K.M. Ho and A.A. Shvartsburg and B.C. Pan and Z.Y. Lu and C.Z. Wang and J.G. Wacker and J.L. Fye and M.F. Jarrold", journal = "Nature", volume ="392", number ="6676", pages ="582--585", year ="1998", Abstract = "Silicon is the most important semiconducting material in the microelectronics industry, If current miniaturization trends continue, minimum device features will soon approach the size of atomic clusters. In this size regime, the structure and properties of materials often differ dramatically from those of the hulk, An enormous effort has been devoted to determining the structures of free silicon clusters(1-22). Although progress has been made for Si-n with n < 8, theoretical predictions for larger clusters are contradictory(2-22) and none enjoy any compelling experimental support, Here we report geometries calculated for medium-sized silicon clusters using an unbiased global search with a genetic algorithm. Ion mobilities(23) determined for these geometries by trajectory calculations are in excellent agreement,vith the values that we measure experimentally, The cluster geometries that we obtain do not correspond to fragments of the hulk, For n = 12-18 they are built on a structural motif consisting of a stack of Si-9 tricapped trigonal prisms, For n greater than or equal to 19, our calculations predict that near-spherical cage structures become the most stable, The transition to these more spherical geometries occurs in the measured mobilities for slightly larger clusters than in the calculations, possibly because of entropic effects." } @article{Pullan_97, title ="Structure prediction of benzene clusters using a genetic algorithm", author ="W.J. Pullan", journal ="Journal of Chemical Information and Computer Sciences", volume ="37", number ="6", pages = "1189--1193", year ="1997", Abstract = "This paper describes a real coded, parallel genetic algorithm implemented to find global minimum energy structures of clusters of benzene (C6H6) molecules. Starting from randomly generated structures, the genetic algorithm was able to find minimum energy structures for clusters of two to fifteen benzene molecules." } @article{Hobday_97, title="Optimisation of carbon cluster geometry using a genetic algorithm", author ="S. Hobday and R. Smith", journal ="Journal of The Chemical Society-Faraday Transactions", volume ="93", number ="22", pages ="3919--3926", year ="1997", Abstract = "A genetic algorithm (GA) based global optimisation procedure has been developed and used to find the most stable configurations of small carbon clusters. The CA attempts to locate the set of atomic nuclei coordinates associated with the global minimum of the potential-energy function using an analogy to Darwinian natural selection. This algorithm uses a novel encoding scheme to evolve a population of cluster geometries towards a low-energy final state. Two semi-empirical many-body potential-energy functions have been encoded for carbon interactions. The binding energies and structural forms of carbon clusters between C-3 and C-60 are reported. It has been shown that the algorithm can determine structures with a lower energy than those previously published using more classical local optimisation procedures. The GA can also be used to predict the global minimal energy configuration of pairwise interaction potentials." } @article{Pucello_97, title="Search of molecular ground state via genetic algorithm: Implementation on a hybrid {SIMD-MIMD} platform", author = "N. Pucello and M. Rosati and G. D'Agostino and F. Pisacane and V. Rosato and M. Celino", journal = "International Journal of Modern Physics C", volume ="8", number ="2", pages ="239--252", year ="1997", abstract = "A genetic algorithm for the optimization of the ground-state structure of a metallic cluster has been developed and ported on a SIMD-MIMD parallel platform. The SIMD part of the parallel platform is represented by a Quadrics/APE100 consisting of 512 floating point units, while the MIMD part is formed by a cluster of workstations. The proposed algorithm is composed by a part where the genetic operators are applied to the elements of the population and a part which performs a further local relaxation and the fitness calculation via Molecular Dynamics. These parts have been implemented on the MIMD and on the SIMD part, respectively. Results have been compared to those generated by using Simulated Annealing" } %% Added by Peter Merz % Landscapes @article{Weinberger91b, author = "Edward D. Weinberger", title = "{Local Properties of Kauffman's N-k model: A tunably Rugged Enegy Landscape}", journal = "Physical Review A", volume = "44", number = "10", pages = "6399--6413", year = "1991", } @InProceedings{Wright32, author = "S. Wright", title = "{The Roles of Mutation, Inbreeding, Crossbreeding, and Selection in Evolution}", volume = "1", pages = "365", booktitle = "Proceedings of the Sixth Congress on Genetics", year = "1932", } @article{Weinberger91, author = "Edward D. Weinberger", title = "{Correlated and Uncorrelated Fitness Landscapes and How to Tell the Difference}", journal = "Biological Cybernetics", volume = "63", pages = "325--336", year = "1990", } @Article{Reeves97, author = "C. R. Reeves", title = "{Landscapes, Operators and Heuristic Search}", journal = "Annals of Operations Research", year = "1998", note = "To appear.", } @article{Stadler:92d, author = "Peter F. Stadler", title = "{Correlation in Landscapes of Combinatorial Optimization Problems}", journal = {Europhys.\ Lett.}, volume = {20}, pages = {479-482}, year = {1992}, } @inproceedings{Stadler:95c, author = {Peter F. Stadler}, title = "{Towards a Theory of Landscapes}", pages = {77-163}, editor = {R. {Lop{\'e}z-Pe{\~n}a} and R. Capovilla and R. Garc{\'\i}a-Pelayo and H. Waelbroeck and F. Zertuche}, booktitle = {Complex Systems and Binary Networks}, publisher = {Springer Verlag}, address = {Berlin, New York}, year = {1995}, series = {Lecture Notes in Physics}, volume = {461}, note = {SFI preprint 95-03-030}, } @article{Stadler:96b, author = {Peter F. Stadler}, title = "{Landscapes and their Correlation Functions}", journal = {J.\ Math.\ Chem.}, pages = {1-45}, volume = {20}, year = {1996}, note = {SFI preprint 95-07-067}, } @Article{Angel98, author = "E. Angel and V. Zissimopoulos", title = "{Autocorrelation Coefficient for the Graph Bipartitioning Problem}", journal = "Theoretical Computer Science", volume = "191", pages = "229--243", year = "1998", } @Article{Davidor90b, key = "Davidor", author = "Yuval Davidor", title = "{Epistasis Variance: Suitability of a Representation to Genetic Algorithms}", journal = "Complex Systems", pages = "369--383", volume = "4", number = "4", year = "1990", } @Book{Kauffman93, author = "S. A. Kauffman", title = "The Origins of Order: Self-Organization and Selection in Evolution.", publisher = "Oxford University Press", year = "1993", keywords = "self organization, organisation, OUP, GA, genetic algorithm, chaos, text, book, emergent", abstract = "via enews", } @Book{Englemore_Morgan_88, author = "R. Englemore and T. Morgan (eds.)", title = "Blackboard Systems", publisher = "Addison-Wesley", year ="1988" } @Article{Kauffman87b, author = "S. A. Kauffman and S. Levin", title = "{Towards a General Theory of Adaptive Walks on Rugged Landscapes}", journal = "Journal of Theoretical Biology", volume = "128", pages = "11--45", year = "1987", } @InProceedings{JonesForrest95, author = "T. Jones and S. Forrest", title = "{Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms}", pages = "184--192", editor = "L. J. Eshelman", booktitle = "Proceedings of the 6th International Conference on Genetic Algorithms", publisher = "Morgan Kaufmann", year = "1995", } % EA books @Book{Holland75:book, author = "J. Holland", title = "Adaptation in Natural and Artificial Systems.", publisher = "University of Michigan Press", year = "1975", } @Book{Rechenberg73:book, author = "I. Rechenberg", title = "Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution", publisher = "Frommann-Holzboog", year = "1973", address = "Stuttgart", } @Book{Fogel66:book, author = "L. J. Fogel and A. J. Owens and M. J. Walsh", title = "Artificial Intelligence through Simulated Evolution", publisher = "John Wiley \& Sons", address = "New York", year = "1966", } % additional references @Article{LinKin73, author = "S. Lin and B. Kernighan", title = "{An Effective Heuristic Algorithm for the Traveling Salesman Problem}", journal = "Operations Research", volume = "21", pages = "498--516", year = "1973", } @Article{FredmanJohnson95, author = "M. L. Fredman and D. S. Johnson and L. A. McGeoch and G. Ostheimer", title = "{Data Structures for Traveling Salesmen}", journal = "Journal of Algorithms", volume = "18", year = "1995", pages = "432--479" } @InCollection{Johnson97, author = "D. S. Johnson and L. A. McGeoch", title = "{The Traveling Salesman Problem: A Case Study}", booktitle = "Local Search in Combinatorial Optimization", editor = "E. H. L. Aarts and J. K. Lenstra", publisher = "Wiley and Sons, New York", pages = "215--310", year = "1997", } @techreport{Boese95, author = "K.D. Boese", title = "{Cost versus Distance in the Traveling Salesman Problem}", number = "TR-950018", institution = "UCLA CS Department", year = 1995 } @Book{Lawler:tour, author = "E. L. Lawler and J. K. Lenstra and A. H. G. {Rinnooy Kan} and D. B. Shmoys", title = "{The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization}", year = "1985", address = "New York", publisher = "Wiley and Sons", } @book{Reinelt94, author = "Gerhard Reinelt", title = "{The Traveling Salesman: Computational Solutions for TSP Applications}", volume = "840", series = "Lecture Notes in Computer Science", publisher = "Springer-Verlag, Berlin, Germany", year = 1994 } @Article{KernighanLin72, author = "B. Kernighan and S. Lin", title = "{An Efficient Heuristic Procedure for Partitioning Graphs}", journal = "Bell Systems Journal", volume = "49", pages = "291--307", year = "1972", } @InProceedings{Battiti97, author = "R. Battiti and A. Bertossi", title = "{Differential Greedy for the 0--1 Equicut Problem}", booktitle = "Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location", editor = "D.Z. Du and P.M. Pardalos", publisher = "American Mathematical Society", year = "1998", note = "to appear.", } @InProceedings{Fiduccia82, author = "C. M. Fiduccia and R. M. Mattheyses", title = "{A Linear-Time Heuristic for Improving Network Partitions}", booktitle = "Proceedings of the 19th ACM/IEEE Design Automation Conference DAC 82", pages = "175--181", year = "1982", } @InProceedings{Cung97, author = "Van-Dat Cung and Thierry Mautor and Philippe Michelon and Andr\'ea Tavares", title = "{A Scatter Search Based Approach for the Quadratic Assignment Problem}", editor = {Thomas B\"ack and Zbigniew Michalewicz and Xin Yao}, pages = "165--170", booktitle = "Proceedings of the 1997 IEEE International Conference on Evolutionary Computation (ICEC)", year = "1997", publisher = "IEEE Press", address = "Indianapolis, USA", } @TechReport{pmfs98:tr01, author = "P. Merz and B. Freisleben", title = "{Fitness Landscapes, Memetic Algorithms and Greedy Operators for Graph Bi-Partitioning}", institution = "University of Siegen, Germany", number = "98-01", year = "1998", note = "to appear in {Evolutionary Computation}" } @book{GareyJohnson79, author = "M. R. Garey and D. S. Johnson", title = "Computers and Intractability: A Guide to the Theory of NP-Completeness", publisher = "Freeman, New York", year = "1979" } @InProceedings{Slootmaekers_vanWulpen_Joosen_98, title = "Modelling genetic search agents with a concurrent object-oriented language", author = "R. Slootmaekers and H. Van Wulpen and W. Joosen", booktitle = "Proceedings of High-Performance Computing and Networking: International Conference and Exhibition, Amsterdam, The Netherlands , April 21-23, 1998 ", editor = "P. Sloot and M. Bubak and B. Hertzberger", pages = "843--853", series = "Lecture Notes in Computer Science", year = "1998", publisher = "Springer, Berlin", volume = "1401", abstract = "In this paper, we present a multi-agent approach to modelling genetic algorithms (GAs). GAs let a population of chromosomes evolve in order to optimise a given objective function. We model chromosomes as autonomous agents, that are themselves responsible for applying the genetic operators. Moreover, they are further enhanced by adding local search and adaptive behaviour. These extensions lead to the concept of Genetic Search Agents. We illustrate the expressive power of the Correlate language and runtime system in which we implemented our agents. Experiments with the Travelling Salesman Problem show the power of Genetic Search Agents, outperforming both distributed GAs and parallel local search." } %%% % % Added by Carlos Cotta % and Pablo Moscato (09/Aug/2000) % %% @article{Minsky_94, title = "Negative Expertise", author = "M. Minsky", journal = "International Journal of Expert Systems", volume = "7", number = "1", pages = "13--19", year = "1994" } @article{Johnson_Papadimitriou_Yannakakis_88, author = "D.S. Johnson and C.H. Papadimitriou and M. Yannakakis", title = "How easy is local search~?", journal = "Journal of Computers and System Sciences", volume = "37", year = "1988", pages = "79-100" } @Incollection{Yannakakis_LS_complexity_survey, author = "M. Yannakakis", title = "Computational Complexity", booktitle = "Local Search in Combinatorial Optimization", year = "1997", pages = "19--55", editor = "E.H.L. Aarts and J.K. Lenstra", publisher = "Wiley, Chichester" } @book{Papadimitriou_Steiglitz_82, title = "Combinatorial Optimization: Algorithms and Complexity", author = "C.H. Papadimitriou and K. Steiglitz", publisher = "Prentice-Hall, Inc.", address = "Englewood Cliffs, New Jersey", year = "1982" } @article{Lin_65, title = "Computer Solutions of the Traveling Salesman Problem", author = "S. Lin", journal = "Bell System Technical Journal", volume = "10", number = "", pages = "2245--2269", year = "December 1965" } @techreport{Goldstein_Lesk_75, title = "Common Feature Techniques for Discrete Optimization", author = "A.J. Goldstein and A.B. Lesk", type = "Comp. Sci. Tech. Report", number = "27", institution = "Bell. Tel. Labs", year = "March 1975" } @book{Lewis_Papadimitriou_98, author = "H.R. Lewis and C.H. Papadimitriou", title = "Elements of the Theory of Computation", publisher = "Prentice-Hall, Inc.", address = "Upper Saddle River, New Jersey", year = "1998" } @Incollection{Johnson_McGeoch_97, author = "D.S. Johnson and L.A. McGeoch", title = "The traveling salesman problem: A case study", booktitle = "Local Search in Combinatorial Optimization", year = "1997", pages = "215--310", editor = "E.H.L. Aarts and J.K. Lenstra", publisher = "Wiley, Chichester" } @inproceedings{Steiglitz_Weiner_68, title = "Some Improved Algorithms for Computer Solution of the Traveling Salesman Problem", author = "K. Steiglitz and P. Weiner", booktitle = "Proceedings of the Sixth Allerton Conference on Circuit and System Theory", address = "Urbana, Illinois", pages = "814--821", year = "1968" } @article{Kirkpatrick_Toulouse_85, title = "Configuration Space analysis of traveling salesman problems", author = "S. Kirkpatrick and G. Toulouse", journal = "J. Physique", volume = "46", pages = "1277--1292", year ="1985" } @Book{Baeck96, title = {Evolutionary Algorithms in Theory and Practice}, author = {B\"ack, Th.}, year = {1996}, publisher = {Oxford University Press}, address = {New York} } @InCollection{Cotta98a, title = {Utilising Dynastically Optimal Forma Recombination in Hybrid Genetic Algorithms}, author = {Cotta, C. and Alba, E. and Troya, J.M.}, editor = {Eiben, A.E. and B\"ack, Th. and Schoenauer, M. and Schwefel, H.-P.}, booktitle = {Parallel Problem Solving From Nature V}, year = {1998}, series = {Lecture Notes in Computer Science}, volume = {1498}, publisher = {Springer-Verlag}, address = {Berlin}, pages = {305--314} } @InProceedings{Cotta99c, title = {Stochastic Reverse Hillclimbing and Iterated Local Search}, author = {Cotta, C. and Alba, E. and Troya, J.M.}, booktitle = {Proceedings of the 1999 Congress on Evolutionary Computation}, year = {1999}, pages = {1558--1565}, publisher = {IEEE}, address = {Washington D.C.} } @article{Cotta98b, author = {Cotta, C.}, title = {A Study of Hybridisation Techniques and their Application to the Design of Evolutionary Algorithms}, journal = {AI Communications}, year = {1998}, volume = {11}, number = {3-4}, pages = {223-224} } @InProceedings{Cotta_Troya97, title = {A Hybrid Genetic Algorithm for the 0-1 Multiple Knapsack Problem}, author = {Cotta, C. and Troya, J.M.}, editor = {Smith, G.D. and Steele, N.C. and Albrecht, R.F.}, booktitle = {Artificial Neural Nets and Genetic Algorithms 3}, year = {1998}, pages = {251--255}, publisher = {Springer-Verlag}, address = {Wien New York} } @InProceedings{Cotta_Troya00a, title = {On the Influence of the Representation Granularity in Heuristic Forma Recombination}, author = {Cotta, C. and Troya, J.M.}, booktitle = {ACM Symposium on Applied Computing 2000}, year = {2000}, editor = {Carroll, J. and Damiani, E. and Haddad, H. and Oppenheim, D.}, pages = {433--439}, publisher = {ACM Press} } @InProceedings{Cotta_Troya00b, author = {Cotta, C. and Troya, J.M.}, title = {Using a Hybrid Evolutionary­-{A}$^*$ Approach for Learning Reactive Behaviors}, booktitle = {Real-World Applications of Evolutionary Computation}, year = {2000}, editor = {Cagnoni, S. and others}, volume = {1803}, series = {Lecture Notes in Computer Science}, pages = {347--356}, address = {Edinburgh}, publisher_address = {Berlin}, month = {15-16 } # apr, organisation = {EvoNet}, publisher = {Springer-Verlag}, keywords = {genetic algorithms, evolutionary robotics}, ISBN = {}, } @InProceedings{Cobb_Grefenstette93, title = {Genetic Algorithms for Tracking Changing Environments}, author = {Cobb, H.G. and Grefenstette, J.J.}, editor = {Forrest, S.}, booktitle = {Proceedings of the Fifth International Conference on Genetic Algorithms}, year = {1993}, pages = {529--530}, publisher = {Morgan Kaufmann}, address = {San Mateo, CA} } @BOOK{Dawkins76, author = {Dawkins, R.}, title = {The Selfish Gene}, publisher = {Clarendon Press}, year = {1976}, address = {Oxford}, } @article{Wolpert_Macready_NFL_97, author = {Wolpert, D.H. and Macready, W.G.}, title = {No Free Lunch Theorems for Optimization}, journal = {IEEE Transactions on Evolutionary Computation}, volume = {1(1)}, pages = {67--82}, year = {1997} } @InProceedings{Reynolds94, title = {An Introduction to Cultural Algorithms}, author = {Reynolds, R. G.}, booktitle = {Proceedings of the Third Annual conference on Evolutionary Programming}, editor = {Sebalk, A.V. and Fogel, L.J.}, year = {1994}, address = {River Edge NJ}, publisher = {World Scientific Publishing}, pages = {131--139} } @Book{Rechenberg73, author = {Rechenberg, I.}, title = {Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution}, year = {1973}, publisher = {Frommann-Holzboog Verlag}, address = {Stuttgart} } @article{Radcliffe_algebra_94b, author = {Radcliffe, N.J.}, title = {The Algebra of Genetic Algorithms}, journal = {Annals of Mathematics and Artificial Intelligence}, volume = {10}, pages = {339--384}, year = {1994}, abstract = {A rigorous formulation of the generalisation of schema analysis known as forma analysis is presented. This is shown to provide a direct mechanism for harnessing knowledge about a search space, codified through the imposition of equivalence relations over that space, to generate a genetic representation and operators. It is shown that a single characterisation of a space leads to a unique genetic representation, and the kinds of representations that are possible are classified and discussed. A relatively new operator, called {\em random assorting recombination\/}, is defined rigorously and is shown to be, in an important sense, a universal recombination operator.} } @InProceedings{Hart_Belew_hard_91, title = {Optimizing an Arbitrary Function is Hard for the Genetic Algorithm}, author = {Hart, W.E. and Belew, R.K.}, editor = {Belew, R.K. and Booker, L.B.}, booktitle = {Proceedings of the Fourth International Conference on Genetic Algorithms}, year = 1991, publisher = {Morgan Kaufmann}, pages = {190-195}, address = {San Mateo CA} } @InProceedings{Hulin97, title = {An Optimal Stop Criterion for Genetic Algorithms: A Bayesian Approach}, author = {Hulin, M.}, editor = {B\"ack, Th.}, booktitle = {Proceedings of the Seventh International Conference on Genetic Algorithms}, year = {1997}, pages = {135--143}, publisher = {Morgan Kaufmann}, address = {San Mateo, CA} } @Book{Davis_handbook_91, author = {Davis, L.}, title = {Handbook of Genetic Algorithms}, year = {1991}, publisher = {Van Nostrand Reinhold Computer Library}, address = {New York} } @phdthesis{Jones95, author = {Jones, T.C.}, title = {Evolutionary Algorithms, Fitness Landscapes and Search}, year = {1995}, school = {University of New Mexico} } @InProceedings{Syswerda89, title = {Uniform Crossover in Genetic Algorithms}, author = {Syswerda, G.}, editor = {Schaffer, J.D.}, booktitle = {Proceedings of the Third International Conference on Genetic Algorithms}, year = {1989}, pages = {2--9}, publisher = {Morgan Kaufmann}, address = {San Mateo, CA} } @InProceedings{Nagata_Kobayashi_97, title = {Edge Assembly Crossover: A High-power Genetic Algorithm for the Traveling Salesman Problem}, author = "Y. Nagata and Sh. Kobayashi", editor = {B\"ack, Th.}, booktitle = "Proceedings of the Seventh International Conference on Genetic Algorithms, East Lansing, EUA", year = {1997}, pages = {450--457}, publisher = {Morgan Kaufmann}, address = {San Mateo, CA} } @article{Schwefel84, author = {Schwefel, H.-P.}, title = {Evolution Strategies: A Family of Non-Linear Optimization Techniques Based on Imitating Some Principles of Natural Evolution}, journal = {Annals of Operations Research}, volume = {1}, pages = {165--167}, year = {1984} } @InProceedings{Davidor_Ben-Kiki92, title = {The Interplay among the Genetic Algorithm Operators: Information Theory Tools used in a Holistic Way}, author = {Davidor, Y. and Ben-Kiki, O.}, editor = {M\"anner, R. and Manderick, B.}, booktitle = {Parallel Problem Solving From Nature II}, year = {1992}, publisher = {Elsevier Science Publishers B.V.}, pages = {75--84}, address = {Amsterdam} } @Article{Merz_Freisleben_evocomp_00, title = {Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning}, author = {Merz, P. and Freisleben, B.}, journal = {Evolutionary Computation}, volume = {8}, number = {1}, pages = {61--91}, year = {2000} } @InProceedings{Ran96, title = {Automatic timetabling in practice}, author = {Rankin, R.C.}, booktitle = {Practice and Theory of Automated Timetabling. First International Conference. Selected Papers}, publisher = {Springer-Verlag}, address = {Berlin}, pages = {266--279}, year = {1996} } @InProceedings{CG96, title = {Parallel machine scheduling problems using memetic algorithms}, author = {Cheng, R. and Gen, M.}, booktitle = {1996 IEEE International Conference on Systems, Man and Cybernetics. Information Intelligence and Systems}, publisher = {IEEE}, address = {New York, NY}, year = {1996}, volume = {4}, pages = {2665--2670}, } @InProceedings{BS99, title = {A multi-stage approach for the thermal generator maintenance scheduling problem}, author = {Burke, E.K. and Smith, A.J.}, booktitle = {Proceedings of the 1999 Congress on Evolutionary Computation}, year = {1999}, pages = {1085--1092}, publisher = {IEEE}, address = {Washington D.C.} } @Article{PWHP99, title = {The application of evolutionary and maximum entropy algorithms to photoelastic spectral analysis}, author = {Pacey, M.N. and Wang, X.Z. and Haake, S.J. and Patterson, E.A.}, journal = {Experimental Mechanics}, volume = {39}, number = {4}, pages = {265--273}, year = {1999}, } @InProceedings{Osm95, title = {Hybrid and distributed genetic algorithms for motion control}, author = {Osmera, P.}, editor = {Chundy, V. and Kurekova, E.}, booktitle = {Proceedings of the Fourth International Symposium on Measurement and Control in Robotics}, pages = {297--300}, year = {1995}, } @Article{MIT96, title = {Genetic algorithms for flowshop scheduling problems}, author = {Murata, T. and Ishibuchi, H. and Tanaka, H.}, journal = {Computers \& Industrial Engineering}, volume = {30}, number = {4}, pages = {1061--1071}, year = {1996}, } @InProceedings{MLGP96, title = {Hybrid genetic algorithms for minimization of a polypeptide specific energy model}, author = {Merkle, L.D. and Lamont, G.B. and Gates, G.H. Jr. and Pachter, R.}, booktitle = {Proceedings of 1996 IEEE International Conference on Evolutionary Computation}, publisher = {IEEE}, address = {New York, NY}, pages = {396--400}, year = {1996}, } @article{WY99, title = {Extracting fuzzy rules for system modeling using a hybrid of genetic algorithms and Kalman filter}, author = {Wang, L. and Yen, J.}, journal = {Fuzzy Sets and Systems}, volume = {101}, number = {3}, pages = {353--362}, year = {1999}, } @article{KM99, title = {Intelligent control of via formation by photosensitive {BCB} for {MCM-L/D} applications}, author = {Kim, T.S. and May, G.S.}, journal = {{IEEE} Transactions on Semiconductor Manufacturing}, volume = {12}, pages = {503--515}, year = {1999}, } @Article{HP99, title = {A genetic algorithm for a 2D industrial packing problem}, author = {Hopper, E. and Turton, B.}, journal = {Computers \& Industrial Engineering}, volume = {37}, number = {1-2}, pages = {375--378}, year = {1999}, } @Article{CGT99, title = {A tutorial survey of job-shop scheduling problems using genetic algorithms. II. Hybrid genetic search strategies}, author = {Cheng, R. and Gen, M. and Tsujimura, Y.}, journal = {Computers \& Industrial Engineering}, volume = {37}, number = {1-2}, pages = {51--55}, year = {1999}, } @article{Yeh99, title = {Hybrid genetic algorithms for optimization of truss structures}, author = {Yeh, I.C.}, journal = {Computer Aided Civil and Infrastructure Engineering}, volume = {14}, number = {3}, pages = {199--206}, year = {1999}, } @Article{CG98, title = {Hybrid genetic algorithms for a multiple-objective scheduling problem}, author = {Cavalieri, S. and Gaiardelli, P.}, journal = {Journal of Intelligent Manufacturing}, volume = {9}, number = {4}, pages = {361--367}, year = {1998}, } @Article{GML98, title = {Iterative improvement methods for a multiperiod network design problem}, author = {Garcia, B.L. and Mahey, P. and LeBlanc, L.J.}, journal = {European Journal of Operational Research}, volume = {110}, number = {1}, pages = {150--165}, year = {1998}, } @Article{KHN98, title = {Performance analysis for crossover operators of genetic algorithm}, author = {Katayama, K. and Hirabayashi, H. and Narihisa, H.}, journal = {Transactions of the Institute of Electronics, Information and Communication Engineers}, volume = {J81D-I}, number = {6}, pages = {639--650}, year = {1998}, } @article{SV97, title = {Hybrid genetic algorithms for constrained placement problems}, author = {Schnecke, V. and Vornberger, O.}, journal = {{IEEE} Transactions on Evolutionary Computation}, volume = {1}, number = {4}, pages = {266--277}, year = {1997}, } @Article{Mon96, title = {Hybrid genetic algorithms for timetabling}, author = {Monfroglio, A.}, journal = {International Journal of Intelligent Systems}, volume = {11}, number = {8}, pages = {477--523}, year = {1996}, } @Article{BM96, title = {Genetic algorithm and graph partitioning}, author = {Bui, T.N. and Moon, B.R.}, journal = {{IEEE} Transactions on Computers}, volume = {45}, number = {7}, pages = {841--855}, year = {1996}, } @Article{Mon96b, title = {Hybrid genetic algorithms for a rostering problem}, author = {Montfroglio, A.}, journal = {Software -- Practice and Experience}, volume = {26}, number = {7}, pages = {851--862}, year = {1996}, } @Article{Mon96c, title = {Timetabling through constrained heuristic search and genetic algorithms}, author = {Monfroglio, A.}, journal = {Software -- Practice and Experience}, volume = {26}, number = {3}, pages = {251--279}, year = {1996}, } @Article{Lee94, title = {Genetic algorithms for single machine job scheduling with common due date and symmetric penalties}, author = {Lee, C.Y.}, journal = {Journal of the Operations Research Society of Japan}, volume = {37}, number = {2}, pages = {83--95}, year = {1994}, } @InProceedings{MI94, title = {Performance evaluation of genetic algorithms for flowshop scheduling problems}, author = {Murata, T. and Ishibuchi, H.}, booktitle = {Proceedings of the First IEEE Conference on Evolutionary Computation}, publisher = {IEEE}, address = {New York, NY}, pages = {812--817}, volume = {2}, year = {1994} } @Article{NT94, title = {A genetic algorithm for the talent scheduling problem}, author = {Nordstrom, A.L. and Tufekci, S.}, journal = {Computers \& Operations-Research}, volume = {21}, number = {8}, pages = {927--940}, year = {1994}, } @Article{FX97, title = {A rolling horizon job shop rescheduling strategy in the dynamic environment}, author = {Fang, J. and Xi, Y.}, journal = {International Journal of Advanced Manufacturing Technology}, volume = {13}, number = {3}, pages = {227--232}, year = {1997} } @Article{Abd98, title = {A hybrid heuristic for the uncapacitated hub location problem}, author = {Abdinnour, H.S.}, journal = {European Journal of Operational Research}, volume = {106}, number = {2-3}, pages = {489--99}, year = {1998}, } @InProceedings{BD94, title = {OFDD based minimization of fixed polarity {Reed-Muller} expressions using hybrid genetic algorithms}, author = {Becker, B. and Drechsler, R.}, booktitle = {Proceedings IEEE International Conference on Computer Design: VLSI in Computers and Processor}, publisher = {IEEE}, pages = {106--110}, year = {1994}, address = {Los Alamitos, CA}, } @Article{KN-M99, title = {Genetic K-means algorithm}, author = {Krishna, K and Narasimha-Murty, M.}, journal = {{IEEE} Transactions on Systems, Man and Cybernetics, Part B (Cybernetics)}, volume = {29}, number = {3}, pages = {433--439}, year = {1999}, } @Article{Ost99, title = {Solving irregular econometric and mathematical optimization problems with a genetic hybrid algorithm}, author = {Ostermark, R.}, journal = {Computational Economics}, volume = {13}, number = {2}, pages = {103--115}, year = {1999}, } @Article{Ost99b, title = {Solving a nonlinear non-convex trim loss problem with a genetic hybrid algorithm}, author = {Ostermark, R.}, journal = {Computers \& Operations Research}, volume = {26}, number = {6}, pages = {623--635}, year = {1999}, } @Article{GC99, title = {Optimal design of the broadband stepped impedance transformer based on the hybrid genetic algorithm}, author = {Guotian, M. and Changhong, L.}, journal = {Journal of Xidian University}, volume = {26}, number = {1}, pages = {8--12}, year = {1999}, } @InProceedings{MW94, title = {Noisy function evaluation and the delta coding algorithm}, author = {Mathias, K.E. and Whitley, L.D.}, booktitle = {Proceedings of the SPIE--The International Society for Optical Engineering}, pages = {53--64}, year = {1994} } @article{AWM97, title = {Design of multilayered periodic strip gratings by genetic algorithms}, author = {Aygun, K. and Weile, D.S. and Michielssen, E.}, journal = {Microwave and Optical Technology Letters}, volume = {14}, number = {2}, pages = {81--85}, year = {1997}, } @InProceedings{HBMRF96, title = {Hybrid genetic algorithms applied to beam orientation in radiotherapy}, author = {Haas, O.C.L. and Burnham, K.J. and Mills, J.A. and Reeves, C.R. and Fisher, M.H.}, booktitle = {Fourth European Congress on Intelligent Techniques and Soft Computing Proceedings}, publisher = {Verlag Mainz}, address = {Aachen, Germany}, pages = {2050--2055}, volume = {3}, year = {1996}, } @InProceedings{LMW96, title = {Economic environmental dispatch made easy with hybrid genetic algorithms}, author = {Li, F. and Morgan, R. and Williams, D.}, booktitle = {Proceedings of the International Conference on Electrical Engineering}, publisher = {Int. Acad. Publishers}, address = {Beijing, China}, pages = {965--969}, volume = {2}, year = {1996}, } @InProceedings{BSB98, title = {A hybrid genetic algorithm for the vehicle routing problem with time windows}, author = {Berger J. and Salois, M. and Begin, R.}, editor = {Mercer, R.E. and Neufeld, E.}, booktitle = {Advances in Artificial Intelligence. 12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence}, publisher = {Springer-Verlag}, address = {Berlin}, pages = {114--127}, year = {1998}, } @InProceedings{KRT97, title = {Vector quantization using genetic K-means algorithm for image compression}, author = {Krishna, K. and Ramakrishnan, K.R. and Thathachar, M.A.L.}, booktitle = {1997 International Conference on Information, Communications and Signal Processing}, publisher = {IEEE}, address = {New York, NY}, pages = {1585--1587}, volume = {3}, year = {1997}, } @InProceedings{JH99, title = {Dynamic vehicle routing using hybrid genetic algorithms}, author = {Jih, W.R. and Hsu, Y.J.}, booktitle = {Proceedings of the 1999 Congress on Evolutionary Computation}, year = {1999}, publisher = {IEEE}, address = {Washington D.C.}, pages = {453--458}, } @InProceedings{Gri99, title = {Hybrid genetic algorithms for analogue network synthesis}, author = {Grimbleby, J.B.}, booktitle = {Proceedings of the 1999 Congress on Evolutionary Computation}, year = {1999}, publisher = {IEEE}, address = {Washington D.C.}, pages = {1781--1787}, } @InProceedings{QV98, title = {Hybrid genetic algorithms as tools for complex optimisation problems}, author = {Quagliarella, D. and Vicini, A.}, editor = {Blonda, P. and Castellano, M. and Petrosino, A.}, booktitle = {New Trends in Fuzzy Logic II. Proceedings of the Second Italian Workshop on Fuzzy Logic}, publisher = {World Scientific}, address = {Singapore}, pages = {300--307}, year = {1998}, } @Article{GIY98, title = {Bicriteria transportation problem by hybrid genetic algorithm}, author = {Gen, M. and Ida, K. and Yinzhen, L.}, journal = {Computers \& Industrial Engineering}, volume = {35}, number = {1-2}, pages = {363--366}, year = {1998}, } @InProceedings{IK98, title = {Learning of neural networks with parallel hybrid GA using a royal road function}, author = {Ichimura, T. and Kuriyama, Y.}, booktitle = {1998 IEEE International Joint Conference on Neural Networks}, publisher = {IEEE}, address = {New York, NY}, pages = {1131--1136}, volume = {2}, year = {1998}, } @InProceedings{CTO97, title = {Time efficient and robust {3-D} brain image centering and realignment using hybrid genetic algorithm}, author = {Cadieux, S. and Tanizaki, N. and Okamura, T.}, booktitle = {Proceedings of the 36th SICE Annual Conference}, publisher = {IEEE}, pages = {1279--1284}, year = {1997}, } @Article{ADR-S98, title = {Service restoration in compensated distribution networks using a hybrid genetic algorithm}, author = {Augugliaro, A. and Dusonchet, L. and Riva-Sanseverino, E.}, journal = {Electric Power Systems Research}, volume = {46}, number = {1}, pages = {59--66}, year = {1998}, } @Article {HBM98, title = {Optimization of beam orientation in radiotherapy using planar geometry}, author = {Haas, O.C.L. and Burnham, K.J. and Mills, J.A.}, journal = {Physics in Medicine and Biology}, volume = {43}, number = {8}, pages = {2179--2193}, year = {1998}, } @Article {Bos98, title = {Aircraft conceptual design by genetic/gradient-guided optimization}, author = {Bos, A.H.W.}, journal = {Engineering Applications of Artificial Intelligence}, volume = {11}, number = {3}, pages = {377--382}, year = {1998}, } @Article{MWC99, title = {A hybrid simplex genetic algorithm for estimating geoacoustic parameters using matched-field inversion}, author = {Musil, M. and Wilmut, M.J. and Chapman, N.R.}, journal = {{IEEE} Journal of Oceanic Engineering}, volume = {24}, number = {3}, pages = {358--369}, year = {1999}, } @Article {WRWH99, title = {The impact of approximate evaluation on the performance of search algorithms for warehouse scheduling}, author = {Watson, J.P. and Rana, S. and Whitley, L.D. and Howe, A.E.}, journal = {Journal of Scheduling}, volume = {2}, number = {2}, pages = {79--98}, year = {1999}, } @Article{RHH99, title = {Volume estimation from sparse planar images using deformable models}, author = {Ruff, C.F. and Hughes, S.W. and Hawkes, D.J.}, journal = {Image and Vision Computing}, volume = {17}, number = {8}, pages = {559--565}, year = {1999}, } @Article{AC98, title = {Resolution of pattern recognition problems using a hybrid genetic/random neural network learning algorithm}, author = {Aguilar, J. and Colmenares, A.}, journal = {Pattern Analysis and Applications}, volume = {1}, number = {1}, pages = {52--61}, year = {1998}, } @Article{WM99, title = {Design of doubly periodic filter and polarizer structures using a hybridized genetic algorithm}, author = {Weile, D.S. and Michielssen, E.}, journal = {Radio Science}, volume = {34}, number = {1}, pages = {51--63}, year = {1999}, } @Article{Ozd99, title = {A genetic algorithm approach to a general category project scheduling problem}, author = {Ozdamar, L.}, journal = {IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews)}, volume = {29}, number = {1}, pages = {44--59}, year = {1999}, } @Article{MC98, title = {Identical parallel machine scheduling problem for minimizing the makespan using genetic algorithm combined with simulated annealing}, author = {Min, L. and Cheng, W.}, journal = {Chinese Journal of Electronics}, volume = {7}, number = {4}, pages = {317--321}, year = {1998}, } @Article{HI98, title = {Automatic design of frequency sampling filters by hybrid genetic algorithm techniques}, author = {Harris, S.P. and Ifeachor, E.C.}, journal = {IEEE Transactions on Signal Processing}, volume = {46}, number = {12}, pages = {3304--3314}, year = {1998}, } @Article{MM00, title = {A hybrid Hopfield network-genetic algorithm approach to optimal process plan selection}, author = {Ming, X.G. and Mak, K.L.}, journal = {International Journal of Production Research}, volume = {38}, number = {8}, pages = {1823--1839}, year = {2000}, } @Article{WK00, title = {A hybrid genetic algorithm for global solution of nondifferentiable nonlinear function}, author = {Wei, X. and Kangling, F.}, journal = {Control Theory \& Applications}, volume = {17}, number = {2}, pages = {180--183}, year = {2000}, } @Article{SCPN00, title = {Development of an intelligent technique for traffic network incident detection}, author = {Srinivasan, D. and Cheu, R.L. and Poh, Y.P. and Ng, A.K.C.}, journal = {Engineering Applications of Artificial Intelligence}, volume = {13}, number = {3}, pages = {311--322}, year = {2000}, } @Article{YKN99, title = {Estimation of impulse response of vocal tract using hybrid genetic algorithm-a case of only glottal source}, author = {Yoneyama, M. and Komori, H. and Nakamura, S.}, journal = {Journal of the Acoustical Society of Japan}, volume = {55}, number = {12}, pages = {821--830}, year = {1999}, } @Article{NCG00, title = {A continuous approach to the design of physical distribution systems}, author = {Novaes, A.G.N. and De-Cursi, J.E.S. and Graciolli, O.D.}, journal = {Computers \& Operations Research}, volume = {27}, number = {9}, pages = {877--893}, year = {2000}, } @Article{Ost99c, title = {A neuro-genetic algorithm for heteroskedastic time-series processes: empirical tests on global asset returns}, author = {Ostermark, R.}, journal = {Soft Computing}, volume = {3}, number = {4}, pages = {206--220}, year = {1999}, } @Article{MCPB00, title = {Hybrid genetic optimization and statistical model based approach for the classification of shadow shapes in sonar imagery}, author = {Mignotte, M. and Collet, C. and P\'erez, P. and Bouthemy, P.}, journal = {{IEEE} Transactions on Pattern Analysis and Machine Intelligence}, volume = {22}, number = {2}, pages = {129--141}, year = {2000}, } @Article{DJ00, title = {Solving large unconstrained multilevel lot-sizing problems using a hybrid genetic algorithm}, author = {Dellaert, N. and Jeunet, J.}, journal = {International Journal of Production Research}, volume = {38}, number = {5}, pages = {1083--1099}, year = {2000}, } @Article{KMV00, title = {A hybrid genetic approach for channel reuse in multiple access telecommunication networks}, author = {Kassotakis, I.E. and Markaki, M.E. and Vasilakos, A.V.}, journal = {{IEEE} Journal on Selected Areas in Communications}, volume = {18}, number = {2}, pages = {234--243}, year = {2000}, } @Article{MCML99, title = {A hybrid genetic algorithm for the single machine scheduling problem}, author = {Miller, D.M. and Chen, H.C. and Matson, J. and Liu, Q.}, journal = {Journal of Heuristics}, volume = {5}, number = {4}, pages = {437--454}, year = {1999}, } @Article{KR99, title = {Hybrid genetic algorithm for transmitter location in wireless networks}, author = {Krzanowski, R.M. and Raper, J.}, journal = {Computers, Environment and Urban Systems}, volume = {23}, number = {5}, pages = {359--382}, year = {1999}, } @Article{UGSFL99, title = {A hybrid genetic algorithm for optimal reactive power planning based upon successive linear programming}, author = {Urdaneta, A.J. and G\'omez, J.F. and Sorrentino, E. and Flores, L. and D\'{\i}az, R.}, journal = {{IEEE} Transactions on Power Systems}, volume = {14}, number = {4}, pages = {1292--1298}, year = {1999}, } @Article{H-ABM99, title = {A hybrid genetic/optimization algorithm for a task allocation problem}, author = {Hadj-Alouane, A.B. and Bean, J.C. and Murty, K.G.}, journal = {Journal of Scheduling}, volume = {2}, number = {4}, year = {1999}, } @Article{WC99, title = {A hybrid genetic algorithm for function optimization}, author = {Wei, P. and Cheng, L.X.}, journal = {Journal of Software}, volume = {10}, number = {8}, pages = {819--823}, year = {1999}, } @InCollection{BH91, author = {B\"ack, T. and Hoffmeister, F.}, title = {Adaptive Search by Evolutionary Algorithms}, booktitle = {Models of Selforganization in Complex Systems}, year = {1991}, editor = {Ebeling, W. and Peschel, M. and Weidlich, W.}, pages = {17--21}, series = {Mathematical Research}, number = {64}, publisher = {Akademie-Verlag}, } @InProceedings{CBFR99, author = {Crain, T. and Bishop, R. and Fowler, W. and Rock, K.}, title = {Optimal Interplanetary Trajectory Design Via Hybrid Genetic Algorithm/Recursive Quadratic Program Search}, booktitle = {Ninth AAS/AIAA Space Flight Mechanics Meeting}, year = {1999}, editor = {}, pages = {99-133}, address = {Breckenridge CO}, publisher = {}, } @article{Ersoy_Panwar93, author = {Ersoy, C. and Panwar, S.S.}, title = {Topological design of interconnected {LAN/MAN} networks}, journal = {IEEE Journal on Selected Areas in Communications}, volume = {11}, number = {8}, pages = {1172--1182}, year = {1993} } @InProceedings{Gottlieb_Kruse00, title = {Selection in Evolutionary Algorithms for the Traveling Salesman Problem}, author = {Gottlieb, J. and Kruse, T.}, booktitle = {ACM Symposium on Applied Computing 2000}, year = {2000}, editor = {Carroll, J. and Damiani, E. and Haddad, H. and Oppenheim, D.}, pages = {415--421}, publisher = {ACM Press} } @InProceedings{Gottlieb00, title = {Permutation-Based Evolutionary Algorithms for Multidimensional Knapsack Problems}, author = {Gottlieb, J.}, booktitle = {ACM Symposium on Applied Computing 2000}, year = {2000}, editor = {Carroll, J. and Damiani, E. and Haddad, H. and Oppenheim, D.}, pages = {408--414}, publisher = {ACM Press} } @Incollection {Karp72, booktitle = {Complexity of Computer Computations}, year = {1972}, title = {Reducibility among combinatorial problems}, pages = {85--103}, author = {Karp, R.M.}, editor = {Miller, R.E. and Thatcher, J.W.}, publisher = {Plenum}, address = {New York NY} } @article{Lia00, author = {Liaw, C.F.}, title = {A hybrid genetic algorithm for the open shop scheduling problem}, journal = {European Journal of Oprational Research}, volume = {124}, number = {1}, pages = {28--42}, year = {2000} } @book{Sait_Youssef95, author = {Sait, S.M. and Youssef, H.}, title = {{VLSI} Design Automation: Theory and Practice}, publisher = {McGraw-Hill Book Co. (copublished by IEEE)}, address = {Europe}, year = {2000} } @InCollection{Surry_Radcliffe96, title = {Inoculation to Initialise Evolutionary Search}, author = {Surry, P.D. and Radcliffe, N.J.}, booktitle = {Evolutionary Computing: AISB Workshop}, editor = {Fogarty, T.C.}, year = {1996}, series = {Lecture Notes in Computer Science}, number = {1143}, pages = {269--285}, publisher = {Springer-Verlag}, } @InProceedings{Louis_MVRP99, title = {Multiple Vehicle routing with Time Windows Using Genetic Algorithms}, author = {Louis, S.J. and Yin, X. and Yuan, Z.Y.}, booktitle = {Proceedings of the 1999 Congress on Evolutionary Computation}, year = {1999}, pages = {1804--1808}, publisher = {IEEE Neural Network Council - Evolutionary Programming Society - Institution of Electrical Engineers}, address = {Washington D.C.} } @InProceedings{icga87*108, author = "D. Whitley", title = "Using reproductive evaluation to improve genetic search and heuristic discovery", pages = "108--115", ISBN = "0-8058-0159-6", editor = "Grefenstette, J.J.", booktitle = "Proceedings of the Second International Conference on Genetic Algorithms and their Applications", address = "Cambridge, MA", month = jul, year = "1987", publisher = "Lawrence Erlbaum Associates", } @InProceedings{BrHuSp89, author = "D. Brown and C. Huntley and A. Spillane", editor = "J. Schaffer", title = "A {P}arallel {G}enetic {H}euristic for the {Q}uadratic {A}ssignment { P}roblem", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", year = "1989", publisher = "Morgan Kaufmann", pages = "406--415", } @Article{Wehrens93, author = "R. Wehrens and C. Lucasius and L. Buydens and G. Kateman", title = "{HIPS}, {A} Hybrid self-adapting expert system for nuclear magnetic resonance spectrum interpretation using genetic algorithms", journal = "Analytica Chimica ACTA", year = "1993", volume = "277", number = "2", pages = "313--324", month = may, } @InProceedings{TopchyAPLe1996a, author = "A.P. Topchy and O.A. Lebedko and V.V. Miagkikh", booktitle = "Proceedings of International Conference on Evolutionary Computation and its Applications", title = "Fast Learning in Multilayered Networks by means of Hybrid Evolutionary and Gradient Algorithms", year = "1996", abstract-url = "http://web.cps.msu.edu/~miagkikh/web/6.ASC", url = "http://web.cps.msu.edu/~miagkikh/web/6.ps.gz", keywords = "genetic algorithms, neural networks, evolutionary programming, cooperative evolution", month = jun, pages = "390--398", scope = "learn", } @InProceedings{icga97*489, author = "E. Ramat and G. Venturini and C. Lente and M. Slimane", title = "Solving the Multiple Resource Constrained Project Scheduling Problem with a Hybrid Genetic Algorithm", pages = "489--496", ISBN = "1-55860-487-1", editor = "B{\"a}ck, Th.", booktitle = "Proceedings of the Seventh International Conference on Genetic Algorithms", publisher = "Morgan Kaufmann", address = "San Francisco CA", year = "1997" } @Article{yao93evolutionary, author = "Yao, X.", title = "Evolutionary Artificial Neural Networks", journal = "Int. Journal of Neural Systems", year = "1993", volume = "4", number = "3", pages = "203--222", month = sep, class = "nn, learning, genetic, survey", abstract = "Combinations of NNs with evolutionary search procedures, e.g. genetic algorithms. 3 levels of evolution: of connection weights, of topology, of learning rule. Discusses representation issues/problems, GA vs. gradient search, hybrids, developmental rule representation, fractal representation, node-centered representation, evolution of transfer functions. Large bibliography (137 titles)", notes = "^^", } @InProceedings{Rei00, title = {Simulation if Imprecise Ordinary Differential Equations Using Evolutionary Algorithms}, author = {Reich, C.}, booktitle = {ACM Symposium on Applied Computing 2000}, year = {2000}, editor = {Carroll, J. and Damiani, E. and Haddad, H. and Oppenheim, D.}, pages = {428--432}, publisher = {ACM Press} } @InProceedings{RJ00, title = {A weighted coding in a Genetic Algorithm for the Degree-constrained Minimum Spanning Tree Problem}, author = {Raidl, G.R. and Julstron, B.A.}, booktitle = {ACM Symposium on Applied Computing 2000}, year = {2000}, editor = {Carroll, J. and Damiani, E. and Haddad, H. and Oppenheim, D.}, pages = {440--445}, publisher = {ACM Press} } @InCollection{RRCT98, title = {An Evolutionary and Local Search Algorithm for Planning Two Manipulators Motion}, author = {Ridao, M.A. and Riquelme, J. and Camacho, E.F. and Toro, M.}, editor = {Del Pobil, A.P. and Mira, J. and Ali, M.}, booktitle = {Tasks and Methods in Applied Artificial Intelligence}, year = {1998}, series = {Lecture Notes in Computer Science}, volume = {1416}, publisher = {Springer-Verlag}, address = {Berlin Heidelberg}, pages = {105-114} } @Article{XZ97, author = {Xiao, J. and Zhang, L.}, title = {Adaptive Evolutionary Planner/Navigator for Mobile Robots}, journal = {{IEEE} Transactions on Evolutionary Computation}, year = {1997}, volume = {1}, number = {1}, pages = {18--28}, } @Article{Boldrin_Saffiotti_99, author = {L. Boldrin and A. Saffiotti}, title = {A modal logic for merging partial belief of multiple reasoners}, journal = {Journal of Logic and Computation}, year = 1999, volume = 9, number = 1, pages = {81--103}, note = {Online at http://www.aass.oru.se/$\sim$asaffio/} } @InProceedings{CZ99, title = {Hybridisation of Neural Networks and Genetic Algorithms for Time-Optimal Control}, author = {Chaiyaratana, N. and Zalzala, A.M.S.}, booktitle = {Proceedings of the 1999 Congress on Evolutionary Computation}, year = {1999}, pages = {389--396}, publisher = {IEEE}, address = {Washington D.C.} } @InProceedings{PDG99, title = {Fuzzy-Genetic Algorithms and Mobile Robot Navigation Among static Obstacles}, author = {Pratihar, D.K. and Deb, K. and Ghosh, A.}, booktitle = {Proceedings of the 1999 Congress on Evolutionary Computation}, year = {1999}, pages = {327--334}, publisher = {IEEE}, address = {Washington D.C.} } @techreport{Lamma_Pereira_Riguzzi_MultiAgentLogic, author = {E.~Lamma and L. M.~Pereira and F.~Riguzzi}, title = {Multi-agent Logic Aided Lamarckian Learning}, year = {2000}, institution = {Dipartimento di Elettronica, Informatica e Sistemistica, University of Bologna (Italy)}, number = {DEIS-LIA-00-004}, note = {LIA Series no.~44, submitted for publication}, } @InProceedings{Walters_98, author = "T. Walters", title = "Repair and Brood Selection in the Traveling Salesman Problem", booktitle = "Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature, Amsterdam, The Netherlands", editor = "A.E. Eiben and T. Back and M. Schoenauer and H.-P. Schwefel", series = "Lecture Notes in Computer Science", volume = "1498", publisher = "Springer-Verlag", pages = "813--822", year = "1998" } @inproceedings{Knowles00telecomworkshop, author = "J.D. Knowles and D. W. Corne", title = "{M}ultiobjective {A}pproaches to the {A}daptive {D}istributed {D}atabase {M}anagement {P}roblem", booktitle = "Proceedings of the SAB/PPSN Workshops (Evolutionary Computation in Telecommunications Workshop", editor = "D. Corne", year = "2000" } @inproceedings{Knowles00cec, author = "J.D. Knowles and D. W. Corne", title = "M-{PAES}: {A} {M}emetic {A}lgorithm for {M}ultiobjective {O}ptimization", booktitle = "Proceedings of the 2000 Congress on Evolutionary Computation (CEC00)", publisher = "IEEE Press", address = {Piscataway, NJ}, pages = "325--332", year = "2000", note = "Nominated by CEC Program Committe to be extended and submitted to Knowledge and Information Systems (KAIS) Journal" } @misc{Knowles00patent, author = "J. Knowles and D. Corne", title = "{O}ptimisation {M}ethod", howpublished = "European Patent EP00305549.8", note = "Date filed: 30th June", info = "This is a patent (filed by Joshua Knowles' sponsors, BT Plc.,) of the {M-PAES} algorithm", year = "2000" } @inproceedings{Knowles00memeticwshop, author = "J.D. Knowles and D.W. Corne", title = "A {C}omparison of {D}iverse {A}proaches to {M}emetic {M}ultiobjective {C}ombinatorial {O}ptimization", editor = "Annie S. Wu", booktitle = "Proceedings of the 2000 Genetic and Evolutionary Computation Conference Workshop Program", pages = "103--108", year = "2000" } @inproceedings{Knowles00ppsn, author = "J.D. Knowles and D.W. Corne and M.J. Oates", title = "On the {A}ssessment of {M}ultiobjective {A}pproaches to the {A}daptive {D}istributed {M}anagement {P}roblem", booktitle = "Proceedings of the Sixth International Conference of Parallel Problem Solving From Nature (PPSN VI)", publisher = "Springer-Verlag", address = "Berlin", pages = "869--878", year = "2000" } @article{Knowles00bttj, author = "J.D. Knowles and M.J. Oates and D.W. Corne", title = "Advanced {M}ultiobjective {E}volutionary {A}lgorithms {A}pplied to two {P}roblems in {T}elecommunications", journal = "BT Technology Journal", volume = "18", number = "4", pages = "51--65", publisher = "Kluwer Academic Publishers", month = "October", year = "2000" } @misc{Knowles00kais, author = "J.D. Knowles and D. W. Corne", title = "{B}enchmarking a {N}ew {M}emetic {A}lgorithm {F}ramework for {P}areto {M}ultiobjective {O}ptimization", note = "Submitted to {\em Knowledge and Information Systems\/}", year = "2000" } @InProceedings{Hodgson_00cec, author = "R.J.W. Hodgson", title = "Memetic Algorithms and the Molecular Geometry Optimization Problem", booktitle = "Proceedings of the 2000 {C}ongress on {E}volutionary {C}omputation", pages = "625--632", year = "2000", address = "Piscataway, NJ", publisher = "IEEE Service Center" } @InProceedings{Merz_Freisleben_QAP_99, author = "P. Merz and B. Freisleben", title = "A comparion of {M}emetic {A}lgorithms, {T}abu {S}earch, and ant colonies for the quadratic assignment problem", booktitle = "Proceedings of the 1999 {C}ongress on {E}volutionary {C}omputation, Washington D.C.", pages = "2063--2070", year = "1999", address = "Piscataway, NJ", publisher = "IEEE Service Center" } @mastersthesis{Hartmann_mastersthesis_99, author = "John W. Hartmann", title = "Low-thrust Trajectory Optimization using Stochastic Optimization Methods", school = "Graduate College of the University of Illinois at Urbana-Champaign", organisation = "Department of Aeronautical and Astronautical Engineering, UIUC Dynamics, Control and Design Group ", address = "Urbana-Champaign, Illinois, USA", advisor = "Prof. Victoria Coverstone-Carroll", year = "1999" } @article{Tanaka_Yamada_99, title = "Solving Multiobjective Time Tabling Problem by Using Requests", author = "Masahiro Tanaka and Mari Yamada", journal = "Transactions of Systems, Control and Information", volume = "12", number = "2", year = "1999", pages = "90--97", abstract = "In this paper, the time tabling problem of schools is discussed where the teachers, preference of time slots for each lecture is considered. The teachers' preference and the students' wishes are aggregated into two objectives, and the problem is treated as the two objectives of the multicriteria optimization problem. The problem is solved by using the framework of multiobjective genetic algorithm. The primary difficulty of this problem is how to satisfy the constraints. Here this problem is solved by using the local search for each individual that does not satisfy the constraints, and the revised ones are used in the next generation." } @InProceedings{Franca_Mendes_Moscato_98SOBRAPO, author = "P.M. {Fran\c{c}a} and A.S. Mendes and P. Moscato", title = "{Algoritmos Mem\'eticos e o Sequenciamento em M\'aquina Simples com Setup Times e Restri\c{c}\~oes de Datas de Entrega}", booktitle = "{XXX SOBRAPO} - {Simp\'osio Brasileiro de Pesquisa Operacional, Curitiba, PR, Brazil, 25-27 de Novembro}", pages = "315--316", year ="1998", publisher = "{Sociedade Brasileira de Pesquisa Operacional}", note = "extended abstract" } @InProceedings{Holstein_Moscato_98SOBRAPO, author = "D. Holstein and P. Moscato", title = "{Um Algoritmo Mem\'etico que utiliza Busca Local Guiada: Estudo do caso no Problema do Caixeiro Viajante}", booktitle = "{XXX SOBRAPO} - {Simp\'osio Brasileiro de Pesquisa Operacional, Curitiba, PR, Brazil, 25-27 de Novembro}", pages = "341--342", year ="1998", publisher = "{Sociedade Brasileira de Pesquisa Operacional}", note = "extended abstract" } @InProceedings{Buriol_Franca_Mendes_Moscato_98SOBRAPO, author = "P.M. {Fran\c{c}a} and P. Moscato and F. {M\"uller} and A.S. Mendes and L.S. Buriol", title = "{O Projeto MemePool: Um Framework para Otimiza\c{c}\~ao Combinat\'oria}", booktitle = "{XXX SOBRAPO} - {Simp\'osio Brasileiro de Pesquisa Operacional, Curitiba, PR, Brazil, 25-27 de Novembro}", pages = "20--21", year ="1998", publisher = "{Sociedade Brasileira de Pesquisa Operacional}", note = "extended abstract" } @InProceedings{Berretta_Moscato_98SOBRAPO, author = "R.E. Berretta and P. Moscato", title = "{Una an\'alise da utiliza\c{c}\ao de algoritmos gen\'eticos no problema de parti\c{c}\~ao de n\'umeros}", booktitle = "{XXX SOBRAPO} - {Simp\'osio Brasileiro de Pesquisa Operacional, Curitiba, PR, Brazil, 25-27 de Novembro}", pages = "271--272", year ="1998", publisher = "{Sociedade Brasileira de Pesquisa Operacional}", note = "extended abstract" } @InProceedings{Buriol_Franca_Moscato_99SOBRAPO, author = "L.S. Buriol and P.M. {Fran\c{c}a} and P. Moscato", title = "{Algoritmo Mem\'etico para o Problema do Caixeiro Viajante}", booktitle = "Proceedings of {XXXI SOBRAPO} - {Simp\'osio Brasileiro de Pesquisa Operacional, Juiz de Fora, MG, Brazil, 20-22 de Octobre}", pages = "1015--1028", year ="1999", publisher = "{Sociedade Brasileira de Pesquisa Operacional}" } @misc{Buriol_Franca_Moscato_Havana2000, title = "New heuristic results for the asymmetric traveling salesman problem", author = "L.S. Buriol and P.M. {Fran\c{c}a} and P. Moscato", note = "Abstract accepted to \emph{4th International Conference on Operations Research Optimization. Havana, March 6-10\/}. Organized by Universidad de La Habana and Humboldt-{Universit\"at} zu Berlin" } @misc{Buriol_Franca_Moscato_JOH99, title = "{A New Memetic Algorithm for the Asymmetric Traveling Salesman Problem}", author = "L.S. Buriol and P.M. Fran\c{c}a and P. Moscato", note = "Submitted to \emph{Journal of Heuristics\/} (October/1999), under revision" } @misc{Mendes_Franca_Moscato_ICANNGA2001, title = "{Fitness Landscapes for the Total Tardiness Single Machine Scheduling Problem}", author = "A.S. Mendes and P.M. Fran\c{c}a and P. Moscato", note = "Accepted at \emph{ICANNGA 2001 - V International Conference on Artificial Neural Networks and Genetic Algorithms, Prague, Czech Republic, April, 2001\/}" } @misc{Franca_Mendes_MoscatoEJOR, title = "{A Memetic Algorithm for the Total Tardiness Single Machine Scheduling Problem}", author = "P.M. Fran\c{c}a and A.S. Mendes and P. Moscato", note = "Accepted in \emph{European Journal of Operations Research\/}" } @InProceedings{Mendes_Franca_Moscato_00fuzzy, author = "A.S. Mendes and P.M. {Fran\c{c}a} and P. Moscato", title = "{Fuzzy-Evolutionary Algorithms Applied to Scheduling Problems}", booktitle = "Proceedings of POM2000 - First World Conference on Production and Operations Management, Sevilla, Spain", pages = "", year ="2000", publisher = "" } @InProceedings{Franca_Gupta_Mendes_Moscato_Veltink_99SOBRAPO, author = "P.M. Fran\c{c}a and J.D. Gupta and A.S. Mendes and P. Moscato and K.J. Veltink", title = "{Novos resultados para o problema de flowshop com fam\'{\i}lias de tarefas e tempos de prepara\c{c}\~ao}", booktitle = "Proceedings of {XXXI SOBRAPO} - {Simp\'osio Brasileiro de Pesquisa Operacional, Juiz de Fora, MG, Brazil, 20-22 de Octobre}", pages = "", year ="1999", publisher = "{Sociedade Brasileira de Pesquisa Operacional}" } @InProceedings{Franca_Gupta_Mendes_Moscato_Veltink_00flowshop, author = "P.M. Fran\c{c}a and J.D. Gupta and A.S. Mendes and P. Moscato and K.J. Veltink", title = "{Metaheuristic Approaches for the Pure Flowshop Manufacturing Cell Problem}", booktitle = "PMS2000 - 7th International Workshop On Project Management And Scheduling, Osnabrück, Germany", pages = "", year ="2000", month = "April", publisher = "", note = "extended abstract" } @misc{Mendes_Muller_Franca_Moscato_PPC, title = "Comparing Meta-Heuristic Approaches for Parallel Machine Scheduling Problems", author = "A.S. Mendes and F.M. {M\"uller} and P.M. Fran\c{c}a and P. Moscato", note = "accepted in \emph{Production Planning \& Control}" } @misc{Mendes_Franca_Moscato_IEEE, title = "On optimal instances and fitness landscapes for the Single Machine Scheduling Problem with sequence-dependent setup times", author = "A.S. Mendes and P.M. Fran\c{c}a and P. Moscato", note = "submitted to \emph{{IEEE} Transactions on Evolutionary Computation}" }