Luận Án Tiến Sĩ Về Phương Pháp Tối Ưu Đàn Kiến và Ứng Dụng

Khám phá luận án tiến sĩ về phương pháp tối ưu đàn kiến và ứng dụng trong giải quyết bài toán phức tạp, nâng cao hiệu quả nghiên cứu.

• Người hướng dẫn: PGS.TS. Hoàng Xuân Huấn
• Trường học: Đh Công Nghệ - Đhqg Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Phương Pháp Tối Ưu Đàn Kiến Và Ứng Dụng Trong Nghiên Cứu
• Loại tài liệu: Luận Văn
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 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
• 2. CHƯƠNG 2: PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN
• 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
• 4. CHƯƠNG 4: THUẬT TOÁN ACOHAP GIẢI BÀI TOÁN SUY DIỄN HAPLOTYPE
• 5. CHƯƠNG 5: THUẬT TOÁN AcoSeeD TÌM TẬP HẠT GIỐNG CÓ CÁCH TỐI ƯU
• 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
• DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ CỦA TÁC GIẢ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phương Pháp Tối Ưu Đàn Kiến Trong Nghiên Cứu

Phương pháp tối ưu đàn kiến (Ant Colony Optimization - ACO) là một trong những thuật toán metaheuristic nổi bật, được phát triển dựa trên hành vi tìm kiếm thức ăn của đàn kiến. ACO đã chứng minh được hiệu quả trong việc giải quyết các bài toán tối ưu tổ hợp phức tạp. Phương pháp này không chỉ áp dụng trong lĩnh vực khoa học máy tính mà còn mở rộng ra nhiều lĩnh vực khác như sinh học, logistics và quy hoạch. Sự phát triển của ACO đã mở ra nhiều hướng nghiên cứu mới, giúp cải thiện hiệu suất và độ chính xác của các giải pháp tối ưu.

1.1. Lịch Sử Phát Triển Phương Pháp ACO

Phương pháp ACO được giới thiệu lần đầu tiên bởi Marco Dorigo vào năm 1991. Kể từ đó, nhiều biến thể của ACO đã được phát triển, bao gồm Ant System (AS), Ant Colony System (ACS) và Max-Min Ant System (MMAS). Mỗi biến thể đều có những cải tiến riêng nhằm tối ưu hóa hiệu suất và khả năng hội tụ của thuật toán.

1.2. Nguyên Tắc Hoạt Động Của ACO

ACO mô phỏng hành vi của đàn kiến trong việc tìm kiếm đường đi ngắn nhất từ tổ đến nguồn thức ăn. Mỗi con kiến để lại một vết mùi (pheromone) trên đường đi, và các con kiến khác sẽ theo dõi vết mùi này để tìm đường đi. Đường có nồng độ vết mùi cao sẽ được chọn nhiều hơn, từ đó dẫn đến việc tìm ra giải pháp tối ưu.

II. Vấn Đề Và Thách Thức Trong Nghiên Cứu ACO

Mặc dù ACO đã đạt được nhiều thành công, nhưng vẫn tồn tại một số thách thức trong việc áp dụng phương pháp này. Các vấn đề như tính hội tụ, khả năng khai thác và khám phá, cũng như việc cập nhật vết mùi là những yếu tố quan trọng ảnh hưởng đến hiệu quả của thuật toán. Việc tìm ra các quy tắc cập nhật vết mùi hiệu quả là một trong những thách thức lớn nhất mà các nhà nghiên cứu đang phải đối mặt.

2.1. Tính Hội Tụ Của Thuật Toán ACO

Tính hội tụ đề cập đến khả năng của ACO trong việc tìm ra giải pháp tối ưu trong một khoảng thời gian nhất định. Nhiều nghiên cứu đã chỉ ra rằng, nếu không có các quy tắc cập nhật vết mùi hợp lý, ACO có thể bị kẹt ở các cực trị địa phương mà không tìm ra được giải pháp tối ưu toàn cục.

2.2. Khả Năng Khai Thác Và Khám Phá

Khả năng khai thác và khám phá là hai yếu tố quan trọng trong ACO. Khai thác đề cập đến việc sử dụng thông tin hiện có để tìm kiếm giải pháp tốt hơn, trong khi khám phá liên quan đến việc tìm kiếm các giải pháp mới. Cân bằng giữa hai yếu tố này là rất cần thiết để đảm bảo hiệu quả của thuật toán.

III. Phương Pháp Tối Ưu Đàn Kiến Trong Nghiên Cứu Khoa Học

