An improvement of the ant algorithm for the maximum clique problem

• Autorzy: Schiff K.

Identyfikatory

DOI

10.4467/2353737XCT.15.098.3930

Warianty tytułu

PL

Udoskonalenie algorytmu mrówkowego do wyznaczania kliki maksymalnej

• Języki publikacji: EN

Abstrakty

EN

The maximum clique problem is a very well-known NP-complete problem and for such a problem, meta-heuristic algorithms have been developed which ant algorithms belongs to. There are many algorithms including ant algorithms that have been elaborated for this problem. In this paper, a new dynamic function of selecting with a new improvement procedure in order to get a larger size of clique for the ant algorithm is presented and this search for the maximum clique in graph is compared to the best ant algorithms that are already known.

PL

Problem kliki maksymalnej przynależy do klasy problemów NP-zupełnych i dla takich problemów opracowuje się obecnie algorytmy metaheurystyczne, do których zaliczają się algorytmy mrówkowe. W niniejszym artykule prezentowany jest algorytm mrówkowy z dynamiczną funkcją wyboru wierzchołków włączanych do tworzonej kliki przez każdą mrówkę wraz z procedurą poprawy wymiaru otrzymanej kliki poprzez wymianę wierzchołków, a otrzymany algorytm został porównany z innymi już dotychczas opublikowanymi.

Słowa kluczowe

EN

maximum clique; ant algorithm; desirability function

PL

klika maksymalna; algorytmy mrówkowe; funkcja pożądania

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Elektrotechnika
• Rocznik: 2015
• Tom: Y. 112, iss. 2-E
• Strony: 225--233
• Opis fizyczny: Bibliogr. 6 poz., wz., rys., tab., wykr.

Twórcy

autor

Schiff K.

• Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology

Bibliografia

• [1] Dorigo M., Ant Algorithms for Discrete Optimization, Artificial Life, 1999, Vol. 5, No. 2, pp. 137–172.
• [2] Tang N., Finding Maximum Cliques with Distributed Ants, GECCO 2004, LNCS 3102, pp. 24–35.
• [3] Fenet S., Solnon C., Searching for Maximum Cliques with Ant Colony Optimization, EvoWorkshops 2003, LNCS 2611, pp. 236–245.
• [4] Xu X., Ma J., Lee J., An Improved Ant Colony Optimization for the Maximum Clique Problem, IEEE Third International Conference on Natural Computation, 2007.
• [5] Rizzo J., An Ant System Algorithm for Maximum Clique, Master Thesis, The Pennsylvania State University, 2003.
• [6] Schiff K., Ant colony optimization algorithms for clustering problems, Technical Transaction – Automatic Control, 2013, Y-110, 4-AC, pp. 77–87.