Genetic Algorithm for Restricted Maximum k-Satisfiability in the Hopfield Network
DOI:
https://doi.org/10.9781/ijimai.2016.429Keywords:
Genetic Algorithms, Neural Network, Hopfield, K-satisfiabilityAbstract
The restricted Maximum k-Satisfiability MAX- kSAT is an enhanced Boolean satisfiability counterpart that has attracted numerous amount of research. Genetic algorithm has been the prominent optimization heuristic algorithm to solve constraint optimization problem. The core motivation of this paper is to introduce Hopfield network incorporated with genetic algorithm in solving MAX-kSAT problem. Genetic algorithm will be integrated with Hopfield network as a single network. The proposed method will be compared with the conventional Hopfield network. The results demonstrate that Hopfield network with genetic algorithm outperforms conventional Hopfield networks. Furthermore, the outcome had provided a solid evidence of the robustness of our proposed algorithms to be used in other satisfiability problem.Downloads
References
[1] D. Givry, Simon, J. Larrosa, P. Meseguer, and T. Schiex. “Solving Max-SAT as weighted CSP.” In Principles and Practice of Constraint Programming–CP 2003, Springer Berlin Heidelberg, 2003, pp. 363-376.
[2] Papadimitriou, Christos, and M. Yannakakis. “Optimization, approximation, and complexity classes.” In Proceedings of the twentieth annual ACM symposium on Theory of computing, ACM, 1988, pp. 229-234.
[3] W. A. T. W. Abdullah, The logic of neural networks. Physics Letters A, 176(3), 1993, pp. 202-206.
[4] J.J. Hopfield, D. W. Tank, Neural computation of decisions in optimization problem, Biological Cybernatics, 52, 141-152, 1985.
[5] R. Rojas, Neural Networks: A Systematic Introduction. Berlin: Springer, 1996.
[6] S. Sathasivam, Learning in the Recurrent Hopfield Network, Proceedings of the Fifth International Conference on Computer Graphics, Imaging and Visualisation, 323-328, 2008.
[7] M. Peng, N. K. Gupta, & A. F. Armitage, An investigation into the improvement of local minima of the Hopfield network. Neural networks, 9(7), pp. 1241-1253, 1996.
[8] S. Salcedo-Sanz, C. Bousoño-Calzón, & A. R Figueiras-Vidal, A mixed neural-genetic algorithm for the broadcast scheduling problem.Wireless Communications, IEEE Transactions on, vol. 2, no. 2, pp. 277-283, 2003.
[9] X. G. Ming and K. L. Mak. “A hybrid Hopfield network-genetic algorithm approach to optimal process plan selection.” International Journal of Production Research 38, no. 8, pp. 1823-1839, 2000.
[10] C. Y. Ngo, & V. O. Li, Fixed channel assignment in cellular radio networks using a modified genetic algorithm. Vehicular Technology, IEEE Transactions on, vol. 47, no. 1, pp. 163-172, 1998.
[11] S. Sathasivam, P.F. Ng, N. Hamadneh, Developing agent based modelling for reverse analysis method, 6 (22), pp. 4281-4288, 2013.
[12] U. P. Wen, K. M. Lan & H. S. Shih, A review of Hopfield neural networks for solving mathematical programming problems. European Journal of Operational Research, vol. 198, no. 3, pp. 675-687, 2009.
[13] S. Haykin, Neural Networks: A Comprehensive Foundation, New York: Macmillan College Publishing, 1999.
[14] S. Sathasivam, Upgrading Logic Programming in Hopfield Network, Sains Malaysiana, 39, 115-118, 2010.
[15] M. Velavan, Z. R. Yahya, M. N. A. Halif, & S. Sathasivam, (2015). Mean Field Theory in Doing Logic Programming Using Hopfield Network. Modern Applied Science, vol. 10, no. 1, p. 154, 2015.
[16] L. M. Ionescu, A. G. Mazare, & G. Serban, VLSI Implementation of an associative addressable memory based on Hopfield network model. IEEE Semiconductor Conference, vol. 2, pp. 499-502, 2010.
[17] W. A. T. W. Abdullah, Logic Programming on a Neural Network. Malaysian Journal of computer Science, 9 (1), 1-5, 1993.
[18] S. Sathasivam, “Learning Rules Comparison in Neuro-Symbolic Integration.” International Journal of Applied Physics and
Mathematics, vol.1, no.2, pp. 129, 2011.
[19] X. Zeng, and T. R. Martinez, “Improving the performance of the Hopfield network by using a relaxation rate.” In Artificial Neural Nets and Genetic Algorithms Springer Vienna.s, 1999, pp. 67-72.
[20] M. S. Kasihmuddin, “Modifying Activation Function in Neuro Symbolic Integration,” M.S. thesis, Dept. Mathematical Science., Universiti Sains Malaysia, Penang, Malaysia, 2014.
[21] M. Velavan, Boltzman Machine and Hyperbolic Activation Function in Higher Order Network, 9 (2), 140-146, 2014.
[22] E. Elbeltagi, T. Hegazy and D. Grierson, Comparison among five evolutionary-based optimization algorithms. Advanced engineering informatics, vol. 19, no. 1, pp. 43-53, 2005
[23] C. K. Chong, M. S. Mohamad, S. Deris, M. S. Shamsir, Y. W. Choon, and L. E. Chai, Improved differential evolution algorithm for parameter estimation to improve the production of biochemical pathway. International Journal of Interactive Multimedia and Artificial Intelligence, no.5, 2012.
[24] E. Nudelman, K. Leyton-Brown, H. H. Hoos, A. Devkar, and Y. Shoham, Understanding random SAT: Beyond the clauses-to-variables ratio. In Principles and Practice of Constraint Programming–CP 2004, Springer Berlin Heidelberg, 2004, pp. 438-452.
[25] A. Imada and K. Araki, What does the landscape of a Hopfield associative memory look like? In Evolutionary Programming VII, 1998, Springer Berlin Heidelberg, pp. 647-65.
[26] S. Sathasivam, W. A. T. W. Abdullah, Flatness of the Energy Landscape for Horn Clauses. SSJ, vol 1, no. 2, pp. 2, 2008.
[27] Aiman, U. and Asrar, N., Genetic Algorithm Based Solution to SAT-3 Problem. Journal of Computer Sciences and Applications, 3(2), pp. 33- 39, 2015.
[28] Zinovik, I., Kroening, D. and Chebiryak, Y., Computing binary combinatorial gray codes via exhaustive search with SAT solvers. Information Theory, IEEE Transactions on, 54(4), pp.1819-1823, 2008.
[29] Xie, J. and Dong, J., Heuristic genetic algorithms for general capacitated lot-sizing problems. Computers & Mathematics with applications, 44(1), pp. 263-276, 2002.
[30] Salcedo-Sanz, S. and Yao, X., A hybrid Hopfield network-genetic algorithm approach for the terminal assignment problem. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 34(6), pp. 2343-2353, 2004.
[31] Pooranian, Z., Shojafar, M., Tavoli, R., Singhal, M. and Abraham, A., A hybrid metaheuristic algorithm for Job scheduling on computational grids. Informatica, 37(2), pp.157, 2013.
[32] Kaushik, M., Comparative analysis of exhaustive search algorithm with ARPS algorithm for motion estimation. International Journal of Applied Information Systems, 1(6), pp. 16-19, 2012.
[33] Luke, S., Essentials of metaheuristics, 2nd edition. United States: Lulu, 2013.
[34] Mark, W.G., & Lee C.G., Routing in random multistage interconnections networks: Comparing exhaustive search, greedy, and neural network approaches. International Journal of Neural System, 2 (3), pp. 125-142, 1992.
[35] Hooker, J.N., Unifying local and exhaustive search. In L. Villasenor and A.I Martinez, editors. Proceeding of ENC 2005-Sixth Mexican International Conference on Computer Science, p. 237-243, 2005.
[36] Kumar, S., and Singh, M. P., Pattern recall analysis of the Hopfield neural network with a genetic algorithm. Computers & Mathematics with Applications, 60(4), pp. 1049-1057, 2010.
[37] Raman, V., Ravikumar, B., and Rao, S. S., A simplified NP-complete MAXSAT problem. Information Processing Letters. 65(1), pp. 1-6, 1998.
[38] Fernandez, W., Random 2-SAT: Result and Problems. Theoretical Computer Science. 265 (1): pp. 131-146, 2001.
[39] Pipatsrisawat, K., Palyan, A., Chavira, M., Choi, A., and Darwiche, A., Solving weighted Max-SAT problems in a reduced search space: A performance analysis. Journal on Satisfiability, Boolean Modeling and Computation. 4: pp. 191-217, 2008.
[40] Hansen, P. and Jaumard, B., Algorithms for the maximum satisfiability problem. Computing, 44(4), pp.279-303, 1990.
[41] Broder, A.Z., Frieze, A.M. and Upfal, E., On the satisfiability and maximum satisfiability of random 3-CNF formulas. In SODA (Vol. 93, pp. 322-330), 1993.
[42] Madsen, B. A., and Rossmanith, P. Maximum exact satisfiability: NPcompleteness proofs and exact algorithms. BRICS Report Series. 11(19), 2004.
[43] Borchers, B., & Furman, J., A two-phase exact algorithm for MAXSAT and weighted MAX-SAT problems. Journal of Combinatorial Optimization, 2(4), pp. 299-306, 1998.
[44] Layeb, A., Deneche, A. H., and Meshoul, S., A new artificial immune system for solving the maximum satisfiability problem. Trends in Applied Intelligent Systems, pp. 136-142, 2010.
[45] Kowalski, R. A., The early years of logic programming. Communications of the ACM. 31(1): pp. 38-43, 1988.
[46] Gottlieb J., Marchiori E., & Rossi C. Evolutionary algorithms for the satisfiability problem. Evolutionary Computation. 2002;10(1):35-50.
[47] Rossi, C., Marchiori, E., & Kok, J. N. (2000, March). An adaptive evolutionary algorithm for the satisfiability problem. In Proceedings of the 2000 ACM symposium on Applied computing-Volume 1 (pp. 463-469). ACM.
[48] Marchiori, E, & Rossi, C. (1999, July). A flipping genetic algorithm for hard 3-SAT problems. In Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation-Volume 1 (pp. 393-400). Morgan Kaufmann Publishers Inc.
[49] J. Singha, & R. H. Laskar, (2016). Hand gesture recognition using two-level speed normalization, feature selection and classifier fusion. Multimedia Systems, pp. 1-16.
Downloads
Published
-
Abstract14
-
PDF17
Submit Article
Information
