1st International ICST Conference on Bio Inspired Models of Network, Information and Computing Systems

Research Article

An ant algorithm for static and dynamic MAX-SAT problems

Cite
BibTeX Plain Text
  • @INPROCEEDINGS{10.1145/1315843.1315856,
    author={Pedro C. Pinto and Thomas A.  Runkler and Joao M. C.   Sousa},
    title={An ant algorithm for static and dynamic MAX-SAT problems},
    proceedings={1st International ICST Conference on Bio Inspired Models of Network, Information and Computing Systems},
    publisher={ACM},
    proceedings_a={BIONETICS},
    year={2006},
    month={12},
    keywords={},
    doi={10.1145/1315843.1315856}
}
  • Pedro C. Pinto
    Thomas A. Runkler
    Joao M. C. Sousa
    Year: 2006
    An ant algorithm for static and dynamic MAX-SAT problems
    BIONETICS
    ACM
    DOI: 10.1145/1315843.1315856
Pedro C. Pinto1,2,3, Thomas A. Runkler1,4, Joao M. C. Sousa3
  • 1: Siemens AG, Corporate Technology Information and Communications, CT IC 4
  • 2: Otto-Hahn-Ring 6, 81730 Munich - Germany.
  • 3: Technical University of Lisbon, Instituto Superior Tecnico Department of Mechanical Engineering, GCAR - IDMEC, Avenida Rovisco Pais, 1049-001 Lisbon - Portugal
  • 4: Otto-Hahn-Ring 6, 81730 Munich - Germany

Abstract

This paper proposes a modified ant colony optimization algorithm, which is applied to the dynamic variant of the maximum satisfiability problem, or MAX-SAT. In the first part of the article we describe the developed algorithm and validate it using previous results of ant optimization applied to normal MAX-SAT problems. In the second part of the article we describe the changes implemented to optimize the dynamic problem and analyze the parameters of the new algorithm. The adapted ant colony optimization accomplishes very well the task of dealing with systematic changes of dynamic MAX-SAT instances derived from static problems.

Published
2006-12-13
Publisher
ACM
http://dx.doi.org/10.1145/1315843.1315856
Copyright © 2006–2024 ACM