Binary-Real Coded Genetic Algorithm Based k-Means Clustering for Unit Commitment Problem
Abstract: This paper presents a new algorithm for solving unit commitment (UC) problems using a binary-real coded genetic algorithm based on k-means clustering technique. UC is a NP-hard nonlinear mixed-integer optimization problem, encountered as one of the toughest problems in power systems, in which some power generating units are to be scheduled in such a way that the forecasted demand is met at minimum production cost over a time horizon. In the proposed algorithm, the algorithm integrates the main features of a binary-real coded genetic algorithm (GA) and k-means clustering technique. The binary coded GA is used to obtain a feasible commitment schedule for each generating unit; while the power amounts generated by committed units are determined by using real coded GA for the feasible commitment obtained in each interval. k-means clustering algorithm divides population into a specific number of subpopulations with dynamic size. In this way, using k-means clustering algorithm allows the use of different GA operators with the whole population and avoids the local problem minima. The effectiveness of the proposed technique is validated on a test power system available in the literature. The proposed algorithm performance is found quite satisfactory in comparison with the previously reported results.
Cite this paper: Farag, M. , El-Shorbagy, M. , El-Desoky, I. , El-Sawy, A. and Mousa, A. (2015) Binary-Real Coded Genetic Algorithm Based k-Means Clustering for Unit Commitment Problem. Applied Mathematics, 6, 1873-1890. doi: 10.4236/am.2015.611165.
References

[1]   Wood, A.J. and Wollenberg, B.F. (1996) Power Generation, Operation and Control. John Wiley & Sons, New York.

[2]   Guan, X.H., Luh, P.B., Yan, H. and Amalfi, J.A. (1992) An Optimization-Based Method for Unit Commitment. International Journal of Electrical Power & Energy Systems, 14, 9-17.
http://dx.doi.org/10.1016/0142-0615(92)90003-R

[3]   Jeong, Y.W., Park, J.B., Shin, J.R. and Lee, K.Y. (2009) A Thermal Unit Commitment Approach Using an Improved Quantum Evolutionary Algorithm. Electric Power Components and Systems, 37, 770-786.
http://dx.doi.org/10.1080/15325000902762331

[4]   Padhy, N.P. (2004) Unit Commitment—A Bibliographical Survey. IEEE Transactions on Power Systems, 19, 1196-1205.
http://dx.doi.org/10.1109/TPWRS.2003.821611

[5]   Senjyu, T., Miyagi, T., Saber, A.Y., Urasaki, N. and Funabashi, T. (2006) Emerging Solution of Large-Scale Unitcommitment Problem by Stochastic Priority List. Electrical Power and Energy Systems, 76, 283-292.
http://dx.doi.org/10.1016/j.epsr.2005.07.002

[6]   Rong, A., Hakonen, H. and Lahdelma, R. (2009) A Dynamic Regrouping Based Sequential Dynamic Programming Algorithm for Unit Commitment of Combined Heat and Power Systems. Energy Conversion and Management, 50, 1108-1115.
http://dx.doi.org/10.1016/j.enconman.2008.12.003

[7]   Chen, C.L. and Wang, S.C. (1993) Branch-and-Bound Scheduling for Thermal Generating Units. IEEE Transactions on Energy Conversion, 8, 184-189.

[8]   Singhal, P.K. (2011) Generation Scheduling Methodology for Thermal Units Using Lagrangian Relaxation. Proceedings of the 2nd IEEE International Conference on Current Trends in Technology, 1-6.

[9]   Frangioni, A., Gentile, C. and Lacalandra, F. (2009) Tighter Approximated MILP Formulations for Unit Commitment Problems. IEEE Transactions on Power Systems, 24, 105-113.
http://dx.doi.org/10.1109/TPWRS.2008.2004744

[10]   Sheble, G.B. and Fahd, G.N. (1993) Unit Commitment Literature Synopsis. IEEE Transactions on Power Systems, 9, 128-135.
http://dx.doi.org/10.1109/59.317549

[11]   Swarup, K. and Simi, P. (2006) Neural Computation Using Discrete and Continuous Hopfield Networks for Power System Economic Dispatch and Unit Commitment. Neurocomputing, 70, 119-129.
http://dx.doi.org/10.1016/j.neucom.2006.05.002

[12]   Kazarlis, S.A., Bakirtzis, A.G. and Petridis, V. (1996) A Genetic Algorithm Solution to the Unit Commitment Problem. IEEE Transactions on Power Systems, 11, 1129-1136.

