Robust Artificial Immune System in the Hopfield network for Maximum k-Satisfiability

Authors

DOI:

https://doi.org/10.9781/ijimai.2017.448

Keywords:

Algorithms, Neural Network, Hopfield, Artificial Immune System, Brute Force
Supporting Agencies
The authors fully acknowledged Ministry of Higher Education (MOHE) and School of Mathematical Sciences, Universiti Sains Malaysia for the support which makes this important research viable and effective.

Abstract

Artificial Immune System (AIS) algorithm is a novel and vibrant computational paradigm, enthused by the biological immune system. Over the last few years, the artificial immune system has been sprouting to solve numerous computational and combinatorial optimization problems. In this paper, we introduce the restricted MAX-kSAT as a constraint optimization problem that can be solved by a robust computational technique. Hence, we will implement the artificial immune system algorithm incorporated with the Hopfield neural network to solve the restricted MAX-kSAT problem. The proposed paradigm will be compared with the traditional method, Brute force search algorithm integrated with Hopfield neural network. The results demonstrate that the artificial immune system integrated with Hopfield network outperforms the conventional Hopfield network in solving restricted MAX-kSAT. All in all, the result has provided a concrete evidence of the effectiveness of our proposed paradigm to be applied in other constraint optimization problem. The work presented here has many profound implications for future studies to counter the variety of satisfiability problem.

Downloads

Download data is not yet available.

References

Xiao, R. B., & Wang, L. (2002). Artificial immune system: principle, models, analysis and perspectives. Chinese Journal of Computers (Chinese Edition), 25(12), 1281–1293.

Hart, E., & Timmis, J. (2008). Application areas of AIS: The past, the present and the future. Applied Soft Computing, 8(1), 191–201.

Dasgupta, D., Ji, Z., & González, F. A. (2003). Artificial immune system (AIS) research in the last five years. In Proceedings of the IEEE Congress on Evolutionary Computation (Vol. 1, pp. 123–130).

Farmer, J. D., Packard, N. H., & Perelson, A. S. (1986). The immune system, adaptation, and machine learning. Physica D: Nonlinear Phenomena, 22(1), 187–204.

Timmis, J., & Neal, M. (2001). A resource limited artificial immune system for data analysis. Knowledge-Based Systems, 14(3), 121–130.

Cruz-Cortés, N., Trejo-Pérez, D., & Coello, C. A. C. (2005). Handling constraints in global optimization using an artificial immune system. In International Conference on Artificial Immune Systems (pp. 234–247).

de Castro, L. N., & Timmis, J. (2002). Artificial immune systems: A novel paradigm to pattern recognition. In Artificial Neural Networks in Pattern Recognition (pp. 67–84).

Layeb, A., & Deneche, A. H. (2007). Multiple sequence alignment by immune artificial system. In IEEE/ACS International Conference on Computer Systems and Applications (pp. 336–342).

Engin, O., & Döyen, A. (2004). A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Generation Computer Systems, 20(6), 1083–1095.

Layeb, A., Deneche, A. H., & Meshoul, S. (2010). A new artificial immune system for solving the maximum satisfiability problem. In International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (pp. 136–142).

Hansen, P., & Jaumard, B. (1990). Algorithms for the maximum satisfiability problem. Computing, 44(4), 279–303.

Crescenzi, P., & Kann, V. (1997). Approximation on the web: A compendium of NP optimization problems. In International Workshop on Randomization and Approximation Techniques in Computer Science (pp. 111–118). Springer.

Broder, A. Z., Frieze, A. M., & Upfal, E. (1993). On the satisfiability and maximum satisfiability of random 3-CNF formulas. In Proceedings of SODA (pp. 322–330).

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

Hopfield, J. J., & Tank, D. W. (1985). Neural computation of decisions in optimization problem. Biological Cybernetics, 52, 141–152.

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

Abdullah, W. A. T. W. (1993). Logic programming on a neural network. Malaysian Journal of Computer Science, 9(1), 1–5.

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

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

Fernández, J. R. M., & Vidal, J. D. L. C. B. (2016). Improved shape parameter estimation in K clutter with neural networks and deep learning. International Journal of Interactive Multimedia and Artificial Intelligence, 3.

