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

Luận án tiến sĩ phương pháp tối ưu đàn kiến và ứng dụng tại ĐH Công nghệ - ĐHQG Hà Nội

Tối ưu đàn kiến: Thuật toán tìm kiếm hiệu quả cho bài toán phức tạp, ứng dụng trong lịch trình, định tuyến.

Trường ĐH

Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội

Chuyên ngành

Công nghệ thông tin

Tác giả

Luan An

Thể loại

Luận án

Số trang

134

Thời gian đọc

21 phút

Lượt xem

0

Lượt tải

0

Phí lưu trữ

40 Point

Tổng quan nhanh

Chủ đề:: Khám phá Phương pháp Tối ưu Đàn Kiến (ACO)
Số trang:: 134 trang
Trường:: Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội
Chuyên ngành:: Công nghệ thông tin
Tác giả:: Luan An

Tóm tắt nội dung luận án

I.Khám phá Phương pháp Tối ưu Đàn Kiến ACO

Phương pháp tối ưu đàn kiến (ACO) là một thuật toán metaheuristic mạnh mẽ. Thuật toán này lấy cảm hứng từ hành vi tìm kiếm thức ăn của kiến tự nhiên. ACO sử dụng trí tuệ bầy đàn để giải quyết các bài toán tối ưu tổ hợp phức tạp. Cơ chế của nó xoay quanh việc mô phỏng hành vi kiến thông qua chất pheromone. Phương pháp này đã chứng minh hiệu quả trong nhiều lĩnh vực khoa học máy tính và kỹ thuật. Tài liệu này cung cấp một cái nhìn sâu sắc về nền tảng và các ứng dụng tiên tiến của ACO.

1.1. Nguồn gốc Thuật toán ACO từ kiến tự nhiên

Phương pháp tối ưu đàn kiến (ACO) xuất phát từ việc quan sát hành vi tìm kiếm thức ăn của kiến. Kiến di chuyển ngẫu nhiên và để lại chất pheromone trên đường đi. Pheromone này hấp dẫn những con kiến khác. Con đường có nhiều pheromone nhất sẽ được chọn. Đây là một dạng trí tuệ bầy đàn, giúp đàn kiến tìm thấy con đường ngắn nhất giữa tổ và nguồn thức ăn. Mô phỏng hành vi kiến này tạo ra một hệ thống tự tổ chức để giải quyết vấn đề.

1.2. Định nghĩa và vai trò của ACO trong tối ưu

Thuật toán ACO là một thuật toán metaheuristic hiệu quả. Thuật toán này thuộc nhóm trí tuệ bầy đàn. ACO được thiết kế để giải quyết các bài toán tối ưu tổ hợp. Phương pháp này mô phỏng hành vi kiến, sử dụng các 'kiến nhân tạo' di chuyển trên một đồ thị. Các kiến nhân tạo để lại 'vết mùi' (phiên bản số của pheromone) để hướng dẫn tìm kiếm. Đây là một thuật toán heuristic mạnh mẽ cho nhiều ứng dụng, tối ưu hóa các giải pháp qua quá trình lặp.

II.Cơ chế hoạt động của Thuật toán ACO hiệu quả

Để hiểu sâu hơn về tối ưu hóa đàn kiến, cần nắm vững cơ chế hoạt động của thuật toán ACO. Thuật toán này dựa trên một đồ thị cấu trúc, nơi các 'kiến nhân tạo' di chuyển và xây dựng lời giải. Quyết định di chuyển của mỗi con kiến phụ thuộc vào lượng chất pheromone trên các cạnh và thông tin heuristic cục bộ. Quá trình này lặp đi lặp lại, dần dần hội tụ về các giải pháp tối ưu. ACO là một thuật toán heuristic linh hoạt, có khả năng thích nghi với nhiều loại bài toán khác nhau.

2.1. Vai trò của Chất pheromone trong ACO

Chất pheromone đóng vai trò trung tâm trong thuật toán ACO. Đây là 'bộ nhớ' của hệ thống. Lượng pheromone trên mỗi cạnh đồ thị phản ánh chất lượng của các lời giải đã được tìm thấy qua cạnh đó. Khi kiến di chuyển, lượng pheromone trên đường đi của nó được cập nhật. Đồng thời, pheromone cũng bay hơi theo thời gian. Sự bay hơi ngăn chặn các lời giải kém chất lượng tích tụ quá nhiều pheromone, cho phép thuật toán khám phá các con đường mới. Điều này duy trì sự cân bằng giữa khám phá và khai thác.

2.2. Quy trình thuật toán ACO tổng quát

