Tối ưu tổ hợp

Trong luận án này, dựa trên các phân tích toán học, chúng tôi đề xuất quy tắc Max-Min trơn (Smoothed Max-Min Ant System – SMMAS) như là cải tiến của thuật toán Max-Min. Ưu điểm nổi trội của chúng được kiểm định bằng thực nghiệm qua đối với các bài toán chuẩn như: lập lịch sản xuất (Job Shop Scheduling – JSS), người chào hàng (Traveling Salesman Problem – TSP), quy hoạch toàn phương nhị phân không ràng buộc (Unconstrained Binary Quadratic Programming- UBQP). Trường hợp các thông tin heuristic có ảnh hưởng nhiều tới kết quả tìm kiếm, chúng tôi đề xuất quy tắc 3 mức (Three-Level Ant System – 3-LAS) và kiểm định hiệu quả của nó trong bài toán người chào hàng. Ngoài ra, để điều tiết linh hoạt tính khám phá và khai thác của phương pháp ACO, chúng tôi cũng gợi ý phát triển thuật toán đa mức (Multi-level Ant System – MLAS). Trong các quy tắc này, SMMAS đơn giản, dễ sử dụng hơn.

0.00

Trong luận án này, dựa trên các phân tích toán học, chúng tôi đề xuất quy tắc Max-Min trơn (Smoothed Max-Min Ant System – SMMAS) như là cải tiến của thuật toán Max-Min. Ưu điểm nổi trội của chúng được kiểm định bằng thực nghiệm qua đối với các bài toán chuẩn như: lập lịch sản xuất (Job Shop Scheduling – JSS), người chào hàng (Traveling Salesman Problem – TSP), quy hoạch toàn phương nhị phân không ràng buộc (Unconstrained Binary Quadratic Programming- UBQP). Trường hợp các thông tin heuristic có ảnh hưởng nhiều tới kết quả tìm kiếm, chúng tôi đề xuất quy tắc 3 mức (Three-Level Ant System – 3-LAS) và kiểm định hiệu quả của nó trong bài toán người chào hàng. Ngoài ra, để điều tiết linh hoạt tính khám phá và khai thác của phương pháp ACO, chúng tôi cũng gợi ý phát triển thuật toán đa mức (Multi-level Ant System – MLAS). Trong các quy tắc này, SMMAS đơn giản, dễ sử dụng hơn.

Hiện nay, ứng dụng công nghệ thông tin để nghiên cứu sinh học phân tử đang được quan tâm. Nhờ quy tắc cập nhật mùi SMMAS, luận án đề xuất các thuật toán mới giải các bài toán thời sự trong sinh học: bài toán suy diễn haplotype, bài toán tìm tập hạt giống có cách tối ưu, tìm tham số trong phương pháp SVM (Support Vector Machine – SVM) dùng cho bài toán dự báo hoạt động điều tiết gen. Ưu điểm nổi trội của các đề xuất mới được kiểm nghiệm bằng thực nghiệm trên dữ liệu tin cậy.

Các kết quả của luận án đã được công bố trong 7 báo cáo hội nghị quốc tế [20- 26], một bài báo ở tạp chí “Tin học và điều khiển học”  và một hội thảo toàn quốc “Các chủ đề chọn lọc của công nghệ thông tin “.

Ngoài phần kết luận, luận án được tổ chức như sau. Chương 1 giới thiệu phát biểu bài toán tối ưu tổ hợp dạng tổng quát. Những nét chính của phương pháp tối ưu đàn kiến được giới thiệu trong chương 2. Chương 3, dựa trên phân tích toán học về

biến thiên vết mùi, luận án đề xuất các thuật toán mới: MLAS, SMMAS và 3-LAS. Hiệu quả của thuật toán được kiểm nghiệm trên hai bài toán cổ điển TSP và UBQP. Chương 4 trình bày thuật toán ACOHAP giải bài toán suy diễn haplotype và so sánh hiệu quả của nó với hai thuật toán thông dụng, được xem là tốt nhất hiện nay: RPoly và CollHap. Chương 5 trình bày thuật toán AcoSeeD giải bài toán tìm tập hạt giống có cách tối ưu và so sánh hiệu quả của nó với hai thuật toán SpEED và SpEEDfast, được xem là tốt nhất hiện nay. Chương 6 giới thiệu lược đồ ACOSVM và GASVM sử dụng phương pháp ACO và thuật toán di truyền để cải tiến dự báo hoạt động điều tiết gen. Hiệu quả của nó được so sánh với phương pháp lưới thông dụng đã được Zinzen đã đề xuất sử dụng trong.

Tải về miễn phí bản đầy đủ luận văn tại địa chỉ:

https://www.file-upload.com/zp9j01xrl7vv

Đánh giá

Chưa có đánh giá nào.

Hãy là người đầu tiên đánh giá “Tối ưu tổ hợp”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *