Share This Article:

Binary-Real Coded Genetic Algorithm Based k-Means Clustering for Unit Commitment Problem

Abstract Full-Text HTML XML Download Download as PDF (Size:1160KB) PP. 1873-1890
DOI: 10.4236/am.2015.611165    2,563 Downloads   3,045 Views   Citations

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.

Conflicts of Interest

The authors declare no conflicts of interest.

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

  
comments powered by Disqus

Copyright © 2018 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.