Ant Colony Optimization with Adaptive Fitness Function for Satisfiability Testing Export

@incollection{citeulike:4834513, abstract = {Ant Colony Optimization (ACO) is a metaheuristic inspired by the foraging behavior of ant colonies that has been successful in the resolution of hard combinatorial optimization problems. This work proposes MaxMin-SAT, an ACO alternative for the satisfiability problem (SAT). MaxMin-SAT is the first ACO algorithm for SAT that implements an Adaptive Fitness Function, which is a technique used for Genetic Algorithms to escape local optima. To show effectiveness of this technique, three different adaptive fitness functions are compared: Stepwise Adaptation of Weights, Refining Functions, and a mix of the previous two. To experimentally test MaxMin-SAT, a comparison with Walksat (a successful local search algorithm) is presented. Even though MaxMin-SAT cannot beat Walksat when dealing with phase transition instances, experimental results show that it can be competitive with the local search heuristic for overconstrained instances.}, author = {Villagra, Marcos and Bar\'{a}n, Benjam\'{i}n}, citeulike-article-id = {4834513}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-73445-1_26}, citeulike-linkout-1 = {http://www.springerlink.com/content/v34788378tr74386}, doi = {10.1007/978-3-540-73445-1_26}, journal = {Logic, Language, Information and Computation}, keywords = {convexity, global, multi-objective, optimization, problem, salesman, traveling}, pages = {352--361}, posted-at = {2009-06-13 09:22:37}, priority = {0}, title = {Ant Colony Optimization with Adaptive Fitness Function for Satisfiability Testing}, url = {http://dx.doi.org/10.1007/978-3-540-73445-1_26}, year = {2007} }

TY - CHAP ID - citeulike:4834513 L3 - citeulike-article-id:4834513 N2 - Ant Colony Optimization (ACO) is a metaheuristic inspired by the foraging behavior of ant colonies that has been successful in the resolution of hard combinatorial optimization problems. This work proposes MaxMin-SAT, an ACO alternative for the satisfiability problem (SAT). MaxMin-SAT is the first ACO algorithm for SAT that implements an Adaptive Fitness Function, which is a technique used for Genetic Algorithms to escape local optima. To show effectiveness of this technique, three different adaptive fitness functions are compared: Stepwise Adaptation of Weights, Refining Functions, and a mix of the previous two. To experimentally test MaxMin-SAT, a comparison with Walksat (a successful local search algorithm) is presented. Even though MaxMin-SAT cannot beat Walksat when dealing with phase transition instances, experimental results show that it can be competitive with the local search heuristic for overconstrained instances. JF - Logic, Language, Information and Computation EP - 361 TI - Ant Colony Optimization with Adaptive Fitness Function for Satisfiability Testing SP - 352 KW - convexity KW - global KW - multi-objective KW - optimization KW - problem KW - salesman KW - traveling AU - Villagra, Marcos AU - Barán, Benjamín PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-73445-1_26 ER -