基于微粒群优化算法的空间优化决策
收稿日期: 2006-05-29
修回日期: 2006-09-06
网络出版日期: 2006-12-25
基金资助
国家杰出青年基金项目 (40525002); 国家自然科学基金项目 (40471105; 40471106); "985工程"GIS与遥感的地学应用科技创新平台 (105203200400006); 武汉大学测绘遥感信息工程国家重点实验室开放研究基金(37000-4106130)
Spatial Optimal Search Based on Particle Swarm Optimization
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
空间优化决策是GIS应用中复杂而又常见的问题。由于涉及到大量的组合，使用穷举法等方法难以找到最优的解决方案，因此需要运用新的理论方法来解决这类问题。微粒群优化算法是近年来新兴的一种优化技术，与GIS相结合可解决空间优化决策问题。首先，对微粒群优化算法和空间优化决策问题作了简单介绍;然后，基于人口密度、最短距离约束条件下，通过GIS技术，对微粒群优化算法用于空间优化决策的方法、实施过程作了详细阐述;接着，用4×4方格单元对PSO方法的正确性、有效性进行了验证;最后，以广州市芳村区为例，对该方法进行实例验证。通过实验，证明微粒群优化算法具有较好的收敛速度、较高的结果精度，是解决空间优化决策问题的一种有效方法。
杜国明, 陈晓翔, 黎夏 . 基于微粒群优化算法的空间优化决策[J]. 地理学报, 2006 , 61(12) : 1290 -1298 . DOI: 10.11821/xb200612006
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
[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.
/
| 〈 |
|
〉 |