Thuật toán ACO tổng quát bao gồm các bước chính. Đầu tiên, khởi tạo lượng pheromone trên tất cả các cạnh. Sau đó, một số lượng kiến nhân tạo được thả. Mỗi con kiến xây dựng một lời giải bằng cách di chuyển qua các nút của đồ thị dựa trên xác suất (phụ thuộc vào pheromone và thông tin heuristic). Khi tất cả kiến hoàn thành lời giải, lượng pheromone trên các cạnh được cập nhật dựa trên chất lượng của các lời giải đó. Pheromone cũng được làm bay hơi. Quy trình này lặp lại cho đến khi đạt điều kiện dừng. Đây là một ví dụ điển hình của thuật toán metaheuristic.

2.3. Cấu trúc đồ thị và quyết định của kiến

Thuật toán ACO hoạt động trên một cấu trúc đồ thị. Các nút của đồ thị thường đại diện cho các thành phần hoặc trạng thái của bài toán, và các cạnh biểu thị các lựa chọn chuyển đổi. Mỗi con kiến đưa ra quyết định di chuyển từ nút này sang nút khác. Quyết định này không hoàn toàn ngẫu nhiên. Nó bị ảnh hưởng bởi hai yếu tố: lượng pheromone trên cạnh (thông tin về các lời giải trước đây) và thông tin heuristic cục bộ (thông tin cụ thể của bài toán). Sự kết hợp này giúp kiến hướng tới các giải pháp tốt hơn. Thuật toán ACO có khả năng tự định tuyến và tự lập lịch theo cách phân tán.

III.Nâng cấp Thuật toán ACO Cải tiến Vết Mùi

Hiệu suất của thuật toán tối ưu đàn kiến (ACO) phụ thuộc rất nhiều vào cách quản lý và cập nhật vết mùi pheromone. Các nghiên cứu đã tập trung vào việc cải tiến các quy tắc cập nhật mùi để tối ưu hóa quá trình tìm kiếm. Mục tiêu là đạt được sự cân bằng tốt hơn giữa khả năng khám phá các không gian lời giải mới và khai thác các lời giải đã biết. Việc phân tích toán học về xu thế vết mùi cung cấp cơ sở để phát triển các chiến lược cập nhật tiên tiến, tăng cường khả năng hội tụ và chất lượng lời giải của thuật toán metaheuristic này.

3.1. Phân tích toán học về xu thế vết mùi

Phân tích toán học về xu thế vết mùi là trọng tâm để hiểu và cải thiện thuật toán ACO. Việc này ước lượng xác suất tìm thấy một phương án. Nó nghiên cứu cách lượng pheromone thay đổi theo thời gian và tác động của nó đến hành vi của kiến. Các mô hình toán học giúp dự đoán cách thuật toán sẽ hội tụ và xác định các đặc tính quan trọng như tính khai thác và khám phá. Nắm vững điều này cho phép thiết kế các quy tắc cập nhật pheromone hiệu quả hơn, đảm bảo sự ổn định và tối ưu hóa quá trình tìm kiếm.

3.2. Các chiến lược cập nhật mùi tiên tiến

Có nhiều chiến lược cập nhật mùi đã được đề xuất để nâng cao hiệu quả của thuật toán ACO. Một số phương pháp phổ biến bao gồm Ant Colony System (ACS) và Max-Min Ant System (MMAS). ACS tập trung vào việc cập nhật cục bộ và làm bay hơi pheromone ngay sau khi kiến di chuyển, đồng thời chỉ kiến tốt nhất mới được phép cập nhật toàn cục. MMAS giới hạn lượng pheromone tối đa và tối thiểu trên mỗi cạnh, giúp tránh hiện tượng hội tụ sớm và thúc đẩy đa dạng trong tìm kiếm, tối ưu hóa đàn kiến.

3.3. Đề xuất thuật toán mùi mới SMMAS 3 LAS

Tài liệu này giới thiệu các phương pháp cập nhật mùi mới nhằm cải thiện hiệu suất. Ví dụ, thuật toán SMMAS (Stabilized Max-Min Ant System) và 3-LAS (3-Level Ant System) là những đề xuất cụ thể. Các thuật toán này được thiết kế để khắc phục nhược điểm của các phương pháp hiện có. SMMAS tập trung vào việc ổn định quá trình cập nhật, trong khi 3-LAS giới thiệu nhiều cấp độ pheromone để quản lý thông tin tốt hơn. Ưu điểm của các thuật toán này bao gồm tính bất biến và khả năng đạt kết quả thực nghiệm vượt trội trên các bài toán phức tạp như Bài toán người du lịch (TSP) và UBQP.

