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

Cơ kỹ thuật & Kỹ thuật cơ khí động lực Nguyễn Trang Minh, “So sánh một số phương pháp mơ phỏng quá trình tự nhiên.” 158 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 NGUYỄN TRANG MINH 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 tốn 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 ứng dụng để giải các bài tốn trong kỹ thuật. Kết quả nghiên cứu cĩ thể giúp định hướng chọn thuật tốn phù hợp cho một số bài tốn cụ thể. 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. 1. ĐẶT VẤN ĐỀ Dạng tốn học của bài tốn tối ưu tổng quát được viết như sau: Tìm giá trị cực tiểu (hoặc cực đại) hàm:   nRxxf min(max); (1) Với các điều kiện ràng buộc:     0; 1, 2,..., , 0; 1, 2,..., . i i g x i m h x i l     (2) Bài tố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 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à 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à 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 tốn tối ưu. 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 của hàm f(x). 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 đượ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ư 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. 2 2 2 2 2 2 1 2 1 2 1 2( ( 1) ) ( ) ( ( 1) )2 3 51 1 1 2 1 ( ) 3.(1 ) .e 10.( ). . ; 5 3 x x x x x xxf x x x x e e             (3) Hình 1. Hàm Peaks và các đường mức. 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 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 số xây dựng trên cơ sở các thuật tốn truyền thống, trong quá trình giải, rất cĩ khả năng 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 tồn miền khảo sát. Hay nĩi một cách khác, thuật tốn đã hội tụ sớm. Điều này hay xảy ra với Nghiên cứu khoa học cơng nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 159 những bài tố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 thuật tốn đủ tin cậy để tìm nghiệm tối ưu tồn cục luơn được nhiều nhà khoa học quan tâm. Với sự phát triển mạnh của kỹ thuật tính tốn trên máy tính điện tử đã xuất hiện một số thuật tố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à: - Thuật giải di truyền (GA- Genetic Algorithms) - Thuật mơ phỏng luyện kim (SA- Simulated Annealing Algorithm) - Thuật tiến hố vi phân (DE- Differential Evolution Algorithm) Đây là các thuật tốn thuộc lớp các thuật giải xác suất, cả ba thuật tốn trên chủ yếu 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 thuật tốn này cũng chỉ hoạt động được nhờ kỹ thuật số. Cả ba thuật tốn đều đã được ứng dụng để giải những bài tốn tối ưu khĩ trong nhiều lĩnh vực của khoa học kỹ thuật. 2. NGUYÊN LÝ VÀ THUẬT TỐN 2.1. Thuật giải di truyền 2.1.1 Nguyên lý hoạt động Thuật tốn di truyền - GA do D.E. Goldberg đề xuất năm 1968, sau này được phát triển bởi L.Davis và Z.Michalevicz. Đây là thuật tốn hình thành từ việc nhận mơ phỏng lại quá trình tiến hĩa của tự nhiên. Trong quá trình tiến hố, các thế hệ mới được sinh ra 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 tại, cá thể nào kém thích ứng hơn sẽ bị đào thải. Như vậy thuật tốn di truyền mơ phỏng ba quá trình tiến hố cơ bản: Tái sinh và lựa chọn (Reproduction - Selection) Lai ghép (Crossover) Đột biến (Mutation) Để thực hiện được những thuật tốn trên trước tiên cần tiến hành mã hĩa các biến. Cĩ hai phiên bản được sử dụng là phiên bản mã thực và phiên bản mã nhị phân. Trong phiên bản mã nhị phân, mỗi một chuỗi nhị phân với chiều dài xác định (chuỗi nhiễm sắc thể hay cịn gọi là “gen”) sẽ tương ứng với một lời giải của bài tốn đang khảo sát. Quá trình tiến hố sẽ được thực hiện trên một tập các cá thể tương ứng với quá trình tìm ra lời giải tối ưu trong khơng gian các nghiệm cho phép. Điều khác biệt quan trọng giữa tìm kiếm của thuật tốn di truyền với các phương pháp tìm kiếm khác là thuật tốn di truyền luơn duy trì và xử lý một tập các lời giải, trong khi các phương pháp khác chỉ xử lý một điểm trong khơng gian tìm kiếm. Chính vì vậy mà thuật tốn di truyền mạnh hơn và hiệu quả hơn các phương pháp khác [1]. 2.1.2 Sơ đồ thuật tốn Sơ đồ thuật tốn của thuật giải di truyền được trình bày trên hình 2. Mã hố các biến và xây dựng quần thể ban đầu (khối 1,2): Hình 2. Sơ đồ thuật tốn GA. Ký hiệu npop_size là số cá thể trong một quần thể; nếu bài tốn cĩ n biến độc lập và mỗi biến được biểu diễn bởi mi(j) bit thì mỗi phương án cần    n j jminx 1 )( bit để biểu diễn. Cơ kỹ thuật & Kỹ thuật cơ khí động lực Nguyễn Trang Minh, “So sánh một số phương pháp mơ phỏng quá trình tự nhiên.” 160 Tương ứng, tồn bộ bài tốn cần (npop_size*nx) bit. Để cĩ quần thể ban đầu ta chọn ngẫu nhiên npop_size cá thể trong vùng cho phép. 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 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 thực hiện các bước sau: - Tính độ thích nghi eval(vi) cho mỗi cá thể; vi (i = 1, 2, , npop_size) - Tính tổng giá trị thích nghi cho tồn bộ quần thể: )( _ 1    sizenpop i ivevalF (4) - Tính xác suất lựa chọn pi cho mỗi cá thể vi:    sizenpop i i i i veval veval p _ 1 )( )( (5) - Tính vị trí xác suất qi cho mỗi cá thể vi (i = 1, 2, , npop_size)    i j ji pq 1 (6) 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 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ể được chọn hơn một lần và cĩ cá thể sẽ bị loại bỏ. Quá trình lai ghép (khối 5) tiến hành theo hai bước: - Chọn ngẫu nhiên (pc*npop_size) cá thể trong quần thể, sau đĩ chọn ngẫu nhiên một cặp cá thể trong số các cá thể sẽ lai ghép. - Chọn ngẫu nhiên điểm lai ghép và tiến hành lai ghép theo sơ đồ (hình 3). ĐIỂM LAI GHÉP CÁ THỂ SAU LAI GHÉP Hình 3. Sơ đồ lai ghép đơn giản. 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 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 chọn pc= 0,25. 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 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 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 ngược lại. Thơng số điều khiển quá trình là xác suất đột biến pm. Thuật tốn GA thường kết thúc khi số lần tiến hĩa vượt quá giới hạn. 2.2. Thuật mơ phỏng luyện kim 2.2.1. Nguyên lý hoạt động 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 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 trong từng phần tử cũng như tồn bộ hệ thống. Nếu như nhiệt độ giảm nhanh chĩng, các 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 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ử 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. Nghiên cứu khoa học cơng nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 161 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 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 được gọi là Mơ phỏng luyện kim - Simulated Annealing - SA. 2.2.2. Sơ đồ thuật tốn Sơ đồ thuật tốn được trình bày trên hình 3. Khác với thuật tốn di truyền, sau khi cho các tham số ban đầu cần thiết, thuật tốn mơ phỏng luyện kim xuất phát từ một điểm ban đầ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 tốn (khối 1,2). Mức năng lượng của tồn bộ hệ thống sẽ giảm dần thơng qua việc điều khiển 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 tốn (khối 4). Đ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). Sai số giá trị hàm tại cặp điểm trên tính theo cơng thức:  = f(XP) - f(X). Giá trị này được sử dụng để xác định hướng chuyển động tiếp theo trong quá trình tìm nghiệm (khối 5). Trong bài tốn tìm Max, chuyển động đi lên ( >0 - uphill) được chấp nhận, thì điểm mới sẽ thay thế điểm cũ [X(i)=XP(i)] - (khối 7). Một bước đi xuống ( < 0 dowhill), cũng cĩ thể được chấp nhận nếu thỏa mãn tiêu chuẩn kiểm tra Metropolis (khối 8, 9). Bằng cách như vậy thuật tốn cĩ thể thốt khỏi những cực trị cục bộ và sẽ dừng lại ở cực trị tồn cục khi thoả mãn điều kiện dừng (khối 10). Do thuật tốn sử dụng quá ít giá trị hàm mục tiêu nên mức độ xáo trộn rất cao. Mức độ này cĩ thể điều chỉnh được bằng cách sử dụng các tham số điều khiển là: factor- Hệ số giảm nhiệt độ; ntm- Số bước nhiệt độ sẽ thử nghiệm; nlm- Số lần thử nghiệm ở từng mức nhiệt độ. Trong bài tốn tìm cực đại, tiêu chuẩn Metropolis được sử dụng với mục đích cho phép những chuyển động đi xuống nhỏ, đồng thời ngăn chặn những chuyển động đi xuống lớn. Do đĩ tránh cho thuật tốn bị sa lầy ở những cực tiểu cục bộ. Hình 3. Sơ đồ thuật tốn SA (CĐ). 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 với tiêu chuẩn Metropolis: tem   (7) trong đĩ, m là tiêu chuẩn Metropolis; t là giá trị nhiệt độ tính tốn;  là sai số giá trị hàm tại hai điểm đang xét. 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ũ 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à <0 thì khả năng đi xuống (dowhill) sẽ gần như khơng xảy ra. 2.3. Thuật tiến hố vi phân 2.3.1. Nguyên lý hoạt động Trên cơ sở ý tưởng của thuật tốn GA, vào năm 1995, Rainer Storn và Kenneth Price đã hồn thiện cơ chế đột biến và lai ghép để tạo ra một thuật tốn mới tin cậy, hiệu quả hơn [4]. Thêm vào đĩ, điểm khác biệt lớn nhất của DE so với GA là luơn duy trì và bổ Cơ kỹ thuật & Kỹ thuật cơ khí động lực Nguyễn Trang Minh, “So sánh một số phương pháp mơ phỏng quá trình tự nhiên.” 162 sung một cặp 2 quần thể bao gồm (n_popsize) cá thể với (m) chiều các tham số thực. Thuật tốn đã ứng dụng thành cơng khi giải nhiều bài tốn tối ưu ở các lĩnh vực khác nhau. 2.3.2. Sơ đồ thuật tốn Sơ đồ thuật tốn được trình bày trên hình 4. Cũng như thuật tốn GA, thuật tốn tiến hố vi phân cũng khởi tạo quần thể các điểm ban đầu P(t)=[X] theo qui luật ngẫu nhiên phân bố đều trong miền xác định bài tốn (khối 1,2). Mỗi phần tử trong quần thể ban đầu này cũng được DE thực hiện trên miền tham số thực (8): (0,1) ( )ij ij ij ijx rand BU BL BL    (8) trong đĩ, xij là giá trị của phần tử ij ; I là số cá thể xem xét của bài tốn; j là số biến của bài tốn tối ưu; BUij, BLij là giới hạn trên và giới hạn dưới của biến xij; rand(0,1) là số ngẫu nhiên phân bố đều trong [0,1]. Ngay sau quá trình tạo quần thể ban đầu, khác với GA, thuật tốn DE thực hiện luơn tiến trình đột biến (khối 3). Trong tiến trình này, DE tạo ra một quần thể [V] trên cơ sở đột biến từ quần thể [X]. Từng cá thể của [V] xác định theo (9) :  j2rj1rojrij xxFxv ,,, *  (9) Trong đĩ: r0, r1, r2- là các giá trị ngẫu nhiên khác nhau được chọn theo luật phân bố đều trong khoảng [0, n_popsize]; F- Hằng số tỷ lệ, F(0,1) là một số thực dương điều khiển mức độ tiến hĩa của quần thể. Trong quá trình lai ghép (khối 4), DE cũng tiến hành lai ghép theo kiểu cặp đơi (dual crossover) tạo ra một quần thể lai ghép [U] cĩ giá trị các tham số được lựa chọn ngẫu nhiên từ các quần thể [X] và [V] ban đầu. Hình 4. Sơ đồ thuật tốn DE. Kỹ thuật lai ghép sử dụng trong lập trình của DE cĩ thể biểu diễn như (10): ; (0,1) ( ) ; ij r ij ij v if rand C or j rand j u x otherwise     (10) trong đĩ, Cr là xác suất lai ghép. Cr  (0, 1) được người sử dụng định nghĩa nhằm điều khiển một phần các tham số được sao chép từ quần thể đột biến. Thêm vào đĩ giá trị của phần tử lai ghép uij với chỉ số chọn ngẫu nhiên j= rand(j) được lấy từ quần thể đột biến [V] sẽ đảm bảo chắc chắn phần tử lai ghép khơng trùng với phần tử ban đầu xij. Trong quá trình chọn lọc và tái sinh (khối 5,6), các cá thể trong quần thể lai ghép [U] được so sánh với các cá thể trong quần thể ban đầu [X], cá thể nào cĩ giá trị hàm mục tiêu thấp hơn sẽ được lựa chọn vào quần thể mới [Y]. Kỹ thuật lựa chọn của DE cĩ thể biểu diễn như (11): ; ( ) ( ) ; ij ij ij ij ij u if f u f x y x otherwise    (11) Quá trình tái sinh sẽ được thực hiện bằng phép gán [X]=[Y] Nghiên cứu khoa học cơng nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 163 Điều kiện dừng của thuật tốn thể hiện trên khối 7 và 8. Các giá trị về số thế hệ tiến hố (Sth) hoặc một giá trị vơ cùng bé (ε) được đưa ra so sánh với các sai lệch của quá trình tính. Biểu thức điều kiện dừng của thuật tốn DE cĩ thể viết như (12): 1 min ( ) ( ) PN i i P F x F x N    (12) trong đĩ, F(x)min là giá trị nhỏ nhất của hàm mục tiêu tại thế hệ xét; F(x)i là giá trị hàm mục tiêu của cá thể thứ i; Np(= n_popsize) là tổng số cá thể trong quần thể đang xét;  là giá trị vơ cùng bé cho trước (thường chọn  = 10-4 10-6 tùy theo loại bài tốn). 3. BÀI TỐN THỬ NGHIỆM VÀ NHẬN XÉT ĐÁNH GIÁ 3.1. Bài tốn thử nghiệm Tìm cực tiểu hàm số Peaks xác định theo (3) với các điều kiện ràng buộc (13): - 3  x1  3 ; -3  x2  3 (13) 3.1.1. Sử dụng thuật giải di truyền (GA) Sử dụng thuật tốn GA, tính tốn với quần thể gồm 15 cá thể phân bố ngẫu nhiên như hình 6a. Kết quả tính tốn sau 60 thế hệ được giao tuyến của hàm Peaks với giá trị trung bình của quần thể như hình 5 và phân bố các cá thể của quần thể như trên hình 6b. Kết quả tối ưu của bài tốn (3) với các điều kiện hạn chế (13) là: f(x1, x2)min = -6,4249. Tại vị trí: x1= 0,34265; x2= - 1,6058 Hình 5. Giao tuyến hàm Peaks với giá trị trung bình của quần thể ở thế hệ thứ 60. a. b. Hình 6. Sơ đồ phân bố các cá thể của quần thể ban đầu (a) và ở thế hệ thứ 60 (b). 3.1.2. Sử dụng thuật mơ phỏng luyện kim (SA) Với giá trị nhiệt độ cho trước là t = 50, hệ số giảm nhiệt độ rt = 0,8 sử dụng thuật mơ phỏng luyện kim SA, sau 2593 lần tính tốn, kết quả tính hàm Peaks và quỹ đạo tìm nghiệm tối ưu được thể hiện trên hình 7. Kết quả nghiệm tối ưu của bài tốn là: Cơ kỹ thuật & Kỹ thuật cơ khí động lực Nguyễn Trang Minh, “So sánh một số phương pháp mơ phỏng quá trình tự nhiên.” 164 f(x1,x2)min = -6,5511 ; Tại vị trí: x1= 0,22880; x2= - 1,6260. a. b. 1 2 3 4 5 6 7 8 9 10 111 2 Hình 7. Kết quả tính tốn theo SA ở mức nhiệt độ t  00 và quĩ đạo tìm kiếm tối ưu tồn cục. 3.1.3 Sử dụng thuật tốn tiến hố vi phân (DE) Sử dụng thuật tốn tiến hĩa vi phân, tiến hành tính tốn với quần thể gồm 15 cá thể, ở thế hệ thứ 30 ta cĩ các kết quả như hình 8 và hình 9a. Với điều kiện dừng ε = 10-6, sau 46 thế hệ, quá trình tính tốn kết thúc, sơ đồ phân bố các cá thể như trên hình 9b. Ta cĩ kết quả tối ưu của bài tốn là: f(x1,x2)min = -6,5511; Tại vị trí: x1= 0,22883; x2= - 1,6261 Hình 8. Giao tuyến hàm Peaks với giá trị trung bình của quần thể ở thế hệ thứ 30. a. b. Hình 9. Sơ đồ phân bố các cá thể của quần thể ở thế hệ thứ 30 (a) và ở thế hệ thứ 46 (b). Nghiên cứu khoa học cơng nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 165 3.2. So sánh, đánh giá khả năng tìm kiếm của các phương pháp GA, SA, DE Lập trình bằng ngơn ngữ FORTRAN, kết quả tính tốn với các tham số cụ thể cho bài tốn thử nghiệm (3) với các điều kiện hạn chế (13), được đưa ra như bảng 1. Bảng 1. Kết quả tìm cực tiểu hàm Peaks bằng các thuật tốn GA, SA, DE. Thuật tốn sử dụng 2 2 2 2 2 2 1 2 1 2 1 2( ( 1) ) ( ) ( ( 1) )2 3 51 1 1 2 1 ( ) 3.(1 ) .e 10.( ). . ; 5 3 x x x x x xxf x x x x e e             -3  x1  3; -3  x2  3 nf t x* f(x*) ss GA 15055 16% x1*= 0,34265 x2*= -1,6058 -6,4290 1,9% SA 2593 12% x1*=0,22880 x2*= -1,6260 -6,5511 ~0% DE 248 7% x1*= 0,22883 x2*= -1,6261 -6,5511 ~0% Trong đĩ, nf là số lần tính giá trị hàm; t là thời gian tính tốn (% sec); x* là giá trị tối ưu của các biến; f(x*) là giá trị hàm ở điểm tối ưu; ss là phần trăm sai số của các thuật tốn so với giá trị hàm tại vị trí đạt giá trị tối ưu (điểm A - hình 1). Trên cơ sở kết quả quá trình tìm cực tiểu hàm Peaks bằng các thuật tốn khác nhau (bảng 1), cho thấy: trong 3 phương pháp tối ưu được đề cập, phương pháp DE là phương pháp hiệu quả nhất (cả về thời gian tính, kết quả tính ...). Tác giả cũng đã thử nghiệm lập trình tính tốn áp dụng 3 phương pháp tối ưu trên cho nhiều bài tốn thử điển hình khác như: Tìm cực tiểu hàm Generalized Rosenbrock; Tìm cực tiểu hàm Ackley; Tìm cực đại hàm Zbigniew Michalewicz ... kết quả cũng cho các nhận xét tương tự như trên. 4. KẾT LUẬN Qua quá trình nghiên cứu lập trình, tính tốn thử một số bài tốn mẫu cĩ thể đưa ra những kết luận sau: - Ba thuật tốn tối ưu tồn cục được xem xét là GA, SA và DE đều thuộc lớp phương pháp tìm kiếm ngẫu nhiên trên cơ sở mơ phỏng quá trình tự nhiên. Theo nhiều tài liệu nghiên cứu cũng như kinh nghiệm lập trình tính tốn của tác giả khi sử dụng các phương pháp trên thuật tốn DE cho kết quả tốt nhất. - Thơng thường để giải các bài tốn tối ưu trong thực tế trong kỹ thuật quá trình tính tốn một lần giá trị hàm và các điều kiện ràng buộc khác thường mất rất nhiều thời gian. Do vậy, việc rút ngắn được thời gian trong tính tốn tối ưu của thuật tốn DE là một ưu điểm vượt trội so với các thuật tốn khác, bên cạnh đĩ các kỹ thuật lập trình cần thiết đối với thuật tốn DE đơn giản hơn so với thuật tốn GA và SA. - Thuật tốn DE đã và đang từng bước được ứng dụng vào thực tế để giải một số bài tốn tối ưu kết cấu theo tiêu chuẩn trọng lượng cực tiểu hay tiêu chuẩn năng lượng cực tiểu. TÀI LIỆU THAM KHẢO [1] Nguyễn Đình Thúc, “Trí tuệ nhân tạo -Lập trình tiến hĩa” - NXB Giáo dục - 2001. [2] A. Das, B. K. Chakrabarti, “Quantum Annealing and Related Optimization Methods” - Springer – 2005. [3] Zbigniew Michalewicz – “Genetic Algorithms + Data Structures = Evolution Programs” - Springer-Verlag -1994. Cơ kỹ thuật & Kỹ thuật cơ khí động lực Nguyễn Trang Minh, “So sánh một số phương pháp mơ phỏng quá trình tự nhiên.” 166 [4] Kenneth Price, Rainer Storn, Jouni Lampinen – “Differiential Evolution A Practical Approach to Global Optimization” - Springer - 2005. ABSTRACT COMPARE SEVERAL METHODS TO FIND OPTIMAL SOLUTION BASED ON THE NATURAL PROCESS SIMULATION This paper presents research results, evaluation of search algorithms optimal solution is built on the basis of simulating natural processes applied to solve problems in engineering. The research results can help guide select appropriate algorithms for a specific problem. Keywords: Genetic Algorithms, Simulated Annealing, Differential Evolution. Nhận bài ngày 15 tháng 7 năm 2014 Hồn thiện ngày 15 tháng 9 năm 2014 Chấp nhận đăng ngày 25 tháng 9 năm 2014 Địa chỉ: Phịng Đào tạo, Viện Khoa học và Cơng nghệ quân sự.