Luận văn thạc sĩ: Thuật toán di truyền GA và ứng dụng giải bài toán NP

Tìm hiểu cơ sở lý thuyết thuật toán di truyền và ứng dụng giải quyết bài toán NP. Nghiên cứu chi tiết nguyên lý, cơ chế tiến hóa, và phương pháp tối ưu hóa.

• Tác giả: Nguyễn Thị Duyên
• Người hướng dẫn: TS. Vũ Vinh Quang
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông
• Chuyên ngành: Khoa học máy tính
• Đề tài: Cơ sở của thuật toán di truyền và ứng dụng đối với một số bài toán lớp NP
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan về thuật toán di truyền và bài toán lớp NP

Thuật toán di truyền (Genetic Algorithm - GA) là phương pháp tối ưu hóa lấy cảm hứng từ quá trình tiến hóa tự nhiên. Thuật toán hoạt động dựa trên cơ chế chọn lọc tự nhiên, lai ghép và đột biến. Quần thể gồm các cá thể biểu diễn nghiệm tiềm năng. Mỗi cá thể được đánh giá qua hàm độ thích nghi. Qua nhiều thế hệ, quần thể tiến hóa về phía nghiệm tối ưu. Bài toán lớp NP là nhóm bài toán khó trong khoa học máy tính. Thời gian giải các bài toán này tăng theo hàm mũ với kích thước đầu vào. Không tồn tại thuật toán giải chính xác trong thời gian đa thức. Các ví dụ điển hình gồm bài toán người bán hàng, bài toán xếp lịch, bài toán ba lô. Thuật toán di truyền cung cấp hướng tiếp cận xấp xỉ hiệu quả. Phương pháp này không đảm bảo nghiệm tối toàn cục. Tuy nhiên, GA thường cho nghiệm tốt trong thời gian chấp nhận được.

1.1. Khái niệm và nguyên lý hoạt động của thuật toán di truyền

Thuật toán di truyền mô phỏng quá trình tiến hóa sinh học. Quần thể ban đầu được tạo ngẫu nhiên. Mỗi cá thể biểu diễn một lời giải tiềm năng dưới dạng chuỗi gen. Hàm độ thích nghi đánh giá chất lượng từng cá thể. Quá trình chọn lọc ưu tiên cá thể có độ thích nghi cao. Toán tử lai ghép kết hợp gen từ hai cá thể cha mẹ. Toán tử đột biến tạo biến đổi ngẫu nhiên nhằm đa dạng hóa quần thể. Các phép toán này lặp lại qua nhiều thế hệ. Dân số hội tụ dần về các nghiệm gần tối ưu. Nguyên lý Darwin 'thích hợp nhất tồn tại' là nền tảng cốt lõi.

1.2. Bài toán lớp NP và tính chất tính toán phức tạp

Lớp NP gồm các bài toán có thể kiểm tra nghiệm đúng trong thời gian đa thức. Bài toán NP-đầy đủ là khó nhất trong lớp NP. Nếu giải được một bài toán NP-đầy đủ, mọi bài toán NP khác đều giải được. Ví dụ phổ biến gồm bài toán ba lô, bài toán xếp thời khóa biểu, bài toán đồ thị lớn nhất. Không có thuật toán chính xác đa thức thời gian nào được chứng minh tồn tại. Do đó, các phương pháp xấp xỉ như thuật toán di truyền được nghiên cứu rộng rãi. Chúng cung cấp nghiệm gần tối ưu trong thời gian tính toán khả thi.

II. Phân tích các thành phần và toán tử của thuật toán di truyền

Thuật toán di truyền gồm nhiều thành phần cấu thành quan trọng. Biểu diễn cá thể là bước đầu tiên quyết định cách mã hóa lời giải. Với bài toán tổ hợp, cá thể thường được mã dưới dạng véc-tor nhị phân hoặc số nguyên. Hàm độ thích nghi đánh giá mức độ phù hợp của cá thể với bài toán. Hàm này phải phản ánh đúng mục tiêu tối ưu hóa. Toán tử chọn lọc quyết định cá thể nào được truyền gen sang thế hệ sau. Phương pháp phổ biến gồm chọn bánh xe, chọn xếp hạng, chọn giải đấu. Toán tử lai ghép kết hợp gen từ hai cá thể cha mẹ tạo cá thể con. Các kiểu lai ghép gồm lai một điểm, lai đa điểm, lai mặt nạ, lai số học. Toán tử đột biến thay đổi ngẫu nhiên một số gen nhằm tránh hội tụ sớm. Xác suất đột biến thường đặt ở mức nhỏ từ 0.01 đến 0.1. Các tham số này ảnh hưởng lớn đến chất lượng nghiệm cuối cùng. Việc cân bằng giữa khai thác và khám phá là yếu tố then chốt.

