基于蚁群算法的城市中压配电网络规划研究
|
摘要
配电网规划是电力系统规划的重要组成部分,对其进行科学合理的规划,寻求最佳电网投资决策可以获得巨大的经济和社会效益。中压配电网规划是根据变电站的容量及用户的负荷容量,设计最佳的网络结构,给用户提供长期稳定、并能满足用户需求的电能。其涉及线路的辐射状、网络损耗、供电可靠性等约束,是一个非线性、多目标、多约束问题。
在分析和研究国内外配电网络规划方法的基础上,针对配电网络的辐射型、连通性特点,本文对基本的蚁群算法进行了改进,给出了适合于沿街铺设中压配电网络规划的算法。现将本文的主要成果总结如下:
(1)结合数据库技术,加强了软件对配电网络规划的通用性与灵活性。当有新增加负荷或路径时,现有规划策略只需对数据表进行微调即可满足要求。
(2)根据城市中压配电网络规划问题的具体特征,对基本蚁群算法进行了改进。从状态转移准则、信息素初始化、信息素更新等方面改进后的蚁群算法在扩大搜索解空间的同时加快了算法运行速度,取得了比较满意的效果。
(3)提出了以城区街道为配电网络基础结构,保证“辐射型”的配电网络规划方法。该算法中在决定蚂蚁行走方向时引入启发因子(基于街道段负荷指标),极大地提高了配电网络规划的效率,区别于以往文献中的以负荷点为结点的点对点网络铺设,对实际工作更具有指导意义。
对某开发区远景年、近景年分别进行了实例应用分析,结果表明本文提出的基于街道段上负荷指标的启发信息与蚁群算法相结合的网络规划方法能够在保证计算速度的前提下,得到较好的规划方案,进而节省了配电网络规划费用。
Distribution network planning is an important component of power system planning. The great economic and social benefits will be achieved by the aid of scientific planning and optimal power network investment decision. In order to supply abundant and high-qualified power to customers, mid-voltage (MV) distribution network planning needs to provide a powerful and flexible scheme based on the substation capacity and the load capacity. To sum up, distribution network planning is a nonlinear, multi-objective, multi-constraint optimal problem, and is associated with the radiate power line routing, network-loss and power supply reliability etc.
After analyzing the radiate and connective characters of distribution network, this paper reformulates the existing Ant Colony Algorithm (ACA), on which a new approach for the MV distribution network planning applied in real streets is created.
(1) The universality and flexibility of our developed software for distribution network planning is enhanced by combining the database design. So when any additional loads or street paths are encountered, our proposed approach can work well after slightly adjusting the related parameters.
(2) Found on the specialties of urban MV distribution network, the ACA is reformulated including the state transfer principles, the pheromone initialization and pheromone update. The reformulated method can obtain a satisfied solution in extending searching scope and better computing speed for distribution network planning.
(3) Using real streets as the basis of conceiving distribution network, a novel approach of urban MV distribution network planning subject to the radiate restriction is proposed. In this strategy, directive factor is introduced when the ant choices a street path that can improve the distribution network planning effectively. Different from the existing design which adopted the point to point way, our proposed distribution network planning method has much more meanings for actual planning work.
Theoretical analysis and experiments show that our proposed method, which combines the directive factor with the ACA, can be applied to the practical situations, and contributes a better design to the urban MV distribution network planning.
在分析和研究国内外配电网络规划方法的基础上,针对配电网络的辐射型、连通性特点,本文对基本的蚁群算法进行了改进,给出了适合于沿街铺设中压配电网络规划的算法。现将本文的主要成果总结如下:
(1)结合数据库技术,加强了软件对配电网络规划的通用性与灵活性。当有新增加负荷或路径时,现有规划策略只需对数据表进行微调即可满足要求。
(2)根据城市中压配电网络规划问题的具体特征,对基本蚁群算法进行了改进。从状态转移准则、信息素初始化、信息素更新等方面改进后的蚁群算法在扩大搜索解空间的同时加快了算法运行速度,取得了比较满意的效果。
(3)提出了以城区街道为配电网络基础结构,保证“辐射型”的配电网络规划方法。该算法中在决定蚂蚁行走方向时引入启发因子(基于街道段负荷指标),极大地提高了配电网络规划的效率,区别于以往文献中的以负荷点为结点的点对点网络铺设,对实际工作更具有指导意义。
对某开发区远景年、近景年分别进行了实例应用分析,结果表明本文提出的基于街道段上负荷指标的启发信息与蚁群算法相结合的网络规划方法能够在保证计算速度的前提下,得到较好的规划方案,进而节省了配电网络规划费用。
Distribution network planning is an important component of power system planning. The great economic and social benefits will be achieved by the aid of scientific planning and optimal power network investment decision. In order to supply abundant and high-qualified power to customers, mid-voltage (MV) distribution network planning needs to provide a powerful and flexible scheme based on the substation capacity and the load capacity. To sum up, distribution network planning is a nonlinear, multi-objective, multi-constraint optimal problem, and is associated with the radiate power line routing, network-loss and power supply reliability etc.
After analyzing the radiate and connective characters of distribution network, this paper reformulates the existing Ant Colony Algorithm (ACA), on which a new approach for the MV distribution network planning applied in real streets is created.
(1) The universality and flexibility of our developed software for distribution network planning is enhanced by combining the database design. So when any additional loads or street paths are encountered, our proposed approach can work well after slightly adjusting the related parameters.
(2) Found on the specialties of urban MV distribution network, the ACA is reformulated including the state transfer principles, the pheromone initialization and pheromone update. The reformulated method can obtain a satisfied solution in extending searching scope and better computing speed for distribution network planning.
(3) Using real streets as the basis of conceiving distribution network, a novel approach of urban MV distribution network planning subject to the radiate restriction is proposed. In this strategy, directive factor is introduced when the ant choices a street path that can improve the distribution network planning effectively. Different from the existing design which adopted the point to point way, our proposed distribution network planning method has much more meanings for actual planning work.
Theoretical analysis and experiments show that our proposed method, which combines the directive factor with the ACA, can be applied to the practical situations, and contributes a better design to the urban MV distribution network planning.
引文
[1]陈章潮,唐德光,城市电网规划与改造,中国电力出版社,1998
[2]刘健,杨文宇,余健明等,基于改进最小生成树算法并考虑负荷不确定性的配电网架最优规划,电网技术,2005,29(16):61~65
[3]陈庭记,程浩忠,何明等,城市中压配电网接线模式研究,电网技术,2000,24(9):35~38
[4]张菁,基于两联络接线模式的联络线优化研究:[硕士学位论文],天津大学,2007
[5]蓝毓俊,现代城市电网规划设计与建设改造,北京冲国电力出版社,2004
[6]张宪,基于GIS的配电网网架规划的研究:[硕士学位论文],华北电力大学,2006
[7]王赛一,王成山,基于多目标模型的城市中压配电网络规划,中国电力,2006,39 (11):46~50
[8] Miguez E, Cidras J, Diaz-Dorado E, et al, An improved branch-exchange algorithm for large-scale distribution network planning, IEEE Transactions on Power Systems, 2002, 17(4): 931~936
[9] Miranda V, Ranito J V, Procenca L M. Genetic Algorithms in Optimal Multistage Distribution Network Planning[J]. IEEE Trans on Power Systems, 1994, 9(4): 1927~1933
[10] Song Y H, Irving M R. An overview of heuristic optimization techniques for power system expansion planning and design[J]. Power Engineering Society General Meeting, 2004, 1(6): 933
[11] Nara K, Hayashi Y, Yamafuji Y et al. A Tabu search algorithm for determining distribution tie lines[A]. Proceedings of the International Conference on Intelligent Systems Applications to Power Systems, ISAP”96[C]. Orlando, USA, 1996, 266~270
[12] Bouchard D E, Salama M M A, Chikhani A Y. Optimal feeder routing and optimal subsation sizing and placement using guided evolutionary simulated annealing[A]. Proceedings of the Canadian Conference on Electrical and Computer Engineering[C]. Canada, 1995, 688~691
[13]孙洪波,电力网络规划(第一版),重庆大学出版社,1996
[14]钱峰,10kV配电网规划研究:[硕士学位论文],河海大学,2003
[15]徐珍霞,顾洁,粒子群优化算法在配电网网架优化规划中的应用,继电器,2006,34(6):29~33
[16] Hochbaum D S. Approximate algorithms for NP-hard problems[M]. Boston, MA: PWS Publishing Company, 1997, 181~184
[17]王成山,王赛一,基于空间GIS和Tabu搜索技术的城市中压配电网络规划,电网技术,2004,28(14):68~74
[18] STRBAC G, DJAPIC P. A genetic based fuzzy approach to optimization of electrical distribution networks[A]. Proceedings of the First Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications [C]. Sheffield (UK): the University of Sheffield, 1995, 194~199
[19]吕勇,赵光宙,蚁群优化算法及其在电力系统中的应用,电工技术学报,2003,18(4):70~74
[20] HSIAOYT, CHIEN C Y. Multi-objective optimal feeder reconfiguration[J]. IEEE Proceedings of Generation, Transmission and Distribution, 2001, 148(4): 333~336
[21] Lacoban R, Reynolds R G, Berwster J. Cultural swarms: modeling the impact of culture on social interaction and problem solving, Proceedings of the 2003 IEEE Swarm Intelligence Symposium, SIS'03, 205~211
[22] Rivas Davalos F, Irving M R. An efficient genetic algorithm for optimal large-scale power distribution network planning[J]. Power Tech Conference Proceedings, 2003, 3(6): 23~26
[23] Ramirez-Rosado I J, Bernal-Agustin J L. Genetic algorithms applied to the design of large power distribution systems[J]. IEEE Trans on Power Systems, 1998, 13(2): 696~703
[24]刘自发,基于智能优化算法的配电网络规划与优化运行研究:[博士学位论文],天津大学,2005
[25] Han K H, Kiln J H. Quantum inspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE Trans on Evolutionary Computation, 2002, 6(6): 580~593
[26]陈根军,唐国庆,基于禁忌搜素与蚁群最优结合算法的配电网规划,电网技术,2005,29(2):23~27
[27] WEN Fushuan, Chang C S. Transmission Network Optimal Planning Using the Tabu Search method[J]. Electric Power Systems Research, 1997, 42(2): 153~163
[28]倪秋龙,黄民翔,基于支路交换的模拟退火算法在配电网规划中的应用,电力系统及其自动化学报,2000,12(4):31~35
[29] Romero R, Gallego R A, Monticelli A. Transmission System Expansion Planning by Simulated Annealing[A]. Proceedings of 1995 IEEE Power Industry Computer Application Conference (PICA’95). USA: 1995, 278~283
[30] Sensarma P S, RahmaniM. A Comprehensive Method for Optimal Expansion Planning Using Particle Swarm Optimization [A]. Proceedings of the IEEE Power Engineering Society Transmission and Distribution Conference. New York (USA): 2002, 1317~1322
[31] Bonabeau E. Inspiration for optimization from social insect behaviour. Nature, 2000, 406: 39~42
[32] Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies[A]. Proceeding of ECAL91-European Conference on Artificial Life. Paris:1991, 134~142
[33] Colorni A, Dorigo M, Maniezzo. Distributed Optimization by ant colonies[J]. In Proceeding of 1st European Conference on Artificial life. Paris, 1992, 134~142
[34]翟海保,程浩忠,陈春霖等,基于改进蚁群算法的输电网络扩展规划,中国电力,2003,36 (12): 49~52
[35]马良,项培军,蚂蚁算法在组合优化中的应用,管理科学学报,2001,4(2):32~37
[36] Dorigo M, Blum C. Ant colony optimization theory: A survey[J]. Theoretical Computer Science, 2005, 344: 243~278
[37] Israel A Wagner, Michael Lindenbaum. Ants: Agents on networks, trees, and subgraphs. Future Generation System, 2000, 16: 915~926
[38] Gambardella L M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. In Proceedings of the Twelfth International Conference on Machine Learning, 1995, 252~260
[39] Dorigo M. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53~66
[40] Dorigo M. A study of some properties of ant-q. In the Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature, 1996, 656~665
[41]燕忠,袁纯伟,用蚁群优化算法求解中国旅行商问题,电路与系统学报,2004,9(3):122~126
[42] Bullnheimer B, Hard R F, Strauss C. An improved ant system algorithm for the vehicle routing problem[R]. Ann Oper Bes, 1999, 89: 319~328
[43] T Stutzle and H H Hoos. The MAX-MIN Ant System and Search for Combinatorial Optimization Porblem[M]. InS Voss, S Martelo, I H Osman, and C Roucaiorl, editors, Meta-Heuristies: Advances and Trends in Local Search P aradigms for Optimization, Kluwer, Boston, 1999, 313~329
[44] Schoonderwoerd R, Holland O, Bruten J. Ant-based load balancing in telecommunications networks. Adaptive Behavior, 1996, 5(2): 169~207
[45] Colorni A, Dorigo M. Ant system for job-shop scheduling Belgian Journal of Operations Research, Statistics and Computer Science, 1994, 34(1): 39~53
[46]胡荣,符杨,罗萍萍,新建住宅区配电网规划实用技术研究,上海电力学院学报,2005,21(4):296~298
[47] Gianni Di Caro, Marro Dorigo. AntNet: A mobile agents approach to adaptive routing. Technical Report 97-12, IRIDIA, UniversitéLibre de Bruxelles. 1997
[48] Bullnheimer B, Hard R F, Strauss C. An improved ant system algorithm for the vehicle routing problem[R]. Ann Oper Bes, 1999, 89: 319~328
[49]陶振武,肖人彬,协同进化蚁群算法及其在多目标优化中的应用,模式识别与人工智能,2005,18(5):588~595
[50]屈稳太,丁伟,一种改进的蚁群算法及其在TSP中的应用,系统工程理论与实践,2006,5:93~98
[51]李慧,基于加权Voronoi图的变电站优化规划:[硕士学位论文],天津大学,2007
[52]朱福喜,汤怡群,傅建明,人工智能原理,武汉大学出版社,2002
[53]谭浩强,C++程序设计,清华大学出版社,2004
[54] Dorigo M. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on System, Man, and Cybernetics2part B, 1996, 26(1): 1~13
[55]段海滨,王道波,一种快速全局优化的改进蚁群算法及仿真,信息与控制,2004,33(2):241~244
[56] Charles Daniel L, Hafeezulla Khen I, Ravichandran S. Distribution Network Reconfiguration For Loss Reduction Using Ant Colony System Algorithm. IEEE Indicon 2005 Conference, Chennai, India, 2005, 619~622
[2]刘健,杨文宇,余健明等,基于改进最小生成树算法并考虑负荷不确定性的配电网架最优规划,电网技术,2005,29(16):61~65
[3]陈庭记,程浩忠,何明等,城市中压配电网接线模式研究,电网技术,2000,24(9):35~38
[4]张菁,基于两联络接线模式的联络线优化研究:[硕士学位论文],天津大学,2007
[5]蓝毓俊,现代城市电网规划设计与建设改造,北京冲国电力出版社,2004
[6]张宪,基于GIS的配电网网架规划的研究:[硕士学位论文],华北电力大学,2006
[7]王赛一,王成山,基于多目标模型的城市中压配电网络规划,中国电力,2006,39 (11):46~50
[8] Miguez E, Cidras J, Diaz-Dorado E, et al, An improved branch-exchange algorithm for large-scale distribution network planning, IEEE Transactions on Power Systems, 2002, 17(4): 931~936
[9] Miranda V, Ranito J V, Procenca L M. Genetic Algorithms in Optimal Multistage Distribution Network Planning[J]. IEEE Trans on Power Systems, 1994, 9(4): 1927~1933
[10] Song Y H, Irving M R. An overview of heuristic optimization techniques for power system expansion planning and design[J]. Power Engineering Society General Meeting, 2004, 1(6): 933
[11] Nara K, Hayashi Y, Yamafuji Y et al. A Tabu search algorithm for determining distribution tie lines[A]. Proceedings of the International Conference on Intelligent Systems Applications to Power Systems, ISAP”96[C]. Orlando, USA, 1996, 266~270
[12] Bouchard D E, Salama M M A, Chikhani A Y. Optimal feeder routing and optimal subsation sizing and placement using guided evolutionary simulated annealing[A]. Proceedings of the Canadian Conference on Electrical and Computer Engineering[C]. Canada, 1995, 688~691
[13]孙洪波,电力网络规划(第一版),重庆大学出版社,1996
[14]钱峰,10kV配电网规划研究:[硕士学位论文],河海大学,2003
[15]徐珍霞,顾洁,粒子群优化算法在配电网网架优化规划中的应用,继电器,2006,34(6):29~33
[16] Hochbaum D S. Approximate algorithms for NP-hard problems[M]. Boston, MA: PWS Publishing Company, 1997, 181~184
[17]王成山,王赛一,基于空间GIS和Tabu搜索技术的城市中压配电网络规划,电网技术,2004,28(14):68~74
[18] STRBAC G, DJAPIC P. A genetic based fuzzy approach to optimization of electrical distribution networks[A]. Proceedings of the First Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications [C]. Sheffield (UK): the University of Sheffield, 1995, 194~199
[19]吕勇,赵光宙,蚁群优化算法及其在电力系统中的应用,电工技术学报,2003,18(4):70~74
[20] HSIAOYT, CHIEN C Y. Multi-objective optimal feeder reconfiguration[J]. IEEE Proceedings of Generation, Transmission and Distribution, 2001, 148(4): 333~336
[21] Lacoban R, Reynolds R G, Berwster J. Cultural swarms: modeling the impact of culture on social interaction and problem solving, Proceedings of the 2003 IEEE Swarm Intelligence Symposium, SIS'03, 205~211
[22] Rivas Davalos F, Irving M R. An efficient genetic algorithm for optimal large-scale power distribution network planning[J]. Power Tech Conference Proceedings, 2003, 3(6): 23~26
[23] Ramirez-Rosado I J, Bernal-Agustin J L. Genetic algorithms applied to the design of large power distribution systems[J]. IEEE Trans on Power Systems, 1998, 13(2): 696~703
[24]刘自发,基于智能优化算法的配电网络规划与优化运行研究:[博士学位论文],天津大学,2005
[25] Han K H, Kiln J H. Quantum inspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE Trans on Evolutionary Computation, 2002, 6(6): 580~593
[26]陈根军,唐国庆,基于禁忌搜素与蚁群最优结合算法的配电网规划,电网技术,2005,29(2):23~27
[27] WEN Fushuan, Chang C S. Transmission Network Optimal Planning Using the Tabu Search method[J]. Electric Power Systems Research, 1997, 42(2): 153~163
[28]倪秋龙,黄民翔,基于支路交换的模拟退火算法在配电网规划中的应用,电力系统及其自动化学报,2000,12(4):31~35
[29] Romero R, Gallego R A, Monticelli A. Transmission System Expansion Planning by Simulated Annealing[A]. Proceedings of 1995 IEEE Power Industry Computer Application Conference (PICA’95). USA: 1995, 278~283
[30] Sensarma P S, RahmaniM. A Comprehensive Method for Optimal Expansion Planning Using Particle Swarm Optimization [A]. Proceedings of the IEEE Power Engineering Society Transmission and Distribution Conference. New York (USA): 2002, 1317~1322
[31] Bonabeau E. Inspiration for optimization from social insect behaviour. Nature, 2000, 406: 39~42
[32] Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies[A]. Proceeding of ECAL91-European Conference on Artificial Life. Paris:1991, 134~142
[33] Colorni A, Dorigo M, Maniezzo. Distributed Optimization by ant colonies[J]. In Proceeding of 1st European Conference on Artificial life. Paris, 1992, 134~142
[34]翟海保,程浩忠,陈春霖等,基于改进蚁群算法的输电网络扩展规划,中国电力,2003,36 (12): 49~52
[35]马良,项培军,蚂蚁算法在组合优化中的应用,管理科学学报,2001,4(2):32~37
[36] Dorigo M, Blum C. Ant colony optimization theory: A survey[J]. Theoretical Computer Science, 2005, 344: 243~278
[37] Israel A Wagner, Michael Lindenbaum. Ants: Agents on networks, trees, and subgraphs. Future Generation System, 2000, 16: 915~926
[38] Gambardella L M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. In Proceedings of the Twelfth International Conference on Machine Learning, 1995, 252~260
[39] Dorigo M. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53~66
[40] Dorigo M. A study of some properties of ant-q. In the Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature, 1996, 656~665
[41]燕忠,袁纯伟,用蚁群优化算法求解中国旅行商问题,电路与系统学报,2004,9(3):122~126
[42] Bullnheimer B, Hard R F, Strauss C. An improved ant system algorithm for the vehicle routing problem[R]. Ann Oper Bes, 1999, 89: 319~328
[43] T Stutzle and H H Hoos. The MAX-MIN Ant System and Search for Combinatorial Optimization Porblem[M]. InS Voss, S Martelo, I H Osman, and C Roucaiorl, editors, Meta-Heuristies: Advances and Trends in Local Search P aradigms for Optimization, Kluwer, Boston, 1999, 313~329
[44] Schoonderwoerd R, Holland O, Bruten J. Ant-based load balancing in telecommunications networks. Adaptive Behavior, 1996, 5(2): 169~207
[45] Colorni A, Dorigo M. Ant system for job-shop scheduling Belgian Journal of Operations Research, Statistics and Computer Science, 1994, 34(1): 39~53
[46]胡荣,符杨,罗萍萍,新建住宅区配电网规划实用技术研究,上海电力学院学报,2005,21(4):296~298
[47] Gianni Di Caro, Marro Dorigo. AntNet: A mobile agents approach to adaptive routing. Technical Report 97-12, IRIDIA, UniversitéLibre de Bruxelles. 1997
[48] Bullnheimer B, Hard R F, Strauss C. An improved ant system algorithm for the vehicle routing problem[R]. Ann Oper Bes, 1999, 89: 319~328
[49]陶振武,肖人彬,协同进化蚁群算法及其在多目标优化中的应用,模式识别与人工智能,2005,18(5):588~595
[50]屈稳太,丁伟,一种改进的蚁群算法及其在TSP中的应用,系统工程理论与实践,2006,5:93~98
[51]李慧,基于加权Voronoi图的变电站优化规划:[硕士学位论文],天津大学,2007
[52]朱福喜,汤怡群,傅建明,人工智能原理,武汉大学出版社,2002
[53]谭浩强,C++程序设计,清华大学出版社,2004
[54] Dorigo M. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on System, Man, and Cybernetics2part B, 1996, 26(1): 1~13
[55]段海滨,王道波,一种快速全局优化的改进蚁群算法及仿真,信息与控制,2004,33(2):241~244
[56] Charles Daniel L, Hafeezulla Khen I, Ravichandran S. Distribution Network Reconfiguration For Loss Reduction Using Ant Colony System Algorithm. IEEE Indicon 2005 Conference, Chennai, India, 2005, 619~622