Hamming Mesafesi ile Lokal Arama Tabanlı İkili Yapay Arı Kolonisi Algoritması

Yıl 2020, Cilt: 24 Sayı: 1, 120 - 131, 20.04.2020

Zeynep Banu Özger , Bülent Bolat , Banu Diri

https://doi.org/10.19113/sdufenbed.635465

Öz

Yapay Arı Kolonisi Algoritması sürekli uzay problemleri için geliştirilen, popülasyon tabanlı, doğadan esinlemeli bir optimizasyon algoritmasıdır. Bu çalışmanın amacı, büyük veride, öznitelik alt küme seçimi problemini efektif bir biçimde çözmek için Yapay Arı Koloni (YAK) Algoritmasının ikili bir versiyonunu geliştirmektir. YAK Algoritması başarılı bir global yakınsama sunmakla birlikte lokal bölgedeki olası çözümleri gözden kaçırabilmektedir. Algoritmanın komşu kaynak seçimi mekanizmasına, Hamming Mesafe ölçümü tabanlı bir yerel arama prosedürü eklenmiştir. Ayrıca, yeniden nüfus stratejisi ile popülasyonun çeşitliliği artırılmış ve erken yakınsama önlenmiştir. UCI Makine Öğrenmesi Havuzu’ndan, öznitelik sayısı 100’den fazla olan 14 veri kümesi seçilmiş ve önerilen yöntem ile öznitelik seçimi yapılmıştır. Algoritmanın performansı, yaygın kullanılan ve başarısı kanıtlanmış üç sezgisel algoritma ile sınıflandırma hatası, seçilen öznitelik sayısı ve hesapsal maliyet bakımından karşılaştırılmıştır. Elde edilen sonuçlar, YAK algoritmasına entegre edilen lokal arama prosedürünün, algoritmanın performansını tüm kriterler bakımından artırdığını göstermektedir. 

Anahtar Kelimeler

Yapay arı kolonisi, Veri madenciliği, Sezgisel Algoritmalar, Makine Öğrenmesi

A Locally Searched Binary Artificial Bee Colony Algorithm Based on Hamming Distance for Binary Optimization

Öz

Artificial Bee Colony is a population based, bio-inspired optimization algorithm that developed for continues problems. The aim of this study is to develop a binary version of the Artificial Bee Colony (ABC) Algorithm to solve feature subset selection problem on bigger data. ABC Algorithm, has good global search capability but there is a lack of local search in the algorithm. To overcome this problem, the neighbor selection mechanism in the employed bee phase is improved by changing the new source generation formula that has hamming distance based local search capacity. With a re-population strategy, the diversity of the population is increased and premature convergence is prevented. To measure the effectiveness of the proposed algorithm, fourteen datasets which have more than 100 features were selected from UCI Machine Learning Repository and processed by the proposed algorithm. The performance of the proposed algorithm was compared to three well-known algorithms in terms of classification error, feature size and computation time. The results proved that the increased local search ability improves the performance of the algorithm for all criteria.

Anahtar Kelimeler

Artificial bee colony, Data mining, Heuristic algorithms, Machine learning

Kaynakça

