Khóa luận Xây dựng hệ thống điều khiển trực thăng không người lái giả lập bằng mô hình kết hợp GA - FL

a = 0 Vùng điều khiển trực thăng theo hướng dọc cho ra kết luận : góc nghiêng mong ước Rtheta = 4.016275 (cách tính toán được trình bày ở mục 5.4), giá trị lonδ dương (Positive) 1.094118 (cách tính tương tự mục 5.4), tức là phải tăng từ từ góc Theta bằng với góc Rtheta. Điều khiển trực thăng bay theo hướng ngang (lateral control): Điều khiển trực thăng theo hướng ngang là điều khiển trực thăng bay rẽ trái, rẽ phải. Điều khiển này do vùng điều khiển trực thăng theo hướng ngang đảm nhiệm. latδ Với các dữ liệu đầu vào (thử nghiệm): IAS = 43 Ev = 1.5 v_dot = 0.5 Epsi = 3 ---------------------------------------------------------------------------------------------- 42 Chương 5 : Giải quyết bài toán ---------------------------------------------------------------------------------------------- psi_dot = 0.5 p = 1.5 p_dot = 1 u = 3 Phi = 0 Vùng điều khiển trực thăng theo hướng ngang cho ra kết luận : góc nghiêng mong ước Rphi = 3.763474, giá trị latδ dương (Positive) 1.094118, tức là phải tăng từ từ góc Phi bằng với góc Rphi. Điều khiển cánh quạt đuôi (tail rotor control): Cánh quạt đuôi dùng để giữ thăng bằng và điều khiển hướng khi trực thăng bay rẽ trái hoặc rẽ phải. Điều khiển cánh quạt đuôi do vùng điều khiển bàn đạp đảm nhiệm. trδ Với dữ liệu đầu vào (thử nghiệm): IAS = 8.5 Epsi = 6 r = 10 r_dot = 5 Ev = 1.5 v_dot = 0.5 Vùng điều khiển bàn đạp cho ra kết luận : giá trị trδ dương (Positive) 1.195469, tức là phải đạp bàn đạp bên phải để cánh quạt đuôi tạo lực cho trực thăng rẽ sang phải. Điều khiển cần nâng (collective control): Cần nâng có nhiệm vụ điều khiển cánh quạt chính quay để tạo lực nâng cho trực thăng. Điều khiển này do vùng điều khiển cần nâng đảm nhiệm. δ col ---------------------------------------------------------------------------------------------- 43 Chương 5 : Giải quyết bài toán ---------------------------------------------------------------------------------------------- Với dữ liệu đầu vào (thử nghiệm): IAS = 7 Eh = 1.5 h_dot = 1.5 Vùng điều khiển cần nâng cho ra kết luận : giá trị δ col dương (Positive) 1.094118, tức là phải kéo cần nâng lên để tăng tốc độ quay của cánh quạt chính tạo lực nâng lớn hơn nữa cho trực thăng bay lên. 5.5.3.2. Kết hợp các vùng điều khiển cho việc điều khiển trực thăng bay trong những vị trí định sẵn : Bằng cách kết hợp 4 vùng điều khiển, ta sẽ điều khiển toàn bộ hoạt động bay của máy bay trực thăng. Để điều khiển trực thăng bay trong những vị trí định trước, cần phải cung cấp các dữ liệu đầu vào cũng như toạ độ tại mỗi vị trí. Các dữ liệu đầu vào phải được tính toán chính xác, phù hợp với miền giới hạn của bộ điều khiển. Bộ điều khiển sẽ tổng hợp các kết quả của 4 vùng điều khiển để đưa ra quyết định cuối cùng. Ví dụ : -1.5 0 0.25 IAS=12 Eu=7 udot=0.4 q=1.5 qdot=1 theta=0 Ev=4 vdot=0.5 p=4 pdot=2 Epsi=7 psidot=1.5 u=4 -1.24 0.02 0.26 IAS=43 Eu=7 udot=0.4 q=1.5 qdot=1 Ev=1.5 vdot=0.5 p=1.5 pdot=1 Epsi=3 psidot=0.5 u=14 phi=0 -0.7 0.02 0.28 IAS=30 Eu=28 udot=0.6 q=5 qdot=5 theta=11 Ev=15 vdot=0.5 p=1.5 pdot=1 Epsi=3 psidot=0.5 u=14 phi=0 0.06 0.19 0.28 IAS=45 Ev=1.5 vdot=0.5 p=6 pdot=5 Epsi=20 psidot=3 u=15 phi=2 0.67 0.2 0.37 IAS=30 Eu=28 udot=0.6 q=5 qdot=5 theta=11 1.36 0.36 0.38 IAS=30 Ev=1.5 vdot=0.5 p=6 pdot=5 Epsi=-20 psidot=-3 u=15 phi=-2 1.87 0.37 0.29 IAS=6 Eu=-28 udot=-0.6 q=5 qdot=5 theta=-8 2.1 0.32 .29 IAS=45 Ev=1.5 vdot=0.5 p=6 pdot=5 Epsi=20 psidot=3 u=15 phi=2 2.62 0.31 .36 IAS=45 Ev=1.5 vdot=0.5 p=6 pdot=5 Epsi=20 psidot=3 u=15 phi=2 ---------------------------------------------------------------------------------------------- 44 Chương 5 : Giải quyết bài toán ---------------------------------------------------------------------------------------------- Với 3 số đầu là toạ độ (x,y,z) hiện tại của trực thăng với hệ toạ độ định sẵn, mỗi dòng là dữ liệu đầu vào tại mỗi vị trí định trước. 5.6. Kết luận chương 5 : Chương 5 trình bày việc sử dụng mô hình GA- FL để tạo ra bộ luật điều khiển máy bay không người lái và áp dụng bộ luật này cho chương trình giả lập điều khiển trực thăng không người lái cũng như các kết quả thử nghiệm đạt được. ---------------------------------------------------------------------------------------------- 45 Kết luận và hướng phát triển ---------------------------------------------------------------------------------------------- KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Kết luận : Luận văn đạt được một số kết quả sau : - Tìm hiểu về hai kỹ thuật tính toán mềm : Logic mờ và Thuật giải di truyền. - Tìm hiểu về hệ thống điều khiển trực thăng không người lái. Tiến tới xây dựng bộ luật điều khiển bay tự động bằng mô hình kết hợp giữa Logic mờ và Thuật giải di truyền. Cụ thể : + Xây dựng bộ luật cơ bản bằng Logic mờ. + Mở rộng bộ luật cơ bản hình thành bộ luật mở rộng bằng Thuật giải di truyền. - Ứng dụng bộ luật điều khiển được xây dựng cho chương trình giả lập : điều khiển tự động trực thăng bay không người lái. -Tính khả thi của mô hình kết hợp GA – FL thông qua các kết quả thử nghiệm. Hướng phát triển : - Tiếp tục nghiên cứu, phát triển mô hình xây dựng sao cho có thể ứng dụng rộng rãi cho việc điều khiển bay tự động trong nhiều điều kiện giả lập khác : khí hậu, gió, mưa,… - Phát triển mô hình xây dựng để chỉ ra tính khoa học của nó với mục tiêu hướng tới những ứng dụng khác bên ngoài điều khiển bay tự động. ---------------------------------------------------------------------------------------------- 46 Tài liệu tham khảo ---------------------------------------------------------------------------------------------- TÀI LIỆU THAM KHẢO [1] C. Phillips, C.L. Karr, and G. Walker. Helicopter flight control with fuzzy logic and genetic algorithms. Engineering Applications of Artificial Intelligence, 9(2) : 175 – 184, April 1996. [2] Hoàng Kiếm, Lê Hoàng Thái. Thuật giải di truyền, cách giải tự nhiên các bài toán trên máy tính. Nhà xuất bản Giáo Dục, 2000. [3] Nguyễn Đình Thúc. Trí tuệ nhân tạo, Lập trình tiến hoá, Cấu trúc dữ liệu + Thuật giải di truyền = Chương trình tiến hoá. MK.PUB Nhà xuất bản Giáo Dục, 2001. [4] Foundations of Fuzzy Logic, Mathlab - The Language of Technical Computing, Fuzzy Logic Toolbox. [5] John A.R. Tucker, Phillip E. Fraley, and Lawrence P. Swanson, 1994: Fuzzy Logic in C: An Update, Dr. Dobb's Journal, April 1994. [6] L.Doitsidis, K.P. Valavanis, N.C. Tsourveloudis, M. Kontitsis. A Framework for Fuzzy Logic Based UAV Navigation and Control. Proceeding of the 2004 IEEE, International Conference on Robotics & Automation, New Orieans, LA – April 2004. [7] D.K.Kahaner. Fuzzy helicopter control. Asian Technology Information Program (ATIP), 12 April 1993, Japan. [8] D.K.Kahaner. Fuzzy logic. Asian Technology Information Program (ATIP), 24 August 1990, Japan. [9] Jim Murtha, 1995: Applications of fuzzy logic in operational meteorology, Scientific Services and Professional Development Newsletter, Canadian Forces Weather Service, 42-54. [10] Flight Directional Controls. ---------------------------------------------------------------------------------------------- 47 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- PHỤ LỤC A. Thuật giải di truyền :[2], [3] + Đại cương : 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. Quan niệm này có thể được xem như một tiên đề đúng, không chứng minh được, nhưng phù hợp với thực tế khách quan. 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 (phát triển hơn, hoàn thiện hơn) thế hệ trước. Tiến hoá tự nhiên được duy trì nhờ hai quá trình cơ bản : sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hoá tự nhiên, các thế hệ mới luôn được sinh ra để bổ sung thay thế thế hệ cũ. 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. Cá thể nào không thích ứng được với môi trường sẽ bị đào thải. Sự thay đổi môi trường là động lực thúc đẩy quá trình tiến hoá. Ngược lại, tiến hoá cũng tác động trở lại góp phần làm thay đổi môi trường. Quá trình tiến hoá này đã được John Henry Holland ứng dụng vào việc giải quyết vấn đề với máy vi tính. Ông đã đề xướng ra Thuật giải di truyền (Genetic Algorithms _ GA) vào năm 1975. GA là kỹ thuật giúp giải quyết vấn đề bắt chước theo sự tiến hoá của con người hay của sinh vật nói chung, trong điều kiện quy định sẵn của môi trường. GA giúp tìm ra giải pháp tối ưu hay tốt nhất trong điền kiện thời gian và không gian cho phép. GA không giống như những phương pháp giải tích dựa trên các công thức toán học hay phương thức suy luận dựa trên kinh nghiệm của các chuyên gia mà GA xét đến toàn bộ các giải pháp, bằng cách xét trước nhất một số giải ---------------------------------------------------------------------------------------------- 48 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- pháp, sau đó loại bỏ những thành phần không thích hợp và chọn những thành phần thích nghi hơn để tạo sinh và biến hoá nhằm mục đích tạo ra nhiều giải pháp mới có hệ số thích nghi ngày càng cao. Như vậy, GA là một hình thức tìm kiếm có tính ngẫu nhiên nhưng được hướng dẫn bởi hàm số thích nghi. GA không thể luôn luôn tìm ra giải pháp tối ưu, nhưng chắc chắn sẽ cung cấp những giải pháp tương đối tốt trên nền tảng vững chắc và trong thời gian nhanh nhất. + Tính chất đặc thù của Thuật giải di truyền : _GA lập luận mang tính chất ngẫu nhiên, thay vì xác định như toán học giải tích. _GA duyệt xét toàn bộ các giải pháp, sau đó chọn lấy giải pháp tương đối tốt nhất dựa trên hệ số thích nghi. _GA không để ý đến chi tiết vấn đề, trái lại chỉ chú ý đến giải pháp, đặc biệt là dãy số tượng trưng cho giải pháp. _GA rất thích hợp cho việc tìm kiếm giải đáp cho vấn đề, hay tìm điều kiện tối ưu cho việc điều hành, và phân nhóm những giải pháp có được. + Các bước quan trọng trong việc áp dụng Thuật giải di truyền : Bước 1: Chọn mô hình cho giải pháp của vấn đề : chọn một số tượng trưng cho toàn bộ các giải pháp có thể có cho vấn đề. Bước 2: Chỉ định cho mỗi giải pháp một ký hiệu . Ký hiệu có thể là dãy số hệ nhị phân, hay dãy số thập phân, dãy của chữ hay hỗn hợp chữ và số.Trong giai đoạn mới làm quen với GA, chỉ nên dùng hệ nhị phân để làm ký hiệu cho giải pháp. Bước 3: Tìm hàm số thích nghi cho vấn đề và tính hệ số thích nghi cho từng giải pháp. ---------------------------------------------------------------------------------------------- 49 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- Bước 4: Dựa trên hệ số thích nghi của các giải pháp để thực hiện sự tạo sinh (reproduction) và biến hoá các giải pháp. Các phương thức biến hoá gồm: lai ghép (crossover), đột biến (mutation). Bước 5: Tính các hệ số thích nghi cho các giải pháp mới và loại bỏ những giải pháp kém nhất để chỉ còn giữ lại một số nhất định các giải pháp. Bước 6: Nếu chưa tìm được giải pháp tối ưu hay tương đối khá nhất hay chưa hết hạn kỳ ấn định, trở lại bước 4 để tìm giải pháp mới. Bước 7: Tìm được giải pháp tối ưu hoặc nếu thời gian cho phép đã chấm dứt thì báo cáo kết quả tính được. + Sự mã hoá và các toán tử di truyền : Mã hoá : Bước đầu tiên trong Thuật giải di truyền là mã hoá, ánh xạ các biến một xâu với chiều dài hữu hạn sang các tham biến của bài toán tối ưu. Tham biến x thuộc [Umin; Umax] sẽ được biểu diễn bởi chuỗi nhị phân có chiều dài L. L bit mã hoá x ứng với giá trị trong miền [0; 2L] sẽ được ánh xạ lên các giá trị thuộc miền xác định [Umin; Umax]. Theo cách này chúng ta có thể kiểm soát miền giá trị của các biến và tính chính xác của chúng. Tỷ lệ co giãn của ánh xạ này được cho bởi: 12 minmax − −= L UUg Ta thấy giá trị x tương ứng với mã string2 sẽ được xác định theo công thức: x = Umin + decimal(string2)*g trong đó decimal(string2) biểu diễn giá trị thập phân của chuỗi nhị phân string2, g là tỷ lệ co giãn được xác định ở trên. VD: decimal(0001) = 1; decimal(0011) = 3 ---------------------------------------------------------------------------------------------- 50 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- Để mã hoá tập các biến, ta ghép nối mã các biến riêng lẻ lại với nhau. Mỗi mã tương ứng với một chiều dài các bit riêng và xác định một giá trị tương ứng của nó nằm trong miền [Umin; Umax]. VD: Mã hoá cho 4 biến được cho bởi: 0001|0110|1010|1111 U1 | U2 | U3 | U4 Trong đó thành tố thứ nhất (4 bit đầu tiên) tương ứng với biểu diễn của biến thứ nhất, thành tố cuối cùng ( 4 bit cuối cùng) tương ứng với biểu diễn của biến cuối cùng. Các toán tử di truyền : Trong quá trình tiến hoá, các cá thể mới sinh ra nhờ sự lai ghép ở thế hệ cha-mẹ. Một cá thể mới có thể mang những tính trạng của cha mẹ (di truyền), cũng có thể mang tính trạng hoàn toàn mới (đột biến). Di truyền và đột biến là hai cơ chế có vai trò quan trọng như nhau trong tiến trình tiến hoá, dù rằng đột biến xảy ra với xác suất nhỏ hơn nhiều so với hiện tượng di truyền. Các thuật toán tiến hoá tuy có những điểm khác biệt, nhưng đều mô phỏng bốn quá trình cơ bản : lai ghép, đột biến, sinh sản và chọn lọc tự nhiên. Tương ứng với bốn quá trình vừa nêu, trong Thuật giải di truyền ta có: toán tử lai ghép, toán tử đột biến, toán tử tạo sinh, và toán tử chọn lọc. Toán tử lai ghép (crossover) : Toán tử tác động trên các cá thể cha mẹ để tạo ra những con lai tốt bằng cách ghép một hay nhiều đoạn gen của hai (hay nhiều) nhiễm sắc thể cha-mẹ với nhau. Chúng được áp dụng lên cặp cha mẹ được chọn lựa với xác suất lai ghép ký hiệu bởi Pcross . Xác suất này cho chúng ta số lượng (Pcross*pop_size) nhiễm sắc thể được dùng cho hoạt động lai ghép, ở đây pop_size là kích thước của quần thể được tạo lai. ---------------------------------------------------------------------------------------------- 51 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- Với mỗi nhiễm sắc thể trong quần thể: • Phát sinh một số ngẫu nhiên r trong miền [0;1] • Nếu r < P , chọn nhiễm sắc thể đó để lai ghép. cross Sau đó, ta kết hợp các nhiễm sắc thể được chọn một cách ngẫu nhiên: Mỗi cặp nhiễm sắc thể, chúng ta có thể phát sinh một số ngẫu nhiên pos từ miền[1; L] (L là tổng số bit trong nhiễm sắc thể ). Số pos báo hiệu vị trí của điểm lai ghép. Hai nhiễm sắc thể : (b1b2……..bposbpos+1…….b ) và L (c1c2……..cposcpos+1…….c ) L được thay thế bởi cặp con cháu: (b1b2……..bposcpos+1…….c ) và L (c1c2……..cposbpos+1…….b ) L Như vậy xử lý này sản xuất ra hai chuỗi mới, mỗi chuỗi đều được thừa hưởng những đặc tính lấy từ cha và mẹ của chúng. Lai ghép cho phép Thuật giải di truyền sử dụng những thông tin đã có để tìm kiếm trực tiếp trên những vùng tốt hơn. Toán tử đột biến (mutation) : Đột biến là hiện tượng cá thể con mang một số tính trạng không có trong mã di truyền của cha mẹ. Toán tử đột biến nhằm tạo ra những thông tin mới trong quần thể lai tạo tại các vị trí bit (gen) nào đó (quần thể được xem xét có pop_size cá thể, mỗi cá thể được biểu thị qua L bit/gen). Đột biến được áp dụng với xác suất P , nhỏ hơn rất nhiều so với xác suất lai Pmu cross .Số lượng bit đột biến là Pmu*L*pop_size bit. Mỗi bit có cơ hội đột biến như nhau và được thay đổi từ 0 thành 1 hay ngược lại. Có thể xử lý theo cách sau: Với mỗi nhiễm sắc thể trong quần thể và mỗi bit trong nhiễm sắc thể : • Phát sinh một số ngẫu nhiên r trong miền [0; 1] ---------------------------------------------------------------------------------------------- 52 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- • Nếu r < P , tiến hành đột biến tại bit đó. mu Các thao tác xử lý này được áp dụng lặp đi lặp lại cho tới khi các cá thể con cháu của chúng tăng trưởng tới kích cỡ mong muốn của quần thể. Toán tử chọn các thể (selection) : Toán tử chọn lọc là thao tác xử lý trong đó mỗi cá thể được bảo lưu cho vòng tạo sinh tiếp sau tuỳ thuộc vào giá trị thích nghi của nó. Toán tử này là một phiên bản mô phỏng của quá trình chọn lọc tự nhiên. Giá trị thích nghi F(i) được xác định đối với mỗi cá thể trong quần thể. Giá trị này càng lớn thì cá thể được coi là hợp lý. Hàm thích nghi có thể là hàm không liên tục, hàm dương hay phi tuyến. Xử lý chọn lọc các cá thể cha mẹ được hình thành theo mô hình tái tạo quay trên vòng tròn (roulette weel). Vòng quay của chúng có kích cỡ khác nhau ứng với những giá trị hợp lý của các cá thể. Kỹ thuật này được gọi là lựa chọn cha mẹ trên vòng tròn quay (roulette weel parent selection). Mỗi khi cần tạo ra một con cháu, sẽ thực hiện một lần quay trên vòng tròn trọng số nhằm sinh ra ứng cử viên cho việc tái sản xuất. Toán tử chọn lọc nhằm tìm ra những cá thể tồn tại tốt nhất và không tạo ra những cá thể mới. Kỹ thuật này có thể thực hiện theo các bước: • Tính tổng giá trị thích nghi của tất cả thành viên quần thể và gọi nó là tổng thích nghi F (total fitness). t • Phát sinh một số n là số ngẫu nhiên trong miền [0; F ]. t • Trả lại thành viên quần thể đầu tiên mà giá trị thích nghi của nó cộng với giá trị thích nghi của các thành viên quần thể trước đấy lớn hơn hoặc bằng n. ---------------------------------------------------------------------------------------------- 53 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- Toán tử tạo sinh (generation) : Hàm tạo sinh đóng vai trò rất quan trọng trong Thuật giải di truyền. Dựa vào giá trị thích nghi của từng cá thể (fitness) trong quần thể, tổng giá trị thích nghi (total fitness) của quần thể, ứng dụng các toán tử di truyền (chọn lọc, đột biến, lai ghép) lên quần thể để sản sinh ra quần thể mới gồm các cá thể có tính trạng tốt hơn quần thể ban đầu. Hàm này có thể thực hiện như sau: • Chọn lọc các cá thể tốt trong quần thể. • Lai ghép và đột biến các cá thể này để tạo ra các cá thể mới tốt hơn cho quần thể mới. + Hàm thích nghi (Fitness): Là hàm xác định giá trị thích nghi (fitness value) của từng cá thể trong quần thể. Giá trị thích nghi càng cao thì cá thể sẽ được chọn lựa cho lần sinh sản mới, ngược lại cá thể sẽ bị đào thải. Ánh xạ giá trị hàm mục tiêu sang giá trị thích nghi: Vì hàm thích nghi phải nhận giá trị không âm, do đó cần phải xây dựng ánh xạ hàm mục tiêu đang xét trong bài toán sang hàm thích nghi thông qua một hoặc nhiều lần ánh xạ. Nếu bài toán tối ưu là cực tiểu một hàm đánh giá g(x), việc chuyển từ hàm đánh giá sang hàm thích nghi để sử dụng với GA là: ⎩⎨ ⎧ −= 0 (x)Cmax )( g xf khi g(x) < Cmax trong các trường hợp khác Ở đây, Cmax là một tham số đầu vào. Ví dụ, có thể lấy Cmax là giá trị g lớn nhất trong quần thể hiện tại, hoặc lớn nhất sau k vòng lặp. Nói chung Cmax khác nhau tuỳ thuộc vào giá trị các biến của quần thể. ---------------------------------------------------------------------------------------------- 54 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- Khi hàm mục tiêu gốc tăng hoặc đang xét bài toán cực đại hoá một hàm hữu dụng u(x), chúng ta có thể chuyển sang hàm thích nghi như sau: ⎩⎨ ⎧ += 0 Cmin u(x) )(xf khi u(x) + Cmin > 0 trong các trường hợp khác Ở đây Cmin là tham số đầu vào, có thể là trị tuyệt đối của u bé nhất trong quần thể hiện tại hoặc trong k vòng lặp cuối cùng hoặc là một hàm của biến quần thể. Điều chỉnh độ thích nghi: Một vấn đề quan trọng là điều chỉnh số con cháu. Điều này đặc biệt quan trọng cho một vài vòng lặp đầu tiên, khi một vài cá thể “siêu” có tiềm năng chiếm lĩnh phần lớn quần thể và làm cho hội tụ sớm. Điều chỉnh độ thích nghi có thể giúp giải quyết vấn đề này. Một kiểu điều chỉnh hay gặp là điều chỉnh tuyến tính. Chúng ta định nghĩa độ thích nghi gốc là f và độ thích nghi đã biến đổi là f’. Điều chỉnh tuyến tính xác định quan hệ giữa f và f’ như sau: f’ = a*f + b (A.1) Với a, b là các hệ số được chọn sao cho: f’avg = f avg (A.2) và f’ = Cmax mult*favg (A.3) Ở đây Cmult là số các bản sao cần thiết đối với một thành viên tốt nhất. Với lượng biến tương đối nhỏ (n=50 đến 100), Cmult thường được chọn từ 1.2 đến 2 và tỏ ra khá hiệu quả. ---------------------------------------------------------------------------------------------- 55 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- Biểu thức (A.2) bảo đảm rằng mỗi thành viên với độ thích nghi trung bình sẽ cho một con hay một cháu đối với lần phát sinh tiếp theo. Biểu thức (A.3) kiểm soát số con cháu được nạp vào làm thành viên với độ thích nghi gốc cực đại. Lưu ý rằng điều chỉnh tuyến tính trong biểu thức từ (A.1) – (A.3) có thể làm cho giá trị thích nghi trở thành âm. Điều này không cho phép vì phải luôn đảm bảo tính không âm của nó. Một giải pháp thay thế điều kiện trong biểu thức (A.3) là sử dụng điều kiện f = 0. min + Thuật giải: Sơ đồ thuật giải: ---------------------------------------------------------------------------------------------- 56 Phụ lục A : Thuật giải di truyền ---------------------------------------------------------------------------------------------- Thuật giải : Bước 1: Khởi tạo quần thể các nhiễm sắc thể nhằm thiết lập số lượng nhiễm sắc thể ngẫu nhiên ban đầu (thường dưới dạng chuỗi nhị phân) với kích cỡ quần thể bằng pop_size (xác định trước). Bước 2: Xác định giá trị thích nghi (fitness value) của từng nhiễm sắc thể. Bước 3: Sao chép lại các nhiễm sắc thể dựa vào giá trị thích nghi của chúng và tạo ra những nhiễm sắc thể mới bằng việc kết hợp các nhiễm sắc thể hiện tại (dùng các toán tử lai ghép, đột biến, tái kết hợp). Bước 4: Loại bỏ những thành viên không thích nghi trong quần thể. Bước 5: Chèn những nhiễm sắc thể mới vào quần thể để hình thành một quần thể mới. Tiếp tục cho đến khi đạt được điều kiện định trước. ---------------------------------------------------------------------------------------------- 57 Phụ lục B : Logic mờ ---------------------------------------------------------------------------------------------- Mã giải : [3] Bắt đầu : t = 0; Khởi tạo P(t); Tính độ thích nghi cho các cá thể thuộc P(t); Khi (điều kiện dừng chưa thoả) lặp t = t + 1; Tái sinh P’(t) từ P(t); Lai Q(t) từ P(t-1); Đột biến R(t) từ P(t-1); Chọn lọc P(t) từ P(t-1) Q(t) ∪ R(t) P’(t); ∪ ∪ Hết lặp Kết thúc. B. Logic mờ (fuzzy logic): + Đại cương: [2] Hệ thống nhị phân là nguyên tắc hoạt động căn bản của máy vi tính: mạch điện đóng (1) hay mở (0), sự kiện có (1) hay không có (0), đáp số trúng (1) hay không trúng (0), … là những chi tiết mà máy vi tính xét đến để giải quyết vấn đề. Nhưng trong thực tế, chúng ta không luôn luôn đối diện với những tình trạng rõ ràng như trên, những gì chúng ta phải giải quyết hầu như không đầy đủ, không chính xác hay không có biên giới rõ ràng. VD: _Chiều nay có thể mưa nhưng không chắc sẽ có mưa rào. _Máy phát điện chạy không êm chắc là thiếu nhớt trong trục máy. _Hiệu điện thế thay đổi khá nhiều chắc là nhu cầu điện tăng giảm bất thường. ---------------------------------------------------------------------------------------------- 58 Phụ lục B : Logic mờ ---------------------------------------------------------------------------------------------- Hệ thống nhị phân, trắng đen rõ ràng, của máy vi tính không thể giúp giải quyết vấn đề này. Và L.A.Zadeh thuộc đại học Hoa Kỳ đã đề xuất lý thuyết về Logic mờ (Fuzzy Logic) dựa trên một nhóm số không chính xác là tập mờ (fuzzy set) để giải quyết các vấn đề mơ hồ(vague) bằng máy vi tính. Ngày nay Logic mờ là kỹ thuật được ưa chuộng nhất trong điều khiển máy móc, biến chế dữ kiện, thu thập kiến thức,… Sau đây là phần trình bày các vấn đề liên quan đến Logic mờ: + Tập mờ (fuzzy sets) [4] Tập mờ là tập chứa các phần tử mà giá trị của nó được ánh xạ sang miền [0, 1]. Khác với logic đúng-sai (Boolean) chỉ chứa 2 giá trị 0 hoặc 1, logic mờ chứa những giá trị nằm giữa 0 và 1, ví dụ như 0, 0.2, 0.7213, 0.02, 1, …Tập mờ được xác định bởi hàm thành viên. + Hàm thuộc (hay hàm thành viên) (membership function) [4] Hàm thuộc là một đường mà vạch rõ mọi điểm nằm t