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
Erschienen in:
Managing Natural Noise in Recommender Systems Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

A Discrete Artificial Bee Colony Algorithm Based on Similarity for Graph Coloring Problems

verfasst von : Kui Chen, Hitoshi Kanoh

Erschienen in: Theory and Practice of Natural Computing

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this paper, a novel non-hybrid discrete artificial bee colony (ABC) algorithm is proposed for solving planar graph coloring problems. The original ABC intends to handle only continuous optimization problems. To apply ABC to discrete problems, the original ABC operators need to be redefined over discrete space. In this work, a new algorithm based on Similarity is introduced. Compared with HDPSO, the experiment shows that the proposed method matches the competitive results and obtains higher success rate and lower average evaluation times when solving planar graph coloring problems.

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 "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

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
Vorheriges Kapitel How to Implement a Random Bisection Cut
Nächstes Kapitel A Multi-objective Evolutionary Approach to Pareto Optimal Model Trees. A Preliminary Study
Literatur
1.
Beni, G., Wang, J.: Swarm intelligence in cellular robotic systems. Robots and Biological Systems: Towards a New Bionics?, vol. 102, pp. 703–712. Springer, Heidelberg (1993)CrossRef
2.
Kennedy, J., Eberhart Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948 (1995)
3.
Krause, J., Cordeirol, J., Parpinelli, R.S., Heitor S.L.: A survey of swarm algorithms applied to discrete optimization problems. Swarm Intelligence and Bio-Inspired Computation, pp. 169–191 (2013)
4.
Cui, G., Qin, L., Liu, S., Wang, Y., Zhang, X., Cao, X.: Modified PSO algorithm for solving planar graph coloring problem. Progress Nat. Sci. 18, 353–357 (2008)CrossRef
5.
Hsu, L.-Y., Fan, P., Horng, S.-J., Khurram, M., Wang, Y.-R., Run, R.-S., Lai, J.-L., Chan, R.-J.: MTPSO algorithm for solving planar graph coloring problem. Expert Syst. Appl. 38, 5525–5531 (2001)CrossRef
6.
Zhang, K., Zhu, W., Liu, J., He, J.: Discrete particle swarm optimization algorithm for solving graph coloring problem. In: 10th International Conference Bio-Inspired Computing - Theories and Applications, pp. 643–652 (2015)
7.
Aoki, T., Aranha, C., Kanoh, H.: PSO algorithm with transition probability based on hamming distance for graph coloring problem. In: IEEE International Conference on Systems, Man, and Cybernetics, pp. 1956–1961 (2015)
8.
Qu, R., Burke, E.K.: Hybridizations within a graph-based hyper-heuristic framework for University timetabling problems. J. Oper. Res. Soc. 60, 1273–1285 (2009)CrossRefMATH
9.
Fen, H.S., Safaai, D., Hashim, M., Zaiton, S.: University course timetable planning using hybrid particle swarm optimization. In: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, pp. 239–246 (2009)
10.
Kanoh, H., Chen, S.: Particle swarm optimization with transition probability for timetabling problems. In: Tomassini, M., Antonioni, A., Daolio, F., Buesser, P. (eds.) ICANNGA 2013. LNCS, vol. 7824, pp. 256–265. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-37213-1_​27 CrossRef
11.
Dorigo, M., Stutzle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)MATH
12.
Kanoh, H., Ochiai, J.: Solving time-dependent traveling salesman problems using ant colony optimization based on predicted traffic. In: International Symposium on Distributed Computing and Artificial Intelligence, Advances in Intelligent and Soft Computing, vol. 151, pp. 25–32 (2012)
13.
Karaboga, D., Basturk, B., Owerful, A.: Efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J. Global Optim. 39, 459–471 (2007)MathSciNetCrossRefMATH
14.
Pan, Q.K., Tasgetiren, M.F., Suganthan, P.N., Chua, T.J.: A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Inf. Sci. 181(12), 2455–2468 (2011)MathSciNetCrossRef
15.
Tasgetiren, M.F., Pan, Q.K., Suganthan, P.N., Chen, A.H.-L.: A discrete artificial bee colony algorithm for the total flowtime minimization and permutation flow shops. Inf. Sci. 181(16), 3459–3475 (2011)MathSciNetCrossRef
16.
Fister Jr., I., Fister, I., Brest, J.: A hybrid artificial bee colony algorithm for graph 3-coloring. Swarm Evol. Comput. 7269, 66–74 (2012)CrossRef
17.
Karaboga, D., Basturk, A.: A survey: algorithms simulating bee swarm intelligence. Artif. Intell. Rev. 31(1–4), 61–85 (2009)CrossRef
18.
Minton, S., Johnston, M.D., Philips, A.B., Laird, P.: Minimizing conflicts: a heuristic repair mehod for constraint-satisfaction and scheduling problems. Artif. Intell. 58, 161–205 (1992)MathSciNetCrossRefMATH
19.
Hogg, T., Williams, C.: The hardest constraint problems, a double phase transition. Artif. Intell. 69(1–2), 359–377 (1994)CrossRefMATH
20.
Deep, K., Bansal, J.C.: A socio-cognitive particle swarm optimization for multi-dimentional knapsack problem. In: First International Conference on Emerging Trends in Engineering an Technology, pp. 355–360 (2008)
21.
Shen, X., Li, Y., Chen, C., Yang, J., Zhang, D.: Greedy continuous particle swarm optimization algorithm for the knapsack problems. Int. J. Comput. Appl. Technol. 44(2), 137–144 (2012)CrossRef
22.
Ucar, H., Tasgetiren, M.F.: A particle swarm optimization algorithm for permutation flow shop sequencing problem with the number of tardy jobs criterion. In: 5th International Symposium on Intelligent Manufacturing Systems, pp. 237–250 (2006)
23.
Algorithms, S., Yang, X.S.: Firefly algorithm for multimodal optimization. Found. Appl. 5792, 169–178 (2009)
24.
Sayadi, M.K., Ramezanian, R., Ghaffari-Nasab, N.: A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. Int. J. Ind. Eng. Comput. 1(1), 1–10 (2010)
25.
Palit, S., Sinha, S.N., Molla, M.A., Khanra, A., Kule, M.: A cryptanalytic attack on the knapsack cryptosystem using binary firefly algorithm. In: 2nd International Conference on Computer and Communication Technology, pp. 428–432 (2011)
26.
Banati, H., Bajaj, M.: Firefly based feature selection approach. Int. J. Comput. Sci. Issues 8(4), 73–480 (2011)
27.
Fister, I., Yang, X.S., Fister, I., Brest, J.: Memetic firefly algorithm for combinatorial optimization. In: 5th International Conference on Bioinspired Optimization Methods and Their Applications, pp. 75–86 (2012)
28.
Yang, X.S., Deb, S.: Cuckoo search via levy flights. In: World Congress on Nature and Biologically Inspired Computing, pp. 210–214 (2009)
29.
Burnwal, S., Deb, S.: Scheduling optimization of flexible manufacuring system using cuckoo search-based approach. Int. J. Adv. Manuf. Technol. 64(5), 951–959 (2013)CrossRef
30.
Gherboudj, A., Layeb, A., Chikhi, S.: Solving 0–1 knapsack problems by a discrete binary version of cuckoo search algorithm. Int. J. Bio-Inspired Comput. 4(4), 229–236 (2012)CrossRef
Metadaten
Titel
A Discrete Artificial Bee Colony Algorithm Based on Similarity for Graph Coloring Problems
verfasst von
Kui Chen
Hitoshi Kanoh
Copyright-Jahr
2016
Buch
Theory and Practice of Natural Computing

Print ISBN: 978-3-319-49000-7

Electronic ISBN: 978-3-319-49001-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-49001-4_6

Premium Partner

    Bildnachweise