Zastosowanie algorytmu mrówkowego do wyznaczania maksymalnej grupy wzajemnie połączonych elementów
Wariant tytułu
ANT algorithms for determining maximum group of interconnected elements
Autor
Schiff, Krzysztof
Opublikowane w
Czasopismo Techniczne. Elektrotechnika
Numeracja
R. 105, Z. 17, 1-E
Data wydania
2008
Miejsce wydania
Kraków
Wydawca
Wydawnictwo PK
Język
polski
Abstrakt
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.
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.