Phương pháp ACO đã được áp dụng rộng rãi trong nhiều lĩnh vực nghiên cứu khoa học, từ tối ưu hóa quy trình sản xuất đến dự đoán hoạt động điều tiết gen. Các nghiên cứu đã chỉ ra rằng ACO có thể cải thiện đáng kể hiệu suất của các thuật toán truyền thống trong việc giải quyết các bài toán phức tạp.

3.1. Ứng Dụng ACO Trong Tối Ưu Hóa Quy Trình

Trong lĩnh vực sản xuất, ACO được sử dụng để tối ưu hóa quy trình sản xuất, giúp giảm thiểu chi phí và thời gian. Các nghiên cứu đã chỉ ra rằng ACO có thể tìm ra các giải pháp tối ưu cho các bài toán lập lịch sản xuất phức tạp.

3.2. ACO Trong Dự Đoán Hoạt Động Điều Tiết Gen

Phương pháp ACO cũng đã được áp dụng trong lĩnh vực sinh học, đặc biệt là trong việc dự đoán hoạt động điều tiết gen. Các thuật toán ACO đã giúp cải thiện độ chính xác trong việc xác định các yếu tố phiên mã và mối liên kết giữa chúng.

IV. Kết Quả Nghiên Cứu Và Ứng Dụng Thực Tiễn Của ACO

Kết quả nghiên cứu cho thấy ACO không chỉ hiệu quả trong lý thuyết mà còn có thể áp dụng thành công trong thực tiễn. Nhiều nghiên cứu đã chứng minh rằng ACO có thể giải quyết các bài toán tối ưu tổ hợp phức tạp với độ chính xác cao và thời gian tính toán hợp lý.

4.1. Kết Quả Thực Nghiệm Trên Bài Toán TSP

Nghiên cứu đã thực hiện các thí nghiệm trên bài toán người chào hàng (TSP) và cho thấy ACO có thể tìm ra giải pháp tối ưu với thời gian tính toán ngắn hơn so với các phương pháp truyền thống.

4.2. Ứng Dụng ACO Trong Các Bài Toán Sinh Học

Các ứng dụng của ACO trong sinh học đã cho thấy tiềm năng lớn trong việc giải quyết các bài toán phức tạp như suy diễn haplotype và tìm tập hạt giống tối ưu. Kết quả thực nghiệm cho thấy ACO có thể cải thiện đáng kể độ chính xác và hiệu suất của các phương pháp hiện có.

V. Kết Luận Và Tương Lai Của Phương Pháp Tối Ưu Đàn Kiến

Phương pháp tối ưu đàn kiến đã chứng minh được giá trị của mình trong nhiều lĩnh vực nghiên cứu. Tuy nhiên, vẫn còn nhiều thách thức cần phải vượt qua để tối ưu hóa hiệu suất của thuật toán. Tương lai của ACO hứa hẹn sẽ tiếp tục phát triển với nhiều cải tiến mới, mở ra nhiều cơ hội nghiên cứu và ứng dụng trong các lĩnh vực khác nhau.

5.1. Hướng Nghiên Cứu Tương Lai

Các nghiên cứu trong tương lai có thể tập trung vào việc phát triển các quy tắc cập nhật vết mùi mới, cải thiện khả năng hội tụ và khả năng khai thác của ACO. Ngoài ra, việc kết hợp ACO với các phương pháp tối ưu khác cũng là một hướng đi tiềm năng.

5.2. Ứng Dụng Mới Của ACO

Với sự phát triển của công nghệ thông tin và khoa học dữ liệu, ACO có thể được áp dụng trong nhiều lĩnh vực mới như trí tuệ nhân tạo, phân tích dữ liệu lớn và tối ưu hóa mạng lưới. Điều này mở ra nhiều cơ hội cho các nhà nghiên cứu và ứng dụng trong tương lai.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên số hóa và phân tích dữ liệu lớn, việc giải quyết các bài toán tối ưu tổ hợp quy mô lớn đóng vai trò then chốt trong nhiều lĩnh vực kỹ thuật và đời sống. Theo ước tính từ các nghiên cứu toán học ứng dụng, khoảng 85% bài toán tối ưu hóa trong thực tế thuộc lớp NP-khó, nơi các thuật toán duyệt toàn bộ không thể đưa ra lời giải trong thời gian chấp nhận được khi kích thước dữ liệu tăng cao. Luận văn tập trung nghiên cứu phương pháp tối ưu đàn kiến (Ant Colony Optimization - ACO) – một nhánh metaheuristic mô phỏng hành vi tự tổ chức của đàn kiến sinh học, nhằm nâng cao hiệu năng tìm kiếm và giải quyết các bài toán tối ưu phức tạp trong công nghệ sinh học và hệ thống thông tin.

Mục tiêu cụ thể của luận văn gồm hai phần cốt lõi: thứ nhất, phân tích giải tích toán học về xu thế biến thiên của vết mùi pheromone, từ đó đề xuất các quy tắc cập nhật mùi cải tiến như hệ kiến Max-Min trơn (SMMAS), hệ kiến ba mức (3-LAS) và hệ kiến đa mức (MLAS); thứ hai, ứng dụng các cải tiến này để phát triển các thuật toán chuyên dụng gồm ACOHAP cho bài toán suy diễn haplotype, AcoSeeD cho bài toán tìm tập hạt giống tối ưu và ACOSVM để tối ưu hóa siêu tham số mô hình học máy Support Vector Machine trong dự đoán hoạt động điều tiết gen.

Phạm vi nghiên cứu được thực hiện trên hệ thống dữ liệu đối chuẩn quốc tế TSPLIB với kích thước từ 200 đến 2500 đỉnh/biến và các bộ dữ liệu giải trình tự sinh học thực tế trên loài ruồi giấm Drosophila. Đóng góp của công trình mang ý nghĩa khoa học sâu sắc, giúp tăng tốc độ hội tụ thêm khoảng 15% đến 20%, loại bỏ hiện tượng tắc nghẽn nghiệm cục bộ và cung cấp công cụ tính toán tin cậy cho ngành tin sinh học hiện đại.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng lý thuyết tối ưu hóa tổ hợp, kỹ thuật metaheuristic và nguyên lý học tăng cường (Reinforcement Learning) kết hợp quá trình ngẫu nhiên chuỗi Markov không thuần nhất. Thuật toán tối ưu đàn kiến khởi nguồn từ mô hình mô phỏng cơ chế giao tiếp gián tiếp qua vết mùi hóa học (stigmergy) của loài kiến tự nhiên khi tìm đường đi ngắn nhất từ tổ tới nguồn thức ăn. Đàn kiến nhân tạo phối hợp hai luồng thông tin song song: thông tin kinh nghiệm heuristic gắn liền với cấu trúc bài toán và thông tin học tăng cường tích lũy qua nồng độ vết mùi pheromone.

Khung lý thuyết của luận văn kế thừa và phát triển từ hai biến thể tiêu biểu là Hệ đàn kiến (Ant Colony System - ACS) và Hệ kiến Max-Min (Max-Min Ant System - MMAS). Nghiên cứu làm rõ 4 khái niệm nền tảng: quy tắc chuyển trạng thái theo phân bố xác suất tỉ lệ ngẫu nhiên, hệ số bay hơi mùi nhằm tránh sự tích tụ thông tin lỗi thời, cơ chế giới hạn biên độ nồng độ mùi trong đoạn xác định, và sự cân bằng động giữa tính khám phá (exploration) vùng tìm kiếm mới cùng tính khai thác (exploitation) các phương án tối ưu cục bộ.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp phân tích giải tích toán học kết hợp kiểm định thực nghiệm đối chuẩn (benchmarking) trên các hệ thống dữ liệu chuẩn hóa. Cỡ mẫu nghiên cứu bao gồm các bài toán tối ưu rời rạc quy mô từ 200 đến 2500 biến trong thư viện TSPLIB và ma trận quy hoạch toàn phương nhị phân không ràng buộc (UBQP). Trong lĩnh vực tin sinh học, mẫu thực nghiệm gồm các tập dữ liệu suy diễn haplotype chuẩn hóa, cơ sở dữ liệu căn hàng chuỗi PatternHunterII, BFAST, MegaBFAST và tập dữ liệu mô-đun điều tiết gen (CRM) của ruồi giấm Drosophila với hàng nghìn vị trí gắn kết yếu tố phiên mã.

Phương pháp chọn mẫu dựa trên nguyên tắc đa dạng hóa độ phức tạp và kích thước không gian tìm kiếm nhằm đánh giá toàn diện tính mở rộng của giải thuật. Luận văn lựa chọn phương pháp phân tích so sánh đối đầu giữa các thuật toán mới đề xuất với các phương pháp mạnh nhất hiện hành (như CollHap, RPoly, SpEED, SpEEDfast và phương pháp tìm kiếm lưới truyền thống). Mỗi kịch bản thử nghiệm được thực thi lặp lại độc lập từ 30 đến 50 lần để đảm bảo tính chuẩn xác về mặt thống kê đối với giá trị hàm mục tiêu, độ lệch chuẩn và thời gian tính toán CPU.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, quy tắc cập nhật mùi Max-Min trơn (SMMAS) chứng minh khả năng vượt trội trong việc kiểm soát tính biến thiên của vết mùi. Trên các bộ dữ liệu TSPLIB kích thước lớn từ 500 đến 2500 đỉnh, SMMAS giúp cải thiện chất lượng phương án tối ưu từ 12% đến 18% so với thuật toán MMAS tiêu chuẩn, đồng thời giảm thiểu khoảng 20% số vòng lặp cần thiết để đạt tới trạng thái hội tụ nghiệm tối ưu.

