Luận văn Ứng dụng thuật toán tiến hóa ước lượng tham số điều khiển con lắc ngược

ự cân bằng, tháp vô tuyến, giàn khoan, công trình biểnKhi lý thuyết về các bộ điều khiển hiện đại ngày càng hoàn thiện hơn thì con lắc ngược là một trong những đối tượng được áp dụng để kiểm tra các lý thuyết đó. Con lắc ngược quay (hay còn gọi là con lắc Furura) là mô hình bao gồm một cánh tay quay trong mặt phẳng nằm ngang và một con lắc gắn vào cánh tay có thể xoay tự do trong mặt phẳng thẳng đứng. Mô hình được phát minh vào năm 1992 bởi Katsuhisa Futura và các đồng nghiệp. 2.2 Ứng dụng của hệ thống con lắc ngược quay Trong nghiên cứu hệ thống con lắc ngược quay là mô hình có tính phi tuyến cao nên được dùng để khảo sát, so sánh các lý thuyết điều khiển về thời gian đáp ứng, độ vọt lố, sai số xác lập. Từ cách điều khiển con lắc ngược ta có thể phát triển để điều khiển những hệ phức tạp hơn, ví dụ như :  Chân robot: khi robot dạng người đứng trên 1 chân sẽ tương đương với con lắc ngược, nguyên lý điều khiển robot không ngã tương tự như điều khiển con lắc.  Tàu vũ trụ: khi phóng lên không gian, phi thuyền có thể chệch khỏi quỹ đạo định sẵn. Nguyên lý điều khiển tương tự như con lắc (mong muốn góc nghiêng của phi thuyền so với phương quỹ đạo trong giới hạn cho phép).  Xe tự cân bằng: khá phổ biến hiện nay. 2.3 Tổng quan về các bài toán trên hệ thống con lắc ngược quay 2.3.1 Swingup (bật lên) Bài toán đưa con lắc từ vị trí cân bằng dưới lên vị trí cân bằng trên. Phương pháp được sử dụng để giải quyết bài toán này là phương pháp điều khiển năng lượng được đề xuất bởi K.Furura. 2.3.2 Cân bằng con lắc Bài toán giữ cho con lắc cân bằng ở vị trí cân bằng trên. Có rất nhiều phương 5 pháp để giải bài toán này bằng cách áp dụng nhiều bộ điều khiển tuyến tính cũng như phi tuyến khác nhau. Vị trí cân bằng trên Hình 2.2 Các vị trí đặc biệt của con lắc 2.4 Các nghiên cứu trong và ngoài nước công bố Đến nay đã có rất nhiều nghiên cứu sử dụng các giải thuật toán khác nhau để điều khiển hệ thống con lắc ngược quay như điều khiển tuyến tính hóa, điều khiển phi tuyến, điều khiển thông minh,  Hệ thống con lắc ngược quay KRi – PP300, được thiết kế và chế tạo bởi nhà sản xuất Kent Ridge Instruments Pte.Ltd. dựa trên sự hợp tác với Trường đại học công nghệ Nanyang, Singapore. Hệ thống này đã được ứng dụng, sử dụng tại nhiều phòng thí nghiệm thuộc các viện nghiên cứu, nhiều trường Đại học kỹ thuật trên thế giới, trong đó Việt Nam. Đây là hệ thống phục vụ cho công việc nghiên cứu một số thuật toán điều khiển trong nhiều ứng dụng từ cơ bản đến phức tạp như: điều khiển con lắc ở vị trí ổn định dưới, cân bằng con lắc, swing up và cân bằng con lắc, swing up và cân bằng con lắc ở vị trí bất kì cho trước, Vị trí cân bằng dưới 6 Hình 2.3 Hệ thống KRi – PP300  Trong một báo cáo ở Tạp chí Quốc tế về Khoa học, Kỹ thuật và Nghiên cứu Công nghệ (IJSETR), Tập 3, Số 10, tháng 10 năm 2014 với đề tài “Modeling and Controller Designing of Rotary Inverted Pendulum (RIP)-Comparison by Using Various Design Methods”[3], 2 tác giả Mr.Kurella Pavan Kumar và Prof.Dr.G.Vsiva KrishnaRao đã tiến hành mô phỏng, thiết kế và so sánh 2 bộ điều khiển hiện đại trên mô hình con lắc ngược quay là Full State Feedback (FSF) và Linear Quadratic Regulator (LQR) trong bài toán swingup và cân bằng con lắc. Kết quả nghiên cứu cho thấy, bộ điều khiển LQR là tốt hơn trong chế độ swing up, trong khi để cân bằng con lắc tại vị trí thẳng đứng thì cả hai bộ điều khiển đều đáp ứng tốt.  Trong một báo cáo khác ở Tạp chí Quốc tế về điều khiển mô hình hóa và mô phỏng (IJCCMS) Tập 3, số 1 2, tháng 6 năm 2014 với đề tài “A Comparative study of controllers for stabilizing a Rotary Inverted Pendulum” [4], 2 tác giả Velchuri Sirisha và Dr. Anjali.S. Junghare đến từ trường đại học Visvesvaraya National Institute of Technology, Ấn Độ đã so sánh 4 mô hình toán điều khiển PID, LQR, Fuzzy Logic và H∞ trong môi trường Matlab Simulink và trong phòng thí nghiệm. Kết quả cho thấy trong môi trường mô phỏng thì bộ điều khiển Fuzzy Logic có độ vọt lố và thời gian tăng (63% giá trị xác lập) ít hơn 3 bộ điều khiển còn lại trong khi ở môi trường phòng thí nghiệm thì bộ điều khiển LQR có độ vọt lố và thời gian tăng ít nhất. Ngoài ra còn có một số đề tài nghiên cứu khác như: 7  Md.AkhtaruzzamanandA.A.Shafie,(2010),“Modeling and Controlofa Rotary Inverted Pendulum Using Various Methods, Comparative Assessment and Result Analysis” [5], Proceeding softhe 2010 IEEE, International Conferenceon Mechatronics and Automation, Xi'an, China.  Hassanzadeh, I., Mobayen, S. (2011), “Controller design for rotary inverted pendulum system using evolutionary algoritms”[6], Hindawi Publishing Corporation Mathematical Problems in Enginnering. 8, pp.1 -11.  Tại trường Đại học Bách Khoa TP.HCM có công trình nghiên cứu Bộ điều khiển mờ giữa cân bằng con lắc ngược quay dùng giải thuật di truyền. Con lắc cân bằng chưa ổn định tuyệt đối do thiết kế điều khiển sai số các tham số  MOHD RAHAIRI BIN RANI với đề tài: Tối ưu hóa đa mục tiêu số điều khiển PID sử dụng thuật toán di truyền kết quả chưa ổn định tuyệt đối. Từ các kết quả nghiên cứu ở trên dựa trên lý thuyết điều khiển LQR và GA – PID tác giả chọn phương pháp điều khiển LQR và GA-PID để ổn định cho hệ con lắc ngược quay và so sánh thời gian ổn định của hệ khi sử dụng các phương pháp điều khiển. 2.5 Nhiệm vụ và mục tiêu của luận văn. 2.5.1 Nhiệm vu  Tìm hiểu tổng quan về hệ thống con lắc ngược quay.  Tính toán, thiết kế và chế tạo mô hình con lắc ngược quay.  Thiết kế bộ điều khiển để điều khiển mô hình con lắc ngược quay.  Sử dụng bộ điều khiển đã thiết kế để điều khiển mô hình con lắc ngược quay đã chế tạo.  So sánh, đánh giá và rút ra kết luận. 2.5.2 Mục tiêu  Thiết kế và chế tạo được một mô hình con lắc ngược quay.  Thiết kế luật điều khiển cho mô hình đã chế tạo.  Kiểm nghiệm luật điều khiển trên mô hình đã chế tạo. 8 Chương 3: CƠ SỞ LÝ THUYẾT Mô hình toán học hệ con lắc ngược quay được xây dựng trên cơ sở các định luật cân bằng lực của Newton, phương trình Euler cho chuyển động quay và phương trình cân bằng năng lượng của con lắc. Sau đó tuyến tính hóa mô hình toán học. 3.1 Giới thiệu sơ lược hệ thống con lắc ngược quay Hệ thống con lắc ngược là một vấn đề điều khiển cổ điển nó được sử dụng trong các trường đại học trên khắp thế giới, nó là mô hình phù hợp để kiểm tra các thuật toán điều khiển phi tuyến cao. Mô hình hệ thống con lắc ngược quay gồm hai phần: cánh tay, gắn vào động cơ DC quay quanh trục thẳng đứng và con lắc (khớp quay tự do) gắn vào trục encoder ở cuối cánh tay tự do, trong mặt phẳng vuông góc với cánh tay. Con lắc ngược là hệ thống không ổn định nó luôn ở vị trí buông thõng ngã xuống, trừ khi có lực tác động thích hợp vào cánh tay. Bài toán đặt ra là điều khiển cánh tay để swing-up sao cho con lắc ổn định ở vị trí cân bằng thẳng đứng hướng lên trên. Hình 3.1 Mô hình hệ thống con lắc ngược quay Mô hình mô phỏng được dựa theo phương trình động lực học của hệ thống con lắc ngược quay. Đồng thời bộ điều khiển cơ bản cũng được trình bày trong phần tiếp theo của chương này. Mục đích của việc trình bày con lắc ngược trong mô phỏng là để kiểm chứng lại lý thuyết từ các mô hình toán. Từ đây có để đánh giá được sự ổn định của hệ thống con lắc ngược quay trong lý thuyết. 9 3.2 Thiết lập mô hình toán học hệ thống con lắc ngược quay 3.2.1 Động cơ DC Hình 3.2 Sơ đồ mạch điện tương đương của động cơ DC Trong đó:  Vin: Là điện áp cấp cho động cơ V  Im: Là cường độ dòng điện qua động cơ A  Rm: Là điện trở của động cơ Ω  Lm: Là điện cảm của cuộn dây trong động cơ H  : Là sức điện động tạo ra trong động cơ có độ lớn ̇ V Áp dụng định luật Kirchhoff 2 cho sơ đồ trên ta được: Vin = VR + VL + Vemf = ImRm + Lm ̇ (3.1) Trong đó:  VR: Là điện áp giữa 2 đầu điện trở Rm (V)  VL: Là điện áp giữa 2 đầu cuộn dây Lm (V)  Vemf: Là điện áp tạo ra trong rotor (V)  Km: Là hằng số của động cơ (Vs)  : Là góc của motor (rad) Ta có: Tm = K Im là moment của động cơ; đặt K = Km Im= Giả sử ảnh hưởng của cuộn từ cảm Lm là không đáng kể. Ta có thể viết lại phương trình (3.1) như sau: Vin = ̇ (V) 10 Với: Tm= ̇ (3.2) Ta có phương trình cân bằng moment trên trục động cơ: Tm = T1 + B ̇ ̈ (3.3) Trong đó:  T1: là moment tải quy đổi về trục động cơ.  B: là hệ số ma sát.  J: là moment quán tính động cơ và moment quán tính của hệ thống quy đổi về trục động cơ. Quy đổi moment động cơ về trục làm việc: ́ (3.4) Trong đó:  Kg: là tỉ số truyền  là hiệu suất của cơ cấu  là vị trí của trục tải Ta có: moment tải quy đổi về trục làm việc, giả sử bỏ qua ma sát ta được: T1 = ̈ (3.5) 3.2.2 Mô hình hóa hệ thống con lắc ngược quay Con lắc ngược quay được thể hiện trên hình 3.3, và được sử dụng như các tọa độ tổng quát mô tả cho hệ thống con lắc ngược quay. Con lắc di chuyển với một góc trong khi cánh tay quay một góc . Giả sử trọng tâm của con lắc ở điểm B, điểm A được gắn trên cánh tay là giao điểm của tọa độ xyz. 11 Hình 3.3 Cấu trúc hình học hệ con lắc ngược quay Cánh tay quay trên mặt phẳng ngang xz và con lắc quay trên mặt phẳng đứng xy, ta có thể vẽ những lực như trên hình 3.4. Hình 3.3 vận tốc ở điểm B trên con lắc có mối liên hệ tới điểm A trên cánh tay là: ̇ ̇ (3.6) ̇ ̇ Con lắc di chuyển cùng với sự quay của cánh tay với vận tốc là r ̇. Do đó, vận tốc tuyệt đối của điểm B trên con lắc là: { ̇ ̇ ̇ ̇ ̇ (3.7) Hình 3.4 Sơ đồ phân tích lực của hệ con lắc ngược quay a) Sơ đồ phân tích lực trên cánh tay b) Sơ đồ phân tích lực trên con lắc 12 Phương trình (3.7) là theo thời gian, ta có gia tốc của điểm B { ̈ ̇ – ̈̈ ̈ ̇ ̈ (3.8) Áp dụng định luật 2 Newton trên con lắc theo hướng x, ta được. M ̈ ∑ hay: mr ̈ ̇ – ̈ (3.9) Áp dụng định luật 2 Newton trên con lắc theo hướng y, ta được. m ̈ ∑ hay: -mLcos( ̇ ̈ -mg hay: mg – mLcos( ̇ ̈ (3.10) Áp dụng phương trình Euler cho chuyển động quay của con lắc về điểm B, ta được: ̈ ∑ hay: ̈ Hay: ̈ Lcos( (3.11) Áp dụng phương trình Euler cho chuyển động quay của cánh tay về điểm O, ta được: ̈ ∑ hay ̈ ̇ (3.12) Thay thế phương trình (3.9) và (3.10) vào (3.11), ta có được vế trái: ̈ [ ̈ ̇ ̈] +[ ̇ ̈] ̈ [ ̈ ̇ ̈] +[ ̇ ̈] -mLrcos( ̈ m ̈ ̈ (3.13) Thế (3.9) vào (3.12), ta được: ̈= ̇ [ ̈ ̇ ̈] ̈ - ̇ [ ̈ ̇ ̈] ( ̈- mLrcos( ̈ ̇ ̇ (3.14) Ta có được hệ phương trình chuyển động của hệ thống. 13 { ( ) ̈ ̈ ̇ ̇ ̈ ̈ (3.15) Động năng của hệ thống được sinh ra từ cánh tay quay và con lắc là: W = ̇ ̇ ̇ ̇ = ̇ [ ̇ ̇] [ ̇] ̇ = ( ̇ ̇ ̇ ̇ (3.16) Trong đó: là momen quán tính của con lắc. Lấy mặt phẳng nằm ngang là mặt phẳng quay của cánh tay coi như là mặt phẳng mốc, ta thấy chỉ có lực trọng trường là thế năng của hệ thống: V (3.17) Ta có hai tọa độ tổng quát là và , do đó ta có được hai phương trình theo Lagrange là: { ( ̇ ) ̇ ( ̇ ) (3.18) Moment quán tính của tải tại trục làm việc là T1: ̈ = ̇ ̈ = ̇ ̈ (3.19) Thế (3.19) vào (3.15), ta có được mô hình phi tuyến của hệ thống như sau: ̈ ̈ ̇ = = ̇ ̈ ̇ ( ̈ ̈ ̇ ( ) ̇ = ̈ m ̈ (3.20) Với: 14 a = b = mLr c = d = mLg e = f = Ta được: ̈ ̈ ̇ (3.21) -bcos( ̈ + c ̈ (3.22) Là hệ phương trình phi tuyến của hệ thống con lắc ngược quay. 3.3 Tuyến tính hóa từ mô hình phi tuyến Sử dụng phương pháp sai lệch nhỏ, theo phương pháp này việc tuyến tính hoá được thực hiện bằng cách khai triển hàm phi tuyến thành chuỗi Taylor tại vùng lân cận điểm ổn định (tương ứng với chế độ xác lập). Chỉ khảo sát các sai lệch bậc nhất trong chuỗi đó. Sai lệch so với trạng thái ổn định càng nhỏ thì việc đánh giá các quá trình của phần tử phi tuyến có sai số càng bé sau khi biến đổi tuyến tính. Cho n biến: n = được rút gọn như sau: y = ̅ ̅ ̅ ̅ ̅ Ta có: y- ̅ ̅ || ̅ ̅ ̅ ̅ || ̅ ̅ ̅ ̅ || ̅ ̅ ̅ Sử dụng kỹ thuật phân tích ở trên, mô hình được tuyến tính hóa như sau: Giả sử và ̇ Đặt: 15 ̇ ̅ ̅ Từ phương trình (3.21) ta đặt: y = ̈ ̈ ̇ = ̈ ̅ ̈ ̈ ̇ Với: ̈ ̇ | ̇ ̇ ̇ ̇ | ̇ y- ̅ | ̇ ̇ ̇ | ̇ y ̅ | ̇ ̇ ̇ | ̇ = a ̈- b ̈ ̇ Do đó, từ phương trình (3.21) ta có phương trình tuyến tính hóa là: a ̈- b ̈ ̇ Hay: a ̈- b ̈ ̇ (3.23) Từ phương trình (3.22) ta đặt: y = ̈ ̈ = ̈ ̅ ̈ ̈ ̈ | ̇ 16 ̇ = 0 y- ̅ | ̇ ̇ ̇ | ̇ y ̅ | ̇ ̇ ̇ | ̇ y = - b ̈ ̈ Do đó, từ phương trình (3.22) ta có phương trình tuyến tính hóa là: - b ̈ ̈ (3.24) Từ hai phương trình (3.23) và (3.24) ta nhận được mô hình tuyến tính hóa của hệ thống như sau: { ̈ ̈ ̇ ̈ ̈ (3.25) Từ phương trình (3.21) và (3.22) ta suy ra hai đại lượng là ̈ và ̈, ta được giải pháp từ mô hình phi tuyến: ̈ | ̇ ̇ | ̈ | ̇ | ̈ * [ ̇ ̇ ] (3.26) ̈ [ ̇ ̇ ] (3.27) Từ phương trình (3.25) ta suy ra hai đại lượng là ̈ và ̈ ̈ | ̇ | ̇ ̈ | ̇ – | ̇ (3.28) Suy ra hệ phương trình biến trạng thái của hệ con lắc ngược quay: 17 [ ̇ ̈ ̇ ̈ ] [ ] [ ̇ ̇ ̇ ]+ [ ] (3.29) Biến đổi Laplace mô hình tuyến tính hóa của hệ thống (phương trình 3.25) ta được: { (3.30) Ở trên ta xét là các điều kiện ban đầu giả sử là zero. Từ phương trình 3.30 ta có mối quan hệ giữa vị trí mong muốn của con lắc và điện áp đầu vào của đáp ứng như sau: (3.31) Đây là mô hình của hệ thống con lắc ngươc quay Bảng 3.1 Thông số hệ thống Ký hiệu Mô tả Giá trị Thành phần X của lực tác động lên con lắc ở điểm A Thành phần Y của lực tác động lên con lắc ở điểm B A Vị trí của con lắc ̇ Tốc độ của con lắc ̈ Gia tốc của con lắc Hệ số ma sát nhớt 0.004 G Gia tốc trọng trường 9.81 Dòng điện vào mạch phần ứng động cơ DC Là moment quán tính của con lắc quy về trọng tâm Là moment quán tính của cánh tay và con lắc về trục của 0.0035842 Moment quán tính của động cơ DC 67.7x Tỉ số truyền từ động cơ qua tải 102/16 Hằng số phản hồi 36.4x L ½ chiều dài con lắc 10x Điện cảm phần ứng m Khối lượng của con lăc 50x (Kg) 18 r Bán kính quay của cánh tay 10x (m) Điện trở phần ứng 1.11 (Ω) Moment xoay của tải Moment xoay của động cơ Vị trí góc của cánh tay và của trục tải ̇ Vộc tốc của trục tải ̈ Gia tốc của trục tải Vị trí của trục động cơ Điện áp phản hồi Điệm áp vào phần ứng Là hiệu suất của bộ truyền 0.9 ̇ Vận tốc của con lắc ở trọng tâm theo hướng X ̇ Vận tốc của con lắc ở trọng tâm theo hướng Y ̈ Gia tốc của con lắc ở trọng tâm theo hướng X ̈ Gia tốc của con lắc ở trọng tâm theo hướng Y Với giá trị cụ thể ở bảng 1.1 , tính các giá trị a, b, c, d, e, f: a = a = 4.296* b = mLr = 0.05 * 0.1* 0.1 = 5* c = d = mgL = 0.05* 9.81 * 0.1 = 0.04905 e = e = 0.004 + ( ) f = 3.4 Lý thuyết về giải thuật toán tiến hóa GA (Genetic Algorithm) 3.4.1 Giới thiệu Thuật toán di truyền là thuật toán tối ưu ngẫu nhiên dựa trên cơ chế chọn lọc 19 tự nhiên và tiến hóa di truyền. Nguyên lý cơ bản của thuật toán di truyền đã được Holland giới thiệu vào năm 1962. Cơ sở toán học đã được phát triển từ cuối những năm 1960 và đã được giới thiệu trong quyển sách đầu tiên của Holland, Adaptive in Natural and Artificial Systems. Thuật toán di truyền được ứng dụng đầu tiên trong hai lĩnh vực chính: tối ưu hóa và học tập của máy. Trong lĩnh vực tối ưu hóa thuật toán di truyền được phát triển nhanh chóng và ứng dụng trong nhiều lĩnh vực khác nhau như tối ưu hàm, xử lý ảnh, bài toán hành trình người bán hàng, nhận dạng hệ thống và điều khiển. Thuật toán di truyền cũng như các thuật toán tiến hóa nói chung, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa 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ể 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 hóa 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 bởi tính kế thừa và đấu tranh sinh tồn. 3.4.2 Các tính chất đặc thù của thuật toán di truyền.  GA lập luận mang tính chất ngẫu nhiên (stochastic) thay vì xác định (determinstic) như toán học giải tích.  GA xét duyệt toàn bộ các giải pháp, sau đó lựa chọn giải pháp tốt nhất dựa trên hệ số thích nghi.  GA chỉ tập trung vào giải pháp (dãy số tượng trưng cho giải pháp) mà không cần quan tâm đến chi tiết vấn đề.  GA thích hợp cho việc 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. 3.4.3 Các phép toán của thuật toán di truyền 3.4.3.1 Tái sinh (Reproduction) Tái sinh là quá trình chọn quần thể mới thỏa phân bố xác suất dựa trên độ thích nghi. Độ thích nghi là một hàm gán một giá trị thực cho cá thể trong quần thể. Các cá thể có độ thích nghi lớn sẽ có nhiều bản sao trong thế hệ mới. Hàm thích nghi có thể không tuyến tính, không đạo hàm, không liên tục bởi vì thuật toán di truyền chỉ cần liên kết hàm thích nghi với các chuỗi số. 20 Quá trình này được thực hiện dựa trên bánh xe quay roulette (bánh xe xổ số) với các rãnh được xác định kích thước theo độ thích nghi. Kỹ thuật này được gọi là lựa chọn cha mẹ theo bánh xe Roulette. Bánh xe Roulette được xây dựng như sau (giả định rằng, các độ thích nghi đều dương, trong trường hợp ngược lại thì ta có thể dùng một vài phép biến đổi tương ứng để định lại tỷ lệ sao cho các độ thích nghi đều dương). - Tính độ thích nghi i= 1 của mỗi nhiễm sắc thể trong quần thể hiện hành, với n là kích thước của quần thể (số nhiễm sắc thể trong quần thể). - Tìm tổng giá trị thích ghi toàn quần thể F = ∑ - Tính xác suất chọn cho mỗi nhiễm sắc thể: - Tính vị trí xác suất của mỗi nhiễm sắc thể: ∑ Tiến trình chọn lọc được thực hiện bằng cách quay bánh xe roulette n lần, mỗi lần chọn một nhiễm sắc thể từ quần thể hiện hành vào quần thể mới theo cách sau: - Phát sinh ngẫu nhiên một số r trong khoảng [0÷1] khi quay bánh xe. - Nếu r < thì chọn nhiễm sắc thể đầu tiên; ngược lại thì chọn nhiễm sắc thể thứ i sao cho < r ≤ Ví dụ 1: Xét bài toán dân số có 6 nhiễm sắc thể với chuỗi mã hóa và hệ số thích nghi tương ứng cho trong bảng 3.1. Bảng 3.2 Các nhiễm sắc thể và các giá trị thích nghi. Nhiễm sắc thể Chuỗi mã hóa Trị thích ghi (i) 1 01110 8 2 11000 15 3 00100 2 4 10010 5 5 01100 12 6 00011 8  Giá trị tổng thích ghi toàn quần thể là: F =∑  Tính xác suất chọn của mỗi nhiễm sắc thể 21  Tính vị trí xác suất = ∑ Kết quả thu được điền vào bảng 3.3 Bảng 3.3 Kết quả tính toán cho các nhiễm sắc thể. Nhiễm sắc thể Chuỗi mã hóa Trị thích ghi Xác suất chọn Vị trí xác suất 1 01110 8 0.16 0.16 2 11000 15 0.3 0.46 3 00100 2 0.04 0.5 4 10010 5 0.1 0.6 5 01100 12 0.24 0.84 6 00011 8 0.16 1 Bây giờ ta quay bánh xe roulette 6 lần, mỗi lần chọn một nhiễm sắc thể cho quần thể mới. Giá trị ngẫu nhiên của 6 số trong khoảng [0÷1] và các nhiễm sắc thể tương ứng được chọn, cho trong bảng 3.2. Hình 3.5 Bánh xe Roulette Bảng 3.4 Quần thể mới Số lần quay 1 2 3 4 5 6 Số ngẫu nhiên 0.55 0.1 0.95 0.4 0.8 0.7 Nhiễm sắc thể 4 1 6 2 5 5 22 Ta thấy: Lần 1: r1= 0.55 > q1= 0.16 và q3 < r <q4 nên ta chọn NST 4 Lần 2: r2= 0.1 < q1 = 0.16 nên ta chọn NST 1 Tương tự cho các lần quay còn lại, ta có sẽ được một quần thể mới. Ta thấy, có thể sẽ có một số nhiễm sắc thể được chọn nhiều lần, các nhiễm sắc thể có độ thích nghi cao hơn sẽ có nhiều bản sao hơn, các nhiễm sắc thể có độ thích nghi kém nhất thì dần dần chết đi. Sau khi lựa chọn được quần thể mới, bước tiếp theo trong thuật toán di truyền là thực hiện các phép toán lai ghép và đột biến. 3.4.3.2 Lai ghép (Crossover) Phép lai là quá trình hình thành nhiễm sắc thể mới trên cơ sở các nhiễm sắc thể cha - mẹ, 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. Phép lai xảy ra với xác suất pc, được thực hiện như sau:  Đối với mỗi nhiễm sắc thể trong quần thể mới, phát sinh ngẫu nhiên một số r trong khoảng [0÷1], nếu r < pc thì nhiễm sắc thể đó được chọn để lai ghép.  Ghép đôi các nhiễm sắc thể đã chọn được một cách ngẫu nhiên, đối với mỗi cặp nhiễm sắc thể được ghép đôi, ta phát sinh ngẫu nhiên một số nguyên pos trong khoảng [0÷m-1] (m là tổng chiều dài của một nhiễm sắc thể - tổng số gen). Số pos cho biết vị trí của điểm lai. điều này được minh họa như sau: Vị trí lai Hình 3.6 Số pos cho biết vị trí của điểm lai 23 - Chuyển đổi các gen nằm sau vịtrí lai. Hình 3.7 Chuyển đổi các gen nằm sau vị trí lai Như vậy phép lai này tạo 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. Mặc dù phép lai ghép sử dụng lựa chọn ngẫu nhiên, nhưng nó không được xem như là một lối đi ngẫu nhiên qua không gian tìm kiếm. Sự kết hợp giữa tái sinh và lai ghép làm cho thuật toán di truyền hướng việc tìm kiếm đến những vùng tốt hơn. 3.4.3.3 Độ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ẹ. Phép đột biến xảy ra với xác suất pm, nhỏ hơn rất nhiều so với xác suất lai pc. Theo nghiên cứu của Kenneth De Jong thì:  Tỉ lệ lai ghép trung bình: 0.6  Tỉ lệ đột biến: 0.001  Tỉ lệ tạo sinh: 0.399 Mỗi gen trong tất cả các nhiễm sắc thể có cơ hội bị đột biến như nhau, nghĩa là đối với mỗi nhiễm sắc thể trong quần thể hiện hành (sau khi lai) và đối với mỗi gen trong nhiễm sắc thể, quá trình đột biến được thực hiện như sau: - Phát sinh ngẫu nhiên một số r trong khoảng [0÷1] - Nếu r < pm, thì đột biến gen đó. Đột biến làm tăng khả năng tìm được lời giải gần tối ưu của thuật toán di truyền. đột biến không được sử dụng thường xuyên vì nó là phép toán tìm kiếm ngẫu nhiên, với tỷ lệ đột biến cao, thuật toán di truyền sẽ còn xấu hơn phương pháp tìm kiếm ngẫu nhiên. 24 Sau quá trình tái sinh, lai và đột biến, quần thể mới tiếp tục được tính toán các giá trị thích nghi, sự tính toán này được dùng để xây dựng phân bố xác suất (cho tiến trình tái sinh tiếp theo), nghĩa là, để xây dựng lại bánh xe roulette với các rãnh được định kích thước theo các giá trị thích nghi hiện hành. Phần còn lại của thuật toán di truyền chỉ là sự lặp lại chu trình của những bước trên. 3.4.3.4 Hàm thích nghi (Fitness) Ta xây dựng hàm thích nghi f(x) nhận giá trị không âm. Có 2 trường hợp:  Đối với bài toán tìm cực tiểu hàm g(x) (x) = { Có thể lấy Cmax là giá trị g lớn nhất trong quần thể hiện tại.  Đối với bài toán tìm cực đại hàm g(x) (x) = { Có thể lấy Cmin là trị tuyệt đối của u bé nhất trong quần thể hiện tại. 3.4.4 Cấu trúc của thuật toán di truyền tổng quát Thuật toán di truyền bao gồm các bước sau: Bước 1: Khởi tạo quần thể các nhiễm sắc thể. Chọn mô hình cho giải pháp của vấn đề. Chỉ định cho mỗi giải pháp một ký hiệu. Bước 2: Tìm hàm thích nghi và xác định giá trị thích nghi 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 (tạo sinh) và tạo ra những nhiễm sắc thể mới bằng các phép toán di truyền (lai ghép hay đột biến). Bước 4: Tính hệ số thích nghi cho các thành viên mới để loại bỏ những thành viên không phù hợp trong quần thể. Bước 5: Nếu chưa tìm được giải pháp tối ưu thì trở lại bước 3. Nếu mục tiêu tìm kiếm đã đạt được thì dừng lại. Báo cáo kết quả. 25 Hình 3.8 Cấu trúc của thuật toán di truyền 3.4.5 Kết luận Thuật toán di truyền đã chứng tỏ tính hữu ích của nó khi được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau của cuộc sống. Trong lĩnh vực điều khiển tự động, thuật toán di truyền có thể được sử dụng để xác định thông số tối ưu cho các bộ điều khiển. Thông số bộ điều khiển được mã hóa thành các nhiễm sắc thể, thông qua mô phỏng, các nhiễm sắc thể này được đánh giá và lựa chọn thông qua mức độ thích nghi của chúng (cũng chính là các chỉ tiêu chất lượng của hệ thống). Kết quả của thuật toán sẽ cho một bộ điều khiển có thông số tốt nhất. Trong y học, cấu trúc của các chất hóa học được mã hóa thành các nhiễm sắc thể hoặc đồ thị. Thuật toán di truyền sẽ lai ghép, lựa chọn để tạo ra các nhiễm sắc thể mới (các chất hóa học mới). Và trong thực tế đã có rất nhiều loại thuốc mới được tạo ra như vậy. 26 3.5 Tối ưu hóa bộ điều khiển PID bằng giải thuật di truyền 3.5.1 Giới thiệu Trong lý thuyết điều khiển, có rất nhiều phương pháp để hiệu chỉnh thông số của bộ điều khiển PID, phổ biến nhất là phương pháp Ziegler-Nichols và thông thường, các thông số của bộ điều khiển được xác lập bằng phương pháp Ziegler- Nichols (Z-N) dựa trên kết quả đo đạc được từ đáp ứng của hệ thống.