Optimiranje razmještaja oznaka na zemljopisnim kartama

magistarski rad

• Naslov (engleski): Map labeling problem
• Autor: Dejan Gambin
• Mentor: Leo Budin (mentor)
• Član povjerenstva: Leo Budin (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; (Zavod za elektroniku, mikroelektroniku, računalne i inteligentne sustave); Zagreb
• Datum i država obrane: 2001, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo
• Univerzalna decimalna klasifikacija (UDC): 004 - Računalna znanost i tehnologija. Računalstvo. Obrada podataka

Sažetak

Genetski algoritmi, kao podskup evolucijskih algoritama, čine jedan poseban model strojnog učenja zasnovan na zakonima prirodne selekcije i evolucije. Zbog svojih svojstava predstavljaju robusnu metodu optimiranja i danas se koriste za rješavanje čitavog niza različitih problema. Označavanje zemljopisnih karata važno je područje u kartografiji i spada u red teških kombinacijskih problema. U radnji se ispituje uporaba genetskih algoritama u problemima označavanja zemljopisnih karata. Najprije se uvode osnove genetskih algoritama, opisuju njihova svojstva i način funkcioniranja Slijedi podroban opis problema označavanja karata sa osvrtom na postojeće metode koje ga rješavaju. Nadalje se za ovaj problem izgrađuje genetski algoritam sa bogatim skupom parametara. Nudi se mnoštvo mogućnosti od inicijalizacije kromosoma, izbora roditelja i zamjene potomcima, odabira funkcije cilja, standardnih i problemski specifičnih operatora križanja i mutacije, pa sve do konačnih izvješća i analiza. Algoritam se testira uz različite kombinacije ulaznih parametara, te se vrši statička i dinamička analiza dobivenih rezultata radi utvrđivanja kvalitete konvergencije. Također se dobiveni rezultati uspoređuju sa rezultatima ostalih metoda primijenjenih na isti problem. Rezultati ispitivanja ukazuju na prednost uporabe modela stacionarne zamjene sa elitizmom i specifičnim operatorima križanja, dok je utjecaj mutacije zanemariv. Tako odabrana konfiguracija daje najbolje rezultate uz najmanju osjetljivost na promjenu parametara.

Sažetak (engleski)

Genetic algorithms, as a subset of evolutionary algorithms, make a special model of device learning based on principles of natural selection and evolution. Because of their features, they represent a robust optimization method and are used to solve many different problems. Map labeling is a very important area in cartography and is considered a difficult combinatorial problem. This master thesis tries to investigate the usage of genetic algorithms to solve the map labeling problem. After the introduction of the basic principles and description of fundamentals of genetic algorithms, the map labeling problem is described in details and the existing methods for map labeling are presented. Then, a genetic algorithm is constructed with a rich set of possible choices: initialization of the first generation, selection and replacement strategies, fitness function, standard and problem specific crossover and mutation operators and final reports and analysis. The algorithm is tested against the various combinations of input parameters and the quality of convergence is evaluated. The final results are also compared with the results of other methods applied to the same problem. The results of testing show the advantage of using the steady-state model with elitism and specific crossover operators, while mutation operator is almost irrelevant. Such configuration gives the best results and it is less sensitive to parameter changes.

• Ključne riječi: Genetski algoritmi; optimiranje; genetski operatori; problem; označavanje zemljopisnih karata; razmještanje oznaka; pozicija oznake; preklapanje oznaka
• Ključne riječi (engleski): Genetic algorithms; optimisation; genetic operators; problem; map labeling; placing labels; label positioning; label overlap
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:141187
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: poslijediplomski znanstveni (magistarski); Akademski / stručni naziv: magistar inženjer računarstva (mag. ing. comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-05-22 13:24:22