• [1] Guyon, I., Elisseeff, A. 2013. An Introduction to Variable and Feature Selection. Journal of Machine Learning Research, 3, 1157–1182.
• [2] Sánchez-Maroño, N., Alonso-Betanzos, A., Tombilla-Sanromán, M. 2007. Filter Methods for Feature Selection: a Comparative Study. I Proceedings of the 8th International Conference on Intelligent Data Engineering and Automated Learning, December, Berlin, Heidelberg, 178–187.
• [3] Kohavi, R., John, G. H. 1997. Wrappers for Feature Subset Selection. Artificial Intelligence, 1-2, 273-324.
• [4] Unler, A., Murat, A. 2010. A Discrete Particle Swarm Optimization Method for Feature Selection in Binary Classification Problems. European Journal of Operational Research, 206(3), 528-539.
• [5] Cervante, L., Xue, B., Shang, L., Zhang, M. 2012. A Dimension Reduction Approach to Classification Based on Particle Swarm Optimisation and Rough Set Theory. Advances in Artificial Intelligence, 1 st ed., Springer, Berlin, Heidelberg, 313–325.
• [6] Cervante, L., Xue, B., Shang, L., Zhang, M. 2013. A Multi-Objective Feature Selection Approach Based on Binary Pso and Rough Set Theory. Evolutionary Computation in Combinatorial Optimization, 7832, 25–36.
• [7] Yang, J., Honavar, V.G. 1998. Feature Subset Selection Using a Genetic Algorithm. IEEE Intelligent System, 13(2), 44–49.
• [8] Raymer, M. L., Punch, W. F., Goodman, E. D., Kuhn, L. A., Jain, A. K. 2000. Dimensionality Reduction Using Genetic Algorithms. IEEE Transactions on Evolutionary Computation, 4(2), 164–171.
• [9] Ahmed, S., Zhang, M., Peng, L. 2014. Improving Feature Ranking for Biomarker Discovery in Proteomics Mass Spectrometry Data Using Genetic Programming. Connection Science, 26(3), 215–243.
• [10] Nemati, S., Basiri, M. E., Ghasem-Aghaee, N., Aghdam, M. H. 2009. A Novel ACO-GA Hybrid Algorithm for Feature Selection in Protein Function Prediction. Expert System Application, 36(10), 12086–12094.
• [11] Wen, L., Yin, Q., Guo, P. 2008. Ant Colony Optimization Algorithm for Feature Selection and Classification of Multispectral Remote Sensing Image. IEEE International Geoscience and Remote Sensing Symposium (IGARSS2008), 7-11 July, Boston, USA, 923-926.
• [12] Jensen, R. 2006. Performing Feature Selection with ACO. Swarm Intelligence in Data Mining, Springer, Berlin, Heidelberg, 45-73.
• [13] Nakamura, R., Pereira, L., Costa, K., Rodrigues, D., Papa, J. 2012. BBA: a Binary Bat Algorithm for Feature Selection. Conference on Graphics, Patterns and Images, 22–25 Aug, Ouro Preto, 291-297.
• [14] Oduntana, I. O., Toulouse, M., Baumgartner, R., Bowman, C., Somorjai, R., Crainic, T. G. 2008. A Multilevel Tabu Search Algorithm for the Feature Selection Problem in Biomedical Data. Computers & Mathematics with Applications, 55, 1019–1033.
• [15] Chuang, L. Y., Yang, C. H. 2009. Tabu Search and Binary Particle Swarm Optimization for Feature Selection using Microarray Data. Journal of Computational Biology, 16(12), 1689-1703.
• [16] Balabina, R. M., Smirnov, S. V. 2011. Variable Selection in Near-Infrared Spectroscopy: Benchmarking of Feature selection Methods on Biodiesel Data. Analytica Chimica Acta, 692, 63–72.
• [17] Ustunkar, G., Ozogur-Akyuz, S., Weber, G. W., Friedrich, C. M., Aydin Son, Y. 2011. Selection of Representative SNP Sets for Genome-Wide Association Studies: a Metaheuristic Approach. Optimization Letters, 6(6), 1207–1218.
• [18] Hancer, E. 2019. Differential Evolution for Feature Selection: a Fuzzy Wrapper-Filter Approach. Soft Computing, 23(13), 5233-5248.
• [19] Li, T., Dong, H., Sun, J. 2019. Binary Differential Evolution Based on Individual entropy for Feature Subset Optimization. IEEE Access, 7, 24109-24121.
• [20] Öztürk, C., Hançer, E., Karaboğa, D. 2015. A Novel Binary Artificial Bee Colony Algorithm Based on Genetic Operators. Information Science, 297, 154-170.
• [21] Jia, D., Duan, X., Khan, M. K. 2014. Binary Artificial Bee Colony Optimization Using Bitwise Operation (BitABC). Computers and Industrial Engineering, 76, 360–365.
• [22] Kiran, M. S., Gündüz, M. 2013. XOR Based Artificial Bee Colony algorithm for Binary Optimization. Turkish Journal of Electrical Engineering & Computation Sciences, 21, 2307–2328.
• [23] Kashan, M. H., Nahavandi, N., Kashan, A. H. 2012. DisABC: A New Artificial Bee Colony Algorithm for Binary Optimization. Applied Soft Computing, 12, 342-352.
• [24] Öztürk, C., Hançer, E., Karaboğa, D. 2014. Dynamic Clustering With Improved Binary Artificial Bee Colony-IDisABC. Applied Soft Computing, 28, 69-80.
• [25] Hançer, E., Xue, B., Karaboğa, D., Zhang, M. 2015. A Binary ABC Algorithm Based on Advanced Similarity scheme for Feature Selection. Applied Soft Computing, 36, 334-348.
• [26] Singhal, P. K., Noresh, R., Sherma, V. 2015. A Novel Strategy-Based Hybrid Binary Artificial Bee Colony Algorithm for Unit Commitment Problem. Arabian Journal for Science and Engineering, 40(5), 1455–1469.
• [27] Yurtkurtaran, A., Emel, E. 2016. A Discrete Artificial Bee Algorithm for Single Machine Scheduling Problem. International Journal of Production Research, 54(22), 6860-6878.
• [28] Zhang, X., Zhang, X. 2016. A Binary Artificial Bee Colony Algorithm for Constructing Spanning Trees in Vehicular ad Hoc Networks. Ad Hoc Networks, 58, 198-204.
• [29] Zhang, S., Gu, X. 2015. An Effective Discrete Artificial Bee Colony Algorithm for Flow Shop Scheduling Problem with Intermediate Buffers. Journal of Central South University, 22, 3471−3484.
• [30] Tasgetiren, M. F., Pan, Q., Suganthan, P. N., Chen, A. 2011. A Discrete Artificial Bee Colony Algorithm for the Total Flow Time Minimization in Permutation Flow Shops. Information Sciences, 181, 3459–3475.
• [31] Zhang, H., Ye, D. 2015. Key-Node-Based Local Search Discrete Artificial Bee Colony Algorithm for Obstacle-Avoiding Rectilinear Steiner Tree Construction. Neural Comput & Applications, 26, 875–898.
• [32] Ye, D., Chen, Z. 2015. A New Approach to Minimum Attribute Reduction Based on Discrete Artificial Bee Colony. Soft Computing, 19, 1893–1903.
• [33] Ribas, I., Companys, R., Tort-Martorell, X. 2015. An Efficient Discrete Artificial Bee Colony Algorithm for the Blocking Flow Shop Problem with Total Flowtime Minimization. Expert Systems with Applications, 42, 6155–6167.
• [34] Han, Y. Y., Gong, D., Sun, X. A Discrete Artificial Bee Colony Algorithm Incorporating Differential Evolution for the Flow-Shop Scheduling Problem with blocking. Engineering Optimization, 47, 927–946.
• [35] Schiezaro, M., Pedrini, H. 2013. Data Feature Selection Based on Artificial Bee Colony Algorithm. Journal on Image and Video Processing, 47.
• [36] Özmen, Ö., Batbat, T., Özen, T., Sinanoğlu, C., Güven, A. 2018. Optimum Assembly Sequence Planning System Using Discrete Artificial Bee Colony Algorithm. Mathematical Problems in Engineering, 2018, 340764.
• [37] Wei, L., Hanning, C. 2012. BABC: A Binary Version of Artificial Bee Colony Algorithm for Discrete Optimization. International Journal of Advancements in Computing Technology, 4(14), 307-314.
• [38] Tran, D. C., Wu, Z. 2014. New Approaches for Binary Artificial Bee Colony Algorithm for Solving 0-1 Knapsack Problem. Advances in Information Sciences and Service Sciences, 4(22), 464-471.
• [39] Kıran, M. S. 2015. The Continues Artificial Bee Colony Algorithm for Binary Optimization. Applied Soft Computing, 33, 15-23.
• [40] Mandala, M., Gupta, C. P. 2014. Binary Artificial Bee Colony Optimization for GENCO’s Profit Maximization under Pool Electricity Market. International Journal of Computer Applications, 90, 34-42.
• [41] Ozger, Z. B., Bolat, B., Diri, B. 2016. A Comparative Study on Binary Artificial Bee Colony Optimization Methods for Feature Selection. INnovations in Intelligent SysTems and Applications (INISTA), 2-5 Aug., Romaina, 1-4.
• [42] Karaboga, D., Akay, B. 2009. A Survey: Algorithms Simulating Bee Swarm Intelligence. Artificial Intelligence Review, 31, 61-85.
• [43] Mirjalili, S., Lewis, A. 2013. S-Shaped Versus v-Shaped Transfer Functions for Binary Particle Swarm Optimization. Swarm Evolution Computation, 9, 1–14.
• [44] Sivanandam, S., Deepa, S. 2008. Genetic Algorithm Implementation Using Matlab. Introduction to Genetic Algorithms, Berlin: Heidelberg, 211-262.
• [45] Mernik, M., Liu, S. H., Karaboga, D., Črepinšek, M. 2015. On Clarifying Misconceptions When Comparing Variants of the Artificial Bee Colony Algorithm by Offering a New Implementation. Information Sciences, 291, 115-127.
• [46] Draa, A. 2015. On the Performances of the Flower Pollination Algorithm–Qualitative and Quantitative Analyses. Applied Soft Computing, 34, 349-371.
• [47] Črepinšek, M., Liu, S. H., Mernik, L., Mernik, M. 2016. Is a Comparison of Results Meaningful from the Inexact Replications of Computational experiments?. Soft Computing, 20(1), 223-235.