Sains Malaysiana 47(6)(2018): 1327–1335

http://dx.doi.org/10.17576/jsm-2018-4706-30

Discrete Hopfield Neural Network in Restricted Maximum k-Satisfiability Logic Programming

(Rangkaian Neural Hopfield Diskret dalam Pengaturcaraan Logik Maksimum

k-Kepuasan Terhad)

MOHD SHAREDUWAN MOHD KASIHMUDDIN¹*, MOHD ASYRAF MANSOR²

& SARATHA SATHASIVAM¹

¹Pusat Pengajian Sains Matematik, Universiti Sains Malaysia, 11800 USM, Pulau Pinang

Malaysia

²Pusat Pengajian Pendidikan Jarak Jauh, Universiti Sains Malaysia, 11800 USM, Pulau Pinang

Malaysia

Received: 19 August 2017/Accepted: 19 January 2018

ABSTRACT

Maximum k-Satisfiability (MAX-kSAT) consists of the most consistent interpretation that generate the maximum number of satisfied clauses. MAX-kSAT is an important logic representation in logic programming since not all combinatorial problem is satisfiable in nature. This paper presents Hopfield Neural Network based on MAX-kSAT logical rule. Learning of Hopfield Neural Network will be integrated with Wan Abdullah method and Sathasivam relaxation method to obtain the correct final state of the neurons. The computer simulation shows that MAX-kSAT can be embedded optimally in Hopfield Neural Network.

Keywords: Hopfield Neural Network; Maximum k-Satisfiability; Wan Abdullah method

ABSTRAK

Maksimum k-Kepuasan (MAX-kSAT) terdiri daripada penyelesaian yang paling konsisten untuk menghasilkan bilangan klausa yang betul secara maksimum. MAX-kSAT merupakan perwakilan logik yang penting dalam pengaturcaraan logik kerana tidak semua masalah kombinatori boleh dipuaskan. Artikel ini membentangkan Rangkaian Neural Hopfield berdasarkan peraturan logik MAX-kSAT. Pembelajaran Rangkaian Neural Hopfield akan diintegrasikan dengan kaedah Wan Abdullah dan kaedah rehat Sathasivam untuk mendapatkan tahap akhir neuron yang betul. Simulasi komputer menunjukkan bahawa MAX-kSAT boleh diintegrasi secara optimum dalam Rangkaian Neural Hopfield.

Kata kunci: Kaedah Wan Abdullah; maksimum k-Kepuasan; Rangkaian Neural Hopfield

REFERENCES

Abdul Rahman, N. 2017. Binomial distribution of 2sat interpretation. Private Communication.

Alzaeemi, S.A., Sathasivam, S., Adebayo, S.A., Kasihmuddin, M.S.M. & Mansor, M.A. 2017. Kernel machine to doing logic programming in hopfield network for solve non horn problem-3sat. MOJ Applied Bionics and Biomechanics 1(1): 1-6.

Berg, J. & Järvisalo, M. 2015. Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability. Artificial Intelligence 244: 110-142.

Borchers, B. & Furman, J. 1998. A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems. Journal of Combinatorial Optimization 2(4): 299-306.

Bouhmala, N. 2016. A variable neighbourhood search structure based-genetic algorithm for combinatorial optimisation problems. International Journal of Intelligent Systems Technologies and Applications 15(2): 127-146.

Feige, U. & Goemans, M. 1995. Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In Theory of Computing and Systems Proceedings, Third Israel Symposium. pp. 182-189.

Hamadneh, N., Sathasivam, S., Tilahun, S.L. & Choon, O.H. 2012. Learning logic programming in radial basis function network via genetic algorithm. Journal of Applied Sciences 12(9): 840-847.

Hölldobler, S., Kalinke, Y. & Störr, H.P. 1999. Approximating the semantics of logic programs by recurrent neural networks. Applied Intelligence 11(1): 45-58.

Hopfield, J.J. & Tank, D.W. 1985. Neural computation of decisions in optimization problems. Biological Cybernatics 52: 141-152.

Hopfield, J.J. 1982. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences 79(8): 2554-2558.

Imada, A. & Araki, K. 1998. What does the landscape of a Hopfield associative memory look like? International Conference on Evolutionary Programming. pp. 647-656.

Ionescu, L.M., Mazare, A.G. & Serban, G. 2010. VLSI Implementation of an associative addressable memory based on Hopfield network model. IEEE Semiconductor Conference 2: 499-502.

Kasihmuddin, M.S.M. & Sathasivam, S. 2016. Accelerating activation function in higher order logic programming. Advance in Industrial and Applied Mathematics: Proceedings of 23rd Malaysian National Symposium of Mathematical Sciences (SKSM23) 1750: 030008-1–030008-6 https://doi. org/10.1063/1.4954544.

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.

