{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T20:05:50Z","timestamp":1769717150708,"version":"3.49.0"},"reference-count":37,"publisher":"SAGE Publications","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IFS"],"published-print":{"date-parts":[[2023,7,2]]},"abstract":"<jats:p>Constraint satisfaction problems have a wide range of applications in areas such as basic computer theory research and artificial intelligence, and many major studies in industry are not solved directly, but converted into instances of satisfiability problems for solution. Therefore, the solution of the satisfiability problem is a central problem in many important areas in the future. A large number of solution algorithms for this problem are mainly based on completeness algorithms and heuristic algorithms. Intelligent optimization algorithms with heuristic policies run significantly more efficiently on large-scale instances compared to completeness algorithms. This paper compares the principles, implementation steps, and applications of several major intelligent optimization algorithms in satisfiability problems, analyzes the characteristics of these algorithms, and focuses on the performance in solving satisfiability problems under different constraints. In terms of algorithms, evolutionary algorithms and swarm intelligence algorithms are introduced; in terms of applications, the solution to the satisfiability problem is studied. At the same time, the performance of the listed intelligent optimization algorithms in applications is analyzed in detail in terms of the direction of improvement of the algorithms, advantages and disadvantages and comparison algorithms, respectively, and the future application of intelligent optimization algorithms in satisfiability problems is prospected.<\/jats:p>","DOI":"10.3233\/jifs-230073","type":"journal-article","created":{"date-parts":[[2023,4,25]],"date-time":"2023-04-25T12:28:49Z","timestamp":1682425729000},"page":"445-461","source":"Crossref","is-referenced-by-count":3,"title":["A survey of intelligent optimization algorithms for solving satisfiability problems"],"prefix":"10.1177","volume":"45","author":[{"given":"Lan","family":"Yang","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan"}]},{"given":"Xiaofeng","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan"}]},{"given":"Hongsheng","family":"Ding","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan"}]},{"given":"Yi","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan"}]},{"given":"Xingyu","family":"Zhao","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan"}]},{"given":"Lichao","family":"Pang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan"}]}],"member":"179","reference":[{"key":"10.3233\/JIFS-230073_ref2","doi-asserted-by":"crossref","unstructured":"Davis M. , A Computing Procedure for Quantification Theory[J], Journal of the Acm 7 (1960).","DOI":"10.1145\/321033.321034"},{"issue":"8","key":"10.3233\/JIFS-230073_ref3","doi-asserted-by":"crossref","first-page":"103397","DOI":"10.1016\/j.artint.2020.103397","article-title":"Understanding the power of max-sat resolution through up-resilience[J]","volume":"289","author":"Cherif","year":"2020","journal-title":"Artificial Intelligence"},{"issue":"9","key":"10.3233\/JIFS-230073_ref7","doi-asserted-by":"crossref","first-page":"1321","DOI":"10.1093\/comjnl\/bxz063","article-title":"NuDist: An Efficient Local Search Algorithm for (Weighted) Partial MaxSAT[J]","volume":"63","author":"Lei","year":"2020","journal-title":"The Computer Journal"},{"key":"10.3233\/JIFS-230073_ref8","doi-asserted-by":"crossref","first-page":"103354","DOI":"10.1016\/j.artint.2020.103354","article-title":"Old techniques in new ways:clause weighting, unit propagation and hybridization for maximum satisfiability[J]","volume":"287","author":"Cai","year":"2020","journal-title":"Artificial Intelligence"},{"issue":"02","key":"10.3233\/JIFS-230073_ref13","first-page":"52","article-title":"Genetic algorithm is used to solve NP complete problems [J]","author":"Yang Qing","year":"2001","journal-title":"Journal of Shandong University: Natural Science Edition"},{"key":"10.3233\/JIFS-230073_ref14","unstructured":"Wu Sheng , Solving 3-SAT Problem with Genetic Algorithm [J], Fujian Computer (7) (2005)."},{"key":"10.3233\/JIFS-230073_ref15","unstructured":"Corne D. , Dorigo M. and Glover F. , New Ideas in Optimization, McGraw-Hill Ltd., UK (1999)."},{"key":"10.3233\/JIFS-230073_ref16","first-page":"163","article-title":"Object-oriented implementation of heuristic search methods for graph coloring, maximum clique and satisfiability[J]","volume":"26","author":"Fleurent","year":"1996","journal-title":"Dimacs Ser Discrete Math"},{"issue":"6","key":"10.3233\/JIFS-230073_ref17","first-page":"41","article-title":"Solving 3-SAT Problem Based on Improved Genetic Algorithm [J]","volume":"33","author":"Yu\u2019an Zhang","year":"2015","journal-title":"Journal of Qinghai University: Natural Science Edition"},{"issue":"4","key":"10.3233\/JIFS-230073_ref19","first-page":"4","article-title":"Solving the satisfiability problem based on improved genetic algorithm [J]","author":"Guosheng Cao","year":"2008","journal-title":"Modern Computer"},{"issue":"4","key":"10.3233\/JIFS-230073_ref20","first-page":"xxviii+365","article-title":"Genetic algorithms and genetic programming[J]","volume":"7","author":"Grafeeva","year":"2013","journal-title":"Parallel Processing Letters"},{"issue":"4","key":"10.3233\/JIFS-230073_ref22","doi-asserted-by":"crossref","first-page":"115","DOI":"10.25046\/aj020416","article-title":"Solving the SAT problem using Genetic Algorithm[J]","volume":"2","author":"Bhattacharjee","year":"2017","journal-title":"Advances in Science Technology and Engineering Systems Journal"},{"key":"10.3233\/JIFS-230073_ref26","doi-asserted-by":"crossref","unstructured":"Baeck T. , Fogel D.B. and Michalewicz Z. , Handbook of Evolutionary Computation, IOP Publishing Ltd., 1997.","DOI":"10.1201\/9780367802486"},{"issue":"3","key":"10.3233\/JIFS-230073_ref30","first-page":"4","article-title":"Improved ant colony algorithm for solving satisfiable problems [J]","volume":"45","author":"Fen Lin","year":"2009","journal-title":"Computer Engineering and Application"},{"issue":"8","key":"10.3233\/JIFS-230073_ref31","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1016\/S0167-739X(00)00044-3","article-title":"A Graph-based Ant System and its convergence[J]","volume":"16","author":"Walter","year":"2000","journal-title":"Future Generations Computer Systems: FGCS"},{"issue":"99","key":"10.3233\/JIFS-230073_ref34","first-page":"1","article-title":"An Effective SAT Solver Utilizing ACO based on Heterogenous Systems[J]","volume":"PP","author":"Youness","year":"2020","journal-title":"IEEE Access"},{"issue":"2","key":"10.3233\/JIFS-230073_ref40","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.20057","article-title":"Survey propagation: an algorithm for satisfiability[J]","volume":"27","author":"Braunstein","year":"2010","journal-title":"Random Structures & Algorithms"},{"issue":"1-2","key":"10.3233\/JIFS-230073_ref45","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1023\/A:1006343127545","article-title":"Guided local search for solving SAT and weighted MAX-SAT problems","volume":"24","author":"Mills","year":"2000","journal-title":"Journal of Automated Reasoning"},{"issue":"5","key":"10.3233\/JIFS-230073_ref47","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1023\/A:1011306011437","article-title":"Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: Experimental evaluation","volume":"7","author":"Yagiura","year":"2001","journal-title":"Journal of Heuristics"},{"key":"10.3233\/JIFS-230073_ref49","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/S0167-8191(05)80147-4","article-title":"Robust taboo search for the quadratic assignment problem","volume":"17","author":"Taillard","year":"1991","journal-title":"Parallel Computing"},{"issue":"2","key":"10.3233\/JIFS-230073_ref50","doi-asserted-by":"crossref","first-page":"138","DOI":"10.4304\/jait.3.2.138-146","article-title":"A Clonal Selection Algorithm Based Tabu Search for Satisfiability Problems[J]","volume":"3","author":"Layeb","year":"2012","journal-title":"Journal of Advances in Information Technology"},{"issue":"10","key":"10.3233\/JIFS-230073_ref51","doi-asserted-by":"crossref","first-page":"661","DOI":"10.4236\/ijcns.2012.510068","article-title":"A Multilevel Tabu Search for the Maximum Satisfiability Problem[J]","volume":"05","author":"Bouhmala","year":"2012","journal-title":"International Journal of Communications, Network and System Sciences"},{"issue":"2","key":"10.3233\/JIFS-230073_ref52","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1287\/ijoc.6.2.126","article-title":"The reactive tabu search","volume":"6","author":"Battiti","year":"1994","journal-title":"ORSA Journal on Computing"},{"key":"10.3233\/JIFS-230073_ref53","doi-asserted-by":"crossref","unstructured":"Battiti R. , Brunato M. and Mascia F. , Reactive search and intelligent optimization, Springer Science & Business Media 45 (2008).","DOI":"10.1007\/978-0-387-09624-7"},{"issue":"11","key":"10.3233\/JIFS-230073_ref56","first-page":"1082","article-title":"Method Accelerating Entropy-based Artificial Immune Algorithm[J]","volume":"12","author":"Zheng","year":"2004","journal-title":"Computer Automated Measurement and Control"},{"key":"10.3233\/JIFS-230073_ref57","first-page":"55","article-title":"A modified artificial immune algorithm[J]","volume":"33","author":"Zheng","year":"2003","journal-title":"Computer Applications in Engineering Education"},{"issue":"3","key":"10.3233\/JIFS-230073_ref58","first-page":"6","article-title":"Improved immune algorithm based on hamming distance and its application in SAT [J]","volume":"6","author":"Chaodong Fan","year":"2011","journal-title":"Journal of Systems Engineering"},{"issue":"004","key":"10.3233\/JIFS-230073_ref60","first-page":"616","article-title":"The orthogonal immune clonal particle swarm optimization algorithm is used to solve the SAT problem [J]","volume":"34","author":"Lin Cong","year":"2007","journal-title":"Journal of Xi\u2019an University of Electronic Science and Technology (Natural Science Edition)"},{"issue":"1","key":"10.3233\/JIFS-230073_ref61","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/4235.752920","article-title":"An orthogonal genetic algorithm for multimedia multicast routing[J]","volume":"3","author":"Zhang","year":"1999","journal-title":"Evolutionary Computation IEEE Transactions on"},{"issue":"2","key":"10.3233\/JIFS-230073_ref62","first-page":"8","article-title":"Quantum immune cloning algorithm for solving SAT problem [J]","volume":"30","author":"Li","year":"2007","journal-title":"Journal of Computer Science"},{"issue":"6","key":"10.3233\/JIFS-230073_ref64","first-page":"5","article-title":"Quantum Cooperative Immune Algorithm for SAT Problem [J]","author":"Wu","year":"2009","journal-title":"Systems Engineering and Electronic Technology"},{"issue":"1","key":"10.3233\/JIFS-230073_ref67","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.asoc.2011.08.038","article-title":"DisABC: A new artificial bee colony algorithm for binary optimization","volume":"12","author":"Kashan","year":"2012","journal-title":"Applied Soft Computing"},{"issue":"1","key":"10.3233\/JIFS-230073_ref70","first-page":"5","article-title":"An artificial bee colony algorithm for SAT problem [J]","volume":"35","author":"Guo","year":"2014","journal-title":"Journal of Northeast University: Natural Science Edition"},{"issue":"2","key":"10.3233\/JIFS-230073_ref72","first-page":"3","article-title":"A heuristic initial solution strategy for ABCSAT algorithm [J]","volume":"17","author":"Jinlian Zhou","year":"2018","journal-title":"Software Guide"},{"issue":"4","key":"10.3233\/JIFS-230073_ref75","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/s12293-020-00310-9","article-title":"Feature selection based bee swarm meta-heuristic approach for combinatorial optimisation problems: a case-study on MaxSAT[J]","volume":"12","author":"Sadeg","year":"2020","journal-title":"Memetic Computing"},{"issue":"02","key":"10.3233\/JIFS-230073_ref78","doi-asserted-by":"publisher","first-page":"82","DOI":"10.13245\/j.hust.220214","article-title":"Overview of algorithms for maximum satisfiability problems [J]","volume":"50","author":"He Kun","year":"2022","journal-title":"Journal of Huazhong University of Science and Technology (Natural Science Edition)"},{"issue":"08","key":"10.3233\/JIFS-230073_ref79","doi-asserted-by":"publisher","first-page":"2290","DOI":"10.19734\/j.issn.1001-3695.2022.01.0023","article-title":"An improved warning propagation algorithm for solving the Max-SAT problem[J]","volume":"39","author":"Wu","year":"2022","journal-title":"Computer Application Research"}],"updated-by":[{"DOI":"10.1177\/10641246251331509","type":"retraction","label":"Retraction","source":"retraction-watch","updated":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000},"record-id":"64024"},{"DOI":"10.1177\/10641246251331509","type":"retraction","label":"Retraction","source":"publisher","updated":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000}}],"container-title":["Journal of Intelligent &amp; Fuzzy Systems"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/JIFS-230073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T09:22:58Z","timestamp":1769678578000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/JIFS-230073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,2]]},"references-count":37,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.3233\/jifs-230073","relation":{},"ISSN":["1064-1246","1875-8967"],"issn-type":[{"value":"1064-1246","type":"print"},{"value":"1875-8967","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,2]]}}}