A Genetic Algorithm for Satisfiability Problem in a Probabilistic Logic: A First Report

1. T. Bäck, A. E. Eiben, and M. E. Vink. A superior evolutionary algorithm for 3-SAT. In Proc. of the 7th Annual Conference on Evolutionary Programming, LNCS 1744, 125–136, 1998.

   Google Scholar 

2. D. Beasley, D. R. Bull, and R. R. Martin. An Overview of Genetic Algorithms, Part 1: Fundamentals. University Computing, Vol. 15, No. 2, pp. 58–69, 1993.

   Google Scholar 

3. A. Cano and S. Moral. A genetic algorithm to approximate convex sets of probabilities. In Proc. of the IPMU-96, Vol. 2, 859–864, 1996.

   Google Scholar 

4. P. Cheeseman, B. Kanefsky, and W. M. Taylor. Where the really hard problems are. In Proc. of the IJCAI-91. 331–337, 1991.

   Google Scholar 

5. K. A. De Jong and W. M. Spears. Using genetic algorithms to solve NP-complete problems. In 3th International Conference on Genetic Algorithms, 124–132. 1989.

   Google Scholar 

6. R. Fagin, J. Halpern, and N. Megiddo. A logic for reasoning about probabilities. Information and Computation, 87:78–128, 1990.

   Article  MathSciNet  MATH  Google Scholar 

7. R. Fagin and J. Halpern. Reasoning about knowledge and probability. JACM, 41(2):340–367, 1994.

   Article  MATH  MathSciNet  Google Scholar 

8. A. Frish and P. Haddawy. Anytime deduction for probabilistic logic. Artificial Intelligence, 69:93–122, 1994.

   Article  MathSciNet  Google Scholar 

9. G. Georgakopoulos, D. Kavvadias, and C. Papadimitriou. Probabilistic satisfiability. Journal of Complexity, 4(1):1–11, 1988.

   Article  MATH  MathSciNet  Google Scholar 

10. D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Weseley Publ. Reading, Mass., 412p, 1989.

    MATH  Google Scholar 

11. J. Y. Halpern. A logical approach to reasoning about uncertainty: A tutorial. In X. Arrazola, K. Korta, and F. J. Pelletier, editors, Discourse, Interaction, and Communication. Kluwer, 1997.

    Google Scholar 

12. P. Hansen, B. Jaumard, G.-B. D. Nguetse, and M. P. de Aragao. Models and algorithms for probabilistic and Bayesian logic. In Proceedings IJCAI-95, 1862–1868, 1995.

    Google Scholar 

13. J. H. Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor 1975.

    Google Scholar 

14. B. Jaumard, P. Hansen, and M. P. de Aragao. Column generation methods for probabilistic logic. ORSA Journal on Computing, 3:135–147, 1991.

    MATH  Google Scholar 

15. J. Kratica. Improving Performances of the Genetic Algorithm by Caching. Computers and Artificial Intelligence, Vol. 18, No. 3, pp. 271–283, 1999.

    MATH  Google Scholar 

16. J. Kratica. Parallelization of Genetic Algorithms for Solving Some NP-Complete Problems. Ph.D. thesis, University of Belgrade, Faculty of Mathematics, 2000. (in Serbian)

    Google Scholar 

17. E. Marchiori, and C. Rossi. A flipping genetic algorithm for hard 3-SAT problems. In Proc. of the Genetic and Evolutionary Computation Conference, 1999.

    Google Scholar 

18. E. Marchiori, and A. Steenbeek. A genetic local search algorithm for random binary constraint satisfaction problems. In Proc. of the SAC2000.

    Google Scholar 

19. N. Nilsson. Probabilistic logic. Artificial Intelligence, 28:71–87, 1986.

    Article  MATH  MathSciNet  Google Scholar 

20. Z. Ognjanović and M. Rasković. Some probability logics with new types of probability operators. Journal of Logic and Computation, 9(2):181–195, 1999.

    Article  MathSciNet  MATH  Google Scholar 

21. Z. Ognjanović and M. Rasković. Some first-order probability logics. Theoretical Computer Science, 247(1–2):191–212, 2000.

    Article  MathSciNet  MATH  Google Scholar 

22. M. Rasković. Classical logic with some probability operators. Publications de l’Institut Mathématique, Nouvelle Série, Beograd, 53(67):1–3, 1993.

    Google Scholar 

Download references