@InProceedings{Manderick89a, author = "Bernard Manderick and Piet Spiessens", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", editor = "J. David Schaffer", title = "Fine-Grained Parallel Genetic Algorithms", publisher = "Morgan Kaufmann Publishers", } @InProceedings{Muhlenbein91a, author = "Heinz M{\"u}hlenbein", booktitle = "Foundations of Genetic Algorithms", editor = "Gregory J. E. Rawlins", title = "Evolution in Time and Space -- The Parallel Genetic Algorithm", publisher = "Morgan Kaufmann Publishers", } @InProceedings{Cohoon87a, author = "J. P. Cohoon and S. U. Hegde and W. N. Martin and D. Richards", booktitle = "Proceedings of the Second International Conference on Genetic Algorithms", editor = "John J. Grefenstette", publisher = "Lawrence Erlbaum Associates, Publishers", title = "Punctuated equilibria: a parallel genetic algorithm", year = "1987", } @InProceedings{Jog87a, author = "Prasanna Jog and {Dirk Van Gucht}", booktitle = "Proceedings of the Second International Conference on Genetic Algorithms", editor = "John J. Grefenstette", publisher = "Lawrence Erlbaum Associates, Publishers", title = "Parallelisation of probabilistic sequential search algorithms", year = "1987", } @InProceedings{Pettey87a, author = "Chrisila B. Pettey and Michael R. Leuze and John J. Grefenstette", booktitle = "Proceedings of the Second International Conference on Genetic Algorithms", editor = "John J. Grefenstette", publisher = "Lawrence Erlbaum Associates, Publishers", title = "A parallel genetic algorithm", year = "1987", } @InProceedings{Robertson87a, author = "George G. Robertson", booktitle = "Proceedings of the Second International Conference on Genetic Algorithms", editor = "John J. Grefenstette", publisher = "Lawrence Erlbaum Associates, Publishers", title = "Parallel implementation of genetic algorithms in a classifier system", year = "1987", } @InProceedings{Tanese87a, author = "Reiko Tanese", booktitle = "Proceedings of the Second International Conference on Genetic Algorithms", editor = "John J. Grefenstette", publisher = "Lawrence Erlbaum Associates, Publishers", title = "Parallel genetic algorithms for a hypercube", year = "1987", } @InProceedings{Brown89a, author = "Donald E. Brown and Christopher L. Huntley and Andrew R. Spillane", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", editor = "J. David Schaffer", publisher = "Morgan Kaufmann Publishers", title = "A Parallel Genetic Heuristic for the Quadratic Assignment Problem", year = "1989", } @InProceedings{Goldberg89b, author = "David E. Goldberg", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", editor = "J. David Schaffer", publisher = "Morgan Kaufmann Publishers", title = "Sizing Populations for Serial and Parallel Genetic Algorithms", year = "1989", } @InProceedings{Grefenstette89a, author = "John J. Grefenstette and James E. Baker", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", editor = "J. David Schaffer", publisher = "Morgan Kaufmann Publishers", title = "How Genetic Algorithms Work: {A} Critical Look at Implicit Parallelism", year = "1989", } @InProceedings{Muhlenbein89a, author = "Heinz M{\"\}{u\}hlenbein", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", publisher = "Morgan Kaufmann Publishers, Inc", title = "Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization", year = "1989", } @InProceedings{Petty89a, author = "Chrisila C. Pettey and Michael R. Leuze", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", editor = "J. David Schaffer", publisher = "Morgan Kaufmann Publishers", title = "A Theoretical Investigation of a Parallel Genetic Algorithm", year = "1989", } @InProceedings{Tanese89a, author = "R. Tanese", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", editor = "J. D. Schaffer", publisher = "Morgan Kaufmann Publishers", title = "Distributed Genetic Algorithms", year = "1989", } @PhdThesis{Tanese89, author = "R. Tanese", note = "Computer Science and Engineering", school = "University of Michigan", title = "Distributed Genetic Algorithms for Function Optimization", year = "1989", } @MastersThesis{Camilli90, author = "A. Camilli", school = "University of Pisa", title = "Classifier systems in massively parallel architectures (in Italian)", year = "1990", } @PhdThesis{Gorges90, author = "M. Gorges-Schleuter", school = "University of Dortmund", title = "Genetic algorithms and population structure - {A} massively parallel algorithm", year = "1990", } @InProceedings{Collins91a, author = "Robert J. Collins and David R. Jefferson", address = "San Mateo, CA", booktitle = "Proceedings of the Fourth International Conference on Genetic Algorithms", editor = "Richard K. Belew and Lashon B. Booker", publisher = "Morgan Kaufmann Publishers", title = "Selection in Massively Parallel Genetic Algorithms", year = "1991", } @InProceedings{Grefenstette91a, author = "John J. Grefenstette", booktitle = "Foundations of Genetic Algorithms", editor = "Gregory J. E. Rawlins", publisher = "Morgan Kaufmann Publishers", title = "Conditions for Implicit Parallelism", year = "1991", } @InProceedings{Kitano91a, author = "Hiroaki Kitano and Stephen F. Smith and Tetsuya Higuchi", address = "San Mateo, CA", booktitle = "Proceedings of the Fourth International Conference on Genetic Algorithms", editor = "Richard K. Belew and Lashon B. Booker", publisher = "Morgan Kaufmann Publishers", title = "{GA}-1: {A} Parallel Associative Memory Processor for Rule Learning with Genetic Algorithms", year = "1991", } @InProceedings{Kosak91a, author = "Corey Kosak and Joe Marks and Stuart Shieber", address = "San Mateo, CA", booktitle = "Proceedings of the Fourth International Conference on Genetic Algorithms", editor = "Richard K. Belew and Lashon B. Booker", publisher = "Morgan Kaufmann Publishers", title = "A Parallel Genetic Algorithm for Network-Diagram Layout", year = "1991", } @InProceedings{Muhlenbein91b, author = "Heinz M{\"\}{u\}hlenbein and M. Schomisch and J. Born", address = "San Mateo, CA", booktitle = "Proceedings of the Fourth International Conference on Genetic Algorithms", editor = "Richard K. Belew and Lashon B. Booker", publisher = "Morgan Kaufmann Publishers", title = "The Parallel Genetic Algorithm as Function Optimizer", year = "1991", } @InProceedings{Spiessens91a, author = "Piet Spiessens and Bernard Manderick", address = "San Mateo, CA", booktitle = "Proceedings of the Fourth International Conference on Genetic Algorithms", editor = "Richard K. Belew and Lashon B. Booker", publisher = "Morgan Kaufmann Publishers", title = "A Massively Parallel Genetic Algorithm: Implementation and First Analysis", year = "1991", } @MastersThesis{Sirtori91, author = "E. Sirtori", note = "MP-AI Project, Department of Electronics", school = "Politecnico di Milano", title = "{ALECSYS} - {A} parallel architecture for Machine Learning (in Italian)", year = "1991", } @InProceedings{Mutalik92a, author = "P. P. Mutalik and L. R. Knight and J. L. Blanton and R. L. Wainwright", booktitle = "Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing", pages = "1031--1038", title = "Solving Combinatorial Optimization Problems Using Parallel Simulated Annealing and Parallel Genetic Algorithms", year = "1992", } @PROCEEDINGS( icga2, key = "ICGA", booktitle = "Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms", year = 1987, publisher = "Lawrence Erlbaum" ) @PROCEEDINGS( icga3, key = "ICGA", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", year = 1989, publisher = "Morgan Kaufman" ) @Article{ArFeStTe69, author = "J. Arabeyre and J. Fearnley and F. Steiger and W. Teather", title = "The {A}irline {C}rew {S}cheduling {P}roblem: {A} {S}urvey", journal = "Transportation Science", year = "1969", volume = "3", number = "2", pages = "140--163", } @Article{BaFi81, author = "E. Baker and M. Fisher", title = "Computational {R}esults for {V}ery {L}arge {A}ir {C}rew {S}cheduling {P}roblems", journal = "OMEGA", year = "1981", volume = "9", number = "6", pages = "613--618", } @Article{BaPa76, author = "E. Balas and M. Padberg", title = "Set {P}artitioning: {A} {S}urvey", journal = "SIAM Review", year = "1976", volume = "18", number = "4", pages = "710--760", } @Article{BaHu90, author = "J. Barutt and T. Hull", title = "Airline {C}rew {S}cheduling: Supercomputers and {A}lgorithms", journal = "SIAM News", year = "1990", volume = "23", number = "6", } @TechReport{BiGrLuMaSh91, author = "R. Bixby and J. Gregory and I. Lustig and R. Marsten and D. Shanno", title = "Very {L}arge-{S}cale {L}inear {P}rogramming: {A} {C}ase {S}tudy in {C}ombining {I}nterior {P}oint and {S}implex {M}ethods", year = "1991", institution = "Rice University", number = "CRPC", } @Article{Ch79, author = "V. Chvatal", title = "A {G}reedy {H}euristic for the {S}et {C}overing {P}roblem", journal = "OMEGA", year = "1979", volume = "4", number = "3", pages = "233--235", } @Book{Ch83, author = "V. Chvatal", title = "Linear Programming", publisher = "W. H. Freeman and Company", address = "New York", year = "1983", } @Article{Fi85, author = "M. Fischer", title = "An {A}pplications {O}riented {G}uide to {L}agrangian {R}elaxation", journal = "INTERFACES", year = "1985", volume = "15", number = "2", pages = "10--21", } @Article{FiKe90, author = "M. Fischer and P. Kedia", title = "Optimal {S}olution of {S}et {C}overing/{P}artitioning {P}roblems using {D}ual {H}euristics", journal = "Management Science", year = "1990", volume = "36", number = "6", pages = "674--688", } @Article{Fl72, author = "M. Flynn", title = "Some Computer Organizations and Their Effectiveness", journal = "IEEE Transactions on Computers", year = "1972", volume = "21", pages = "948--960", } @Book{GaNe72, author = "R. Garfinkel and G. Nemhauser", title = "Integer Programming", publisher = "John Wiley and Sons Inc.", year = "1972", } @Book{Go89, author = "D. Goldberg", title = "{G}enetic {A}lgorithms in Search, Optimization and Machine Learning", publisher = "Addison-Wesley Publishing Company, Inc.", year = "1989", } @TechReport{Go, author = "D. Goldberg", title = "Sizing Populations for Serial and Parallel Genetic Algorithms", year = "XX", institution = "The University of Alabama", number = "Technical Report", } @InProceedings{SuGu, author = "J. Suh and D. Gucht", title = "Incorporating Heuristic Information into Genetic Search", pages = "100--107", } @Book{Ho75, author = "J. Holland", title = "Adaption in Natural and Artificial Systems", publisher = "The University of Michigan Press", year = "1975", } @TechReport{JoSuGu90, author = "P. Jog and J. Suh and D. Gucht", title = "{P}arallel {G}enetic {A}lgorithms {A}pplied to the {T}raveling {S}alesman {P}roblem", year = "1990", institution = "Indiana University", number = "No. 314", } @TechReport{LiHiPaMo, author = "G. Liepins and M. Hilliard and M. Palmer and M. Morrow", title = "Greedy Genetics", institution = "Oak Ridge National Laboratory", number = "Oak Ridge National Laboratory Technical Report", } @InBook{LiHiRiPa, author = "G. Liepins and M. Hilliard and J. Richardson and M. Palmer", editor = "D. Brown and C. White", title = "{G}enetic {A}lgorithms {A}pplications to {S}et {C}overing and {T}raveling {S}alesman {P}roblems", year = "19XX", booktitle = "OR/AI: The Integration of Problem Solving Strategies", pages = "29--57", } @Article{Li65, author = "S. Lin", title = "Computer {S}olutions of the {T}raveling {S}alesman {P}roblem", journal = "Bell System Technical Journal", year = "1965", volume = "44", pages = "2245--2269", } @Article{LiKe73, author = "S. Lin and B. Kernighan", title = "An {E}ffective {H}euristic {A}lgorithm for the {T}raveling {S}alesman {P}roblem", journal = "Operations Research", year = "1973", volume = "21", pages = "498--516", } @Article{Ma74, author = "R. Marsten", title = "An {A}lgorithm for {L}arge {S}et {P}artitioning {P}roblems", journal = "Management Science", year = "1974", volume = "20", pages = "774--787", } @Article{MaSh81, author = "R. Marsten and F. Shepardson", title = "Exact {S}olution of {C}rew {S}cheduling {P}roblems {U}sing the {S}et {P}artitioning {M}odel: Recent {S}uccessful {A}pplications", journal = "Networks", year = "1981", volume = "11", pages = "165--177", } @Article{Mu91, author = "H. Muhlenbein", title = "Parallel {G}enetic {A}lgorithms and {C}ombinatorial {O}ptimization", journal = "SIAM Journal on Optimization", year = "1991", volume = "To appear", } @Book{PaSt82, author = "C. Papadimitriou and K. Steiglitz", title = "Combinatorial Optimization Algorithms and Complexity", publisher = "Prentice-Hall Inc.", year = "1982", } @Article{Pi68, author = "J. Pierce", title = "Application of {C}ombinatorial {P}rogramming to a {C}lass of {A}ll-{Z}ero-{O}ne {I}nteger {P}rogramming {P}roblems", journal = "Management Science", year = "1968", volume = "15", pages = "191--209", } @InProceedings{Ta89, author = "R. Tanese", editor = "J. Schaffer", title = "Distributed {G}enetic {A}lgorithms", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", year = "1989", pages = "434--440", publisher = "Morgan Kaufmann", } @InProceedings{LaMu91, author = "G. von Laszewsski and H. Muhlenbein", title = "Partitioning a {G}raph with a {P}arallel {G}enetic {A}lgorithm", booktitle = "Parallel Problem Solving from Nature", editor = "H. Schwefel and R. Manner", year = "1991", publisher = "Springer-Verlag", pages = "165--169", } @InProceedings{CoMaRi91, author = "J. Cohoon and W. Martin and D. Richards", title = "{G}enetic {A}lgorithms and {P}unctuated {E}quilibria in {VLSI}", booktitle = "Parallel Problem Solving from Nature", editor = "H. Schwefel and R. Manner", year = "1991", publisher = "Springer-Verlag", pages = "134--144", } @InProceedings{Sc91, author = "M. Gorges-Schleuter", title = "Explicit {P}arallelism of {G}enetic {A}lgorithms through {P}opulation {S}tructures", booktitle = "Parallel Problem Solving from Nature", editor = "H. Schwefel and R. Manner", year = "1991", publisher = "Springer-Verlag", pages = "150--159", } @InProceedings{StWhMa91, author = "T. Starkweather and D. Whitley and K. Mathias", title = "Optimization {U}sing {D}istributed {G}enetic {A}lgorithms", booktitle = "Parallel Problem Solving from Nature", editor = "H. Schwefel and R. Manner", year = "1991", publisher = "Springer-Verlag", pages = "176--185", } @InProceedings{FoHu91, author = "T. Fogarty and R. Huang", title = "Implementing the {G}enetic {A}lgorithm on {T}ransputer {B}Ased {P}arallel {P}rocessing {S}ystems", booktitle = "Parallel Problem Solving from Nature", editor = "H. Schwefel and R. Manner", year = "1991", publisher = "Springer-Verlag", pages = "145--149", } @InProceedings{KrScVo91, author = "B. Kroger and P. Schwenderling and O. Vornberger", title = "Parallel {G}enetic {P}acking of {R}ectangles", booktitle = "Parallel Problem Solving from Nature", editor = "H. Schwefel and R. Manner", year = "1991", publisher = "Springer-Verlag", pages = "160--164", } @TechReport{LiBa91, author = "G. Liepins and S. Baluja", title = "{apGA}: An {A}daptive {P}arallel {G}enetic {A}lgorithm", year = "1991", institution = "Oak Ridge National Laboratory", } @InProceedings{Da87, author = "L. Booker", editor = "L. Davis", title = "Improving {S}earch in {G}enetic {A}lgorithms", booktitle = "Genetic Algorithms and Simulated Annealing", publisher = "Pitman Publishing", address = "London", pages = "61--73", year = "1987", } @Book{Da91, author = "L. Davis", title = "Handbook of Genetic Algorithms", publisher = "Van Nostrand Reinhold", address = "New York", year = "1991", } @Book{PaRa88, author = "R. Parker and R. Rardin", title = "Discrete Optimization", publisher = "Academic Press", address = "San Diego", year = "1988", } @InProceedings{CoDoMaXX, author = "A. Colorni and M. Dorigo and V. Maniezzo", title = "{G}enetic {A}lgorithms and {H}ighly {C}onstrained {P}roblems: the {T}ime-table {C}ase", booktitle = "XXXX-XXXX", year = "XX", pages = "55--59", } @InProceedings{RiPaLiHi89, author = "J. Richardson and M. Palmer and G. Liepins and M. Hilliard", editor = "J. Schaffer", title = "Some {G}uidelines for {G}enetic {A}lgorithms with {P}enalty {F}unctions", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", year = "1989", publisher = "Morgan Kaufmann", pages = "191--197", } @InProceedings{SiSk89, author = "Siedlecki and Sklansky", editor = "J. Schaffer", title = "Constrained {G}enetic {O}ptimization via {D}ynamic {R}eward-{P}enalty {B}alancing and {I}ts {U}se in {P}attern {R}ecognition", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", year = "1989", publisher = "Morgan Kaufmann", pages = "141--150", } @Article{FoGrSt92, author = "I. Foster and W. Gropp and R. Stevens", title = "The {P}arallel {S}sclability of the {S}pectral {T}ransform {M}ethod", journal = "Monthly Weather Review", year = "1992", volume = "To appear", } @TechReport{tec:norman:GeneAppTopOptMultiArch, author = "Michael G Norman", title = "A Genetic Approach to Topology Optimisation for Multiprocessor Architectures", institution = "Edinburgh Concurrent Supercomputer Project", year = "1988", } @Article{art:radcliffe:EquClasAnalGenAlg, author = "Nicholas J Radcliffe", title = "Equivalence Class Analysis of Genetic Algorithms", journal = "Complex Systems", year = "1991", volume = "5", number = "2", pages = "183--205", note = "EPCC-TR90-03", } @InProceedings{inp:radcliffe:FormaAnal, author = "Nicolas J Radcliffe", title = "Forma Analysis and Random Respectful Recombination", booktitle = "Proc. of 4th International Conference on Genetic Algorithms", year = "1991", editor = "R K Belew and L B Booker", pages = "222--229", publisher = "Morgan Kaufmann", address = "San Mateo", note = "EPCC-TR91-02", } @TechReport{tec:radcliffe:GeneSetRecomb+Apps, author = "Nicolas J Radcliffe", title = "Genetic Set Recombination and its Application to Neural Network Topology Optimisation", institution = "EPCC", year = "1991", number = "TR91-21", note = "to be published in Neural Computing and its Applications, Vol 1, no. 1", } @InCollection{inc:radcliffe:GeneSetRecomb, author = "Nicolas J Radcliffe", title = "Genetic Set Recombination", booktitle = "Foundations of Genetic Algorithms II", publisher = "M Kaufmann", year = "1992", editor = "D Whitley", note = "to be published, autumn", } @InCollection{inc:radcliffe:Non-LinGeneReps, author = "Nicolas J Radcliffe", title = "Non-Linear Genetic Representations'", booktitle = "Parallel Problem Solving from Nature II", publisher = "Elsevier Science Publishers", year = "1992", note = "to appear", } @TechReport{tec:radcliffe:AlgGeneAlg, author = "Nicolas J Radcliffe", title = "The Algebra of Genetic Algorithms", institution = "EPCC", year = "1992", number = "TR92-11", note = "in preparation", } @Unpublished{unp:edwards:GenAlgOptProcPlan, author = "Donald Edwards", title = "Genetic Algorithms for the Optimisation of Process Planning", note = "EPCC-SS90-09", } @Unpublished{unp:russo:GenerFrameImpGenetAlg, author = "Claudio Russo", title = "A General Framework for Implementing Genetic Algorithms", note = "EPCC-SS91-17", } @PhdThesis{phd:radcliffe:GenNNMIMDComps, author = "Nicolas J Radcliffe", title = "Genetic Neural Networks on {MIMD} Computers", school = "University of Edinburgh", year = "1990", note = "Physics PhD thesis", } @Conference{Hof91, crossref = "GP91", author = "Frank Hoffmeister", title = "Scalable Parallelism by Evolutionary Algorithms", pages = "175--198", year = "1991", } @Book{GP91, editor = "M. Grauer and D.~B. Pressmar", title = "Applied Parallel and Distributed Optimization", volume = "367", series = "Lecture Notes in Mathematical Systems and Economics", publisher = "Springer", address = "Berlin", year = "1991", } @InProceedings{gorges89a:ga, author = "{Martina Gorges-Schleuter}", title = "{ASPARAGOS}: An Asynchronous Parallel Genetic Optimization Strategy", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", editor = "J. David Schaffer", publisher = "Morgan Kaufmann Publishers", year = "1989", } @InProceedings{knight92a:ga, author = "L. R. Knight and R. L. Wainwright", publisher = "SPPCC'92", title = "{HYPERGEN}: {A} Distributed Genetic Algorithm on a Hypercube", booktitle = "Proceedings of the 1992 Scalable High Performance Computing Conference", year = "1992", } @MastersThesis{camilli90:gat, author = "A. Camilli", title = "Classifier systems in massively parallel architectures (in Italian)", school = "University of Pisa", year = "1990", } @TechReport{Brown92, author = "Ricardo Bianchini and Christopher M. Brown", title = "Parallel Genetic Algorithms on Distributed-Memory Architectures", year = "1992", month = aug, number = "436", institution = "Computer Science Department, University of Rochester", keywords = "parallel genetic algorithms; integer linear programming; transputers; distributed-memory systems", abstract = "The implementation of genetic algorithms raises many important issues. These issues can be divided into two main classes: genetic search quality and execution performance. In the context of parallel genetic algorithms on distributed-memory computers, performance considerations have always driven the design of implementations. Thus, centralized implementations have not previously been seriously considered for distributed-memory architectures. \par The work we present here defines a set of genetic algorithm implementation alternatives for distributed-memory computers, in which strategies with some centralization are included. Each of our implementation alternatives uses a different level of distribution of the population, from the single logically centralized population to a totally distributed set of subpopulations. \par The design alternatives we define can be applied to the implementation of any parallel genetic algorithm. As an example of such an implementation, we study the quality of the search and the execution performance of our strategies on the 0-1 Integer Linear Programming problem, on a Transputer network. Our results show that implementations incurring higher overheads can produce as good or better solutions faster than than very {"}efficient{"} implementations, depending on the characteristics of the problem at hand. More specifically, in some cases, utilizing more centralized parallel genetic search strategies results in the fastest convergence towards the optimal solution, therefore reducing the number of generations needed by the algorithm. (File 92.tr436.parallel_genetic_algorithms.ps.Z (in pub/papers/systems))", } @TechReport{Tanese89, author = "Reiko Tanese", title = "Distributed Genetic Algorithms for Function Optimization", institution = "University of Michigan", year = "1989", number = "CSE-TR-26-89", }