Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal

  • Focus
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

Multi-objective algorithms are aimed to obtain a set of solutions, called Pareto set, covering the whole Pareto front, i.e. the representation of the optimal set of solutions. To this end, the algorithms should yield a wide amount of near-optimal solutions with a good diversity or spread along this front. This work presents a study on different coarse-grained distribution schemes dealing with Multi-Objective Ant Colony Optimization Algorithms (MOACOs). Two of them are a variation of independent multi-colony structures, respectively having a fixed number of ants in every subset or distributing the whole amount of ants into small sub-colonies. We introduce in this paper a third method: an island-based model where the colonies communicate by migrating ants, following a neighbourhood topology which fits to the search space. All the methods are aimed to cover the whole PF, thus each sub-colony or island tries to search for solutions in a limited area, complemented by the rest of colonies, in order to obtain a more diverse high-quality set of solutions. The models have been tested by implementing them considering three different MOACOs: two well-known and CHAC, an algorithm previously proposed by the authors. Three different instances of the bi-Criteria travelling salesman problem have been considered. The experiments have been performed in a parallel environment (inside a cluster platform), in order to get a time improvement. Moreover, the system scaling factor with respect to the number of processors will be also analysed. The results show that the proposed Pareto-island model and its novel neighbourhood topology performs better than the other models, yielding a more diverse and more optimized set of solutions. Moreover, from the algorithmic point of view, the proposed algorithm, named CHAC, yields the best results on average.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. We have chosen this acronym instead of the extended MACS in order to distinguish the algorithm of the preceding MACS by Gambardella et al. (1999).

  2. Obviously the colonies does not find solutions below the Pareto front.

  3. The rest of the tradeoff study boxplots can be found at: http://geneura.ugr.es/~amorag/papers/i-moacos_soco.

  4. http://www.r-project.org.

  5. There are 9 approaches, so there are 8 degrees of freedom or possible values con compare with a given one.

