Báo cáo Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi (Phần 1)

Nội dung text: Báo cáo Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG NGHIÊN CỨU ỨNG DỤNG THUẬT TOÁN PSO ĐỂ THIẾT KẾ BỘ LỌC NOTCHS K C 0 0 3 9 5 9 THÍCH NGHI MÃ SỐ: T2014-12 S KC 0 0 5 4 8 7 Tp. Hồ Chí Minh, 2014
2. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 A GIỚI THIỆU Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 1
3. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 I. TÍNH CẤP THIẾT CỦA ĐỀ TÀI Bộ lọc Notch (bộ lọc chắn dải) là một trong những giải pháp để lọc nhiễu tuần hoàn trong các ứng dụng y sinh: đo điện tim Từ bộ lọc sơ khởi ban đầu để tăng khả năng lọc nhiều loại nhiễu có tần số khác nhau ngƣời ta tích hợp tính thích nghi vào bộ lọc. Bộ lọc Notch thích nghi cổ điển thƣờng dùng thuật toán LMS (Least Mean Square) để thiết kế. Tuy nhiên tốc độ hội tụ của thuật toán này chậm có thể không đáp ứng kịp với sự thay đổi của nhiễu và khả năng của bộ lọc phụ thuộc rất nhiều vào bƣớc thích nghi (stepsize) . Thuật toán PSO (Practicle Swarm Optimization) là một dạng của thuật toán tiến hoá quần thể đƣợc ứng dụng giải bài toán tối ƣu. Việc ứng dụng thuật toán PSO vào việc thiết kế bộ lọc sẽ làm tăng đáp ứng và khả năng lọc nhiễu cho bộ lọc. II. MỤC TIÊU NGHIÊN CỨU Ứng dụng thuật toán PSO để thiết kế tăng chất lƣợng của bộ lọc Notch III. PHƢƠNG PHÁP NGHIÊN CỨU - Nghiên cƣ́ u lý thuyết. - Xây dựng mô hình mô phỏng. IV. PHẠM VI NGHIÊN CỨU - Nghiên cƣ́ u thiết kế bộ lọc dùng giải thuậtt PSO. - Mô phỏng bằng phần mềm Matlab. V. NÔỊ DUNG NGHIÊN CÚ U - Nghiên cƣ́ u về bộ lọc Notch. - Nghiên giải thuật PSO. - Xây dƣṇ g mô hình mô phỏng. Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 2
4. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 B NÔỊ DUNG Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 3
5. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 GIỚI THIỆU TỔNG QUAN TÌNH HÌNH NGHIÊN CỨU TRÊN THẾ GIỚI Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 4
6. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 Bộ lọc Notch, triệt tín hiệu nhiễu tại tần số mong muốn, thƣờng đƣợc ứng dụng để triệt tín hiệu nhiễu 50Hz của tín hiệu điện tim, điện não. Để tăng tính thích nghi, triệt đƣợc nhiễu tại những tần số khác, thuật toán thích nghi đƣợc sử dụng. Điển hình là thuật toán trung bình bình phƣơng tối thiểu (LMS – Least Mean Square). Ứng dụng thuật toán LMS vào bài toán lọc nhiễu đƣơc Bernard Widrow công bố rất sớm từ năm 1975 trên tạp chí IEEE trong bài báo “Adaptive Noise Canceling Principles and Applications”. Ngày nay, những nghiên cứu của ông vẫn đƣợc áp dụng rộng rãi trong những ứng dụng y sinh: điện não, điện tâm đồ. Thuật toán này với ƣu điểm đơn giản, nhƣng tốc độ hội tụ không cao, và phụ thuộc nhiều vào việc chọn bƣớc thích nghi. Chọn không đúng dẫn đến bài toán khó hội tụ, tốc độ hội tụ chậm, khả năng triệt nhiễu thấp. Thuật toán PSO (Particles Swarm Optization - giải thuật bầy đàn) đƣợc nghiên cứu và phát triển bởi Russell Eberhard và James Kennedy vào năm 1995 dựa vào mô phỏng hoạt động tìm kiếm thức ăn của bầy chim trong thức tế. Các cá thể tìm kiếm theo ngẫu nhiên, sau đó sẽ dùng tín hiệu để báo cho các cá thể còn lại địa điểm tìm đƣợc tốt nhất, cả đàn sẽ tập trung tìm kiếm ở địa điểm mới để tìm ra nơi tốt nhất. Thuật toán PSO là một thuật toán mạnh, đơn giản, không phụ thuộc nhiều vào việc lựa chọn thông số, không gian tìm kiếm rộng, tính hội tụ rất cao.Ứng dụng cho bộ lọc sẽ tăng tốc độ hội tụ, cải thiện khả năng triệt nhiễu và giảm yếu tố phụ thuộc của bài toán vào bƣớc thích nghi. Trên thế giới thuật toàn PSO áp dụng đƣợc thiết kế mạch lọc notch thích nghi đang và đã đƣợc nghiên cứu trong những năm gần đây và đƣợc đăng tải trên các tạp chí khoa học uy tín. “Research and application of the particle swarm optimization in adaptive notch filter design” Shi Haixia tạp chí IEEE 2009. “Application of Quantum Particle Swarm Optimization in Adaptive Notch Filter Design” Zhang Jie tạp chí Scientific.Net 2012. Giải thuật PSO còn đƣợc ứng dụng rộng rãi cho các bộ lọc khác “Analysis The IIR Filter Design Using Praticle Swarm Optimazation Method” Nehan Gupta tạp chí USRRS 2013. Tại Việt Nam, thông qua quá trình tra cứu trên internet bộ lọc Notch thích nghi đƣợc nghiên cứu với các giải pháp nhƣ cải tiến bƣớc thích nghi của thuật toán LMS Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 5
7. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 nhƣ luận án tiến sĩ, tác giả Hoàng Mạnh Hà Viện công nghệ thông tin năm 2011 đề tài “Các phương pháp thích nghi trong lọc nhiễu tín hiệu điện tim”. Pham Tran Nhu, Hoang Manh Ha, “Adjustment in central frequency of Adaptive Notch Filter base on Wavelet Transform in frequency Domain” Proceeding of the Second International Conference on Communications and Electronics (HUTICCE), Hoian, Vietnam, June 2008, nghiên cứu bộ lọc notch thích nghi dùng biến đổi Wavelet. Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 6
8. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 CHƢƠNG I: BỘ LỌC NOTCH THÍCH NGHI Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 7
9. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 I. TỔNG QUAN: 1. Bộ lọc Notch cơ bản Bộ lọc Notch, bộ lọc triệt tần, với thiết kế triệt một tần số, tần số đó chính là tần số nhiễu. Bộ lọc thƣờng đƣợc ứng dụng triệt nhiễu tại tần số 50Hz trong tín hiệu y sinh. Đáp ứng tần số của bộ lọc cơ bản đƣợc thể hiện ở hình vẽ f triệt Hình 1.1: Đáp ứng tần số của bộ lọc Notch Hàm truyền của bộ lọc có dạng nhƣ sau: (1.1) Trong đó: H0 là độ lợi của mạch lọc Q: hệ số phẩm chất của mạch lọc Tùy theo giá trị của tần số điểm zero z và tần số điểm cực 0 mà ta có các dạng mạch lọc khác nhau. Nếu z > 0 ta có mạch lọc notch có độ khuếch đại cao ở tần số thấp (lowpass notch filter), ngƣợc lại ta có high pass notch filter khi z < 0, khi z = 0 ta có mạch lọc notch tiêu chuẩn (standard notch filter). Các dạng đáp ứng tần số của mạch lọc notch đƣợc trình bày ở hình sau. Trong phạm vi bài nghiên cứu này, đo không có yêu cầu đặc biệt nên dạng mạch lọc notch tiêu chuẩn đƣợc sửa dụng. Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 8
10. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 Hình 1.2: Các dạng mạch lọc Notch 2. Bộ lọc thích nghi Thuật toán thích nghi là một thuật toán đƣợc sử dụng rộng rãi trong lĩnh vực tự động, các bộ điều khiển, lọc nhiễu Thuật toán xây dựng cho đối tƣợng tính thích nghi trƣớc những thay đổi thông số trong phạm vi nhất định của bài toán. Hình 1.3: Mô hình tổng quát của bộ lọc thích nghi Trong đó: Xk: tính hiệu đầu vào tại thời điểm k T Xk= [xk xk-1 . xk-L] Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 9
11. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 Xk là vector cột có độ dài L Wk: vector trọng số của bộ lọc thích nghi tại thời điểm k T Wk= [w0 w1 . wL] yk tín hiệu đầu ra tại thời điểm k T yk X k W k (1.2) dk tín hiệu mong muốn đạt đến k sai số giữa tín hiệu mong muốn dk và tín hiệu đầu ra yk. T  k d k y k d k X k W k (1.3) Từ tín hiệu đầu vào kèm nhiễu Xk, các thuật toán thích nghi sẽ chỉnh định ma trận trọng số Wk. Trọng số Wk sẽ đƣa vào bộ lọc nhằm tối thiểu sai số giữa tín hiệu ngõ ra mạch lọc yk và tín hiệu mong muốn không kèm nhiễu dk. Công thức cập nhật ma trận trọng số đƣợc chứng minh nhƣ sau: Bình phƣơng hai vế, lấy kỳ vọng 22 TTT  Ee k Ed k EWXXW k k k k 2 EdXW k k (1.4) Hình 1.4: Đồ thị hàm kì vọng Mặt đặc tính của  theo w1, w2. Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 10
12. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 x2 x x x x x x 0k 0 k 1 k 0 k 2 k 0 k Lk x x x2 x x x x T 1k 0 k 1 k 1 k 2 k 1 k Lk REXXE kk  xxLk0 k (1.5) Đặt T PEdX  kk Edx kkkkkk0 dx 1 dx 2  dx kLk  (1.6) Ta đƣợc 22 TT  E kk E d W RW 2 P W (1.7) Tính gradient của    22RW P (1.8) W Khi  → 0 thì sai số  nhỏ nhất. khi đó   2RW * 2 P 0 W Thì W*=R-1P (1.9) Cắt parabol  bằng những mặt phằng song song với mặt phẳng (w1, w2) ta sẽ đƣợc các elip đồng tâm và tâm của elip chính là điểm cực tiểu của Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 11
13. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 Hình 1.5: Mặt elip đồng tâm Qui tắc cập nhật trọng số sao cho trọng số ngày càng tiến tới giá trị W*, nghĩa là sai số ngày càng giảm dần đạt giá trị min. Để đƣợc nhƣ vậy thì qui luật cập nhật phải ngƣợc chiều với gradient  và tỷ lệ với một giá trị µ chính là bƣớc thích nghi. WWk 1 k   k (1.10) Nếu giá trị µ lớn thì bài toán nhanh hội tụ nhƣng sai số nhiều. Ngƣợc lại µ nhỏ bài toán sẽ chậm hội tụ 2 kk ww 00 2 kk ˆ  ww00 22k kX k  (1.11) 2 kk wwLL Từ các dẫn dắt trên, ta có công thức cập nhật trọng số ˆ WWWXk 1 k   k k 2  k k (1.12) Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 12
14. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 3. Mô hình bộ lọc Bernard Widrow Lấy mẫu Tín hiệu + nhiễu s(n) + n0(n) + e(n) s(t) + n0(t)  x W1 y(n) Tín hiệu 1k + k tham - x  chiếu 900 2k + x(t) W2k Dịch pha LMS Hình 1.6: Mô hình lọc nhiễu thích nghi Bernard Widrow Trong đó: s(t): tín hiệu chƣa bị nhiễu n0(t): nhiễu cộng ảnh hƣởng đến tín hiệu s(t) + n0(t): tín hiệu lẫn nhiễu thu đƣợc adaptive s(n) + n0(n): là tín hiệu lẫn nhiễu đã lấy mẫu x1, k: là tín hiệu nhiễu thu đƣợc đầu vào tham chiếu (reference input) sau khi lấy mẫu tại thời điểm k o x2,k: là trễ 90 của x1,k. x1,k; x2,k: đƣợc mô tả nhƣ sau: x1,k= Ccos(k0 + ). (1.13) x2,k= Csin(k0 + ). (1.14) y(n)= x1,kW1,k + x2,kW2,k. (1.15) e(n)= s(n) + n0(n) – y(n). (1.16) W1,k và W2,k: là hai thông số của bộ lọc Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 13
15. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 Bernard Widrow là tác giả đầu tiên đƣa ra mô hình bộ lọc nhiễu thích nghi Notch. Mô hình của ông đƣợc xem là tiền đề quan trọng và còn đƣợc sửa dụng rộng rãi cho tới ngày nay. Mô hình với ƣu điểm đơn giản và đƣợc xem là dạng mạch lọc thích nghi notch truyền thống. Thuật toán LMS điều chỉnh ma trận trọng số W sao cho có thể xấp xỉ gần đúng nhất với nhiễu n0(n) của tín hiệu từ tín hiệu nhiễu tham chiếu. Tín hiệu nhiễu tham chiếu có dạng hàm sin và cos. Tín hiệu nhiễu tham chiếu x(n)= Ccos(k0 + ) chứa tần số tín hiệu nhiễu cần triệt 0 và góc pha ban đầu tham chiếu . Yêu cầu là tín hiệu tham chiếu nhiễu không tƣơng quan với tín hiệu gốc nhƣng tƣơng quan với tín hiệu nhiễu. Ngõ ra mạch lọc e(n) là lệch giữa tín hiệu kèm nhiễu s(n) + n0(n) và tín hiệu nhiễu đã xấp xỉ y(n), cũng chính là tín hiệu y sinh đã triệt nhiễu. Thuật toán LMS cập nhật ma trận trọng số đƣợc Widrow và Hoff đề xuất: W1,k 1 W 1, k2 k x 1 k W2,k 1 W 2, k2 k x 2 k (1.17) Với µ là giá trị bƣợc thích nghi (stepsize) Hàm truyền mạch lọc trên nếu hội tụ sẽ có biểu thức nhƣ sau: 2 zz 2 cos0 1 Hz() 2 2 2 (1.18) z 2(1  C ) z cos 0 1 2  C j0 Với giá trị điểm zero ze (1.19) Và giá trị điểm cực 2 2 2 2 1/2 z (1  C )cos 00 j [(1 2  C ) (1  C ) cos  ] (1.20) Từ biểu thức của hàm truyền ta có thể thấy mạch lọc trên là dạng mạch lọc Notch Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 14
16. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 CHƢƠNG II: GIẢI THUẬT TỐI ƢU BẦY ĐÀN (PSO – PRACTICLE SWARM OPTIMIZATION) Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 15
17. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 I. GIỚI THIỆU Phƣơng pháp tối ƣu bầy đàn, đƣợc giới thiệu vào năm 1995 tại một hội nghị của IEEE bởi James Kennedy và kỹ sƣ Russell C. Eberhart, là một dạng của các thuật toán tiến hóa quần thể nhƣ thuật giải di truyền(Genetic algorithm (GA)), thuật toán đàn kiến(Ant colony algorithm). Điểm khác biệt của PSO so với GA là nó sử dụng sự tƣơng tác giữa các cá thể trong một quần thể để khám phá không gian tìm kiếm. PSO đƣợc xây dựng dựa trên việc mô hình hóa việc đàn chim bay đi tìm kiếm thức ăn nên nó đƣợc xếp vào các loại thuật toán có sử dụng trí tuệ bầy đàn . Thuật toán có nhiều ứng dụng trong các lĩnh vực cần giải quyết các bài toán tối ƣu hóa. Để hiểu rõ thuật toán PSO hãy xem một ví dụ đơn giản về quá trình tìm kiếm thức ăn của một đàn chim. Không gian tìm kiếm thức ăn là toàn bộ không gian ba chiều. Tại thời điểm bắt đầu tìm kiếm cả đàn bay theo một hƣớng ngẫu nhiên. Tuy nhiên sau một thời gian tìm kiếm một số cá thể trong đàn bắt đầu tìm ra đƣợc nơi có chứa thức ăn. Tùy theo số lƣợng thức ăn vừa tìm kiếm, mà cá thể gửi tín hiệu đến các các cá thể khác đang tìm kiếm ở vùng lân cận. Tín hiệu này lan truyền trên toàn quần thể. Dựa vào thông tin nhận đƣợc mỗi cá thể sẽ điều chỉnh hƣớng bay và vận tốc theo hƣớng về nơi có nhiều thức ăn nhất. Cơ chế truyền tin nhƣ vậy thƣờng đƣợc xem nhƣ là một kiểu hình của trí tuệ bầy đàn. Cơ chế này giúp cả đàn chim tìm ra nơi có nhiều thức ăn nhất trên không gian tìm kiếm vô cùng rộng lớn. Nhƣ vậy đàn chim đã dùng trí tuệ, kiến thức và kinh nghiệm của cả đàn để nhanh chóng tìm ra nơi chứa thức ăn. Thuật toán PSO sẽ ứng dụng quá trình phỏng sinh học (bioinspired) để xây dựng thuật toán tìm lời giải tối ƣu cho bài toán và đƣợc gọi là thuật toán phỏng sinh học (bioinspired algorithms). Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 16
18. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 II. GIẢI THUẬT Bài toán tối ƣu của hàm số F đƣợc xét trong không gian n chiều. Mỗi vị trí trong không gian là một điểm tọa độ n chiều. Hàm mục tiêu F(fitness function) đƣợc xác định trong không gian n chiều và nhận giá trị thực. Mục đích là tìm ra điểm cực tiểu của hàm F trong miền xác định nào đó. Giả sử rằng số lƣợng thức ăn tại một vị trí tỉ lệ nghịch với giá trị của hàm F tại vị trí đó. Có nghĩa là ở một vị trí mà giá trị hàm F càng nhỏ thì số lƣợng thức ăn càng lớn. Việc tìm vùng chứa thức ăn nhiều nhất tƣơng tự nhƣ việc tìm ra vùng chứa điểm cực tiểu của hàm F trên không gian tìm kiếm. PSO đƣợc khởi tạo bằng một nhóm cá thể (nghiệm) ngẫu nhiên và sau đó tìm nghiệm tối ƣu bằng cách cập nhật các thế hệ. Trong mỗi thế hệ, mỗi cá thể đƣợc cập nhật theo hai giá trị tốt nhất. Gía trị thứ nhất là nghiệm tốt nhất đạt đƣợc cho tới thời điểm hiện tại, gọi là Pbest. Một nghiệm tối ƣu khác mà cá thể này bám theo là nghiệm tối ƣu toàn cục Gbest, đó là nghiệm tốt nhất mà cá thể lân cận cá thể này đạt đƣợc cho tới thời điểm hiện tại. Nói cách khác, mỗi cá thể trong quần thể cập nhật vị trí của nó theo vị trí tốt nhất của nó và của cá thể trong quần thể tính tới thời điểm hiện tại. k c .rand ().(G – x ) 2 2 best(i) i p best(i) G best(i) k+1 v i k c .rand ().(p – x ) 1 1 besti i k w.v i Hình 2.1: Giải thuật PSO Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 17
19. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 Trong đó : k Xi : Vị trí cá thể thứ i tại thế hệ thứ k k Vi : Vận tốc cá thể i tại thế hệ thứ k k Xi : Vị trí cá thể thứ i tại thế hệ k +1 k Vi : Vận tốc cá thể i tại thế hệ thứ k + 1 Pbesti : Vị trí tốt nhất của cá thể thứ i Gbesti : Vị trí tốt nhất của cá thể trong quần thể Vận tốc và vị trí của mỗi cá thể đƣợc tính nhƣ sau : vk 1 wx k c rand() P x k c rand () G x k (3.1) i i1 1 besti i 2 2 besti i k 11 k k xi x i v i (3.2) Trong đó: w : trọng số quán tính c1, c2 : các hệ số gia tốc rand1, rand2 : số ngẫu nhiên giữa 0 và 1 Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 18
20. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 Bắt dầu Khởi tạo: Số cá thể , Số lần tìm kiếm w, c1, c2. Khởi tạo ngẫu nhiên: Vị trí cá thể Vận tốc cá thể Tính giá trị hàm fitness Cập nhật: Pbest, Gbest, vị trí, vận tốc cá thể Sai Kiểm tra tiêu chuẩn sai số Đúng Kết thúc Hình 2.2: Lƣu đồ giải thuật PSO Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 19
21. Đề tài nghiên cứ u khoa hoc̣ cấp trườ ng – T2014-12 CHƢƠNG III: ỨNG DỤNG GIẢI THUẬT PSO THIẾT KẾ BỘ LỌC NOTCH THÍCH NGHI Nghiên cứu ứng dụng thuật toán PSO để thiết kế bộ lọc Notch thích nghi 20
22. S K L 0 0 2 1 5 4