SONG SONG HÓA THUẬT TOÁN LAI GHÉP DAVIS' ORDER CROSSOVER TRÊN FPGA SỬ DỤNG TRUE DUAL PORT RAM - MỘT CÁCH TIẾP CẬN TRONG GIẢI QUYẾT BÀI TOÁN NGƯỜI DU LỊCH BẰNG GIẢI THUẬT DI TRUYỀN

Tóm tắt

Bài toán Người du lịch (TSP - Travelling Salesman Problem) được xem là một trong những bài toán kinh điển của tối ưu hóa, đã và đang được ứng dụng rộng rãi trong nhiều lĩnh vực như lập kế hoạch, thiết kế vi mạch, phân tích gen,.. TSP với lời giải tổng quát thuộc lớp bài toán có độ phức tạp không phái đa thức (NP - đầy đủ), vì vậy việc tìm kiếm lời giải tối ưu cho bài toán là không khả thi. Đã có nhiều nghiên cứu nhằm nâng cao hiệu năng cho TSP trong phạm vi vài chục ngàn thành phố như sử dụng giải thuật tìm kiếm Tabu, mạng Nơron nhân tạo, giải thuật Di truyền (GA - Genetic Algorithm),.. Trong bài báo này, nhóm tác giả đề xuất giải pháp tăng cường mức độ song song hóa giải thuật GA nhằm cải thiện hiệu năng của giải thuật này khi giải quyết bài toán TSP bằng cách song song hóa thuật toán OX1 (Davis' Order Crossover) trên nền tảng FPGA (Field-Programmable Gate Array) với True Dual - Port RAM (T2P-RAM).