Negative Learning Ant Colony Optimization for MaxSAT
Abstract Recently, a new negative learning variant of ant colony optimization (ACO) has been used to successfully tackle a range of combinatorial optimization problems. For providing stronger evidence of the general applicability of negative learning ACO, we investigate how it can be adapted to solv...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2022-08-01
|
| Series: | International Journal of Computational Intelligence Systems |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s44196-022-00120-6 |
| _version_ | 1798004293517705216 |
|---|---|
| author | Teddy Nurcahyadi Christian Blum Felip Manyà |
| author_facet | Teddy Nurcahyadi Christian Blum Felip Manyà |
| author_sort | Teddy Nurcahyadi |
| collection | DOAJ |
| description | Abstract Recently, a new negative learning variant of ant colony optimization (ACO) has been used to successfully tackle a range of combinatorial optimization problems. For providing stronger evidence of the general applicability of negative learning ACO, we investigate how it can be adapted to solve the Maximum Satisfiability problem (MaxSAT). The structure of MaxSAT is different from the problems considered to date and there exists only a few ACO approaches for MaxSAT. In this paper, we describe three negative learning ACO variants. They differ in the way in which sub-instances are solved at each algorithm iteration to provide negative feedback to the main ACO algorithm. In addition to using IBM ILOG CPLEX, two of these variants use existing MaxSAT solvers for this purpose. The experimental results show that the proposed negative learning ACO variants significantly outperform the baseline ACO as well as IBM ILOG CPLEX and the two MaxSAT solvers. This result is of special interest because it shows that negative learning ACO can be used to improve over the results of existing solvers by internally using them to solve smaller sub-instances. |
| first_indexed | 2024-04-11T12:21:16Z |
| format | Article |
| id | doaj.art-3d1b3734ce63479abc7c11022d92225c |
| institution | Directory Open Access Journal |
| issn | 1875-6883 |
| language | English |
| last_indexed | 2024-04-11T12:21:16Z |
| publishDate | 2022-08-01 |
| publisher | Springer |
| record_format | Article |
| series | International Journal of Computational Intelligence Systems |
| spelling | doaj.art-3d1b3734ce63479abc7c11022d92225c2022-12-22T04:24:05ZengSpringerInternational Journal of Computational Intelligence Systems1875-68832022-08-0115111910.1007/s44196-022-00120-6Negative Learning Ant Colony Optimization for MaxSATTeddy Nurcahyadi0Christian Blum1Felip Manyà2Artificial Intelligence Research Institute (IIIA-CSIC)Artificial Intelligence Research Institute (IIIA-CSIC)Artificial Intelligence Research Institute (IIIA-CSIC)Abstract Recently, a new negative learning variant of ant colony optimization (ACO) has been used to successfully tackle a range of combinatorial optimization problems. For providing stronger evidence of the general applicability of negative learning ACO, we investigate how it can be adapted to solve the Maximum Satisfiability problem (MaxSAT). The structure of MaxSAT is different from the problems considered to date and there exists only a few ACO approaches for MaxSAT. In this paper, we describe three negative learning ACO variants. They differ in the way in which sub-instances are solved at each algorithm iteration to provide negative feedback to the main ACO algorithm. In addition to using IBM ILOG CPLEX, two of these variants use existing MaxSAT solvers for this purpose. The experimental results show that the proposed negative learning ACO variants significantly outperform the baseline ACO as well as IBM ILOG CPLEX and the two MaxSAT solvers. This result is of special interest because it shows that negative learning ACO can be used to improve over the results of existing solvers by internally using them to solve smaller sub-instances.https://doi.org/10.1007/s44196-022-00120-6Combinatorial optimizationAnt colony optimizationNegative learningMaximum satisfiability problem |
| spellingShingle | Teddy Nurcahyadi Christian Blum Felip Manyà Negative Learning Ant Colony Optimization for MaxSAT International Journal of Computational Intelligence Systems Combinatorial optimization Ant colony optimization Negative learning Maximum satisfiability problem |
| title | Negative Learning Ant Colony Optimization for MaxSAT |
| title_full | Negative Learning Ant Colony Optimization for MaxSAT |
| title_fullStr | Negative Learning Ant Colony Optimization for MaxSAT |
| title_full_unstemmed | Negative Learning Ant Colony Optimization for MaxSAT |
| title_short | Negative Learning Ant Colony Optimization for MaxSAT |
| title_sort | negative learning ant colony optimization for maxsat |
| topic | Combinatorial optimization Ant colony optimization Negative learning Maximum satisfiability problem |
| url | https://doi.org/10.1007/s44196-022-00120-6 |
| work_keys_str_mv | AT teddynurcahyadi negativelearningantcolonyoptimizationformaxsat AT christianblum negativelearningantcolonyoptimizationformaxsat AT felipmanya negativelearningantcolonyoptimizationformaxsat |