intTypePromotion=1

Ứ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

Chia sẻ: Thi Thi | Ngày: | Loại File: PDF | Số trang:7

0
58
lượt xem
8
download

Ứ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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. 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)

Chủ đề:
Lưu

Nội dung Text: Ứ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 và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 86(10): 213 - 218<br /> <br /> ỨNG DỤNG GIẢI THUẬT DI TRUYỀN<br /> CHO BÀI TOÁN ĐIỀU KHIỂN TỐI ƯU ĐA MỤC TIÊU<br /> Lại Khắc Lãi1*, Đặng Ngọc Trung2<br /> 1<br /> <br /> Đại học Thái Nguyên, 2ĐTrường ĐH Kỹ Thuật Công nghiệp- ĐH Thái Nguyên<br /> <br /> TÓM TẮT<br /> 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<br /> 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<br /> 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<br /> 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<br /> truyền với quá trình tìm kiếm cực trị toàn cục.<br /> Từ khóa: Điều khiển tối ưu, Đa mục tiêu, Giải thuật di truyền.<br /> <br /> <br /> ĐẶT VẤN ĐỀ<br /> Bài toán tối ưu đa mục tiêu có mặt hầu hết<br /> trong các bài toán điều khiển dây chuyền<br /> công nghệ hiện đại trong công nghiệp nói<br /> riêng và mở rộng ra nhiều lĩnh vực khác. Tuy<br /> nhiên chưa có nhiều nghiên cứu về các bài<br /> toán này. Hiện nay các đề tài khoa học chủ<br /> yếu mới chỉ giải quyết và ứng dụng các bài<br /> toán tối ưu một mục tiêu. Ví dụ ta xét công<br /> nghệ gia nhiệt phôi kim loại trong lò nung là<br /> một trong những quá trình có tham số biến<br /> đổi chậm, trong đó các hàm mục tiêu đặt ra<br /> với lò gia nhiệt như sau: nung nhanh nhất<br /> hoặc nung chính xác nhất, nung ít bị Ôxi<br /> hóa nhất; trong các bài toán điều khiển mức<br /> của dây truyền sản xuất nước ngọt thì các<br /> hàm mục tiêu có thể là: ổn định mức dung<br /> dịch H chính xác nhất hoặc thời gian ổn<br /> định nhanh nhất...<br /> Đã có nhiều phương pháp tiếp cận khác nhau<br /> nhằm giải quyết các loại bài toán này, song<br /> gần đây việc ứng dụng các giải thuật tính toán<br /> tiến hóa đã bắt đầu cho thấy được ưu điểm nổi<br /> bật.Tuy vậy những nghiên cứu về lĩnh vực<br /> này trong nước ta chưa nhiều, nhất là chưa<br /> đưa ra được những mô hình ứng dụng thực tế<br /> cụ thể trong khi nhu cầu ứng dụng lại rất cao,<br /> đã có một số tác giả đề cập và nghiên cứu ví<br /> dụ như: trong [2] tác giả Nguyễn Mạnh Xuân<br /> đã sử dụng giải thuật tiến hóa để tìm lời giải<br /> tối ưu cho các hàm mục tiêu trong mô hình<br /> <br /> <br /> bài toán phân bố dòng chảy và xử lý nước<br /> thải; trong [5] tác giả Lại Khắc Lãi đề cập đến<br /> việc sử dụng giải thuật di truyền để tối ưu hóa<br /> suy luận mờ... các kết quả nghiên cứu này<br /> mới chỉ dừng lại ở các hàm mục tiêu có sẵn,<br /> tính thực tiễn chưa cao. Đây chính là lý do mà<br /> đề tài này tập trung chủ yếu vào việc xây<br /> dựng bài toán tối ưu nhiều mục tiêu cho dây<br /> chuyền công nghệ thực tế và ứng dụng giải<br /> thuật di truyền (Genetic Algorithm – GA) để<br /> giải quyết bài toán tối ưu đó.<br /> Nội dung bài báo với kết quả chạy chương<br /> trình tính toán bằng giải thuật di truyền và mô<br /> phỏng điều khiển với đối tượng là mức dung<br /> dich H trong bình trộn khuấy cho thấy tính<br /> ưu việt của việc sử dụng giải thuật di truyền<br /> với quá trình tìm kiếm cực trị toàn cục trên<br /> cơ chế chọn lọc thích nghi tự nhiên và cơ<br /> chế song song ẩn cho những bài toán tối ưu<br /> hoặc tối ưu đa mục tiêu và có thể triển khai<br /> để áp dụng rộng rãi cho nhiều đối tượng<br /> điều khiển và trong nhiều lĩnh vực như: khí<br /> tượng, thủy văn…<br /> GIẢI THUẬT DI TRUYỀN<br /> Khái quát giải thuật di truyền<br /> Giải thuật di truyền (GA – Genetic Algorithm)<br /> là giải thuật tìm kiếm, chọn lựa các giải pháp<br /> tối ưu để giải quyết các bài toán thực tế khác<br /> nhau, dựa trên cơ chế chọn lọc của tự nhiên:<br /> Từ tập lời giải ban đầu, thông qua nhiều<br /> bước tiến hóa, hình thành tập lời giải mới<br /> <br /> Tel: 0913 507464<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> 213<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Lại Khắc Lãi và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> phù hợp hơn, và cuối cùng dẫn đến lời giải<br /> tối ưu toàn cục.<br /> Các nhà khoa học đã nghiên cứu và xây dựng<br /> nên giải thuật di truyền dựa trên cơ sở chọn lọc<br /> tự nhiên và quy luật tiến hóa. Giải thuật di<br /> truyền sử dụng các thuật ngữ được lấy từ di<br /> truyền học như: lai ghép, đột biến, NST, cá<br /> thể… Ở đây mỗi cá thể được đặc trưng bởi một<br /> tập nhiễm sắc thể, nhưng để đơn giản khi trình<br /> bày, ta xét trường hợp tế bào mỗi cá thể chỉ một<br /> NST. Các NST được chia nhỏ thành các gen<br /> được sắp xếp theo một dãy tuyến tính. Mỗi cá<br /> thể (hay NST) biểu diễn một lời giải có thể của<br /> bài toán. Một xử lý tiến hóa duyệt trên tập các<br /> NST tương đương với việc tìm kiếm lời giải<br /> trong không gian lời giải của bài toán.<br /> Giải thuật di truyền có thể mô tả vắn tắt như sau:<br /> Proceduce Giải_thuật_di_truyền;<br /> Begin<br /> t:=0;<br /> Khởi tạo ngẫu nhiên quần thể P(t);<br /> Đánh giá độ phù hợp từng cá thể trong P(t);<br /> Repeat<br /> t:= t + 1;<br /> Chọn các cá thể từ P(t – 1);<br /> Lai tạo các cá thể đã chọn tạo ra P(t) mới;<br /> Đột biến các cá thể trong P(t) theo xác<br /> suất Pm;<br /> Đánh giá độ phù hợp các cá thể trong tạp<br /> P(t);<br /> Until (thỏa mãn điều kiện dừng);<br /> End;<br /> Các kỹ thuật trong giải thuật di truyền<br /> Giải thuật di truyền kinh điển sử dụng mã hóa<br /> nhị phân, mỗi cá thể được mã hóa là một<br /> chuỗi nhị phân có chiều dài cố định.<br /> Mã hóa- biểu diễn các biến bằng vec tơ<br /> nhị phân<br /> Ta sử dụng véctơ nhị phân có độ dài L như<br /> một NST để biểu diễn giá trị thực của biến<br /> x  lx ; ux . Độ dài L của NST phụ thuộc<br /> vào yêu cầu cụ thể của bài toán. Một bit mã<br /> <br /> <br /> <br /> <br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> 86(10): 213 - 218<br /> <br /> hóa x ứng với một giá trị trong khoảng<br /> 0; 2 L  sẽ được ánh xạ lên giá trị thực thuộc<br /> miền lx ; ux . Nhờ đó, ta có thể kiểm soát<br /> miền giá trị của các biến và tính chính xác của<br /> chúng. Tỷ lệ co giãn của ánh xạ được tính<br /> như sau:<br /> Giá trị x tương ứng với chuỗi NST nhị phân<br /> là: x  lx  decimal  NST  * g . Trong đó,<br /> <br /> <br /> <br /> <br /> <br /> decimal  NST  là giá trị thập phân của chuỗi<br /> <br /> NST nhị phân và g <br /> <br /> u x  lx<br /> 2L<br /> <br /> Khởi tạo quần thể<br /> Để khởi tạo quần thể, chỉ cần đơn giản tạo<br /> pop – size (kích cỡ quần thể) nhiễm sắc thể<br /> ngẫu nhiên theo từng bit. Phần còn lại của<br /> thuật giải di truyền rất đơn giản: Trong mỗi<br /> thế hệ, ta lượng giá từng NST (tính giá trị của<br /> hàm f trên các chuỗi biến nhị phân đã được<br /> giải mã), chọn quần thể mới thỏa mãn phân<br /> bố xác suất dựa trên độ thích nghi và thực<br /> hiện các phép đột biến và lai để tạo ra các cá<br /> thể thế hệ mới. Sau một số thế hệ, khi không<br /> còn cải thiện thêm được gì nữa, NST tốt nhất<br /> sẽ được xem như lời giải của bài toán tối ưu<br /> (thường là toàn cục).<br /> Hàm thích nghi<br /> Sau khi khởi tạo quần thể hoặc ở thời điểm<br /> các thế hệ mới được tạo thành, chúng ta phải<br /> sử dụng hàm thích nghi để đánh giá mức độ<br /> thích nghi của mỗi nhiễm sắc thể nhằm có cơ<br /> sở cho việc lựa chọn bố mẹ cho các phép lai<br /> tạo và đột biến.<br /> Các phương pháp xác định độ thích nghi:<br /> + Xác định theo tỷ lệ thích nghi (Fitness<br /> scaling )<br /> + Xác định theo phương pháp cửa sổ thích<br /> nghi (Fitness windowing )<br /> + Xác định theo thứ hạng thích nghi (Fitness<br /> ranking )<br /> Toán tử chọn lọc<br /> Ở mỗi thế hệ, dựa trên gí trị của hàm thích<br /> nghi, các cá thể có độ thích nghi tốt sẽ được<br /> 214<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Lại Khắc Lãi và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> chọn lọc để tạo thành quần thể ở thể ở thế hệ<br /> mới và chuẩn bị cho việc thực hiện các phép<br /> toán lai ghép và đột biến sau này.<br /> Một số phép chọn lọc thường được sử dụng<br /> bao gồm:<br /> + Sử dụng bánh xe Roulette<br /> + Chọn lọc xếp hạng<br /> + Chọn lọc cạnh tranh<br /> Toán tử lai ghép<br /> Trong giải thuật di truyền, số lượng các cá thể<br /> trong quần thể ở mỗi thế hệ là không đổi.<br /> Phép chọn lọc đã chọn ra một số cá thể có độ<br /> thích nghi cao và loại bỏ đi một số cá thể<br /> thích nghi thấp. Sự thiếu hụt số lượng cá thể<br /> trong quần thể mới sẽ được bù đắp bằng lấy<br /> các cá thể thích nghi cao là thế hệ cha mẹ, tạo<br /> ra các thế hệ con bằng phép lai ghép và đột<br /> biến trên các cá thể thích nghi cao này.<br /> Một số phương pháp lai ghép:<br /> + Lai ghép một điểm<br /> + Lai ghép nhiều điểm<br /> + Lai ghép mặt nạ<br /> Toán tử đột biến<br /> <br /> 86(10): 213 - 218<br /> <br /> Khi xử lý tập nghiệm Pareto, vai trò của<br /> người sử dụng (NSD) hay người nhận lời giải<br /> của bài toán đóng vai trò quan trọng. NSD sẽ<br /> căn cứ vào lợi ích của mình để chọn phương<br /> án cho hợp lý, cách đó gọi là kết hợp<br /> QHĐMT với NSD. Có thể nói lợi ích ở đây là<br /> một hàm U : Y(D)  R thường được giả thiết<br /> thỏa mãn một vài điều kiện nào đó dùng để đo<br /> sở thích của NSD.<br /> Phương pháp nhượng bộ dần<br /> B1: Giải k bài toán một mục tiêu riêng rẽ, sau<br /> đó lập bảng thưởng phạt.<br /> B2: Căn cứ vào bảng thưởng phạt, với giá trị<br /> Y10 NSD buộc Y1 nhượng bộ một lượng Y1<br /> và giải bài toán:<br /> <br /> max Y2 (X) với XD; Y1(X)Y10 - Y1<br /> Giả sử Y2* là trị tối ưu của bài toán này,<br /> chuyển sang B3.<br /> B3: NSD căn cứ vào Y20 và Y2* buộc Y2<br /> nhượng bộ lượng Y2 và giải bài toán:<br /> <br /> max Y3 (X) với XD; Y1(X)Y10 - Y1;<br /> Y2(X) Y2* - Y2;<br /> Giả sử Y3* là trị tối wucuar bài toán này,<br /> chuyển tiếp sang bước tiếp….<br /> <br /> Đột biến là thay đổi các bít trên chuỗi nhiễm<br /> sắc thể một cách ngẫu nhiên để tạo ra tính đa<br /> dạng. Phép đột biến được điều khiển bởi xác<br /> suất đột biến Pm. Nếu không đột biến thì giải<br /> thuật chỉ đi tìm kiếm lời giải ở không gian<br /> khởi tạo. Tuy nhiên, nếu Pm quá lớn, quá trình<br /> tìm kiếm trở thành tìm kiếm ngẫu nhiên.<br /> <br /> Bk: NSD căn cứ vào Yk-10 và Yk-1* buộc Yk-1<br /> nhượng bộ lượng Yk-1 và giải bài toán:<br /> <br /> Các phương pháp giải bài toán tối ưu đa<br /> mục tiêu<br /> <br /> Phương pháp thỏa hiệp<br /> <br /> Mô hình toán học của bài toán<br /> Y(X)  min(max)<br /> X  D  Rn<br /> Y(X) = (Y1 (X),...,Yk (X))  Rk gọi là véc tơ<br /> <br /> mục tiêu.<br /> X gọi là phương án, D là tập các phương án.<br /> Y1,…,Yk gọi là các hàm mục tiêu.<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> max Yk (X) với XD; Y1(X)Y10 - Y1;<br /> Y2(X) Y2* - Y2;...,Yk-1(X) )Yk-1*- Yk-1;<br /> Nghiệm của bài toán cuối cùng này lấy làm<br /> nghiệm của bài toán.<br /> B1: Giải k bài toán một mục tiêu riêng rẽ, giả<br /> sử nghiệm tối ưu là Xi (i=1,…,k).<br /> Đặt Mi = Yi(Xi) và đưa vào biến phụ W:<br /> Mi  Yi ( X i )<br />  W với mọi i= 1,…,k<br /> Mi<br /> <br /> Vế trái trong công thức trên gọi là độ lệch<br /> tương đối chung.<br /> B2: Giải bài toán min W với XD từ đó tìm<br /> được nghiệm tối ưu X0 và W0<br /> 215<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Lại Khắc Lãi và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 86(10): 213 - 218<br /> <br /> Trong trường hợp này, lợi ích tỷ lệ với độ lệch<br /> tương đối, phương án X1 là tốt hơn X2 nếu độ<br /> lệch tương đối chung của X1 nhỏ hơn X2.<br /> Phương pháp tìm nghiệm có khoảng cách nhỏ<br /> nhất đến nghiệm lý tưởng<br /> Phương pháp này giả định có một nghiệm lý<br /> tưởng , X1 tốt hơn X2 nếu khoảng cách từ X1<br /> đến nghiệm lý tưởng nhỏ hơn khoảng cách<br /> tương ứng của X2.<br /> Định nghĩa: Giả sử X1, X2 Rn, khoảng cách<br /> giữa X1 và X2 là số d xác định bởi:<br /> <br /> d   X i1  X i2  là tham số >1<br /> <br /> <br /> Khi đó bài toán maxY(X) với XD đưa về<br /> bài toán<br /> <br /> min<br /> <br />  Y ( X )  Y <br /> * <br /> <br /> i<br /> <br /> i<br /> <br /> Vấn đề xác định tham số  phụ thuộc vào<br /> từng bài toán.<br /> ỨNG DỤNG GIẢI THUẬT DI TRUYỀN<br /> CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU<br /> Đặt bài toán<br /> Giả sử điều khiển mức dung dịch H trong<br /> bình khuấy trộn theo sơ đồ điều khiển và sơ<br /> đồ khối như hình 1 dưới đây<br /> Trong đó:<br /> + Hàm truyền đạt của bộ chuyển đổi dòng<br /> điện – khí nén (I/P):<br /> K<br /> <br /> Hình 1. Sơ đồ điều khiển mức của bình trộn<br /> <br /> + Hàm truyền đạt của thiết bị đo mức: tín hiệu<br /> vào là khoảng cách và tín hiệu đầu ra là điện áp:<br /> <br /> WH ( s) <br /> <br /> 0,016<br /> 1  0,005s<br /> <br /> Bài toàn tối ưu đặt ra ở đây là thiết kế bộ<br /> điều khiển PD sao cho ổn định mức dung<br /> dịch H chính xác nhất và thời gian ổn định<br /> nhanh nhất, tương ứng với hai hàm mục tiêu<br /> như sau:<br /> <br />  KG / mm 2 <br /> Pmax 0,01  0,002<br /> <br />  0,5<br /> <br /> I max<br /> 20  4<br />  mA <br /> <br /> + Hàm truyền đạt của van: tín hiệu vào là áp<br /> suất khí nén và tín hiệu ra là lưu lượng nước<br /> cấp thông qua cơ cấu van:<br /> W1 (s)  WV T 1 (s) <br /> <br /> 50<br /> 125<br /> ; W2 ( s)  WV T 2 ( s) <br /> 1  0,01s<br /> 1  0,01s<br /> <br /> Hình 2. Sơ đồ khối điều khiển mức<br /> <br /> Mục tiêu 1: J1  e 2 (t )dt  min<br /> <br /> Mục tiêu 2: J 2   e(t )dt  min<br /> Từ hình 2 tính toán và rút ra được phương<br /> trình vi phân:<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> 216<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br /> Lại Khắc Lãi và Đtg<br /> 0,015.<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 86(10): 213 - 218<br /> <br /> d 2e<br /> de<br />  (1,4 K D  1)  1,4.K P .e  0<br /> dt 2<br /> dt<br /> <br /> Ta có phương trình đặc trưng là:<br /> 0,015.k 2  (1,4 K D  1)k  1,4.K P  0<br /> <br /> Với điều kiện   0 thì phương trình trên có<br /> một nghiệm riêng là<br /> <br /> e(t )  e k1t  e k 2 t<br /> Chọn 25  KP  100 suy ra 1,35  KD  50<br /> Trong đó:<br /> <br /> Hình 4. Kết quả mô phỏng với bộ thông số tối ưu<br /> KP = 25.895; KD = 18.349<br /> <br /> 2<br /> <br /> 1,4 K D  1  1,4 K D  1  0,084.K P<br />  k1  1,4 K D  1   <br /> <br /> 0.03<br /> 0.03<br /> <br /> 2<br /> <br /> 1,4 K D  1   1,4 K D  1  1,4 K D  1  0,084.K P<br /> <br />  k2 <br /> 0.03<br /> 0.03<br /> <br /> <br /> Thay t=3(s) cuối cùng ta có được bài toán tối<br /> ưu hai muc tiêu điều khiển mức dung dịch H<br /> như sau:<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> J1 <br /> <br /> 1 2 k1t<br /> 2<br /> 1 2 k2t<br /> e <br /> e k1  k2 t <br /> e  min<br /> 2k1<br /> k1  k2<br /> 2k 2<br /> <br />  ek1t ek2t<br /> J2  <br /> <br /> k2<br />  k1<br /> 25  K P  100<br /> <br /> <br />   min<br /> <br /> <br /> 1,35  K D  50<br /> <br /> Giải quyết bài toán<br /> Dùng thuật toán giải thuật di truyền viết trên<br /> phần mềm Matlab với quần thể khởi tạo ban<br /> đầu gồm 30 cá thể, sau các bước lai ghép,<br /> chọn lọc, đột biến giải bài toán đa mục tiêu<br /> trên ta thu được kết quả tối ưu của bộ giá trị<br /> (KP và KD) sau: KP = 25.895; KD = 18.349<br /> làm cho J1 và J2 min. Vậy đó chính là bộ giá<br /> trị tối ưu của bộ điều khiển PD trong sơ đồ<br /> điều khiển mức trên với lưu đồ thuật toán của<br /> giải thuật di truyền như hình 3.<br /> <br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> Hình 5. Kết quả mô phỏng với bộ thông số tối ưu<br /> và bộ thông số khác<br /> <br /> Các kết quả mô phỏng được chỉ ra trên hình 4<br /> và hình 5. Trong đó: Hình 4 ứng với các<br /> thông số tối ưu tìm được bằng giải thuật di<br /> truyền còn Hình 5 là đáp ứng quá độ ứng với<br /> bộ thông số tối ưu và nộ thông số khác.<br /> <br /> 217<br /> <br /> http://www.lrc-tnu.edu.vn<br /> <br />
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2