References

  • Alba E, Leguizamón G, Ordoñez G (2007) Two models of parallel ACO algorithms for the minimum tardy task problem. Int J High Perform Syst Archit 1(1):50–59

    Article  Google Scholar 

  • Bai H, OuYang D, Li X, He L, Yu H (2009) Max–Min Ant System on GPU with CUDA. In: Proceedings of the 2009 fourth international conference on innovative computing. information and control, IEEE Computer Society, pp 801–804

  • Barán B, Schaerer M (2003) A multiobjective ant colony system for vehicle routing problem with time windows. In: IASTED International Multi-Conference on Applied Informatics, Vol 21 in IASTED IMCAI, pp 97–102

  • Bolondi M, Bondanza M (1993) Parallelizzazione di un Algoritmo per la Risoluzione del Problema del Commesso Viaggiatore. Master’s thesis, Dipartimento di Elettronica, Politecnico di Milano

  • Bullnheimer B, Hartl RF, Strauss C (1998) Parallelization strategies for the Ant System. In: High performance algorithms and software in nonlinear optimization; applied optimization, vol 24

  • Cantú-Paz E (1999) Topologies, migration rates, and multi-population parallel genetic algorithms. In: Genetic and evolutionary computation conference, GECCO-99, pp 13–17

  • Catalá A, Jaen J, Mocholí JA (2007) Strategies for accelerating ant colony optimization algorithms on graphical processing units. In: Proceedings of the 2007 IEEE Congress on Evolutionary Computation (CEC-2007), pp 492–500

  • Cheng J, Zhang G, Li Z, Li Y (2012) Multi-Objective Ant Colony Optimization Based on Decomposition for Bi-Objective Traveling Salesman Problems. Soft Comput 16:597–614

    Article  MATH  Google Scholar 

  • Coello CA, Veldhuizen DA, Lamont GB (2002) Evolutionary algorithms for solving multi-objective problems. Kluwer, Dordrecht

  • Croes G (1958) A method for solving traveling salesman problems. Oper Res 6:791–812

    Article  MathSciNet  Google Scholar 

  • Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, Hoboken

  • Deneubourg JL, Pasteels JM, Verhaeghe JC (1983) Probabilistic behaviour in ants: a strategy of errors? J Theor Biol 105:259–271

    Article  Google Scholar 

  • Dickinson P., Chow B. (1971) Some properties of the tukey test to Duckworth’s specification. Office of Institutional Research, University of Southwestern Louisiana, Lafayette, Louisiana

  • Doerner K, Hartl RF, Kiechle G, Lucka M, Reimann M (2004) Parallel ant systems for the capacitated vehicle routing problem. In: European conference on evolutionary computation in combinatorial optimization (EVOCop 2004), LNCS 3004, pp 72–83

  • Dorigo M, Maniezzo V, Colorni A (1996) The Ant System: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B Cybern 26(1):29–41

    Article  Google Scholar 

  • Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1(1):53–66

    Article  Google Scholar 

  • Dorigo M, Di Caro G (1999) The ant colony optimization meta-heuristic. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw-Hill, New York, pp 11–32

  • Dorigo M, Stützle T (2002) The ant colony optimization metaheuristic: algorithms, applications, and advances. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer, Dordrecht, pp 251–285

  • Durillo JJ, Nebro AJ, Alba E (2010) The jMetal framework for multi-objective optimization: design and architecture. In: IEEE conference on evolutionary computation CEC-2010, pp 4138–4325

  • Fisher RA (1925) Theory of statistical estimation. Proc Camb Phil Soc 22:700–725

    Article  MATH  Google Scholar 

  • Fonseca CM, Fleming PJ (1996) On the performance assessment and comparison of stochastic multiobjective optimizers. In: Fourth international conference on parallel problem solving from nature (PPSN-IV), LNCS, vol 1141, pp 584–593

  • Fu J, Lei L, Zhou G (2010) A parallel ant colony optimization algorithm with GPU acceleration based on all-in-roulette selection. In: Proceedings of the 3rd international workshop on advanced computational intelligence, pp 260–264

  • Gambardella L, Taillard E, Agazzi G (1999) MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization, McGraw-Hill, New York, pp 73–76

  • García-Martínez C, Cordón O, Herrera F (2007) A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. Eur J Oper Res 180(1):116–148

    Article  MATH  Google Scholar 

  • Grassé P-P (1959) La Reconstruction du Nid et les Coordinations Inter-Individuelles chez Bellicositermes Natalensis et Cubitermes sp. la Theorie de la Stigmerie. Insects Soc 6:41–80

    Article  Google Scholar 

  • Gropp W, Lusk E, Doss N, Skjellum A (1996) A high-performance, portable implementation of the MPI message passing interface standard. Parallel Comput 22(6):789–828

    Article  MATH  Google Scholar 

  • Iredi S, Merkle D, Middendorf M (2001) Bi-criterion optimization with multi colony ant algorithms. In: Zitzler E, Deb K, Thiele L, Coello CAC, Corne D (eds) Proceedings of the first international conference on evolutionary multi-criterion optimization (EMO 2001). Volume 1993 of Lecture Notes in Computer Science. Springer, Berlin, pp 359–372

  • Janson S, Merkle D, Middendorf M (2005) Parallel Metaheuristics. In: Alba E (ed) Parallel ant algorithms. Wiley, London

  • Jovanovic R, Tuba M, Simian D (2010) Comparison of different topologies for island-based multi-colony ant algorithms for the minimum weight vertex cover problem. WSEAS Trans Comput 9(1)

  • Knowles J (2005) A summary-attainment-surface plotting method for visualizing the performance of stochastic multiobjective optimizers. In: Proceedings of the IEEE international conference on intelligent systems design and applications (ISDA 2005), pp 552–557

  • Knowles J, Thiele L, Zitzler E (2006) A tutorial on the performance assessment of stochastic multiobjective optimizers. Tech. Rep. 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich

  • Krüger F, Middendorf M, Merkle D (1998) Studies on a parallel ant system for the BSP model. Unpublished manuscript

  • Lawler EL, Lenstra JK, Kan AHGR, Shmoys DB (1985) (eds), The traveling salesman problem. Wiley, Hoboken

  • Li N, Gao D, Gong G, Chen Z (2010) Realization of parallel ant colony algorithm based on TBB multi-core platform. Proc Int Forum Inf Technol Appl 1:177–180

    Google Scholar 

  • López-Ibañez M, Stützle T (2010) The impact of design choices of multiobjective ant colony optimization algorithms on performance: an experimental study on the biobjective TSP. In: Proceedings of the 2010 Genetic and Evolutionary Computation Conference (GECCO-2010), pp 71–78

  • Manfrin M, Birattari M, Stützle T, Dorigo M (2006) Parallel ant colony optimization for the travelling salesman problem. In: ANTS 2006, LNCS 4150, pp 224–234

  • Michel R, Middendorf M (1998) An island model based ant system with lookahead for the shortest supersequence problem. In: Fifth international conference on parallel problem solving from nature (PPSN-V)

  • Middendorf M, Reischle F, Schmeck H (2000) Information exchange in multi colony ant algorithms. In: Proceedings of the 15 IPDPS 2000 workshops on parallel and distributed processing

  • Middendorf M, Reischle F, Schmeck H (2002) Multi colony ant algorithms. J Heurist 8:305–320

    Article  MATH  Google Scholar 

  • Mocholí JA, Jaen J, Canos JH (2005) A grid ant colony algorithm for the orienteering problem. In: Proceedings of the 2005 IEEE Congress on Evolutionary Computation (CEC-2005), pp 942–949

  • Mora AM, Merelo JJ, Laredo JLJ, Millán C, Torrecillas J (2009) CHAC, a MOACO algorithm for computation of bi-criteria military unit path in the battlefield: presentation and first results. Int J Intell Syst 24(7):818–843

    Article  MATH  Google Scholar 

  • Mora AM, Merelo JJ, Castillo PA, Arenas MG (2011) hCHAC: a family of MOACO algorithms for the resolution of the bi-criteria military unit pathfinding problem. Comput Oper Res. doi:10.1016/j.cor.2011.11.015

  • Mora AM, Merelo JJ, Castillo PA, Arenas MG, García-Sánchez P, Laredo JLJ, Romero G (2011) A study of parallel approaches in MOACOs for solving the bicriteria TSP. In: Proceedings of the international work conference on artificial neural networks (IWANN 2011), Part II. Special session in bio-inspired combinatorial optimization, LNCS 6692, pp 316–324

  • Osyczka A (1985) Multicriteria optimization for engineering design. In: John SG (ed) Design optimization. Academic Press, New York, pp 193–227

  • Pareto V (1896) Cours D’Economie Politique, volume I and II. F. Rouge, Lausanne

  • Pedemonte M, Nesmachnow S, Cancela H (2011) A survey on parallel ant colony optimization. Appl Soft Comput 11(8):5181–5197

    Article  Google Scholar 

  • Randall M, Lewis A (2002) A parallel implementation of ant colony optimization. J Parallel Distrib Comput 62(9):1421–1432

    Article  MATH  Google Scholar 

  • Sameh A, Ayman A, Hasan N (2010) parallel ant colony optimization. Int J Res Rev Comput Sci 1(2):77–82

    Google Scholar 

  • Stützle T (1998) Parallelization strategies for ant colony optimization. In: Fifth international conference on parallel problem solving from nature (PPSN-V), LNCS, vol 1498, pp 722–741

  • Talbi EG, Roux O, Fonlupt C, Robilliard D (1999) Parallel ant colonies for combinatorial optimization problems. In: IPPS/SPDP Workshops

  • Twomey C, Stützle T, Dorigo M, Manfrin M, Birattari M (2010) An analysis of communication policies for homogeneous multi-colony ACO algorithms. Inf Sci 180(12):2390–2404

    Article  Google Scholar 

  • Weis G, Lewis A (2009) Using XMPP for ad-hoc grid computing - an application example using parallel ant colony optimisation. In: Proceedings of the international symposium on parallel and distributed processing, pp 1–4

  • Yu B, Yang Z-Z, Xie J-X (2011) A parallel improved ant colony optimization for multi-depot vehicle routing problem. J Oper Res Soc 62(1):183–188

    Article  Google Scholar 

  • Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans Evol Comput 3(4):257–271

    Article  Google Scholar 

Download references

Acknowledgments

This work has been supported in part by HPC-Europa 2 project (with the support of the European Commission—Capacities Area—Research Infrastructures), and the P08-TIC-03903 project awarded by the Andalusian Regional Government, the FPU Grant 2009-2942, the TIN2011-28627-C04-02 project, the University of Granada PR-PP-2011-5 project and, in part, by the MUSES project (number 318508—FP7).

Author information

Authors and Affiliations

  1. ATC Department, University of Granada, Granada, Spain

    A. M. Mora, P. García-Sánchez, J. J. Merelo & P. A. Castillo

Authors
  1. A. M. Mora
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. García-Sánchez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. J. Merelo
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. P. A. Castillo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. M. Mora.

Additional information

Communicated by E. Alba.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mora, A.M., García-Sánchez, P., Merelo, J.J. et al. Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal. Soft Comput 17, 1175–1207 (2013). https://doi.org/10.1007/s00500-013-0993-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-013-0993-y

Keywords

Search

Navigation