Sathasivam, S., & Abdullah, W. A. T. W. (2008). Flatness of the energy landscape for Horn clauses. SSJ, 1(2), 2.

Aiman, U., & Asrar, N. (2015). Genetic algorithm based solution to SAT-3 problem. Journal of Computer Sciences and Applications, 3(2), 33–39.

Verma, D., Kakkar, N., & Mehan, N. (2014). Comparison of brute-force and KD tree algorithm. International Journal of Advanced Research in Computer and Communication Engineering, 3(1), 5291–5294.

Abdeen, R. A. (2011). An algorithm for string searching based on brute-force algorithm. International Journal of Computer Science and Network Security, 11(7), 24–27.

Zinovik, I., Kroening, D., & Chebiryak, Y. (2008). Computing binary combinatorial Gray codes via exhaustive search with SAT solvers. IEEE Transactions on Information Theory, 54(4), 1819–1823.

Haddouch, K., Elmoutaoukil, K., & Ettaouil, M. (2016). Solving the weighted constraint satisfaction problems via the neural network approach. International Journal of Interactive Multimedia and Artificial Intelligence, 4 (Special Issue).

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

Kowalski, R. A. (1988). The early years of logic programming. Communications of the ACM, 31(1), 38–43.

Imada, A., & Araki, K. (1998). What does the landscape of a Hopfield associative memory look like? In Evolutionary Programming VII (pp. 647–665). Springer.

Haykin, S. (1999). Neural Networks: A Comprehensive Foundation. Macmillan College Publishing.

Velavan, M., Yahya, Z. R., Halif, M. N. A., & Sathasivam, S. (2015). Mean field theory in doing logic programming using Hopfield network. Modern Applied Science, 10(1), 154.

Elbeltagi, E., Hegazy, T., & Grierson, D. (2005). Comparison among five evolutionary-based optimization algorithms. Advanced Engineering Informatics, 19(1), 43–53.

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

Baldominos Gómez, A., Mingueza, N. L., & García del Pozo, M. C. (2015). OpinAIS: An artificial immune system-based framework for opinion mining. International Journal of Interactive Multimedia and Artificial Intelligence.

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

Bordeaux, L., Hamadi, Y., & Zhang, L. (2006). Propositional satisfiability and constraint programming: A comparative survey. ACM Computing Surveys, 38(4), 12.

Sathasivam, S., Ng, P. F., & Hamadneh, N. (2013). Developing agent based modelling for reverse analysis method. Research Journal of Applied Sciences, Engineering and Technology, 6(22), 4281–4288.

Ming, X. G., & Mak, K. L. (2000). A hybrid Hopfield network–genetic algorithm approach to optimal process plan selection. International Journal of Production Research, 38(8), 1823–1839.

Wen, U. P., Lan, K. M., & Shih, H. S. (2009). A review of Hopfield neural networks for solving mathematical programming problems. European Journal of Operational Research, 198(3), 675–687.

Ionescu, L. M., Mazare, A. G., & Serban, G. (2010). VLSI implementation of an associative addressable memory based on Hopfield network model. In IEEE Semiconductor Conference (Vol. 2, pp. 499–502).

Goldberg, D. E., & Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms (Vol. 1, pp. 69–93).

Semwal, V. B., Mondal, K., & Nandi, G. C. (2015). Robust and accurate feature selection for humanoid push recovery and classification: Deep learning approach. Neural Computing and Applications, 1–10.

Singha, J., & Laskar, R. H. (2016). Hand gesture recognition using two-level speed normalization, feature selection and classifier fusion. Multimedia Systems, 1–16.

Kumari, P., & Vaish, A. (2016). Feature-level fusion of mental task’s brain signal for an efficient identification system. Neural Computing and Applications, 27(3), 659–669.

Downloads

Published

2017-06-01
Metrics
Views/Downloads
  • Abstract
    23
  • PDF
    10

How to Cite

Mansor, M. A. B., Kasihmuddin, M. S. B. M., and Sathasivam, S. (2017). Robust Artificial Immune System in the Hopfield network for Maximum k-Satisfiability. International Journal of Interactive Multimedia and Artificial Intelligence, 4(4), 63–71. https://doi.org/10.9781/ijimai.2017.448

Issue

Vol. 4 No. 4 (2017): IJIMAI 2017 - Regular Issue.

Section

Regular Articles