Phương pháp tối ưu đàn kiến và ứng dụng

Giới thiệu một phát biểu bài toán tối ưu tổ hợp dạng tổng quát. Tìm hiểu phương pháp tối ưu đàn kiế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. Trình bày thuật toán ACOHAP giải bài toán suy diễn haplotype. Trình bày thuật toán AcoSeeD giải bài toán tìm tập hạt giống tối ưu ứng dụng trong tìm kiếm tương đồng của các chuỗi sinh học. Giới thiệu thuật toán GASVM và ACOSVM để cải tiến dự báo hoạt động điều tiết gen.

Nội dung bài viết

Tính cấp thiết của luận án

Trong thực tế và khi xây dựng các hệ thông tin, ta thường gặp các bài toán tối ưu tổ hợp (TƯTH). Trong đó phải tìm các giá trị cho các biến rời rạc để làm cực trị hàm mục tiêu nào đó. Đa số các bài toán này thuộc lớp NP-khó. Trừ các bài toán cỡ nhỏ có thể tìm lời giải bằng cách tìm kiếm vét cạn, còn lại thì thường không thể tìm được lời giải tối ưu.

Đối với các bài toán cỡ lớn không có phương pháp giải đúng, đến nay người ta vẫn dùng các cách tiếp cận sau:

1) Tìm kiếm heuristic để tìm lời giải đủ tốt;
2) Tìm kiếm cục bộ để tìm lời giải tối ưu địa phương;
3) Tìm lời giải gần đúng nhờ các thuật toán mô phỏng tự nhiên như: mô phỏng luyện kim, giải thuật di truyền, tối ưu bầy đàn,…
Hai cách tiếp cận đầu thường cho lời giải nhanh nhưng không thể cải thiện thêm lời giải tìm được, nên cách tiếp cận thứ ba đang được sử dụng rộng rãi cho các bài toán cỡ lớn.

Trong các phương pháp mô phỏng tự nhiên, tối ưu đàn kiến (Ant Colony Optimization – ACO) là cách tiếp cận metaheuristic tương đối mới, được giới thiệu bởi Dorigo năm 1991 đang được nghiên cứu và ứng dụng rộng rãi cho các bài toán TƯTH khó.

Các thuật toán ACO sử dụng kết hợp thông tin kinh nghiệm (heuristic) và học tăng cường qua các vết mùi của các con kiến nhân tạo để giải các bài toán TƯTH bằng cách đưa về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc tương ứng của bài toán. Phương pháp này được áp dụng rộng rãi để giải nhiều bài toán khó và hiệu quả nổi trội của chúng so với các phương pháp mô phỏng tự nhiên khác đã được chứng tỏ bằng thực nghiệm.

Khi áp dụng các thuật toán tối ưu đàn kiến thông dụng như ACS và MMAS, người ta phải tìm một lời giải đủ tốt, trên cơ s đó xác định các tham số cho cận trên và cận dưới của vết mùi. Điều này gây nhiều khó khăn khi áp dụng thuật toán cho các bài toán mới. Ngoài ra, lượng mùi cập nhật cho mỗi thành phần trong đồ thị tỷ lệ với giá trị hàm mục tiêu của lời giải chứa nó liệu có phản ánh đúng thông tin học t ng cường hay không cũng còn phải thảo luận.

Việc nghiên cứu sâu hơn về các thuật toán ACO và ứng dụng của nó đang được nhiều người quan tâm. Từ năm 1998 đến nay, cứ 2 năm thì có một hội nghị quốc tế về phương pháp này tổ chức Brussels.

Mục tiêu của luận án

1) Phân tích xu thế biến thiên của vết mùi trong các thuật toán ACO, trên cơ sở đó đề xuất các quy tắc cập nhật mùi dễ sử dụng và hiệu quả hơn.

2) Đề xuất các thuật toán giải một số bài toán thời sự.

Các đóng góp của luận án

Dựa trên các phân tích toán học, luận án đề xuất các quy tắc cập nhật mùi: Đa mức (MLAS), Max Min trơn (SMMAS). Ưu điểm nổi trội của thuật toán được kiểm định bằng thực nghiệm đối với các bài toán chuẩn như: lập lịch sản xuất (Job Shop Scheduling – JSS), người chào hàng (Traveling Salesman Problem – TSP), quy hoạch toàn phương nhị phân không ràng buộc (Unconstrained Binary Quadratic Programming – UBQP). Trường hợp các thông tin heuristic có ảnh hưởng nhiều tới kết quả tìm kiếm, luận án đề xuất quy tắc 3 mức (3-LAS) và kiểm định hiệu quả của nó qua bài toán người chào hàng. Thực nghiệm cho thấy hiệu quả của các quy tắc này như nhau nhưng quy tắc SMMAS đơn giản và dễ sử dụng hơn, thích hợp cho ứng dụng rộng rãi.

Nhờ quy tắc cập nhật mùi SMMAS, luận án đề xuất các thuật toán mới ứng dụng cho bài toán suy diễn haplotyp , bài toán tìm tập hạt giống tối ưu. Ngoài ra, luận án cũng đưa ra lược đồ ứng dụng ACO, thuật toán di truyền xác định tham số khi dùng phương pháp SVM (Support Vector Machine – SVM) cho bài toán dự báo hoạt động điều hòa gen. Ưu điểm nổi trội của các đề xuất mới được kiểm nghiệm bằng thực nghiệm trên dữ liệu tin cậy.

Bố cục của luận án

Ngoài phần kết luận, luận án được tổ chức như sau.
Chương 1: Luận án giới thiệu một phát biểu bài toán tối ưu tổ hợp dạng tổng quát để tiện dụng về sau.
Chương 2: Những nét chính của phương pháp tối ưu đàn kiến được giới thiệu trong chương 2.
Chương 3: Dựa trên phân tích toán học về biến thiên vết mùi, luận án đề xuất các thuật toán mới MLAS, SMMAS và 3-LAS, hiệu quả của thuật toán được kiểm nghiệm trên hai bài toán cổ điển TSP và UBQP.
Chương 4: Trình bày thuật toán ACOHAP giải bài toán suy diễn haplotype.
Chương 5: Trình bày thuật toán AcoS giải bài toán tìm tập hạt giống tối ưu ứng dụng trong tìm kiếm tương đồng của các chuỗi sinh học.
Chương 6: Giới thiệu thuật toán GASVM và ACOSVM để cải tiến dự báo hoạt động điều tiết gen.

Link tải tài liệu: https://tii.la/rS1m8

Lưu ý: Link tải có chứa quảng cáo được rút gọn bằng Shrinkearn.com

Mật khẩu mở tệp PDF: sharetailieu.net

Nghiên cứu chế tạo và khảo sát tính chất vật liệu Polyme Nanocompozit trên cơ sở Polyaniline và Graphit

Nghiên cứu công nghệ chế tạo và tính chất của giả vật liệu Metamaterial

Nghiên cứu chế tạo vật liệu sắt điện BaTiO3 và tổ hợp BaTiO3/Fe3O4 có cấu trúc micro-nano bằng phương pháp thủy phân nhiệt

Tiếp cận các ứng dụng giao thức truyền thông không dây MiWi PRO

Nghiên cứu chế tạo và khảo sát tính chất vật liệu Polyme Nanocompozit trên cơ sở Polyaniline và Graphit

Nghiên cứu công nghệ chế tạo và tính chất của giả vật liệu Metamaterial

Nghiên cứu chế tạo vật liệu sắt điện BaTiO3 và tổ hợp BaTiO3/Fe3O4 có cấu trúc micro-nano bằng phương pháp thủy phân nhiệt

Tiếp cận các ứng dụng giao thức truyền thông không dây MiWi PRO

Tính cấp thiết của luận án

Mục tiêu của luận án

Các đóng góp của luận án

Bố cục của luận án

LEAVE A REPLY Cancel reply

Mới Nhất

Nghiên cứu chế tạo và khảo sát tính chất vật liệu Polyme Nanocompozit trên cơ sở Polyaniline và Graphit

Nghiên cứu công nghệ chế tạo và tính chất của giả vật liệu Metamaterial

Nghiên cứu chế tạo vật liệu sắt điện BaTiO3 và tổ hợp BaTiO3/Fe3O4 có cấu trúc micro-nano bằng phương pháp thủy phân nhiệt

Tiếp cận các ứng dụng giao thức truyền thông không dây MiWi PRO

Nâng cao độ chính xác định vị robot bằng phương pháp tổng hợp dữ liệu cảm biến lập mã quang với bộ lọc Kalman...

Cùng Chuyên Mục

Đọc Nhiều Nhất

Áp dụng OSGi trong việc xây dựng hệ thống dựa thành...

Kiến trúc hướng dịch vụ và ứng dụng điện toán đám...

Nghiên cứu tính khả kiểm thử của ứng dụng trên nền...

Kiểm thử đơn vị cho hệ thống

Phát triền phần mềm cho người học tại Đại học Quốc...

Các kỹ thuật phân cụm trong khai phá dữ liệu sử...