Optimiranje razmještaja oznaka na zemljopisnim kartama

scientific master's theses

• Title (english): Map labeling problem
• Author: Dejan Gambin
• Mentor: Leo Budin (mentor)
• Committee member: Leo Budin (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Electronics, Microelectronics, Computer and Intelligent Systems); Zagreb
• Defense date and country: 2001, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Universal decimal classification (UDC): 004; GENERALLY; Computer science and technology. Computing. Data processing

Abstract

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.

Abstract (english)

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.

• Keywords: Genetski algoritmi; optimiranje; genetski operatori; problem; označavanje zemljopisnih karata; razmještanje oznaka; pozicija oznake; preklapanje oznaka
• Keywords (english): Genetic algorithms; optimisation; genetic operators; problem; map labeling; placing labels; label positioning; label overlap
• Language: croatian
• URN:NBN: urn:nbn:hr:168:141187
• Study programme: Title: Postgraduate master programe in computing; Study programme type: university; Study level: postgraduate; Academic / professional title: magistar inženjer računarstva (magistar inženjer računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-05-22 13:24:22