TAILIEUCHUNG - Giải thuật di truyền giải bài toán cực tiểu hoá độ trễ

Bài báo trình bày thuật toán phát triển dựa trên sơ đồ của thuật toán di truyền (Genetic Algorithm – GA – thuật toán áp dụng hiệu quả cho lớp bài toán tối ưu tổ hợp) để giải bài toán MLP. Kết quả thực nghiệm cho thấy, thuật toán đề xuất đưa ra được lời giải với chất lượng tốt hơn so với các lời giải của các thuật toán gần đúng tốt nhất hiện biết. | TẠP CHÍ KHOA HỌC CÔNG NGHỆ CÁC TRƯỜNG ĐẠI HỌC KỸ THUẬT SỐ 71 - 2009 GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN CỰC tiểu HOÁ độ trễ GENETIC ALGORITHM FOR SOLVING THE MINIMUM LATENCY PROBLEM Ban Hà Bằng Nguyễn Đức Nghĩa Trường Đại học Bách Khoa Hà Nội TÓM TẮT Bài toán cực tiểu hoá độ trễ Minimum Latency Problem - MLP - hay còn gọi là bài toán thợ sửa chữa lưu động - là một trong những lớp bài toán tối ưu tổ hợp có nhiều ứng dụng trong thực tế. Trong trường hợp tổng quát MLP được chứng minh là bài toán NP-khó. Hiện nay đã có nhiều thuật toán giải gần đúng bài toán MLP được đề xuất song chất lượng lời giải thu được chưa cao. Bài báo trình bày thuật toán phát triển dựa trên sơ đồ của thuật toán di truyền Genetic Algorithm - GA -thuật toán áp dụng hiệu quả cho lớp bài toán tối ưu tổ hợp để giải bài toán MLP. Kết quả thực nghiệm cho thấy thuật toán đề xuất đưa ra được lời giải với chất lượng tốt hơn so với các lời giải của các thuật toán gần đúng tốt nhất hiện biết. ABSTRACT Minimum Latency Problem MLP - also known as traveling repairman problem - is a class of combinatiorial optimization problems that have many practical applications. In general case MLP is proved to be NP-hard. Recently there are several efficient approximation algorithms for solving MLP however the quality of the provided solution is not actually high. This paper presents a new algorithm based on the scheme of the genetic algorithm for solving MLP. The experimental result on the proposed algorithm shows that it gives a better solution than the best one of the approximation algorithms. I. ĐẶT VẤN ĐỀ Bài toán MLP được phát biểu dưới dạng đồ thị như sau Cho đồ thị đầy đủ có trọng số Kn với tập đỉnh V 1 2 . n và ma trận trọng số không âm đối xứng C cij i j 1 2 . n . Giả sử P u1 u2 . un là một đường đi trên Kn. Ta gọi độ trễ của đỉnh uk 1 k n trên đường đi P là tổng p uk 2 e u uM 1 trong đó c ui ui 1 là trọng số của cạnh ui ui 1 . Độ trễ của đường đi P được định nghĩa như là tổng độ trễ của tất cả các đỉnh trên .

• Sinh học
• Giải thuật di truyền
• Bài toán cực tiểu hoá độ trễ
• Bài toán MLP
• Giải thuật di truyền giải bài toán MLP
• Thuật toán di truyền
• Ứng dụng giải thuật di truyền
• Đặc điểm của GAs
• Tính chất của giải thuật di truyền
• Bước giải thuật di truyền
• Nguyên lý giải thuật di truyền
• Tiếp cận thuật giải di truyền
• Phân lớp dữ liệu
• Thuật giải di truyền
• Mô tả thuật giải di truyền
• Cơ chế thực hiện thuật giải di truyền
• Kết hợp giải thuật di truyền
• Tìm kiếm Tabu
• Tối ưu hóa đa mục tiêu
• Bài giảng Tìm kiếm heuristic leo đồi
• Thuật giải leo đồi
• Các thuật toán tìm kiếm cục bộ
• Lựa chọn của thuật giải di truyền
• Nội dung về thuật giải leo đồi
• Ứng dụng thuật giải di truyền
• Thiết lập danh mục đầu tư hiệu quả
• Đề tài Công nghệ thông tin
• Mã hóa bài toán di truyền
• Lược đồ cơ sở dữ liệu
• Bài toán người du lịch
• Công nghệ thông tin
• Ứng dụng thuật toán di truyền
• Khoa học máy tính
• báo cáo khoa học
• bài toán max sat
• giải thuật di truyền song song
• ứng dụng di truyền song song
• toán di truyền
• mô phỏng luyện thép
• toán tổ hợp
• Bài toán tối ưu trong kinh tế
• GA Genetic Algorithm
• Phương pháp giải thuật
• ứng dụng di truyền
• di truyền học
• mô phỏng sự tiến hóa
• công nghệ sinh học
• bài toán xếp ba lô
• bài toán thống kê
• luận văn
• kỹ thuật điện
• luận văn thạc sỹ
• khoa học máy tình
• luận văn thạc sĩ
• luận văn công nghệ thông tin
• bải toán P median
• phương pháp sinh cột
• mô hình toán học
• giải thuật di truyền cho bài toán p median
• Phương trình phi tuyến
• Kỹ thuật tính toán mềm
• Hệ phương trình phi tuyến
• phục hồi thông tin
• dựng ảnh chân dung
• thuật giải di truyền tương tác
• Bài tập lớn trí tuệ nhân tạo
• Tìm hiểu về giải thuật di truyền
• Đề tài tốt nghiệp công nghệ thông tin
• Báo cáo thực tập quản trị mạng
• Đồ án tốt nghiệp mạng máy tính
• thông tin trên văn bản
• tiểu luận
• quản trị mạng
• phương pháp nghiên cứu khoa học
• lập trình tin học
• Xếp thời khóa biểu
• Hệ tín chỉ trường đại học
• Ma trận tối ưu LQR
• Hệ con lắc ngược phi tuyến
• Tối ưu hóa
• Journal of Science and Technology
• Ứng dụng giải thuật di truyền mờ
• Giải thuật di truyền mờ
• Bài toán quản lí hàng đợi tích cực AQM
• Phương pháp quản lí hàng đợi
• Bài toán vận tải tuyến tính
• GAs Genetic Algorithms
• Bài toán vận tải
• Gen phụ thuộc nhau
• Điều hành hồ nước
• Lĩnh vực thủy văn
• Giải thuật di truyền mã hóa số thực
• Phân cụm loại trừ
• Tham số điều khiển
• Trích lọc dữ liệu
• Điều khiển tối ưu
• Đa mục tiêu
• Bài toán tối ưu đa mục tiêu
• Ứng dụng giải thuật di truyền
• Điều hành công tác bệnh viện
• Hỗ trợ lập lịch công tác tại Bệnh viện
• Thiết kế giải thuật di truyền
• Quy trình lập kế hoạch công tác