Skip to main content

Advertisement

SpringerLink
Log in

OMEGA one multi ethnic genetic approach

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

The genetic algorithm (GA) is a quite efficient paradigm to solve several optimization problems. It is substantially a search technique that uses an ever-changing neighborhood structure related to a population which evolves according to a number of genetic operators. In the GA framework many techniques have been devised to escape from a local optimum when the algorithm fails in locating the global one. To this aim we present a variant of the GA which we call OMEGA (One Multi Ethnic Genetic Approach). The main difference is that, starting from an initial population, \(k\) different sub-populations are produced at each iteration and they independently evolve in \(k\) different environments. The resulting sub–populations are then recombined and the process is iterated. Our basic algorithmic scheme is tested on a recent and well-studied variant of the classic problem of the minimum spanning tree: the Minimum Labeling Spanning Tree problem. We compare our algorithm with several approaches drawn from the literature. The results are encouraging in view of future application of OMEGA to other classes of problems.

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.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

References

  1. Baker, J.M.: Adaptive speciation: the role of natural selection in mechanisms of geographic and non-geographic speciation. Stud. Hist. Philos. Sci. Part C Stud. Hist. Philos. Biol. Biomed. Sci. 36(2), 303–326 (2005)

    Article  Google Scholar 

  2. Barricelli, N.: Numerical testing of evolution theories. Acta Biotheoretica 16(1–2), 69–98 (1962)

    Article  Google Scholar 

  3. Captivo, M., Clímaco, J., Pascoal, M.: A mixed integer linear formulation for the minimum label spanning tree problem. Comput. Oper. Res. 36(11), 3082–3085 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Carrabs, F., Cerulli, R., Gaudioso, M., Gentili, M.: Lower and upper bounds for the spanning tree with minimum branch vertices. Comput. Optim. Appl. 56(2), 405–438 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  5. Cerrone, C., Cerulli, R., Raiconi, A.: Relations, models and a memetic approach for three degree-dependent spanning tree problems. Eur. J. Oper. Res. 232(3), 442–453 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  6. Cerulli, R., Fink, A., Gentili, M., Voss, S.: Metaheuristics comparison for the minimum labelling spanning tree problem. In: Golden, B.L., Raghavan, S., Wasil, E.A. (eds.) The next wave on computing, optimization, and decision technologies, pp. 93–106. Springer, Berlin (2005)

  7. Chang, R.S., Shing-Jiuan, L.: The minimum labeling spanning trees. Inf. Process. Lett. 63, 277–282 (1997)

    Article  Google Scholar 

  8. Consoli, S., Moreno-Prez, J.A., Mladenovic, N.: Intelligent variable neighbourhood search for the minimum labelling spanning tree problem. Electron. Notes Discrete Math. 41, 399–406 (2013)

    Article  Google Scholar 

  9. Cordeau, J.F., Gaudioso, M., Laporte, G., Moccia, L.: A memetic heuristic for the generalized quadratic assignment problem. INFORMS J. Comput. 18(4), 433–443 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  10. Fraser, A.: Simulation of genetic systems by automatic digital computers. I. Introd. Aust. J. Biol. Sci. 10, 484–491 (1957)

    Google Scholar 

  11. Fraser, A.: Computer models in genetics. McGraw-Hill, New York (1970)

    Google Scholar 

  12. Goldberg, D.E.: Genetic algorithms in search. Optimization and machine learning. Addison-Wesley Longman Publishing Co., Inc., Boston (1989)

    MATH  Google Scholar 

  13. Grefenstette, John J. Lamarckian learning in multi-agent environments. Navy Center For Applied Research in Artificial Intelligence Washington DC, (1995)

  14. Holland, J.H.: Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press (1975)

  15. Krumke, S., Wirth, H.: On the minimum label spanning tree problem. Inf. Process. Lett. 66(2), 81–85 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  16. Moscato, P., Norman, M.G.: A memetic approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems. Parallel Comput. Transput. Appl. 1, 177–186 (1992)

    Google Scholar 

  17. Miettinen, K., Mäkelä, M.M., Neittaanmäki, P., Periaux, J. (eds.): Evolutionary algorithms in engineering and computer science. Wiley, Chichester (1999)

    MATH  Google Scholar 

  18. Nummela, J., Julstrom, B.: An effective genetic algorithm for the minimum-label spanning tree problem. In: GECCO ’06 Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp. 553–558 (2006)

  19. Reed, J., Toombs, R., Barricelli, N.: Simulation of biological evolution and machine learning. I. Selection of self-reproducing numeric patterns by data processing machines, effects of hereditary control, mutation type and crossing. J. Theoret Biol. 17, 319–342 (1967)

    Article  Google Scholar 

  20. Xiong, Y., Golden, B., Wasil, E.: A one-parameter genetic algorithm for the minimum labeling spanning tree problem. IEEE Trans. Evolut. Comput. 9(1), 55–60 (2005)

    Article  Google Scholar 

  21. Xiong, Y., Golden, B., Wasil, E.: Improved heuristics for the minimum label spanning tree problem. IEEE Trans. Evol. Comput. 10(6), 700–703 (2006)

    Article  Google Scholar 

  22. Whitley, D., Rana, S., Heckendorn, R.B.: The island model genetic algorithm: on separability, population size and convergence. J. Comput. Inf. Technol. 7, 33–48 (1999)

    Google Scholar 

  23. Latter, B.D.H.: The island model of population differentiation: a general solution. Genetics 73(1), 147–157 (1973)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Matematica, Universitá di Salerno, 84084, Fisciano, SA, Italy

    Carmine Cerrone & Raffaele Cerulli

  2. Dipartimento di Ingegneria Informatica, Modellistica, Elettronica e Sistemistica, Universitá della Calabria, 87036, Rende, CS, Italy

    Manlio Gaudioso

Authors
  1. Carmine Cerrone
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raffaele Cerulli
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Manlio Gaudioso
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Manlio Gaudioso.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cerrone, C., Cerulli, R. & Gaudioso, M. OMEGA one multi ethnic genetic approach. Optim Lett 10, 309–324 (2016). https://doi.org/10.1007/s11590-015-0852-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-015-0852-0

Keywords

Search

Navigation