Kowalski, R.A. 1979. Logic for Problem Solving. New York: Elsevier Science Publishing,

Kumar, S. & Singh, M.P. 2010. Pattern recall analysis of the Hopfield network with a genetic algorithm. Computer and Mathematic with Applications 60: 1049-1057.

Layeb, A., Deneche, A.H. & Meshoul, S. 2010. A new artificial immune system for solving the maximum satisfiability problem. In Trends in Applied Intelligent Systems. Berlin, Heidelberg: Springer. pp. 136-142.

Liu, S. & de Melo, G. 2017. Should algorithms for random sat and max-sat be different? AAAI. pp. 3915-3921.

Madsen, B.A. & Rossmanith, P. 2004. Maximum exact satisfiability: NP-completeness proofs and exact algorithms. BRICS Report Series 04(19): 1-20.

Mansor, M.A. & Sathasivam, S. 2016. Performance analysis of activation function in higher order logic programming. Advance in Industrial and Applied Mathematics: Proceedings of 23rd Malaysian National Symposium of Mathematical Sciences (SKSM23) 1750: 030007-1–030007-7 https://doi. org/10.1063/1.4954543.

Mathias, A.C. & Rech, P.C. 2012. Hopfield neural network: The Hyperbolic tangent and the piecewise-linear activation functions. Neural Networks 34: 42-45.

Menaï, M.E.B. & Batouche, M. 2005. A backbone-based co-evolutionary heuristic for partial MAX-SAT. In Artificial Evolution. Berlin Heidelberg: Springer. pp. 155-166.

Muezzinoglu, M.K., Guzelis, C. & Zurada, J.M. 2003. A new design method for the complex-valued multistate Hopfield associative memory. IEEE Transactions on Neural Networks 14(4): 891-899.

Pinkas, G. & Dechter, R. 1995. Improving connectionist energy minimization, J. Artif. Intell. Res. (JAIR) 3: 223-248.

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

Pipatsrisawat, K., Palyan, A., Chavira, M., Choi, A. & Darwiche, A. 2008. Solving weighted Max-SAT problems in a reduced search space: A performance analysis. Journal on Satisfiability, Boolean Modeling and Computation 4: 191- 217.

Raman, V., Ravikumar, B. & Rao, S.S. 1998. A simplified NP-complete MAXSAT problem. Information Processing Letters 65(1): 1-6.

Rojas, R. 1996. Neural Networks: A Systematic Introduction. Berlin: Springer.

Santra, S., Quiroz, G., Ver Steeg, G. & Lida, D.A. 2014. Max 2-sat with up to 108 qubits. New Journal of Physics 16(4): 045006.

Sathasivam, S. & Fen, N.P. 2013. Developing agent based modelling for doing logic programming in Hopfield network. Applied Mathematical Sciences 7(1): 23-35.

Sathasivam, S. & Velavan, M. 2014. Boltzmann Machine and Hyperbolic Activation Function in Higher Order Network. Modern Applied Science 8(3): 140.

Sathasivam, S. & Wan Abdullah, A.T.W. 2007. Flatness of the energy landscape for horn clauses. Matematika 23: 147-156.

Sathasivam, S. 2008. Learning in the recurrent Hopfield network. Computer Graphics, Imaging and Visualisation, CGIV'08. Fifth International Conference on IEEE.pp. 323-328.

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

Sathasivam, S. 2011. Boltzmann machine and new activation function comparison. Applied Mathematical Sciences 5(78): 3853-3860.

Sulehria, H.K. & Zhang, Y. 2007. Hopfield neural networks: A survey. Proceedings of the 6th Conference on 6th WSEAS Int. Conf. on Artificial Intelligence, Knowledge Engineering and Data Bases. pp. 125-130.

Velavan, M., Yahya, Z.R., Abdul Halif, M.N. & Sathasivam, S. 2016. Mean field theory in doing logic programming using hopfield network. Modern Applied Science 10(1): 154-160.

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

Wan Abdullah, A.T.W. 1993. The logic of neural networks. Physics Letters A 176(3-4): 202-206.

Yannakakis, M. 1994. On the approximation of maximum satisfiability. Journal of Algorithms 17(3): 475-502.

Zeng, X. & Martinez, T. 1999. A new relaxation procedure in the hopfield network for solving optimization problems. Neural Processing Letters 10(3): 211-222.

Zhang, H., Hou, Y., Zhao, J., Wang, L., Xi, T. & Li, Y. 2017. Automatic welding quality classification for the spot welding based on the hopfield associative memory neural network and chernoff face description of the electrode displacement signal features. Mechanical Systems and Signal Processing 85: 1035-1043.

*Corresponding author; email: shareduwan@usm.my