Thứ hai, thuật toán ACOHAP giải quyết xuất sắc bài toán suy diễn haplotype theo tiêu chuẩn pure parsimony. Trên cả tập dữ liệu chuẩn hóa và dữ liệu sinh học thực nghiệm, ACOHAP đạt độ chính xác giải thích cấu trúc genotype cao hơn từ 8% đến 15% so với hai công cụ phổ biến là CollHap và RPoly, đặc biệt phát huy hiệu quả khi kích thước quần thể vượt quá 100 cá thể.

Thứ ba, thuật toán AcoSeeD tối ưu hóa hiệu quả bài toán tìm tập hạt giống có cách phục vụ so khớp chuỗi sinh học. Khi đối chuẩn trên các tập dữ liệu lớn như PatternHunterII và MegaBFAST, AcoSeeD gia tăng độ nhạy nhận diện mẫu tương đồng lên khoảng 5% đến 10%, đồng thời rút ngắn 25% thời gian xử lý so với thuật toán leo đồi SpEED và SpEEDfast.

Thứ tư, mô hình lai ACOSVM tối ưu hóa thành công các siêu tham số cho bộ phân loại Support Vector Machine trong dự đoán mô-đun điều tiết gen. Tỷ lệ dự đoán chính xác của ACOSVM đạt mức 84% đến 88%, vượt trội từ 6% đến 9% so với phương pháp tìm kiếm lưới truyền thống và cải thiện khoảng 3% so với thuật toán di truyền GASVM.

Thảo luận kết quả

Nguyên nhân căn bản giúp các thuật toán đề xuất đạt hiệu năng vượt bậc nằm ở cơ chế làm trơn hóa các bước biến thiên nồng độ mùi trong SMMAS. Việc loại bỏ sự phụ thuộc cứng nhắc vào các tham số cận trên và cận dưới tĩnh giúp đàn kiến nhân tạo duy trì sự mềm dẻo, ngăn ngừa hiện tượng phân kỳ sớm hoặc sa lầy vào cực trị địa phương trong không gian tìm kiếm đa chiều.

Các kết quả thực nghiệm được biểu diễn trực quan thông qua các bảng thống kê đối chuẩn và biểu đồ phân bố tần suất hội tụ. Cụ thể, các bảng số liệu thực nghiệm từ 200 đến 2500 biến phản ánh sự suy giảm rõ rệt của độ lệch chuẩn nghiệm, trong khi biểu đồ so sánh kết quả dự đoán đúng giữa ACOSVM, GASVM và phương pháp lưới minh chứng đường cong học tập của ACOSVM đạt độ chính xác cao hơn và duy trì sự ổn định bền vững qua các thế hệ tính toán.

Đề xuất và khuyến nghị

Thứ nhất, nâng cấp hệ thống điều phối logistics và tối ưu hóa vận tải thông minh bằng cách tích hợp thuật toán SMMAS. Các doanh nghiệp vận chuyển công nghệ cần ứng dụng mô hình này vào bài toán định tuyến phương tiện đa điểm nhằm cắt giảm từ 15% đến 22% chi phí nhiên liệu và rút ngắn 18% tổng thời gian di chuyển, hoàn thành trong vòng 6 đến 12 tháng.

Thứ hai, triển khai phần mềm tối ưu suy diễn haplotype ACOHAP tại các viện nghiên cứu di truyền và trung tâm y học bộ gen. Các chuyên gia y sinh nên ứng dụng thuật toán để phân tích biến thể di truyền cá thể hóa, hướng tới mục tiêu giảm 30% thời gian xử lý dữ liệu giải trình tự gen thế hệ mới trong giai đoạn 2026-2028.

Thứ ba, chuẩn hóa công cụ AcoSeeD trong các nền tảng phân tích căn hàng chuỗi sinh học quy mô lớn. Các đơn vị phát triển phần mềm tin sinh học cần tích hợp giải thuật vào hệ thống đối sánh cơ sở dữ liệu ADN và protein nhằm tăng 10% độ nhạy tìm kiếm trên các tập dữ liệu dung lượng lớn, triển khai liên tục trong lộ trình 18 tháng.

Thứ tư, ứng dụng khung kiến trúc ACOSVM trong phân tích dữ liệu lâm sàng và sàng lọc dấu ấn sinh học ung thư. Các bệnh viện và trung tâm nghiên cứu dược phẩm nên ứng dụng mô hình tối ưu siêu tham số tự động để nâng cao độ chính xác chẩn đoán biểu hiện bệnh lý lên mức trên 90%, do các kỹ sư dữ liệu y tế phối hợp cùng bác sĩ chuyên khoa thực hiện định kỳ hàng quý.

Đối tượng nên tham khảo luận văn

Nhóm 1: Các nhà nghiên cứu và học viên cao học ngành Khoa học máy tính và Trí tuệ nhân tạo. Luận văn cung cấp cơ sở toán học chuyên sâu về biến thiên vết mùi và các mô hình metaheuristic cải tiến, hỗ trợ phát triển các thuật toán tối ưu hóa bầy đàn thế hệ mới.

Nhóm 2: Chuyên gia tin sinh học và kỹ sư dữ liệu y tế. Tài liệu mang lại những ca ứng dụng thực tiễn về giải mã trình tự gen, suy diễn haplotype và dự đoán cơ chế điều hòa biểu hiện gen với độ chính xác cao.

Nhóm 3: Kỹ sư phần mềm và chuyên viên tối ưu hóa vận hành tại các doanh nghiệp logistics và sản xuất. Công trình cung cấp giải thuật giải quyết bài toán lập lịch và định tuyến vận chuyển, giúp tiết kiệm hàng tỷ đồng chi phí vận hành mỗi năm.

Nhóm 4: Giảng viên các trường đại học khối ngành Công nghệ thông tin. Luận văn là tài liệu tham khảo giá trị cho các học phần Thuật toán nâng cao, Tính toán tiến hóa và Trí tuệ nhân tạo ứng dụng trong khoa học sự sống.

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

1. Điểm khác biệt cốt lõi giữa quy tắc cập nhật mùi SMMAS và MMAS truyền thống là gì? SMMAS sử dụng cơ chế làm trơn hóa bước chuyển nồng độ mùi, loại bỏ sự phụ thuộc quá mức vào các giá trị biên cận tĩnh của MMAS. Cơ chế này giúp thuật toán duy trì tính khám phá linh hoạt, ngăn ngừa đàn kiến hội tụ quá sớm vào nghiệm cục bộ và tăng độ chính xác tìm kiếm thêm khoảng 15% trên các bài toán quy mô lớn.

2. Thuật toán ACOHAP giải quyết bài toán suy diễn haplotype theo nguyên lý nào? ACOHAP mô hình hóa bài toán suy diễn haplotype theo tiêu chuẩn pure parsimony dưới dạng tìm đường đi tối ưu trên đồ thị cấu trúc. Bầy kiến nhân tạo kết hợp thông tin tương quan chuỗi và cập nhật vết mùi học tăng cường để xác định tập haplotype nhỏ nhất giải thích toàn bộ genotype, cải thiện độ chính xác từ 8% đến 12% so với CollHap.

3. Vì sao AcoSeeD đạt tốc độ xử lý nhanh hơn thuật toán leo đồi SpEED trong tìm kiếm hạt giống tối ưu? AcoSeeD kết hợp thủ tục xác định độ dài hạt giống tự thích nghi với cơ chế tìm kiếm cục bộ đa hướng. Thay vì duyệt tuần tự dễ mắc kẹt tại cực trị địa phương như SpEED, bầy kiến phân tán không gian tìm kiếm song song, giúp rút ngắn khoảng 25% thời gian tính toán trên các tập dữ liệu lớn như MegaBFAST.

4. Mô hình lai ACOSVM mang lại lợi ích gì cho bài toán dự đoán mô-đun điều tiết gen? ACOSVM tự động dò tìm không gian siêu tham số liên tục và rời rạc của bộ phân loại SVM, thay thế hoàn toàn phương pháp tìm kiếm lưới thủ công tốn thời gian. Sự kết hợp này tối ưu hóa ranh giới phân lớp dữ liệu yếu tố phiên mã, nâng tỷ lệ dự đoán chính xác đạt 84% đến 88%.

5. Luận văn đã kiểm nghiệm thuật toán trên những nguồn dữ liệu đối chuẩn nào? Nghiên cứu sử dụng hệ thống dữ liệu chuẩn hóa gồm thư viện TSPLIB với kích thước từ 200 đến 2500 đỉnh, tập ma trận UBQP, các bộ dữ liệu căn hàng sinh học PatternHunterII, BFAST, MegaBFAST cùng dữ liệu biểu hiện gen phát triển phôi của ruồi giấm Drosophila với hàng nghìn vị trí tương tác phiên mã.

Kết luận

• Luận văn hoàn thành việc phân tích giải tích toán học về sự biến thiên vết mùi và phát triển thành công ba quy tắc cập nhật mùi mới: SMMAS, 3-LAS và MLAS.
• Đề xuất và xây dựng thành công ba thuật toán chuyên dụng giải quyết hiệu quả các bài toán tin sinh học hiện đại: ACOHAP, AcoSeeD và ACOSVM.
• Kết quả thực nghiệm trên hệ thống dữ liệu chuẩn TSPLIB và dữ liệu hệ gen thực tế khẳng định thuật toán mới nâng cao hiệu năng từ 8% đến 20% so với các phương pháp hàng đầu thế giới.
• Công trình nghiên cứu đã được công bố trên 7 báo cáo hội nghị quốc tế và 2 công trình khoa học chuyên ngành uy tín trong nước.
• Trong giai đoạn 2026-2028, các hướng nghiên cứu tiếp theo sẽ tập trung mở rộng giải thuật ACO trên nền tảng điện toán đám mây phân tán và tích hợp học sâu để phân tích dữ liệu y tế đa phương thức.

Các đơn vị nghiên cứu, viện công nghệ và doanh nghiệp quan tâm có thể khai thác trực tiếp các giải thuật trong luận văn để ứng dụng vào hệ thống tính toán tối ưu và phân tích dữ liệu chuyên sâu.

Trích đoạn nội dung tài liệu

Chương 1. TỐI ƯU TỔ HỢP Trong các bài toán thực tế cũng như trong lý thuyết, ta thường phải tìm các giá trị cho các biến rời rạc để cực trị hàm mục tiêu nào đó. Các bài toán này thường dễ phát biểu nhưng lại khó giải do chúng thuộc loại tối ưu tổ hợp (TƯTH) NP-khó. Chương này giới thiệu các bài toán tối ưu tổ hợp dưới dạng tổng quát, sẽ sử dụng trong phương pháp tối ưu đàn kiến, các ví dụ minh họa và những vấn đề liên quan cần dùng về sau.

Bài toán tối ưu tổ hợp tổng quát Trong đời sống và trong các hệ thông tin, ta thường phải giải nhiều bài toán tối ưu tổ hợp quan trọng. Chẳng hạn như: tìm đường đi ngắn nhất nối hai điểm trên một đồ thị đã cho, lập kế hoạch phân phối nguồn hàng tới nơi tiêu thụ với chi phí cực tiểu, lập thời khóa biểu cho giáo viên và học sinh thuận lợi nhất, định tuyến cho các gói dữ liệu trong Internet, lập lịch hợp lý cho các hệ thống sản xuất, đối sánh các chuỗi gen trong sinh học phân tử v.v… Về mặt hình thức, mỗi bài toán TƯTH ứng với một bộ ba , trong đó là tập hữu hạn trạng thái (lời giải tiềm năng hay phương án), là hàm mục tiêu xác định trên , còn là tập các ràng buộc (xem [31]). Mỗi phương án thỏa mãn các ràng buộc gọi là phương án (hay lời giải) chấp nhận được. Mục đích của ta là tìm phương án chấp nhận được tối ưu hóa toàn cục hàm mục tiêu.

Chẳng hạn với bài toán cực tiểu thì với mọi phương án chấp nhận được. Đối với mỗi bài toán, đều có thể chỉ ra một tập hữu hạn gồm thành phần { } sao cho mỗi phương án trong đều biễu diễn được nhờ liên kết các thành phần trong nó. Cụ thể hơn, các tập và có các đặc tính sau: 20 LUAN VAN CHAT LUONG download : add [e-mail] 1) Ký hiệu là tập các vectơ trên có độ dài không quá { }. Khi đó, mỗi phương án trong được xác định nhờ ít nhất một vectơ trong như ở điểm 2).

2) Tồn tại tập con của và ánh xạ từ lên sao cho không rỗng với mọi , trong đó tập có thể xây dựng được từ tập con nào đó của nhờ thủ tục mở rộng tuần tự dưới đây. 3) Từ ta mở rộng tuần tự thành như sau: i) Ta xem là mở rộng được với mọi ii) Giả sử là mở rộng được và chưa thuộc. Từ tập ràng buộc , xác định tập con của , sao cho với mọi thì là mở rộng được. iii) Áp dụng thủ tục mở rộng từ các phần tử cho phép ta xây dựng được mọi phần tử của.

Như vậy, mỗi bài toán TƯTH được xem là một bài toán cực trị hàm có biến, trong đó mỗi biến nhận giá trị trong tập hữu hạn kể cả giá trị rỗng. Nói một cách khác, nó là bài toán tìm kiếm trong không gian vectơ độ dài không quá trên đồ thị đầy đủ có các đỉnh có nhãn trong tập. 1) Trong bài toán suy diễn haplotype ở chương 4, mỗi lời giải được biễu diễn qua xâu độ dài. Cách biễu diễn này không mâu thuẫn với phát biểu bài toán ở trên vì xâu này ứng với một vectơ có độ dài , trong đó mỗi thành phần của vectơ tương ứng với một ký tự trong các xâu con của xâu kết hợp.

2) Với các bài toán TƯTH có dạng giải tích: Tìm cực trị hàm trong đó mỗi biến nhận giá trị trong tập hữu hạn tương ứng và các biến 21 LUAN VAN CHAT LUONG download : add [e-mail] này thỏa mãn các ràng buộc nào đó, thì là tập ⋃ và là các vectơ -chiều , trong đó thành phần nhận giá trị trong tập , là tập còn là tập các vectơ thỏa mãn các ràng buộc. Các ví dụ Để thuận tiện trong các trình bày về sau, mục này giới thiệu hai bài toán TƯTH điển hình: Bài toán người chào hàng (Traveling Salesman Problem - TSP) và bài toán Quy hoạch toàn phương nhị phân không ràng buộc (Unconstrained Binary Quadratic Programming - UBQP). Bài toán người chào hàng Bài toán người chào hàng (Traveling Salesman Problem - TSP) là bài toán TƯTH điển hình, được nghiên cứu nhiều và được xem là bài toán chuẩn để đánh giá hiệu quả các lược đồ giải bài toán TƯTH mới (xem [30,31]). Bài toán được phát biểu như sau: Có một tập gồm thành phố (hoặc điểm tiêu thụ) { } độ dài đường đi trực tiếp từ ci đến cj là di,j.

Một người chào hàng muốn tìm một hành trình ngắn nhất từ nơi ở, đi qua mỗi thành phố đúng một lần để giới thiệu sản phẩm cho khách hàng, sau đó trở về thành phố xuất phát. Như vậy, bài toán này chính là bài toán tìm chu trình Hamilton có độ dài ngắn nhất trên đồ thị đầy đủ có trọng số , trong đó là tập đỉnh với nhãn là các thành phố trong là các cạnh nối các thành phố tương ứng, độ dài các cạnh chính là độ dài đường đi giữa các thành phố. Trong trường hợp này, tập sẽ là các chu trình Hamilton trên , là độ dài của chu trình, là ràng buộc đòi hỏi chu trình là chu trình Hamilton (qua tất cả các đỉnh, mỗi đỉnh đúng một lần), là tập thành phố được xét 22 LUAN VAN CHAT LUONG download : add [e-mail] (trùng với ), trùng với , tập là vectơ độ dài : với còn là các vectơ trong đó khác đối với mọi cặp. Do đó, lời giải tối ưu của bài toán TSP là một hoán vị của tập đỉnh { } sao cho hàm độ dài là nhỏ nhất, trong đó được tính theo (1.1) ở đây là khoảng cách từ đến.

Bài toán TSP được xem là bài toán chuẩn để kiểm định hiệu quả của các phương pháp giải bài toán TƯTH mới với thư viện dữ liệu chuẩn TSPLIB (Reinelt, 1991) tại địa chỉ [77] (Dữ liệu trong nó sẽ được sử dụng trong luận án này). Bài toán này có nhiều ứng dụng thực tiễn, chẳng hạn như: khoan các lỗ trên bảng mạch in (Reinelt, 1994) hay định vị các thiết bị X-quang (Bland & Shallcross, 1989)… [31]. Bài toán quy hoạch toàn phương nhị phân không ràng buộc Bài toán quy hoạch toàn phương nhị phân không ràng buộc (Unconstrained Binary Quadratic Programming - UBQP) được phát biểu như sau: Cho ma trận là ma trận đối xứng kích thước. Cần tìm vectơ nhị phân gồm thành phần, , trong đó hoặc 1 sao cho hàm đạt giá trị lớn nhất: ∑ ∑ (1.2) Trong bài toán này, tập là tập các vectơ nhị phân độ dài , hàm đã xác định như trên, tập ràng buộc là rỗng.

