Tiếp cận một số thuật toán lớp Metaheuristic giải bài toán cây khung đa mục tiêu

257

TIẾP CẬN MỘT SỐ THUẬT TOÁN LỚP METAHEURISTIC GIẢI BÀI

TOÁN CÂY KHUNG ĐA MỤC TIÊU

(Approaching some metaheuristic algorithms for Multi-objective Spanning Tree)

Trần Văn Vinh (*)

Abstract:

Most metaheuristic algorithms are nature-inspired as they have been developed based

on some abstraction of nature such as Simulated Annealing (SA), Tabu Search (TS), Genetic

Algorithm (GA), Memetic Algorithm (MA), … They are widely recognized as one of the most

practical approaches for combinatorial optimization problems. In this paper, we have

approached them for multiobjective Spanning tree problems such as Minimum Routing Cost

Spanning Tree – MRCT, Minimizing The Maximum Edge Load Spanning Tree –MMEDT,

Maximum-Leaf Spanning Tree – MLST. Finally, we also mention some advanced techniques

to enhance the efficiency of metaheuristics.

Keywords: Metaheuristic Algorithms, Simulated Annealing (SA), Tabu Search (TS),

Genetic Algorithm (GA), Memetic Algorithm (MA), Minimum Routing Cost Spanning Tree –

MRCT, Minimizing The Maximum Edge Load Spanning Tree –MMEDT, Maximum-Leaf

Spanning Tree – MLST.

Tóm tắt :

Hầu hết các thuật toán lớp metaheuristic lấy cảm hứng từ tự nhiên như thuật toán luyện

thép, Tabu Search, thuật giải di truyền, thuật toán Memetic. Chúng được xem là một trong

những hướng tiếp cận hiệu quả giải các bài toán tối ưu tổ hợp. Trong bài báo này, chúng tôi

tiếp cận chúng cho bài toán tối ưu trên cây khung đa mục tiêu như MRCT, MMEDT, MLST.

Cuối cùng chúng tôi cũng đề cập đến những kỹ thuật nhằm nâng cao hiệu quả của thuật toán

metaheuristic.

1. ĐẶT VẤN ĐỀ :

Các bài toán tối ưu tổ hợp là loại bài toán tối ưu phổ biến nhất, nó thường liên quan đến

lý thuyết đồ thị như bài toán người bán hàng, bài toán lập lịch, bài toán cái túi xách, đây là

những bài toán thuộc dạng NP-khó kinh điển, chúng thường được phát biểu dễ hiểu, dễ nhớ

nhưng để tìm được lời giải đúng là điều bí ẩn và thách thức lớn đối với giới khoa học thuật

toán. Một trong những lãnh vực được khai thác nhiều nhất trong lý thuyết đồ thị là các bài

toán tối ưu trên cây khung. Cây khung là một cấu trúc quan trọng vì nó là một đồ thị con phản

ánh được nhiều thông tin về đồ thị ban đầu, nó có nhiều ứng dụng thực tế như trong lãnh vực

thiết kế mạng, giao thông, viễn thông, sinh-tin học, …Ngoài bài toán tìm cây khung nhỏ nhất

đã được giải quyết trọn vẹn với các thuật toán cho lời giải chính xác như Kruskal hay Prim,

rất nhiều bài toán NP-khó về tối ưu trên cây khung đã được tìm thấy hiện nay như Minimum

Routing Cost Spanning Tree – MRCT (Shortest total path length spanning tree), Minimizing

The Maximum Edge Load Spanning Tree –MMEDT, Maximum Leaf Spanning Tree –MLST,

Capacitated Minimum Spanning Tree (cMST), Degree Constrained Spanning Tree, Bounded

Diameter Spanning Tree, …