So sánh một số phương pháp tìm nghiệm tối ưu xây dựng trên cơ sở mô phỏng quá trình tự nhiên

Cơ kỹ thuật & Kỹ thuật cơ khí động lực<br /> <br /> <br /> So s¸nh Mét sè ph­¬ng ph¸p t×m nghiÖm<br /> tèi ­u x©y dùng trªn c¬ së m« pháng<br /> qu¸ tr×nh tù nhiªn<br /> NGUYỄN TRANG MINH<br /> Tóm tắt: Bài báo giới thiệu kết quả nghiên cứu, đánh giá một số thuật toán<br /> tìm kiếm nghiệm tối ưu được xây dựng trên cơ sở mô phỏng quá trình tự nhiên<br /> ứng dụng để giải các bài toán trong kỹ thuật. Kết quả nghiên cứu có thể giúp<br /> định hướng chọn thuật toán phù hợp cho một số bài toán cụ thể.<br /> Từ khóa: Thuật giải di truyền, Thuật mô phỏng luyện kim, Thuật tiến hóa vi phân.<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> Dạng toán học của bài toán tối ưu tổng quát được viết như sau:<br /> Tìm giá trị cực tiểu (hoặc cực đại) hàm:<br /> f  x   min(max); x  R n (1)<br /> Với các điều kiện ràng buộc:<br /> gi  x   0; i  1, 2,..., , m<br /> (2)<br /> hi  x   0; i  1, 2,..., l.<br /> Bài toán đặt ra yêu cầu là tìm tập hợp các biến {xi}; i = 1, 2, …, n thoả mãn các điều<br /> kiện ràng buộc đồng thời hàm f(x) đạt giá trị cực tiểu (hoặc cực đại). Hàm f(x) được gọi là<br /> hàm mục tiêu - biểu diễn mối quan hệ giữa tiêu chuẩn chất lượng của quá trình khảo sát và<br /> các biến độc lập x. Các hàm số gi(x), hi(x) là các điều kiện ràng buộc của bài toán tối ưu.<br /> Trong không gian các biến, các hàm số này tạo ra miền giới hạn D các khả năng cho phép<br /> của hàm f(x).<br /> Trong miền cho phép D nếu hàm f(x) đơn điệu và tồn tại một cực trị thì nghiệm tìm<br /> được luôn luôn là duy nhất. Tuy vậy trong thực tế không phải lúc nào cũng vậy, ví dụ như<br /> hàm Peaks [2]- hai biến là hàm đơn điệu đa cực trị, được biểu diễn bằng đồ thị như hình 1.<br /> 2 2 x 2 2 1 2 2<br /> f ( x)  3.(1  x1 )2 .e(  x1 ( x2 1) )  10.( 1  x13  x25 ).e(  x1  x2 )  .e(  ( x1 1)  x2 ) ; (3)<br /> 5 3<br /> <br /> <br /> <br /> <br /> Hình 1. Hàm Peaks và các đường mức.<br /> <br /> Từ đồ thị hình 1 cho thấy, xung quanh phương án tốt nhất (điểm A đạt giá trị Min) còn<br /> có điểm B đạt cực trị địa phương và một số điểm nghi ngờ cực trị khác. Với phương pháp<br /> số xây dựng trên cơ sở các thuật toán truyền thống, trong quá trình giải, rất có khả năng<br /> kết quả cho là một điểm cực trị địa phương nào đó chứ không phải điểm Min trong toàn<br /> miền khảo sát. Hay nói một cách khác, thuật toán đã hội tụ sớm. Điều này hay xảy ra với<br /> <br /> <br /> 158 Nguyễn Trang Minh, “So sánh một số phương pháp … mô phỏng quá trình tự nhiên.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> những bài toán có số chiều lớn và hàm mục tiêu không liên tục. Vì vậy, việc phát triển các<br /> thuật toán đủ tin cậy để tìm nghiệm tối ưu toàn cục luôn được nhiều nhà khoa học quan<br /> tâm. Với sự phát triển mạnh của kỹ thuật tính toán trên máy tính điện tử đã xuất hiện một số thuật<br /> toán tìm nghiệm tối ưu dựa trên cơ sở mô phỏng các quá trình xảy ra trong tự nhiên. Điển hình là:<br /> - Thuật giải di truyền (GA- Genetic Algorithms)<br /> - Thuật mô phỏng luyện kim (SA- Simulated Annealing Algorithm)<br /> - Thuật tiến hoá vi phân (DE- Differential Evolution Algorithm)<br /> Đây là các thuật toán thuộc lớp các thuật giải xác suất, cả ba thuật toán trên chủ yếu<br /> dựa vào giá trị hàm mục tiêu không phụ thuộc vào đặc điểm của hàm và các biến. Những<br /> thuật toán này cũng chỉ hoạt động được nhờ kỹ thuật số. Cả ba thuật toán đều đã được ứng<br /> dụng để giải những bài toán tối ưu khó trong nhiều lĩnh vực của khoa học kỹ thuật.<br /> <br /> 2. NGUYÊN LÝ VÀ THUẬT TOÁN<br /> 2.1. Thuật giải di truyền<br /> 2.1.1 Nguyên lý hoạt động<br /> Thuật toán di truyền - GA do D.E. Goldberg đề xuất năm 1968, sau này được phát<br /> triển bởi L.Davis và Z.Michalevicz. Đây là thuật toán hình thành từ việc nhận mô phỏng<br /> lại quá trình tiến hóa của tự nhiên. Trong quá trình tiến hoá, các thế hệ mới được sinh ra<br /> bổ sung, thay cho thế hệ cũ, cá thể nào phát triển hơn thích ứng hơn với môi trường sẽ tồn<br /> tại, cá thể nào kém thích ứng hơn sẽ bị đào thải.<br /> Như vậy thuật toán di truyền mô phỏng ba quá trình<br /> tiến hoá cơ bản:<br /> Tái sinh và lựa chọn (Reproduction - Selection)<br /> Lai ghép (Crossover)<br /> Đột biến (Mutation)<br /> Để thực hiện được những thuật toán trên trước tiên<br /> cần tiến hành mã hóa các biến. Có hai phiên bản được sử<br /> dụng là phiên bản mã thực và phiên bản mã nhị phân.<br /> Trong phiên bản mã nhị phân, mỗi một chuỗi nhị phân<br /> với chiều dài xác định (chuỗi nhiễm sắc thể hay còn gọi<br /> là “gen”) sẽ tương ứng với một lời giải của bài toán đang<br /> khảo sát. Quá trình tiến hoá sẽ được thực hiện trên một<br /> tập các cá thể tương ứng với quá trình tìm ra lời giải tối<br /> ưu trong không gian các nghiệm cho phép.<br /> Điều khác biệt quan trọng giữa tìm kiếm của thuật toán<br /> di truyền với các phương pháp tìm kiếm khác là thuật toán di<br /> truyền luôn duy trì và xử lý một tập các lời giải, trong khi các<br /> phương pháp khác chỉ xử lý một điểm trong không gian tìm<br /> kiếm. Chính vì vậy mà thuật toán di truyền mạnh hơn và hiệu<br /> quả hơn các phương pháp khác [1].<br /> 2.1.2 Sơ đồ thuật toán<br /> Sơ đồ thuật toán của thuật giải di truyền được trình<br /> bày trên hình 2. Mã hoá các biến và xây dựng quần thể<br /> Hình 2. Sơ đồ thuật toán GA.<br /> ban đầu (khối 1,2):<br /> Ký hiệu npop_size là số cá thể trong một quần thể; nếu bài toán có n biến độc lập và mỗi<br /> n<br /> biến được biểu diễn bởi mi(j) bit thì mỗi phương án cần nx   mi( j ) bit để biểu diễn.<br /> j 1<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 159<br />  Cơ kỹ thuật & Kỹ thuật cơ khí động lực<br /> <br /> Tương ứng, toàn bộ bài toán cần (npop_size*nx) bit. Để có quần thể ban đầu ta chọn ngẫu<br /> nhiên npop_size cá thể trong vùng cho phép.<br /> Quá trình chọn lọc các cá thể (khối 4) trong GA dựa trên độ thích nghi của chúng (khối<br /> 3) thông qua xác suất lựa chọn như định nghĩa bởi biểu thức (5). Để tính xác suất lựa chọn<br /> thực hiện các bước sau:<br /> - Tính độ thích nghi eval(vi) cho mỗi cá thể; vi (i = 1, 2, …, npop_size)<br /> - Tính tổng giá trị thích nghi cho toàn bộ quần thể:<br /> npop _ size<br /> F  eval(v ) i<br /> (4)<br /> i 1<br /> <br /> - Tính xác suất lựa chọn pi cho mỗi cá thể vi:<br /> eval (vi ) (5)<br /> pi  npop _ size<br /> <br />  eval (v )<br /> i 1<br /> i<br /> <br /> <br /> - Tính vị trí xác suất qi cho mỗi cá thể vi (i = 1, 2, …, npop_size)<br /> i<br /> qi   p j (6)<br /> j 1<br /> <br /> Tiến trình chọn lọc được thực hiện bằng cách quay bánh xe Rulet npop_size lần; mỗi<br /> một lần sẽ chọn được một cá thể để đưa vào quần thể mới. Như vậy sẽ có một số cá thể<br /> được chọn hơn một lần và có cá thể sẽ bị loại bỏ.<br /> Quá trình lai ghép (khối 5) tiến hành theo hai bước:<br /> - Chọn ngẫu nhiên (pc*npop_size) cá thể trong quần thể, sau đó chọn ngẫu nhiên một<br /> cặp cá thể trong số các cá thể sẽ lai ghép.<br /> - Chọn ngẫu nhiên điểm lai ghép và tiến hành lai ghép theo sơ đồ (hình 3).<br /> <br /> <br /> ĐIỂM LAI GHÉP CÁ THỂ SAU LAI GHÉP<br /> <br /> <br /> <br /> <br /> Hình 3. Sơ đồ lai ghép đơn giản.<br /> <br /> Thông số có ý nghĩa đối với việc lai ghép là xác suất lai ghép pc, tham số này cho biết<br /> số cá thể sẽ tham gia lai ghép trong quần thể là (pc*npop_size). Theo tài liệu [3], thường<br /> chọn pc= 0,25.<br /> Quá trình đột biến (khối 6) thực hiện như sau: Phát (pm*nx*npop_size) lần số ngẫu<br /> nhiên r phân bố đều trong khoảng [1, (nx*npop_size)]. Nếu r trùng với vị trí nào sẽ tiến<br /> hành đột biến bit đó, có nghĩa là nếu giá trị của bit đó bằng 0 thì chuyển thành 1 hoặc<br /> ngược lại. Thông số điều khiển quá trình là xác suất đột biến pm.<br /> Thuật toán GA thường kết thúc khi số lần tiến hóa vượt quá giới hạn.<br /> 2.2. Thuật mô phỏng luyện kim<br /> 2.2.1. Nguyên lý hoạt động<br /> Như ta đã biết khi đốt nóng đến một mức nhiệt độ nào đó các phân tử của thủy tinh<br /> hoặc kim loại sẽ chuyển động tự do [2]. Lúc này, nhiệt độ là thước đo mức năng lượng<br /> trong từng phần tử cũng như toàn bộ hệ thống. Nếu như nhiệt độ giảm nhanh chóng, các<br /> phần tử ấy sẽ đông đặc lại như một kết cấu phức hợp. Tuy nhiên nếu nhiệt độ giảm chậm<br /> hơn thì dạng tinh thể của chúng sẽ mịn hơn nhiều. Trong trường hợp này những phần tử<br /> của các tinh thể rắn ấy ở trạng thái năng lượng cực tiểu. Năm 1983, S. Kirkpatrick; C. D.<br /> <br /> <br /> 160 Nguyễn Trang Minh, “So sánh một số phương pháp … mô phỏng quá trình tự nhiên.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Gelatt và M. P. Vecchi đã mô phỏng lại quá trình tự nhiên xảy ra với mạng tinh thể của<br /> thủy tinh hoặc kim loại khi làm nguội để tìm nghiệm tối ưu, do vậy phương pháp đề xuất<br /> được gọi là Mô phỏng luyện kim - Simulated Annealing - SA.<br /> 2.2.2. Sơ đồ thuật toán<br /> Sơ đồ thuật toán được trình bày trên hình 3. Khác với thuật toán di truyền, sau khi cho<br /> các tham số ban đầu cần thiết, thuật toán mô phỏng luyện kim xuất phát từ một điểm ban<br /> đầu được khởi tạo theo qui luật ngẫu nhiên phân bố đều trong miền xác định của bài toán<br /> (khối 1,2). Mức năng lượng của toàn bộ hệ thống sẽ giảm dần thông qua việc điều khiển<br /> nhiệt độ (khối 3). Xác định một điểm mới XP(i) trong miền cho phép của bài toán (khối 4).<br /> Điểm mới phụ thuộc vào điểm ban đầu X(i) và véc tơ điều chỉnh chiều dài bước Vm(i).<br /> Sai số giá trị hàm tại cặp điểm trên tính theo<br /> công thức:  = f(XP) - f(X).<br /> Giá trị này được sử dụng để xác định hướng<br /> chuyển động tiếp theo trong quá trình tìm nghiệm<br /> (khối 5). Trong bài toán tìm Max, chuyển động đi<br /> lên ( >0 - uphill) được chấp nhận, thì điểm mới<br /> sẽ thay thế điểm cũ [X(i)=XP(i)] - (khối 7). Một<br /> bước đi xuống ( < 0 dowhill), cũng có thể được<br /> chấp nhận nếu thỏa mãn tiêu chuẩn kiểm tra<br /> Metropolis (khối 8, 9). Bằng cách như vậy thuật<br /> toán có thể thoát khỏi những cực trị cục bộ và sẽ<br /> dừng lại ở cực trị toàn cục khi thoả mãn điều kiện<br /> dừng (khối 10).<br /> Do thuật toán sử dụng quá ít giá trị hàm mục<br /> tiêu nên mức độ xáo trộn rất cao. Mức độ này có<br /> thể điều chỉnh được bằng cách sử dụng các tham số<br /> điều khiển là: factor- Hệ số giảm nhiệt độ; ntm- Số<br /> bước nhiệt độ sẽ thử nghiệm; nlm- Số lần thử<br /> nghiệm ở từng mức nhiệt độ.<br /> Trong bài toán tìm cực đại, tiêu chuẩn<br /> Metropolis được sử dụng với mục đích cho phép<br /> những chuyển động đi xuống nhỏ, đồng thời ngăn<br /> chặn những chuyển động đi xuống lớn. Do đó tránh Hình 3. Sơ đồ thuật toán SA (CĐ).<br /> cho thuật toán bị sa lầy ở những cực tiểu cục bộ.<br /> Tại khối 9, ta lấy một số ngẫu nhiên phân bố đều trong khoảng [0,1] là p và so sánh<br /> với tiêu chuẩn Metropolis:<br /> <br /> m e t (7)<br /> trong đó, m là tiêu chuẩn Metropolis; t là giá trị nhiệt độ tính toán;  là sai số giá trị hàm<br /> tại hai điểm đang xét.<br /> Do  là âm trong nhánh này nên giá trị m cũng sẽ nằm trong khoảng [0,1]. Khi số mũ<br /> càng âm thì giá trị của m càng gần với 0 hơn. Tức là khi nhiệt độ giảm dần tới không và<br /> 