Đề tài Tối ưu số cho bài toán tối ưu một mục tiêu

ặp xây dựng dãy íxký hội tụ tới điểm tối ưu (hay điểm dừng) x*. Giả sử ta đang ở điểm xk thuộc lân cận của x*, khi đó để làm cho hàm mục tiêu giảm ta nên chuyển động theo hướng p làm với f’(xk) một góc tù, tức là xác định. xk+1 = xk + ap, trong đó a > 0. (f’(xk),p) < 0. Thật vậy, khai triển f(x) theo chuỗi Taylo: F(x) = f(xk) + a( f,p) + a2/2 trong đó f = f’(xk), f = f’’(xkc), xkc = xk + q(x - xkc), q Ỵ [0,1]. Nếu < 0 thì với a nhỏ ta có f(x) < f(xk) (vì dấu của phần vế phải xác định bởi phần tuyến tính đối với a). Việc lựa chọn hướng dịch chuyển p và độ dài bước a khác nhau cho ta các phương pháp cực tiểu khác nhau. Phương pháp gradient (hay còn gọi là phương pháp tụt nhanh nhất) có dạng xk+1 = xk - akf’(xk), ak > 0, k = 0,1, ... (1) tức là chọn pk = f’(xk). Đây là phương pháp thông dụng nhất để tìm cực tiểu, nó rất đơn giản và áp dụng được cho những lớp hàm rất rộng. Thuật toán xác định ak tại mỗi bước lặp: Chọn giá trị tùy ý a (và cố định, ví dụ a = 1) và xác định điểm x=xk - af. Tính f(x) = f(xk - af). Kiểm tra bất đẳng thức f(x) – f(xk) £ ea = -ea êêf êê2, (2) trong đó 0 < e < 1 là một hằng số chọn tùy ý và cố định. Nếu (2) thỏa mãn thì ta chọn giá trị a làm giá trị phải tìm: ak=a. Nếu (2) không thỏa mãn thì ta chia a (bằng cách nhân a với số l < 1) cho đến khi bất đẳng thức (2) được thỏa mãn. Các dạng khác của phương pháp Gradient Phương pháp gradient với bước dịch chuyển cố định. Phương pháp gradient với việc cực tiểu hàm theo hương chuyển động. PHƯƠNG PHÁP MONTE-CARLO Phát biểu bài toán Trong kinh tế cũng như trong kỹ thuật, chúng ta thường gặp bài toán tối ưu mà hàm mục tiêu không phải là tuyến tính, không lồi, không lõm, còn miền ràng buộc cũng không lồi. Nhiều khi hàm mục tiêu không viết được dưới dạng hiển mà chỉ có một quy trình tính toán phức tạp để được một giá trị. Xét bài toán min f(x) (1) với các ràng buộc x Ỵ D (2) aj £ xj £ bj, j = 1, .... , n (3) trong đó x = (x1, ... , xn), D là một tập thuộc Rn và hàm mục tiêu f là ánh xạ từ Rn vào R1. Hàm f(x) và miền ràng buộc D có thể được xác định bởi những hàm phi tuyến rất khó tính. Để giải những bài toán như vậy, chúng ta chỉ còn hy vọng vào phương pháp Monte-Carlo để tìm lời giải tối ưu toàn cục. Phương pháp này chỉ áp dụng được cho bài toán (1)-(3) với số biến không nhiều (n £ 30). Nội dung phương pháp Biến it được dùng để đếm số điểm tạo ngẫu nhiên trong siêu hợp S=íx:aj £ xj £ bj, j = 1, .... , n ý Ì Rn, sf để đếm số phương án chấp nhận được tìm được. Tại mỗi bước lặp gọi x là phương án tốt nhất hiện biết với trị hàm mục tiêu a=f(x). Phương pháp Monte-Carlo gồm các bước sau: Bước 1: Đặt it = 0, sf = 0, a = M (M là số dương đủ lớn, chẳng hạn 1030). Bước 2: Mở đầu bước lặp với việc tăng số điểm tạo ngẫu nhiên lên một: it = it +1. Với mỗi j ta tạo một số ngẫu nhiên phân bố đều trên đoạn [aj, bj] theo công thức x’j = aj + x(bj - aj). (4) trong đó x là một số ngẫu nhiên phân bố đều trên đoạn [0,1]. Lưu ý rằng với mỗi số j số x trong (4) là khác nhau. Như vậy sau n lần tạo số ngẫu nhiên ta được một bộ giá trị x’=(x’j, ... , x’n). Bước 3: Kiểm tra xem x’ có thuộc D hay không. Nếu x’ Ï D thì chuyển lên bước 2. Nếu x’ Ỵ D thì số phương án tìm được tăng lên một đơn vị sf=sf + 1 và sang bước 4. Bước 4: Tính giá trị hàm mục tiêu f(x’) Nếu f(x’) > a thì chuyển tới bước 2. Nếu f(x’) < a (x’ là phương án của bài toán (1)-(3) tốt hơn phương án x cũ) thì lấy x’ thay cho x và lấy a = f(x’). Chuyển lên bước 2. Người ta có thể chứng minh được rằng nếu bài toán (1)-(3) có phương án tối ưu thì khi it đủ lớn ta có thể tìm được lời giải của bài toán với xác suất bằng 1. Cách dừng thuật toán: Trong quá trình giải, sau một số lần tạo điểm x’ theo (4) ta lại in lên màn hình số điểm chấp nhận được đã tìm được, giá trị hàm mục tiêu cùng phương án tốt nhất cho tới lúc này: sf, a và x. Nếu số điểm chấp nhận được đủ nhiều, phương án x và f(x) phù hợp với thực tiễn thì dừng tính toán. Nếu số bước lặp it đã quá lớn hoặc thời gian tính toán đã quá lâu mà giá trị hàm mục tiêu không cải tiến thêm thì dừng tính toán. Khi dừng tính toán theo cách này mà số phương án sf = 0 thì ta nghi ngờ bài toán (1)-(3) không có phương án, cần xét lại cách đặt các ràng buộc sao cho hợp lý. KẾT LUẬN Qua các phương pháp nêu trên, ta thấy có rất nhiều phương pháp để giải bài toán tối ưu hóa. Các phương pháp đều đưa ra được các lời giải tối ưu, nhưng chưa đạt được độ chính xác cao và đối với các bài toán lớn với hơn hàng trăm ràng buộc thì phải tốn nhiều thời gian để thực hiện các bước trong phương pháp. Để khắc phục các nhược điểm đó, người ta đã đưa ra một thuật giải mới : Thuật Giải Di Truyền. Phần 3 GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN TỔNG QUAN VỀ THUẬT GIẢI DI TRUYỀN (GENETIC ALGORITHMS - GA) ĐẠI CƯƠNG Trong sinh hoạt hằng ngày, chúng ta thường gặp những vấn đề từ đơn giản đến phức tạp như chọn trường cho con em, tìm đường đi ngắn nhất để đi làm, hoạch định chương trình chạy máy để tận dụng khả năng các dụng cụ Để giải quyết vấn đề thường dựa vào các phương thức sau: Dựa trên các công thức toán học hay những định luật khoa học (tiếp cận chính xác). Dựa theo ý kiến của các chuyên gia lĩnh vực (tiếp cận kinh nghiệm). Dựa theo sự tiến hóa, bắt chước lối cải thiện thích nghi mà con người hay sinh vật nói chung, đã dùng để tồn tại và phát triển (tiếp cận thử và sai). Phương thức dựa trên các công thức toán học hay những định luật khoa học thường cho những đáp số rất chính xác. Nhưng ta phải tìm ra công thức hay giả tưởng những điều kiện hoạt động cho giống với thực tế, điều này không thể thực hiện một cách dễ dàng. Trong những năm 70, mạng Nơron nhân tạo, logic mờ cùng với thuật giải di truyền được nghiện cứu và áp dụng trong việc giải quyết các trường hợp phức tạp. Nhìn chung, con người và sinh vật đều phải “tiến hóa để thích nghi với hoàn cảnh”. “Tiến hóa cho thích nghi” không có nghĩa là luôn tìm ra giải pháp tuyệt đối cho vấn đề, nhưng có thể chỉ là tương đối trong điều kiện cho phép. THUẬT GIẢI DI TRUYỀN GIẢI QUYẾT VẤN ĐỀ TRÊN MÁY VI TÍNH GA bắt nguồn từ ý niệm tiến hóa để tồn tại và phát triển trong tự nhiên. GA là phương thức giải quyết vấn đề bắt chước lối hành xử của con người để sinh tồn và phát triển. GA giải quyết được vấn đề trên máy vi tính nhờ vào chương trình tin học để thể hiện những ý tưởng cơ bản như tìm ra giải pháp tối ưu hay tốt nhất trong điều kiện thời gian và không gian cho phép. Không giống các phương pháp khác, GA xét đến toàn bộ các giải pháp, bằng cách xét trước nhất một số giải pháp, sau đó loại bỏ những thành phần không thích hợp và chọn những thành phần thích nghi hơn để tạo sinh và biến hóa nhằm mục đích tạo ra nhiều giải pháp mới có hệ số thích nghi ngày càng cao. Do đó khi giải quyết vấn đề bằng GA, chúng ta phải thông qua các giai đoạn sau: Chọn mô hình (model) để tượng trưng cho các giải pháp. Các mô hình có thể là dãy (String) những số nhị phân : 1 và 0, thập phân và có thể là chữ hay hỗn hợp của chữ và số. Aùp dụng lý luận và cách biến hóa trên mô hình này, thay vì trên các giải pháp. Chọn hàm số thích nghi để dùng làm tiêu chuan đánh giá các giải pháp. Tiếp tục các hình thức biến hóa cho đến khi đạt được giải pháp tốt nhất hoặc đến khi thời gian cho phép chấm dứt. Như vậy, GA là một hình thức tìm kiếm có tính ngẫu nhiên nhưng được hướng dẫn bởi hàm số thích nghi. GA không thể luôn tìm ra giải pháp tối ưu, nhưng chắc chắn sẽ cung cấp những giải pháp tương đối trên nền tảng vững chắc và trong thời gian nhanh nhất. TỔNG KẾT Tuy chỉ mới được hình thành cách đây chưa đầy 25 năm, GA đã có được cơ sở toán học vững chắc về lý thuyết và số lượng những áp dụng ngày càng gia tăng bao gồm nhiều lĩnh vực khác nhau. GA đã kết hợp với các kỹ thuật thuộc lĩnh vực trí tuệ nhân tạo như Expert Systems (Hệ Chuyên Gia), Artificial Neural Network (mạng Nơron nhân tạo) và Fuzzy Logic (Logic mờ) nhằm tìm giải pháp tối ưu cho những vấn đề phức tạp mà các phương thức cổ điển đã không giải quyết thỏa đáng. GA được ứng dụng trong nhiều lĩnh vực khác nhau. Nhìn chung, những ứng dụng này có thể chia làm 3 nhóm chính: Tìm mô hình tối ưu cho vấn đề. Tìm kiếmvà tối ưu hóa giải pháp là đề tài thích hợp nhất của GA. Hoạch định quy trình sản xuất, lộ trình chuyển vận, cách bố trí các bộ phận trong môi trường. Chọn lựa các nhóm hay thành phần trong một tổ chúc. Chúng ta cũng có thể sắp xếp các ứng dụng theo lĩnh vực như: quản trị, kinh tế-tài chính, kỹ thuật, nghiên cứu và phát triển. NHỮNG NGUYÊN TẮC CƠ BẢN CỦA THUẬT GIẢI DI TRUYỀN ĐẠI CƯƠNG GA không chú trọng đến giải pháp duy nhất và chính xác như phương pháp cổ điển, trái lại GA xét đến toàn bộ các giải pháp và chọn lấy giải pháp tương đối tốt nhất nếu không nói là tối ưu. GA tuy dựa trên tính ngẫu nhiên nhưng có hướng dẫn bởi hàm số thích nghi, do đó không có nghĩa là “đoán mò” như nhiều người hiểu lầm, trái lại GA có một nền tảng toán học vững chắc. CÁC TÍNH CHẤT ĐẶC THÙ CỦA THUẬT GIẢI DI TRUYỀN GA lập luận mang tính chất ngẫu nhiên (stochastic), thay vì xác định (deterministic) như toán học giải tích. GA duyệt xét toàn bộ các giải pháp, sau đó chọn lấy giải pháp tương đối tốt nhất dựa trên hệ số thích nghi. GA không để ý đến chi tiết vấn đề, trái lại chỉ chú ý đến giải pháp, đặc biệt là dãy số tượng trưng cho giải pháp. GA rất thích hợp cho việc tìm kiếm giải đáp cho vấn đề, hay tìm điều kiện tối ưu cho việc điều khiển, và phân nhóm những giải pháp có được. CÁC BƯỚC QUAN TRỌNG TRONG VIỆC ÁP DỤNG THUẬT GIẢI DI TRUYỀN Có 7 bước: Bước 1: Chọn mô hình cho giải pháp của vấn đề: chọn một số tượng trưng cho toàn bộ các giải pháp có thể cho vấn đề. Bước 2: chỉ định cho mỗi giải pháp một ký hiệu. Ký hiệu có thể là dãy của những số 1 và 0 thuộc hệ nhị phân, hay dãy số thập phân, dãy của chữ hay hỗn hợp của số và chữ. Bước 3: tìm hàm số thích nghi cho vấn đề và tính hệ số th1ch nghi cho từng giải pháp. Bước 4: dựa trên hệ số thích nghi của các giải pháp để thực hiện sự tạo sinh(reproduction) và biến hóa các giải pháp. Các phương thức biến hóa gồm: lai ghép (crossover), đột biến (mutation). Bước 5: tính các hệ số thích nghi cho các giải pháp mới và loại bỏ những giải pháp kém nhất để chỉ còn giữ lại một số nhất định các giải pháp. Bước 6: nếu chưa tìm được giải pháp tối ưu hay tương đối khá nhất, hay chưa hết hạn kỳ ấn định, trở lại bước 4 để tìm giải pháp mới. Bước 7: tìm ra được giải pháp tối ưu hoặc nếu thời gian cho phép đã chấm dứt thì báo cáo kết quả tính được. VÍ DỤ MINH HỌA Ví dụ: X2 = 64 Bước 1: qui định số lượng các đáp số và ấn định ký hiệu cho từng đáp số. Giả sử ta chưa biết đáp số, nên sẽ chọn 4 số trong những đáp số có thể có của bài toán. Đồng thời ta dùng hệ thống nhị phân để ký hiệu các đáp số. Thập phân 1 2 3 4 5 6 7 8 Nhị phân 0001 0010 0011 0100 0101 0110 0111 1000 Bước 2: chỉ định đáp số và ký hiệu các đáp số cho bài toán Sau đây 4 số có thể là đáp số cho bài toán: Thứ tự Nhị phân Thập phân 1 2 3 4 00100 10101 01010 11000 4 21 10 24 Bước 3: ấn định hàm số thích nghi (fitness Function) và tính hệ số thích nghi (fitness) cho từng đáp số. Chúng ta có thể chọn bất cứ hệ thức hay hàm số nào để biểu diễn sự thích nghi của các đáp số của bài toán. Ta chọn hàm số thích nghi : 1000-(X2-64) và quy định đáp số nào có hệ số thích nghi bằng 1000 hay gần 1000 nhất sẽ là đáp số của bài toán. Thứ tự Nhị phân Thập phân X2-64 Thích nghi 1 2 3 4 00100 10101 01010 11000 4 21 10 24 -48 377 36 512 952 623 964 488 Bước 4: biến hóa các đáp số để tìm các đáp số có hệ số thích nghi tối ưu. Nguyên tắc của GA đã trình bày là số nào có hệ số thi71ch nghi cao nhất sẽ có cơ hội tạo sinh và biến hóa hơn các hệ số thích nghi thấp. Chú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