Application of Genetic algorithms in graph searching problem

• Autorzy: Wrona Ł. , Jaworski B.

Warianty tytułu

PL

Zastosowanie algorytmów genetycznych w problemie przeszukiwania grafów

• Języki publikacji: EN

Abstrakty

EN

Graph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in an environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called the (edge) search strategy. Unfortunately calculating both the optimal search strategy and the search number is NP-hard for general graphs. Furthermore, due to the complexity of the pursuit rules, the application of heuristic solutions is not straightforward. In this paper we suggest a method of applying genetic algorithms to solve graph searching problem. The idea is based on LaPaugh's result on graph searching monotonicity and utilizes representation of a search strategy as a permutation of edges.

PL

Przeszukiwanie grafów to często stosowane podejście do problemu przechwytywania wrogiej jednostki przez grupę mobilnych agentów. Zadanie to jest realizowane w środowisku zamodelowanym za pomocą grafu G. Odpowiadamy na pytanie ile mobilnych agentów jest niezbędnych by przechwycić dowolnie szybkiego, niewidzialnego i bystrego intruza. Liczba ta jest nazywana (krawędziową) liczbą przeszukiwawczą G a strategia, którą realizują agenci - (krawędziową) strategią przeszukiwawczą. Zarówno wyznaczanie liczby przeszukiwawczej jak i strategii przeszukiwawczej jest trudne obliczeniowo. Dodatkowo, ze względu na złożoność zasad, według których odbywa się przechwytywanie, stosowanie podejścia heurystycznego jest utrudnione. W tej pracy sugerujemy metodę zastosowania algorytmów genetycznych w rozwiązywaniu omawianego problemu. W pomyśle wykorzystany jest lemat LaPaugha, dotyczący monotoniczności przeszukiwania grafów i zakłada reprezentację strategii przeszukiwawczej jako permutacji krawędzi.

Słowa kluczowe

EN

genetic algorithms; graph searching problem

PL

algorytmy genetyczne; przeszukiwanie 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: 353--358
• Opis fizyczny: Bibliogr. 10 poz., rys.

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.
• [4] LaPaugh A.S.: Recontamination does not help to search a graph, J. ACM 40 1993, 2 p. 224–245.
• [5] Megiddo N., et al.: The complexity of searching a graph, J. ACM 35 1988, 1 p. 18–44.
• [6] Wrona L.: Methods of capturing moving objects by mobile agents, Master’s Thesis (In Polish), Gdansk University of Technology 2006.
• [7] Cytowski J.: Genetic Algorithms - Fundamentals and Applications (in Polish), Akademicka Oficyna Wyd. 1996.
• [8] Goldberg D.E.: Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co, 1989
• [9] Bienstock D., Seymour P.: Monotonicity in graph searching, J. Algorithms 12 1991, 2 p. 239–245.
• [10] Wrona L., Jaworski B.: Comparison of reproduction strategies in genetic algorithm approach to graph searching. In: Proceedings of the 2nd International Conference on Information Technology ICIT 2010.