Skip to main content
SpringerLink
Log in

Comparison of a genetic algorithm and simulated annealing in an application to statistical image reconstruction

  • Published:
Statistics and Computing Aims and scope Submit manuscript

Abstract

Genetic algorithms (GAs) are adaptive search techniques designed to find near-optimal solutions of large scale optimization problems with multiple local maxima. Standard versions of the GA are defined for objective functions which depend on a vector of binary variables. The problem of finding the maximum a posteriori (MAP) estimate of a binary image in Bayesian image analysis appears to be well suited to a GA as images have a natural binary representation and the posterior image probability is a multi-modal objective function. We use the numerical optimization problem posed in MAP image estimation as a test-bed on which to compare GAs with simulated annealing (SA), another all-purpose global optimization method. Our conclusions are that the GAs we have applied perform poorly, even after adaptation to this problem. This is somewhat unexpected, given the widespread claims of GAs' effectiveness, but it is in keeping with work by Jennison and Sheehan (1995) which suggests that GAs are not adept at handling problems involving a great many variables of roughly equal influence.

We reach more positive conclusions concerning the use of the GA's crossover operation in recombining near-optimal solutions obtained by other methods. We propose a hybrid algorithm in which crossover is used to combine subsections of image reconstructions obtained using SA and we show that this algorithm is more effective and efficient than SA or a GA individually.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Atkinson, A. C. (1992) A segmented algorithm for simulated annealing. Statistics and Computing, 2, 221–30.

    Google Scholar 

  • Atkinson, A. C. and Weisberg, S. (1991) Simulated annealing for the detection of multiple outliers using least squares and least median of squares fitting. In Directions in Robust Statistics and Diagnostics, Part I, (W. Stahel and S. Weisberg, eds), Springer-Verlag, New York, pp. 7–20.

    Google Scholar 

  • Battiti, R. and Tecchiolli, G. (1992) Parallel biased search for combinatorial optimization: genetic algorithms and TABU. Microprocessors and Microsystems, 16, 351–67.

    Google Scholar 

  • Besag, J. E. (1986) On the statistical analysis of dirty pictures (with discussion). Journal of the Royal Statistical Society B, 48, 259–302.

    Google Scholar 

  • Boseniuk, T. and Ebeling, W. (1991) Boltzmann-, Darwin-, and Haeckel-strategies in optimization problems. In Lecture Notes in Computer Sciences: Parallel Problem Solving from Nature, 496, pp. 430–44.

    Google Scholar 

  • Brown, D. E., Huntley, C. L. and Spillane, A. R. (1989) A parallel genetic heuristic for the quadratic assignment problem. In Proceedings of the Third International Conference on Genetic Algorithms, (J. D. Schaffer, ed.), Morgan Kaufmann, San Mateo, California, pp. 406–15.

    Google Scholar 

  • Bui, T. N. and Moon, B. R. (1995) On multi-dimensional encoding/crossover. In Proceedings of the Sixth International Conference on Genetic Algorithms, (L. J. Eshelman, ed.), Morgan Kaufmann, San Mateo, California, pp. 49–56.

    Google Scholar 

  • Crawford, K. D. and Wainwright, R. L. (1995) Applying genetic algorithms to outlier detection. In Proceedings of the Sixth International Conference on Genetic Algorithms, (L. J. Eshelman, ed.), Morgan Kaufmann, San Mateo, California, pp. 546–550

    Google Scholar 

  • Das, R. and Whitley, D. (1991) The only challenging problems are deceptive: Global search by solving order-1 hyperplanes. In Proceedings of the Fourth International Conference on Genetic Algorithms, (R. K. Belew and L. B. Booker, eds), Morgan Kaufmann, San Mateo, California, pp. 166–73.

    Google Scholar 

  • Davis, L. (1991)Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York.

    Google Scholar 

  • De Jong, K. A. and Spears, W. M. (1991) An analysis of the interacting role of population size and cross-over in genetic algorithms. In Lecture Notes in Computer Sciences, Parallel Problem Solving from Nature, 496, (H. P. Schwefel and R. Manner, eds), Springer-Verlag, London, pp. 38–47.

    Google Scholar 

  • DeJong, K. and Spears, W. (1993) On the state of evolutionary computation. In Proceedings of the Fifth International Con-ference on Genetic Algorithms, (S. Forrest ed.), Morgan Kaufmann, San Mateo, California, pp. 618–23.

    Google Scholar 

  • Eshelman, L. J. (1991) The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination. In Foundations of Genetic Algorithms and Classifier Systems, (G. Rawlins, ed.), Morgan Kaufmann, San Mateo, California, pp. 265–83.

    Google Scholar 

  • Eshelman, L. J and Schaffer, J. D. (1991) Preventing premature convergence in genetic algorithms by preventing incest. In Proceedings of the Fourth International Conference on Genetic Algorithms, (R. K. Belew and L. B. Booker, eds), Morgan Kaufmann, San Mateo, California, pp. 115–22.

    Google Scholar 

  • Geman, D. and Geman, S. (1984) Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6, 721–41.

    Google Scholar 

  • Goldberg, D. E. (1989) Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley, Reading, Mass.

    Google Scholar 

  • Goldberg, D. E. (1990) A note on Boltzmann tournament selec-tion for genetic algorithms and population-oriented simu-lated anealing. Complex Systems, 4, 445–60.

    Google Scholar 

  • Goldberg, D. E. and Richardson, J. (1987) Genetic algorithms with sharing for multimodal function optimization. In Pro-ceedings of the Second International Conference on Genetic Algorithms, (J. J. Grefenstette, ed.), Lawrence Erlbaum, Hillsdale, NJ, pp. 41–9.

    Google Scholar 

  • Goutsias, J. (1989) A theoretical analysis of Monte Carlo algo-rithm for the simulation of Gibbs random field images. Technical Report JHU/ELE 89–07, Image Analysis and Communications Laboratories, Dept of Elect. and Comput. Eng., The John Hopkins University, Baltimore.

    Google Scholar 

  • Goutsias, J. (1991) A theoretical analysis of Monte Carlo algo-rithm for the simulation of Gibbs random field images. IEEE Transactions on Information Theory, 373, 1618–28.

    Google Scholar 

  • Grefenstette, J. J. (1987) Incorporating problem specific know-ledge into genetic algorithms. In Genetic Algorithms and Simulated Annealing, (L. Davis, ed.), Pitman, London, pp. 42–60.

    Google Scholar 

  • Greig, D. M., Porteous, B. T. and Seheult, A. H. (1989) Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society B, 51, 271–9.

    Google Scholar 

  • Hatjimihail, A. T. and Hatjimihail, T. T. (1995) Design of sta-tistical quality control procedures using genetic algorithms. In Proceedins of the Sixth International Conference on Genetic Algorithms, (L. J. Eshelman, ed.), Morgan Kaufmann, San Mateo, California, pp. 551–7.

    Google Scholar 

  • Holland, J. H. (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.

    Google Scholar 

  • Holland, J. H. (1992) Genetic Algorithms. Scientific American, 267, 44–50.

    Google Scholar 

  • Ingber, L. and Rosen, B. (1992) Genetic algorithms and very fast simulated reannealing: A comparison. Mathematical and Computer Modelling, 16, 87–100.

    Google Scholar 

  • Jennison, C. and Sheehan, N. (1995) Theoretical and empirical properties of the genetic algorithm as a numerical optimizer. Journal of Computational and Graphical Statistics, 4, 296–318.

    Google Scholar 

  • Julstrom, B. A. (1995) What have you done for me lately? Adapting operator probabilities in a steady-state genetic al-gorithm. In Proceedings of the Sixth International Conference on Genetic Algorithms, (L. J. Eshelman, ed.), Morgan Kaufmann, San Mateo, California, pp. 81–7.

    Google Scholar 

  • Kido, T., Kitano, H. and Nakanishi, M. (1993) A hybrid search for genetic algorithms: Combining genetic algorithms, TABU search, and simulated annealing. In Proceedings of the Fifth International Conference on Genetic Algorithms, (S. Forrest, ed.), Morgan Kaufmann, San Mateo, California, p. 641.

    Google Scholar 

  • Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P. (1983) Optimi-zation by simulated annealing. Science, 220, 671–80.

    Google Scholar 

  • Lin, F.-T., Kao, C.-Y. and Hsu, C.-C. (1991) Incorporating ge-netic algorithms into simulated annealing. In Proceedings of the Fourth International Symposium on AI, pp. 290–297.

  • Mahfoud, S. W. and Goldberg, D. E. (1995) Parallel recombi-native simulated annealing: A genetic algorithm. Parallel Computing, 21, 1–28.

    Google Scholar 

  • Michalewicz, Z. (1994) Non-standard methods in evolutionary computation. Statistics and Computing 4, 141–55.

    Google Scholar 

  • Michalewicz, Z. and Janikow, C. Z. (1991) Genetic algorithms for numerical optimization. Statistics and Computing, 1, 75–91.

    Google Scholar 

  • Michalewicz, Z., Vignaux, G. A. and Hobbs, M. (1991) A non-standard genetic algorithm for the nonlinear transportation problem. ORSA Journal on Computing, 3, 307–16.

    Google Scholar 

  • Reeves, C. R. and Wright, C. C. (1995a) Epistasis in genetic algorithms: An experimental design perspective. In Proceed-ings of the Sixth International Conference on Genetic Algo-rithms, (L. J. Eshelman, ed.), Morgan Kaufmann, San Mateo, California pp. 217–24.

    Google Scholar 

  • Reeves, C. R. and Wright, C. C. (1995b) An experimental design perspective on genetic algorithms. In Foundations of Genetic Algorithms 3, (L. J. Whitley and M. D. Vose, eds), Morgan Kaufmann, San Francisco, California, pp. 7–22.

    Google Scholar 

  • Reeves, C. R. and Wright, C. C. (1995c) Genetic algorithms and statistical methods: a comparison. In Genetic Algorithms in Engineering System: Innovations and Applications, IEE Con-ference Publication No. 414, pp. 137–40.

  • South, M. C., Wetherill, G. B. and Tham, M. T. (1993) Hitch-hiker's guide to genetic algorithms. Journal of Applied Sta-tistics, 20, 153–75.

    Google Scholar 

  • Stander, J. and Silverman, B. W. (1994) Temperature sched-ules for simulated annealing. Statistics and Computing, 4, 21–32.

    Google Scholar 

  • Tan, K. C., Li, Y., Murray-Smith, D. J. and Sharman, K. C. (1995) System identification and linearisation using genetic algorithms with simulated annealing. In Genetic Algorithms in Engineering Systems: Innovations and Applications. IEE Conference Publication No. 414, pp. 164–9.

  • Varanelli, J. M. and Cohoon, J. P. (1995) Population-oriented simulated annealing: A genetic/thermodynamic hybrid approach to optimization. In Proceedings of the Sixth In-ternational Conference on Genetic Algorithms. (L. J. Eshel-man, ed.), Morgan Kaufmann, San Mateo, California, pp. 174–81.

    Google Scholar 

  • Whitley, D. (1989) The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. In Proceedings of the Third International Conference on Genetic Algorithms, (J. D. Schaffer, ed.), Morgan Kaufmann, San Mateo, California, pp. 116–21.

    Google Scholar 

  • Whitley, D. (1994) A genetic algorithm tutorial. Statistics and Computing,4, 65–85.

    Google Scholar 

  • Wichmann, B. A. and Hill, J. D. (1982) Algorithm AS183. An efficient and portable pseudo-random number generator. Applied Statistics, 31, 188–90.

    Google Scholar 

  • Wu, C. F. J., Mao, S. S. and Ma, F. S. (1990) SEL: A search method based on orthogonal arrays. In Statistical Design and Analysis of Industrial Experiments, (S. Ghosh ed.), Marcel Dekker, New York, pp. 279–310.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Istat, Servizio Studi Metodologici, Via A. Depretis 74/B, 00184, Rome, Italy

    LUISA FRANCONI

  2. School of Mathematical Sciences, University of Bath, Claverton Down, Bath, BA2 7AY, UK

    CHRISTOPHER JENNISON

Authors
  1. LUISA FRANCONI
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. CHRISTOPHER JENNISON
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

FRANCONI, L., JENNISON, C. Comparison of a genetic algorithm and simulated annealing in an application to statistical image reconstruction. Statistics and Computing 7, 193–207 (1997). https://doi.org/10.1023/A:1018538202952

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018538202952

Search

Navigation