[13]   Arroyo, J.M. and Conejo, A.J. (2002) A Parallel Repair Genetic Algorithm to Solve the Unit Commitment Problem. IEEE Electrical Power Energy Systems, 17, 1216-1224.
http://dx.doi.org/10.1109/tpwrs.2002.804953

[14]   Dang, C. and Li, M. (2007) A Floating-Point Genetic Algorithm for Solving the Unit Commitment Problem. European Journal of Operational Research, 181, 1370-1395.
http://dx.doi.org/10.1016/j.ejor.2005.10.071

[15]   Sundararajan, D., Subramanian, B., Subramanian, K. and Krishnan, M. (2013) Generation Scheduling Problem by Intelligent Genetic Algorithm. Computers and Electrical Engineering, 39, 79-88.

[16]   Datta, D. (2013) Unit Commitment Problem with Ramp Rate Constraint Using a Binary-Real-Coded Genetic Algorithm. Applied Soft Computing, 13, 3873-3883.

[17]   Juste, K.A., Kita, H., Tanaka, E. and Hasegawa, J. (1999) An Evolutionary Programming Solution to the Unit Commitment Problem. IEEE Transactions on Power Systems, 14, 1452-1459.
http://dx.doi.org/10.1109/59.801925

[18]   Simopoulos, N., Kavatza, S. and Vournas, C. (2006) Unit Commitment by an Enhanced Simulated Annealing Algorithm. IEEE Transactions on Power Systems, 21, 68-76.
http://dx.doi.org/10.1109/TPWRS.2005.860922

[19]   Mantawy, A.H., Abdel-Magid, Y.L. and Selim, S.Z. (1999) Integrating Genetic Algorithms, Tabu Search, and Simulated Annealing for the Unit Commitment Problem. IEEE Transactions on Power Systems, 14, 829-836.
http://dx.doi.org/10.1109/59.780892

[20]   Ebrahimi, J., Hosseinian, S.H. and Gharehpetian, G.B. (2011) Unit Commitment Problem Solution Using Shuffled Frog Leaping Algorithm. IEEE Transactions on Power Systems, 26, 573-581.

[21]   Logenthiran, T. and Srinivasan, D. (2010) Particle Swarm Optimization for Unit Commitment Problem. Proceedings of the IEEE International Conference on Probabilistic Methods Applied to Power Systems, Singapore, 14-17 June 2010, 642-647.
http://dx.doi.org/10.1109/PMAPS.2010.5528899

[22]   Mantawy, A.H., Abdel-Magid, Y.L. and Selim, S.Z. (1998) Unit Commitment by Tabu Search. IEE Proceedings— Generation, Transmission and Distribution, 145, 56-64.
http://dx.doi.org/10.1049/ip-gtd:19981681

[23]   El-Saadawi, M.M., Tantawi, M.A. and Tawfik, E. (2004) A Fuzzy Optimization-Based Approach to Large Scale Thermal Unit Commitment. Electric Power Systems Research, 72, 245-252.
http://dx.doi.org/10.1016/j.epsr.2004.04.009

[24]   Pourjamal, Y. and Ravadanegh, S.N. (2013) HSA Based Solution to the UC Problem. International Journal of Electrical Power & Energy Systems, 46, 211-220.
http://dx.doi.org/10.1016/j.ijepes.2012.10.042

[25]   Chandrasekaran, K., Hemamalini, S., Simon, S.P. and Padhy, N.P. (2012) Thermal Unit Commitment Using Binary/ Real Coded Artificial Bee Colony Algorithm. Electric Power Systems Research, 84, 109-119.

[26]   Mousa, A.A., El-Shorbagy, M.A. and Abd El-Wahed, W.F. (2012) Local Search Based Hybrid Particle Swarm Optimization for Multiobjective Optimization. International Journal of Swarm and Evolutionary Computation, 3, 1-14.

[27]   Farag, M.A., El-Shorbagy, M.A., El-Desoky, I.M., El-Sawy, A.A. and Mousa, A.A. (2015) Genetic Algorithm Based on K-Means-Clustering Technique for Multi-Objective Resource Allocation Problems. British Journal of Applied Science & Technology, 8, 80-96.
http://dx.doi.org/10.9734/BJAST/2015/16570

[28]   El-Shorbagy, M.A., Mousa, A.A. and Abd-El-Wahed, W.F. (2011) Hybrid Particle Swarm Optimization Algorithm for Multi-Objective Optimization. Lambert Academic Publishing GmbH & Co. KG, Berlin.

