Skip to main content
SpringerLink
Log in

Multi-Objective Optimization using Grid Computing

  • Original Paper
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

This paper analyzes some technical and practical issues concerning the use of parallel systems to solve multi-objective optimization problems using enumerative search. This technique constitutes a conceptually simple search strategy, and it is based on evaluating each possible solution from a given finite search space. The results obtained by enumeration are impractical for most computer platforms and researchers, but they exhibit a great interest because they can be used to be compared against the values obtained by stochastic techniques. We analyze here the use of a grid computing system to cope with the limits of enumerative search. After evaluating the performance of the sequential algorithm, we present, first, a parallel algorithm targeted to multiprocessor systems. Then, we design a distributed version prepared to be executed on a federation of geographically distributed computers known as a computational grid. Our conclusion is that this kind of systems can provide to the community with a large and precise set of Pareto fronts that would be otherwise unknown.

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

Similar content being viewed by others

References

  1. Alba E, Tomassini M (2002) Parallelism and evolutionary algorithms. IEEE Trans Evol Comput 6(5):443–462

    Article  Google Scholar 

  2. Alba E, Troya JM (1999) A survey of parallel distributed genetic algorithms. Complexity 4(4):31–52

    Article  MathSciNet  Google Scholar 

  3. Aloisio G, Blasi E, Cafaro M, Epicoco I, Fiore S, Mocavero S (2003) A grid environment for diesel engine chamber optimization. In: Proceedings of ParCo2003

  4. Anstreicher K, Brixius N, Goux J-P, Linderoth J (2002) Solving large quadratic assignment problems on computational grids. Mathe Program 91:563–588

    Article  MathSciNet  MATH  Google Scholar 

  5. Baker M, Buyya R, Laforenza D (2002) Grids and grid technologies for wide area distributed computing. Soft Prac Exp 32:1437–1466

    Article  MATH  Google Scholar 

  6. Berman F, Fox GC, Hey AJG (2003) Grid comptuing. making the global infrastructure a reality. In: Communications networking and distributed systems. Wiley New York

  7. Coello CA (1999) A comprehensive survey of evolutionary-based multiobjective optimization techniques. Knowl Inf Sys Int J 1(3):269–308

    Google Scholar 

  8. Coello CA, Van Veldhuizen DA, Lamont GB (2002) Evolutionary algorithms for solving multi-objective problems. In: Genetic algorithms and evolutionary computation. Kluwer Dordrecht

  9. Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, New York

    MATH  Google Scholar 

  10. Deb K, Zope P, Jain A (2002) Distributed computing of pareto-optimal solutions using multi-objective evolutionary algorithms. Technical Report 2002, KanGAL

  11. Fonseca CM, Flemming PJ (1995) An overview of evolutionary algorithms in multiobjective optimization. Evol Comput 3(1):1–16

    Google Scholar 

  12. Foster I, Kesselman C (1997) Globus: a metacomputing infraestructure toolkit. Int J Supercomput Appl 11(2):115–128

    Article  Google Scholar 

  13. Foster I, Kesselman C (1999) The grid: blueprint for a new computing infrastructure. Morgan-Kaufmann, San Francisco

    Google Scholar 

  14. Gendron B, Crainic TG (1994) Parallel branch and bound algorithms: survey and synthesis. Oper Res 42:1042–1066

    Article  MathSciNet  MATH  Google Scholar 

  15. Grama A, Kumar V (1999) State of the art in parallel search techniques for discrete optimization. IEEE Trans Knowl Data Eng 11(1):28–35

    Article  Google Scholar 

  16. Grimshaw A, Wulf W (1997) The legion vision of a worldwide virtual computer. Commun ACM 40(1) 1995

  17. Kurpati A, Azarm S, Wu J (2002) Constraint handling improvements for multi-objective genetic algorithms. Struct Multidisciplinary Optimization, 23(3):204–213

    Article  Google Scholar 

  18. Migdalas A, Pardalos PM, Story S (1997) Parallel computing in optimization applied optimization, Vol 7. Kluwer, Dordrecht

    Google Scholar 

  19. Neary MO, Cappello P (2002) Advanced eager scheduling for Java-based adaptively parallel computing. In: Procedings of the ACM Java grande/ISCOPE conference, pp 56–65

  20. Osyczka A (1985) Multicriteria optimization for engineering. Academic, London

    Google Scholar 

  21. Tanimura Y, Hiroyasu T, Miki M, Aoi K (2002) The System for evolutionary computing on the computational grid. In: Parallel and distributed computing and systems (PDCS 2002)

  22. Thain D, Tannenbaum T, Livny M (2002) Condor and the grid. In: Berman F, Fox G, Hey T (eds). Grid Computing: making the global infrastructure a reality. Wiley, New York

    Google Scholar 

  23. UEA CALMA Group (1995) CALMA project report 2.4: parallelism in combinatorial optimisation. Technical report, School of Information Systems, University of East Anglia, Norwch, UK

    Google Scholar 

  24. Van Veldhuizen DA, Lamont GB (2000) Multiobjective evolutionary algorithms: analyzing the state-of-the-art. Evol Comput 8(2):125–147

    Article  Google Scholar 

  25. Van Veldhuizen DA, Zydallis JB, Lamont GB (2003) Considerations in engineering parallel multiobjective evolutionary algorithms. IEEE Trans Evol Comput 87(2):144 –173

    Article  Google Scholar 

  26. Wright SJ (2000) Solving optimization problems on computational grids. Technical report, Mathematics and Computer Science Division, Argonne National Latoratory, Argonne, IL

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Lenguajes y Ciencias de la Computación, E.T.S. Ingeniería Informática, Universidad de Málaga, Office 3.2.15 Campus de Teatinos, 29071, Malaga, Spain

    Antonio J. Nebro

  2. Departamento de Lenguajes y Ciencias de la Computación, E.T.S. Ingeniería Informática, Universidad de Málaga, Office 3.2.12 Campus de Teatinos, 29071, Malaga, Spain

    Enrique Alba

  3. Departamento de Lenguajes y Ciencias de la Computación, E.T.S. Ingeniería Informática, Universidad de Málaga, Office 3.3.4 Campus de Teatinos, 29071, Malaga, Spain

    Francisco Luna

Authors
  1. Antonio J. Nebro
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Enrique Alba
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Francisco Luna
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Antonio J. Nebro.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Nebro, A.J., Alba, E. & Luna, F. Multi-Objective Optimization using Grid Computing. Soft Comput 11, 531–540 (2007). https://doi.org/10.1007/s00500-006-0096-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-006-0096-0

Keywords

Search

Navigation