2.1. Các phương pháp biểu diễn và khởi tạo quần thể

Biểu diễn cá thể quyết định không gian tìm kiếm của thuật toán. Biểu diễn nhị phân phù hợp với bài toán tổ hợp rời rạc. Mỗi bit trong chuỗi đại diện cho một quyết định chọn hoặc không chọn. Biểu diễn số nguyên sử dụng cho bài toán xếp lịch hoặc hoán vị. Biểu diễn thực số áp dụng cho bài toán tối ưu hàm liên tục. Quần thể ban đầu thường được tạo ngẫu nhiên để đảm bảo tính đa dạng. Kích thước quần thể ảnh hưởng đến tốc độ hội tụ và chất lượng nghiệm. Quần thể quá nhỏ dẫn đến hội tụ sớm. Quần thể quá lớn làm tăng thời gian tính toán.

2.2. Các toán tử lai ghép và đột biến chi tiết

Toán tử lai ghép một điểm cắt chuỗi gen tại vị trí ngẫu nhiên. Lai ghép đa điểm cắt tại nhiều vị trí tạo sự đa dạng hơn. Lai ghép mặt nạ chọn ngẫu nhiên các vị trí để hoán đổi gen. Lai số học tính tổ hợp tuyến tính của gen cha mẹ với hệ số a. Lai ghép heuristic tạo cá thể con theo hướng cải thiện từ cá thể tốt hơn. Lai ghép BLX-alpha tạo giá trị con trong khoảng mở rộng quanh giá trị cha mẹ. Toán tử đột biến đảo bit hoặc thay đổi giá trị gen ngẫu nhiên. Xác suất đột biến thấp giúp duy trì tính ổn định của quần thể. Kết hợp đúng các toán tử này là yếu tố quyết định hiệu quả thuật toán.

III. Ứng dụng thuật toán di truyền giải bài toán lớp NP cụ thể

Luận văn áp dụng thuật toán di truyền cho bài toán xếp lịch hướng dẫn thực hành. Bài toán này thuộc lớp NP vì số cách xếp lịch tăng theo hàm mũ. Mỗi giáo viên có chuyên môn phù hợp với một số phòng thực hành. Mỗi giáo viên có thời gian sẵn sàng tại các buổi khác nhau. Mục tiêu là xếp giáo viên vào phòng và buổi sao cho thỏa mãn mọi ràng buộc. Biểu diễn cá thể sử dụng ma trận X kích thước N×m. Mỗi phần tử trong ma trận biểu diễn một quyết định phân công. Hàm độ thích nghi tính tổng số ràng buộc được thỏa mãn. Thuật toán tiến hóa qua nhiều thế hệ cho đến khi hội tụ. Kết quả thực nghiệm trên bộ dữ liệu 10 giáo viên, 5 phòng, 7 buổi cho kết quả khả quan. Thuật toán tìm được nghiệm thỏa mãn tất cả ràng buộc trong thời gian ngắn. So với phương pháp duyệt vét cạn, GA giảm đáng kể thời gian tính toán. Chất lượng nghiệm phụ thuộc vào thiết lập tham số ban đầu.

3.1. Mô hình hóa bài toán xếp lịch hướng dẫn thực hành

Bài toán xếp lịch được xây dựng dưới dạng tối ưu tổ hợp có ràng buộc. Ràng buộc thứ nhất là giáo viên phải có chuyên môn phù hợp với phòng. Ràng buộc thứ hai là giáo viên phải sẵn sàng tại buổi được phân công. Ràng buộc thứ ba là mỗi phòng chỉ có một giáo viên tại mỗi buổi. Hàm mục tiêu tối đa hóa số ràng buộc được thỏa mãn đồng thời. Ma trận phù hợp chuyên môn là đầu vào quan trọng. Ma trận sẵn sàng xác định tính khả thi của phân công. Bài toán trở thành tìm ma trận phân công tối ưu thỏa mãn mọi ràng buộc.

3.2. Thiết kế thuật toán và kết quả thực nghiệm

