遗传算法求解电力设施选址问题

Solving Grid System Facility Location Problem Based on Improved Genetic Algorithm

电力系统设施选址优化问题是电力系统规划和设计中的一个基础性问题,可以抽象成约束型的p-中位(p-median)问题,这是一个经典的NP-hard问题。该问题可以描述为从一个点的集合中选择p个有容量限制的中位点,让它们去服务一些有需求的点(客户),要求每一个中位点都不超出容量,并且总花费最小。文中针对这一优化问题,在经典遗传算法的基础上,提出了一种改进的遗传算法,并混合使用局部搜索算法,进行问题的求解。该算法能够利用遗传算法的全局收敛性,并且有效克服遗传算法的局部收敛和早熟问题,从而得到更准确的近似解。最后,使用网上的公开测试数据集以及经地理信息平台(GIS)收集的某供电局的坐标信息进行实验验证。结果表明,提出的算法能够有效解决设施选址问题,并且为企业提供切实可行的方案。

Grid system facility location, as a basic problem in grid system plan and design, can be modeled as a capacitated p -median problem,which is a classical NP-hard problem. It can be described as selectingp -capacitated medians from a vertices set in order to serve a set of demand vertices （ customers）, so that the total assigned demand to each of the candidate median does not exceed its capacity, and the cost is minimum. To solve this problem, an improved genetic algorithm incorporated with a local search procedure is proposed based on classical genetic algorithm. It can use the global convergence and avoid the local convergence and premature in genetic algorithm to obtain the more accurate approximated solution. The algorithm has been tested using standard testing data and the real data collected by a geographic information system. The results show that this method can provide a feasible and promising solution for the industry.