intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Kết hợp giải thuật di truyền với phân cụm loại trừ trong tối ưu hóa tham số điều khiển

Chia sẻ: Hoang Son | Ngày: | Loại File: PDF | Số trang:6

56
lượt xem
5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Dữ liệu trong các thiết bị điều khiển thường bị nhiễu bởi nhiều loại dữ liệu khác nhau. Việc hiệu chỉnh, tinh chỉnh và kiểm tra dữ liệu dùng trong các hệ thống điều khiển là cần thiết. Nghiên cứu này đề xuất phương pháp phân cụm loại trừ và giải thuật di truyền trong trích lọc dữ liệu từ một tập dữ liệu ban đầu. Thực hiện phân cụm để loại bỏ phần dư thừa, hình thành các luật làm tri thức đầu vào cho hệ điều khiển. Giải thuật di truyền là công cụ tìm kiếm, xác định các giá trị tối ƣu cho tập tham số điều khiển.

Chủ đề:
Lưu

Nội dung Text: Kết hợp giải thuật di truyền với phân cụm loại trừ trong tối ưu hóa tham số điều khiển

Trần Mạnh Tuấn và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 90(02): 87 - 92 KẾT HỢP GIẢI THUẬT DI TRUYỀN VỚI PHÂN CỤM LOẠI TRỪ TRONG TỐI ƢU HÓA THAM SỐ ĐIỀU KHIỂN Trần Mạnh Tuấn1*, Nguyễn Thị Linh1, Vũ Đình Minh2 Trường ĐH CNTT&TT, 2Trường CĐ Công nghiệp Thái Nguyên – ĐHTN TÓM TẮT Dữ liệu trong các thiết bị điều khiển thƣờng bị nhiễu bởi nhiều loại dữ liệu khác nhau. Việc hiệu chỉnh, tinh chỉnh và kiểm tra dữ liệu dùng trong các hệ thống điều khiển là cần thiết. Nghiên cứu này đề xuất phƣơng pháp phân cụm loại trừ và giải thuật di truyền trong trích lọc dữ liệu từ một tập dữ liệu ban đầu. Thực hiện phân cụm để loại bỏ phần dƣ thừa, hình thành các luật làm tri thức đầu vào cho hệ điều khiển. Giải thuật di truyền là công cụ tìm kiếm, xác định các giá trị tối ƣu cho tập tham số điều khiển. Từ khóa: Giải thuật di truyền, phân cụm loại trừ, trích lọc dữ liệu, hệ điều khiển, tham số điều khiển. MỞ ĐẦU* Mặc dù khả năng thực hiện của mô hình phụ thuộc rất nhiều vào chính bản thân mô hình, nhƣng có một thực tế rằng dữ liệu đóng một vai trò rất quan trọng trong xây dựng các mô hình chất lƣợng. Điều này càng đặc thù hơn cho một mô hình định hƣớng dữ liệu. Dữ liệu nhiễu sẽ cho kết quả trong một mô hình xây dựng không phù hợp. Khi đó, các mô hình điều khiển cần dữ liệu đƣợc chuẩn hóa. Nhƣ vậy, kết quả thu đƣợc từ mô hình điều khiển sử dụng dữ liệu chuẩn sẽ đƣa ra dự đoán tốt và đáng tin cậy. Trong các yêu cầu đặt ra cho quá trình phân cụm thì yêu cầu về độ chính xác luôn đƣợc đặt ra hàng đầu, ngoài ra sự kết hợp các thuật toán phân cụm và giải thuật di truyền còn đòi hỏi thỏa mãn đƣợc tính tối ƣu của các luật đƣợc sử dụng. Vì vậy một cách tiếp cận khác mà bài báo nêu ra đó là sử dụng phân cụm kết hợp với giải thuật di truyền để chuẩn hóa dữ liệu cho điểu khiển. Bài báo đƣợc tổ chức nhƣ sau: Phần 2 trình bày về hệ thống suy luận mờ, phƣơng pháp phân cụm và giới thiệu một số thuật toán phân cụm. Phần 3 trình bày về sử dụng giải thuật di truyền để tối ƣu hóa các luật đƣợc hình thành sau quá trình phân cụm. Cuối cùng, phần 4 đƣa ra kết quả cài đặt thực nghiệm chƣơng trình. * Tel: 098 3 668 841; Email: tmtuan@ictu.edu.vn MỘT SỐ VẤN ĐỀ CƠ SỞ Hệ thống suy luận mờ Giả sử với tập dữ liệu có p đầu vào và q đầu ra trong hệ luật mờ. Theo Mamdani[2] luật thứ i trong hệ gồm k luật đƣợc viết: i i Ri: If x1 is A1 and x2 is A2 and .. and xp is i i A p then y1 is C1 and y2 is C 2i and...and yq is C qi Trong đó: x j là các biến vào A ij là giá trị ngữ nghĩa của biến đầu vào yj là các biến ra C ij là giá trị ngữ nghĩa của biến đầu ra Khi K = 7, hàm thuộc với các giá trị ngữ nghĩa của hệ thống với 2 biến vào và một biến ra đƣợc miêu tả trên hình 2-1 và hình 2-2: Hình 2-1: Các giá trị ngữ nghĩa của biến đầu vào Các giá trị ngữ nghĩa của biến đầu ra trên hình 2-2: Hình 2-2: Các giá trị ngữ nghĩa của biến đầu ra 87 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Trần Mạnh Tuấn và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ Với hệ hai đầu vào và một đầu ra gồm 7 giá trị ngôn ngữ, thì sẽ có 72 = 49 luật cho xây dựng hệ suy diễn mờ. Bảng hệ thống luật mờ cho xây dựng hệ suy diễn mờ có thể thấy trên bảng 2-1: 90(02): 87 - 92 K Ekmeans  x X xi   h địa phƣơng. Thuật toán K-Means đƣợc thực hiện qua các bƣớc sau: (1). Khởi tạo các cụm: các tâm ban đầu K  h( 0) h1 đƣợc chọn ngẫu nhiên (2). Lặp cho tới khi hội tụ Gán cụm: Gán mỗi đối tƣợng dữ liệu x vào A2 A3 A4 A5 A6 A7 A1 C7 C7 C7 C7 C7 C7 C7 A2 C7 C6 C6 C6 C6 C6 C6 A3 C7 C6 C5 C5 C5 C5 C5 cụm h* (tức là tập A4 C7 C6 C5 C4 C4 C4 C4 argmin x   h(t ) A5 C7 C6 C5 C4 C3 C3 C3 A6 C7 C6 C5 C4 C3 C2 C2 A7 C7 C6 C5 C4 C3 C2 C1 Phƣơng pháp phân cụm Các thuật toán phân cụm thƣờng đƣợc biết tới nhƣ một cách tổ chức và phân loại dữ liệu hợp lý. Kết quả của phân cụm là một sự phân chia dữ liệu thành các nhóm tƣơng đồng. Sự phân chia không gian nhận đƣợc từ quá trình phân chia dữ liệu. Mỗi luật tƣơng ứng với một cụm trong đó các tập mờ không đƣợc chia sẻ bởi tập các luật mà với số chiều cho trƣớc, mỗi tập mờ đƣợc gắn với một luật duy nhất. Các tập mờ kết quả thƣờng rất khó để biểu diễn một cách rõ ràng. * Một số thuật toán phân cụm cứng + Thuật toán K-Means [2] K-Means lặp lại nhiều lần quá trình bố trí lại vị trí của đối tƣợng dữ liệu để phân hoạch một tập dữ liệu thành K cụm và cực tiểu địa phƣơng giá trị bình phƣơng trung bình khoảng cách giữa các đối tƣợng tới tâm cụm của nó. Cụ thể hơn, với tập dữ liệu X   xi i 1 , xi d thuật toán K-Means N tạo ra K phân hoạch  X h h 1 của X sao cho K nếu h h1 K mục tiêu sau: đại diện cho K tâm thì hàm đạt cực tiểu i h 1 A1 Bảng 2-1. Hệ thống luật mờ cho xây dựng hệ suy diễn mờ 2   X  ( t 1) K ) h* h 1 với h* = 2 Ƣớc lƣợng tâm:  h(t 1)  1 X h(t 1)  xX h( t 1) x t = t+1 + Thuật toán K-Medoids Thuật toán K-Medoids có khả năng khắc phục đƣợc nhiễu bằng cách chọn đối tƣợng ở gần tâm cụm nhất làm đại diện cho cụm đó (medoid). Thuật toán K-Medoids đƣợc thực hiện qua các bƣớc sau: (1). Chọn K đối tƣợng bất kỳ trong N đối tƣợng ban đầu làm các medoid ban đầu (2). Lặp cho tới khi hội tụ - Gán mỗi đối tƣợng còn lại vào cụm có medoid gần nhất với nó - Thay thế medoid hiện tại bằng một đối tƣợng không phải là medoid sao cho chất lƣợng phân cụm đƣợc cải thiện (Chất lƣợng đƣợc đánh giá sử dụng hàm chi phí, hàm tính độ phi tƣơng tự giữa một đối tƣợng và medoid của cụm chứa đối tƣợng đó). K-Medoids tỏ ra hiệu quả hơn K-Means trong trƣờng hợp dữ liệu có nhiễu hoặc đối tƣợng ngoại lai (Outlier). Nhƣng so với K-Means thì K-Medoids có độ phức tạp tính toán lớn hơn. Cả hai thuật toán trên để có nhƣợc điểm chung là số lƣợng cụm K đƣợc cung cấp bởi ngƣời dùng. 88 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Trần Mạnh Tuấn và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ * Thuật toán phân cụm mờ C – Means (FCM) [5] FCM đƣợc giới thiệu bởi Dunn vào năm 1973. Bezdek đã chứng minh các tính chất của nó và đề xuất tiêu chuẩn hợp lệ phân cụm đầu tiên. Mỗi n cặp dữ liệu thuộc về một trong c nhóm với một hệ số thành viên, u ik thể hiện mức độ thuộc của mẫu dữ liệu k trong cụm i. Cho Dik2 là khoảng cách giữa cặp dữ liệu k và cụm i, về cơ bản đƣợc xác định theo chuẩn Euclide và tổng quát hơn là: Dik2  xk  vi  xk  vi Axk  vi  2 T A Trong đó x k cặp dữ liệu thứ k đƣợc dùng cho việc phân cụm, A là một ma trận đối xứng, xác định dƣơng và v i là một nguyên mẫu của cụm. Cho U là ma trận hệ số u ik và V ma trận tọa độ trung tâm. Thuật toán sinh ra U và V làm cực tiểu hàm tổn thất sau: n c J FCM   u k 1 Với i 1 Dik2 ràng c u i 1 m ik ik buộc (1) xác suất:  1; k  1,..., n. và m  1 là mũ mờ. Sự tối ƣu hàm trên đƣợc thực hiện bằng một thủ tục tối ƣu lặp. Đầu tiên, các hệ số u ik đƣợc khởi tạo ngẫu nhiên, sau đó, tại mỗi bƣớc, hai thao tác sau đƣợc thực hiện thành công: (1). Tính toán các trung tâm cụm mờ v i , giả sử các bậc u ik là các hằng số, dùng phƣơng n trình sau: v  i u k 1 n m ik u k 1 xk m ik (2). Tính toán mức độ thuộc u ik , giả sử các trung tâm v i là các vector hằng, dùng phƣơng trình: 1 uik   Dik    j 1  D jk c 2  m1    90(02): 87 - 92 Các thao tác trên đƣợc lặp lại cho đến khi hội tụ, nghĩa là các tọa độ trung tâm là ổn định đối với sai số đã cho. Thuật toán phân cụm FCM thích hợp với các cụm với hình dạng và kích thƣớc có thể so sánh đƣợc (là hình cầu khi dùng ma trận đơn vị) hoặc khi các cụm đƣợc phân chia rõ ràng. Nguyên mẫu cụm là các điểm dữ liệu đƣợc chọn làm trung tâm cụm. Input : Số cụm k và tham số mũ m cho hàm tiêu chuẩn J OutPut: c cụm dữ liệu sao cho hàm mục tiêu (1) đạt giá trị tối thiểu. Begin (1). Nhập giá trị cho hai tham số k (1>pm2,pm3 để giảm số luật hiện diện trong mỗi cá thể nhằm tìm ra cá thể tốt, từ đó nhận đƣợc số tối thiểu các luật mà vẫn phân lớp đúng mẫu học. Phép lai ghép Là một phép toán quan trọng trong GA để tìm kiếm các tính chất hữu ích của cha mẹ. Mỗi cặp cá thể Sh, Sk đƣợc thực hiện lai ghép đều với xác suất pc nhƣ sau: - Chọn các cặp bit si1, i = 1, 2,…, L với xác suất 0.5, nếu bit si1 đƣợc chọn thì các cặp bit tiếp theo cũng đƣợc chọn (chọn đủ một luật). - Trao đổi các cặp bit đã chọn giữa 2 cá thể h S , Sk. - Hai cá thể con cháu mới do lai tạo sẽ đƣợc thay thế cho hai cá thể cha mẹ trong thế hệ kế tiếp. 90 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Trần Mạnh Tuấn và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ Phép chọn lọc Là quá trình cá thể đƣợc chọn dựa vào giá trị thích nghi của nó đối với mục tiêu cần đạt đƣợc bằng cách tạo một vòng quay đƣợc phân chia thành nhiều phần, mỗi phần thể hiện giá trị thích nghi của mỗi cá thể. Khi vòng quay quay, có một viên bi với giá trị ngẫu nhiên nhỏ hơn tổng các giá trị thích nghi di chuyển theo hƣớng ngƣợc lại. Khi vòng quay ngừng, viên bi dừng trên phần chia nào thì cá thể đó đƣợc chọn. Thuật toán đƣợc mô tả nhƣ sau: - Tính tổng: SUM   (ai (t )) L i 1 - Chọn một giá trị để so sánh: Sel [0;SUM] - Khởi tạo i = 1; - Kiểm tra:  While (Sel >  ( a i (t )) )  { Sel = Sel -  ( a i (t )) ; i = i+1; } select()=i; /* phần tử thứ i đƣợc chọn Chiến lƣợc phần tử ƣu tú: Luôn luôn chọn cá thể có giá trị thích nghi cao nhất trong thế hệ P(t) để đƣa trực tiếp vào thế hệ kế tiếp P(t+1) khi thực hiện phép toán chọn lọc nếu nó chƣa đƣợc chọn để đảm bảo các thế hệ kế tiếp không đánh mất truyền thống thích nghi tốt nhất và nhờ đó cải thiện sự tiến hóa một cách liên tục. Hiệu chỉnh độ tin cậy trong thuật giải GA Để tăng khả năng phân cụm đúng 100% các mẫu học với chỉ một số ít luật, cần phải thay đổi độ tin cậy của mỗi luật thông qua sự thƣởng, phạt từng luật bằng cách đƣa thêm một thủ tục hiệu chỉnh độ tin cậy vào quá trình thực hiện giải thuật di truyền. Với một mẫu dữ liệu học Xp và với số lần lặp xác định, độ tin cậy đƣợc tăng hay giảm phụ thuộc vào việc Xp đƣợc phân cụm đúng hay sai. Thủ tục nhƣ sau: Với mỗi mẫu dữ liệu học X p , p = 1, …, P thực hiện: - Xếp lớp cho Xp: 90(02): 87 - 92 • Tính độ tƣơng thích của mẫu Xp đối với từng cụm ci: k = max{uj1(xp1) uj2(xp2) …ujN(xpN)CFi|RjS,CFj=ci} • Nếu  i≠j mà Ci = Cj thì Xp không xếp cụm đƣợc Nếu ko = max{k ,k = 1, …, K } thì xếp mẫu Xp vào cụm Cko - Dùng công thức sau để xác định luật Ri chịu trách nhiệm phân lớp mẫu Xp i1 (xp1) i2(xp2) …iN(xpN). CFi = max{j1 (xp1) j2(xp2) …jN(xpN). CFj; RjS } Trong đó: ij(xpj): là hàm thành viên tập mờ Aij, i = 1, 2, …, n; j= 1, 2, …N. Nếu luật Ri xếp đúng lớp cho Xp thì tăng độ tin cậy của nó theo công thức: CFi = CFi + 1. (1- CFi) Nếu luật Ri xếp sai lớp cho Xp thì giảm độ tin cậy của nó theo công thức: CFi = CFi - 2.CFi Với: 1 và 2 là các hằng số trong khoảng (0;1). Đánh giá: Ƣu điểm: Làm tăng khả năng tìm ra cá thể có các luật phân lớp đúng 100% mẫu học. Nhƣợc điểm: Cá thể tốt nhất trong thế hệ trƣớc qua phép chọn phần tử ƣu tú có thể không còn là cá thể tốt nhất ở thế hệ sau do độ tin cậy các luật của nó đã bị điều chỉnh. KẾT QUẢ THỰC NGHIỆM Với dữ liệu đầu vào là một bảng dữ liệu (bảng 2-1): Hình 4-1: Dữ liệu nhập ban đầu 91 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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