Thuật toán được thiết kế với các bước cụ thể. Bước một tạo quần thể ban đầu ngẫu nhiên gồm N cá thể. Bước hai lai ghép tất cả các cặp cá thể để sinh cá thể con. Bước ba đánh giá độ thích nghi toàn bộ cá thể. Bước bốn chọn N cá thể tốt nhất cho thế hệ tiếp theo. Bước năm thực hiện đột biến với xác suất 0.05. Quá trình lặp lại cho đến khi đạt số thế hệ tối đa. Thuật toán được lập trình trong môi trường Matlab. Kết quả trên bộ dữ liệu thử nghiệm cho thấy thuật toán hội tụ nhanh. Nghiệm tìm được thỏa mãn toàn bộ ràng buộc của bài toán.

IV. Kết luận và hướng phát triển ứng dụng thuật toán di truyền

Luận văn đã xây dựng cơ sở lý thuyết vững chắc về thuật toán di truyền. Các thành phần chính gồm biểu diễn, chọn lọc, lai ghép, đột biến được phân tích chi tiết. Nhiều kiểu toán tử lai ghép khác nhau đã được trình bày và so sánh. Ứng dụng cho bài toán xếp lịch hướng dẫn thực hành đạt kết quả khả quan. Thuật toán tìm được nghiệm thỏa mãn trong thời gian tính toán hợp lý. Phương pháp này có khả năng mở rộng cho các bài toán NP lớn hơn. Các biến thể như thuật toán di truyền đa mục tiêu có thể được nghiên cứu thêm. Kết hợp GA với các phương pháp local search cải thiện chất lượng nghiệm. Việc điều chỉnh tham số tự động giúp thuật toán thích nghi tốt hơn. Nghiên cứu trong tương lai có thể tập trung vào song song hóa thuật toán. Ứng dụng thực tiễn trong giáo dục, logistics, sản xuất rất tiềm năng. Thuật toán di truyền vẫn là công cụ mạnh mẽ cho bài toán tối ưu tổ hợp.

4.1. Đánh giá ưu nhược điểm của phương pháp đề xuất

Ưu điểm lớn nhất là khả năng tìm nghiệm gần tối ưu trong thời gian ngắn. Thuật toán không yêu cầu thông tin đạo hàm của hàm mục tiêu. GA hoạt động tốt trên không gian tìm kiếm rời rạc và phức tạp. Phương pháp dễ song song hóa trên nhiều bộ xử lý. Nhược điểm là không đảm bảo nghiệm tối toàn cục. Kết quả phụ thuộc vào lựa chọn tham số ban đầu. Hội tụ sớm có thể xảy ra nếu quần thể mất tính đa dạng. Thời gian tính toán tăng khi kích thước bài toán lớn. Cần cân nhắc kỹ giữa chất lượng nghiệm và thời gian giải.

4.2. Hướng phát triển và mở rộng nghiên cứu

Một hướng phát triển là kết hợp GA với phương pháp tìm kiếm cục bộ. Thuật toán lai này cải thiện khả năng khai thác nghiệm tốt. Hướng khác là áp dụng GA cho bài toán đa mục tiêu thực tế. Bài toán xếp lịch thực tế có nhiều mục tiêu xung đột cần được cân bằng. Song song hóa thuật toán giúp giảm thời gian tính toán đáng kể. Nghiên cứu cơ chế thích nghi tham số tự động trong quá trình chạy. Mở rộng ứng dụng sang các bài toán NP khác như bài toán ba lô, bài toán TSP. Tích hợp trí tuệ nhân tạo để học chiến lược tiến hóa hiệu quả hơn.

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

chương 1 trình bày một số khái niệm về giải thuật di truyền, mô hình thiết kế giải thuât, các toán tử trong GA. Thuật toán di truyền mã hóa số thực. Các kết quả được tham khảo trong các tài liệu [2, 3, 4, 5, 6, 7, 8] 1.1 Giới thiệu về GA Giải thuật di truyền GA(GENETIC ALGORITHM) do D. Goldberg đề xuất, sau đó được L.

Michalevicz phát triển là kỹ thuật phỏng theo quá trình thích nghi tiến hóa của các quần thể sinh học dựa trên học thuyết Darwin, đây cũng chính là một trong các thuật toán tiến hóa. Thuật toán tiến hóa là các chương trình máy tính có dùng các thuật toán tìm kiếm, tối ưu hóa dựa trên nguyên lý tiến hóa tự nhiên. GA là phương pháp tìm kiếm tối ưu ngẫu nhiên bằng cách mô phỏng theo sự tiến hóa của con người hay của sinh vật. Tư tưởng của thuật toán di truyền là mô phỏng các hiện tượng tự nhiên, là kế thừa và đấu tranh sinh tồn.

