Thuật toán metaheuristic giải bài toán tập phủ đỉnh.

- 9 CHƢƠNG 1: BÀI TOÁN PHỦ ĐỈNHTRÊN ĐỒ THỊ.
- 10 1.1.1 Cơ sở về bài toán tính toán và thuật toán.
- 12 1.1.3 Các khái niệm về đồ thị.
- 15 1.1.5 Lớp bài toán NP-đầy đủ.
- Bài toán phủ đỉnh nhỏ nhất trên đồ thị.
- Tổng quan về bài toán.
- Các trƣờng hợp giải tốt của bài toán.
- Đồ thị 2 phía.
- Đồ thị nhiều phía.
- Các cách tiếp cận giải bài toán.
- Thuật toán tham lam.
- Thuật toán của Ashay Dharwadker - AD.
- Thuật toán tìm kiếm Tabu - TabuAlg.
- 48 4.1.1 Nhắc lại bài toán.
- 87 Vũ Tiến Khang 3 Lớp CNTT1 - Khoá 2013B LỜI CAM ĐOAN Tôi xin cam đoan: Luận văn "Thuật toán metaheuristic giải bài toán phủ đỉnh" là do bản thân tôi tự thực hiện dƣới sự hƣớng dẫn của PGS.TS Nguyễn Đức Nghĩa - Viện Công nghệ thông tin và Truyền thông - Đại học Bách khoa Hà Nội.
- 715 Vũ Tiến Khang 6 Lớp CNTT1 - Khoá 2013B THUẬT NGỮ TIẾNG ANH STT Tiếng Anh Giải thích 1 Decision Problem Bài toán quyết định 2 Input Đầu vào 3 Output Đầu ra 4 Tile Ô vuông 5 Tabu Search Tìm kiếm có danh sách cấm 6 Minimum Vertex Cover Problem Bài toán phủ đỉnh nhỏ nhất 7 Genetic Algorithm Thuật toán di truyền 8 Hill-climbing Leo đồi 9 Ant Colony Thuật toán đàn kiến Vũ Tiến Khang 7 Lớp CNTT1 - Khoá 2013B DANH MỤC CÁC TỪ VIẾT TẮT STT Từ viết tắt Tên đầy đủ Giải thích 1 DP Decision Problem Bài toán quyết định 2 GA Genetic Algorithm Thuật toán di truyền 3 AC Ant Colony Thuật toán đàn kiến 4 MVCP Minimum Vertex Cover Problem Bài toán phủ đỉnh nhỏ nhất 5 AD Ashay Dharwadker Tên riêng của 1 tác giả ngƣời Ấn Độ 6 NP Non-deterministic Polynomial-time Chƣa giải đƣợc trong thời gian đa thức 7 TabuAlg Tabu Search Algorithm Thuật toán tìm kiếm tabu tôi 8 MetaheuristicAlg Metaheuristic Algorithm Thuật toán metaheuristic của tôi Vũ Tiến Khang 8 Lớp CNTT1 - Khoá 2013B PHẦN MỞ ĐẦU 1.
- Lý do chọn đề tài Bài toán tập phủ đỉnh nhỏ nhất trên đồ thị là bài toán NP-khó trong nhóm các bài toán về đồ thị.
- Bài toán tập phủ đỉnh nhỏ nhất trên đồ thị đƣợc ứng dụng trongnhiều lĩnh vực thực tế nhƣ việc đạt trạm quan sát, ứng dụng trong việc xét nghiệm ung thƣ cổ bằng cách kiểm tra màng tế bào.
- Do tầm quan trọng của bài toán, rất nhiều hƣớng tiếp cận để giải xấp xỉ bài toán đã đƣợc đề xuất với mục đích đƣa ra lời giải xấp xỉ tốt nhất với thời gian chấp nhận đƣợc.
- Các cách tiếp cận truyền thống thƣờng sử dụng một thuật toán nhƣ giải thuật di truyền, giải thuật đàn kiến hay giải thuật tìm kiếm Tabu và đã thu đƣợc kết quả nhất định, trong luận văn này em xin đi theo hƣớng lai ghép các heuristic để tạo thành metaheuristic giải bài toán phủ đỉnh nhỏ nhất.
- Mục tiêu và nhiệm vụ nghiên cứu Với mục đích tạo ra thuật toán Metaheuristic, kết hợp các kỹ thuật và thuật toán khác nhau để xây dựng một thuật toán mới hiệu quả hơn (về thời gian, kết quả), vì vậy luận văn tập trung vào các nội dung chính sau: o Phát biểu bài toán Tập phủ đỉnh nhỏ nhất và các ứng dụng của bài toán.
- o Nghiên cứu các hƣớng tiếp cận giải bài toán phủ đỉnh nhỏ nhất trên đồ thị tổng quát nhƣ giải thuật di truyền, giải thuật của Ashay Dharwadker, giải thuật tìm kiếm Tabu.
- o Cài đặt thuật toán tìm kiếm Tabu, thuật toán di truyền, giải thuật của Ashay Dharwadker và Metaheuristic cùng giải bài toán phủ đỉnh nhỏ nhất, đƣa ra kết quả thực nghiệm để so sánh và đánh giá.
- Bố cục của luận văn Chƣơng 1: Bài toán tập phủ đỉnh nhỏ nhất trên đồ thị.
- Chƣơng này đƣợc chia làm hai phần: phần 1 trình bày các kiến thức cơ sở về thuật toán và bài toán tính toán, về đồ thị và lớp bài toán NP-đầy đủ với mục đích làm nền tảng lý thuyết cho các chƣơng tiếp theo, phần 2 phát biểu bài toán và các ứng dụng thực tế.
- Chƣơng 2: Các cách tiếp cận bài toán.
- Trình bày về các trƣờng hợp giải tốt cũng nhƣ một số phƣơng pháp giải xấp xỉ và các thuật toán độc lập giải bài toán.
- Chƣơng 3: Metaheuristicgiải bài toán phủ đỉnh.
- Vũ Tiến Khang 10 Lớp CNTT1 - Khoá 2013B CHƢƠNG 1: BÀI TOÁN PHỦ ĐỈNHTRÊN ĐỒ THỊ 1.1.
- Một số khái niệm cơ bản Phần này đƣa ra những khái niệm cơ bản về thuật toán, về bài toán, về đồ thị và lớp bài toán NP-đầy đủ nhằm làm cƣ sở lý thuyết cho các chƣơng sau.
- 1.1.1 Khái niệm bài toán tính toán và thuật toán Bài toán tính toán F là ánh xạ từ tập các xâu nhị phân độ dài hữu hạn vào tập các xâu nhị phân độ dài hữu hạn: F:[0,1.
- Khái niệm thuật toán Ta hiểu thuật toán giải bài toán đặt ra là một thủ tục xác định bao gồm một dãy hữu hạn các bƣớc cần thực hiện để thu đƣợc đầu ra cho một đầu vào cho trƣớc của bài toán.
- Đầu ra (Output): Với mỗi tập các dữ liệu đầu vào, thuật toán sẽ đƣa ra các dữ liệu tƣơng ứng với lời giải của bài toán.
- thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho.
- (g(n)) thì thời gian tính tốt nhất của thuật toán có bậc không nhỏ hơn g(n) hay thời gian tính tốt nhất của thuật toán là (g(n.
- Phụ thuộc vào từng bài toán mà các cạnh có thể có hƣớng (cặp (u, v) là có thứ tự) hoặc vô hƣớng (cặp (u, v) không có thứ tự).
- Nhiều vấn đề thực tế có thể khảo sát nhờ sử dụng đồ thị: Bài toán ngƣời du lịch (mỗi thành phố là 1 đỉnh), mạng máy tính, mạng giao thông, trò chơi (mỗi đỉnh=trạng thái của trò chơi.
- Đồ thị có hƣớng G=(V,E) là cặp.
- 1.1.5 Lớp bài toán NP-đầy đủ Bài toán quyết định (Decision Problem –DP) Bài toán quyết định là bài toán mà đầu ra chỉ có thể là “yes” hoặc “no” (0/1, đúng/sai,chấp nhận/từ chối.
- Bài toán quyết định tương ứng với bài toán tối ưu Xét bài toán tối ƣu hóa (P) max{f(x):xD}.
- Ta gọi bài toán dạng quyết định tƣơng ứng với bài toán tối ƣu (P) là bài toán quyết định sau: (PD) “Cho giá trị K.
- Hỏi có tìm được u  D sao cho f(u) K hay không?” Bài toán tối ƣu và bài toán quyết định của nó có mối liên hệ đƣợc phát biểu trong định lý sau: Định lý:Nếu bài toán quyết định tƣơng ứng với một bài toán tối ƣu có thể giải đƣợc hiệu quả (chẳng hạn bằng thuật toán có thời gian tính đa thức) thì bài toán tối ƣu đó cũng giải đƣợc hiệu quả (bằng thuật toán thời gian tính đa thức).
- Ta gọi bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời „yes‟ cho bộ dữ liệu vào „yes‟ của bài toán là một bằng chứng có độ dài bị chặn bởi một đa thức bậc cố định của độ dài dữ liệu đầu vào của bài toán, và việc kiểm tra nó là bằng chứng xác nhận câu trả lời „yes‟ đối với đầu vào đã cho của bài toán có thể thực hiện xong sau thời gian đa thức.
- Lớp bài toán P, NP và co-NP Ta gọi P là lớp các bài toán có thể giải đƣợc sau thời gian đa thức.
- Ta gọi NP là lớp các bài toán quyết định mà để xác nhận câu trả lời “yes” của nó ta có thể đƣa ra bằng chứng ngắn gọn dễ kiểm tra .
- Vũ Tiến Khang 18 Lớp CNTT1 - Khoá 2013B Ta gọi co-NP là lớp các bài toán quyết định mà để xác nhận câu trả lời “no” của nó ta có thể đƣa ra bằng chứng ngắn gọn dễ kiểm tra .
- Qui dẫn Giả sử A và B là hai bài toán quyết định,ta nói bài toán A có thể quy dẫn về bài toán B sau thời gian đa thức nếu tồn tại thuật toán thời gian đa thức R cho phép biến đổi bộ dữ liệu đầu vào x của A thành bộ dữ liệu đầu vào R(x) của B sao cho x là bộ dữ liệu “yes” của A khi và chỉ khi R(x) là bộ dữ liệu “yes” của B.
- Sơ đồ chứng minh quy dẫn Ký hiệu AB dùng để chỉ bài toán A có thể quy dẫn về bài toán B.
- Phép quy dẫn thƣờng dùng để so sánh độ khó của hai bài toán.
- NP-đầy đủ và NP-khó Định nghĩa bài toán NP-đầy đủ: Một bài toán quyết định A đƣợc gọi là NP-đầy đủ nếu nhƣ A là bài toán trong NP và mọi bài toán trong NP đều có thể quy dẫn về A.
- Bổ đề về NP-đầy đủ: Giả sử bài toán A là NP-đầy đủ, bài toán B thuộc lớp NP và bài toán A quy dẫn về B.
- Khi đó bài toán B cũng là NP-đầy đủ Từ đó, một bài toán là NP-đầy đủ sẽ có độ khó không kém gì mọi bài toán trong lớp NP.
- Bổ đề đƣa ra một cách đơn giản để chứng minh một bài toán là NP-đầy đủ nhờ quy dẫn từ một bài toán NP-đầy đủ khác.
- Vấn đề khó khăn ở đây là làm sao tìm đƣợc bài toán NP-đầy đủ xuất phát để có thể quy dẫn về bài toán cần chứng minh.
- Định nghĩa bài toán NP-khó: Một bài toán A đƣợc gọi là NP-khó nếu nhƣ sự tồn tại thuật toán đa thức để giải nó kéo theo sự tồn tại thuật toán đa thức để giải mọi bài toán trong NP.
- Vũ Tiến Khang 19 Lớp CNTT1 - Khoá 2013B Từ định nghĩa NP-khó suy ra rằng mọi bài toán NP-đầy đủ cũng là bài toán NP-khó.Tuy nhiên điều ngƣợc lại thì không phải lúc nào cũng đúng.
- Để chứng minh một bài toán (P) là NP-đầy đủ, ta thực hiện theo sơ đồ: Chứng minh bằng quy dẫn bài toán P là NP-đầy đủ 1 Chứng minh (P) thuộc NP bằng cách đƣa ra một bằng chứng ngắn gọn dễ kiểm tra.
- 2 Chọn bài toán (P‟) là NP-đầy đủ đã biết.
- 3 Mô tả thuật toán tính hàm f biến mọi thể hiện x{0,1}* của bài toán P‟ thành thể hiện f(x) của bài toán P.
- Các bƣớc từ 2-5 nhằm chứng minh bài toán (P) là NP-khó.
- Tổng quan về bài toán Phát biểu bài toán tổng quát Bài toán phủ đỉnh nhỏ nhất (Minimum Vertex CoverProblem - MVCP) đƣợc phát biểu nhƣ sau: Cho đồ thị vô hƣớng G=(V,E), tìm U là tập con với lực lƣợng nhỏ nhất của V sao cho mỗi cạnh trong E đều có ít nhất 1 đầu mút trong U.
- Ví dụ: Với đồ thị sau, tập S nhỏ nhất chỉ gồm 2 đỉnh Vũ Tiến Khang 20 Lớp CNTT1 - Khoá 2013B Tập với 7 đỉnh đƣợc tô màu xanh trong đồ thị Frucht là tập đỉnh nhỏ nhất phủ đồ thị đó nhƣ hình sau: Tổng quan về bài toán.
- Có hai cách phát biểu khác nhau của bài toán phủ đỉnh nhỏ nhất: phát biểu theo dạng bài toán quyết định hoặc phát biểu theo dạng bài toán tối ƣu.
- Theo cách phát biểu dƣới dạng bài toán quyết định, nhiệm vụ cần làm là kiểm tra với một đồ thị cho trƣớc, có tồn tại hay không một tập đỉnh phủ đồ thị theo một kích thƣớc xác định.
- Bài toán phủ đỉnh nhỏ nhất là một trong 21 bài toán NP-đầy đủ đƣợc Karp đƣa ra năm 1972.
- Nó là một trƣờng hợp riêng của bài toán set cover.
- MVCP cũng liên quan tới nhiều bài toán đồ thị khó khác cho nên nó đƣợc nhiều nhà nghiên cứu quan tâm tìm hiểu xây dựng các giải thuật tối ƣu và gần đúng.
- Ví dụ nhƣ bài toán về tập độc lập là tƣơng tự nhƣ bài toán phủ đỉnh bởi vì một tập nhỏ nhất các đỉnh phủ đồ thị cũng tạo nên một tập độc lập lớn nhất và ngƣợc lại.
- Một vấn đề thú vị khác liên quan đến bài toán này đó là bài toán tìm tập cạnh nhỏ nhất sao cho (edge cover), mỗi đỉnh đồ thị là đầu mút của ít nhất một cạnh trong tập đó.
- Tập tìm đƣợc gọi là tập phủ cạnh - Có nhiều thuật giải để giải bài toán phủ đỉnh nhƣ: thuật toán tham lam, thuật toán đánh giá cận dƣới, giải thuật di truyền (GA), bầy kiến hay tìm kiếm Tabu … Các hƣớng tiếp cận đó sẽ đƣợc trình bày trong chƣơng 2.
- Bài toán phủ vị trí thƣờng đƣợc phân làm 2 lớp: Bài toán phủ ủy nhiệm - phủ tất cả các điểm phục vụ với số điều kiện thuận lợi nhỏ nhất vàbài toán phủ lớn nhất - phủ một số lớn nhất các điểm phục vụ với một số nhất định các điều kiện thuận lợi đã có.
- Ở đây ta xét bài toán phủ ủy nhiệm, với ứng dụng trong việc xét nghiệm ung thƣ cổ bằng cách kiểm tra màng tế bào.
- Điều này tƣơng đƣơng với bài toán phân hoạch bè nhỏ nhất trên đồ thị đã xây dựng.
- Vũ Tiến Khang 23 Lớp CNTT1 - Khoá 2013B Ứng dụng cho truyền thông Trong truyền thông việc chọn vị trí đặt trạm phát sóng là rất quan trọng, làm sao cho ít chi phí nhất nhƣng chất lƣợng là tốt nhất, bài toán đặt ra là có một vùng địa hình phức tạp, cần đặt các trạm phát sóng với tầm phát tốt xác định sao cho số lƣợng trạm là ít nhất và mỗi máy thu đều nằm trong phạm vi phát tốt của ít nhất một trạm phát sóng.
- Các trƣờng hợp giải tốt của bài toán Phần này đƣa ra các trƣờng hợp đồ thị đặc biệt, với những trƣờng hợp này chúng ta có những thuật toán chạy đúng trong thời gian đa thức.
- Cây Trƣờng hợp đồ thị G là cây ta có thuật toán đa thức sau đây để giải bài toán: Ký hiệu: C: là tập đỉnh dùng để lƣu tập phủ đỉnh nhỏ nhất.
- Các cách tiếp cận giải bài toán Phần này chúng ta đề cập tới các phƣơng pháp giải gần đúng áp dụng cho bài toán phủ đỉnh nhỏ nhất, các phƣơng pháp này ít nhiều đã từng đƣợc sử dụng và đã chứng minh đƣợc hiệu quả của mình.
- Thuật toán tham lam Thuật toán tham lam là thuật toán giải quyết vấn đề dựa trên yêu cầu của bài toán bằng cách lựa chọn giải pháp tốt nhất trong mỗi trạng thái với hy vọng tạo ra kết quả tốt.
- Với bài toán phủ đỉnh nhỏ nhất chúng ta có thuật toán tham lam giải quyết vấn đề nhƣ sau: B1: Tìm đỉnh v trong tập đỉnh là đầu mút của nhiều cạnh nhất (bậc cao nhất).
- Vũ Tiến Khang 26 Lớp CNTT1 - Khoá 2013B Thuật toán này có vẻ nhƣ là thuật toán heuristic đơn giản nhất để giải quyết bài toán phủ đỉnh nhỏ nhất, tuy nhiên thuật toán này thƣờng sẽ không cho ta kết quả tối ƣu.
- Thuật toán di truyền Genetic Algorithm – GA Giải thuật GA là giải thuật phát triển dựa trên sơ đồ giải thuật di truyền sử dụng phép lai ghép các cha mẹ để giải quyết bài toán phủ đỉnh nhỏ nhất.
- Các chuỗi ban đầu Mặt nạ lai ghép Các cá thể con Lai ghép điểm đơn: Vũ Tiến Khang 29 Lớp CNTT1 - Khoá 2013B 2.2.2.5 Xử lý ràng buộc GA thích hợp cho các bài toán tìm kiếm tối ƣu với điều kiện không ràng buộc.
- Tuy nhiên thực tế bài toán có thể chứa một hoặc nhiều ràng buộc phải thỏa.
- Trong bài toán phủ đỉnh nhỏ nhất, điều kiện ràng buộc là cá thể đó phải phủ đƣợc hết đồ thị.
- Đƣa ra lời giải Áp dụng thuật toán đàn kiến giải bài toán phủ đỉnh nhỏ nhất 2.2.3.1 Xây dựng hàm kết nối nhị phân C[n,n] Gọi Gc=(V,Ec) là đồ thị đầy đủ sinh bởi tập đỉnh V của đồ thị đã cho Định nghĩa.
- Bài toán sẽ chuyển về: xác định chuỗi nhị phân 0 và 1 độ dài n sao cho số giá trị 1 là nhỏ nhất và thỏa mãn điều kiện phủ đỉnh (ở đây là mỗi cạnh của E đều có ít nhất 1 đầu mút trong U) Việc mã hóa lời giải sẽ giúp thực hiện bƣớc chuyển 1 cách linh hoạt.
- V thỏa mãn điểu kiện phủ đỉnh của bài toán Ví dụ cho lân cận “ngang.
- 3.1.1 Tổng quan về heuristic Đối với nhiều bài toán, hoặc không có lời giải, hoặc độ phức tạp tính toán là hàm mũ, hoặc là bài toán NP-đầy đủ…, có nghĩa là nó không có lời giải khả thi, thì thông thƣờng thay vì tìm lời giải tối ƣu cho chúng, chúng ta cố gắng tìm lời giải có thể chấp nhận đƣợc, đáp ứng đƣợc yêu cầu của thực tế.
- Các thuật toán tìm kiếm luôn luôn đóng vai trò quan trọng trong việc giải các bài toán tin học.
- Các thuật toán loại này rất phong phú, có thể kể đến nhƣ: vét cạn, đệ quy quay lui, nhánh cận, nhị phân…Tuy nhiên, khi gặp những bài toán có không gian tìm kiếm lớn (đặc biệt trong các trò chơi cờ) thì các thuật toán tìm kiếm thông thƣờng không cho kết quả hoặc kết quả không tối ƣu (do những hạn chế về thời gian và bộ nhớ).
- Một hƣớng tiếp cận độc đáo có thể đáp ứng đƣợc đòi hỏi cho nhiều bài toán loại này là dùng thuật toán Heuristic.
- Thuật ngữ Heuristic đƣợc Feigenbaum Feldman định nghĩa nhƣ sau: ″Heuristic là các quy tắc, phƣơng pháp, chiến lƣợc, mẹo giải hay phƣơng cách nào đó nhằm làm giảm khối lƣợng tìm kiếm lời giải trong không gian bài toán cực lớn″.
- Giải bài toán theo thuật giải Heuristic thƣờng dễ dàng và nhanh chóng đƣa ra kết quả hơn so với giải thuật tối ƣu, vì vậy chi phí thấp hơn.
- Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thƣờng tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.
- Ðó là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bƣớc giải.
- Mặc dù đây là giải thuật đơn giản nhƣng lại nó lại rất mạnh và hiệu quả trong việc giải quyết các bài toán CSP lớn.
- Nếu số lần lặp đủ lớn thì ta có thể tìm đƣợc đỉnh tối ƣu toàn cục, tuy nhiên với những bài toán có không gian tìm kiếm khổng lồ (chẳng hạn nhƣ bài toán xếp lịch) ta không thể đƣa ra số lần lặp đủ lớn để đảm bảo tìm đƣợc lời giải tối ƣu.
- Nhận xét: Hiệu quả của thuật toán leo đồi phụ thuộc rất nhiều vào “bề mặt” của không gian tìm kiếm bài toán.
- Nếu bài toán chỉ có vài đỉnh tối ƣu cục bộ thì giải thuật sẽ tìm ra lời giải tối ƣu rất nhanh, tuy nhiên trong trƣờng hợp bề mặt không gian tìm kiếm lại quá lồi lõm (rất nhiều đỉnh tối ƣu cục bộ), giải thuật sẽ bị luẩn quẩn trong vùng tối ƣu cục bộ và có thể không tìm ra đƣợc lời giải tối ƣu của bài toán.
- Cài đặt chƣơng trình 4.1.1 Nhắc lại bài toán Bài toán phủ đỉnh nhỏ nhất (MVCP) đƣợc phát biểu nhƣ sau: Cho đồ thị G=(V,E), cần tìm tập con U của tập đỉnh V với lực lƣợng nhỏ nhất sao cho mỗi cạnh của đồ thị đều có ít nhất 1 đầu mút trong U

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt