Báo cáo khoa học: "SO SÁNH MỘT SỐ PHƯƠNG PHÁP TÌM KIẾM TỐI ƯU ỨNG DỤNG TRONG KỸ THUẬT"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

113
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 tìm kiếm tối ưu dựa trên cơ sở mô phỏng Monte - Carlo đang được ứng dụng để giải các bài toán kỹ thuật trên thế giới. Kết quả nghiên cứu có thể áp dụng cho bài toán tối ưu ứng dụng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo khoa học: "SO SÁNH MỘT SỐ PHƯƠNG PHÁP TÌM KIẾM TỐI ƯU ỨNG DỤNG TRONG KỸ THUẬT"

SO SÁNH MỘT SỐ PH ƯƠNG PHÁP TÌM KIẾM TỐI ƯU ỨNG DỤNG TRONG KỸ THUẬT TS. NGUYỄN QUÁN THĂNG Phòng Khoa học Công nghệ MT Bộ Tư lệnh Công binh TS. NGUYỄN TUẤN ANH Bộ môn Kỹ thuật ATGT Trường Đại học Giao thông Vận tải ThS. NGUYỄN THẾ MINH Bộ môn Xe máy Công binh Học viện Kỹ thuật Quân sự 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 tìm kiếm tối ưu dựa trên cơ sở mô phỏng Monte - Carlo đang được ứng dụng để giải các bài toán kỹ thuật trên thế giới. Kết quả nghiên cứu có thể áp dụng cho bài toán tối ưu ứng dụng. Summary: The article is introduced about result searched and evaluated for some optimal method bese on Monte - Carlo simulation that be using in the world. The result can be apllied for optimal mechanism design. CT 2 I. ĐẶT VẤN ĐỀ 1.1. Xác định nhiệm vụ của bài toán tối ưu Trong k ỹ thuật, khi giải quyết bất kỳ nhiệm vụ nào chúng ta đ ều mong muốn có phương án tốt nhất theo một hoặc một vài tiêu chí nào đó. Có thể liệt kê rất nhiều những ví dụ cụ thể như: tiết kiệm thời gian nhất, chi phí nhỏ nhất, năng suất lớn nhất, quãng đường đi ngắn nhất, thiết kế kết cấu với trọng lượng vật liệu nhỏ nhất… Để giải được những bài toán này, toán học đã cho ra đời một ngành là “Quy hoạch toán học” hay “tối ưu hóa” [1], [3]. Bài toán tối ưu nói chung được viết dưới dạng toán học như sau: Tìm giá trị cực tiểu (hoặc cực đại) hàm: f(x)  min(max); x  R n (1) Với các điều kiện: gi(x) ≥ 0; i = 1,2,... , m hi(x) = 0; i = 1,2,... , l
Bài toán đặt ra yêu cầu là tìm tập hợp các biến xi, i = 1, … ,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). Thực ra tìm cực tiểu hoặc cực đại trong toán học không khác nhau nhiều (dùng phép biến đổi hàm ngược), do vậy trong bài báo này chủ yếu ta xét bài toán tìm cực tiểu. Hàm f(x) trong biểu thức (1) đ ược gọi là hàm mục tiêu hoặc tiêu chuẩn tối ư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 toán tối ưu dưới dạng đẳng thức và bất đẳng thức. 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). Nếu như D  Rn (với R là số chiều của hàm mục tiêu), có nghĩa là không tồn tại bất kỳ một điều kiện giới hạn nào ta nói rằng bài toán quy hoạch phi tuyến không có điều kiện ràng buộc. Tuy nhiên trong phần lớn các b ài toán tối ưu, người sử dụng thường có băn khoăn đó là: kết quả nhận được từ quá trình tính đã thật sự là phương án tốt nhất chưa. Để minh họa vấn đ ề này ta có thể xét 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ư trên hình 1. (-x12-(x2 +1)2 ) (-x2-x2 ) 1 (-(x +1)2-x2 ) x f(x) = 3.(1- x1)2.e -10.( 1 - x1 - x5 ).e 1 2 - .e 1 3 2 (2) 2 5 3 CT 2 Hình 1. Minh hoạ tối ưu toàn cục Như trên hình 1, xung quanh phương án t ốt nhất (ở đây chọn là điểm thấp nhất - đi ểm A) còn có một điểm đạt cực trị địa phương là điểm B và một số điểm nghi ngờ có cực tiểu khác. Trong quá trình giải, rất có khả năng kết quả giải b ài toán tối ưu của chúng ta bị "kẹt" tại một cực trị nào đó (không phải điểm A) và không thoát ra được. Vì vậy, việc phát triển các thuật toán đủ mạnh tiệm cận đ ược giá trị tối ưu luôn được người làm kỹ thuật quan tâm. 1.2. Các dạng bài toán tìm kiếm tối ưu dựa trên cơ sở mô phỏng Monte - Carlo Với các phương pháp cổ điển, những bài toán tìm kiếm tối ưu trong không gian tìm kiếm nhỏ là tương đối phù hợp. Tuy nhiên để tìm đ ược nghiệm tiệm cận tối ưu trong không gian tì m ki ếm lớn cần thiết phải có những kỹ thuật tìm kiếm đặc biệt dựa trên những hiểu biết về trí tu ệ nhân tạo và mô phỏng các hiện tượng vật lý hay sinh học. Trong số đó nổi bật lên là các phương pháp tìm kiếm tối ưu Monte - Carlo sau: - Thuật giải di truyền (Genetic Algorithms - GA)
- Thuật mô phỏng luyện kim (Simulated Annealing Algorithm - SA) - Thuật tiến hoá vi phân (Differential Evolution Algorithm - DE) Đây là các thuật toán thuộc lớp các thuật giải xác suất, hiện đại và đang được quan tâm ứng dụng vào giải các bài toán tối ưu k ỹ thuật. II. NGUYÊN LÝ HOẠT ĐỘNG VÀ SƠ ĐỒ THUẬT TOÁN 2.1. Thuật giải di truyền a. Nguyên lý hoạt động Giải thuật 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 toán hình thành từ việc nhận xét thế giới tự nhiên: Quá trình tiến hoá tự nhiên là quá trình tối ưu nhất, hoàn hảo nhất. Đây được 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. Tính tối ưu của quá trình tiến hoá thể hiện ở chỗ thế hệ sau bao giờ cũng tốt hơn (phát triển hơn, hoàn thiện hơn và phù hợp với môi trường hơn) thế hệ trước. Xuyên suốt quá trình tiến hoá, các thế hệ mới được sinh ra đ ể bổ sung, thay thế thế hệ cũ, trong quá trình này 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 toán di truyền đ ều mô phỏng bốn quá trình tiến hoá cơ bản: lai ghép, đột biến, sinh sản, chọn lọc tự nhiên. b. Xây dựng sơ đồ thuật toán CT 2 Sơ đồ thuật toán được trình bày trên hình 2a. Mã hoá các bi ến và xây dựng quần thể ban đầu (khối 1, 2): 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 biến được biểu diễn bởi mi(j) bit thì n mỗi phương án cần nx   mi( j) bit để biểu diễn. Tương ứng, toàn bộ bài toán cần j1 (npop_size*nx) bit. Để có quần thể ban đầu ta chọn ngẫu nhiên npop_size cá thể trong phạm vi 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 (4). Để 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 toàn bộ quần thể: npop_size F= eval(v ) (3)  i=1 i - Tính xác suất lựa chọn p i cho mỗi cá thể vi:
eval(v ) i (4) p= i npop_size eval(v )  i=1 i - Tính vị trí xác suất qi cho mỗi cá thể vi (i = 1,2,…, npop_size) i (5) q = p i j=1 j 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ể đã bị loại bỏ. Trong quá trình lai ghép (khối 5), 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). Thường pc=0.25 [1], [2], [4]. - Chọn ngẫu nhiên (pc*npop_size) cá thể trong quần thể, tiếp tục lại chọn ngẫu 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. Đối với quá trình đột biến (khối 6), thông số khác điều khiển quá trình là xác suất đột biến pm. Tham số này cho biết số bit sẽ đột biến là (p m . nx . npop_size). Cách thực hiện như sau: CT 2 - 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 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. 2.2. Thuật mô phỏng luyện kim a. Nguyên lý hoạt động Như ta đã biết khi đốt nóng các phân tử của thủy tinh hoặc kim loại chuyển động tự do, nhiệt đ ộ là thước đo mức năng lượng 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 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. 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 được đề xuất có tên là Mô phỏng luyện kim (SA). b. Xây dựng sơ đồ thuật toán Sơ đồ thuật toán được trình bày trên hình 2b. Khác với thuật toán di truyền, trong thuật toán mô phỏng luyện kim chỉ có một điểm ban đầu được khởi tạo theo quy luật ngẫu nhiên phân bố đều trong miền xác định của b ài toán sau
khi cho các tham số ban đầu cần thiết (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 nhiệt độ (khối 3). Sau đó một điểm mới XP(i) trong miền xác định của bài toán cũng đ ược xác lập (khối 4). Điểm mới này phụ thuộc vào điểm ban đầu X(i) cũng như vào 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). (6) Giá trị này được sử dụng để xem xét đánh giá nhằm 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 toá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 (
Trong đó: r0, r1, r2 - 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. Kỹ thuật lai ghép sử dụng trong lập trình của DE có thể biểu di ễn như sau:  v ; if rand(0,1) £ C or j = rand(j) r  ij (9) u = ij  x ; otherwise  ij Trong đó: Cr - 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] theo hướng 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ư sau: CT 2 u ;if f(u ) £ f(x )  ij ij ij (10) y = ij  x ; otherwise  ij Quá trình tái sinh sẽ được thực hiện bằng phép gán [X] = [Y]. Điều kiện dừng của thuật toán DE cũng rất dễ dàng và thuận tiện. Các khối 7, 8, 9 biểu diễn điều kiện kiểm tra dừng và xuất kết quả của thuật toán. Các giá trị về số thế hệ tiến hoá (Sth) hoặc một giá trị vô cùng bé (EPS) đượ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 toán DE có thể viết như sau: Np  F(x)i i=1 (11) £ ε; F(x)min - Np Trong đó: F(x)min - giá trị nhỏ nhất của hàm mục tiêu tại thế hệ xét; F(x)i - giá trị hàm mục tiêu của cá thể thứ i; Np(= n_popsize) - tổng số cá thể trong quần thể đang xét;  - giá trị vô cùng bé cho trước (thường chọn = 10-4  10-6 tùy theo loại bài toán).
a) b) c) Hình 2. Sơ đồ các thuật toán GA, SA và DE III. M ỘT SỐ BÀI TOÁN THỬ NGHIỆM VÀ SO SÁNH 3.1. Một số bài toán thử nghiệm CT 2 a. Bài toán 1: Tìm cực tiểu hàm Generalized Rosenbrock Tìm cực tiểu hàm số sau: D-2 22 2 f(x) =  (100.(x - x ) + (x -1) ; j+1 j j j=0 Các điều kiện hạn chế có dạng: -30  xj  30; j = 0,1,2, … , D - 1; D >1 Đồ thị hàm Generalized Rosenbrock với 2 Hình 3. Đồ thị hàm Generalized Rosenbrock biến được biểu diễn như hình 3. b. Bài toán 2: Tìm cực tiểu hàm Ackley Tìm cực tiểu hàm số sau: 1 D-1 2 1 D-1 .  x j ) - exp(  cos(2.π.x j )) + 20 + e; f(x) = -20.exp(-0, 2. D j=0 D j=0 Các điều kiện hạn chế có dạng: -30  xj  30; j = 0,1,2, …, D - 1; D > 1 Đồ thị hàm Ackley với 2 biến được biểu diễn như hình 4.
Hình 4. Đồ thị hàm Ackley c. Bài toán 3: Tìm cực đại hàm Zbigniew Michalewicz Tìm cực đại hàm số sau:     f(x) = 21,5 + x sin  4πx  + x sin  20πx  1 1 2 2 Các điều kiện hạn chế có dạng: -3.0  x1  12.1; 4.1  x2  5.8 Đồ thị hàm Zbigniew Michalewicz đ ược biểu diễn như hình 5. CT 2 Hình 5. Đồ thị hàm Zbigniew Michalewicz d. Kết quả tính toán các bài toán thử nghiệm Kết quả tính toán ba bài toán thử nghiệm trên bằng chương trình tính viết bằng ngôn ngữ FORTRAN 95 được thể hiện trên bảng như sau: Bài toán 1 (n = 6) Bài toán 2 (n = 6) Bài toán 3 (n = 2) -2  xi  2 -30  xi  30 -3  x1  12,1; 4,1 x2  5,8 Tính toán nf t x* f(x*) nf t x* f(x*) nf t x* f(x*) 11,645 GA - - - - - - - - 702 0 38,209 5,522 11,625 SA 12000 14 {0,9} 0,0036 13801 3 {0} 0 2601 3 38,350 5,225 11,625 DE 19350 2 {1} 0 12421 3 {0} 0 870 0 38,850 5,725 Trong đó: nf - số lần tính giá trị hàm; t - thời gian tính toán (% sec); x* - giá trị tối ưu của các biến; f(x*) - giá trị hàm ở điểm tối ưu.
3.2. So sánh khả năng của các phương pháp Từ các tài liệu tham khảo và kết quả lập trình, tính toán cụ thể cho các bài toán thử nghiệm, nhận thấy ưu nhược điểm của ba phương pháp trên như sau: GA SA DE - Thuộc lớp thuật toán - Có đầy đ ủ các ưu - Thuộc lớp thuật toán Monte- Monte - Carlo, có khả điểm của GA và SA. Carlo và do xem xét nhiều cá thể năng tạo ra các đ ột biến - Thời gian tính rất Ưu trong một quần thể nên có thể để tiệm cận điểm tối ưu nhanh. điểm vượt qua cực trị địa phương, của bài toán. - Được đ ánh giá là tiệm cận điểm tối ưu của bài - Có tiêu chuẩn dừng rõ một thuật toán hiện toán. đại nhất trong tối ưu. ràng. - Thời gian tính thường - Việc lựa chọn các - Việc xây dựng tiêu chuẩn dừng kéo dài hơn so với các hệ số tỷ lệ F và hệ số rất khó khăn. phương pháp GA, DE xác suất lai ghép Cr Nhược - Rất khó sử dụng đối với các điểm do số lượng vòng lặp phụ thuộc rất nhiều hàm số biến đổi trái dấu ngẫu trong chương trình vào kinh nghiệm nhiên. nhiều. người sử dụng VI. KẾT LUẬN Qua quá trình nghiên cứu và thử nghiệm nhiều lần trên máy tính điện tử các thuật toán tối ưu trên kết hợp với kết quả thử nghiệm một số bài toán mẫu như đã đề cập, có thể đưa ra một số kết luận sau: - Theo quan điểm thuần tuý toán học, việc chứng minh nghiệm tối ưu của một bài toán thật sự không đơn giản đặc biệt với bài toán kỹ thuật. Tuy vậy, các phương pháp nêu trên cũng chỉ CT 2 ra cho chúng ta một bức tranh khá tốt về tìm ki ếm nghiệm tối ưu trong không gian lớn của bài toán đa cực trị, không liên tục khá phổ biến trong kỹ thuật. Với cả ba phương pháp đã trình bầy thì nghiệm đ ạt được chí ít cũng là phương án tốt nhất (theo một tiêu chuẩn xác định) trong tất cả các phương án đã xem xét. - Thông thường đ ể giải các bài toán tối ưu thực tế trong kỹ thuật quá trình tính toán thường mất rất nhiều thời gian. Ví dụ dùng thuật toán GA để giải bài toán tối ưu kết cấu trong môi trường Matlab thường mất nhiều tiếng. Do đó, vi ệc rút ngắn đ ược thời gian trong tính toán t ối ưu của thuật toán DE là một ưu đi ểm vượt trội so với các thuật toán khác trong quá trình tìm nghiệm, đặc biệt với bài toán mà giá trị hàm không thể biểu diễn được bằng những hàm đại số tường minh và với số biến lớn. Tài liệu tham khảo [1]. Hoàng Kiếm, Thuật giải di truyền, NXB Giáo dục, Hà nội, 2000. [2]. Nguyễn Đình Thúc, Trí tuệ nhân tạo - Lập trình tiến hóa, NXB Giáo dục, Hà nội, 2001. [3]. Bùi Minh Trí, Bài tập tối ưu hoá, NXB Khoa học Kỹ thuật, Hà nội, 2002. [4]. Zbigniew Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, Verlag, 1994. [5]. Kenneth Price, Rainer Storn, Jouni Lampinen, Differiential Evolution A Practical Approach to Global Optimization, Springer, Verlag, 2005