Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Soft Computing
Erschienen in: Soft Computing 1/2011

01.01.2011 | Original Paper

\(\epsilon\)- DANTE : an ant colony oriented depth search procedure

verfasst von: Pedro Cardoso, Mário Jesus, Alberto Márquez

Erschienen in: Soft Computing | Ausgabe 1/2011

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The \(\epsilon\)-Depth ANT Explorer (\(\epsilon\)- DANTE ) algorithm applied to a multiple objective optimization problem is presented in this paper. This method is a hybridization of the ant colony optimization algorithm with a depth search procedure, putting together an oriented/limited depth search. A particular design of the pheromone set of rules is suggested for these kinds of optimization problems, which are an adaptation of the single objective case. Six versions with incremental features are presented as an evolutive path, beginning in a single colony approach, where no depth search is applied, to the final \(\epsilon\)- DANTE . Versions are compared among themselves in a set of instances of the multiple objective Traveling Salesman Problem. Finally, our best version of \(\epsilon\)- DANTE is compared with several established heuristics in the field showing some promising results.
Vorheriger Artikel Unit commitment problem using enhanced particle swarm optimization algorithm
Nächster Artikel Polynomial permutations on bounded commutative directoids with an antitone involution

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The used problems are combinations of the single objective problems with the same prefix (kro) available at the TSPLib. Files are truncated to obtain the 50 node instances, and pairwise combined to obtain the multiple objectives (Jaszkiewicz 2002).
 
