Giải thuật di truyền với các gen phụ thuộc nhau - Vũ Trọng Sinh

Vũ Trọng Sinh và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 127 - 131 127 GIẢI THUẬT DI TRUYỀN VỚI CÁC GEN PHỤ THUỘC NHAU Vũ Trọng Sinh1, Trương Thị Hương2, Vũ Mạnh Xuân*2 1Trường ĐH Khoa học - ĐH Thái Nguyên ,2Trường ĐH Sư phạm - ĐH Thái Nguyên TÓM TẮT Bài báo này trình bày giải thuật di truyền trong trường hợp các gen của mỗi cá thể không bình đẳng mà phụ thuộc vào nhau. Phần ứng dụng xét một bài toán cụ thể là điều hành bốn hồ chứa nước trong lĩnh vực thủy văn. Từ khóa: Giải thuật di truyền, gen, điều hành hồ nước MỞ ĐẦU* Trong các bài toán tối ưu số được giải bằng giải thuật di truyền, vai trò của các gen thường là bình đẳng với nhau, không phụ thuộc vào cách mã hóa [4]. Đối với những bài toán với các thành phần (gen) của cá thể (lời giải) không bình đẳng mà phụ thuộc nhau, việc thực hiện các toán tử lai ghép (crossover) và đột biến (mutation) cần được xem xét chi tiết. Khi lai ghép hoặc đột biến làm biến đổi giá trị tại một gen nào đó, các gen khác có quan hệ với nó cũng cần phải biến đổi theo để đảm bảo không vi phạm các ràng buộc. Bài báo này trình bày giải pháp thực hiện các toán tử di truyền với các gen trong mỗi cá thể không độc lập với nhau và ứng dụng cho một bài toán cụ thể trong lĩnh vực thủy văn. Bài báo có cấu trúc như sau: Sau phần mở đầu là khái quát về giải thuật di truyền mã hóa số thực với vai trò các gen không bình đẳng. Phần tiếp theo trình bày một bài toán cụ thể điều hành van xả nước của bốn hồ chứa nước và sử dụng giải thuật di truyền giải bài toán trên. Phần cuối cùng là kết luận và danh mục tài liệu tham khảo. GIẢI THUẬT DI TRUYỀN VỚI CÁC GEN PHỤ THUỘC NHAU Đối với giải thuật di truyền mã hóa nhị phân (mỗi gen chỉ có giá trị 0 hay 1 với các toán tử lai ghép thông thường như lai một điểm, lai đa điểm hay lai mặt nạ và phép đột biến là phép đảo bit), vai trò các gen là bình đẳng với nhau. Thực tế, mỗi nhóm bit biểu thị một thành phần của cá thể, nên giữa các nhóm bit này có thể có những quan hệ phụ thuộc nhau. * Tel: 0912700396; Email:vmxuan08@gmail.com Trong trường hợp đó, tất nhiên khi mã và giải mã phải tính lại các thành phần để kiểm tra xem chúng có vi phạm các ràng buộc hay không. Trong bài này chúng tôi đề cập đến giải thuật di truyền mã hóa số thực (RCGA- Real Code Genetic Algorrithm). Mỗi cá thể được mã hóa như một véc tơ trong không gian Rn, mỗi thành phần (gen) của nó là một số thực trong miền xác định tương ứng. Giả thiết các gen này không bình đẳng mà có sự phụ thuộc vào nhau. Với giả thiết trên, ngay từ bước khởi tạo quần thể ta đã phải tính từng gen để đảm bảo không bị vi phạm các ràng buộc. Chẳng hạn việc tạo ngẫu nhiên gen thứ i của một cá thể có thể như sau: Repeat Gen(i) := random(i); Until (không vi phạm ràng buộc); trong đó random(i) là hàm phát sinh một giá trị ngẫu nhiên trong miền xác định của gen(i), còn ràng buộc chỉ sự phụ thuộc của gen(i) vào các gen khác trong cá thể. Cũng như vậy, trong các toán tử di truyền cơ bản, lai ghép và đột biến là hai toán tử có sự thay đổi giá trị gen. Hai khả năng xảy ra mỗi khi có sự biến đổi này: 1) Gen có sự biến đổi giá trị nhưng không ảnh hưởng đến các gen khác, hay nói cách khác không vi phạm ràng buộc nào. Khi đó cá thể sinh ra sẽ được chấp nhận để chuyển sang bước kế tiếp của giải thuật. 2) Sự thay đổi giá trị tại một gen dẫn đến phải thay đổi giá trị của các gen liên quan với nó. Khi đó có thể dùng kỹ thuật phạt chết: Vũ Trọng Sinh và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 127 - 131 128 hủy bỏ cá thể mới tạo ra hoặc gọi một thủ tục hiệu chỉnh giá trị các gen liên quan. Đáng chú ý là khi hiệu chỉnh giá trị các gen liên quan cần được tiến hành sao cho tính ngẫu nhiên vẫn được đảm bảo để duy trì tính đa dạng của quần thể. Có thể xem việc tính lại các gen này thực ra là quá trình khởi tạo lại cá thể, song ở đây không phải khởi tạo toàn bộ mà chỉ đối với các gen có liên quan đến gen bị biến đổi do áp dụng toán tử di truyền. Với những bài toán dạng này, các dạng lai ghép truyền thống như lai một điểm, lai đa điểm hay lai mặt nạ tỏ ra không phù hợp lắm. Trong [3] các tác giả đã khảo sát toán tử lai ghép SBX (Simulated Binary Crossover), hai cá thể con được tạo từ một cặp cá thể cha mẹ x và y mà các thành phần được tính bởi: uk = 0.5*((1-β)*xk + (1+β)*yk) vk = 0.5*((1+β)*xk + (1-β)*yk) Trong đó uk và vk là thành phần thứ k của cá thể con được tạo ra từ hai cá thể cha mẹ có thành phần tương ứng là xk và yk còn β là tham biến. Với việc chọn tham số β một cách thích hợp có thể thu được các dạng lai ghép truyền thống. Tuy nhiên nếu điều chỉnh β theo các phân phối xác suất khác có thể thu được kết quả tốt hơn. Vấn đề ở đây là khi thực hiện lai ghép, với những gen mới tạo thành có thể vi phạm những ràng buộc do sự phụ thuộc của nó vào những gen khác. Tương tự như vậy đối với toán tử đột biến. Cách làm thông thường là: chọn một gen, thay nó bởi một giá trị khác trong miền xác định tương ứng. Tuy nhiên ở đây cần xem xét lại tất cả những gen có quan hệ đến gen vừa được thay thế vì có thể chúng bị biến đổi theo và vi phạm ràng buộc. Như vậy trong trường hợp sử dụng giải thuật di truyền mà các gen trong mỗi cá thể có sự phụ thuộc vào nhau thì vẫn tiến hành giải thuật như thường. Song mỗi khi có sự thay đổi giá trị tại một gen nào đó thì cần tính lại hoặc kiểm tra tất cả các gen có quan hệ đến nó để đảm bảo thỏa các ràng buộc của bài toán. Nếu xảy ra vi phạm tại một vị trí nào đó thì có thể chọn một trong các giải pháp sau: - Sử dụng kỹ thuật phạt, có thẻ phạt chết (loại ngay cá thể vi phạm) hoặc vẫn lấy cá thể đó với một xác suất nào đó sau khi đã đánh dấu với hy vọng các cá thể ngoại lai vẫn có thể sinh thế hệ sau tốt. - Sử dụng một thủ tục sửa lỗi, có thể bắt đầu từ gen vi phạm rồi hiệu chỉnh nó, có thể phát sinh ngẫu nhiên gen thay thế hợp lệ. - Thay toán tử vừa sử dụng bởi một dạng khác. BÀI TOÁN 4 HỒ CHỨA Để minh họa, chúng tôi giới thiệu một bài toán trong lĩnh vực thủy văn là bài toán bốn hồ chứa sau [1], [2]: Giả sử có bốn hồ chứa nước với mục đích sản xuất điện và tưới tiêu ở hạ lưu với sơ đồ sau: Hình 1. Sơ đồ bốn hồ chứa nước Trong hình trên, bốn hồ chứa nước ký hiệu lần lượt là S1, S2, S3 và S4; q1, q2 là lượng nước chảy từ nguồn đến S1 và S2 tương ứng; ui (i = 1, 2, 3, 4) lần lượt là lượng nước thoát ra từ các hồ Si; các giá trị ui có thể được điều chỉnh bởi hệ thống. Giả thiết các dòng chảy q1 và q2 đến các hồ S1 và hồ S2 là không đổi. Dung lượng các hồ chứa cần thỏa mãn điều kiện: (1) Tại thời điểm ban đầu (k=1) thì S1 = S2 = S3 = S4 = 5 (2) u3 u2 S1 S2 S3 q1 q2 u1 u4 S4 0 < S1 < 10 0 < S2 < 10 0 < S3 < 10 0 < S4 < 15 Vũ Trọng Sinh và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 127 - 131 129 Các biến ui (i = 1, 2, 3, 4) là lưu lượng thoát nước từ hồ chứa Si tương ứng có thể điều khiển nhờ hệ thống đóng mở cửa xả nước tại thời điểm k. Các biến này cần thỏa mãn điều kiện: (3) Bài toán đặt ra là điều khiển các ui (i = 1, 2, 3, 4) để lợi ích thu được từ sản xuất điện và tưới tiêu đạt giá trị cực đại, đồng thời tại thời điểm k = 13 hệ thống cần thỏa mãn điều kiện: S1 = S2 = S3 = 5; S4 = 7 (4) Phương trình cân bằng của hệ thống tại thời điểm (k+1) có thể tính bởi công thức (5) sau: S1(k+1) = S1(k) + q1 – u1(k) S2(k+1) = S2(k) + q2 – u2(k) S3(k+1) = S3(k) + u2(k) – u3(k) (5) S4(k+1) = S4(k) + u1(k) + u3(k) – u4(k) Lợi ích của toàn hệ thống được tính như sau: (6) Trong công thức (6) gồm có ba tổng thành phần, cụ thể là: ♦ Tổng thứ nhất là lợi ích mang lại từ sản xuất điện. ♦ Tổng thứ hai là lợi ích do tưới tiêu ở hạ lưu. ♦ Tổng thứ ba là lợi ích phụ do lượng nước lưu trữ ở thời kỳ cuối cùng, nếu các hồ chứa nhiều hơn hay ít hơn lượng nước yêu cầu tại thời điểm k = 13 thì lợi ích phụ bằng 0. Như vậy ta cần tính các ui(k) (i = 1, 2, 3, 4 và k = 1, ..., 12) sao cho (6) đạt giá trị cực đại trong khi các ràng buộc (1), (2), (3), (4) và (5) được thỏa mãn. GIẢI BÀI TOÁN TRÊN BẰNG GIẢI THUẬT RCGA Sử dụng giải thuật RCGA giải bài toán này như sau: Mã hóa: Theo yêu cầu của bài toán, ta cần tính các giá trị ui(k) trong đó i là chỉ số hồ thứ i và k là thời điểm điều khiển. Một cách tự nhiên, ta sử dụng một mảng 2 chiều để mã hóa một cá thể chẳng hạn C(m,n) với m =12 và n = 4. Trong mảng này, dòng thứ k (k=1, ..., 12) ứng với một sự điều chỉnh cửa xả nước của bốn hồ tại thời điểm thứ k (C[k,i] là giá trị ui tại thời điểm k). Lưu ý rằng các giá trị này cần thỏa mãn các điều kiện (1), (2), (3) và (5). Để theo dõi và tính toán thuận tiện, tại mỗi thời điểm k cần ghi lại lượng nước Si có trong hồ thứ i. Khi đó có thể mã hóa mỗi cá thể là một mảng hai chiều C(12,8), trong đó C[k,i] với i=1..4 tương ứng là các giá trị Si, còn C[k,i] với i=5..8 là các giá trị ui tại thời điểm k. Như vậy, một quần thể có size cá thể có thể mã hóa thành mảng 3 chiều, trong đó thành phần đầu tiên là chỉ số của cá thể trong quần thể. Chẳng hạn quần thể có 30 cá thể được mã hóa là C(30,12,8). Toán tử lai ghép: Với cách mã hóa như trên, các thành phần trong mỗi cá thể không bình đẳng với nhau vì việc thoát nước tại một hồ chứa cần phải căn cứ vào dung lượng nước có trong hồ này, khả năng chứa của hồ kế tiếp và khả năng mở tối đa của cửa xả. Như vậy, các dạng lai ghép kinh điển như lai một điểm, lai nhiều điểm hay lai mặt nạ tỏ ra không phù hợp trong bài toán này vì chúng sẽ sinh nhiều cá thể không thỏa mãn các ràng buộc. Chương trình sử dụng dạng toán tử lai ghép SBX đã nêu trên với việc điều chỉnh tham số β theo phân phối mũ λ.e(-λx) với λ là hằng số. Trong trường hợp toán tử này sinh ra cá thể không thỏa mãn các ràng buộc, trong chương trình này sử dụng kỹ thuật phạt chết, chỉ xét đến các con hợp lệ, các cá thể vi phạm các ràng buộc sẽ bỏ qua. Việc gọi một thủ tục sửa lỗi có thể làm phức tạp thêm hoặc tăng thời gian tính toán. Toán tử đột biến: Sử dụng đột biến đều, tại vị trí chọn đột biến k (thời điểm k), sinh ngẫu nhiên các giá trị ui thoả điều kiện (3). Song khi đó các giá trị Si và ui tại tất cả các thời điểm j (j = k+1, , 12) đều phải tính lại và đảm bảo không vi phạm các ràng buộc. 0 < u1 < 3 0 < u2 < 4 0 < u3 < 4 0 < u4 < 7 Vũ Trọng Sinh và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 127 - 131 130 Chọn lọc tạo sinh: Chương trình sử dụng chiến lược chọn lọc tạo sinh có tính tinh hoa. Hai cá thể cha mẹ sau khi thực hiện lai ghép sinh ra hai cá thể con. Nếu có cá thể con nào có độ phù hợp “tốt hơn” cha hoặc mẹ chúng thì thay thế cho cá thể kém hơn đó. Độ phù hợp của mỗi cá thể được tính như sau: Giá trị hàm mục tiêu của mỗi cá thể được tính là tổng lợi ích của hệ thống theo công thức (6). Đồng thời do điều kiện (4) nên độ phù hợp của cá thể phụ thuộc hai yếu tố: giá trị hàm mục tiêu càng lớn càng tốt, trong khi tổng độ lệch của lượng nước trong mỗi hồ chứa tại thời điểm k = 13 theo điều kiện (4) càng nhỏ càng tốt. Để tiện so sánh các thông số được giữ nguyên như trong [1], các hệ số bi(k) trong công thức (6) được lấy bằng 1, tổng lợi ích phụ (số hạng thứ ba trong (6)) bằng 0 do hệ thống hầu như không thể đạt độ chính xác yêu cầu của dung tích các hồ chứa tại thời điểm k=13. Kết quả thực hiện chương trình cho bởi bảng 1. Với kết quả này, tổng độ lệch dung lượng nước của 4 hồ tại thời điểm k = 13 so với yêu cầu của điều kiện (4) là 1.9584; tổng lợi ích thu được theo công thức (6) là 217.0344. So sánh với kết quả đã biết theo [1], tổng độ lệch dung lượng nước của 4 hồ tại thời điểm k = 13 so với yêu cầu của điều kiện (4) là 3.5; tổng lợi ích thu được theo công thức (6) là 216.6. Rõ ràng so với kết quả đã biết đó thì kết quả tính được ở đây tốt hơn. KẾT LUẬN Bài báo này đề cập đến một dạng giải thuật di truyền trong những bài toán với mã hóa các gen của cá thể không bình đẳng, phụ thuộc lẫn nhau. Kết quả thực nghiệm trên bài toán cụ thể cho thấy kỹ thuật này đã phát huy được tính ưu việt của nó. Trong bài này sử dụng kỹ thuật phạt chết, tuy nhiên có thể phát triển kết quả này bằng cách sử dụng các hàm sửa lỗi và các cơ chế khác. TÀI LIỆU THAM KHẢO [1]. Lê Xuân Cầu (2000), Ứng dụng của thuật toán gen trong nghiên cứu thủy văn, Tạp chí Khí tượng Thủy văn số 7/2000. [2]. Lê Xuân Cầu (2002), Tối ưu đa mục tiêu sử dụng tài nguyên nước bằng thuật toán gen. Tạp chí Khí tượng Thủy văn số 4/2002. [3]. Vũ Mạnh Xuân, Nguyễn Thanh Thủy (2006), Giải thuật di truyền mã hóa số thực với toán tử lai ghép SBX, Tạp chí “Tin học và điều khiển học”, tập 22, số 2, 2006. [4]. Goldberg, D.E. (1989), Genetic algorithms in search, optimization and machine learning, Addison-Wesley, Reading, MA. [5]. K. Deb (1999), Multi-Objective Genetic Algorithms: Problem Difficulties and Construction of Test Problems, Evolutionary Computation, 7(3), 205-230. [6]. Haimes Y.Y., Hall W.A. & Freedman, (1974), Multiobjectives optimization in Water Resources Systems: The Surrogate Worth Trade-off Method, Developments in Water Science, No. 3, Elsevier. Bảng 1. Kết quả bài toán 4 hồ chứa nước sử dụng RCGA k S1 S2 S3 S4 u1 u2 u3 u4 1 5 5 5 5 2.4276 3.9749 3.177 3.7616 2 4.5724 4.0251 5.798 6.843 1.7203 1.9386 3.7678 6.2019 3 4.8521 5.0864 3.9688 6.1292 2.9986 3.8143 3.1668 5.7387 4 3.8534 4.2721 4.6163 6.5559 2.9124 3.3398 2.8842 3.5619 5 2.9411 3.9323 5.072 8.7906 1.5616 2.6406 3.1885 4.4778 6 3.3795 4.2917 4.524 9.0629 2.6039 3.4302 3.0817 5.5305 7 2.7756 3.8616 4.8725 9.2181 0.9694 3.804 1.7279 3.643 8 3.8062 3.0576 6.9486 8.2724 2.4907 1.2462 3.2461 6.7406 9 3.3155 4.8113 4.9487 7.2686 1.861 3.1926 3.5331 3.5379 10 3.4545 4.6187 4.6082 9.1248 1.8764 3.1372 1.8851 5.3833 11 3.5782 4.4815 5.8603 7.503 0.6095 3.6562 2.6883 6.9188 12 4.9687 3.8253 6.8283 3.8819 2.4642 2.1083 3.9922 4.4626 13 4.5045 4.717 4.9443 5.8758 Vũ Trọng Sinh và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 127 - 131 131 SUMMARY GENETIC ALGORITHM WITH DEPENDING GENS Vu Trong Sinh 1, Truong Thi Huong 2, Vu Manh Xuan 2* 1 College of Sciences – TNU,2 College of Education – TNU This paper presents genetic algorithm using gens are not equal but, depend on each other. The applied section presents a concrete problem of controlling four lakes in the hydrology field. Keywords: Genetic Algorithm, gene, contronlling lakes * Tel: 0912700396; Email:vmxuan08@gmail.com