IV.Ứng dụng Thuật toán ACO Giải quyết Bài Toán TSP

Bài toán người du lịch (TSP) là một trong những bài toán tối ưu tổ hợp kinh điển. Nó thách thức việc tìm đường đi ngắn nhất qua một tập hợp các thành phố, mỗi thành phố được ghé thăm đúng một lần và quay trở lại điểm xuất phát. Thuật toán tối ưu đàn kiến (ACO) đã được chứng minh là một phương pháp hiệu quả để giải quyết TSP. Khả năng mô phỏng hành vi kiến và cơ chế pheromone giúp ACO tìm kiếm các lộ trình tối ưu. Ngoài TSP, ACO còn ứng dụng rộng rãi trong bài toán định tuyến, bài toán lập lịch và nhiều vấn đề tối ưu khác.

4.1. ACO giải Bài toán người du lịch TSP

Thuật toán ACO được áp dụng hiệu quả để giải Bài toán người du lịch (TSP). Trong bối cảnh TSP, mỗi thành phố được coi là một nút trên đồ thị, và các tuyến đường giữa các thành phố là các cạnh. Các 'kiến nhân tạo' di chuyển từ thành phố này sang thành phố khác, xây dựng một chu trình Hamilton. Lượng pheromone trên các cạnh giúp hướng dẫn kiến tìm kiếm các con đường ngắn nhất. Khi kiến hoàn thành chuyến đi, pheromone sẽ được cập nhật, tăng cường các con đường tốt và làm suy yếu các con đường kém hiệu quả. Đây là một ứng dụng tiêu biểu của trí tuệ bầy đàn.

4.2. Thực nghiệm và hiệu quả trên TSP

Các thực nghiệm đã chứng minh hiệu quả của thuật toán ACO trên Bài toán người du lịch (TSP). Tài liệu này trình bày kết quả thực nghiệm chi tiết, so sánh hiệu suất của các thuật toán ACO khác nhau, bao gồm cả các cải tiến mới về quy tắc cập nhật mùi. Kết quả cho thấy ACO có khả năng tìm kiếm các lời giải gần tối ưu hoặc tối ưu cho TSP, ngay cả với các tập dữ liệu lớn. Điều này khẳng định tính ứng dụng và sức mạnh của phương pháp tối ưu hóa đàn kiến trong giải quyết các bài toán tối ưu tổ hợp phức tạp.

V.ACO trong Sinh học Phân tử Suy diễn Haplotype

Thuật toán tối ưu đàn kiến (ACO) mở rộng ứng dụng sang lĩnh vực sinh học phân tử, đặc biệt là bài toán suy diễn Haplotype. Đây là một bài toán tối ưu tổ hợp phức tạp, đóng vai trò quan trọng trong nghiên cứu di truyền học và y học cá thể hóa. Thuật toán ACOHAP được phát triển để giải quyết vấn đề này, tận dụng cơ chế tìm kiếm hiệu quả của ACO. Ứng dụng này cho thấy tính linh hoạt và khả năng thích nghi của thuật toán metaheuristic với các lĩnh vực đòi hỏi phân tích dữ liệu lớn và phức tạp.

5.1. Bài toán Suy diễn Haplotype với ACOHAP

Bài toán Suy diễn Haplotype là một thách thức lớn trong sinh học. Nó liên quan đến việc xác định chuỗi haplotype từ dữ liệu genotype. Thuật toán ACOHAP được đề xuất để giải quyết bài toán này dựa trên tiêu chuẩn pure parsimony. ACOHAP sử dụng mô hình tối ưu đàn kiến để tìm kiếm các tổ hợp haplotype tối ưu. Cấu trúc đồ thị được thiết kế đặc biệt để biểu diễn các lựa chọn genotype, và các kiến nhân tạo di chuyển để xây dựng các bộ haplotype khả thi. Đây là một ứng dụng cụ thể của thuật toán heuristic trong genomics.

5.2. Cấu trúc thuật toán ACOHAP chi tiết

Thuật toán ACOHAP có cấu trúc chi tiết để giải quyết bài toán suy diễn Haplotype. Nó bao gồm một đồ thị cấu trúc đặc trưng cho bài toán. Các kiến xây dựng lời giải bằng cách di chuyển qua các vị trí trong bộ genotype. Thông tin heuristic được sử dụng để hướng dẫn quá trình tìm kiếm. Vết mùi pheromone được cập nhật dựa trên chất lượng của các lời giải haplotype. ACOHAP cũng tích hợp hoán vị thứ tự xử lý các vị trí và sử dụng tìm kiếm cục bộ để nâng cao chất lượng lời giải. Kết quả thực nghiệm trên dữ liệu chuẩn và dữ liệu thực chứng minh hiệu quả của nó.

