×

Test driving three 1995 genetic algorithms: New test functions and geometric matching. (English) Zbl 0853.68106

Summary: Genetic algorithms have attracted a good deal of interest in the heuristic search community. Yet there are several different types of genetic algorithms with varying performance and search characteristics. In this article we look at three genetic algorithms: an elitist simple genetic algorithm, the CHC algorithm and Genitor. One problem in comparing algorithms is that most test problems in the genetic algorithm literature can be solved using simple local search methods. In this article, the three algorithms are compared using new test problems that are not readily solved using simple local search methods. We then compare a local search method to genetic algorithms for geometric matching and examine a hybrid algorithm that combines local and genetic search. The geometric matching problem matches a model (e.g., a line drawing) to a subset of lines contained in a field of line fragments. Local search is currently the best known method for solving general geometric matching problems.

MSC:

68W10 Parallel algorithms in computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bäck, T., Hoffmeister, F., and Schwefel, H.P. (1991). A survey of evolution strategies. In L. Booker and R. Belew (Eds.),Proceedings of the Fourth International Conference on Gas (pp. 2–9). San Mateo, CA: Morgan Kaufmann.
[2] Back, T., and Schwefel, H.P. (1993). An overview of evolutionary algorithms for parameter optimization.Evolutionary computation, 1, 1–23. · Zbl 05412697 · doi:10.1162/evco.1993.1.1.1
[3] Beveridge, J. Ross. (1993). Local search algorithms for geometric object recognition: Optimal correspondence and pose. Ph. D. thesis, University of Massachusetts at Amherst.
[4] Beveridge, J. Ross, and Riseman, E.M. (1995). Optimal geometric model matching under full 3D perspective.CVGIP: Image Understanding. (Short version in IEEE Second CAD-Based Vision Workshop).
[5] Beveridge, J. Ross, Weiss, Rich, and Riseman, Edward M. (1989). Optimization of two-dimensional model matching. InProceedings: Image Understanding Workshop (pp. 815–830): Los Altos, CA: DARPA, Morgan Kaufmann.
[6] Beveridge, J. Ross, Weiss, Rich, and Riseman, Edward M. (1989). Optimization of two-dimensional model matching. In Hatem Nasr (Ed.),Selected Papers on Automatic Object Recognition (originally appeared in DARPA Image Understanding Workshop). SPIE Milestone Series. Bellingham, WA: SPIE.
[7] Bolles, R.C., and Cain, R.A. (1982). Recognizing and locating partially visible objects: The local-feature-focus method.International Journal of Robotics Research, 1(3), 57–82. · doi:10.1177/027836498200100304
[8] Collins, R.T., and Beveridge, J. Ross. (1993). Matching perspective views of coplanar structures using projective unwarping and similarity matching. InProceedings: 1993 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (pp. 240–245). New York: IEEE.
[9] Davis, Lawrence. (1991a). Bit-climbing, representational bias, and test suite design. In L. Booker and R. Belew (Eds.),Proceedings of the Fourth International Conference on GAs (pp. 18–23). San Mateo, CA: Morgan Kaufmann.
[10] Davis, Lawrence. (1991b).Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold.
[11] DeJong, Ken. (1975). An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, University of Michigan, Department of Computer and Communication Sciences, Ann Arbor.
[12] Eshelman, Larry. (1991). The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination. In G. Rawlins (Ed.),FOGA-1 (pp. 265–283). San Mateo, CA: Morgan Kaufmann.
[13] Fennema, Claude, Hanson, Allen, Riseman, Edward, Beveridge, J.R., and Kumar, R. (1990). Model-directed mobile robot navigation.IEEE Trans. on System. Man and Cybernetics, 20(6), 1352–1369. · doi:10.1109/21.61206
[14] Fogel, D.B. (1994). Evolutionary programming: An introduction and some current directions.Statistics and Computing, 4, 113–130. · doi:10.1007/BF00175356
[15] Fogel, L.J., Owens, A.J., and Walsh, M.J. (1966).Artificial Intelligence Through Simulated Evolution. New York: Wiley. · Zbl 0148.40701
[16] Glover, F. (1994). Genetic algorithms and scatter search: Unsuspected potentials.Statistics and Computing, 4, 131–140. · doi:10.1007/BF00175357
[17] Goldberg, David. (1989).Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley. · Zbl 0721.68056
[18] Goldberg, David. (1990). A note on Boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing. Technical Report No. 90003, Department of Engineering Mechanics, University of Alabama. · Zbl 0717.68083
[19] Grimson, W. Eric L. (1990).Object Recognition by Computer: The Role of Geometric Constraints. Cambridge, MA: MIT Press.
[20] Holland, John. (1975).Adaptation in Natural and Artificial Systems, Ann Arbor: University of Michigan Press. · Zbl 0317.68006
[21] Kernighan, B.W., and Lin, S. (1972). An efficeint heuristic procedure for partitioning graphs.Bell Systems Technical Journal, 49, 291–307. · Zbl 0333.05001
[22] Lowe, David G. (1985).Perceptual Organization and Visual Recognition. Boston: Kluwer.
[23] Mühlenbein, H. (1991). Evolution in time and space: The parallel genetic algorithm. In G. Rawlins (Ed.),FOGA-1 (pp. 316–337). San Mateo: Morgan Kaufmann.
[24] Mühlenbein, H., and Schlierkamp-Voosen, D. (1993). Predictive models for the breeder genetic algorithm.Journal of Evolutionary Computation, 1(1), 25–49. · Zbl 05412791 · doi:10.1162/evco.1993.1.1.25
[25] Mathias, Keith E., and Whitley, L. Darrell. (1994). Transforming the search space with Gray coding. In J.D. Schaffer (Ed.),IEEE International Conference on Evolutionary Computation (pp. 513–518). IEEE Service Center.
[26] Mathias, Keith E., Whitley, L. Darrell, Stork, Christof, and Kusuma, Tony. (1994). Staged hybrid genetic search for seismic data imaging. In J.D. Schaffer (Ed.),IEEE International Conference on Evolutionary Computation (pp. 356–361). IEEE Service Center.
[27] Papadimitriou, Christos H., and Steiglitz, Kenneth. (1982).Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall. · Zbl 0503.90060
[28] Shaffer, J. David, Caruana, Richard A., Eshelmen, Larry J., and Das, Rajarshi. (1989). A study of control parameters affecting online performance of genetic algorithms for function optimization. In J.D. Schaffer (Ed.),Proceedings of the Third International Conference on GAs (pp. 51–60). San Mateo, CA: Morgan Kaufmann.
[29] Starkweather, Timothy, Whitley, L. Darrell, and Mathias, Keith E. (1990). Optimization using distributed genetic algorithms. In H.P. Schwefel and R. Männer (Eds.),Parallel Problem Solving from Nature (pp. 176–185). Berlin: Springer/Verlag.
[30] Syswerda, Gilbert. (1989). Uniform crossover in genetic algorithms. In J.D. Schaffer (Ed.),Proceedings of the Third International Conference on GAs. San Mateo, CA: Morgan Kaufmann.
[31] Whitley, L. Darrell. (1989). The GENITOR algorithm and slective pressure: Why rank based allocation of reproductive trials is best. In J.D. Schaffer (Ed.),Proceedings of the Third International Conference on Gas (pp. 116–121). Morgan Kaufmann.
[32] Whitley, L. Darrell. (1994). A genetic algorithm tutorial.Statistics and Computing, 4, 65–85. · Zbl 0828.68084 · doi:10.1007/BF00175354
[33] Whitley, Darrell, and Kauth, Joan. (1988). GENITOR: A different genetic algorithm. InProceedings of the 1988 Rocky Mountain Conference on Artificial Intelligence. City: Publisher.
[34] Whitley, Darrell, Mathia, Keith, Rana, Soraya, and Dzubera, John. (1995). Building better test functions. In L. Eshelman (Ed.),Proceedings of the Sixth International Conference on Gas. City: Morgan Kaufmann.
[35] Whitley, Darrell, Mathias, Keith, Rana, Soraya, and Dzubera, John. (1995). Evaluating evolutionary algorithms. Manuscript.
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.