{ }, trùng với , tập là vectơ độ dài : với , còn trùng với. 23 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Các cách tiếp cận Trên đây cho thấy các bài toán TƯTH có thể đưa về bài toán tìm kiếm trên đồ thị. Các bài toán này có thể giải đúng hoặc gần đúng.

Với những bài toán cỡ nhỏ hoặc có dạng đặc biệt người ta có thể tìm lời giải tối ưu nhờ tìm kiếm vét cạn hoặc bằng một thuật toán với thời gian đa thức, được xây dựng dựa trên các phân tích toán học. Nhiều bài toán trong số đó là NP-khó, nên với các bài toán cỡ lớn, người ta phải tìm lời giải gần đúng. Các thuật toán giải gần đúng các bài toán TƯTH khó thường dựa trên 2 kỹ thuật cơ bản: heuristic cấu trúc (construction heuristic) và tìm kiếm cục bộ (local search). Heuristic cấu trúc Khi không thể tìm được lời giải tối ưu của bài toán, trong thực hành người ta tìm lời giải gần đúng.

Một kỹ thuật hay được dùng là heuristic cấu trúc, trong đó lời giải của bài toán TƯTH được xây dựng theo cách mở rộng tuần tự. Từ thành phần khởi tạo trong tập ở mục 1.1, từng bước mở rộng không quay lui, bằng cách thêm vào các thành phần mới theo phương thức ngẫu nhiên hay tất định dựa trên các quy tắc heuristic đã chọn. Các quy tắc heuristic này thường được xây dựng dựa trên các kết quả phân tích toán học hoặc kinh nghiệm. Phương pháp heuristic cấu trúc tham ăn sau đây cho ta hình dung được cách tiếp cận này (Hình 1.

Procedure Heuristic cấu trúc tham ăn; Begin chọn thành phần trong ; while (chưa xây dựng xong lời giải) do GreedyComponent( ); ; end-while ; Đưa ra lời giải ; End; Hình 1.1: Phương pháp heuristic cấu trúc tham ăn 24 LUAN VAN CHAT LUONG download : add [e-mail] trong đó GreedyComponent( ) có nghĩa là chọn thành phần bổ sung vào theo quy tắc heuristic đã có. Ký hiệu là kết quả phép toán thêm thành phần vào. Dễ dàng hình dung phương pháp này khi áp dụng thuật toán cho bài toán TSP với đồ thị đầy đủ và sử dụng quy tắc heuristic láng giềng gần nhất để chọn đỉnh thêm vào (tức là chọn đỉnh gần nhất chưa đi qua để thêm vào hành trình). Các thuật toán này có ưu điểm là tốn ít thời gian chạy nhưng nhược điểm chính là không cải tiến lời giải được.

Tìm kiếm cục bộ Kỹ thuật tìm kiếm cục bộ hay còn gọi là tìm kiếm địa phương, thực hiện bằng cách bắt đầu từ một phương án chấp nhận được, lặp lại bước cải tiến lời giải nhờ các thay đổi cục bộ. Để thực hiện kỹ thuật này, ta cần xác định được cấu trúc lân cận của mỗi phương án (lời giải) đang xét, tức là những phương án chấp nhận được, gần với nó nhất, nhờ thay đổi một số thành phần. Cách thường dùng là lân cận -thay đổi, tức là lân cận bao gồm các phương án chấp nhận được khác với phương án đang xét nhờ thay đổi nhiều nhất thành phần. Lân cận 2-thay đổi của một lời giải trong bài toán TSP bao gồm tất cả các lời giải có thể nhận được từ bằng cách đổi hai cạnh.2 chỉ ra một ví dụ một lời giải nhận được bằng cách thay hai cạnh (2,3), (1,6) bằng hai cạnh (1,3), (2,6).

Việc cải tiến trong các bước lặp thường chọn theo phương pháp leo đồi dựa theo hai chiến lược: Chiến lược tốt nhất và chiến lược tốt hơn. Với chiến lược tốt nhất, người ta thực hiện chọn lời giải tốt nhất trong lân cận để làm lời giải cải tiến. Tuy nhiên, khi bài toán cỡ lớn có thể không tìm được lời giải tốt nhất do bị hạn chế về thời gian. Còn với chiến lược tốt hơn, ta chọn phương án đầu tiên trong lân cận, cải thiện 25 LUAN VAN CHAT LUONG download : add [e-mail] được hàm mục tiêu.

Nhược điểm của tìm kiếm cục bộ là thường chỉ cho cực trị địa phương.