Luận văn Tối ưu số cho bài toán tối ưu một mục tiêu

ùng ta sẽ loại bỏ số 21 và 24, lai ghép hai số 4 và 10 tại điểm giữa hàng thứ hai và thứ ba: 001|00 (4) 010|00 (hay 8) 010|10 (10) 001|10 (hay 6) Bước 5: tính hệ số thích ghi cho các đáp số vừa có được. Thứ tự Nhị phân Thập phân X2-64 Thích nghi 1 2 3 4 00100 01010 01000 00110 4 10 8 6 -48 36 0 28 952 964 1000 968 Bước 6: kiểm tra sự thích nghi, nhưng ta thấy đáp số ở hàng thứ ba là số 8 với hệ số thích nghi bằng 1000, là số có hệ số thích nghi cao nhất. Nên không quay lại bước 4 và 5, chúng ta có kết quả là 8 Bước 7: kết quả là X=8 CÁC PHƯƠNG THỨC BIẾN HÓA CỦA THUẬT GIẢI DI TRUYỀN Có 3 phương thức: Tạo sinh (reproduction) Lai ghép (cross over) Đột biến (mutation) Tạo sinh: là dùng những thành phần của thế hệ trước để tạo thêm thành phần của thế hệ sau. Lai ghép: dùng lại những tin tức có sẵn trong các thành phần của thế hệ trước và truyền lại cho thế hệ sau. Đột biến: là việc thay đổi trị số của một số trong dãy số. So với lai ghép, phương thức biến hóa dựa trên đột biến ít xảy ra. Theo kết quả nghiên cứu của Keneth De Jong thì tỉ lệ lai ghép trung bình là 0.6, trong khi tỉ lệ đột biến là 0.01, phần còn lại là 0.399 là tạo sinh. Đột biến tạo ra những tin tức hoàn toàn mới. TÍNH CHẤT QUAN TRỌNG CỦA THUẬT GIẢI DI TRUYỀN GA lập luận có tính chất ngẫu nhiên để tìm giải pháp tối ưu cho những vấn đề phức tạp. Tuy nhiên đây là hình thức ngẫu nhiên có hướng dẫn bởi trị số thích nghi. Chính hàm số thích nghi là vật chỉ đường cho GA tìm giải pháp tối ưu trong muuôn ngàn giải pháp có thể có. Vấn đề thích hợp nhất cho GA là tìm điều kiện tối ưu. Tối ưu đây không nhất thiết phải là tuyệt đối, nhưng có thể chỉ là tương đối trong hoàn cảnh và thời gian cho phép. Một điểm khác của GA là lý thuyết này thích hợp cho những trường hợp phải tìm kiếm (search). Một trong những bước quan trọng và khó khăn nhất là tìm hàm số thích nghi (fitness Function). Hàm số thích nghi phải có liên hệ trực tiếp đến vấn đề phải giải quyết. GA và mạng Nơron nhân tạo đều thuộc vào nhóm khoa học trí tuệ nhân tạo, tuy nhiên GA lập luận dựa theo sự tiến hóa và xét vấn đề ở tầm mức của gen và nhiễm sắc thể, khác với mạng Nơron nhân tạo dựa trên các kinh nghiệm và cách giải quyết vấn đề mà bộ óc con người thường dùng. GIẢI PHÁP TỐI ƯU THEO PHƯƠNG PHÁP GA ĐẶT VẤN ĐỀ Tối ưu hóa là một nội dung quan trọng của tin học ứng dụng, có liên quan đến mọi lĩnh vực của tự nhiên và xã hội. Chúng ta sẽ áp dụng GA cho bài toán tối ưu một hàm f có n biến, f(x1,x2,...,xn). Biết rằng mỗi xi biến có thể lấy các giá trị từ miền Di =[ ai, bi] là tập con của tập các số thực R và yêu cầu độ chính xác là k chữ số thập phân đối với các giá trị biến. BIỂU DIỄN CÁC BIẾN NHỜ CÁC VÉCTƠ NHỊ PHÂN Bước đầu tiên trong thuật giải di truyền là mã hóa, ánh xạ một xâu với chiều dài hữu hạn sang các tham biến của bài toán tối ưu. Tham biến x thuộc [Umin, Umax] sẽ được biểu diễn bởi chuỗi nhị phân có chiều dài L. L bit mã hóa x ứng với giá trị trong miền [0,2L] sẽ được ánh xạ lên các giá trị thuộc miền xác định [Umin, Umax]. Theo cách này, chúng ta có thể kiểm soát miền giá trị của các biến và tính chính xác của chúng. Tỷ lệ co dãn của ánh xạ này được cho bởi G = (Umin - Umax) / (2L - 1) Giá trị x tương ứng với mã string2 sẽ được xác định theo công thức x = Umin + decimal(string2) * g trong đó decimal(string2) biểu diễn giá trị thập phân của chuỗi nhị phân string2, g được xác định bởi công thức g. Ví dụ: decimal(0001) = 1 hay decimal(0011) = 3 TOÁN TỬ CHỌN CÁ THỂ(SELECT) Toán tử chọn lọc là thao tác xử lý trong đó mỗi cá thể được bảo lưu cho vòng tạo sinh tiếp sau, tùy thuộc vào giá trị thích nghi của nó. Toán tử này là một phiên bản mô phỏng của quá trình chọn lọc tự nhiên. Giá trị thích nghi f(i) được xác định đối với mỗi cá thể trong quần thể. Giá trị này càng lớn thì cá thể được coi là hợp lý. Hàm thích nghi có thể là hàm không liên tục, hàm dương hay phi tuyến. Xử lý chọn lọc các cá thể cha mẹ được hình thành theo mô hình tái tạo quay trên vòng tròn (roulette weel). Vòng quay của chúng có kích cỡ khác nhau ứng với những giá trị hợp lý của các cá thể. Kỹ thuật này có thể thực hiện theo các bước Tính tổng giá trị thích nghi của tất cả thành viên quần thể và gọi nó là tổng thích nghi (total fitness). Phát sinh một số n là số ngẫu nhiên trong khoảng từ 0 đến tổng thích nghi. Trả lại thành viên quần thể đầu tiên mà độ thích nghi của nó cộng với độ thích nghi của các thành viên quần thể trước đây lớn hơn hay bằng n. TOÁN TỬ LAI GHÉP (CROSSOVER) Toán tử chọn lọc nhằm tìm ra những cá thể tồn tại tốt nhất nhưng nó không tạo ra những cá thể mới. Toán tử tác động trên các cá thể cha mẹ để tạo ra những con lai tốt được gọi là lai ghép. Chúng được áp dụng lên cặp cha mẹ, được chọn lựa với xác suất lai ghép ký hiệu bởi Pcross. Xác suất này cho chúng ta số lượng Pcross * pop_size nhiễm sắc thể được dùng cho hoạt động lai ghép, pop_size là kích thước của quần thể được lai tạo. Với mỗi nhiễm sắc thể trong quần thể: Phát sinh một số ngẫu nhiên r trong miền [0,1]. Nếu r < Pcross , chọn nhiễm sắc thể đó để lai ghép Sau đó ta kết hợp các nhiễm sắc thể được chọn một cách ngẫu nhiên: ® mỗi nhiễm sắc thể, ta có thể phát sinh một số ngẫu nhiên pos từ miền [1,L] (L là tổng số bit trong nhiễm thể). Số pos báo hiệu vị trí của điểm lai ghép. Hai nhiễm sắc thể: (b1b2 ... bposbpos+1 ... bL) và (c1c2 ... cposcpos+1 ... cL) được thay thế bởi (b1b2 ... bposcpos+1 ... bL) và (c1c2 ... cposbpos+1 ... cL) Như vậy, xử lý này sản xuất ra 2 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. TOÁN TỬ ĐỘT BIẾN (MUTATION) Toán tử đột biến nhằm tạo ra những thông tin mới trong quần thể lai tạo tại các vị trí bit(gen) nào đó (quần thể được xem xét có po_size cá thể, mỗi cá thể biểu thị qua L bit/gen). Đột biến được áp dụng với xác suất Pmu. Số lượng bit đột biến là Pmu*L*pop_size bit. Mỗi bit có cơ hội đột biến như nhau và được thay đổi từ 0 thành 1 hay ngược lại. Với mỗi nhiễm sắc thể trong quần thể và mỗi bit trong nhiễm sắc thể: Phát sinh một số ngẫu nhiên r trong miền [0,1]. Nếu r < Pmu , tiến hành đột biến tại bit đó. Các thao tác xử lý này được áp dụng lặp lại cho tới khi các cá thể con cháu của chúng tăng trưởng tới kích cỡ mong muốn của quần thể. HÀM THÍCH NGHI (FITNESS) ÁNH XẠ GIÁ TRỊ HÀM MỤC TIÊU SANG GIÁ TRỊ THÍCH NGHI Vì hàm thích nghi phải nhận giá trị không âm, do đó cần phải xây dựng ánh xạ hàm mục tiêu đang xét trong bài toán sang hàm thích nghi thông qua một hoặc nhiều lần ánh xạ. Nếu bài toán tối ưu là cực tiểu một hàm đánh giá g(x), việc chuyển từ hàm đánh giá sang hàm thích nghi để sử dụng với GA: Cmax – g(x) khi g(x) < Cmax 0 (trong các trường hợp khác) f(x) = Cmax là tham số đầu vào Khi hàm mục tiêu gốc tăng hoặc đang xét bài toán cực đại hóa một hàm hữu dụng u(x), ta có thể chuyển sang hàm thích nghi sau: u(x) + Cmin khi u(x) + Cmin > 0 0 (trong các trường hợp khác) f(x) = ĐIỀU CHỈNH ĐỘ THÍCH NGHI Một vấn đề quan trọng là điều chỉnh số con cháu. Điều này đặc biệt quan trọng cho một vòng lặp đầu tiên, khi một vài cá thể “siêu” có tiềm năng chiếm lĩnh phần lớn quần thể và làm cho hội tụ sớm. Một kiểu điều chỉnh hay gặp là điều chỉnh tuyến tính. Chúng ta định nghĩa độ thích nghi gốc là f và độ thích nghi biến đổi là f’. Điều chỉnh tuyến tính xác định quan hệ giữa f và f’ như sau: f’ = a * f + b Ở đây, hệ số a và b được chọn sao cho f’avg = favg (1) f’max = Cmult * favg (2) Cmult là số bản sao cần thiết đối với một thành viên tốt nhất. Với lượng biến tương đối nhỏ (n = 50 đến 100), Cmult thường được chọn từ 1.2 đến 2 và tỏ ra khá hiệu quả. Biểu thức (1) bảo đảm rằng mỗi thành viên với độ thích nghi trung bình sẽ cho một con hay một cháu cho lần phát sinh tiếp theo. Biểu thức (2) kiểm soát số con cháu được nạp vào làm thành viên với độ thích nghi gốc cực đại. Điều chỉnh tuyến tính làm giá trị thích nghi có thể thành âm, giải pháp thay thế điều kiện trong biểu thức là sử dụng điều kiện fmin = 0. THUẬT GIẢI CHO BÀI TOÁN CỰC TIỂU HÀM F VỚI N BIẾN LIÊN TỤC Bước 1: khởi tạo quần thể các nhiễm sắc thể nhằm thiết lập số lượng nhiễm sắc thể ngẫu nhiên ban đầu dưới dạng chuỗi nhị phân với kích cỡ quần thể bằng pop_size (xác định trước) Bước 2: xác định giá trị thích nghi (fitness value) 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 và tạo ra những nhiễm sắc thể mới bằng việc kết hợp các nhiễm sắc thể hiện tại (dùng các toán tử lai ghép, đột biến, tái kết hợp) Bước 4: loại bỏ những thành viên không thích nghi trong quần thể Bước 5: chèn những nhiễm sắc thể mới vào quần thể để hình thành một quần thể mới Tiếp tục cho đến khi đạt được điều kiện định trước (thường sau một số vòng lặp xác định khi không tìm được cải tiến tốt hơn dựa vào tốc độ máy tính và yêu cầu chính xác. Phần 4 GIẢI THUẬT TÌM KIẾM NGẪU NHIÊN THEO XÁC SUẤT VÀ MỘT SỐ ỨNG DỤNG CƠ SỞ SINH HỌC Lãnh vực tính toán tiến hóa dựa cơ sở trên các giải thuật tìm kiếm và tối ưu hóa mà chúng lấy cảm hứng từ mô hình sinh học của việc chọn lọc trong tự nhiên. Nhiều mô hình giải thuật tiến hóa khác nhau được đưa ra, trong đó chúng ta thấy có các mô hình nổi tiếng như Lập Trình Tiến Hóa, Chiến Lược Tiến Hóa, Giải Thuật Di Truyền và Lập Trình Di Truyền đều lấy ý tưởng từ thuyết tiến hóa cổ điển của Đắc-uyn. Giả thiết chung cho các mô hình này là sự tồn tại một quần thể các cá thể mà chúng đấu tranh với nhau cho sự sống sót và tái sinh sản, và mục đích của giải thuật là tìm kiếm những cá thể có độ thích nghi tốt nhất. Dưới quan điểm này thì đơn vị cơ sở của sự tiến hoá là cá thể. Mỗi một cá thể được gán cho một giá trị fitness mà nó được dùng để đo độ tốt hay độ thích nghi của cá thể. Thời gian được phân chia thành các bước rời rạc gọi là các thế hệ. Tại mỗi thế hệ, một số các cá thể mới được phát sinh trong quá trình tái sinh sản và một số các cá thể thì bị loại bỏ. Quá trình tái sinh sản được thực hiện thông qua các chiến lược chọn lọc, lai ghép, đột biến và thay thế. Việc chọn lọc các cá thể nào để thực hiện tái sinh sản là dựa vào độ fitness của chúng. Thông thường là sử dụng một kỹ thuật có tên là elitism (phát triển tầng lớp ưu tú) để giữ lại các cá thể tốt nhất xuyên qua các thế hệ. Quá trình tái sinh sản của Giải Thuật Di Truyền (GTDT) nói riêng và các giải thuật tiến hóa nói chung, sử dụng kỹ thuật di truyền chủ yếu dựa trên toán tử lai ghép, còn toán tử đột biến lại không được xem trọng. Sở dĩ đột biến không được xem trọng là vì kỹ thuật sinh sản dựa trên lai ghép là hữu tính. Một quá trình sinh sản hữu tính như thế thường diễn ra chậm chạp vì phải trải qua các quá trình chọn lọc, lai ghép, đột biến và thay thế. Bên cạnh đó để thuận lợi cho việc lai ghép nên lời giải của bài toán thường được mã hóa thành một bộ gen có cấu trúc là một dãy các bit nhị phân và các thủ tục giải mã gen thường là cầu kỳ và phức tạp đến độ với các thủ tục giải mã khác nhau dẫn đến các kết quả khác nhau, thậm chí có các thủ tục giải mã tự bản thân nó đã triệt tiêu lời giải tối ưu. Các thủ tục giải mã phức tạp như thế đã làm tiêu tốn thêm thời gian thực thi. Điều đó có nghĩa là trong một thời gian ngắn số lượng các cá thể được sản sinh ra rất ít không đủ để cho quá trình đột biến mang lại hiệu quả rõ ràng. Trong tự nhiên, mục đích của lai ghép hay sinh sản hữu tính là nhằm tạo ra những cá thể mới có sự đa dạng về di truyền và điều này đúng với những bộ máy di truyền cực lớn và phức tạp như của con người chẳng hạn. Tuy nhiên điều này lại không đúng cho những cá thể với bộ gen có kích thước rất nhỏ và đơn giản như của vi sinh vật. Đột biến không những là nguyên liệu mà còn là nhân tố tiến hóa, nó tạo ra sự khác biệt rất cao giữa các độ thích nghi của các cá thể trong một quần thể. Trong tự nhiên, vì xác suất của các đột biến có thể tạo ra được những cá thể mới có độ thích nghi tốt hơn là rất thấp, cho nên để tạo ra được một cá thể có độ thích nghi tốt hơn bằng phương pháp đột biến thì cần phải có một số lượng rất lớn các cá thể được sản sinh ra trong một khoảng thời gian cực ngắn. Vì vậy đột biến chỉ thích hợp với các sinh vật có tốc độ sinh sản rất nhanh và số lượng cá thể được sản sinh ra rất lớn trong một thời gian ngắn thì các giá trị do đột biến mang lại mới nhanh chóng được biểu hiện. ƯU THẾ VÀ ĐẶC ĐIỂM CỦA DI TRUYỀN HỌC VI SINH VẬT [12] Đối tượng nghiên cứu của các nhà di truyền học là bộ gen sinh học. Trong nghiên cứu di truyền học, các đối tượng vi sinh vật có nhiều ưu thế hơn hẳn các động vật và thực vật bậc cao. Các ưu thế đó là: Vòng đời ngắn, tốc độ sinh sản nhanh. Trong một thời gian ngắn, số lượng sinh sản các cá thể tăng vọt dẫn đến có thể phát hiện các sự kiện di truyền hiếm hoi do đột biến hay các dạng tái tổ hợp. Cấu tạo bộ máy di truyền đơn giản. Dễ nghiên cứu bằng các kỹ thuật vật lý và hóa học. Điều kiện nuôi cấy không cồng kềnh. TÍNH XÁC SUẤT VÀ TÍNH THỨ BẬC CỦA CÁC VỊ TRÍ GEN CỦA BỘ GEN Nhận xét rằng: Mỗi vị trí của bộ gen có một vai trò khác nhau trong việc định giá hàm mục tiêu của lời giải tối ưu nên xác suất đột biến tại mỗi vị trí của bộ gen là khác nhau. Các vị trí của bộ gen đều có mối tương quan với nhau theo một thứ bậc nào đó, nghĩa là giá trị đột biến tại vị trí này có khả năng quyết định giá trị đúng của đột biến tiếp theo tại một vị trí khác. Vì vậy việc xác định thứ bậc đột biến của các vị trí của bộ gen là quan trọng. Dựa trên cơ sở di truyền học vi sinh vật và phương pháp sinh sản không sử dụng kỹ thuật di truyền truyền thống mà bằng cách tác động trực tiếp gây đột biến theo hướng dẫn của xác suất tại mỗi vị trí của bộ gen theo một thứ tự đã xác định trước, một kỹ thuật như thế được gọi là gây đột biến có định hướng theo xác suất, chúng tôi đề nghị một giải pháp tối ưu mới có tên gọi là Giải Thuật Tìm Kiếm Ngẫu Nhiên Theo Xác Suất như sau. CÁC NGUYÊN TẮC SINH HỌC CĂN BẢN CỦA GIẢI THUẬT TKNNTXS Bộ gen phải thật đơn giản (như là bộ gen của vi sinh vật) và các thành phần của gen chính là lời giải trực tiếp của bài toán. Điều kiện này nhằm duy trì tính xác suất và tính thứ bậc của các vị trí của bộ gen, bên cạnh đó làm giảm bớt thời gian tính toán của việc mã hóa và giải mã lời giải, do đó làm tăng tốc độ sinh sản. Việc mã hóa lời giải thành một dãy các bit nhị phân như trong giải thuật di truyền đã xóa bỏ tính xác suất và tính thứ bậc của các chữ số của các biến quyết định trong lời giải của bài toán. Kỹ thuật sinh sản là vô tính hoặc trao đổi thông tin giữa 2,3 cá thể và số lượng sinh sản phải tăng vọt. Sử dụng kỹ thuật chọn lọc các dòng gen có năng suất cao để gây đột biến có định hướng. theo xác suất. Tính xác suất và tính thứ bậc: mỗi vị trí của bộ gen có một xác suất đột biến khác nhau và các vị trí của bộ gen có một thứ bậc đột biến thích hợp. Sử dụng kỹ thuật tác động trực tiếp gây đột biến có định hướng theo hướng dẫn của xác suất tại mỗi vị trí của bộ gen để đem lại sự đa dạng về di truyền nhằm tìm kiếm những gen lạ hiếm hoi. ÁP DỤNG VÀO CÁC BÀI TOÁN TỐI ƯU SỐ MÔ HÌNH BÀI TOÁN Chúng ta xét một mô hình TƯĐMT có ràng buộc gồm có p+q hàm mục tiêu fi(x) ( i=1, . . . , p), gj(x) ( j=1, . . . , q) và r hàm (có thể phi tuyến) ràng buộc hk(x) ( k=1, . . . , r) với x=(x1, . . . , xn) là biến quyết định n chiều theo mô hình đã định nghĩa ở chương 1 như sau : Max [fi(x1, . . . , xn)] (i=1, . . . , p) Min [gj(x1, . . . , xn)] (j=1, . . . , q) s.t. hk(x1, . . . , xn) £ ak (k=1, . . . , r) với x=(x1, . . . , xn)ỴPÌRn, P là tập bị chận và akỴRn (k=1, . . . , r) Gọi O(x) = ( f1(x), . . . , fp(x), g1(x), . . . , gq(x) ) là hàm vectơ p+q chiều. Bài toán tối ưu một mục tiêu là trường hợp đặc biệt của mô hình trên. CÁC BƯỚC TỔNG QUÁT CỦA GIẢI THUẬT TKNNTXS TRONG TỐI ƯU SỐ Giải Thuật TKNNTXS tối ưu số cho bài toán tối ưu đa mục tiêu (bài toán tối ưu một mục tiêu là trường hợp đặc biệt) được mô tả qua các bước tổng quát sau: Bước 1: Chọn ngẫu nhiên một lời giải khả thi L1. Bước 2: Tính giá trị mục tiêu O(L1) của L1. Bước 3: Thực hiện kỹ thuật tác động trực tiếp gây đột biến có định hướng theo hướng dẫn của xác suất trên lời giải khả thi L1 thành một lời giải khả thi mới L2. Bước 4: Tính giá trị mục tiêu O(L2) của L2. Bước 5: Nếu O(L2) tốt hơn hay bằng O(L1) thì thực hiện phép gán L1:=L2 và O(L1):=O(L2). Bước 6: Nếu điều kiện dừng của giải thuật được thỏa thì giải thuật chấm dứt tại đây. Bước 7: Quay trở lại bước B3. Thông thường điều kiện dừng của giải thuật là một ngưỡng khá lớn cho số lần lặp hoặc lời giải khả thi đang có đã đạt được một độ tốt đối với bài toán đang xét mà giải thuật có thể thỏa mãn được trong một thời gian hữu hạn. Trong bước 5 chúng ta sử dụng khái niệm “tốt hơn hay bằng” được hiểu theo nghĩa như sau Đối với bài toán tối ưu một mục tiêu: “£” : đối với bài toán lấy min “³” : đối với bài toán lấy Max Đối với bài toán tối ưu đa mục tiêu: theo nghĩa tối ưu Pareto Do cho phép chọn các lời giải mới “tốt hơn hay bằng” lời giải cũ nên giải thuật cho phép nhiều lời giải khả thi mới có cùng giá trị mục tiêu với lời giải cũ xuất hiện trong quá trình tìm kiếm, vì vậy giải thuật có thể tìm được nhiều lời giải tối ưu hoặc gần tốùi ưu khác nhau trong một lân cận nếu có. MÔ TẢ CẤU TRÚC DỮ LIỆU Không sử dụng mã hóa nhị phân, mà sử dụng mã hóa theo kiểu dấu chấm cố định. Cấu trúc của một lời giải là một bộ gồm n số thực tương ứng với n biến lấy quyết định. Mỗi số thực được biểu diễn như là một dãy con có m thành phần, mỗi thành phần là một chữ số của số thực, nghĩa là mỗi thành phần có giá trị là số nguyên từ 0 đến 9. Vì vậy số các số lẻ của độ chính xác mà bài toán đòi hỏi là tùy ý về mặt lý thuyết. Bây giờ ta có thể mã hoá một lời giải a như là một mảng hai chiều a[i, j] với a[i, j] có giá trị là các số nguyên từ 0 đến 9 và 1£i£n, 1£j£m. KỸ THUẬT GÂY ĐỘT BIẾN CÓ ĐỊNH HƯỚNG THEO XÁC SUẤT Để đột biến một lời giải khả thi ban đầu a[i, j] thành một lời giải khả thi mới b[i, j], với 1£i£n và 1£j£m, thì có hai vấn đề: Vấn đề thứ nhất là trong n biến quyết định của một lời giải khả thi hiện đang có, cần phải đột biến bao nhiêu biến trong một lần lặp thì mang lại hiệu quả cao nhất theo nghĩa xác suất cho ra một lời giải khả thi mới có giá trị hàm mục tiêu tốt hơn là cao nhất. Nếu đột biến chỉ một biến hoặc đột biến tất cả n biến trong một lần lặp thì có nhiều khả năng làm cho lời giải trở nên xấu đi rất nhiều và thậm chí không khả thi. Do đó vấn đề đặt ra là tìm kiếm một số k (1£k£n) sao cho trong quá trình vận động và đột biến của giải thuật, số biến tương tác với nhau nhiều nhất là k đủ để phát sinh ra các lời giải khả thi mới tốt hơn lời giải khả thi hiện hành. Vấn đề thứ hai là khi chọn được một biến quyết định để tiến hành đột biến thì phải đột biến số thực đó thành một số thực mới sao cho cả hai khả năng sau đều có thể xảy ra: Khả năng tối ưu số: số thực mới phải ở lân cận với số thực cũ trong không gian tìm kiếm để có khả năng đạt giá trị mục tiêu tốt hơn, nhưng điều này có thể đem đến tối ưu địa phương. Sự kiện này tương đương với đột biến các chữ số số phía bên phải của biến quyết định và nó mang ý nghĩa di truyền bằng cách thừa hưởng các giá trị tốt của các chữ số phía bên trái của lời giải khả thi hiện hành. Khả năng vượt qua tối ưu địa phương: số thực mới ở cách xa với số thực cũ trong không gian tìm kiếm để nó có khả năng tìm kiếm được một giá trị mục tiêu tối ưu toàn cục tốt hơn nếu có, điều này làm cho giải thuật có thể thoát ra được các bẫy tối ưu địa phương và làm tăng tốc độ hội tụ theo kiểu nhảy vọt trong một số các lần lặp đầu tiên. Sự kiện này tương đương với đột biến các chữ số phía bên trái của biến quyết định. Lời giải khả thi mới có tính đột phá và nó không mang ý nghĩa di truyền vì lời giải khả thi mới không thừa hưởng các giá trị tốt của lời giải khả thi hiện hành. Chúng ta tìm kiếm một kỹ thuật tác động trực tiếp gây đột biến có định hướng theo hướng dẫn của xác suất trên các chữ số của các biến quyết định để sao cho qua một lần đột biến chúng ta có thể kiểm soát và điều chỉnh được hai yếu tố sau: Khả năng thay đổi hay xác suất cho phép đột biến tại mỗi chữ số của biến quyết định Số trung bình các chữ số thay đổi giá trị của biến quyết định sau một lần đột biến. Tổng quát, vì không biết vai trò của các biến quyết định trong việc định giá hàm mục tiêu tương quan với nhau như thế nào, nên chúng ta có thể giả sử chúng có vai trò giống nhau. Từ đó ta có thể giả sử xác suất đột biến tại chữ số thứ j (j=1, . . . , m) của mỗi biến quyết định là như nhau. Gọi pj là xác suất đột biến tại chữ số thứ j (j=1, . . . , m) của mỗi biến lấy quyết định. Vì các chữ số bên trái có vai trò quan trọng hơn các chữ số bên phải trong việc định giá hàm mục tiêu, nên kỹ thuật đột biến có định hướng là tác động trực tiếp lên mỗi chữ số lần lượt theo thứ tự từ trái sang phải của mỗi biến quyết định xi với xác suất đột biến tương ứng là pj (j=1, . . . , m). Khi xác suất đột biến pj xảy ra thì có 3 khuynh hướng đột biến tại chữ số thứ j tương ứng với các xác suất r1, r2 và r3 (r1+r2+r3=1) như sau r1: lấy một giá trị ngẫu nhiên từ 0 đến 9 r2: tăng giá trị cũ lên một đơn vị r3: giảm giá trị cũ xuống một đơn vị Kỹ thuật đột biến có định hướng trên các chữ số của biến quyết định thứ i (1£i£n) được mô tả chi tiết trong đoạn chương trình sau: for j:=1 to m do if Xác_suất_biến cố_ngẫu_nhiên_1 = pj then if Xác_suất_biến cố_ngẫu_nhiên_2 = r1 else if Xác_suất_biến cố_ngẫu_nhiên_2 = r2 else (* Xác_suất_biến cố_ngẫu_nhiên_2 = r3 *) else (* Xác_suất_biến cố_ngẫu_nhiên_1 = 1-pj *) ; Kỹ thuật đột biến tại một chữ số trên đây có thể được bổ xung thêm các trường hợp tăng/giảm hai đơn vị và tăng/giảm ba đơn vị tùy theo sự tương tác giữa các biến quyết định với nhau trong một bài toán cụ thể. Theo cách này chúng ta có thể kiểm soát và điều chỉnh được hai yếu tố sau: Khả năng thay đổi hay xác suất đột biến tại chữ số thứ j của biến quyết định là pj Số trung bình các chữ số của biến quyết định có thay đổi giá trị trong sau một lần đột biến là [p1+p2 + . . . +pm] +1. Vấn đề còn lại là chúng ta phải xác định được các bộ xác suất (p1, p2, . . . , pm) và (r1, r2, r3) nào là tối ưu cho việc thực thi. TÍNH TOÁN CÁC BỘ XÁC SUẤT ĐỘT BIẾN TỐI ƯU TÍNH TOÁN BỘ XÁC SUẤT P=(p1, p2 , . . . , pm) Gọi bộ xác suất đột biến ban đầu là (q1, q2, . . . , qm). Nhận xét rằng: Xác suất để chữ số thứ nhất tìm được giá trị đúng trong lời giải tối ưu là q1*1/10 Xác suất trên lớn nhất khi q1= 1 Để chữ số thứ hai tìm được giá trị đúng thì chữ số thứ nhất phải đã được tìm đúng và được giữ cố định, nên xác suất để chữ số thứ hai tìm được giá trị đúng của nó là (q1*1/10)*(1-q1 )*q2*1/10 = (1/100)*(1-q1)*q1*q2 Vì q1 và q2 độc lập nên xác suất trên lớn nhất khi q1=1/2 và q2=1. Để chữ số thứ ba tìm được giá trị đúng thì chữ số thứ nhất và chữ số thứ hai phải đã được tìm đúng và được giữ cố định, nên xác suất để chữ số thứ ba tìm được giá trị đúng của nó là [q1*1/10]*[(1-q1 )*q2*1/10]*[ (1-q1 )*(1-q2)*q3*1/10] = (1/1000)*[q1*(1-q1)2]*[q2*(1-q2)]*q3 Vì q1, q2, q3 độc lập nên xác suất trên lớn nhất khi q1=1/3, q2=1/2, q3=1 Tổng quát, để tìm kiếm chữ số thứ j (1<j£m) tìm được giá trị đúng thì các chữ số phía bên trái từ chữ số thứ nhất đến chữ số thứ j-1 phải được tìm đúng và được giữ cố định, nên xác suất để chữ số thứ j tìm được giá trị đúng là Vì các xác suất qj (1£j£m) độc lập với nhau, nên xác suất q lớn nhất khi và chỉ khi các thành phần trong ngoặc vuông của phương trình (4-1) là lớn nhất. Khi đó ta có: [q1*(1-q1)j-1] lớn nhất ĩ q1=1/j [q2*(1-q2)j-2] lớn nhất ĩ q2=1/(j-1) . . . [qj-1*(1-qj-1)] lớn nhất ĩ qj-1=1/2 qj lớn nhất ĩ qj=1 Vậy bộ xác suất (q1, q2, . . . , qj) tối ưu để chữ số thứ j (j=1, . . . , m) đạt được giá trị đúng của nó là Cuối cùng, bộ xác suất trung bình tối ưu (p1, p2, . . . , pm) để tất cả các chữ số từ vị trí thứ 1 đến vị trí thứ m đều có khả năng đạt được giá trị đúng của nó trong một lời giải tối ưu được tính như sau: Tổng quát ta có công thức Từ đó ta có thể tính số trung bình vị trí thay đổi của một biến lấy quyết định sau một lần thực hiện đột biến là [S] hay [S]+1 với S được tính bởi công thức sau Ví dụ: Biến lấy quyết định có phần nguyên có một chữ số và độ chính xác lấy đến 8 số lẻ thì ta có m=9. Bộ xác suất đột biến trung bình tối ưu P=(p1, p2, p3, p4,p5, p6, p7, p8, p9) để biến quyết định tìm được con số đúng của nó là vậy bộ xác suất đột biến trung bình tối ưu là P=(0.31, 0.34, 0.37, 0.40, 0.45, 0.52, 0.61, 0.75, 1) (2) Nhận xét trong một biến lấy quyết định, các chữ số phía bến trái có vai trò cao hơn các chữ số phía bên phải trong việc định giá hàm mục tiêu. Vì vậy các giải thuật tối ưu số bao giờ cũng tìm được các chữ số phía bên trái một cách nhanh chóng và dễ dàng hơn các chữ số phía bên phải. Do đó để tối ưu số thì trong giải thuật đề nghị, các xác suất biến đổi tại mỗi chữ số phải tăng dần từ trái qua phải. Kết quả tính toán trên (4-2) đã chứng minh nhận xét này là đúng. Ta có 0.31+0.34+0.37+0.40+0.45+0.52+0.61+0.756+1=4.75 Vì vậy sau một lần đột biến thì trong 9 chữ số của số thực của biến quyết định chỉ có khả năng thay đổi trung bình 4 hay 5 chữ số. Nếu các chữ số thay đổi nằm phía bên phải của số thực sẽ cho ta một số thực mới rất gần với số thực cũ, nghĩa là lời giải mới được phát sinh sẽ nằm trong một lân cận của lời giải ban đầu trong không gian tìm kiếm để có khả năng làm giá trị hàm mục tiêu xấp xỉ tối ưu tốt hơn. Nếu có các chữ số thay đổi nằm phía bên trái của số thực sẽ cho ta một số thực mới rất xa với số thực cũ, nghĩa là lời giải mới được phát sinh cách xa các lân cận của lời giải ban đầu trong không gian tìm kiếm và điều này sẽ giúp giải thuật có khả năng tạo ra các lời giải mới vượt qua được các tối ưu địa phương nếu có. Nếu các chữ số thay đổi nằm tại các vị trí ở giữa số thực sẽ giúp tạo ra sự phong phú và đa dạng của các lời giải mới nhằm tìm kiếm những lời giải lạ, hiếm hoi và tăng tốc độ tối ưu số một cách nhảy vọt. TÍNH TOÁN BỘ XÁC SUẤT (r1, r2, r3) Xét hai chữ số kề nhau a1 và a2, khi trạng thái của chữ số a1 là giữ nguyên, trạng thái của chữ số a2 rơi vào trong một các trường hợp tương ứng với xác suất r1, r2 và r3 thì ta có các trường hợp sau xảy ra: Th1: Nếu chữ số a1 đã có giá trị đúng của lời giải tối ưu, khi đó xác suất để cả hai chữ số a1 và a2 đồng thời có các giá trị đúng là vì r1+ r2 + r3 = 1, nên xác suất trên lớn nhất khi và chỉ khi r1=1, r2= r3=0 Th2: Nếu chữ số a1 có giá trị sai so với giá trị của lời giải tối ưu, khi đó xác suất để cả hai chữ số a1 và a2 đồng thời có các giá trị đúng là vì r1+ r2 + r3 = 1 và các xác suất r2 và r3 có vai trò như nhau nên xác suất trên lớn nhất khi và chỉ khi r1=0, r2= r3=0.5. Lấy trung bình cho cả hai trường hợp trên ta có: r1=0.5, r2= r3=0.25 GIẢI THUẬT LAI GHÉP 3 CÁ THỂ Ta khảo sát sự lai ghép giữa một lời giải a và n lời giải b1, b2, . , bn. Bây giờ chúng ta xem xét quá trình đột biến tại chữ số thứ i của một biến quyết định của lời giải a. Ta có các trường hợp sau: Trường hợp chữ số thứ i-1 của biến quyết định tương ứng của lời giải a là đúng Gọi p là xác suất đột biến lấy giá trị ngẫu nhiên tại một chữ số thứ i đó. Gọi q là xác suất đột biến cho phép lấy giá trị của chữ số thứ i của một biến quyết định tương ứng trong các lời giải b1, b2, .. , bn. Trường hợp chữ số thứ i-1 của biến quyết định tương ứng của lời giải a là sai Gọi r là xác suất đột biến tăng/giảm một đơn vị tại chữ số thứ i của lời giải a cho trường hợp chữ số trước đó (thứ i-1) là sai. Ta có các công thức sau: Khi các lời giải đã đạt được giá trị gần tối ưu ta có bảng so sánh sau Xác suất 1 lời giải 2 lời giải 3 lời giải 4 lời giải Đột biến ngẫu nhiên Duy trì giá trị tốt đã có Đột biến tăng/giảm một 33% 33% 33% 20% 60% 20% 11% 78% 11% 6% 88% 6% Nhận xét: Khi các lời giải đã đạt được giá trị gần tối ưu thì kỹ thuật lai ghép ba cá thể cho ta: Xác suất duy trì các giá trị tốt đã có là 78% Xác suất đột biến ngẫu nhiên là 11% Xác suất đột biến tăng/giảm là 11% Với bộ xác suất trên sẽ cho chúng ta duy trì được các giá trị tốt đã có được của lời giải và đột biến đủ nhỏ để không gây ra rối loạn các giá trị mà vẫn có thể tạo ra các giá trị tốt một cách bất ngờ. Ví dụ: Ta khảo sát sự lai ghép giữa một lời giải a và n=3 lời giải b1, b2, b3 Trường hợp p q1 q2 q3 r Chữ số thứ i-1 đúng 1 0 0 0 0 0 0 0 0 1 0 0 ½ ½ 0 1/3 0 0 1 0 ½ 0 ½ 1/3 0 0 0 1 0 ½ ½ 1/3 0 0 0 0 0 0 0 0 Chữ số thứ i-1 sai 0 0 0 0 1 Trung bình 1/9 7/27 7/27 7/27 1/9 11% 78% 11% ĐỘ PHỨC TẠP CỦA GIẢI THUẬT TKNNTXS Xét bài toán có lời giải gồm n biến quyết định và mỗi biến quyết định có m chữ số. Giả sử việc biến đổi của lời giải khả thi phụ thuộc vào k (1£k£n) biến quyết định, nghĩa là trong một vòng lặp chỉ cần chọn ra trung bình k biến quyết định để gây tác động biến đổi thì đủ để đạt được lời giải khả thi tốt hơn lời giải khả thi đang có. Do đó xác suất để một biến quyết định được chọn trong một lần lặp là k/n và ta có xác suất để một biến quyết định có khả năng lần lượt tìm được các chữ số đúng từ trái qua phải của lời giải tối ưu là Chữ số thứ 1: Số lần lặp là: Chữ số thứ 2: Số lần lặp là: . . . . . . . . . . . . Chữ số thứ m: Số lần lặp là: Tổng số lần lặp để giải thuật có khả năng tìm được lời giải tối ưu lần đầu tiên là Xác suất để giải thuật tìm được lời giải tối ưu lần đầu tiên là Gọi vì nên và do pm=1, ta có số lần lặp: Trong một lần lặp, giải thuật thực hiện k*m phép tính bao gồm một phép thử và một phép gán có thời gian là t, ta có độ phức tạp của giải thuật là Nếu số chữ số là m cố định, thì giải thuật có độ phức tạp phụ thuộc vào các số k và n. Trường hợp tốt nhất: k=1 Sự đột biến của các chữ số của một biến quyết định không phụ thuộc vào các biến quyết định khác. Ta có độ phức tạp của giải thuật là Khi đó giải thuật có độ phức tạp tương đương với O(n) Ví dụ: Bài toán có sự đột biến của các chữ số của một biến quyết định không phụ thuộc vào các biến quyết định khác như sau Trường hợp xấu nhất: k=n Sự đột biến của một biến quyết định phụ thuộc vào tất cả các biến quyết định còn lại. Ta có độ phức tạp của giải thuật là Khi đó giải thuật có độ phức tạp tương đương với O(10n) Ví dụ: Bài toán có sự đột biến của các chữ số của một biến quyết định phụ thuộc vào các biến quyết định khác Cho hàm 1 nếu x1=x2=x3=5.5555 f(x1, x2, x3)= 0 ngược lại Tính max f(x) sao cho 0£xi £10 (i=1, . . . , 3) Kết luận: Độ phức tạp O của giải thuật tùy thuộc vào sự tương tác giữa các chữ số của các biến quyết định với nhau trong một bài toán cụ thể và ta có O(n) £ O£O(10n) Xét trường hợp bài toán có n biến quyết định với n khá lớn (n>100), trong một lần lặp của giải thuật nếu tác động đồng thời trên n biến thì có thể chỉ đem đến hậu quả xấu cho lời giải khả thi hiện đang có mà thôi, do đó để tìm kiếm lời giải gần tối ưu thì trong một số lần lặp đầu chúng ta cho số k biến động khá lớn (từ 30% đến 70%) để tìm một đỉnh tốt nhất, sau đó để tối ưu số (leo đồi) chúng ta cho số k biến động nhỏ (từ 2% đến khoảng 20%) thì chúng ta có thể tìm được các lời giải gần tối ưu rất tốt. Ví dụ: Tối ưu một lời giải khả thi có n biến, mỗi biến có 1 chữ số phần nguyên và 4 chữ số phần lẻ. Ta có Trường hợp 1: Sự đột biến của một biến không phụ thuộc vào các biến khác Trường hợp 2: Sự đột biến của một biến phụ thuộc vào các biến khác Vì vậy số lần lặp để có khả năng tìm được lời giải tối ưu lần đầu tiên là nằm trong khoảng [660*n, 1726*10n] Khi n=2, số lần lặp để có khả năng tìm được lời giải tối ưu lần đầu tiên là nằm trong khoảng [1320, 172600] ƯU ĐIỂM VÀ KHUYẾT ĐIỂM CỦA GIẢI THUẬT TKNNTXS Tùy theo sự tương tác giữa k (1£k£n) biến quyết định với nhau trong một bài toán cụ thể mà độ phức tạp của giải thuật TKNNTXS nằm từ O(n) đến O(10n). Khi kích thước bài toán khá lớn (n>100), trong một số lần lặp đầu chúng ta cho số k biến động khá lớn (từ 30% đến 70%) để tìm một đỉnh tốt nhất, sau đó để leo đồi (tối ưu số) chúng ta cho số k biến động nhỏ (từ 2/n đến khoảng 20%) thì chúng ta có thể tìm được một lời giải gần tối ưu rất tốt. Bên cạnh đó một ưu điểm của giải thuật TKNNTXS là nó có thể sản sinh ra lần lượt nhiều lời giải tối ưu trong một lần thực nghiệm nếu có. Về khuyết điểm, cũng giống như các giải thuật mang tính ngẫu nhiên cao khác, giải thuật TKNNTXS cần phải có thời gian thực thi và phải thực thi nhiều lần để có thể tìm kiếm được lời giải tối ưu. Tuy nhiên số lần lặp của giải thuật TKNNTXS là rất lớn. Hầu hết các giải thuật tối ưu hoá đều là các phương pháp lặp. Để giải một bài toán tối ưu hóa, các nhà nghiên cứu các phương pháp toán học truyền thống và các giải thuật tiến hóa đều cố gắng cải tiến thuật toán sao cho trong một số lần lặp ít nhất mà vẫn đạt được lời giải gần tối ưu tốt nhất. Còn giải thuật TKNNTXS đòi hỏi số lần lặp rất lớn để tìm ra được lời giải tối ưu, đó là cái giá phải trả để đảm bảo cho việc giải thuật có khả năng tìm được lời giải tối ưu toàn cục và đạt được kết quả tối ưu số theo một cách tốt nhất có thể có được. Phần 5 CẤU TRÚC CỦA CHƯƠNG TRÌNH TỐI ƯU CÁCH GIẢI QUYẾT YÊU CẦU NGHIỆP VỤ NẠP DỮ LIỆU NGUỒN VÀO Khởi động các trị BEGIN Đọc chuỗi Chuỗi=”” Buffer ¬ chuỗi lookahead ¬ token entry ¬ trị từ vựng Gọi hàm phân tích cú pháp END False True CẤU TRÚC CHƯƠNG TRÌNH TRUE BEGIN Entry=HÀM Phân tích hàm Lưu hàm vào cấu trúc trúc trung gian Ghi nhận các biến và lưu vao cấu trúc trung gian Entry=RÀNG BUỘC Phân tích RÀNG BUỘC Lưu RÀNG BUỘC vào cấu trúc trúc trung gian Ghi nhận các biến và lưu vao cấu trúc trung gian FALSE Phát sinh giá trị cho biến và tối ưu giá trị đó. Gán giá trị vào các biến Tính các hàm và các ràng buộc In kết quả các biến tối ưu Thỏa Ràng buộc Không thỏa CÁCH TỔ CHỨC DỮ LIỆU NODE DÙNG CHO “BIẾN” CỦA HÀM HAY RÀNG BUỘC value_Var ide_Var value_Var : Giá trị của biến ide_Var : Định danh của biến (tên biến) NODE DÙNG CHO MỘT HÀM RÀNG BUỘC Value_Rela nNoRe ide_Rela() value_Rela : Giá trị chung của 1 ràng buộc (kết quả của ràng buộc) nNoRe : Số các phần tử của một ràng buộc ide_Rela() : Mảng các phần tử trong 1 ràng buộc. NODE DÙNG CHO MỘT HÀM express_Func() nFunc value_Func str_Var() nVar str_Rela() nRela express_Func() :Mảng các phần tử trong 1 hàm nFunc :Số các phần tử trong 1 hàm value_Func :Giá trị của hàm str_Var() :Mảng các biến có liên quan đến hàm nVar :Số các biến có trong toàn bộ 1 hàm str_Rela() :Mảng các ràng buộc có liên quan đến hàm nRela :Số các ràng buộc có trong toàn bộ 1 hàm. CÁCH TÍNH GIÁ TRỊ CHO 1 HÀM HAY 1 RÀNG BUỘC SƠ ĐỒ THỰC HIỆN Đổi sang biểu thức Hậu Tố BEGIN Đưa giá trị vào các phần tử của Node Hàm(Ràng Buộc) Chuỗi=”” Tính giá trị END False True Chuỗi = Đọc giá trị các phần tử của Node Hàm(Ràng Buộc) GIẢI THUẬT CHUYỂN ĐỔI TỪ DẠNG TRUNG TỐ SANG HẬU TỐ BA LAN NGƯỢC Có nhiều giải thuật cho việc chuyển đổi từ một biểu thức số học dạng trung tố sang biểu thức số học dạng hậu tố Ba Lan ngược. Giải thuật được trình bày dưới đây là một ý tưởng của E.W.Dijkstra. Giả sử rằng một biểu thức được kết hợp với các ký hiệu sau: Các biến. Các phép toán có hai toán hạng (+,-,*,/). Các ký tự đại diện 1 hàm số bất kỳ, ký hiệu số mũ, các dấu Relop. Các dấu ngoặc trái hay phải. GIẢI THUẬT: Ta cho máy đọc từng ký tự một trong biểu thức dạng trung tố, bắt đầu từ bên trái cho tới khi gặp ký tự kết thúc “$” lần thứ hai. Tùy theo ký tự được đọc và ký tự ở đỉnh stack ta có các tác vụ sau: Ký tự bắt đầu “$” luôn được đẩy vào stack. Các ký tự là biến luôn được ghi ra, không cất vào stack Các ký tự được đọc +, -, *, /, và ký tự kết thúc $ có tác vụ được thực hiện theo mã số tác vụ được mô tả trong bảng sau: Ký tự được đọc $ Hàm ^ + - * / Relop ( ) Ký tự tại đỉnh stack $ 4 1 1 1 1 1 1 1 1 5 Hàm 2 2 2 2 2 2 2 2 1 2 ^ 2 1 2 2 2 2 2 2 1 2 + 2 1 1 2 2 1 1 2 1 2 - 2 1 1 2 2 1 1 2 1 2 * 2 1 1 2 2 2 2 2 1 2 / 2 1 1 2 2 2 2 2 1 2 Relop 2 1 1 1 1 1 1 2 1 2 ( 5 1 1 1 1 1 1 1 1 3 Trong đó : Hàm : chỉ là một ký tự đại diện cho hàm Relop : Các phép so sánh , =, ³, £, Các tác vụ có mã số là: Push Pop và ghi ra Xóa ký tự đang đọc và xóa ký tự trong stack (pop nhưng không ghi ra) Giải thuật kết thúc. Kết quả biểu thức đã được ghi ra. Giải thuật dừng. Thông báo có một lỗi xuất hiện. Biểu thức gốc không được cân đối đúng. Đối với các hàm mà người sử dụng nhập vào, chương trình sẽ đọc và gán cho 1 ký tự mà chương trình đã được lập trình sẵn để nhận biết hàm đó cho việc tính toán sau này. Sau mỗi tác vụ được lấy, một phép so sánh mới được thực hiện giữa ký tự đang đọc, nó có thể là ký tự ở lần so sánh trước hay là ký tự kế, với ký tự ở đỉnh stack. Quá trình tiếp tục cho đến bước 4 thì đạt kết quả. Thứ tự của các biến là như nhau trong cả hai dạng trung tố và dạng hậu tố Balan ngược. Tuy nhiên, thứ tự của các toán tử là khác nhau. Các toán tử xuất hiện trong dạng hậu tố Ba Lan ngược thì theo thứ tự mà chúng thực sự được thực thi trong việc đánh giá biểu thức. Ví dụ: (8+2*5)/(1+3*2-4) ®Hậu tố: 8 2 5 * + 1 3 2 * + 4 - / ĐỊNH GIÁ BIỂU THỨC DẠNG HẬU TỐ BA LAN NGƯỢC Giải thuật sau định giá biểu thức dạng hậu tố Ba Lan ngược: Bước 1: Ta xét từng ký tự trong biểu thức dạng hậu tố Ba Lan ngược, bắt đầu từ bên trái cho đến khi gặp một toán tử, hàm, relop, hay dấu mũ(^). Bước 2: Ghi toán tử hay relop và hai toán hạng ngay sát bên trái của nó ra giấy nháp (đối với hàm, dấu ^ thì chỉ ghi 1 toán tử). Bước 3: Xóa toán tử và hai toán hạng đó trong biểu thức, tạo ra một khoảng trống. Bước 4: Thực hiện phép toán cho bởi toán tử trên hai(một đối với hàm và dấu mũ) toán hạng và ghi kết quả vào khoảng trống. Bước 5: Nếu biểu thức chỉ còn chứa một giá trị thì đó là kết quả và giải thuật kết thúc, ngược lại thực hiện lại bước 1. Giải thuật định giá biểu thức dạng hậu tố Ba Lan ngược trên máy tính với Stack: Cho biểu thức có n ký hiệu, mỗi ký hiệu là một biến hay một toán tử (hay hàm, relop, dấu mũ). Ta thực hiện lần lược các bước sau: Bước 1 : Đặt k = 1 Bước 2: Xét ký tự thứ k: Nếu ký tự đó là một biến, cất nó vào stack Nếu ký tự đó là một toán tử, lần lượt lấy từ đỉnh stack hai toán hạng (toán hạng bên phải trước, kế đó là toán hạng bên trái), thực hiện phép toán và đẩy ngước kết quả lên stack. Nếu ký tự đó là một đại diện cho một hàm số bất kỳ hay dấu mũ , lấy từ đỉnh stack một toán hạng, thực hiện phép toán và đẩy ngược lên stack Bước 3: Nếu k = n, giải thuật kết thúc, kết quả nằm trong Stack Ngược lại, cộng 1 vào k, và thực hiện lại bước 2. Lưu ý: Con số trên đỉnh stack là toán hạng bên phải, không là toán hạng bên trái. Điều này quan trọng đối với các phép toán trừ và phép toán chia vì thứ tự của các toán hạng có ý nghĩa (không giống như phép cộng và phép nhân). CÁC MÀN HÌNH CHÍNH CỦA CHƯƠNG TRÌNH MÀN HÌNH SPLASH MÀN HÌNH MENU MÀN HÌNH LỰA CHỌN CÁCH NHẬP HÀM MÀN HÌNH NHẬP HÀM MÀN HÌNH NHẬP RÀNG BUỘC MÀN HÌNH LỰA CHỌN CÁCH TỐI ƯU MÀN HÌNH KẾT QUẢ MỘT SỐ THỬ NGHIỆM BÀI TOÁN 1 CỦA NGUYỄN TRỌNG TOÀN f(x) = (x1-3.69)^2+(x2-12)^2 ® min với các ràng buộc x1+x2<=30 -x1+(18*x2*x2/484)-10<=0 -(x1*x1)-(x2*x2)+484<=0 Min của giải thuật của GS. H. Tụy là:89.2171143125 với x=(6.48079,21.02378) Min của chương trình đạt được là: 89.217055385973 với x=(6.475902,21.025287) BÀI TOÁN 2 CỦA NGUYỄN TRỌNG TOÀN f(x) = (x1-2)^2+(x2-1)^2 ® min với các ràng buộc x1+x2<=5 x1^2-4.4*x1+x2^2-2.4*x2+4.03<=0 4*x1-x1^2-0.36*x2^2-2.56<=0 Min của giải thuật của GS. H. Tụy là:0.8785081249 với x=(2.77534,1.526646) Min của chương trình đạt được là: 0.877508004147348 với x=(2.7464411039,1.5659802846) BÀI TOÁN 3 VỀ HÀM PHI TUYẾN ROSENBROCK f(x) = 100*(x2-x1^2)+(1-x1)^2® min với các ràng buộc x1+x2^2>=0 x1^2+x2>=0 x1<=0.5 x2<=10 Nghiệm tối ưu toàn cục là:0.25 với x=(0.5,0.25) Min của chương trình đạt được là: 0.25 với x=(0.5,0.25) BÀI TOÁN 4 CỦA THẠC SĨ PHẠM HOÀNG VƯƠNG f(x) = x1+4*x2+x3® min với các ràng buộc 2*x1+3*x2+4*x3>=20 5*x1-x2+2*x3>=12 x1+2*x2-x3<=2<=0.5 -x1+4*x2-2*x3<=1 Nghiệm tối ưu toàn cục là:5.25 với x=(0.5,0,4.75) Min của chương trình đạt được là: 5.25 với x=(0.5,0,4.75) BÀI TOÁN 5 CỦA THẠC SĨ PHẠM HOÀNG VƯƠNG f(x) = x1+2*x2+3*x3+4*x4+5*x5® max với các ràng buộc x1+2*x2+3*x3-4*x4+5*x5<=0 2*x3+x4+3*x5<=4 3*x1+4*x3+x5<=3 x2-x3+2*x5<=2 4*x2+3*x3+x4+2*x5>=1 Nghiệm tối ưu toàn cục là : 21 với x=(1,2,0,4,0) Max của chương trình đạt được là: 21 với x=(1,2,0,4,0) BÀI TOÁN 6 CỦA THẠC SĨ PHẠM HOÀNG VƯƠNG Trong tam giác ABC, ta có sin2A+sin2B+sin2C<=9/4. Ta kiểm tra lại kết quả này bằng cách chuyển về bài toán tìm : Max f(x1,x2) = sin2x1+sin2x2+sin2(3.14-x1-x2) với các ràng buộc x1+x2<=3.14 Nghiệm do thạc sĩ Phạm Hoàng Vương tìm được là 2.25 Max của chương trình đạt được là: 2.2486202990331 với x=(1.046667,1.046667) BÀI TOÁN 7 CỦA HIMMELBLAU f(x) = 5.3578547*x3*x3+0.8356891*x1*x5+37.293239*x1-40792.141® min với các ràng buộc 85.334407+0.0056858*x2*x5+0.00026*x1*x4-0.0022053*x3*x5>=0 85.334407+0.0056858*x2*x5+0.00026*x1*x4-0.0022053*x3*x5<=92 80.51249+0.0071317*x2*x5+0.0029955*x1*x2+0.0021813*x3*x3>=90 80.51249+0.0071317*x2*x5+0.0029955*x1*x2+0.0021813*x3*x3<=110 9.300961+0.0047026*x3*x5+0.0012547*x1*x3+0.0019085*x3*x4>=20 9.300961+0.0047026*x3*x5+0.0012547*x1*x3+0.0019085*x3*x4<=25 78<=x1<=102 33<=x2<=45 27<=x3<=45 27<=x4<=45 27<=x5<=45 Để giải bài toán này, Himmelblau đã sử dụng phương pháp toán học truyền thống giảm độ dốc tổng quát. Gen và Cheng sử dụng giải thuật di truyền dựa trên tham khảo cả hai toàn cục và cục bộ. Homaifar, Qi và Lai sử dụng giải thuật di truyền với kích thước quần thể là 400. Gần đây nhất, Coello đã sử dụng kỹ thuật hàm phạt tự thích nghi cho tối ưu hóa dựa cơ sở trên giải thuật di truyền. Sử dụng giải thuật TKNNTXS với độ chính xác đến 6 số lẻ, chương trình thu được kết quả tốt hơn các kết quả đã được các nhà nghiên cứu khác tìm ra trước đây như được liệt kê trong bảng sau: Các Biến Lời giải tốt nhất đã tìm thấy Chương trình Coello Gen Hommaifar Himmelblau x1 x2 x3 x4 x5 g1(x) g2(x) g3(x) f(x) 78.000032 33.001783 27.099591 44.999976 44.880584 91.9862825504 100.388288041 20.0000022517 -31023.037906 78.0495 33.0070 27.0810 45.0000 44.9400 91.997635 100.40407857 20.001911 -31020.859 81.4900 34.0900 31.2400 42.2000 34.3700 90.522543 99.318806 20.060410 -30183.576 78.0000 33.0000 29.9950 45.0000 36.7760 90.714681 98.840511 19.999935 -30665.609 78.6200 33.4400 31.0700 44.1800 35.2200 90.520761 98.892933 20.131578 -30373.949 Kết quả của chương trình Phần 6 KẾT LUẬN KẾT LUẬN Chương trình mà tôi đã thực hiện đã giải quyết bài toán một mục tiêu các bài toán tối ưu bằng giải thuật tìm kiếm ngẫu nhiên theo xác suất. Giải thuật này cho chúng ta thấy được các kết quả tối ưu có độ chính xác cao và làm cho kết quả thu được tốt hơn. Luận án cũng đã giới thiệu đầy đủ các phương pháp cổ điển và các phương pháp khác để thực hiện giải quyết tối ưu một bài toán nào đó. Tuy nhiên, chương trình cũng có một số khuyết điểm như thời gian, tốc độ ... mà tôi sẽ cố gắng khắc phục nó để chương trình được hoàn thiện hơn. Trong tương lai, tôi mong muốn được học hỏi và nghiên cứu tiếp thuật giải này cũng như các thuật giải khác về vấn đề tối ưu hóa. HƯỚNG PHÁT TRIỂN Chương trình sẽ khắc phục được vấn đề về thời gian để đưa ra kết quả nhanh nhất. Chương trình sẽ được phát triển thành một ứng dụng web trên mạng.