Sains Malaysiana 49(11)(2020): 2847-2857

http://dx.doi.org/10.17576/jsm-2020-4911-23

Novel Random k Satisfiability for k ≤ 2 in Hopfield Neural Network

(Novel Rawak k Kepuasan untuk k ≤ 2 dalam Rangkaian Neural Hopfield)

SARATHA SATHASIVAM¹, MOHD. ASYRAF MANSOR²*, AHMAD IZANI MD ISMAIL¹, SITI ZULAIKHA MOHD JAMALUDIN¹, MOHD SHAREDUWAN MOHD KASIHMUDDIN¹ & MUSTAFA MAMAT³

¹School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM, Pulau Pinang, Malaysia

²School of Distance Education, Universiti Sains Malaysia, 11800 USM, Pulau Pinang, Malaysia

³Faculty of Informatics and Computing, Universiti Sultan Zainal Abidin, 21300 UniSZA Kuala Terengganu, Terengganu Darul Iman, Malaysia

Diserahkan: 23 Mac 2020/Diterima: 18 Mei 2020

ABSTRACT

The k Satisfiability logic representation (kSAT) contains valuable information that can be represented in terms of variables. This paper investigates the use of a particular non-systematic logical rule namely Random k Satisfiability (RANkSAT). RANkSAT contains a series of satisfiable clauses but the structure of the formula is determined randomly by the user. In the present study, RANkSAT representation is successfully implemented in Hopfield Neural Network (HNN) by obtaining the optimal synaptic weights. We focus on the different regimes for k ≤ 2 by taking advantage of the non-redundant logical structure, thus obtaining the final neuron state that minimizes the cost function. We also simulate the performances of RANkSAT logical rule using several performance metrics. The simulated results suggest that the RANkSAT representation can be embedded optimally in HNN and that the proposed method can retrieve the optimal final state.

Keywords: Artificial neural network; Hopfield neural network; logic programming; random satisfiability

ABSTRAK

Perwakilan logik k Kepuasan mengandungi maklumat berguna yang diwakilkan dalam sebutan pemboleh ubah. Kajian ini mengkaji penggunaan suatu peraturan logik yang tidak sistematik iaitu logik k Kepuasan Rawak (RANkSAT). RANkSAT mengandungi siri klausa penuh tetapi struktur rumusnya ditentukan secara rawak oleh pengguna. Dalam kajian ini, perwakilan RANkSAT berjaya dilaksanakan untuk Rangkaian Neural Hopfield (HNN) dengan memperoleh pemberat sinapsis yang optimum. Fokus diberikan kepada rejim berbeza bagi k ≤ 2 dengan menggunakan struktur logik yang tidak berulang dan justeru memperoleh secara optimal keadaan neuron akhir yang meminimumkan fungsi kos. Prestasi logik k Kepuasan Rawak disimulasi dengan menggunakan beberapa indikator prestasi tertentu. Keputusan simulasi menunjukkan perwakilan RANkSAT boleh dimasukkan secara optimum dalam HNN dan teknik yang telah dicadangkan berupaya memperoleh semula perwakilan neuron akhir yang optimum.

Kata kunci: Kepuasan rawak; rangkaian neural buatan; rangkaian neural Hopfield; pengaturcaraan logik

RUJUKAN

Abdullah, W.A.T.W. 1996. Logic programming in neural networks. International Journal of Computer Science 9(1): 1-5.

Abdullah, W.A.T.W. 1992. Logic programming on a neural network. International Journal of Intelligent Systems 7(6): 513-519.

Amendola, G., Ricca, F. & Truszczynski, M. 2020. New models for generating hard random boolean formulas and disjunctive logic programs. Artificial Intelligence 279: 103185.

Barra, A., Beccaria, M. & Fachechi, A. 2018. A new mechanical approach to handle generalized Hopfield neural networks. Neural Networks 106: 205-222.

Fan, Y. & Shen, J. 2011. On the phase transitions of random k-constraint satisfaction problems. Artificial Intelligence 175(3-4): 914-927.

Fitzsimmons, M. & Kunze, H. 2019. Combining Hopfield neural networks, with applications to grid-based mathematics puzzles. Neural Networks 118: 81-89.

Gao, Y. 2009. Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability. Artificial Intelligence 173(14): 1343-1366.

Hamadneh, N., Sathasivam, S. & Choon, O.H. 2012. Higher order logic programming in radial basis function neural network. Applied Mathematical Sciences 6(3): 115-127.

Hopfield, J.J. & Tank, D.W. 1985. “Neural” computation of decisions in optimization problems. Biological Cybernetics 52(3): 141-152.

Jia, D., Duan, X. & Khan, M.K. 2014. Binary artificial bee colony optimization using bitwise operation. Computers & Industrial Engineering 76: 360-365.

