Giải thuật di truyền với các gen phụ thuộc nhau

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