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á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

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ DUYÊN 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 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. VŨ VINH QUANG THÁI NGUYÊN, 2020 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ DUYÊN 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 Chuyên ngành: Khoa học máy tính Mã số: 8 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. VŨ VINH QUANG THÁI NGUYÊN, 2020 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn LỜI CAM ĐOAN Sau quá trình học tập tại Trường Đại học công nghệ thông tin & truyền thông, với những kiến thức lý thuyết và thực hành đã tích lũy được, với việc vận dụng các kiến thức vào thực tế, em đã tự nghiên cứu các tài liệu, các công trình nghiên cứu, đồng thời có sự phân tích, tổng hợp, đúc kết và phát triển để hoàn thành luận văn thạc sĩ của mình. Em xin cam đoan luận văn này là công trình do bản thân em tự tìm hiểu, nghiên cứu và hoàn thành dưới sự hướng dẫn của thầy giáo TS. Thái Nguyên, tháng 7 năm 2020 Sinh viên Nguyễn Thị Duyên Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn LỜI CẢM ƠN Trong thời gian hai năm của chương trình đào tạo thạc sỹ, trong đó gần một nửa thời gian dành cho các môn học, thời gian còn lại dành cho việc lựa chọn đề tài, giáo viên hướng dẫn, tập trung vào nghiên cứu, viết, chỉnh sửa và hoàn thiện đề tài. Với quỹ thời gian như vậy và với vị trí công việc đang phải đảm nhận, không riêng bản thân em mà hầu hết các sinh viên cao học muốn hoàn thành tốt luận văn của mình trước hết đều phải có sự sắp xếp thời gian hợp lý, có sự tập trung học tập và nghiên cứu với tinh thần nghiêm túc, nỗ lực hết mình; tiếp đến cần có sự ủng hộ về tinh thần, sự giúp đỡ về chuyên môn một trong những điều kiện không thể thiếu quyết định đến việc thành công của đề tài. Để hoàn thành được đề tài này trước tiên em xin gửi lời cảm ơn đến thầy giáo hướng dẫn TS. Vũ Vinh Quang, người đã có những định hướng cho em về nội dung và hướng phát triển của đề tài, người đã có những đóng góp quý báu cho em về những vấn đề chuyên môn của đề tài, giúp em tháo gỡ kịp thời những vướng mắc trong quá trình làm luận văn. Em cũng xin cám ơn các thầy cô giáo Trường Đại học Công nghệ thông tin và Truyền thông cũng như bạn bè cùng lớp đã có những ý kiến đóng góp bổ sung cho đề tài luận văn của em. Xin cảm ơn gia đình, người thân cũng như đồng nghiệp luôn quan tâm, ủng hộ hỗ trợ về mặt tinh thần trong suốt thời gian từ khi nhận đề tài đến khi hoàn thiện đề tài này. Em xin hứa sẽ cố gắng hơn nữa, tự trau dồi bản thân, tích cực nâng cao năng lực chuyên môn của mình để sau khi hoàn thành đề tài này sẽ có hướng tập trung nghiên cứu sâu hơn, không ngừng hoàn thiện hơn nữa đề tài của mình để có những ứng dụng thực tiễn cao trong thực tế. Thái Nguyên, tháng 7 năm 2020 Sinh viên Nguyễn Thị Duyên Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn MỤC LỤC LỜI CAM ĐOAN.ii DANH MỤC CÁC BẢNG.vii DANH MỤC CÁC HÌNH.viii LỜI MỞ ĐẦU. 1 CHƯƠNG 1 GIẢI THUẬT DI TRUYỀN.1 Giới thiệu về GA.2 Các khái niệm cơ bản.1 Cá thể, nhiễm sắc thể.3 Mô hình GA.4 Các tham số của GA.1 Kích thước quần thể.2 Xác suất lai ghép.3 Xác suất đột biến.5 Cơ chế thực hiện GA.2 Khởi tạo quần thể ban đầu.3 Xác định hàm thích nghi.4 Cơ chế lựa chọn.5 Các toán tử di truyền. Thuật toán di truyền kinh điển. 12 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc. Toán tử lai ghép. Toán tử đột biến. Thuật toán di truyền mã hóa số thực (RCGA). 15 CHƯƠNG 2 LỚP BÀI TOÁN NP VÀ MỘT SỐ MÔ HÌNH.1 Khái niệm về thuật toán và độ phức tạp thuật toán.1 Khái niệm về thuật toán. Các yêu cầu của thuật toán. Độ phức tạp của thuật toán. Chi phí phải trả cho một quá trình tính toán. Độ phức tạp của thuật toán. Các qui tắc xác định độ phức tạp thuật toán. Vấn đề phân lớp các bài toán dựa trên độ phức tạp thuật toán. Lớp bài toán P.4 Một số mô hình bài toán lớp NP.1 Mô hình bài toán KNAPSACK.2 Bài toán quân cờ Domino.3 Mô hình bài toán TSP. 33 CHƯƠNG 3: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN LẬP LỊCH GIẢNG DẠY THỰC HÀNH.1 Mô hình bài toán thực tế.2 Thiết kế giải thuật di truyền GA.1 Xây dựng cấu trúc cá thể, các hàm kiểm tra.2 Xây dựng các toán tử trong GA.3 Các kết quả thực nghiệm.1 Bộ số liệu Test 1.2 Bộ số liệu Test 2. 42 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn KẾT LUẬN. 46 TÀI LIỆU THAM KHẢO. 47 PHẦN PHỤ LỤC. 48 NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN. 60 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT GA – Genetic Algorithm: giải thuật di truyền TSP - Travelling Salesman Problems: bài toán người du lịch EC - Evolutionary computation: tính toán tiến hóa EP - Evolutionary Programming: quy hoạch tiến hóa ES - Evolutionary Strategies: các chiến lược tiến hóa GP - Genetic Programming: lập trình di truyền CS - Classifier Systems: các hệ thống phân loại NST – nhiễm sắc thể Selection: chọn lọc Cross-over: lai ghép Mutation: đột biến Reproduction: sinh sản pop-size: kích cỡ quần thể RCGA: thuật toán di truyền mã hóa số thực BLX-α - Blend Crossover: lai ghép BLX-α CMX - Center of Mass Crossover: lai ghép CMX NP-hard: bài toán NP khó NP-complete: bài toán NP đầy đủ Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn DANH MỤC CÁC BẢNG Bảng 2.1: Bảng giá trị độ phức tạp tính toán của các hàm số.1: Giáo viên phù hợp chuyên môn với phòng thực hành.2: Giáo viên sẵn sàng nhận buổi hướng dẫn.3: Lịch giảng dạy Test 1.4: Số buổi giảng dạy đối với các giáo viên Test 1.5: Lịch giảng dạy Test 1.6: Số buổi giảng dạy đối với các giáo viên.7 Lịch giảng dạy.8 Số buổi giảng dạy đối với các giáo viên.9: Bảng các giáo viên phù hợp chuyên môn với phòng thực hành.10: Bảng các giáo viên sẵn sàng nhận buổi hướng dẫn.11: Lịch giảng dạy Test 2.12: Số buổi giảng dạy đối với các giáo viên Test 2.13: Lịch giảng dạy.14: Số buổi giảng dạy đối với các giáo viên.15: Lịch giảng dạy. 45 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn DANH MỤC CÁC HÌNH Hình 1.1: Sơ đồ mô tả GA.2: Lai ghép CMX.3: Phân bố của x cj i.4: Toán tử lai ghép SX.1: Các lớp P, NP và NPC. 26 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn LỜI MỞ ĐẦU Trong thực tế, việc tìm kiếm các phương pháp giải lớp các bài toán tối ưu là một lĩnh vực được các nhà khoa học trên thế giới đặc biệt quan tâm. Đã có rất nhiều các công trình nghiên cứu về lĩnh vực này, chủ yếu được phát triển trong lý thuyết tối ưu hóa đối với mô hình các bài toán quy hoạch và mô hình các bài toán trong công nghệ thông tin để tìm kiếm các thuật toán giải các lớp bài toán NP. Trong thời gian gần đây một hướng nghiên cứu quan trọng được phát triển trong lĩnh vực tính toán tiến hóa, đó chính là nghiên cứu về thuật toán di truyền (Genetic Algorithm - GA). Chính vì vậy, GA đã trở thành một trong những đề tài nghiên cứu thu hút được nhiều sự quan tâm và hiện nay đã và đang đem đến rất nhiều ứng dụng trong thực tiễn. Xuất phát từ thuyết tiến hóa muôn loài của Darwin, các nhà toán học John Holland (1975) và Goldberg (1989) đã đề xuất và phát triển GA. GA là một thuật toán đưa ra lời giải tương đối tối ưu. Tư tưởng chính của thuật toán là tìm kiếm lời giải tối ưu dựa trên cơ chế lai ghép, chọn lọc, sử dụng các nguyên lý về tính di truyền, sự thích nghi và sự sống các cá thể thích nghi nhất trong tự nhiên từ đó tiếp cận đến lời giải tối ưu của bài toán đang xét. Ngày nay, GA được ứng dụng khá nhiều trong các lĩnh vực như khoa học, kinh doanh và giải trí. Đầu tiên phải kể đến là các bài toán tối ưu bao gồm: Tối ưu số và tối ưu tổ hợp đã sử dụng GA để tìm lời giải như là bài toán người du lịch (Travelling Salesman Problems - TSP). Một ứng dụng khác cũng đang được ứng dụng rộng rãi của GA là giải quyết vấn đề bùng nổ về lượng thông tin trên mạng internet bao gồm: Thư viện điện tử, thông tin điện tử. dẫn đến phát sinh một số lượng lớn văn bản với tốc độ tăng chóng mặt. Nội dung chính của luận văn là nghiên cứu thuật toán di truyền và một số ứng dụng với lớp các bài toán NP. Cấu trúc luận văn gồm 3 chương: Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn Chương 1 trình bày các khái niệm cơ bản, mô hình, các tham số cơ bản, các phép toán, cơ chế thực hiện tổng quát của thuật toán di truyền. Chương 2 trình bày khái niệm về thuật toán và độ phức tạp của thuật toán, sự phân lớp các bài toán qua độ phức tạp, một số mô hình bài toán lớp NP. Chương 3 trình bày kết quả sử dụng GA xây dựng thuật toán giải bài toán lập lịch phân công giảng dạy tại mô hình trường cao đẳng dạy nghề. Các kết quả kiểm tra thuật toán GA giải một số mô hình bài toán NP đã được lập trình trên môi trường Matlab version 7. Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn Chương 1. GIẢI THUẬT DI TRUYỀN Nội dung chính của 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.