A Monogenous MBO Approach to Satisfiability
DOI:
关键词: Constraint (information theory) 、 Computer science 、 Heuristics 、 Artificial bee colony algorithm 、 Mathematical optimization 、 Swarm intelligence 、 Ant colony optimization algorithms 、 Satisfiability 、 Variation (game tree) 、 Metaheuristic
摘要: The marriage in honey–bees optimization (MBO) algorithm was recently proposed and showed good results for combinatorial problems. Contrary to most of the swarm intelligence algorithms (such as Ant Colony Optimization), MBO uses self-organization mix different heuristics. This paper presents a variation where colony contains single queen with multiple workers. model is used solve special class propositional satisfiability problems (SAT) known 3-SAT, each constraint exactly three variables. objective this detail analyze its behavior on 3-SAT using parameters gleaned from biological concepts: queen’s spermatheca size, amount time devoted brood-care. outperformed well heuristics SAT.
researchgate.net 参考文章(9)
Hussein A. Abbass, A single queen single worker honey–bees approach to 3-SAT genetic and evolutionary computation conference. pp. 807- 814 ,(2001)
Stephen A. Cook, David G. Mitchell, Finding hard instances of the satisfiability problem: A survey. Satisfiability Problem: Theory and Applications. pp. 1- 17 ,(1996)
Bart Selman, David Mitchell, Hector Levesque, A new method for solving hard satisfiability problems national conference on artificial intelligence. pp. 440- 446 ,(1992)
H.A. Abbass, MBO: marriage in honey bees optimization-a Haplometrosis polygynous swarming approach congress on evolutionary computation. ,vol. 1, pp. 207- 214 ,(2001) , 10.1109/CEC.2001.934391
Kenneth Steiglitz, Christos H. Papadimitriou, Combinatorial Optimization: Algorithms and Complexity ,(1981)
R. E. Page, R. B. Kimsey, H. H. Laidlaw, Migration and dispersal of spermatozoa in spermathecae of queen honeybees (Apis mellifera L.) Cellular and Molecular Life Sciences. ,vol. 40, pp. 182- 184 ,(1984) , 10.1007/BF01963589
Eric Bonabeau, Guy Theraulaz, Marco Dorigo, Swarm Intelligence: From Natural to Artificial Systems ,(1999)
Edward D. Rothman, Zila L. Paulino, Warwick E. Kerr, Julian Adams, ESTIMATION OF THE NUMBER OF SEX ALLELES AND QUEEN MATINGS FROM DIPLOID MALE FREQUENCIES IN A POPULATION OF APIS MELLIFERA Genetics. ,vol. 86, pp. 583- 596 ,(1977) , 10.1093/GENETICS/86.3.583
Bart Selman, Henry A. Kautz, Brain Cohen, Noise strategies for improving local search national conference on artificial intelligence. pp. 337- 343 ,(1994)