Received date: 2006-05-29
Revised date: 2006-09-06
Online published: 2006-12-25
Supported by
National Outstanding Youth Foundation of NSF of China, No.40525002; National Natural Science Foundation of China,No.40471105; No.40471106; "985 Project", No.105203200400006; Open Foundation of National Key Lab for Information Engineering in Surveying, Mapping and Remote Sensing in Wuhan University, No.37000-4106130
The solutions to spatial optimal search are complex and important. Since combinatorial optimal problems are computationally difficult, brute-force search can hardly solve the problems. As a result, a novel approach is necessary to deal with them. Particle swarm optimization (PSO) is a new kind of optimal technique, which can solve complex nonlinear spatial optimal problems. This paper demonstrates that PSO solves the spatial optimal search based on GIS under the constraint conditions of population distribution and shortest path. The PSO treats each solution as a particle searching in D-dimensional hyperspace. Different from other optimal problems, the spatial optimal search is in 2-dimensional geographic space, in which each point includes X, Y coordinates. D is equal to 2n. Where n is the number of marketplaces. So the position vector of the particle i is (xi/1, yi/1, xi/2, yi/2, …, xin, yin). Each particle flies over search space and its velocity vector is (vxi/1, vyi/1, vxi/2, vyi/2, …, vxi/n, vyi/n). The particles can adjust their positions and velocities according to the current optimal value p(t) and global optimal value pg/. The work in this paper makes use of the control MapObject2.3 to extract the centroid coordinates, area and population density of each cell in the map of population distribution by means of the computer programming language. It initializes the parameters, computes the fitness value of each particle and finds the current optimal value and global optimal value which adjust the position and velocity of each particle until they satisfy the condition of maximal number of iterations or precision. Finally, it identifies the position of the particle with the global optimal value is the optimal location of the marketplaces. The contents of this paper include: first, this paper introduces the characteristic and research progress about PSO and spatial search. Secondly, the paper elaborates on the implementing procedure and method of spatial optimal search by using PSO and GIS under the constraint condition of population distribution and shortest path. Thirdly, the paper utilizes the 4×4 spatial regions as an example to prove the correctness and effectiveness of the proposed method. Finally, the paper further verifies this method by a case of Fangcun District, Guangzhou. It is concluded that particle swarm optimization is a robust method of solving spatial optimal search under complex conditions.
Key words： particle swarm optimization; GIS; optimal search; Guangzhou city
DU Guoming, CHEN Xiaoxiang, LI Xia . Spatial Optimal Search Based on Particle Swarm Optimization[J]. Acta Geographica Sinica, 2006 , 61(12) : 1290 -1298 . DOI: 10.11821/xb200612006
[1] Angeline P J. Evolutionary optimization versus particle swarm optimization: philosophy and performance difference. Proceedings of the 7th Annual Conference on Evolutionary Programming, 1998. 601-610.
[2] Kennedy J, Spears W M. Matching algorithms to problems: an experimental test of the particle swarm and some genetic algorithms on the multimodal problem generator. Proceedings of IEEE International Conference on Evolutionary Computation, Anchorage, AK, USA, 1998. 78-83.
[3] Ren Bin, Feng Zhenping. Improved genetic algorithm and particle swarm optimization as well as comparison between them. Journal of Nanjing Normal University (Engineering and Technology), 2002, 2(2): 14-20.
[任斌, 丰镇平. 改进遗传算法与粒子群优化算法及其对比分析. 南京师范大学学报 (工程技术版), 2002, 2(2): 14-20.]
[4] Shen Yan, Guo Bing, Gu Tianxiang. Particle swarm optimization algorithm and comparison with genetic algorithm. Journal of UEST of China, 2005, 34(5): 696-699.
[沈艳, 郭兵, 古天祥. 粒子群优化算法及其与遗传算法的比较. 电子科技大学学报, 2005, 34(5): 696-699.]
[5] Kennedy J, Eberhart R C. Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, 1995. 1942-1948.
[6] Kennedy J, Eberhart R C. A new optimizer using particle swarm theory. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan: IEEE, 1995. 39-43.
[7] Openshow S, Steadman P. On the geography of a worst case nuclear attack on population of Britain. Political Geography Quarterly, 1982, (1): 263-278.
[8] Li Xia, Yeh A. Optimal spatial search using genetic algorithms and GIS. Acta Geographica Sinica, 2004, 59(5): 745-753.
[黎夏, 叶嘉安. 遗传算法和GIS结合进行空间优化决策. 地理学报, 2004, 59(5): 745-753.]
[9] Aerts J, Heuvelink G. Using simulated annealing for resource allocation. International Journal of Geographical Information Science, 2002, 16(6): 571-587.
[10] Jaramillo J H, Bhadury J, Batta R. On the use of genetic algorithms to solve location problems. Computers & Operations Research, 2002, 29: 761-779.
[11] Dong Chaojun, Liu Zhiyong, Qiu Zulian. Catastrophe-particle swarm optimization algorithm and its application to traffic control. Computer Engineering and Applications, 2005, 29: 19-23.
[董超俊, 刘智勇, 邱祖廉. 灾变粒子群优化算法及其在交通控制中的应用. 计算机工程与应用, 2005, 29: 19-23.]
[12] Shi Yuhui, Eberhart R C. Parameter selection in particle swarm optimization. The Seventh Annual Conference on Evolutionary Programming, Washington DC, 1998. 591-600.
[13] Clerc M, Kennedy J. The particle swarm explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 58-73.
[14] Krink T, Vesterstroem J S, Riget J. Particle swarm optimization with spatial particle extension. Proceedings of the IEEE Congress on Evolutionary Computation, Honolulu, Hawaii, 2002. 1474-1479.
[15] Secrest B R, Lamont G B. Visualizing particle swarm optimization: Gaussian particle swarm optimization. Proceedings of the IEEE Swarm Intelligence Symposium, Indianapolis, 2003. 198-204.
[16] Van den Bergh F, Engelbrecht A P. Effects of swarm size on cooperative particle swarm optimizers. Genetic and Evolutionary Computation Conference, San Francisco, USA, 2001. 892-899.
[17] Lovbjerg M, Rasmussen T K, Krink T. Hybrid particle swarm optimiser with breeding and subpopulations. Proceeding of Genetic and Evolutionary Computation Conference, Morgan Kaufmann, 2001. 469-476.
[18] Parsopoulos K E, Vrahatis M N. Particle swarm optimization method in multiobjective problems. Proceedings ACM Symposium on Applied Computing, 2002. 603-607.
[19] Ray T, Liew K. M. A swarm with an effective information sharing mechanism for unconstrained and constrained single objective optimization problems. Proceedings of the IEEE International Conference on Evolutionary Computation, Seoul, 2001. 75-80.
[20] Messerschmidt L, Engelbrecht A P. Learning to play games using a PSO-based competitive learning approach. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 280-288.
/
| 〈 |
|
〉 |