Thiết kế giải thuật di truyền giải bài toán tối ưu phi tuyến đa ràng buộc

Nội dung text: Thiết kế giải thuật di truyền giải bài toán tối ưu phi tuyến đa ràng buộc

1. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải THIẾT KẾ GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN TỐI ƯU PHI TUYẾN ĐA RÀNG BUỘC Phạm Thanh Hà Trường Đại học Giao thông vận tải Số 3 Cầu Giấy, Hà Nội Tác giả liên hệ: hapt@utc.edu.vn Tóm tắt Bài báo tập trung nghiên cứu cơ sở toán học của tối ưu phi tuyến từ đó thiết kế các toán tử di truyền phục vụ việc xây dựng giải thuật di truyền giải bài toán tối ưu phi tuyến. Các kết quả của bài báo là cơ sở để thiết kế các giải thuật di truyền ứng dụng cho các bài toán tối ưu số đa ràng buộc như bài toán vận tải, bài toán lập kế hoạch, tối ưu hóa lộ trình, pha trộn hợp chất. Từ khóa: Giải thuật di truyền, tối ưu phi tuyến, đa ràng buộc. 1. Đặt vấn đề Cho đến nay đã có nhiều thuật toán tìm lời giải tối ưu cho nhiều lĩnh vực bài toán, ví dụ như trong bài toán tìm kiếm trên danh sách, cây, đồ thị các nhà khoa học đã đưa ra thuật toán tìm kiếm quay lui, vét cạn. Các thuật toán này tuy tìm được nghiệm tối ưu nhưng chỉ áp dụng được cho các bài toán có không gian tìm kiếm nhỏ [3]. Để khắc phục các hạn chế như trên các nhà khoa học cũng đã đưa ra các thuật toán tìm kiếm heurictics, đây là thuật toán có sử dụng các tri thức về lĩnh vực bài toán để nhằm giảm thời gian tìm kiếm. Tuy nhiên các thuật toán này lại vấp phải một vấn đề là các tri thức thường là kinh nghiệm của con người, do đó nó có thể chưa chính xác, đầy đủ và điều này có thể dẫn tới sự chệch hướng trong quá trình tìm kiếm [3]. Giải thuật tiến hóa cung cấp những kỹ thuật tìm kiếm tối ưu giúp ta giải quyết được những vấn đề đã đặt ra ở trên, nó cho phép ta tìm kiếm lời giải tối ưu trên các không gian lớn, nguyên tắc cơ bản của giải thuật tiến hóa là mô phỏng quá trình tiến hóa của tự nhiên. Cho đến nay lĩnh vực nghiên cứu về giải thuật tiến hóa đã thu được nhiều thành tựu, giải thuật tiến hóa được ứng dụng trong nhiều lĩnh vực phức tạp, các vấn đề khó có thể giải quyết được bằng phương pháp thông thường [1,2]. Với khả năng tiềm tàng của giải thuật di truyền, bài báo tập trung nghiên cứu cơ sở toán học và xây dựng giải thuật di truyền để giải bài toán tối ưu phi tuyến. 2. Giải thuật di truyền -290-
2. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải Giải thuật di truyền thuộc lớp các giải thuật tìm kiếm tiến hoá. Khác với phần lớn các giải thuật khác tìm kiếm theo điểm, giải thuật di truyền thực hiện tìm kiếm ngẫu nhiên trên một tập được gọi là quần thể các lời giải có thể [4,6,7]. Thông qua việc áp dụng các toán tử di truyền, giải thuật di truyền tráo đổi thông tin giữa các cực trị và do đó làm giảm thiểu khả năng kết thúc giải thuật tại một cực trị địa phương. Giải thuật di truyền duy trì một quần thể các lời giải có thể của bài toán tối ưu hoá. Thông thường, các lời giải này được mã hoá dưới dạng một chuỗi các gien. Giá trị của các gien có trong chuỗi được lấy từ một bảng các ký tự được định nghĩa trước. Mỗi chuỗi gien được liên kết với một giá trị được gọi là độ thích nghi. Độ thích nghi được dùng trong quá trình chọn lọc [1,2]. Cơ chế chọn lọc đảm bảo các cá thể có độ thích nghi tốt hơn có xác suất được lựa chọn cao hơn. Quá trình chọn lọc sao chép các bản sao của các cá thể có độ thích nghi tốt vào một quần thể tạm thời được gọi là quần thể bố mẹ. Các cá thể trong quần thể bố mẹ được ghép đôi một cách ngẫu nhiên và tiến hành lai ghép tạo ra các cá thể con. Điều đáng lưu ý là giải thuật không yêu cầu toán tử lai ghép luôn xảy ra đối với hai cá thể bố mẹ được chọn. Sự lai ghép chỉ xảy ra khi số ngẫu nhiên tương ứng với cặp cá thể bố mẹ được sinh ra trong khoảng [0, 1) không ln hơn một tham số pc (gọi là xác suất lai ghép). Nếu số ngẫu nhiên này lớn hơn pc, toán tử lai ghép không xảy ra. Khi đó hai cá thể con là bản sao trực tiếp của hai cá thể bố mẹ. Hình 1. Sơ đồ giải thuật di truyền Sau khi tiến hành quá trình lai ghép, giải thuật di truyền mô phỏng một quá trình khác trong tự nhiên là quá trình đột biến. Toán tử đột biến duyệt từng gien của từng cá -291-
3. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải thể con được sinh ra sau khi tiến hành toán tử lai ghép và tiến hành biến đổi giá trị trong miền xác định với một xác suất pm được gọi là xác suất đột biến. Trong giải thuật di truyền, quần thể con được sinh ra từ quần thể hiện tại thông qua 3 toán tử là chọn lọc, lai ghép và đột biến thay thế hoàn toàn quần thể hiện tại và trở thành quần thể hiện tại của thế hệ tiếp theo. Giải thuật di truyền phụ thuộc vào các tham số như: số cá thể trong quần thể; xác suất lai ghép; xác suất đột biến; số thế hệ cần tiến hoá. Cá thể có giá trị hàm mục tiêu tốt nhất của mọi thế hệ là lời giải cuối cùng của giải thuật. Quần thể đầu tiên được khởi tạo một cách ngẫu nhiên. 3.Tối ưu phi tuyến và xử lý ràng buộc Xét bài toán tối ưu phi tuyến tổng quát: q Tìm x để hàm f(x), x=(x1, ,xq) R đạt giá trị tối ưu thỏa: p≥0 phương trình gj(x)=0, j=0, ,p và m-p bất phương trình hj(x), j=p+1, ,m Cho đến nay vẫn chưa có phương pháp nào giúp xác định cực trị cho bài toán này, chỉ khi hàm mục tiêu và các ràng buộc gj và hj thỏa một số tính chất nào đó thì đôi khi mới tìm được tối ưu toàn cục. Như chúng ta đã biết giải thuật di truyền có thể giải quyết bài toàn tối ưu số [3], tuy nhiên các bài toán tối ưu này chỉ bị ràng buộc theo miền D Rq với D= nghĩa là mỗi biến xk bị giới hạn trong khoảng cho trước. Tuy nhiên những bài toán tối ưu tổng quát thường gặp trong thực tế hầu hết lại là bài toán tối ưu có ràng buộc [5,8]. Trong bài toán tối ưu có ràng buộc, dạng hình học của tập lời giải trong Rq là đặc trưng quan trọng nhất của bài toán. Hiện chỉ có tập lồi là có lý thuyết phát triển nhất. Trong phần này ta quan tâm đến bài toán tối ưu hàm f(x), x=(x1, ,xq) D, D  Rq và D là tập lồi. Miền D được xác định từ các khoảng giá trị lk ≤xk≤rk với k=1 q và từ tập ràng buộc C. Do tính chất lồi của D mà với mỗi điểm x=(x1, ,xq) D trong không gian tìm kiếm tồn tại 1 đoạn của biến xk, trong đó các biến xi (i=1, ,k- 1,k+1, ,q) khác vẫn cố định, nói cách khác điểm điểm x’=(x1, ,xk-1,y,xk+1, ,xq) D với y Ví dụ nếu DR2 được xác định như sau -3≤ x1 ≤3 0≤ x2 ≤8 2 x1 ≤ x2 ≤ x1+4 -292-
4. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải Thì đối với điểm (2,5) D cho tước ta có left(1) = 1, right(1) = left(2) = 4, right(2) = 6 Điều này có nghĩa là thành phần thứ nhất của véc tơ (2,5) có thể thay đổi từ 1 đến (trong khi x2 = 5 không đổi) và thành phần thứ 2 của véc tơ này có thể thay đổi từ 4 đến 6 (trong khi x1 = 2 vẫn giữ nguyên) Nếu tập ràng buộc C không rỗng thì không gian tìm kiếm D = là lồi, hơn nữa left(k)=lk, right(k)=rk và như thế kết quả luôn thỏa ràng buộc. Tính chất trên là cơ sở để xây dựng các toán tử đột biến, nếu biến xk bị đột biến thì khoảng đột biến phải là và như thế kết quả luôn thỏa ràng buộc. Một tính chất khác của không gian tìm kiếm lồi là bảo đảm với hai điểm x1, x2 bất kỳ trong không gian lời giải D, tổ hợp tuyến tính ax1+(1-a)x2 với a [0,1] cũng là điểm trong D. Tính chất này sẽ được sử dụng khi ta xây dựng phép lai số học. Ta xét một lớp bài toán tối ưu được xác định trên một miền lồi, lớp bài toán này được hình thức hóa như sau: Tối ưu hàm f(x1, ,xq) với tập ràng buộc tuyến tính 1. Ràng buộc về miền l ≤ x ≤ u với x=(x1, ,xq), l=(l1, ,lq), u=(u1, ,uq) 2. Ràng buộc đẳng thức Ax=b, x=(x1, ,xq), b=(b1, ,bp), A=(aij), 1 ≤ i≤ p và 1 ≤ j ≤ q với p là số phương trình 3. Ràng buộc bất đẳng thức Cx ≤ d, x=(x1, ,xq), d=(d1, ,dm), C=(cij), 1 ≤ i≤ q, 1 ≤ j ≤ m với m là số bất đẳng thức Cách hình thức hóa như vậy đủ để xử lý một lớp lớn các bài toán tối ưu với ràng buộc tuyến tính của một hàm mục tiêu bất kỳ. Trong một số kỹ thuật tối ưu hóa như quy hoạch tuyến tính, các ràng buộc về đẳng thức rất dễ cho việc giải bài toán tối ưu vì nếu lời giải tối ưu tồn tại nó sẽ thuộc bề mặt của tập lồi và như vậy các bất đẳng thức sẽ được chuyển thành các đằng thức bằng cách thêm vào các biến tạm, khi đó phương pháp lời giải tiến hành bằng cách di chuyển từ đỉnh này sang đỉnh khác trên bề mặt [1,2]. Ngược lại đối với phương pháp phát sinh các lời giải ngẫu nhiên như GA, thì các ràng buộc đẳng thức như vậy lại rất khó xử lý. Tuy nhiên ta có thể dễ ràng loại bỏ các ràng buộc đẳng thức này nhờ vào việc thế và đặt lại biến. Ví dụ: Giả sử ta muốn tối ưu hóa hàm 6 biến f(x1,x2,x3,x4,x5,x6) với 2x1+x2+x3=6 x3+x5=10; x1+x4=3; x2+x5≤120 -40 ≤ x1 ≤ 120; 50 ≤ x2 ≤ 75 -293-
5. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải 0 ≤ x3 ≤ 10; 5 ≤ x4 ≤ 15 0≤ x5 ≤ 20; -5≤ x6 ≤ 5 Có 3 phương trình và 6 biến như vậy sẽ có 3 biến tự do và ta sẽ dung 3 phương trình độc lập và biểu diễn các biến qua 3 biến còn lại. x1=3-x4 x2=-10+8x4+x5-3x6 x3=10-x5+3x6 Như vậy bài toán gốc trở thành bài toán tối ưu hóa hàm 3 biến x4, x5, x6 g(x4, x5, x6)=f(3-x4, -10+8x4+x5-3x6, 10-x5+3x6) với ràng buộc -10+8x4+x5-3x6≤ 120 vì x2+x5≤120 -40≤3-x4≤20 vì -40 ≤ x1 ≤ 120 0≤x3=10-x5+3x6≤ 10 vì 0 ≤ x3 ≤ 10 5 ≤ x4 ≤ 15 0≤ x5 ≤ 20 -5≤ x6 ≤ 5 Như vậy nhờ thế và đặt lại biến, ta đã loại được các đẳng thức, đương nhiên không gian tìm kiếm là không gian lồi. Với mỗi điểm có được (x4, x5, x6) sẽ có một khoảng tương ứng, trong đó hai biến còn lại được giữ nguyên. Ví dụ đối với không gian xác định như trên với 1 điểm cho trước (10, 2, 8) ta có: left(1)=7.25, right(1)=10.375 left(2)=6, right(2)=11 left(3)=1, right(3)=2.666 4. Thiết kế các toán tử di truyền cho bài toán tối ưu đa ràng buộc Như đã đề cập ở mục 3, để giải bài toán tối ưu phi tuyến đa ràng buộc thì các toán tử di truyền phải đảm bảo lời giải được sinh ra sau lai ghép, đột biến phải đảm bảo ràng buộc của bài toán 4.1. Toán tử đột biến Toán tử đột biến cần một cá thể x và tạo ra một con duy nhất x’. Phép toán này chọn một thành phần ngẫu nhiên k (1 q) của véc tơ x=(x1, ,xq) và sinh ra , x’=(x1, ,xk’, ,xq), trong đó xk’ là giá trị ngẫu nhiên trong khoảng Toán tử này đóng vai trò quan trong trong những giai đoạn đầu của quá trình tiến hóa khi các lời giải được phép di chuyển tự do trong không gian tìm kiếm. Đặc biệt toán tử cần thiết trong trường hợp quần thể ban đầu gồm nhiều bản sao của cùng một điểm. -294-
6. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải Tình trạng như thế thường xuyên xảy ra trong những bài toán tối ưu có ràng buộc mà người sử dụng đặc tả điểm khởi đầu của tiến trình. Hơn nữa điểm khởi đầu duy nhất này có một thuận lợi to lớn, nó cho phép phát triển một tiến trình lặp mà lần lặp kế tiếp bắt đầu tại một điểm tốt nhất của lần lặp trước Có 2 phép đột biến giải quyết được vấn đề ràng buộc như đề cập trên đó là đột biến biên và đột biến không đồng dạng sau đây. Đột biến biên Toán tử này cần một cá thể x và tạo ra một con duy nhất x’. Toán tử này là biến thể của toán tử đột biến đồng dạng với xk’ hoặc là left(k) hoặc là right(k) với cùng xác suất. Toán tử được xây dựng cho các bài toán tối ưu mà lời giải tối ưu nằm trên hoặc gần biên của không gian tìm kiếm khả thi. Do đó nếu tập ràng buộc C rỗng và biên thật lớn thì các toán tử này gây phiền toái. Đột biến không đồng dạng Đột biến không đồng dạng là một trong những toán tử có nhiệm vụ về tìm độ chính xác của hệ thống. Toán tử đột biến cần một cá thể x và tạo ra một con duy nhất x’. Phép toán này chọn một thành phần ngẫu nhiên k (1 q) của véc tơ x=(x1, ,xq) và sinh ra , x’=(x1, ,xk’, ,xq), trong đó xk’ được xác định như sau: ' xk + (t,right(k) − xk ) neuchu songaunhienla0 xk = xk − (t, xk − left(k)) neu chu songaunhienla1 Hàm (t, y) trả về giá trị trong khoảng [0, y] sao cho xác suất của (t, y) gần bằng 0 sẽ tăng khi t tăng. Xác suất này buộc toán tử tìm kiếm không gian thoạt đầu là đồng dạng (khi t nhỏ) và rất cục bộ ở những giai đoạn sau. Ta sử dụng hàm sau: t (1− )b (t, y) = y (1 − r T ) , với r là số ngẫu nhiên trong khoảng [0 1], T là số thế hệ tối đa và b là tham số hệ thống xác định mức độ không đồng dạng. 4.2. Toán tử lai ghép cho bài toán tối ưu đa ràng buộc Cũng như toán tử đột biến, toán tử lai ghép phải đảm bảo các nghiệm được sinh ra thỏa mẵng ràng buộc của bàn toán, bài báo đưa ra 2 toán tử lai ghép thỏa mãn điều kiện trên, đó là lai ghép số học và lai ghép đơn giản. Lai số học Phép lai số học đơn được xác định như sau: t t Nếu s v = và s w = được lai ghép thì kết quả là: t+1 t+1 s v = và s w = , -295-
7. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải ở đó 1 k m, v’k = a vk + (1 - a) vk và w’k = a wk + (1 - a) wk, a là giá trị động được xác định theo véc tơ sv và sw. Chính xác hơn a được chọn trong phạm vi: [max( ,),min( , )] a [0,0] if vk = wk max( , ),min( ,) Trong đó: = (lk–wk)/(vk–wk),  = (uk–vk)/(wk–vk)  = (lk–vk)/(wk–vk),  = (uk–wk)/(vk–wk) Lai đơn giản Lai ghép số học toàn cục là tổ hợp tuyến tính của hai véc tơ được xác định như sau: t t Nếu s v = và s w = được lai ghép thì kết quả là: t+1 t t t+1 t t s v = a s w+(1- a) s v và s w = a s v+(1- a) s w, với a là một tham số tĩnh nằm trong đoạn [0, 1]. Kết luận Bài báo đã đi sâu nghiên cứu cơ chế hoạt động của giải thuật di truyền, tìm hiểu các cơ chế mã hóa lời giải và các toán tứ di truyền cũng như nghiên cứu bài toán tối ưu số đa ràng buộc, cơ sở toán học của việc xây dựng các toán tử di truyền xử lý đa ràng buộc của bài toán tối ưu số. Các kết quả của bài báo là cơ sở để thiết kế giải thuật di truyền giải các bài toán tối ưu số đa ràng buộc như bài toán lập kế hoạch, bài toán vận tải, bài toán tối ưu hóa lộ trình, pha trộn hợp chất. Tài liệu tham khảo [1] Các mô hình xác suất và ứng dụng, Nguyễn Duy Tiến, Đại học Quốc gia Hà Nội, 2002 [2] Giải thuật di truyền – Cách giải tự nhiên các bài toán trên máy tính, Hoàng Kiếm, Nhà xuất bản khoa học kỹ thuật, 2000 [3] Trí tuệ nhân tạo - Lập trình tiến hoá, Nguyễn Đình Thúc, Nhà xuất bản giáo dục, 2001 [4] An Introduction to Genetic Algorithms. Mitchell Melanie. A Bradford Book The MIT Press. Cambridge, Massachusetts London, England. Fifth printing, 1999. [5] Multi-Criteria Genetic Algorithms for Solving Pig Food Problems, A, International Journal on Computer Science and Engineering (IJCSE). ISSN : 0975- 3397 Vol. 3 No. 1 Jan 2011 -296-
8. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải [6] Practical Genetic Algorithms, Randy L. Haupt, Sue Ellen Haupt, Second Edition, Copyright © 2004 John Wiley & Sons, Inc. [7] Genetic Algorithms in Applications, Rustem Popa, Publisher: IN-TECH (March, 2012) [8] A directional crossover (DX) operator for real parameter optimization using genetic algorithm, Amit Kumar Das & Dilip Kumar Pratihar, Applied Intelligence volume 49, pages1841–1865 (2019) -297-