Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tìm Kiếm Địa Phương Bằng Thuật Toán Kiến Và Sự Thích Ứng Hiệu Quả Của Nó Đối Với Vấn Đề Tô Màu Đồ Thị
Tóm tắt
Trong bài báo này, chúng tôi đề xuất một loại thuật toán kiến mới được gọi là Tìm Kiếm Địa Phương Bằng Kiến. Trong hầu hết các thuật toán kiến, vai trò của mỗi con kiến là xây dựng một giải pháp theo cách xây dựng. Ngược lại, chúng tôi đề xuất coi mỗi con kiến như một tìm kiếm địa phương, trong đó ở mỗi bước và theo sự phù hợp với tất cả các thuật toán kiến, mỗi con kiến điều chỉnh giải pháp hiện tại bằng cách sử dụng lực tham lam và các hệ thống dấu vết. Chúng tôi cũng đề xuất các phương pháp để giảm bớt nỗ lực tính toán liên quan đến mỗi quyết định của con kiến. Phương pháp kiến mới này sau đó được áp dụng cho vấn đề tô màu k, một vấn đề NP-khó. Các thử nghiệm tính toán cho thấy thuật toán của chúng tôi cạnh tranh với những phương pháp tô màu tốt nhất.
Từ khóa
#tìm kiếm địa phương #thuật toán kiến #tô màu đồ thị #vấn đề NP-khóTài liệu tham khảo
Blöchliger I and Zufferey N (2008). A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput Opns Res 35: 960–975.
Blum C (2005). Ant colony optimization: Introduction and recent trends. Phys Life Rev 2: 353–373.
Brélaz D (1979). New methods to color the vertices of a graph. Commun Assoc Comput Mach 22: 251–256.
Chams D, Hertz A and de Werra D (1987). Some experiments with simulated annealing for coloring graphs. Eur J Opl Res 32: 260–266.
Costa D and Hertz A (1997). Ants can colour graphs. J Opl Res Soc 48: 295–305.
Dorigo M (1992). Optimization, learning and natural algorithms (in Italian). PhD thesis, Politecnico di Milano, Dipartimento di Elettronica, Italy.
Dorigo M and Gambardella LM (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE T Evolut Comput 1(1): 53–66.
Dorigo M and Stützle T (2003). The Ant Colony Optimization Metaheuristic: Algorithms, applications, and advances. In: Glover, F and Kochenberger, G (eds). Handbook of Metaheuristics. Spring: New York, pp 251–285.
Dorigo M, Maniezzo V and Colorni A (1991). Positive feedback as a search strategy. Technical report 91-016. Politecnico di Milano, Dipartimento di Elettronica, Italy.
Dorigo M, Birattari M and Stützle T (2006). Ant colony optimization—Artificial ants as a computational intelligence technique. IEEE Comput Int Mag 1(4): 28–39.
Fleurent C and Ferland JA (1996). Genetic and hybrid algorithms for graph coloring. Ann Opns Res 63: 437–461.
Galinier P and Hao JK (1999). Hybrid evolutionary algorithms for graph coloring. J Comb Optim 3: 379–397.
Galinier P and Hertz A (2006). A survey of local search methods for graph coloring. Comput Opns Res 33: 2547–2562.
Galinier P, Hertz A and Zufferey N (2008). An adaptive memory algorithm for the k-coloring problem. Discrete Appl Math 156: 267–279.
Gamst A and Rave W (1982). On frequency assignment in mobile automatic telephone systems. Proceedings of GLOBECOM'82, pp. 309–315.
Garey M and Johnson DS (1979). Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman: San Francisco.
Glass C (2002). Bag rationalisation for a food manufacturer. J Opl Res Soc 53: 544–551.
Glass CA and Prügel-Bennett A (2005). A polynomial searchable exponential neighbourhood for graph colouring. J Opl Res Soc 56: 324–330.
Glover F and Laguna M (1997). Tabu Search. Kluwer Academic Publishers: Boston, MA.
Herrmann F and Hertz A (2002). Finding the chromatic number by means of critical graphs. ACM J Exp Algorithmics 7(10): 1–9.
Hertz A and de Werra D (1987). Using tabu search techniques for graph coloring. Computing 39: 345–351.
Hertz A and Zufferey N (2006). A new ant colony algorithm for the graph coloring problem. In: Pelta DA and Krasnogor N (eds). Proceedings of the Workshop on Nature Inspired Cooperative Strategies for Optimization, NICSO 2006, 29–30 June. Granada, Spain, pp 51–60.
Hertz A, Plumettaz M and Zufferey N (2008). Variable space search for graph coloring. Discrete Appl Math 156: 2551–2560.
Johnson DS, Aragon CR, McGeoch LA and Schevon C (1991). Optimization by simulated annealing: An experimental evaluation: Part II, Graph coloring and number partitioning. Opns Res 39: 378–406.
Leighton FT (1979). A graph coloring algorithm for large scheduling problems. J Res Nat Bur Stand 84: 489–505.
Malaguti E, Monaci M and Toth P (2008). A metaheuristic approach for the vertex coloring problem. INFORMS J Comput 20: 302–316.
Mehrotra A and Trick MA (1996). A column generation approach for graph coloring. INFORMS J Comput 8: 344–354.
Morgenstern C (1996). Distributed coloration neighborhood search. DIMACS Ser Discrete Math Theor Comput Sci 26: 335–357.
Petford A and Welsh D (1989). A randomised 3-colouring algorithm. Discrete Math 74: 253–261.
Shawe-Taylor J and Zerovnik J (2002). Ants and graph coloring. In: Kůrková V, Steele, NC, Neruda R and Kárný M (eds). Proceedings of ICANNGA'01. Springer-Verlag: New York, pp 276–279.
Stecke K (1985). Design, planning, scheduling, and control problems of flexible manufacturing systems. Ann Opns Res 3: 3–12.
Stützle T and Hoos H (1997). Improving the ant system: A detailed report on the max–min ant system. Technical report. Department of Computer Sciences—Intellectics Group, Technical University of Darmstadt.
Zufferey N (2002). Heuristiques pour les Problèmes de la Coloration des Sommets d'un Graphe et d'Affectation de Fréquences avec Polarités. PhD thesis, École Polytechnique Fédérale de Lausanne (EPFL), Switzerland.
Zufferey N, Amstutz P and Giaccari P (2008). Graph colouring approaches for a satellite range scheduling problem. J Sched 11: 263–277.