[29]   El-Shorbagy, M.A., El-Sawy, A.A. and Hendawy, Z.M. (2013) Numerical Optimization & Swarm Intelligence for Optimization: Trust Region Algorithm & Particle Swarm Optimization. Lambert Academic Publishing GmbH & Co. KG, Berlin.

[30]   Mousa, A.A. and El-Desoky, I.M. (2008) GENLS: Co-Evolutionary Algorithm for Nonlinear System of Equations. Applied Mathematics and Computation, 197, 633-642.

[31]   Mousa, A.A. and El-Desoky, I.M. (2013) Stability of Pareto Optimal Allocation of Land Reclamation by Multistage Decision-Based Multipheromone Ant Colony Optimization. Swarm and Evolutionary Computation, 13, 13-21

[32]   Abd El-Wahed, W.F., Mousa, A.A. and El-Shorbagy, M.A. (2011) Integrating Particle Swarm Optimization with Genetic Algorithms for Solving Nonlinear Optimization Problems. Journal of Computational and Applied Mathematics, 235, 1446-1453.

[33]   Mousa, A.A. and El-Shorbagy, M.A. (2012) Enhanced Particle Swarm Optimization Based Local Search for Reactive Power Compensation Problem. Applied Mathematics, 3, 1276-1284.
http://dx.doi.org/10.4236/am.2012.330184

[34]   Michalewiz, Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. Third Edition, Springer-Verlag, New York.

[35]   Verma, M., Srivastava, M., Chack, N., Diswar, A.K. and Gupta, N. (2012) A Comparative Study of Various Clustering Algorithms in Data Mining. International Journal of Engineering Research and Applications (IJERA), 2, 1379-1384.

[36]   Levine, S., Pilowski, I. and Boulton, D.M. (1969) The Classification of Depression by Numerical Taxonomy. The British Journal of Psychiatry, 115, 937-945.
http://dx.doi.org/10.1192/bjp.115.525.937

[37]   Dolnicar, S. (2003) Using Cluster Analysis for Market Segmentation-Typical Misconceptions, Established Methodological Weaknesses and Some Recommendations for Improvement. Australasian Journal of Market Research, 11, 5-12.

[38]   Hodson, F.R. (1971) Numerical Typology and Prehistoric Archaeology. In: Hodson, F.R., Kendall, D.G. and Tautu, P.A., Eds., Mathematics in the Archaeological and Historical Sciences, University Press, Edinburgh.

[39]   Pratima, D., Nimmakanti, N. and Recognition, P. (2011) Algorithms for Cluster Identification Problem. Special Issue of International Journal of Computer Science & Informatics (IJCSI), 2, 2231-5292.

[40]   Doreswamy and Hemanth, K.S. (2012) Similarity Based Cluster Analysis on Engineering Materials Data Sets. Advances in Intelligent Systems and Computing, 167, 161-168.

[41]   Dilts, D., Khamalah, J. and Plotkin, A. (1995) Using Cluster Analysis for Medical Resource Decision Making. Cluster Analysis for Resource Decisions, 15, 333-347.

[42]   Aggarwal, C.C. and Reddy, C.K. (2014) Data Clustering Algorithms and Applications. CRC Press, New York.

[43]   MacQueen, J.B. (1967) Some Methods for Classification and Analysis of Multivariate Observation. In: Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Berkeley, 281-297.

[44]   Priya, R.P., Sivaraj, N. and Muruganandam, M. (2015) A Solution to Unit Commitment Problem with V2G Using Harmony Search Algorithm. International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering, 4, 1208-1214.

[45]   Goldberg, D.E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, Reading.

[46]   Grefenstette, J.J. (1986) Optimization of Control Parameters for Genetic Algorithms. IEEE Transactions on Systems, Man and Cybernetics, 16, 122-128.
http://dx.doi.org/10.1109/TSMC.1986.289288

[47]   Arai, K. and Bu, X.Q. (2007) ISODATA Clustering with Parameter (Threshold for Merge and Split) Estimation Based on GA: Genetic Algorithm. Reports of the Faculty of Science and Engineering, Saga University, 36, 17-23.

[48]   Ng, R.T. and Han, J. (2002) CLARANS: A Method for Clustering Objects for Spatial Data Mining. IEEE Transactions on Knowledge Data Engineering, 14, 1003-1016.

[49]   Judd, D., McKinley, P.K. and Jain, A.K. (1998) Large-Scale Parallel Data Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20, 871-876.

