Khi Muỗi Tấn Công: Các Thuật Toán Muỗi Đối Với Các Vấn Đề Thoả Mãn Ràng Buộc

Artificial Intelligence Review - Tập 24 Số 3 - Trang 455-476 - 2005
Tarrant, Finbarr1, Bridge, Derek1
1Department of Computer Science, University College Cork, Cork, Ireland

Tóm tắt

Chúng tôi mô tả một thuật toán muỗi để giải quyết các vấn đề ràng buộc (Solnon 2002, Tạp chí Giao dịch IEEE về Tính toán Tiến hóa 6(4): 347–357). Chúng tôi phát triển một số biến thể và thực hiện các thí nghiệm. Các kết quả ban đầu của chúng tôi cho thấy rằng cách tốt nhất để phân bổ pheromone và các heuristics tốt nhất cho các chuyển trạng thái có thể khác với thực tiễn hiện tại.

Từ khóa

#thuật toán muỗi #vấn đề thỏa mãn ràng buộc #pheromone #heuristics #thí nghiệm

Tài liệu tham khảo

Achlioptas D., Gomes C.P., Kautz H.A., Selman B. (2000). Generating Satisfiable Problem Instances. In Proceedings of AAAI, 256–261 citation_journal_title=Constraints; citation_title=Random Constraint Satisfaction: A More Accurate Picture; citation_author=D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc, M. Molloy, Y. Stamatiou; citation_volume=6; citation_issue=4; citation_publication_date=2001; citation_pages=329-344; citation_doi=10.1023/A:1011402324562; citation_id=CR2 Bullnheimer B., Hartl R., Strauss C. (1998). Applying the Ant System to the Vehicle Routing Problem. In: Osman I., Voss S., Martello S., Roucairol C (eds). Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization Kluwer 109–120 Clark, D. A., Frank, J., Gent, I. P., MacIntyre, E., Tomov, N. & Walsh, T. (1996). Local Search and the Number of Solutions. In E. C. Freuder (ed.) Principles and Practice of Constraint Programming (Proceedings of CP’96), 119–133. LNCS 1118. Springer citation_journal_title=Artificial Life; citation_title=Ant Algorithms for Discrete Optimization; citation_author=M. Dorigo, G.D. Caro, L.M. Gambardella; citation_volume=5; citation_issue=2; citation_publication_date=1999; citation_pages=137-172; citation_doi=10.1162/106454699568728; citation_id=CR5 citation_journal_title=IEEE Transactions on Systems, Man, and Cybernetics – Part B; citation_title=The Ant System: Optimization by a Colony of Cooperating Agents; citation_author=M. Dorigo, V. Maniezzo, A. Colorni; citation_volume=26; citation_issue=1; citation_publication_date=1996; citation_pages=1-13; citation_id=CR6 citation_journal_title=Random Constraint Satisfaction: Flaws and Structure. Journal of Constraints; citation_author=I.P. Gent, E. MacIntyre, P. Prosser, B.M. Smith, T. Walsh; citation_volume=6; citation_issue=4; citation_publication_date=2001; citation_pages=345-372; citation_id=CR7 Gent, I. P., MacIntyre, E., Prosser, P., & Walsh, T. (1996). The Constrainedness of Search. In Proceedings of 13th AAAI, 246–252. Mertens, K., Steegmans, E. & Holvoet, T. (2002). Cyclic Path-Based Environment: an Ant Environment for Solving Distributed Constraint Satisfaction Problems. In M. Yokoo (ed.) Proceedings of the 3rd International Workshop on Distributed Constraint Reasoning, 94–103 Roli, A., Blum, C. & Dorigo, M. (2001). ACO for Maximal Constraint Satisfaction Problems. In Proceedings of the 4th Metaheuristics International Conference, 187–191 citation_journal_title=In Proceedings of the 2000 Congress on Evolutionary Computation; citation_title=Ant Colonies are Good at Solving Constraint Satisfaction Problems; citation_author=L. Schoofs, B. Naudts; citation_volume=2; citation_publication_date=2000; citation_pages=1190-1195; citation_doi=10.1109/CEC.2000.870784; citation_id=CR11 citation_journal_title=Artificial Intelligence; citation_title=Locating the Phase Transitions in Binary Constraint Satisfaction Problems; citation_author=B.M. Smith, M.E. Dyer; citation_volume=18; citation_issue=1–2; citation_publication_date=1996; citation_pages=155-181; citation_doi=10.1016/0004-3702(95)00052-6; citation_id=CR12 citation_journal_title=IEEE Transactions on Evolutionary Computation; citation_title=Ants Can Solve Constraint Satisfaction Problems; citation_author=C. Solnon; citation_volume=6; citation_issue=4; citation_publication_date=2002; citation_pages=347-357; citation_doi=10.1109/TEVC.2002.802449; citation_id=CR13 Stützle, T. & Hoos, H. (1998). Improvements on the Ant System: Introducing the $$\user1{MAX}-\user1{MIN}$$ Ant System. In G. Smith, N. Steele & R. Albrecht (eds.) Proceedings of Artificial Neural Nets and Genetic Algorithms 1997, Springer, 245–249 Tsang E. (1993). Foundations of Constraint Satisfaction. Academic Press