GA thuộc lớp các giải thuật xuất sắc nhưng lại rất khác các giải thuật ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên. Khác biệt quan trọng giữa tìm kiếm của GA và các phương pháp tìm kiếm khác là GA duy trì và xử lý một tập các lời giải, gọi là một quần thể (population). Trong GA, việc tìm kiếm giả thuyết thích hợp được bắt đầu với một quần thể, hay một tập hợp có chọn lọc ban đầu của các giả thuyết. Các cá thể của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt động lai ghép và đột biến ngẫu nhiên – được lấy mẫu sau các quá trình tiến hóa sinh học.

Ở mỗi bước, các giả thuyết trong quần thể hiện tại được ước lượng liên hệ với đại lượng thích nghi, với các giả thuyết phù hợp nhất được chọn theo xác suất là các hạt giống cho việc sản sinh thế hệ kế tiếp, gọi là cá thể (individual). Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại và ngược lại sẽ bị đào thải. GA có thể dò tìm thế hệ mới có độ thích nghi tốt hơn. GA giải quyết các bài toán quy hoạch toán học thông qua các quá trình cơ bản: lai tạo (crossover), đột biến (mutation) và chọn lọc Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn (selection) cho các cá thể trong quần thể.

Dùng GA đòi hỏi phải xác định được: khởi tạo quần thể ban đầu, hàm đánh giá các lời giải theo mức độ thích nghi – hàm mục tiêu, các toán tử di truyền tạo hàm sinh sản. Trong công nghệ thông tin, GA là một thành phần của Tính toán tiến hóa (Evolutionary computation – EC), một lĩnh vực được coi là có tốc độ phát triển nhanh của trí tuệ nhân tạo. Có thể chia EC thành 5 hướng nghiên cứu như sau : - GA (Genetic Algorithm - GA): Dựa vào quá trình di truyền trong tự nhiên để cải tiến lời giải qua các thế hệ bắt nguồn từ một tập các lời giải ban đầu. - Quy hoạch tiến hoá (Evolutionary Programming - EP): Dựa vào quy luật tiến hoá, tìm phương pháp kết hợp đủ khả năng giải quyết trọn vẹn một bài toán từ một lớp các phương pháp giải quyết được một số phần của bài toán.

- Các chiến lược tiến hoá (Evolutionary Strategies - ES): Dựa trên một số chiến lược ban đầu, tiến hoá để tạo ra những chiến lược mới phù hợp với môi trường thực tế một cách tốt nhất. - Lập trình di truyền (Genetic Programming - GP): Mở rộng GA trong lĩnh vực các chương trình của máy tính. Mục đích của nó là để sinh ra một cách tự động các chương trình máy tính giải quyết một cách tối ưu một vấn đề cụ thể. - Các hệ thống phân loại (Classifier Systems- CS): Các GA đặc biệt được dùng trong việc học máy và việc phát hiện các quy tắc trong các hệ dựa trên các quy tắc.

GA cũng như các thuật toán tiến hoá đều được hình thành dựa trên một quan niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm "Quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu". Quá trình tiến hoá thể hiện tính tối ưu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước. Sự hình thành và phát triển của GA trên thế giới có thể được điểm qua các mốc thời gian quan trọng như sau: Năm 1960, ý tưởng đầu tiên về Tính toán tiến hoá được Rechenberg giới thiệu trong công trình “Evolution Strategies” (Các chiến lược tiến hoá).

Ý Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn tưởng này sau đó được nhiều nhà nghiên cứu phát triển. Năm 1975, Giải thuật gen do John Holland phát minh và được phát triển bởi ông cùng với các đồng nghiệp và những sinh viên. Cuốn sách "Adaption in Natural and Artificial Systems" (Sự thích nghi trong các hệ tự nhiên và nhân tạo) đã tổng hợp các kết quả của quá trình nghiên cứu và phát triển đó. Năm 1992, John Koza đã dùng GA để xây dựng các chương trình giải quyết một số bài toán và gọi phương pháp này là “lập trình gen”.

Ngày nay GA càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu hoá, một lĩnh vực có nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng thường khó và chưa có giải thuật hiệu quả để giải .2 Các khái niệm cơ bản 1.1 Cá thể, nhiễm sắc thể Trong GA, một cá thể biểu diễn một phương án của bài toán. Trong trường hợp tổng quát, một cá thể có nhiều Nhiễm sắc thể(NST), ở đây ta quan niệm một cá thể chỉ có một NST. Do đó khái niệm cá thể và NST trong GA coi như là tương đương. Một NST được tạo thành từ nhiều gen, mỗi gen có thể có các giá trị khác nhau để quy định một tính trạng nào đó.