VI.ACO và Dự đoán Hoạt động Điều Tiết Gen

Tối ưu hóa đàn kiến (ACO) còn được ứng dụng để cải thiện hiệu quả dự đoán hoạt động điều tiết gen, một lĩnh vực quan trọng trong sinh học hệ thống. Bài toán này thường sử dụng các phương pháp học máy như Support Vector Machine (SVM). ACO được dùng để tối ưu hóa các tham số của mô hình SVM, từ đó nâng cao độ chính xác của dự đoán. Ứng dụng này minh họa khả năng của ACO trong việc tối ưu hóa các mô hình phức tạp và đóng góp vào sự phát triển của trí tuệ nhân tạo trong sinh học. Đây là một ví dụ rõ nét về cách thuật toán heuristic hỗ trợ các bài toán thực tế.

6.1. ACO cải tiến dự đoán điều tiết gen

Dự đoán hoạt động điều tiết gen là một nhiệm vụ phức tạp. Nó liên quan đến việc xác định mối liên kết yếu tố phiên mã trong quá trình phát triển phôi, ví dụ như ở ruồi giấm Drosophila. Phương pháp học máy SVM thường được sử dụng. Tuy nhiên, hiệu quả của SVM phụ thuộc vào việc lựa chọn tham số tối ưu. Thuật toán tối ưu đàn kiến được đề xuất để cải tiến quá trình này. Nó giúp tìm kiếm các tham số SVM tốt nhất, từ đó nâng cao đáng kể độ chính xác của mô hình dự đoán. Đây là một ứng dụng đột phá của thuật toán ACO.

6.2. ACO tối ưu tham số cho SVM

Thuật toán tối ưu đàn kiến được thiết kế để tìm kiếm các tham số tối ưu cho SVM. Một đồ thị cấu trúc và ma trận mùi được xây dựng để biểu diễn không gian tham số. Các 'kiến' di chuyển trong không gian này, xây dựng các tập hợp tham số cho SVM. Thủ tục xây dựng lời giải của kiến và cập nhật mùi pheromone dựa trên hiệu suất dự đoán của SVM với các tham số tương ứng. Quá trình này giúp ACO xác định tập tham số tối ưu, mang lại kết quả thực nghiệm vượt trội trong dự đoán hoạt động điều tiết gen. Đây là một kỹ thuật tối ưu hóa mạnh mẽ.

06/07/2026

Mục lục chi tiết luận án

Lời cam đoan

Lời cảm ơn

Danh mục các ký hiệu và chữ viết tắt

Danh mục các bảng

Danh mục các hình vẽ, đồ thị

MỞ ĐẦU

1. CHƯƠNG 1: TỐI ƯU TỔ HỢP

1.1. Bài toán tối ưu tổ hợp tổng quát

1.2. Bài toán người chào hàng

1.3. Bài toán quy hoạch toàn phương nhị phân không ràng buộc

1.4. Các cách tiếp cận

1.4.1. Heuristic cấu trúc

1.4.2. Tìm kiếm cục bộ

1.4.3. Phương pháp metaheuristic

1.5. Kết luận chương

2. CHƯƠNG 2: PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN

2.1. Từ kiến tự nhiên đến kiến nhân tạo

2.1.1. Kiến tự nhiên

2.1.2. Kiến nhân tạo

2.2. Phương pháp ACO cho bài toán TƯTH tổng quát

2.2.1. Đồ thị cấu trúc

2.2.2. Mô tả thuật toán ACO tổng quát

2.3. Phương pháp ACO giải bài toán người chào hàng

2.3.1. Bài toán TSP và đồ thị cấu trúc

2.3.2. Các thuật toán ACO cho bài toán TSP

2.4. Một số vấn đề liên quan

2.4.1. Đặc tính hội tụ

2.4.2. Thực hiện song song

2.4.3. ACO kết hợp với tìm kiếm cục bộ

2.4.4. Thông tin heuristic

2.4.5. Số lượng kiến

2.4.6. Tham số bay hơi

2.5. Kết luận chương

3. CHƯƠNG 3: TÍNH BIẾN THIÊN CỦA VẾT MÙI VÀ CÁC THUẬT TOÁN MỚI

3.1. Thuật toán tổng quát

3.1.1. Quy tắc chuyển trạng thái

3.1.2. Cập nhật mùi

3.2. Phân tích toán học về xu thế vết mùi

3.2.1. Ước lượng xác suất tìm thấy một phương án

3.2.2. Đặc tính của vết mùi

3.2.3. Tính khai thác và khám phá

