Ứng dụng giải thuật di truyền cho bài toán điều khiển tối ưu đa mục tiêu - Lại Khắc Lãi

Lại Khắc Lãi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 86(10): 213 - 218 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 213 ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN ĐIỀU KHIỂN TỐI ƯU ĐA MỤC TIÊU Lại Khắc Lãi1*, Đặng Ngọc Trung2 1Đại học Thái Nguyên, 2ĐTrường ĐH Kỹ Thuật Công nghiệp- ĐH Thái Nguyên TÓM TẮT Trong thực tế hiện nay hầu hết các bài toán điều khiển trong các dây chuyền công nghệ là bài toán tối ưu đa mục tiêu.Việc ứng dụng các giải thuật tính toán tiến hóa hứa hẹn nhiều triển vọng. Bài báo này trình bày một ứng dụng mới để giải bài toán tối ưu đa mục tiêu đó là dùng thuật toán giải thuật di truyền (GA-Genetic Algorithm), nội dung bài báo cho thấy tính ưu việt của giải thuật di truyền với quá trình tìm kiếm cực trị toàn cục. Từ khóa: Điều khiển tối ưu, Đa mục tiêu, Giải thuật di truyền.  ĐẶT VẤN ĐỀ Bài toán tối ưu đa mục tiêu có mặt hầu hết trong các bài toán điều khiển dây chuyền công nghệ hiện đại trong công nghiệp nói riêng và mở rộng ra nhiều lĩnh vực khác. Tuy nhiên chưa có nhiều nghiên cứu về các bài toán này. Hiện nay các đề tài khoa học chủ yếu mới chỉ giải quyết và ứng dụng các bài toán tối ưu một mục tiêu. Ví dụ ta xét công nghệ gia nhiệt phôi kim loại trong lò nung là một trong những quá trình có tham số biến đổi chậm, trong đó các hàm mục tiêu đặt ra với lò gia nhiệt như sau: nung nhanh nhất hoặc nung chính xác nhất, nung ít bị Ôxi hóa nhất; trong các bài toán điều khiển mức của dây truyền sản xuất nước ngọt thì các hàm mục tiêu có thể là: ổn định mức dung dịch H chính xác nhất hoặc thời gian ổn định nhanh nhất... Đã có nhiều phương pháp tiếp cận khác nhau nhằm giải quyết các loại bài toán này, song gần đây việc ứng dụng các giải thuật tính toán tiến hóa đã bắt đầu cho thấy được ưu điểm nổi bật.Tuy vậy những nghiên cứu về lĩnh vực này trong nước ta chưa nhiều, nhất là chưa đưa ra được những mô hình ứng dụng thực tế cụ thể trong khi nhu cầu ứng dụng lại rất cao, đã có một số tác giả đề cập và nghiên cứu ví dụ như: trong [2] tác giả Nguyễn Mạnh Xuân đã sử dụng giải thuật tiến hóa để tìm lời giải tối ưu cho các hàm mục tiêu trong mô hình  Tel: 0913 507464 bài toán phân bố dòng chảy và xử lý nước thải; trong [5] tác giả Lại Khắc Lãi đề cập đến việc sử dụng giải thuật di truyền để tối ưu hóa suy luận mờ... các kết quả nghiên cứu này mới chỉ dừng lại ở các hàm mục tiêu có sẵn, tính thực tiễn chưa cao. Đây chính là lý do mà đề tài này tập trung chủ yếu vào việc xây dựng bài toán tối ưu nhiều mục tiêu cho dây chuyền công nghệ thực tế và ứng dụng giải thuật di truyền (Genetic Algorithm – GA) để giải quyết bài toán tối ưu đó. Nội dung bài báo với kết quả chạy chương trình tính toán bằng giải thuật di truyền và mô phỏng điều khiển với đối tượng là mức dung dich H trong bình trộn khuấy cho thấy tính ưu việt của việc sử dụng giải thuật di truyền với quá trình tìm kiếm cực trị toàn cục trên cơ chế chọn lọc thích nghi tự nhiên và cơ chế song song ẩn cho những bài toán tối ưu hoặc tối ưu đa mục tiêu và có thể triển khai để áp dụng rộng rãi cho nhiều đối tượng điều khiển và trong nhiều lĩnh vực như: khí tượng, thủy văn GIẢI THUẬT DI TRUYỀN Khái quát giải thuật di truyền Giải thuật di truyền (GA – Genetic Algorithm) là giải thuật tìm kiếm, chọn lựa các giải pháp tối ưu để giải quyết các bài toán thực tế khác nhau, dựa trên cơ chế chọn lọc của tự nhiên: Từ tập lời giải ban đầu, thông qua nhiều bước tiến hóa, hình thành tập lời giải mới Lại Khắc Lãi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 86(10): 213 - 218 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 214 phù hợp hơn, và cuối cùng dẫn đến lời giải tối ưu toàn cục. Các nhà khoa học đã nghiên cứu và xây dựng nên giải thuật di truyền dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hóa. Giải thuật di truyền sử dụng các thuật ngữ được lấy từ di truyền học như: lai ghép, đột biến, NST, cá thể Ở đây mỗi cá thể được đặc trưng bởi một tập nhiễm sắc thể, nhưng để đơn giản khi trình bày, ta xét trường hợp tế bào mỗi cá thể chỉ một NST. Các NST được chia nhỏ thành các gen được sắp xếp theo một dãy tuyến tính. Mỗi cá thể (hay NST) biểu diễn một lời giải có thể của bài toán. Một xử lý tiến hóa duyệt trên tập các NST tương đương với việc tìm kiếm lời giải trong không gian lời giải của bài toán. Giải thuật di truyền có thể mô tả vắn tắt như sau: Proceduce Giải_thuật_di_truyền; Begin t:=0; Khởi tạo ngẫu nhiên quần thể P(t); Đánh giá độ phù hợp từng cá thể trong P(t); Repeat t:= t + 1; Chọn các cá thể từ P(t – 1); Lai tạo các cá thể đã chọn tạo ra P(t) mới; Đột biến các cá thể trong P(t) theo xác suất Pm; Đánh giá độ phù hợp các cá thể trong tạp P(t); Until (thỏa mãn điều kiện dừng); End; Các kỹ thuật trong giải thuật di truyền Giải thuật di truyền kinh điển sử dụng mã hóa nhị phân, mỗi cá thể được mã hóa là một chuỗi nhị phân có chiều dài cố định. Mã hóa- biểu diễn các biến bằng vec tơ nhị phân Ta sử dụng véctơ nhị phân có độ dài L như một NST để biểu diễn giá trị thực của biến  ; .x xx l u Độ dài L của NST phụ thuộc vào yêu cầu cụ thể của bài toán. Một bit mã hóa x ứng với một giá trị trong khoảng 0;2L   sẽ được ánh xạ lên giá trị thực thuộc miền  ; .x xl u Nhờ đó, 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ạ được tính như sau: Giá trị x tương ứng với chuỗi NST nhị phân là:  * .xx l decimal NST g  Trong đó,  decimal NST là giá trị thập phân của chuỗi NST nhị phân và 2 x x L u l g   Khởi tạo quần thể Để khởi tạo quần thể, chỉ cần đơn giản tạo pop – size (kích cỡ quần thể) nhiễm sắc thể ngẫu nhiên theo từng bit. Phần còn lại của thuật giải di truyền rất đơn giản: Trong mỗi thế hệ, ta lượng giá từng NST (tính giá trị của hàm f trên các chuỗi biến nhị phân đã được giải mã), chọn quần thể mới thỏa mãn phân bố xác suất dựa trên độ thích nghi và thực hiện các phép đột biến và lai để tạo ra các cá thể thế hệ mới. Sau một số thế hệ, khi không còn cải thiện thêm được gì nữa, NST tốt nhất sẽ được xem như lời giải của bài toán tối ưu (thường là toàn cục). Hàm thích nghi Sau khi khởi tạo quần thể hoặc ở thời điểm các thế hệ mới được tạo thành, chúng ta phải sử dụng hàm thích nghi để đánh giá mức độ thích nghi của mỗi nhiễm sắc thể nhằm có cơ sở cho việc lựa chọn bố mẹ cho các phép lai tạo và đột biến. Các phương pháp xác định độ thích nghi: + Xác định theo tỷ lệ thích nghi (Fitness scaling ) + Xác định theo phương pháp cửa sổ thích nghi (Fitness windowing ) + Xác định theo thứ hạng thích nghi (Fitness ranking ) Toán tử chọn lọc Ở mỗi thế hệ, dựa trên gí trị của hàm thích nghi, các cá thể có độ thích nghi tốt sẽ được Lại Khắc Lãi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 86(10): 213 - 218 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 215 chọn lọc để tạo thành quần thể ở thể ở thế hệ mới và chuẩn bị cho việc thực hiện các phép toán lai ghép và đột biến sau này. Một số phép chọn lọc thường được sử dụng bao gồm: + Sử dụng bánh xe Roulette + Chọn lọc xếp hạng + Chọn lọc cạnh tranh Toán tử lai ghép Trong giải thuật di truyền, số lượng các cá thể trong quần thể ở mỗi thế hệ là không đổi. Phép chọn lọc đã chọn ra một số cá thể có độ thích nghi cao và loại bỏ đi một số cá thể thích nghi thấp. Sự thiếu hụt số lượng cá thể trong quần thể mới sẽ được bù đắp bằng lấy các cá thể thích nghi cao là thế hệ cha mẹ, tạo ra các thế hệ con bằng phép lai ghép và đột biến trên các cá thể thích nghi cao này. Một số phương pháp lai ghép: + Lai ghép một điểm + Lai ghép nhiều điểm + Lai ghép mặt nạ Toán tử đột biến Đột biến là thay đổi các bít trên chuỗi nhiễm sắc thể một cách ngẫu nhiên để tạo ra tính đa dạng. Phép đột biến được điều khiển bởi xác suất đột biến Pm. Nếu không đột biến thì giải thuật chỉ đi tìm kiếm lời giải ở không gian khởi tạo. Tuy nhiên, nếu Pm quá lớn, quá trình tìm kiếm trở thành tìm kiếm ngẫu nhiên. Các phương pháp giải bài toán tối ưu đa mục tiêu Mô hình toán học của bài toán    n Y(X) min(max) X D R  k 1 k Y(X) = (Y (X),...,Y (X)) R gọi là véc tơ mục tiêu. X gọi là phương án, D là tập các phương án. Y1,,Yk gọi là các hàm mục tiêu. Khi xử lý tập nghiệm Pareto, vai trò của người sử dụng (NSD) hay người nhận lời giải của bài toán đóng vai trò quan trọng. NSD sẽ căn cứ vào lợi ích của mình để chọn phương án cho hợp lý, cách đó gọi là kết hợp QHĐMT với NSD. Có thể nói lợi ích ở đây là một hàm U : Y(D) R thường được giả thiết thỏa mãn một vài điều kiện nào đó dùng để đo sở thích của NSD. Phương pháp nhượng bộ dần B1: Giải k bài toán một mục tiêu riêng rẽ, sau đó lập bảng thưởng phạt. B2: Căn cứ vào bảng thưởng phạt, với giá trị Y1 0 NSD buộc Y1 nhượng bộ một lượng Y1 và giải bài toán: 2 max Y (X) với XD; Y1(X)Y1 0 - Y1 Giả sử Y2 * là trị tối ưu của bài toán này, chuyển sang B3. B3: NSD căn cứ vào Y2 0 và Y2 * buộc Y2 nhượng bộ lượng Y2 và giải bài toán: 3 max Y (X) với XD; Y1(X)Y1 0 - Y1; Y2(X) Y2 * - Y2; Giả sử Y3 * là trị tối wucuar bài toán này, chuyển tiếp sang bước tiếp. Bk: NSD căn cứ vào Yk-1 0 và Yk-1 * buộc Yk-1 nhượng bộ lượng Yk-1 và giải bài toán: k max Y (X) với XD; Y1(X)Y1 0 - Y1; Y2(X) Y2 * - Y2;...,Yk-1(X) )Yk-1 * - Yk-1; Nghiệm của bài toán cuối cùng này lấy làm nghiệm của bài toán. Phương pháp thỏa hiệp B1: Giải k bài toán một mục tiêu riêng rẽ, giả sử nghiệm tối ưu là Xi (i=1,,k). Đặt Mi = Yi(Xi) và đưa vào biến phụ W: M ( ) Wi i i i Y X M   với mọi i= 1,,k Vế trái trong công thức trên gọi là độ lệch tương đối chung. B2: Giải bài toán min W với XD từ đó tìm được nghiệm tối ưu X0 và W0 Lại Khắc Lãi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 86(10): 213 - 218 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 216 Trong trường hợp này, lợi ích tỷ lệ với độ lệch tương đối, phương án X1 là tốt hơn X2 nếu độ lệch tương đối chung của X1 nhỏ hơn X2. Phương pháp tìm nghiệm có khoảng cách nhỏ nhất đến nghiệm lý tưởng Phương pháp này giả định có một nghiệm lý tưởng , X1 tốt hơn X2 nếu khoảng cách từ X1 đến nghiệm lý tưởng nhỏ hơn khoảng cách tương ứng của X2. Định nghĩa: Giả sử X1, X2 Rn, khoảng cách giữa X1 và X2 là số d xác định bởi: 1 2 i i d X X      là tham số >1 Khi đó bài toán maxY(X) với XD đưa về bài toán  *min ( )i iY X Y   Vấn đề xác định tham số  phụ thuộc vào từng bài toán. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU Đặt bài toán Giả sử điều khiển mức dung dịch H trong bình khuấy trộn theo sơ đồ điều khiển và sơ đồ khối như hình 1 dưới đây Trong đó: + Hàm truyền đạt của bộ chuyển đổi dòng điện – khí nén (I/P):              mA mmKG I P K 2 max max /5,0 420 002,001,0 + Hàm truyền đạt của van: tín hiệu vào là áp suất khí nén và tín hiệu ra là lưu lượng nước cấp thông qua cơ cấu van: 1 1 2 2 50 125 W ( ) ( ) ; W ( ) ( ) 1 0,01 1 0,01 V T V T s W s s W s s s         Hình 1. Sơ đồ điều khiển mức của bình trộn + Hàm truyền đạt của thiết bị đo mức: tín hiệu vào là khoảng cách và tín hiệu đầu ra là điện áp: 0,016W ( ) 1 0,005 H s s   Bài toàn tối ưu đặt ra ở đây là thiết kế bộ điều khiển PD sao cho ổn định mức dung dịch H chính xác nhất và thời gian ổn định nhanh nhất, tương ứng với hai hàm mục tiêu như sau: Hình 2. Sơ đồ khối điều khiển mức Mục tiêu 1: 2 1 ( )J e t dt min  Mục tiêu 2: 2 ( )J e t dt min  Từ hình 2 tính toán và rút ra được phương trình vi phân: Lại Khắc Lãi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 86(10): 213 - 218 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 217 2 D P2 0,015. (1,4 1) 1,4. . 0 d e de K K e dt dt     Ta có phương trình đặc trưng là: 2 D P 0,015. (1,4 1) 1,4. 0k K k K    Với điều kiện 0  thì phương trình trên có một nghiệm riêng là 1 2k t k t( )e t e e  Chọn P 25 100K  suy ra D 1,35 50K  Trong đó:     2 D D PD 1 2 D D PD 2 1,4 1 1,4 1 0,084.1,4 1 0.03 0.03 1,4 1 1,4 1 0,084.1,4 1 0.03 0.03 K K KK k K K KK k                          Thay t=3(s) cuối cùng ta có được bài toán tối ưu hai muc tiêu điều khiển mức dung dịch H như sau:  1 21 2 1 2 2 t 2 1 1 1 2 2 2 1 2 P D 1 2 1 2 2 25 100 1,35 50 k k tk k t k t k t J e e e min k k k k e e J min k k K K                        Giải quyết bài toán Dùng thuật toán giải thuật di truyền viết trên phần mềm Matlab với quần thể khởi tạo ban đầu gồm 30 cá thể, sau các bước lai ghép, chọn lọc, đột biến giải bài toán đa mục tiêu trên ta thu được kết quả tối ưu của bộ giá trị (KP và KD) sau: KP = 25.895; KD = 18.349 làm cho J1 và J2 min. Vậy đó chính là bộ giá trị tối ưu của bộ điều khiển PD trong sơ đồ điều khiển mức trên với lưu đồ thuật toán của giải thuật di truyền như hình 3. Hình 4. Kết quả mô phỏng với bộ thông số tối ưu KP = 25.895; KD = 18.349 Hình 5. Kết quả mô phỏng với bộ thông số tối ưu và bộ thông số khác Các kết quả mô phỏng được chỉ ra trên hình 4 và hình 5. Trong đó: Hình 4 ứng với các thông số tối ưu tìm được bằng giải thuật di truyền còn Hình 5 là đáp ứng quá độ ứng với bộ thông số tối ưu và nộ thông số khác. Lại Khắc Lãi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 86(10): 213 - 218 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 218 Hình 3. Lưu đồ thuật toán KẾT LUẬN Qua kết qủa mô phỏng trên Matlab Simulink với các bộ giá trị của (KP và KD) lấy từ tập nghiệm của thuật toán giải thuật di truyền, ta có thể tìm thấy một bộ nghiệm tối ưu mà ở đó ta thấy chất lượng điều khiển mức dung dịch H tăng rõ rệt, độ sai lệch và thời gian quá độ đều nhỏ hơn so với các bộ giá trị khác. Với kết quả này cho phép mở rộng hướng thiết kế bộ điều khiển PID tối ưu cho các dây chuyền công nghệ và đây cũng chính là hướng mới trong tính toán mềm sẽ được áp dụng trong các bài toán tối ưu thực tế trong tương lai. TÀI LIỆU THAM KHẢO [1]. Nguyễn Doãn Phước, Phan Xuân Minh, Hán Thành Trung (2003), Lý thuyết điều khiển phi tuyến, Nxb Khoa học và Kỹ thuật, Hà Nội. [2]. Vũ Mạnh Xuân (2006) “Tính toán tiến hóa trong tối ưu đa mục tiêu” Đề tài nghiên cứu khoa học cấp Bộ - Mã số: B2006 TN01 – 04. [3]. Nguyễn Thương Ngô (1999), Lý thuyết điều khiển tự động hiện đại, Nhà xuất bản Khoa học Kỹ thuật. [4]. Vũ Mạnh Xuân, Nguyễn Thanh Thủy (2007) “Giải thuật di truyền với các gen phụ thuộc nhau”, báo cáo Hội thảo Quốc gia “Ngiên cứu cơ bản và ứng dụng công nghệ thông tin”. [5]. Lại Khắc Lãi (2001) “Thiết kế hệ điều khiển mờ nhờ sử dụng thuật gen” Tạp chí Khoa học công nghệ trường Đại học Kỹ thuật Công nghiệp, trang 10-16. [6]. Nguyễn Đình Thúc (2001), Lập trình tiến hóa, Nhà xuất bản Giáo dục. [7]. Goldberg, D.E. (1989), Genetic Algorithm in search, optimization and machine learning, Addsion – Wesley, Reading, MA. Lại Khắc Lãi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 86(10): 213 - 218 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 219 SUMMARY APPLICATION GENETIC ALGOTITHM TO SOLVE MULTI-OBJECTIVE OPTIMIZATION PROBLEMS Lai Khac Lai 1 , Dang Ngoc Trung 2 1 Thai Nguyen University, College of Technology - TNU In fact today most of the control problem in the technology chain optimization problems are multi-purpose. Application of evolutionary computation algorithms promising prospects. This article presents a new application to solve multi-objective optimization algorithm that uses genetic algorithms (GA-Genetic Algorithm), contents of the article shows the superiority of genetic algorithm with the process of finding a global extremum. Key words: Optimization control; Multi objective; Genetic Algorithm.  Tel: 0913 507464