Artificial Bee Colony in the Hopfield Network for Maximum \(k\)-Satisfiability Problem
DOI:
https://doi.org/10.26713/jims.v8i5.467Keywords:
Artificial bee colony, Hopfield neural network, Maximum k-SatisfiabilityAbstract
Artificial bee colony (ABC) is a relatively new swarm intelligence method that solve various type of optimization problems. This algorithm utilized the behavior of the actual bees to minimize or maximize the cost function of any combinatorial problems. The aim of this study is to introduce the hybridization of artificial bee colony algorithm with Hopfield network in doing Restricted MAX-kSAT. The performance of the proposed paradigm will be compared with conventional Hopfield network. The result obtained from computer simulation indicates the beneficial features of ABC towards Hopfield network in doing MAX-kSAT. The findings have led to a significant implication on the choice of determining an alternative method to do MAX-kSAT problem.Downloads
References
S. Bart, D.G. Mitchell, and H.J. Levesque, Generating hard satisfiability problems, Artificial intelligence 81 (1), (1996), 17-29.
H. Frederick, D.A. Waterman, and D.B. Lenat, Building expert systems, Reading, Ma, Addisson-Wesley (1983).
N. Tin, W.A. Perkins, T.J. Laffey, and D. Pecora. Checking an Expert Systems Knowledge Base for Consistency and Completeness, 85 (1), (1985), 375-378.
P. Asirelli, M.D. Santis, and M. Martelli, Integrity constraints in logic databases, The Journal of Logic Programming, 2 (3), (1985), 221-232.
H. Gallaire, J. Minker, and J. M. Nicolas, Logic and databases: A deductive approach, Computing Surveys 16 (2), (1984), 153–185. [6] P. Hansen and B. Jaumard, Algorithms for the maximum satisfiability problem, Computing 44 (4) (1990), 279-303.
R.M. Karp, Reducibility among combinatorial problems, Complexity of computer computations, springer, US (1972), 85-103. [8] J. McCarthy, M.L. Minsky, N. Rochester, and C.E. Shannon. A proposal for the dart mouth summer research project on artificial intelligence, AI magazine, 27 (4), (2006), 12. [9] R. Trippi, and E. Turban. Neural networks in finance and investing: Using artificial intelligence to improve real world performance, McGraw-Hill Inc (1992).
J.J. Hopfield, and D.W. Tank. Neural computation of decisions in optimization problems, Biological cybernetics, 52 (3), (1985), 141-152.
S. Sathasivam, Learning in the Recurrent Hopfield Network, Computer Graphics, Imaging and Visualization, CGIV'08. Fifth International Conference on IEEE (2008), 323-328.
S. Sathasivam, Energy Landscapes for Hopfield Network Programmed with Program Clauses, In 4th IASTED International Conference in Advances Computer Science and Technology, Langkawi, Malaysia, (2008), 179-182.
W.A.T.W. Abdullah, The logic of neural networks, Physics Letters A, 176 (3), (1993), 202-206.
W.A.T.W. Abdullah, Logic programming on a neural network, International journal of intelligent systems 7 (6), (1992), 513-519.
R. Rojas, Neural networks: a systematic introduction. Springer Science & Business Media, (2013). [16] G. Pinkas, Logical inference in symmetric connectionist networks, (1992).
S. Sancho, and X. Yao, A hybrid Hopfield network-genetic algorithm approach for the terminal assignment problem, IEEE Transactions on Systems, Man, and Cybernetics 34 (6), (2004), 2343-2353.
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 (8), (2000), 1823-1839.
S. Salcedo-Sanz, C. Bousoño-Calzón, and A. R. Figueiras-Vidal, A mixed neural-genetic algorithm for the broadcast scheduling problem, Wireless Communications, IEEE Transactions on 2 (2), (2003), 277-283
M. Basu, Artificial bee colony optimization for multi-area economic dispatch, International Journal of Electrical Power & Energy Systems 49 (2013), 181-187. [21] A. Banharnsakun, T. Achalakul, and B. Sirinaovakul, The best-so-far selection in artificial bee colony algorithm, Applied Soft Computing 11(2), (2011), 2888-2901.
D. Karaboga, and B. Basturk, A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, Journal of global optimization 39(3), (2007), 459-471.
A. Singh, An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem, Applied Soft Computing 9(2), (2009), 625-631.
F. Kang, J. Li, and Q. Xu, Structural inverse analysis by hybrid simplex artificial bee colony algorithms, Computers & Structures 87(13), (2009), 861-870.
N. Karaboga, A new design method based on artificial bee colony algorithm for digital IIR filters, Journal of the Franklin Institute 346(4), (2009), 328-348.
D. Teodorović, and P. Lućić, Intelligent parking systems, European Journal of Operational Research 175(3), (2006), 1666-1681.
Drias, Habiba, S. Sadeg, and S. Yahi, Cooperative bees swarm for solving the maximum weighted satisfiability problem, In International Work-Conference on Artificial Neural Networks, Springer Berlin Heidelberg, (2005), 318-325.
D. E. Goldberg, and D. Kalyanmoy, A comparative analysis of selection schemes used in genetic algorithms, Foundations of genetic algorithms 1 (1991), 69-93.
A. Muthiah, and R. Rajkumar, A Comparison of Artificial Bee Colony algorithm and Genetic Algorithm to Minimize the Makespan for Job Shop Scheduling, Procedia Engineering 97 (2014), 1745-1754.
W. Zhang, Configuration landscape analysis and backbone guided local search.: Part I: Satisfiability and maximum satisfiability, Artificial Intelligence 158 (1) (2004), 1-26.
A.Z. Broder, A.M. Frieze, and E. Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, SODA, 93 (1993), 322-330.
A. Layeb, A. H. Deneche and S. Meshoul, A new artificial immune system for solving the maximum satisfiability problem, International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (2010), 136-142.
A. Layeb, A new greedy randomised adaptive search procedure for solving the maximum satisfiability problem, International Journal of Operational Research 17 (4) (2013), 509-525.
J. Nievergelt, (2000), Exhaustive search, combinatorial optimization and enumeration: Exploring the potential of raw computing power, Sofsem 2000: theory and practice of informatics, Springer, Berlin Heidelberg (2000), 18-35.
B. Borchers and J. Furman, A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems, Journal of Combinatorial Optimization 2 (4) (1998), 299-306.
M. Jose and R. Majumdar, Cause clue clauses: error localization using maximum satisfiability, ACM SIGPLAN Notices 46 (6) (2011), 437-446.
R. Niedermeier and P. Rossmanith, New upper bounds for maximum satisfiability, Journal of Algorithms 36 (1) (2000), 63-88.
T. Asano and D.P. Williamson, Improved approximation algorithms for MAX SAT, Journal of Algorithms 42 (1) (2002), 173-202.
S. Sathasivam, Upgrading Logic Programming in Hopfield Network, Sains Malaysiana 39 (1) (2010), 115-118.
M.K. Muezzinoglu, C. Guzelis, and J.M. Zurada, A new design method for the complex-valued multistate Hopfield associative memory, IEEE Transactions on Neural Networks 14 (4) (2003), 891-899.
G. Pinkas, Reasoning, nonmonotonicity and learning in connectionist networks that capture propositional knowledge, Artificial Intelligence 77 (2) (1995), 203-247.
S. Sathasivam, N. Hamadneh, and O.H Choon, Comparing neural networks: Hopfield network and RBF network, Applied Mathematical Sciences 5 (69) (2011), 3439-3452.
B. Ata and R. Coban, Artificial Bee Colony Algorithm Based Linear Quadratic Optimal Controller Design for a Nonlinear Inverted Pendulum, International Journal of Intelligent Systems and Applications in Engineering 3 (1) (2015), 1-6.
U. Aiman and N. Asrar, Genetic Algorithm Based Solution to SAT-3 Problem, Journal of Computer Sciences and Applications, 3 (2) (2015), 33-39.
I. Zinovik, D. Kroening, and Y. Chebiryak, Computing binary combinatorial gray codes via exhaustive search with SAT solvers, Information Theory, IEEE Transactions 54 (4) (2008), 1819-1823.
A. Imada and K. Araki, What does the landscape of a Hopfield associative memory look like, Evolutionary Programming VII, Springer, Berlin (1998), 647-656.
L.M. Ionescu, A.G. Mazare and G. Serban, VLSI Implementation of an associative addressable memory based on Hopfield network model, IEEE Semiconductor Conference 2 (2010), 499-502.
S. Sathasivam, Energy relaxation for Hopfield Network with the new learning rule, International Conference on Power Control and Optimization, (2009), 1-3
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
