Zastosowanie algorytmu mrówkowego do wyznaczania maksymalnej grupy wzajemnie połączonych elementów

• Autorzy: Schiff K.

Warianty tytułu

EN

ANT algorithms for determining maximum group of interconnected elements

• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowano algorytmy mrówkowe wyznaczające największą klikę w grafie, za pomocą której modeluje się problem wyznaczania największego ze skupień wzajemnie połączonych elementów elektronicznych na płytce drukowanej w celu minimalizacji długości połączeń między nimi, a w konsekwencji minimalizacji ilości materiału zużytego na ich wytworzenie. W artykule zaprezentowano algorytm oparty na odmiennych aspektach zachowania się mrówek w porównaniu z dotychczas opracowanymi algorytmami. Główną różnicą między algorytmami jest faza eksploracji, która została wprowadzona w prezentowanym algorytmie. Opracowany algorytm porównano z Algorytmem 457 pod względem wyznaczanego wymiaru klik. Dokonano również porównania procedur lokalnego przeszukiwania (2,1)-wymiany i procedury opartej na metaheurystyce kolonii mrówek.

EN

In this paper an ANT algorithm, which is used to find a maximum group of mutually connected electronic elements in order to minimize the total length of connections, is presented. The new algorithm differs from algorithms which have been presented in scientific papers until now. The main difference is a phase of ANT exploration which is absent in other ANT algorithms. Sizes of maximum clique indicated by ANT algorithm and the Algorithm 457 are compared. The influence of the local search was presented also and the (2,1)-exchange local procedure and the ANT procedure of local search was compared.

Słowa kluczowe

PL

algorytm mrówkowy; algorytmy komputerowe; klika maksymalna; optymalizacja kombinatoryczna; teoria grafów

EN

ant algorithm; combinatorial optimization; computer algorithms; graph theory; maximum clique

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Elektrotechnika
• Rocznik: 2008
• Tom: R. 105, z. 1-E
• Strony: 63--78
• Opis fizyczny: Bibliogr. 19 poz.,Wz., tab.,

Twórcy

autor

Schiff K.

• Katedra Automatyki, Wydział Inżynierii Elektrycznej i Komputerowej, Politechnika Krakowska

Bibliografia

• [1] Abello J., Pardalo s P.M., Resende M.G.C., On Maximum Clique problem in very large graph, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, Vol. 50, American Mathematical Society, 2000, 119-130.
• [2] Auguston G., Mi n k e r J., Analysis of Some Graph theoretic Cluster Techniques, J.ACM 17 (1970), 571-588.
• [3] Karp R.M., Reducibility among combinatorial problems, in Complexity of Computer Computation, [in:] R.E. Miller, J.W. Thatcher (eds.), Plenum Press, New York 1972, 85-103.
• [4] Johnson D.S., Approximation algorithms for the combinatorial problems, Journal of Computer Science 9, 1974, 256-278.
• [5] Battiti R., Protasi M., Reactive local search for the maximum clique problem, Algorithmica 29, 2001, 610-637, praca dostępna w GOOGLE.
• [6] Grosso A., Locatelli M., Della Groce F., Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem, Journal of the Heuristics 10, 2004, 135-152.
• [7] Jagota A., Sanchis L.A., Adaptive, restart, randomized greedy heuristics for the maximum clique, Journal of the Heuristics 7, 2001, 565-585.
• [8] Bron C., Kerbosch J., Algorithm 457: Finding all cliques of an undirected graph, Comm. ACM 16, 1973, 575-577.
• [9] Glover F., Laguna M., Tabu search, [in:] Modern Heuristics Technics for Combinatorial Problems, Blackwell Scientific Publishing, Oxford, UK 1993, 70-141.
• [10] Aarts E.H.L., Korst J.H.M., In simulated annealing and the Boltzmann machines, John Wiley & Sons, Chichester, UK 1989.
• [11] Marchiori E., Genetic, iterated and multistart local search for the maximum clique problem, [in:] Application of Evolutionary Computing, Proc. of Eco Workshops 2002: EvoCOP, EvoIASP, EvoSTim, 2279 of LNCS, Springer-Verlag, 2002, 112-121, praca dostępna w GOOGLE.
• [12] Dorigo M., Di Caro G., The Ant Colony Optimization meta-heuristics, [in:] D. Corne, M. Dorigo, F. Glover (eds.) New Ideas in Optimization, McGraw-Hill, UK 1999, 11-32.
• [13] Dorigo M., GamBardella L.M., Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transaction on Evolutionary Computation 1, 1997, 53-66.
• [14] Elliman D.G., Youssef S.M., Reactive Prohibition-based Ant Colony Optimisation (RPACO): A New Parallel Architecture for Constrained Clique Sub-Graphs, Computer Science Technical Report, No. NOTTCS-TR-2004-7, School of Computer Science and Information Technology, University of Nottingham, UK 2004, praca dostępna w GOOGLE.
• [15] Maniezzo V., Colorni A., The Ant system applied to the quadratic assignment problem, IEEE Transaction on Data and Knowledge Engineering 11, 1999, 769-778.
• [16] Solnon Ch., Fenet S., Investigating ACO capabilities for solving the Maximum clique Problem (raport), University Lyon I, May 24, 2004, praca dostępna w GOOGLE.
• [17] Costa D., Herz A., Ants can colour graphs, Journal of the Operational Research Societz 48, 295-305.
• [18] Corne D., Dorigo M., Glover F., New ideas in Optimization, The McGraw-Hill Companies, Londyn, UK 1999.
• [19] Leguizamon G., Michalewicz Z., A new version of ant system for subsets problems, [in:] Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), Washigton, USA, praca dostępna w GOOGLE.