Kasihmuddin, M.S.M., Mansor, M.A. & Sathasivam, S. 2019a. Students’ performance via satisfiability reverse analysis method with Hopfield Neural Network. Proceedings of the International Conference on Mathematical Sciences and Technology 2018 (MATHTECH2018): Innovative Technologies for Mathematics & Mathematics for Technological Innovation. p. 060035.

Kasihmuddin, M.S.M., Mansor, M.A., Basir, M., Faisal, M. & Sathasivam, S., 2019b. Discrete mutation Hopfield neural network in propositional satisfiability. Mathematics 7(11): 1133.

Kasihmuddin, M.S.M., Mansor, M.A. & Sathasivam, S. 2018a. Satisfiability based reverse analysis method in diabetes detection. In Proceedings of the 25th National Symposium on Mathematical Sciences (SKSM25): Mathematical Sciences as the Core of Intellectual Excellence. p. 020020.

Kasihmuddin, M.S.M., Mansor, M.A. & Sathasivam, S. 2018b. Discrete Hopfield Neural Network in restricted maximum k-satisfiability logic programming. Sains Malaysiana 47(6): 1327-1335.

Kasihmuddin, M.S.M., Mansor, M.A. & Sathasivam, S. 2017. Hybrid genetic algorithm in the hopfield network for logic satisfiability problem. Pertanika Journal of Science & Technology 25(1): 139-152.

Kasihmuddin, M.S.M., Mansor, M.A. & Sathasivam, S. 2016. Bezier Curves Satisfiability Model in Enhanced Hopfield Network. International Journal of Intelligent Systems and Applications 8(12): 9-17.

Kho, L.C., Kasihmuddin, M.S.M., Mansor, M. & Sathasivam, S. 2020. Logic mining in league of legends. Pertanika Journal of Science & Technology 28(1): 211-225.

Kobayashi, M. 2019. Storage capacity of hyperbolic Hopfield neural networks. Neurocomputing 369: 185-190.

Liu, D., Wu, Y.L., Li, X. & Qi, L. 2020. Medi-Care AI: Predicting medications from billing codes via robust recurrent neural networks. Neural Networks 124: 109-116.

Maneva, E. & Alistair, S. 2008. On the satisfiability threshold and clustering of solutions of random 3-SAT formulas. Theoretical Computer Science 407(1-3): 359-369.

Mansor, M.A. & Sathasivam, S. 2016. Accelerating activation function for 3-satisfiability logic programming. International Journal of Intelligent Systems and Applications 8(10): 44-50.

Mansor, M.A., Jamaludin, S.Z.M., Kasihmuddin, M.S.M., Alzaeemi, S.A., Basir, M.F.M. & Sathasivam, S. 2020. Systematic Boolean satisfiability programming in radial basis function neural network. Processes 8(2): 214.

Mansor, M.A., Sathasivam, S. & Kasihmuddin, M.S.M. 2018. Artificial immune system algorithm with neural network approach for social media performance metrics. In Proceedings of the 25th National Symposium on Mathematical Sciences (SKSM25): Mathematical Sciences as the Core of Intellectual Excellence. p. 020072.

Mansor, M.A., Kasihmuddin, M.S.M. & Sathasivam, S. 2017a. Artificial immune system paradigm in the Hopfield network for 3-satisfiability problem. Pertanika Journal of Science & Technology 25(4): 1173-1188.

Mansor, M.A., Kasihmuddin, M.S.M. & Sathasivam, S. 2017b. Robust artificial immune system in the Hopfield network for maximum k-satisfiability. International Journal of Intelligent Systems and Applications 4(4): 63-71.

Mansor, M.A., Kasihmuddin, M.S.M. & Sathasivam, S. 2016a. VLSI circuit configuration using satisfiability logic in Hopfield network. International Journal of Intelligent Systems and Applications 8(9): 22-29.

Mansor, M.A., Kasihmuddin, M.S.M. & Sathasivam, S. 2016b. Enhanced Hopfield Network for pattern satisfiability optimization. International Journal of Intelligent Systems and Applications 8(11): 27-33.

Pinkas, G. 1991. Symmetric neural networks and propositional logic satisfiability. Neural Computation 3(2): 282-291.

Reddy, K.S., Panwar, L., Panigrahi, B.K. & Kumar, R. 2019. Binary whale optimization algorithm: A new metaheuristic approach for profit-based unit commitment problems in competitive electricity markets. Engineering Optimization 51(3): 369-389.

Sathasivam, S. 2010. Upgrading logic programming in Hopfield network. Sains Malaysiana 39(1): 115-118.

Schawe, H., Bleim, R. & Hartmann, A.K. 2019. Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming. PLoS ONE 14(4): e0215309.

Sharma, M. & Garg, R. 2020. An artificial neural network based approach for energy efficient task scheduling in cloud data centers. Sustainable Computing: Informatics and Systems 26: 100373.

Wang, X.Y. & Li, Z.M. 2019. A color image encryption algorithm based on Hopfield chaotic neural network. Optics and Lasers in Engineering 115: 107-118.

*Pengarang untuk surat-menyurat; email: asyrafman@usm.my