3.2.4. Các thuật toán cập nhật mùi theo quy tắc ACS

3.2.5. Các thuật toán cập nhật mùi theo quy tắc MMAS

3.3. Đề xuất các phương pháp cập nhật mùi mới

3.4. Nhận xét về các thuật toán mới

3.4.1. Ưu điểm khi sử dụng SMMAS và 3-LAS

3.4.2. Tính bất biến

3.5. Kết quả thực nghiệm cho hai bài toán TSP và UBQP

3.5.1. Thực nghiệm trên bài toán TSP

3.5.2. Thực nghiệm trên bài toán quy hoạch toàn phương nhị phân không ràng buộc

3.6. Kết luận chương

4. CHƯƠNG 4: THUẬT TOÁN ACOHAP GIẢI BÀI TOÁN SUY DIỄN HAPLOTYPE

4.1. Bài toán suy diễn haplotype và tiêu chuẩn pure parsimony

4.1.1. Giải thích genotype

4.1.2. Suy diễn haplotype theo tiêu chuẩn pure parsimony

4.2. Thuật toán ACOHAP

4.2.1. Mô tả thuật toán

4.2.2. Đồ thị cấu trúc

4.2.3. Thủ tục xây dựng lời giải của mỗi con kiến

4.2.4. Thông tin heuristic

4.2.5. Cập nhật vết mùi

4.2.6. Hoán vị thứ tự xử lý các vị trí trong bộ genotype

4.2.7. Sử dụng tìm kiếm cục bộ

4.2.8. Độ phức tạp thuật toán

4.3. Kết quả thực nghiệm

4.3.1. Thực nghiệm trên bộ dữ liệu chuẩn

4.3.2. Thử nghiệm trên dữ liệu thực

4.4. Kết luận chương

5. CHƯƠNG 5: THUẬT TOÁN AcoSeeD TÌM TẬP HẠT GIỐNG CÓ CÁCH TỐI ƯU

5.1. Bài toán tìm tập hạt giống có cách tối ưu và một số vấn đề liên quan

5.1.1. Bài toán tìm tập hạt giống tối ưu

5.1.2. Các cách tiếp cận hiện nay

5.2. Thuật toán AcoSeeD giải bài toán tìm tập hạt giống tối ưu

5.2.1. Mô tả thuật toán

5.2.2. Thuật toán xác định độ dài các hạt giống

5.2.3. Thuật toán xây dựng các hạt giống

5.2.4. Tìm kiếm cục bộ

5.2.5. Cập nhật mùi

5.3. Kết quả thực nghiệm

5.3.1. Dữ liệu thực nghiệm

5.3.2. Kết quả thực nghiệm trên bộ dữ liệu nhỏ với độ dài các hạt giống đã xác định

5.3.3. Kết quả thực nghiệm trên bộ dữ liệu trung bình

5.3.4. Kết quả thực nghiệm trên bộ dữ liệu lớn

5.4. Kết luận chương

6. CHƯƠNG 6: ỨNG DỤNG PHƯƠNG PHÁP ACO CẢI TIẾN HIỆU QUẢ DỰ ĐOÁN HOẠT ĐỘNG ĐIỀU TIẾT GEN

6.1. Bài toán dự đoán hoạt động điều tiết gen

6.1.1. Mối liên kết yếu tố phiên mã trong phát triển phôi của ruồi giấm Drosophila

6.1.2. Dự đoán hoạt động điều tiết gen bằng phương pháp học máy SVM

6.2. Thuật toán di truyền tìm tham số cho SVM dùng trong dự đoán hoạt động điều tiết gen

6.2.1. Mã hóa các tham số cần tìm

6.2.2. Các phép toán di truyền

6.2.3. Lược đồ thuật toán di truyền

6.3. Thuật toán tối ưu đàn kiến tìm tham số cho SVM dùng trong dự đoán hoạt động điều tiết gen

6.3.1. Đồ thị cấu trúc và ma trận mùi

6.3.2. Thủ tục xây dựng lời giải của kiến và cập nhật mùi

6.4. Kết quả thực nghiệm

6.5. Kết luận chương

DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ CỦA TÁC GIẢ

TÀI LIỆU THAM KHẢO

Xem trước tài liệu

Tải đầy đủ để xem toàn bộ nội dung

Luận án tiến sĩ phương pháp tối ưu đàn kiến và ứng dụng

Tải xuống file đầy đủ để xem toàn bộ nội dung

Tải đầy đủ (134 trang)

Trích đoạn nội dung luận án