2
We notice that comparing \({{\mathcal{P}}}_0\) with non-dominated subset of the union of the results obtained with five runs for each of the Multiple Objective Genetic Local Search (MOGLS), Multiple Objective Simulated Annealing (MOSA), and MOSA-like MOGLS algorithms (Jaszkiewicz 2002, 2006; Ishibuchi and Murata 1998) [results available at (Jaszkiewicz 2006)],\({{\mathcal{P}}}'_0,\) the C metric value were equal to \(C({{\mathcal{P}}}'_0,{{\mathcal{P}}}_0) = 0.34829\) and \(C({{\mathcal{P}}}_0,{{\mathcal{P}}}'_0) = 0.99517\).
 
3
The total run time was 1,800 s although for the comparisons, and unless stated otherwise, we consider the 300 s computation time. The objective of using the 1,800 s running time was to obtain a more accurate approximation set to serve as a reference set.
 
4
In Table 6, the intersection of row i with column j presents the value of p and the confidence interval at 95% for the Mann–Whitney paired test. When p is small (<0.05) we use symbol ▿ to indicate that we should reject the null hypothesis, that is, we can reject the idea that the observed differences are a coincidence and conclude that the populations have different medians (in our case, \({{\mathcal{S}}}(V_i)\) is shifted to the right of \({{\mathcal{S}}}(V_j)\)). If p is large, marked with symbol \(\blacktriangle ,\) the data does not allow us to conclude that the medians are different, which is not the same as to say that they are equal. For instance, row 1 column 2 has p = 0.00 and the confidence interval \((0.1,\infty).\) In this case, since p is small the null hypothesis should be rejected, accepting that \({{\mathcal{S}}}(V_1)\) is shifted to the right of \({{\mathcal{S}}}(V_2).\) This fact is corroborated by the confidence interval. We can conclude that statistically V 1 has a larger \({{\mathcal{S}}}\) value than V 2.
 
5
A beanplot (Kampstra 2008) combines an 1d-scatter plot and a density trace, being an alternative to boxplots. In a beanplot, the individual observations are shown as small (white color) lines in a one-dimensional scatter plot. Next to that, the estimated density of the distributions is visible and the average is shown (black color region).
 
6
For the sake of clarity, only the best eleven variants are presented, which correspond to those with hyper-volume ratio larger than 0.99. We should notice that these variants were the same for every problem instance (kroAC50, kroAD50, and kroAE50).
 
7
Although \(\epsilon\)D.1 was considered the best variant in Sect. 4.3, \(\epsilon\)D.3 \(\equiv\) \(\epsilon\)Dc was the best performing variant for a broader set of instances (see Sect. 5).
 
Literatur
Aarts E, Lenstra J (1997) Local search in combinatorial optimization. Wiley-Interscience Series in discrete mathematics and optimization. Wiley, London
Barán B, Schaerer M (2003) A multiobjective ant colony system for vehicle routing problem with time windows. In: 21st IASTED International Multi-Conference on Applied Informatics, Innsbruck, Austria, pp 97–102
Blum C (2005a) Ant colony optimization: introduction and recent trends. Phys Life Rev 2(4):353–373CrossRef
Blum C (2005b) Beam–ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling. Comput Oper Res 32(6):1565–1591CrossRef
Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Surv (CSUR) 35(3):268–308CrossRef
Bui L, Essam D, Abbass H, Green D (2001) Performance analysis of evolutionary multiobjective optimization methods in noisy environments. Tech. Rep. TR-ALAR-200504006, University of New South Wales, Australia
Camerini P, Galbiati G, Maffioli F (1983) On the complexity of finding multi-constrained spanning trees. Discret Appl Math 5:39–50MATHCrossRefMathSciNet
Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, London
Deb K, Pratap A, Agarwal S, Meyarivan T (2000) A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6:182–197CrossRef
Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30MathSciNet
Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge
Dorigo M, Bonabeau E, Theraulaz G (1999) Swarm intelligence: from natural to artificial systems. Oxford University Press, Oxford
Ehrgott M, Gandibleux X (2004) Approximative solution methods for multiobjective combinatorial optimization. TOP 12(1):1–63MATHCrossRefMathSciNet
Gambardella L, Dorigo M (2000) An ant colony system hybridized with a new local search for the sequential ordering problem. INFORMS J Comput 12(3)
Gambardella LM, Taillard E, Agazzi G (1999) Macs-vrptw: a multiple ant colony system for vehicle routing problems with time windows. New ideas in optimization, pp 63–76
García S, Herrera F (2008) Design of experiments in computational intelligence: on the use of statistical inference. In: HAIS ’08: Proceedings of the 3rd international workshop on hybrid artificial intelligence systems. Springer, Berlin, pp 4–14. doi:10.​1007/​978-3-540-87656-4_​3
García S, Molina D, Lozano M, Herrera F (2009) A study on the use of non-parametric tests for analyzing the evolutionary algorithms behaviour: a case study on the CEC2005 special session on real parameter optimization. J Heuristics 15(6):617–644MATHCrossRef
García S, Fernandez A, Luengo J, Herrera F (2009) A study of statistical techniques and performance measures for genetics-based machine learning: accuracy and interpretability. Soft Comput 13(10):959–977CrossRef
García-Martínez C, Cordón O, Herrera F (2004) An empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. ANTS Workshop, Lecture Notes in Computer Science 3172:61–72
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 127(1):116–148CrossRef
Garey M, Johnson D (1990) Computers and intractability; a guide to the theory of NP-Completeness. W. Freeman & Co., New York
Glover F, Laguna M (1997) Tabu search. Kluwer, Dordrecht
Ishibuchi H, Murata T (1998) Multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans Syst Man Cybern 3(28):392–403
Jaszkiewicz A (2001) Multiple objective metaheuristic algorithms for combinatorial optimization. PhD thesis, Poznan University of Technology
Johnson S (2001) Emergence. The connected lives of ants, brains, cities, and software. Scribner
Kampstra P (2008) Beanplot: a boxplot alternative for visual comparison of distributions. J Stat Softw Code Snippets 28(1):1–9
Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220(4598):671–680
Knowles J (2002) Local-search and hybrid evolutionary algorithms for pareto optimization. PhD thesis, University of Reading, UK
Knowles J, Corne D (2000a) Approximating the nondominated front using the pareto archived evolution strategy. Evol Comput MIT Press 8(22):149–172CrossRef
Knowles J, Corne D (2000b) M-PAES: a memetic algorithm for multiobjective optimization. In: Proceedings of the 2000 Congress on evolutionary computation, vol 1. IEEE Press, La Jolla, pp 325–332
Knowles J, Corne D (2001) A comparative assessment of memetic, evolutionary, and constructive algorithms for the multiobjective d-MST problem. In: 2nd Workshop on memetic algorithms, WOMA2001, pp 162–167
Levine J, Ducatelle F (2004) Ant colony optimisation and local search for bin packing and cutting stock problems. J Oper Res Soc Special Issue on Local Search 55(7):705–716MATH
Mann H, Whitney D (1947) On a test of whether one of two random variables is stochastically larger than the other. Ann Math Stat 18:50–60MATHCrossRefMathSciNet
Middendorf M, Reischle F, Schmeck H (2002) Multi colony ant algorithms. J Heuristics 8:305–320MATHCrossRef
Miettinen K (1999) Nonlinear multiobjective optimization. Kluwer, Dordrecht
Murata T (1997) Genetic algortithms for multi-objective optimization. PhD thesis, Osaka Prefecture University
Paquete L, Stützle T (2003) A two-phase local search for the biobjective traveling salesman problem. In: Fonseca C, Fleming P, Zitzler E, Deb K, Thiele L (eds) Second International Conference on evolutionary multi-Criterion optimization, EMO 2003, vol 2632. Faro, Portugal, pp 479–493
Paquete L, Stützle T (2006) A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices. Eur J Oper Res 169(3):943–959MATHCrossRef
Parmee I (2001) Evolutionary and adaptive computing in engineering design. Springer, London, iSNB:1-85233-029-5
Reimann M, Laumanns M (2004) A hybrid aco algorithm for the capacitated minimum spanning tree problem. In: Blum C, Roli A, Sampels M (eds) First International Workshop on hybrid metaheuristics (HM 2004). Valencia, Spain, pp 1–10
Reimann M, Doerner K, Hartl R (2004) D-ants: savings based ants divide and conquer the vehicle routing problem. Comput Oper Res 31(4):563–591MATHCrossRef
Romero C (1993) Teorí a de la decisión multicritério: conceptos, técnicas y aplicaciones (in spanish). Alianza Universidad Textos
Talbi EG (2002) A taxonomy of hybrid metaheuristics. J Heuristics 8(5):541–564CrossRef
Ulungu E, Teghem J, Fortemps P, Tuyttens D (1999) MOSA method: a tool for solving multiobjective combinatorial optimization problems. J Multi-Criteria Decis Anal 8(4):221 – 236MATHCrossRef
Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. PhD thesis, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland
Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans Evol Comput 3(4):257–271CrossRef
Zitzler E, Deb K, Thiele L (2000) Comparison of multiobjective evolutionary algorithms: empirical results. Evol Comput 8:173–195CrossRef
Zitzler E, Thiele L, Laumanns M, Fonseca C, Fonseca V (2002) Why quality assessment of multiobjective optimizers is difficult. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2002), pp 666–674
Zitzler E, Thiele L, Laumanns M, Fonseca C, Fonseca V (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2):117–132CrossRef
Metadaten
Titel
- DANTE : an ant colony oriented depth search procedure
verfasst von
Pedro Cardoso
Mário Jesus
Alberto Márquez
Publikationsdatum
01.01.2011
Verlag
Springer-Verlag
Erschienen in
Soft Computing / Ausgabe 1/2011
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-010-0543-9

Weitere Artikel der Ausgabe 1/2011

Soft Computing 1/2011 Zur Ausgabe

Focus

Engineering presentation of the stochastic interpolation framework and its applications

Focus

A mixed integer genetic algorithm used in biological and chemical defense applications

Original Paper

Gene expression studies with DGL global optimization for the molecular classification of cancer

Focus

A destructive evolutionary algorithm process

Focus

Genetic programming of the stochastic interpolation framework: convection–diffusion equation

Original Paper

Solving fuzzy linear systems

Premium Partner

    Bildnachweise