An Automated Selection Model of Ditch Based on Multi-objective

Optimization by Genetic Algorithm

R. Zhai

Institute of Surveying and Mapping, Information Engineering University, Zhengzhou, China

chxy_zrj@163.com

Abstract: It’s a key and difficulty to consider the self-characteristic and keep the distributing characteristic of ditch that is a structural selection, which is multi-objective optimization actually. Combining the basic generalization principle of ditch, considering quality characteristic of single ditch and selection results of ditch holistically, and keeping the distributing characteristic, an automated selection model of ditch based on genetic multi-objective optimization is developed.

As a network, ditch is denseness, which is described by route system model, entity of ditch is represented by a whole route, and classified on modality, intersection types of which are concluded into: cross（╋）, left intersection（┫）, right intersection（┣）, concept of ditch relation is proposed. Knowledge rules of ditch selection are summarized. Evaluation of ditch about importance includes structure and quality characteristic, when selecting, importance of quality characteristic is represented by knowledge rules and constraint in genetic algorithm, which is used to evaluate the reservation of structure characteristic. The model adopts layered method in selection, which combines the quality characteristic attribute of ditch first, selects ditches according to knowledge rules initially, therefore, necessary and deleted ditches are distinguished; remaining ditches is selected by genetic algorithm structurally, according to distributing characteristic of ditch, combining constraint code and M kinds of selection case created by local searching strategy, objective function of ditch selection is designed, and proper adapted function is developed, which is used to evaluate each selection case, iterative calculation is done continually, genetic algorithm isn’t stopping until evolving to satisfied the convergence condition, and optimized selection result is got finally.

At last, data of dense ditches (scale 1:250,000) is experimented by the model, each factor influencing the selection of model is compared and analyzed, and three factors influencing model selection are given, which are the selection sums of ditches, minimum space between ditches, adding few “primary” ditches in initial selection. Experiments show that the model is not only considering the ditches’ quality characteristics, but also keeping graphical distribution of ditches. The model is suitable for varieties of ditches, with certain intelligence.

Key Words: automatic map generalization; Genetic Algorithm; ditch network; ditch selection