Comparison of reproduction strategies in genetic algorithm approach to graph searching

• Autorzy: Wrona Ł. , Jaworski B.

Warianty tytułu

PL

Porównanie strategii krzyżowania w odniesieniu do wykorzystania algorytmów ewolucyjnych w problemie przeszukiwania grafów

• Języki publikacji: EN

Abstrakty

EN

Genetic algorithms (GA) are a well-known tool used to obtain approximate solutions to optimization problems. Successful application of a genetic algorithm in solving given problem is largely dependant on selecting appropriate genetic operators. Selection, mutation and crossover techniques play a fundamental role in both time needed to obtain results and their accuracy. In this paper we focus on applying genetic algorithms in calculating (edge) search number and search strategy for general graphs. Our genetic representation of problem domain is based on representing search strategy as a permutation of edges and fitness function is based on the number of searchers needed to perform a given strategy. Our implementation of GA is utilized to compute search strategies for selected graph classes. We compare and discuss results obtained while employing different reproduction strategies.

PL

Algorytmy genetyczne to znane narzędzie służące do otrzymywania dokładnych wyników w problemach optymalizacyjnych. Skuteczna implementacja algorytmu genetycznego celem rozwiązania zadanego problemu zależy w dużej mierze od wyboru odpowiednich operatorów genetycznych. Selekcja, techniki krzyżowania i mutacja odgrywają fundamentalną rolę zarówno w kwestii redukcji czasu potrzebnego na otrzymanie zadowalającego rozwiązania, jak i dokładności takowego. W tym artykule koncentrujemy się na implementacji algorytmów genetycznych celem wyliczenia liczby przeszukiwania (krawędzi) i strategii przeszukiwania dla grafów ogólnych. Reprezentacja genetyczna domeny problemu polega na przedstawieniu strategii przeszukiwania poprzez permutację krawędzi, a liczba przystosowania reprezentuje liczbę agentów potrzebnych do zrealizowania danej strategii.

Słowa kluczowe

EN

reproduction strategies; genetic algorithm; graph searching

PL

strategie krzyżowania; algorytmy ewolucyjne; problem przeszukiwania grafów

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2010
• Tom: T. 18
• Strony: 359--364
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Wrona Ł.

autor

Jaworski B.

• Gdansk University of Technology Department of Algorithms and System Modelling

Bibliografia

• [1] Breich R.L.: An intuitive approach to speleotopology, Southwestern Cavers 6, 1967.
• [2] Parsons T.D.: Pursuit-Evasion in a graph. Lecture Notes in Mathematics. 1976, p. 426421.
• [3] Fomin V.F., Thilikos M.D.: An annotated bibliography on guaranteed graph searching, Theor. Comput. Sci., 2008, 399(3), p. 236258. Nowak K.: Dydaktyczny model łączenia sieci LAN za pomocą sieci rozległych, WETI PG, 2002.
• [4] Alspach B.: Searching and sweeping graphs. A brief survey, Prairie Discrete Math Workshop 2004.
• [5] Wrona L., Jaworski B.: Application of genetic algorithms in graph searching problem. In: Proceedings of the 2nd International Conference on Information Technology ICIT 2010.
• [6] Megiddo N., et al.: The complexity of searching a graph, J. ACM 35 1988, 1 p. 1844.
• [7] Kowalski A., Kabacki K.: Simulation of Network Systems in Education. In: Proceedings of the XXIV Autumn International Colloquium Advanced Simulation of Systems. ASIS 2002, September 911 2002, Ostrava, Czech Republic., s. 213218.
• [8] Eiben E.A., Smith J.E.: Introduction to Evolutionary Computing, Springer 2003.