A Novel Genetic Algorithm Based on all Spanning Trees of Undirected Graph for Distribution Network Reconfiguration

Abstract:

Network reconfiguration is of theoretical and practical significance to guarantee safe and economical operation of distribution system. In this paper, based on all spanning trees of undirected graph, a novel genetic algorithm for electric distribution network reconfiguration is proposed. Above all, all spanning trees of simplified graph of distribution network are found. Tie branches are obtained with spanning tree subtracted from simplified graph. There is one and only one switch open on each tie branch. Decimal identity number of open switch on each tie branch is taken as the optimization variable. Therefore, length of chromosome is very short. Each spanning tree corresponds to one subpopulation. Gene operations of each subpopulation are implemented with parallel computing method. Individuals of offspring after gene operation automatically meet with radial and connected constraints for distribution network operation. Disadvantages of conventional genetic algorithm for network reconfiguration that a large amount of unfeasible solutions are created after crossover and mutation, which result in very low searching efficiency, are completely overcome. High calculation speed and superior capability of the proposed method are validated by two test cases.

• Periodical: Advanced Materials Research (Volumes 960-961)
• Pages: 943-951
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.960-961.943
• Online since: June 2014
• Authors: Jian Zhang, Xiao Dong Yuan
• Keywords: All Spanning Trees of Undirected Graph, Decimal Coding, Distribution Network, Genetic Algorithm (GA), Network Reconfiguration, Paralleling Computing

References

[1] He Yuqing, Peng Jianchun, Wen Ming, Zhou Yangxi, Li Jianying, Li Peng. Minus feasible analysis unit and fast algorithm for distribution network reconfiguration. Proceedings of the CSEE, Vol. 30 (2010), p.50.

[2] S. Civanlar, J.J. Grainger, H. Yin, S.S.H. Lee. Distribution feeder reconfiguration for loss reduction. IEEE Transactions on Power Delivery, Vol. 3 (1988), p.1217.

DOI: 10.1109/61.193906

[3] Bi Pengxiang, Liu J ian, Zhang Wenyuan. A refined branch exchange algorithm for distribution network reconfiguration. Proceedings of the CSEE, Vol. 22 (2001), p.98.

[4] Lei Jiansheng, Deng Youman, Zhang Boming. Hybrid flow pattern and its application in network reconfiguration. Proceedings of the CSEE, Vol. 21(2001), p.57.

[5] Liu Wei, Han Zhenxiang. Distribution network reconfiguration based on optimal flow pattern algorithm and genetic algorithm. Power System Technology, Vol. 28 (2004), p.29.

[6] Liu Jian, Bi Pengxiang, Dong Haipeng. Analysis and simplification of complicated distribution network. China Electric Power Press, 2002, Beijing.

[7] Bi Pengxiang, Liu J ian, Zhang Wenyuan. Study on algorithms of distribution network reconfiguration. Automation of Electric Power Systems, Vol. 10 (2001), p.54.

[8] Li Xiaoming, Huang Yanhao, Yin Xianggen. A genetic algorithm based on improvement strategy for power distribution network reconfiguration. Proceedings of the CSEE, Vol. 24 (2004), p.49.

[9] Bi Pengxiang, Liu Jian, Liu Chun Xin, Zhang Wenyuan. A refined genetic algorithm for power distribution network reconfiguration. Automation of Electric Power Systems, Vol. 2 (2002), p.57.

DOI: 10.1109/icpst.2002.1067829

[10] Ma Xiufan, Zhang Lizi. Distribution network reconfiguration based on genetic algorithm using decimal encoding. Transactions of China Electro- technical Society, Vol. 19 (2004), p.65.

[11] Koichi Nara, Atsushi, Shiose, Minoru Kitagawa, Toshihisa Ishihara. Implementation of genetic algorithm for distribution system loss minimum reconfiguration. IEEE Transactions on Power System, Vol. 7 (1992), p.1044.

DOI: 10.1109/59.207317

[12] Xu Kui. A study of reconfiguration network based on improved adaptive genetic algorithms. Master's dissertation of Guangxi University, (2008).

[13] Wang Yansong，Chen Guoming，Zhang Jiasheng，et al．Optimal switching device placement based on niche genetic algorithm in distribution networks. Transactions of China Electro- technical Society, Vol. 21 (2006), p.82.

[14] Liu Li, Cheng Xueyun. Reconfiguration of distribution network based on fuzzy genetic algorithm. Proceedings of the CSEE, Vol. 20 (2000), p.66.

[15] Yu Yixin, Duan Gang. Shortest path algorithm and genetic algorithm based distribution system reconfiguration. Proceedings of the CSEE, Vol. 20 (2000), p.44.

DOI: 10.1109/icpst.2002.1067828

[16] Ge Shaoyun, Liu Zifa, Yu Yixin. An improved Tabu search for reconfiguration of distribution systems. Power System Technology, Vol. 28 (2004), p.22.

[17] Wang Shouxiang, Wang Chengshan. A novel network reconfiguration algorithm implicity including parallel searching for large scale unbalanced distribution systems. Automation of Electric Power Systems, Vol. 24 (2000), p.34.

[18] Kubin Taleski, Dragoslav Rajicid. Distribution network reconfiguration for energy loss reduction. IEEE Transactions on Power Systems, Vol. 12 (1997), p.398.

DOI: 10.1109/59.575733

[19] Chen Genjun, Li Jiguang, Tang Guoqing. A tabu search approach to distribution network reconfiguration for loss reduction. Proceedings of the CSEE, Vol. 22(2002), p.28.

[20] HAROLD N. Gabow, EUGENE W. Myers. Finding All Spanning Trees of Directed and Undirected Graphs[J]. Society for Industrial and Applied Mathematics, Vol. 7 (1978), p.280.

DOI: 10.1137/0207024

[21] Yan Wei, Liu Fang, Wang Guanjie, et al. Layer-by-layer back/forward sweep method for radial distribution load flow. Proceedings of the CSEE, Vol. 23 (2003), p.76.