# A Novel Method for Building Displacement Based on Multipopulation Genetic Algorithm
## 1 Introduction  
In automatic cartographic generalization, spatial conflicts (e.g., proximity conflicts or overlap conflicts) often occur between both the same and different features (e.g., between buildings and buildings or between buildings and roads) because of map scale reduction and other cartographic generalization operations. To resolve such conflicts, several generalization operations, such as selection [1], aggregation [2; 3], elimination [4], typification [5; 6], and displacement [7; 8], have been used. Compared with other generalization operations, the displacement operation is the most important and frequently adopted method to resolve spatial conflicts. With the development of big data and artificial intelligence, spatial conflict solutions based on displacement operation in cartographic generalization are facing new challenges (e.g., real-time displacement) [9; 10]. Therefore, it is urgent to explore more effective automatic displacement approaches. Building displacement only slightly moves buildings from their original position to new position on the premise of ensuring positional accuracy, which does not significantly reduce the information content in a map [11]. In the process of displacement, several main issues should be considered. First, the displacement approach should try to resolve all possible spatial conflicts under the constraint of positional accuracy, which indicates that the maximum displacement distance of objects on a map should be limited to a specified range (e.g., 0.5 mm). Second, the displacement operation shouldavoid generating secondary conflicts after moving some map objects. Third, the displacement should maintain the spatial positional relations between individual buildings and the arrangement patterns and distribution characteristics within building groups. However, different constraints may contradict each other, and it is not possible to find a solution that satisfies all constraints completely. Instead, a feasible solution is to find the best compromise among constraints. Therefore, the problem of building displacement can be regarded as the combinatorial optimization problem satisfying multiple cartographic constraints [12], which can be solved by the heuristic search method. The genetic algorithm (GA) [13] is a highly parallel and adaptive global optimal search algorithm based natural selection in the biological world. Because of its strong robustness and global search ability, the GA has been widely used in the cartographic generalization field, such as the geographical feature label placement problem [14], map conflation [15], feature selection [1, 16], and displacement operation [17, 18]. However, with the development of GA research, its shortcomings have gradually been exposed, such as premature convergence. For example, when the GA is used for the displacement of buildings to resolve spatial conflicts, the premature convergence of the GA will cause all individuals in the population to tend to be in the same state and stop evolution, resulting in the algorithm not resolving all defined spatial conflicts. Therefore, we propose a novel building displacement method based on multipopulation genetic algorithm (BDMPGA) to resolve spatial conflicts. The BDMPGA breaks through the structure of traditional GA that only relies on a single population for genetic evolution, which introduces multiple populations with different control parameters to conduct simultaneous optimization searches. The immigration operation is used to realize the information exchange among different populations to maintain the diversity of individuals in the population and obtain the optimal solution. Meanwhile, this method adopts elite retention strategy that the optimal individuals in the population are selected and preserved in the elite population through manual selection operation, and the elite population is also the basis for the termination of the algorithm. The remainder of this article is organized as follows.