×

Genetic algorithm crossover operators for ordering applications. (English) Zbl 0813.90098

Summary: We compare the performance of several crossover operators, including two new operators and a new faster formulation of a previously published operator. This new formulation performs better than the other operators we have tested while taking no more computation time. In addition, with practical applications in mind, we show how the use of problem specific information can improve the performance of the genetic algorithm and we describe a method for designing problem specific crossover incorporating a novel tie-breaking algorithm.

MSC:

90C27 Combinatorial optimization
68T05 Learning and adaptive systems in artificial intelligence
92D10 Genetics and epigenetics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, J. E., Adaptive selection methods for genetic algorithms, (Proc. First Int. Conf. Genetic Algorithms and their Applications (1985), Erlbaum), 101-111
[2] Davis, L., Job shop scheduling with genetic algorithms, (Proc. First Int. Conf. Genetic Algorithms and their Applications (1985), Erlbaum), 136-140
[3] De Jong, K. A.; Spears, W. M., Using genetic algorithms to solve NP-complete problems, (Proc. Third Int. Conf. Genetic Algorithms and their Applications. Proc. Third Int. Conf. Genetic Algorithms and their Applications, Kaufmann (1989)), 124-132
[4] Foulds, L. R., Combinatorial Optimization for Undergraduates (1984), Springer: Springer New York · Zbl 0583.90054
[5] Fox, B. R.; McMahon, M. B., Genetic operators for sequencing problems, (Rawlins, G. J.E., Foundations of Genetic Algorithms (1991), Kaufmann), 284-300
[6] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0721.68056
[7] Goldberg, D. E., Zen and the art of genetic algorithms, (Proc. Third Int. Conf. Genetic Algorithms and their Applications (1989), Kaufmann), 80-85
[8] Goldberg, D. E.; Lingle, R. L., Alleles, loci and the traveling salesman problem, (Proc. First Int. Conf. Genetic Algorithms and their Applications (1985), Erlbaum), 154-159
[9] (Grefenstette, J. J., Proc. First Int. Conf. Genetic Algorithms and their Applications (1985), Erlbaum)
[10] (Grefenstette, J. J., Proc. Second Int. Conf. Genetic Algorithms and their Applications (1987), Erlbaum)
[11] Grefenstette, J.; Gopal, R.; Rosmaita, B.; Van Gucht, D., Genetic algorithms for the traveling salesman problem, (Proc. First Int. Conf. Genetic Algorithms and their Applications (1985), Erlbaum), 160-168
[12] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, Mich
[13] Oliver, I. M.; Smith, D. J.; Holland, J. R.C., A study of permutation crossover operators on the traveling salesman problem, (Proc. Second Int. Conf. Genetic Algorithms and their Applications (1987), Erlbaum), 224-230
[14] P. W. Poon, The genetic algorithm applied to PWR reload core design. Ph.D. thesis, Cambridge University. In preparation.; P. W. Poon, The genetic algorithm applied to PWR reload core design. Ph.D. thesis, Cambridge University. In preparation.
[15] Poon, P. W.; Parks, G. T., Optimising PWR reload core designs, (Männer, R.; Manderick, B., Parallel Problem Solving from Nature 2 (1992), North-Holland: North-Holland Amsterdam), 371-380
[16] (Schaffer, J. D., Proc. Third Int. Conf. Genetic Algorithms and their Applications (1989), Kaufmann)
[17] Smith, D., Bin packing with adaptive search, (Proc. First Int. Conf. Genetic Algorithms and their Applications (1985), Erlbaum), 202-226
[18] Starkweather, T.; McDaniel, S.; Mathias, K.; Whitley, D., A comparison of genetic sequencing operators, (Belew, R. K., Proc. Fourth Int. Conf. Genetic Algorithms and their Applications (1991), Kaufmann), 69-76
[19] Syswerda, G., Schedule optimization using genetic algorithms, (Davis, L., A Handbook of Genetic Algorithms (1991), Van Nostrand Reinhold: Van Nostrand Reinhold Amsterdam), 332-349
[20] Whitley, D.; Starkweather, T.; Fuquay, D., Scheduling problems and traveling salesman: the genetic edge recombination and operator, (Proc. Third Int. Conf. Genetic Algorithms and their Applications (1989), Kaufmann), 133-140
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.