Trong GA, một gen được coi như một phần tử trong chuỗi NST.2 Quần thể Quần thể là một tập hợp các cá thể có cùng một số đặc điểm nào đấy. Trong GA ta quan niệm quần thể là một tập các lời giải của một bài toán.3 Chọn lọc (Selection) Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay đổi các cá thể trong quần thể. Những cá thể tốt, thích nghi được với điều kiện sống thì có khả năng đấu tranh lớn hơn, do đó có thể tồn tại và sinh sản. Các cá thể không thích nghi được với điều kiện sống thì dần mất đi.

Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh sinh tồn trong tự nhiên, chọn lựa các cá thể trong GA chính là cách chọn các cá thể có độ thích nghi tốt để đưa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục đích là sinh ra các cá thể mới tốt hơn. Có nhiều cách để lựa chọn nhưng cuối cùng đều nhằm đáp ứng mục tiêu là các cá thể tốt sẽ có khả năng được chọn cao hơn. Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.4 Lai ghép (Cross-over) Lai ghép trong tự nhiên là sự kết hợp các tính trạng của bố mẹ để sinh ra thế hệ con. Trong GA, lai ghép được coi là một sự tổ hợp lại các tính chất (thành phần) trong hai lời giải cha mẹ nào đó để sinh ra một lời giải mới mà có đặc tính mong muốn là tốt hơn thế hệ cha mẹ.

Đây là một quá trình xảy ra chủ yếu trong GA.5 Đột biến (Mutation) Đột biến là một sự biến đổi tại một (hay một số) gen của NST ban đầu để tạo ra một NST mới. Đột biến có xác suất xảy ra thấp hơn lai ghép. Đột biến có thể tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban đầu. Tuy nhiên trong GA thì ta luôn muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua từng thế hệ.3 Mô hình GA Với các khái niệm được giới thiệu ở trên, GA được mô tả bởi sơ đồ sau đây Bắt đầu Nhận các tham số của bài toán Khởi tạo quần thể ban đầu Tính giá trị thích nghi Điều kiện dừng Sinh sản Lai ghép Lựa chọn giải pháp tốt nhất Đột biến Kết thúc Hình 1.1: Sơ đồ mô tả GA Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn Như vậy giải thuật GA được xây dựng qua các bước cơ bản sau đây: 1.

Xác lập các tham số ban đầu của bài toán. Khởi tạo: Sinh ngẫu nhiên một quần thể gồm n cá thể (là n lời giải ban đầu của bài toán). Xác lập quần thể mới: tạo quần thể mới bằng cách lặp lại các bước sau cho đến khi quần thể mới hoàn thành, bao gồm: 3.1 Tính độ thích nghi của mỗi cá thể.2 Kiểm tra điều kiện kết thúc giải thuật.3 Chọn lọc các cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn).4 Tiến hành lai ghép các cặp bố-mẹ với một xác suất lai ghép được chọn để tạo ra một cá thể mới.5 Tiến hành đột biến với xác suất đột biến được chọn xác định cá thể đột biến. Kiểm tra điều kiện dừng: Nếu điều kiện được thỏa mãn thì thuật toán kết thúc và trả về lời giải tốt nhất chính là quần thể hiện tại.4 Các tham số của GA 1.1 Kích thước quần thể Kích thước quần thể cho biết có bao nhiêu cá thể trong một quần thể (trong một thế hệ).

Qua các nghiên cứu cũng như các thử nghiệm đã cho thấy kích thước quần thể không nên quá bé cũng như không quá lớn. Nếu có quá ít cá thể thì ít có khả năng thực hiện lai giống và chỉ một phần nhỏ không gian tìm kiếm được dùng. Như vậy sẽ dễ xảy ra trường hợp bỏ qua các lời giải tốt. Nhưng quá nhiều cá thể cũng không tốt vì GA sẽ chạy chậm đi, ảnh hưởng đến hiệu quả của giải thuật.

Các nghiên cứu cũng đã chỉ ra không có lợi khi tăng kích thước quần thể lên quá một giới hạn cho phép.2 Xác suất lai ghép Xác suất lai ghép cho biết việc lai ghép tạo ra thế hệ mới được thực hiện Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn thường xuyên như thế nào. Nếu xác suất lai ghép là pc, khi đó khả năng để một cá thể được lai ghép là pc. Nếu không thực hiện lai ghép, con sinh ra sẽ giống hoàn toàn bố mẹ. Nếu được lai ghép, con sinh ra sẽ có một phần giống bố và một phần giống mẹ.