Tải xuống để đọc toàn bộ

Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong các công trình nào khác. Tác giả 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Lời cảm ơn Luận án được thực hiện tại trường ĐH Công nghệ - ĐHQG Hà nội, dưới sự hướng dẫn của PGS.TS Hoàng Xuân Huấn.

Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy Hoàng Xuân Huấn, người đã có những định hướng giúp tôi thành công trong việc nghiên cứu của mình. Thầy cũng đã động viên và chỉ bảo giúp tôi vượt qua những khó khăn để tôi hoàn thành được luận án này. Tôi cũng chân thành cảm ơn tới thầy Nguyễn Thanh Thuỷ, thầy Lê Sỹ Vinh, thầy Lê Anh Cường và thầy Nguyễn Phương Thái. Các thầy đã cho tôi nhiều kiến thức quý báu về nghiên cứu khoa học.

Nhờ sự chỉ bảo của các thầy tôi mới hoàn thành tốt luận án. Tôi cũng xin cảm ơn tới các Thầy, Cô thuộc khoa Công nghệ thông tin – ĐH Công nghệ, đã tạo mọi điều kiện thuận lợi giúp tôi trong quá trình làm nghiên cứu sinh. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới gia đình, bạn bè nơi đã cho tôi điểm tựa vững chắc để tôi có được thành công như ngày hôm nay. 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC Lời cam đoan.

3 Danh mục các ký hiệu và chữ viết tắt. 7 Danh mục các bảng. 12 Danh mục các hình vẽ, đồ thị. TỐI ƯU TỔ HỢP.

Bài toán tối ưu tổ hợp tổng quát. Bài toán người chào hàng. Bài toán quy hoạch toàn phương nhị phân không ràng buộc. Các cách tiếp cận.

Heuristic cấu trúc. Tìm kiếm cục bộ. Phương pháp metaheuristic. Kết luận chương.

PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN. Từ kiến tự nhiên đến kiến nhân tạo. Kiến tự nhiên. 28 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

Kiến nhân tạo. Phương pháp ACO cho bài toán TƯTH tổng quát. Đồ thị cấu trúc. Mô tả thuật toán ACO tổng quát.

Phương pháp ACO giải bài toán người chào hàng. Bài toán TSP và đồ thị cấu trúc. Các thuật toán ACO cho bài toán TSP. Một số vấn đề liên quan.

Đặc tính hội tụ. Thực hiện song song. ACO kết hợp với tìm kiếm cục bộ. Thông tin heuristic.

Số lượng kiến. Tham số bay hơi. Kết luận chương. TÍNH BIẾN THIÊN CỦA VẾT MÙI VÀ CÁC THUẬT TOÁN MỚI.

Thuật toán tổng quát. Quy tắc chuyển trạng thái. Cập nhật mùi. Phân tích toán học về xu thế vết mùi.

Ước lượng xác suất tìm thấy một phương án. 55 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Đặc tính của vết mùi. Tính khai thác và khám phá.

Các thuật toán cập nhật mùi theo quy tắc ACS. Các thuật toán cập nhật mùi theo quy tắc MMAS. Đề xuất các phương pháp cập nhật mùi mới. Nhận xét về các thuật toán mới.

Ưu điểm khi sử dụng SMMAS và 3-LAS. Tính bất biến. Kết quả thực nghiệm cho hai bài toán TSP và UBQP. Thực nghiệm trên bài toán TSP.

Thực nghiệm trên bài toán quy hoạch toàn phương nhị phân không ràng buộc. Kết luận chương. THUẬT TOÁN ACOHAP GIẢI BÀI TOÁN SUY DIỄN HAPLOTYPE. Bài toán suy diễn haplotype và tiêu chuẩn pure parsimony.

Giải thích genotype. Suy diễn haplotype theo tiêu chuẩn pure parsimony. Thuật toán ACOHAP. Mô tả thuật toán.

Đồ thị cấu trúc. 85 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Thủ tục xây dựng lời giải của mỗi con kiến. Thông tin heuristic.

Cập nhật vết mùi. Hoán vị thứ tự xử lý các vị trí trong bộ genotype. Sử dụng tìm kiếm cục bộ. Độ phức tạp thuật toán.

Kết quả thực nghiệm. Thực nghiệm trên bộ dữ liệu chuẩn. Thử nghiệm trên dữ liệu thực. Kết luận chương.

THUẬT TOÁN AcoSeeD TÌM TẬP HẠT GIỐNG CÓ CÁCH TỐI ƯU. Bài toán tìm tập hạt giống có cách tối ưu và một số vấn đề liên quan. Bài toán tìm tập hạt giống tối ưu. Các cách tiếp cận hiện nay.

Thuật toán AcoSeeD giải bài toán tìm tập hạt giống tối ưu. Mô tả thuật toán. Thuật toán xác định độ dài các hạt giống. Thuật toán xây dựng các hạt giống.

Tìm kiếm cục bộ. Cập nhật mùi. Kết quả thực nghiệm. 106 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

Dữ liệu thực nghiệm. Kết quả thực nghiệm trên bộ dữ liệu nhỏ với độ dài các hạt giống đã xác định. Kết quả thực nghiệm trên bộ dữ liệu trung bình. Kết quả thực nghiệm trên bộ dữ liệu lớn.

Kết luận chương. ỨNG DỤNG PHƯƠNG PHÁP ACO CẢI TIẾN HIỆU QUẢ DỰ ĐOÁN HOẠT ĐỘNG ĐIỀU TIẾT GEN. Bài toán dự đoán hoạt động điều tiết gen. Mối liên kết yếu tố phiên mã trong phát triển phôi của ruồi giấm Drosophila.

Dự đoán hoạt động điều tiết gen bằng phương pháp học máy SVM. Thuật toán di truyền tìm tham số cho SVM dùng trong dự đoán hoạt động điều tiết gen. Mã hóa các tham số cần tìm. Các phép toán di truyền.

Lược đồ thuật toán di truyền. Thuật toán tối ưu đàn kiến tìm tham số cho SVM dùng trong dự đoán hoạt động điều tiết gen. Đồ thị cấu trúc và ma trận mùi. Thủ tục xây dựng lời giải của kiến và cập nhật mùi.

Kết quả thực nghiệm. 121 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Kết luận chương. 123 DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ CỦA TÁC GIẢ.

125 TÀI LIỆU THAM KHẢO. 126 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Danh mục các ký hiệu và chữ viết tắt Cận trên của vết mùi Cận dưới của vết mùi Cận giữa của vết mùi Vết mùi được khởi tạo ban đầu Vết mùi trên cạnh Thông tin heuristic trên cạnh Số vòng lặp trong thuật toán ACO Số kiến sử dụng trong thuật toán ACO Tham số bay hơi 3-LAS Three-Level Ant System (Hệ kiến ba mức) ACO Ant Colony Optimization (Tối ưu đàn kiến) ACOHAP Thuật toán tối ưu đàn kiến giải bài toán suy diễn haplotype AcoSeeD Thuật toán tối ưu đàn kiến tìm tập hạt giống tối ưu ACOSVM Thuật toán tối ưu đàn kiến tìm tham số trong SVM được dùng để dự báo hoạt động điều tiết gen ACS Ant Colony System (Hệ đàn kiến) 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com AS Ant System (Hệ kiến) CRM Cis-Regulatory Module (Mô-đun điều tiết) EC Evolutionary Computing (Tính toán tiến hoá) GA Genetic Algorithm (Thuật toán di truyền) GASVM Thuật toán di truyền tìm tham số trong SVM được dùng để dự báo hoạt động điều tiết gen G-best Global-best (Lời giải tốt nhất tính đến thời điểm hiện tại) HI Haplotype Inference (Suy diễn haplotype) HIPP Haplotype Inference by Pure Parsimony (Suy diễn haplotype theo tiêu chuẩn Pure Parsimony) I-best Iteration-best (Lời giải tốt nhất trong bước lặp hiện tại) JSS Job Shop Scheduling (Bài toán lập lịch sản xuất) MLAS Multi-level Ant System (Hệ kiến đa mức) MMAS Max-Min Ant System (Hệ kiến Max Min) PSO Particle Swarm Optimization (Tối ưu bầy đàn) SA Simulated Annealing (Thuật toán mô phỏng luyện kim) SMMAS Smoothed Max-Min Ant System (Hệ kiến Max Min trơn) SpEED Thuật toán leo đồi tìm tập hạt giống tối ưu 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com SVM Support Vector Machine (Phương pháp học máy SVM) TSP Traveling Salesman Problem (Bài toán người chào hàng) TƯTH Tối ưu tổ hợp UBQP Unconstrained Binary Quadratic Programming (Bài toán quy hoạch toàn phương nhị phân không ràng buộc) 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Danh mục các bảng Bảng 2.1: Thuật toán ACO theo thứ tự thời gian xuất hiện .1: Kết quả thực nghiệm so sánh bốn phương pháp .2: Kết quả thực nghiệm so sánh các phương pháp MMAS, SMMAS, SMMASRS (SMMAS có khởi tạo lại vết mùi), MLAS và 3-LAS.3: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =200 .4: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =500 .5: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =500 .6: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =1000 .7: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =2500 .1: Thiết đặt tham số cho ACOHAP .2: Bảng tóm tắt thông tin về các bộ dữ liệu chuẩn .3: Kết quả thực nghiệm so sánh ACOHAP với CollHap với dữ liệu chuẩn .4: Thông tin dữ liệu thực .5: Kết quả thực nghiệm với dữ liệu thực .1: Kết quả thực nghiệm SpEED với AcoSeeD trên bộ dữ liệu nhỏ .2: So sánh AcoSeeD với các phương pháp khác trên bộ dữ liệu trung bình .3: Kết quả thực nghiệm so sánh AcoSeeD với các phương pháp trên bộ dữ liệu lớn PatternHunterII và BFAST .4: So sánh AcoSeeD với SpEEDfast trên bộ dữ liệu lớn MegaBFAST .1: Kết quả thực nghiệm so sánh 3 phương pháp. 121 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Danh mục các hình vẽ, đồ thị Hình 1.1: Phương pháp heuristic cấu trúc tham ăn .2: Lời giải nhận được nhờ thay 2 cạnh (2,3), (1,6) bằng (1,3), (2,6) .3: Thuật toán memetic sử dụng EC .1: Thực nghiệm cây cầu đôi .2: Thí nghiệm bổ xung .3: Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm .4: Thuật toán ACO .5: Lựa chọn đỉnh đi tiếp theo .6: Thuật toán ACO giải bài toán TSP có sử dụng tìm kiếm cục bộ .1: Hai chu trình khác nhau 7 cạnh, đường liền qua cạnh và đường đứt đoạn qua cạnh .2: Đồ thị cấu trúc giải bài toán UBQP .1: Thuật toán ACOHAP .2: Đồ thị cấu trúc (phần thuộc đường đậm) xác định giải thích genotype 201 .3: Thủ tục tìm lời giải của mỗi con kiến .4: Lời giải HI của một con kiến với =121, =002, =221 .1: Thuật toán leo đồi dùng trong SpEED và SpEEDfast .2: Thuật toán AcoSeeD .3: Đồ thị cấu trúc để xác định độ dài các hạt giống .4: Đồ thị cấu trúc xây dựng các hạt giống. 105 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1: Dự đoán hoạt động điều tiết gen dựa trên liên kết phiên mã .2: Sơ đồ đánh giá hiệu quả tham số SVM .3: Một nhiễm sắc thể biểu diễn và .4: Gen ở vị trí in đậm đột biến 0 thành 1 hoặc ngược lại .5: Minh họa phép toán tương giao chéo của cặp nhiễm sắc thể .6: Thuật toán GASVM .7: Thuật toán ACOSVM .8: Đồ thị cấu trúc .9: Biểu đồ so sánh kết quả dự đoán đúng giữa ba phương pháp.

