Zastosowanie algorytmu genetycznego do rozwiązywania problemu pokrycia wierzchołkowego

licenciate
dc.abstract.enThe aim of this thesis was to implement genetic algorithm to solve vertex cover problem for chosen undirected graphs. For comparison greedy algorithm was implemented. Firstly, theoretical foundation regarding vertex cover problem, algorithms’ functional principles and terminology were covered. Having conducted tests for five graphs, each of different vertex and edge count, the results were shown and briefly discussed. The application created in the process allows presenting the way the algorithms work, as well as visualisation of the graphs. Its graphical user interface allows reading graph data files and choosing genetic algorithm’s parameters, such as mutation and crossover rates or population size. The application was written in Java and as for the visualisation, Prefuse library was used.pl
dc.abstract.plCelem pracy było zaimplementowanie algorytmu genetycznego do rozwiązania problemu pokrycia wierzchołkowego dla wybranych grafów nieskierowanych. Dla porównania zaimplementowano algorytm zachłanny. Na początku omówiono podstawy teoretyczne dotyczące problemu pokrycia wierzchołkowego, zasady działania algorytmów i dotyczącą je terminologię. Przeprowadzono testy algorytmów dla pięciu grafów o różnej liczbie wierzchołków i krawędzi, na podstawie których przedstawiono i omówiono wyniki. Aplikacja stworzona w tym celu, oprócz pokazania działania algorytmów, umożliwia również wizualizację grafów. Graficzny interfejs użytkownika pozwala na wczytanie pliku z grafem i dobór parametrów algorytmu genetycznego, takich jak współczynniki mutacji i krzyżowania, czy wielkość populacji. Aplikacja została napisana w języku Java, do wizualizacji grafów posłużyła biblioteka Prefuse.pl
dc.affiliationUniwersytet Jagielloński w Krakowiepl
dc.contributor.advisorPaszyńska, Anna - 160672 pl
dc.contributor.authorMizera, Magdalenapl
dc.contributor.departmentbycodeUJK/UJKpl
dc.contributor.reviewerGórski, Adampl
dc.contributor.reviewerPaszyńska, Anna - 160672 pl
dc.date.accessioned2021-11-19T22:37:54Z
dc.date.available2021-11-19T22:37:54Z
dc.date.submitted2021-11-16pl
dc.fieldofstudyinformatyka stosowanapl
dc.identifier.apddiploma-151826-226986pl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/284203
dc.languagepolpl
dc.subject.engenetic algorithm, vertex cover, graphs, Java, greedy algorithm, Prefuse, GraphMLpl
dc.subject.plalgorytm genetyczny, pokrycie wierzchołkowe, grafy, Java, algorytm zachłanny, Prefuse, GraphMLpl
dc.titleZastosowanie algorytmu genetycznego do rozwiązywania problemu pokrycia wierzchołkowegopl
dc.title.alternativeGenetic algorithm application to solving vertex cover problempl
dc.typelicenciatepl
dspace.entity.typePublication
dc.abstract.enpl
The aim of this thesis was to implement genetic algorithm to solve vertex cover problem for chosen undirected graphs. For comparison greedy algorithm was implemented. Firstly, theoretical foundation regarding vertex cover problem, algorithms’ functional principles and terminology were covered. Having conducted tests for five graphs, each of different vertex and edge count, the results were shown and briefly discussed. The application created in the process allows presenting the way the algorithms work, as well as visualisation of the graphs. Its graphical user interface allows reading graph data files and choosing genetic algorithm’s parameters, such as mutation and crossover rates or population size. The application was written in Java and as for the visualisation, Prefuse library was used.
dc.abstract.plpl
Celem pracy było zaimplementowanie algorytmu genetycznego do rozwiązania problemu pokrycia wierzchołkowego dla wybranych grafów nieskierowanych. Dla porównania zaimplementowano algorytm zachłanny. Na początku omówiono podstawy teoretyczne dotyczące problemu pokrycia wierzchołkowego, zasady działania algorytmów i dotyczącą je terminologię. Przeprowadzono testy algorytmów dla pięciu grafów o różnej liczbie wierzchołków i krawędzi, na podstawie których przedstawiono i omówiono wyniki. Aplikacja stworzona w tym celu, oprócz pokazania działania algorytmów, umożliwia również wizualizację grafów. Graficzny interfejs użytkownika pozwala na wczytanie pliku z grafem i dobór parametrów algorytmu genetycznego, takich jak współczynniki mutacji i krzyżowania, czy wielkość populacji. Aplikacja została napisana w języku Java, do wizualizacji grafów posłużyła biblioteka Prefuse.
dc.affiliationpl
Uniwersytet Jagielloński w Krakowie
dc.contributor.advisorpl
Paszyńska, Anna - 160672
dc.contributor.authorpl
Mizera, Magdalena
dc.contributor.departmentbycodepl
UJK/UJK
dc.contributor.reviewerpl
Górski, Adam
dc.contributor.reviewerpl
Paszyńska, Anna - 160672
dc.date.accessioned
2021-11-19T22:37:54Z
dc.date.available
2021-11-19T22:37:54Z
dc.date.submittedpl
2021-11-16
dc.fieldofstudypl
informatyka stosowana
dc.identifier.apdpl
diploma-151826-226986
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/284203
dc.languagepl
pol
dc.subject.enpl
genetic algorithm, vertex cover, graphs, Java, greedy algorithm, Prefuse, GraphML
dc.subject.plpl
algorytm genetyczny, pokrycie wierzchołkowe, grafy, Java, algorytm zachłanny, Prefuse, GraphML
dc.titlepl
Zastosowanie algorytmu genetycznego do rozwiązywania problemu pokrycia wierzchołkowego
dc.title.alternativepl
Genetic algorithm application to solving vertex cover problem
dc.typepl
licenciate
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
20
Views per month
Views per city
Warsaw
5
Gdansk
3
Opole
3
Dublin
2
Poznan
2
Wroclaw
2
Kamesznica
1
Krakow
1

No access

No Thumbnail Available