[50]   Edlaa, D.R. and Janaa, P.K. (2012) A Prototype-Based Modified DBSCAN for Gene Clustering. Procedia Technology, 6, 485-492.

[51]   Rani, Y., Manju and Rohil, H. (2014) Comparative Analysis of BIRCH and CURE Hierarchical Clustering Algorithm Using WEKA 3.6.9. The SIJ Transactions on Computer Science Engineering & Its Applications (CSEA), 2, 25-29.

[52]   Sakthi, M. and Thanamani, A.S. (2011) An Effective Determination of Initial Centroids in K-Means Clustering Using Kernel PCA. International Journal of Computer Science and Information Technologies, 2, 955-959.

[53]   Jain, A. (2010) Data Clustering: 50 Years beyond K-Means. Pattern Recognition Letters, 31, 651-666.
http://dx.doi.org/10.1016/j.patrec.2009.09.011

[54]   Kumar, A. and Jani, N.N. (2010) Network Design Problem Using Genetic Algorithm—An Empirical Study on Selection Operator. International Journal of Computer Science and Applications (IJCSA), 3, 48-52.

[55]   Xing, W. and Wu, F.F. (2002) Genetic Algorithm Based Unit Commitment with Energy Contracts. International Journal of Electrical Power & Energy Systems, 24, 329-336.
http://dx.doi.org/10.1016/S0142-0615(01)00048-5

[56]   Gen, M., Cheng, R. and Lin, L. (2008) Network Models and Optimization: Multi-objective Genetic Algorithm Approach. Springer Science & Business Media, New York.

[57]   Jeong, Y.W., Lee, W.N., Kim, H.H., Park, J.B. and Shin, J.R. (2009) Thermal Unit Commitment Using Binary Differential Evolution. Journal of Electrical Engineering & Technology, 4, 323-329.

[58]   Uyar, A.S., Türkay, B. and Keles, A. (2011) A Novel Differential Evolution Application to Short-Term Electrical Power-Generation Scheduling. Electrical Power and Energy Systems, 33, 1236-1242.

[59]   Yuan, X., Su, A., Nie, H., Yuan, Y. and Wang, L. (2009) Application of Enhanced Discrete Differentia Evolution Approach to Unit Commitment Problem. Energy Conversion & Management, 50, 2449-2456.

[60]   Mohd, R.N. and Geraghty, J. (2011) Genetic Algorithm Performance with Different Selection Strategies in Solving TSP. Proceedings of the World Congress on Engineering II, London, 6-8 July 2011.

[61]   Sivaraj, R. and Ravichandran, T. (2011) A Review of Selection Methods in Genetic Algorithm. International Journal of Engineering Science and Technology, 3, 3792-3797.

[62]   Tzeng, G.H. and Huang, J.J. (2013) Fuzzy Multiple Objective Decision Making. Chapman and Hall/CRC Press, London/Boca Raton.

[63]   Anderson, C.A., Jones, K.F. and Ryan, J. (1991) A Two-Dimensional Genetic Algorithm for the Ising Problem. Complex Systems, 5, 327-333.

[64]   Cheng, C.P. and Liu, C.W. (2002) Unit Commitment by Annealing Genetic Algorithm. International Journal of Electrical Power & Energy Systems, 24, 149-158.

[65]   Sun, L., Zhang, Y. and Jiang, C. (2006) A Matrix Real-Coded Genetic Algorithm to the Unit Commitment Problem. Electric Power Systems Research, 76, 716-728.

[66]   Senjyu, T., Yamashiro, H., Uezato, K. and Funabashi, T. (2002) A Unit Commitment Problem by Using Genetic Algorithm Based on Unit Characteristic Classification. Proceedings of the IEEE Power Engineering Society Winter Meeting, 1, 58-63.

[67]   Kumar, S. and Naresh, R. (2007) Efficient Real Coded Genetic Algorithm to Solve the Non-Convex Hydrothermal Scheduling Problem. Electrical Power and Energy Systems, 29, 738-747.

[68]   Cheng, C.-P., Liu, C.-W. and Liu, C.-C. (2000) Unit Commitment by Lagrangian Relaxation and Genetic Algorithms. IEEE Transactions on Power Systems, 15, 707-714.

[69]   Damousis, I., Bakirtzis, A. and Dokopoulos, P. (2004) A Solution to the Unit-Commitment Problem Using Integer-Coded Genetic Algorithm. IEEE Transactions on Power Systems, 19, 1165-1172.
http://dx.doi.org/10.1109/TPWRS.2003.821625

Top