122 14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ

Trích dẫn luận án này

Phương pháp tối ưu đàn kiến và ứng dụng (n.d.) [Luận án tiến sĩ, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội]. LuanAn.net. https://luanan.net/cong-nghe-thong-tin/tri-tue-nhan-tao/phuong-phap-toi-uu-dan-ken-va-ung-dung

Câu hỏi thường gặp

Luận án "Phương pháp tối ưu đàn kiến và ứng dụng" nghiên cứu về vấn đề gì?

Tối ưu đàn kiến: Thuật toán tìm kiếm hiệu quả cho bài toán phức tạp, ứng dụng trong lịch trình, định tuyến.

Luận án "Phương pháp tối ưu đàn kiến và ứng dụng" được bảo vệ tại trường nào?

Luận án này được bảo vệ tại Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội.

Luận án "Phương pháp tối ưu đàn kiến và ứng dụng" thuộc chuyên ngành gì?

Luận án "Phương pháp tối ưu đàn kiến và ứng dụng" thuộc chuyên ngành Công nghệ thông tin. Danh mục: Trí Tuệ Nhân Tạo.

Luận án "Phương pháp tối ưu đàn kiến và ứng dụng" có bao nhiêu trang?

Luận án "Phương pháp tối ưu đàn kiến và ứng dụng" có 134 trang. Bạn có thể xem trước một phần tài liệu ngay trên trang web trước khi tải về.

Cách tải luận án "Phương pháp tối ưu đàn kiến và ứng dụng" về máy như thế nào?

Để tải luận án về máy, bạn nhấn nút "Tải xuống ngay" trên trang này, sau đó hoàn tất thanh toán phí lưu trữ. File sẽ được tải xuống ngay sau khi thanh toán thành công. Hỗ trợ qua Zalo: 0559 297 239.

Luận án liên quan

Chia sẻ tài liệu: Facebook Twitter