SONG SONG HÓA THUẬT TOÁN LAI GHÉP DAVIS' ORDER CROSSOVER TRÊN FPGA SỬ DỤNG TRUE DUAL PORT RAM - MỘT CÁCH TIẾP CẬN TRONG GIẢI QUYẾT BÀI TOÁN NGƯỜI DU LỊCH BẰNG GIẢI THUẬT DI TRUYỀN

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: TRỌNG ĐỨC NGUYỄN, TRUNG QUÂN NGUYỄN

Ngôn ngữ: vie

Ký hiệu phân loại:

Thông tin xuất bản: Tạp chí Khoa học Công nghệ Hàng hải, 2022

Mô tả vật lý: tr.72-76

Bộ sưu tập: Metadata

ID: 330967

Thêm vào giỏ Liên kết toàn văn

Bài toán Người du lịch (TSP - Travelling Salesman Problem) được xem là một trong những bài toán kinh điển của tối ưu hóa, đã và đang được ứng dụng rộng rãi trong nhiều lĩnh vực như lập kế hoạch, thiết kế vi mạch, phân tích gen,.. TSP với lời giải tổng quát thuộc lớp bài toán có độ phức tạp không phái đa thức (NP - đầy đủ), vì vậy việc tìm kiếm lời giải tối ưu cho bài toán là không khả thi. Đã có nhiều nghiên cứu nhằm nâng cao hiệu năng cho TSP trong phạm vi vài chục ngàn thành phố như sử dụng giải thuật tìm kiếm Tabu, mạng Nơron nhân tạo, giải thuật Di truyền (GA - Genetic Algorithm),.. Trong bài báo này, nhóm tác giả đề xuất giải pháp tăng cường mức độ song song hóa giải thuật GA nhằm cải thiện hiệu năng của giải thuật này khi giải quyết bài toán TSP bằng cách song song hóa thuật toán OX1 (Davis' Order Crossover) trên nền tảng FPGA (Field-Programmable Gate Array) với True Dual - Port RAM (T2P-RAM).Travelling Salesman Problem (TSP) is an optimization problem. It has several applications, such as scheduling, VLSI, logistics, supply chain optimization. TSP is a NP-Hard problem, so it is impossible to find an optimal solution in polynomial time. There is much research that improves TSP performance for thousands of cities, such as Tabu algorithm, neural network, genetic algorithm (GA). In this paper, we suggest a proposed solution to improve parallelization of GA in order to reduce processing time when applied to solve TSP by parallel OX11 step using True Dual Port RAM of the Field-Programmable Gate Array (FPGA).

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR