Diplomová práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Evolutionary Approach to Constructing Finite Planar Emulators of Graphs

Bc. Martin Derka, M.Sc.
Anotace

Tato práce zkoumá možnosti využití technik evolučních výpočtů v teorii grafů. Jako vzorový problém vnímáme konstrukci rovinných emulátorů grafů. Provádíme experimenty s celkem třemi technikami - genetickým programováním s dvěma druhy kódování grafů a s genetickými algoritmy s využitím speciálního operátoru pro rekombinaci grafů. Část práce je věnována návrhu funkce, která může být využita k hodnocení úrovně rovinnosti grafů.

Abstract

This work investigates the possible applications of evolutionary computations in graph theory. We adopt constructing finite planar emulators of graphs as the representative problem. We conduct experiments with three techniques --- genetic programming using cellular encoding and edge encoding, and genetic algorithms with a special graph crossover. Part of this work is devoted to designing a fitness function that can be used for scoring planar graphs.

Zadání práce
The problem of finding a finite planar emulator of a non-projective graph, or proving that it does not exist, is without any doubt extremely difficult. So far, there is no known universal method that would guarantee obtaining a result (not even by brute force). Student's task is to explore the option of using evolutionary computations, i.e. genetic algorithms and genetic programming, for constructing finite planar emulators of graphs. Part of the problem is to propose a fitness measure of planarity that would be suitable for use within such techniques.
Práce zkontrolována:
28. 5. 2013 09:09, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
838,3 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
26. 6. 2013
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponenti

Reshma Ramadurai, PhD.
prof. RNDr. Petr Hliněný, Ph.D., učo 168881

 
Název
Vložil
Vloženo
Práva
  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.
  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.
  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.
  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.
  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.