giải thuật di truyền và ứng dụng

Ngày đăng: 16/05/2016, 16:54

Nội dung đồ án gồm 2 phần chính• Phần 1: Thuật giải di truyền. Phần này trình bày chi tiết về thuật giải di truyềncũng như nguyên lý và cơ chế hoạt động của nó.• Phần 2: Áp dụng vào bài toán tối ưu. Phần này trình bày cách áp dụng thuậtgiải di truyền vào giải bài toán tối ưu. Theo đó là ví dụ minh họa chi tiết cũngnhư mã nguồn của chương trình minh họa. Mục lục Mở đầu GIẢI THUẬT DI TRUYỀN (GENETIC ALGORITHM) 1.1 Lịch sử giải thuật di truyền 1.2 Tóm tắt giải thuật di truyền 1.3 Cách biểu diễn toán giải thuật di truyền 1.3.1 Biểu diễn Gen chuỗi nhị phân 1.3.2 Biểu diễn gen chuỗi số thực 1.3.3 Biểu diễn gen cấu trúc 1.4 Các phương pháp chọn (Selection) 1.4.1 Chọn lọc Roulette (Roulette Wheel Selection) 1.4.2 Chọn lọc cạnh tranh (Tournament Selection) 1.5 Các phương pháp lai tạo (crossover) đột biến (mutation) 1.5.1 Lai ghép (Crossover) 1.5.2 Đột biến (Mutation) 1.6 Các tham số cần sử dụng giải thuật di truyền 1.7 Điều kiện dừng giải thuật di truyền ÁP SỐ 2.1 2.2 2.3 3 7 8 9 10 10 DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN TỐI ƯU Minh họa chi tiết thuật toán Mã nguồn Java giải toán Màn hình kết chạy chương trình 11 11 19 25 Kết luận 26 Tài liệu tham khảo 26 Lời mở đầu Với khả nay, máy tính giúp người giải nhiều toán khó mà trước thường bó tay Mặc dù số lớn toán thú vị chưa có thuật giải hợp lý để giải chúng “Giải thuật di truyền” phát triển dựa mô trình tiến hóa sinh học, bắt đầu Nils Aall Baricelli mô trình tiến hóa trò chơi năm 1954 Sau đến Alex Fraser xuất sách Artificial Selection (chọn lọc nhân tạo) Nhưng John Holland người thực đặt tên cho giải thuật “giải thuật di truyền” việc xuất sách năm 1975 Từ giải thuật có tên “giải thuật di truyền”, với phát triển mạnh mẽ hoàn thiện lý thuyết “giải thuật di truyền” ứng dụng giải thuật toán thực tế Giải thuật di truyền ứng dụng thành công nhiều lĩnh vực kế hoạch hóa tìm đường, quan sát máy, thiết kế chế tạo máy, hệ thống điều khiển ống dẫn dầu, học máy (machine learning) nghiên cứu sâu sử dụng giải thuật di truyền toán mang tính tổng chất quát phân tích biệt số tuyến tính, mô dự báo Nội dung đồ án gồm phần • Phần 1: Thuật giải di truyền Phần trình bày chi tiết thuật giải di truyền nguyên lý chế hoạt động • Phần 2: Áp dụng vào toán tối ưu Phần trình bày cách áp dụng thuật giải di truyền vào giải toán tối ưu Theo ví dụ minh họa chi tiết mã nguồn chương trình minh họa Do thời gian gấp rút, chưa có nhiều kinh nghiệm nên báo cáo khộng thể tránh sai sót Mong thầy cô, bạn đọc góp ý để báo cáo trọn vẹn Và cuối em xin chân thành cảm ơn thầy cô giáo viện dạy em thời gian qua, đặc biệt thầy Nguyễn Quang Thuận trực tiếp dẫn tận tình giúp đỡ em hoàn thành báo cáo Hà Nội, Ngày 01 tháng 12 năm 2015 Phạm Ngọc Chuyển Chương GIẢI THUẬT DI TRUYỀN (GENETIC ALGORITHM) 1.1 Lịch sử giải thuật di truyền Trước tiên ý niệm thuật giải di truyền số nhà sinh vật học đưa từ năm 50-60, kỷ XX Alex Fraser người tiên phong nêu lên tương đồng tiến hóa sinh vật chương trình tin học giả tưởng genetic algorithm Tuy nhiên, John Henry Holland người triển khai ý tưởng phương thức giải vấn đề dựa theo tiến hóa người Từ giảng, báo mình, ông đúc kết ý tưởng vào sách đầu tay Adaptation in Natural and Artifical systems (mô theo tự nhiên hệ thống nhân tạo ), xuất năm 1975 Dựa lý thuyết GA Holland, Keneth De Jong triển khai, chứng minh thành ông thực góp phần quan trọng việc tạo tảng toán học cho lý thuyết thuật giải di truyền Sau John koza tiếp nối, phát triển giải thuật di truyền Lần Holland nghiên cứu thuật giải này, chúng hoàn toàn tên Do nguồn gốc phương pháp từ gen di truyền, Holland đặt tên cho “thuật giải di truyền“ 1.2 Tóm tắt giải thuật di truyền Thuật giải di truyền (GA) kỹ thuật chung giúp giải vấn đề toán cách mô tiến hóa người hay sinh vật nói chung (dựa thuyết tiến hóa muôn loài Darwin) điều kiện qui định sẵn môi trường GA thuật giải, nghĩa mục tiêu GA không nhằm đưa lời giải xác tối ưu mà đưa lời giải tương đối tối ưu Theo đề xuất ban đầu giáo sư John Holland, toán đặt mã hóa thành chuỗi bit với chiều dài cố định Nói cách xác thông số toán chuyển đổi biểu diễn lại dạng chuỗi nhị phân Các thông số biến hàm hệ số biểu thức toán học Người ta gọi chuỗi bit mã gen ứng với cá thể, gen có chiều dài Nói ngắn gọn, lời giải biểu diễn chuỗi bit, giống cá thể quy định gen cá thể Như vậy, thuật giải di truyền, cá thể có gen gen phục vụ cho cá thể Ban đầu, ta phát sinh số lượng lớn, giới hạn cá thể có gen ngẫu nhiên Nghĩa phát sinh tập hợp chuỗi bit ngẫu nhiên Tập cá thể gọi quần thể ban đầu (initial population) Sau đó, dựa hàm đó, ta xác định giá trị gọi độ thích nghi – Fitness Giá trị này, hiểu độ “tốt” lời giải Vì phát sinh ngẫu nhiên nên độ “tốt” lời giải hay tính thích nghi cá thể quần thể ban đầu không xác định Để cải thiện tính thích nghi quần thể, người ta tìm cách tạo quần thể Có hai thao tác thực hệ để tạo hệ khác với độ thích nghi tốt Thao tác chép nguyên mẫu nhóm cá thể tốt từ hệ trước đưa sang hệ sau (selection) Thao tác đảm bảo độ thích nghi hệ sau giữ mức độ hợp lý Các cá thể chọn thông thường cá thể có độ thích nghi cao Thao tác thứ hai tạo cá thể cách thực thao tác sinh sản số cá thể chọn từ hệ trước, thông thường cá thể có độ thích nghi cao Có hai loại thao tác sinh sản: lai tạo (crossover), hai đột biến (mutation) Trong thao tác lai tạo, từ gen hai cá thể chọn hệ trước phối hợp với (theo số quy tắc đó) để tạo thành hai gen Thao tác chọn lọc lai tạo giúp tạo hệ sau Tuy nhiên, nhiều hệ khởi tạo ban đầu có đặc tính chưa phong phú chưa phù hợp nên cá thể không rải hết không gian toán Từ đó, khó tìm lời giải tối ưu cho toán Thao tác đột biến giúp giải vấn đề Đó biến đổi ngẫu nhiên nhiều thành phần gen cá thể hệ trước tạo cá thể hoàn toàn thệ sau Nhưng thao tác phép xảy với tần suất thấp (thường 0.01), thao tác gây xáo trộn làm cá thể chọn lọc lai tạo có tính thích nghi cao, dẫn đến thuật toán không hiệu Thế hệ tạo lại xử lý hệ trước (xác định độ thích nghi tạo hệ mới) có cá thể đạt giải pháp mong muốn đạt đến thời gian giới hạn Tóm lại: Một thuật giải di truyền (hay chương trình tiến hóa bất kỳ) giải toán cụ thể phải gồm năm thành phần sau đây: – Một cấu trúc liệu I biểu diễn không gian lời giải toán, – Phương pháp khởi tạo quần thể ban đầu P(0), – Hàm định nghĩa độ thích nghi eval(.) đóng vai trò môi trường, – Các phép toán di truyền, – Các tham số khác (kích thước quần thể, xác suất lai tạo, xác suất đột biến ) Lược đồ GA: 1.3 Cách biểu diễn toán giải thuật di truyền Để áp dụng giải toán giải thuật di truyền, thao tác quan trọng – phải biết chọn cấu trúc liệu phù hợp Để giải toán giải thuật di truyền, ta thường chọn sử dụng loại cấu trúc liệu sau: Chuỗi nhị phân, chuỗi số thực cấu trúc Trong chuỗi nhị phân chuỗi số thực thường sử dụng nhiều 1.3.1 Biểu diễn Gen chuỗi nhị phân Giả sử ta muốn biểu diễn số thực x nằm khoảng [min, max] chuỗi nhị phân A dài L bit Lúc đó, ta chia miền [min, max] thành 2L − vùng, kích thước vùng : max −min g= 2L − Người ta gọi g độ xác số thực biểu diễn cách (vì g quy định giá trị thập phân nhỏ số thực mà chuỗi nhị phân dài L bit biểu diễn được) Giá trị số thực x biểu diễn qua chuỗi nhị phân tính sau: x = + Decimal(A) ∗ g, Decimal(A) hàm để tính giá trị thập phân nguyên dương chuỗi nhị phân A Hàm tính theo công thức sau: Decimal(A) = aL−1 2L−1 + + a2 22 + a1 21 + a0 20, với bit thứ i chuỗi nhị phân tính từ phải sang trái (bit phải bit 0) Ví dụ: Tìm giá trị lớn hàm f (x) = x.sin(10πx) + với x ∈ [−1, 2] Sử dụng vectơ bit làm nhiễm sắc thể để biểu diễn giá trị thực biến x Chiều dài vectơ phụ thuộc vào độ xác cần có, ví dụ này, ta tính xác đến số lẻ Miền giá trị x có chiều dài – (-1) = 3; với yêu cầu độ xác số lẻ phải chia khoảng [−1, 2] thành 3.106 khoảng có kích thước Điều có nghĩa cần có 22 bit cho vevtơ nhị phân (nhiễm sắc thể) 2097152 = 221 < 3000000 < 222 = 4194304 Ánh xạ chuỗi nhị phân (b21 b20 b0 ) từ số sang số 10: 21 bi 2i )2 = x (b21 b20 b0 )2 = ( i=0 Tìm số thực x tương ứng x = −1 + x 222 −1 với -1 lân cận miền giá trị chiều dài miền Ví dụ, nhiễm sắc thể (1000101110110101000111) biểu diễn số 0.637197 x’ = (1000101110110101000111)2 = 228896710 x = −1.0 + 2288967 = 0.637197 4194303 1.3.2 Biểu diễn gen chuỗi số thực Đối với vấn đề toán có nhiều tham số, việc biểu diễn gen chuỗi số nhị phân đôi lúc làm cho kiểu gen cá thể trở nên phức tạp, dẫn đến việc thi hành thao tác gen trở nên hiệu Khi đó, người ta chọn biểu diễn kiểu gen dạng chuỗi số thực Tuy nhiên, chọn biểu diễn kiểu gen chuỗi số thực cần lưu ý quy tắc đảm bảo tiết kiệm không gian thành phần gen Quy tắc lưu ý phải tiết kiệm mặt không gian nhớ thành phần gen Giả sử nghiệm toán cấu thành từ thành phần, thành phần X thực có giá trị khoảng [1.0, 2.0], thành phần Y nguyên khoảng [0, 15] thành phần Z khoảng [5, 8], không nên chọn biểu diễn kiểu gen chuỗi thành phần số thực Vì biết, số thực phải biểu diễn byte, với số thực, ta tốn hết 12 byte Như với trường hợp cụ thể này, ta nên chọn biểu diễn chuỗi nhị phân, dùng khoảng 10 bit cho thành phần X (độ xác khoảng 0.001), bit cho thành phần Y bit cho thành phần Z, tổng cộng chiếm có 16 bit = byte Chúng ta tiết kiệm nhiều nhớ! 1.3.3 Biểu diễn gen cấu trúc Cấu trúc thường dùng trường hợp thân cấu trúc liệu toán có dạng Đây trường hợp phức tạp nên sử dụng Trong phạm vi đồ án này, em không khảo sát nhiều kiểu liệu Các thao tác thuật giải di truyền thường phụ thuộc nhiều vào toán xét Do đó, ta không trình bày cách tổng quát Một loại thường sử dụng thuật giải di truyền dạng hai nhánh (ở ta dùng chữ hai nhánh để phân biệt với loại nhị phân – thường dùng xếp tìm kiếm) Để hiểu cấu trúc cây, bạn cần có kiến thức trỏ Bạn tìm thấy thông tin tài liệu cấu trúc liệu 1.4 Các phương pháp chọn (Selection) Chọn lọc cá thể thông qua kết quả, hay mục đích vấn đề dựa mức độ thích nghi cá thể Vì vậy, cần đánh giá độ thích nghi cá thể để tìm cá thể tốt Thông thường, đặt vấn đề nhỏ tương ứng với giá trị điểm thích nghi, kết đánh giá gồm tổng số điểm Cá thể tốt có điểm thấp lớn Theo thuyết Darwin, cá thể tốt tồn tạo cá thể Có nhiều phương pháp để chọn nhiễm sắc thể tốt Sau vài phương pháp số 1.4.1 Chọn lọc Roulette (Roulette Wheel Selection) Các cá thể chọn theo độ thích nghi chúng Nhiễm sắc thể tốt có hội cao để tham dự vào hệ Thuật giải chọn lọc roulette(Davis, [1991,8]) sau: − Tính độ thích nghi eval(vi ) nhiễm sắc thể vi (i = popsize); − Tính tổng độ thích nghi thành viên quần thể: popsize F = eval(vi ); i=1 − Tính xác suất chọn pi cho nhiễm sắc thể vi : pi = eval(vi ) ; F − Tìm vị trí xác suất qi nhiễm sắc thể vi : i qi = pj j=1 Tiến trình chọn lọc thực cách quay bánh xe ru-lét pop-size lần; lần chọn nhiễm sắc thể từ quần thể hành vào quần thể theo cách sau: − Phát sinh ngẫu nhiên số r khoảng [0; 1]; − Nếu r < qi chọn nhiễm sắc thể đầu tiên; ngược lại chọn nhiễm sắc thể thứ i(2 ≤ i ≤pop-size) cho qi−1 < r ≤ qi Hiển nhiên, có số nhiễm sắc thể chọn nhiều lần Các nhiễm sắc thể tốt có nhiều hơn, nhiễm sắc thể trung bình không thay đổi, nhiễm sắc thể chết 1.4.2 Chọn lọc cạnh tranh (Tournament Selection) Có nhiều cách chọn lọc cạnh tranh, sau cách chọn phổ biến − Chọn lọc cạnh tranh (2-Tournament Selection): Hai nhiễm sắc thể khác chọn ngẫu nhiên so sánh với nhiễm sắc thể tồn Nếu nhiễm sắc thể v1 không tốt nhiễm sắc thể v2 nghĩa : f (v1 ) ≤ f (v2 ), nhiễm sắc thể v1 chết bị loại khỏi quần thể Quá trình lặp lại đến hết N nhiễm sắc thể lại − Chọn lọc cạnh tranh (3-Tournament Selection): Ba nhiễm sắc thể khác chọn ngẫu nhiên so sánh với nhiễm sắc thể tồn Nếu có: f (v1 ) ≤ f (v2 ) f (v1 ) ≤ f (v3 ), nhiễm sắc thể v1 chết bị loại khỏi quần thể Quá trình lặp lại đến hết N nhiễm sắc thể lại 1.5 Các phương pháp lai tạo (crossover) đột biến (mutation) Lai ghép đột biến hai phép thực giải thuật di truyền nhiều vấn đề Có nhiều phuơng pháp lai ghép đột biến Ở miêu tả số thường dùng 1.5.1 Lai ghép (Crossover) Lai ghép vị trí (Single point crossover) Từ hai nhiễm sắc thể cha mẹ ban đầu ta cắt vị trí sau ghép lại với thành nhiễm sắc thể Lai ghép hai vị trí (Two point crossover) Từ hai nhiễm sắc thể cha mẹ ban đầu ta cắt hai vị trí sau ghép chúng với thành nhiễm sắc thể 1.5.2 Đột biến (Mutation) Chọn số bit sau thay đổi giá trị bít đó, tạo nhiễm sắc thể 1.6 Các tham số cần sử dụng giải thuật di truyền Kích thước quần thể: Pop-size, số cá thể trì qua hệ tiến hóa thuật giải di truyền Xác suất lai ghép: Pc xác suất cá thể chọn cho phép lai ghép Xác suất cho ta số nhiễm sắc thể pop-size∗Pc mong đợi dùng tác vụ lai tạo Ta tiến hành theo cách sau đây: Đối với nhiễm sắc thể quần thể mới: − Phát sinh ngẫu nhiên số r khoảng [0;1] − Nếu r < Pc chọn nhiễm sắc thể để lai tạo Bây giờ, ta ghép đôi nhiễm sắc thể chọn cách ngẫu nhiên: cặp nhiễm sắc thể ghép đôi, ta phát sinh ngẫu nhiên số nguyên pos khoảng [1; m] (m tổng chiều dài - số bit nhiễm sắc thể) Số pos cho biết vị trí điểm lai Một tham số khác Pm cho ta số bit đột biến Pm ∗ m∗pop-size mong đợi Mỗi bit (trong tất nhiễm sắc thể quần thể) có hội bị đột biến Vì ta tiến hành theo cách sau: Đối với nhiễm sắc thể quần thể hành (sau lai) với bit nhiễm sắc thể: − Phát sinh ngẫu nhiên số r khoảng [0;1] − Nếu r < Pm đột biến bit 1.7 Điều kiện dừng giải thuật di truyền Sau trình tiến hóa quần thể, dựa vào toán mà có cách kết thúc vấn đề khác nhau, đạt đến mức yêu cầu Một vài trường hợp thông thường sau: − Dừng theo kết quả: Một đạt đến mức giá trị yêu cầu chấm dứt trình thực − Dừng dựa vào số hệ: Chọn số hệ, trình dừng số hệ quy định trước, không cần biết kết − Tính theo thời gian: Không cần biết hệ hay kết nào, dựa vào số quy định mà kết thúc − Tổ hợp: Dùng nhiều phương án khác cho vấn đề 10 Một nhiễm sắc thể tương ứng số nguyên N số khoảng tính từ nhiễm sắc thể 000 000 đến Nên giá trị mà nhiễm sắc thể biểu diễn x0 = N 198 − 99 −1 230 Như nhiễm sắc thể 011011001100000100000000010110 có giá trị nguyên (cơ số 10) 456146966, suy tương ứng với giá trị thực -14.8856 Độ thích nghi nhiễm sắc thể f (−14.8856) = 9778.4175 Để cực đai hóa hàm f thuật toán di truyền, ta tạo quần thể có pop-size = 20 nhiễm sắc thể Cả 30 bit tất nhiễm sắc thể tạo ngẫu nhiên Giả sử sau trình khởi tạo ta có quần thể sau v0 = 011011001100000100000000010110 v1 = 110011000010111110010001000001 v2 = 001000001100101100110111111010 v3 = 110011000101100111100110111101 v4 = 011100001000011110000100010101 v5 = 111101001101111101110001111011 v6 = 110100000000011110010111110110 v7 = 100011011011100000110111001101 v8 = 000010100000100100011111000100 v9 = 010001000100000101000011000000 v10 = 011100101011010010011101010110 v11 = 001111110111110111101111010010 v12 = 111110100001001000010011111111 v13 = 100010001101000100011010001000 v14 = 001101110001110011110110000011 v15 = 011110100110001010011100101011 v16 = 000110011010110001000001001110 v17 = 101001000100001100010101110101 v18 = 001001100110111001111001100011 v19 = 101101001110000001101110010010 12 Ta tính giá trị thực mà chúng biểu diễn độ thích nghi chúng sau: eval(v0 ) = g(−14.8856) = 9778.41752 eval(v1 ) = g(58.9249) = 6527.84910 eval(v2 ) = g(−73.6360) = 4577.73531 eval(v3 ) = g(59.0528) = 6512.75899 eval(v4 ) = g(−11.9655) = 9856.82511 eval(v5 ) = g(90.3938) = 1828.95527 eval(v6 ) = g(61.8979) = 6168.64491 eval(v7 ) = g(10.6112) = 9887.40143 eval(v8 ) = g(−91.2380) = 1675.61508 eval(v9 ) = g(−46.2090) = 7864.72105 eval(v10 ) = g(−10.2824) = 9894.27132 eval(v11 ) = g(−49.8929) = 7510.69269 eval(v12 ) = g(94.4139) = 1085.997858 eval(v13 ) = g(6.8192) = 9953.497861 eval(v14 ) = g(−56.3734) = 6822.03538 eval(v15 ) = g(−4.3426) = 9981.14100 eval(v16 ) = g(−79.1436) = 3736.28433 eval(v17 ) = g(28.0464) = 9213.39771 eval(v18 ) = g(−69.2756) = 5200.89067 eval(v19 ) = g(40.8968) = 8327.45097 Bây ta xây dựng hệ thống kiến trúc bánh xe ru-let cho tiến trình chọn lọc Tổng độ thích nghi quần thể 19 eval(vi ) = 136404.5836 i=0 Xác suất chọn lọc pi nhiễm sắc thể vi p0 = eval(v0 )/F = 0.0716868 p1 = eval(v1 )/F = 0.0478565 p2 = eval(v2 )/F = 0.0335599 13 p3 = eval(v3 )/F = 0.0477458 p4 = eval(v4 )/F = 0.0722616 p5 = eval(v5 )/F = 0.0134083 p6 = eval(v6 )/F = 0.0452231 p7 = eval(v7 )/F = 0.0724858 p8 = eval(v8 )/F = 0.0122841 p9 = eval(v9 )/F = 0.0576573 p10 = eval(v10 )/F = 0.07253620 p11 = eval(v11 )/F = 0.05506187 p12 = eval(v12 )/F = 0.00796159 p13 = eval(v13 )/F = 0.07297040 p14 = eval(v14 )/F = 0.05001324 p15 = eval(v15 )/F = 0.07317306 p16 = eval(v16 )/F = 0.02739119 p17 = eval(v17 )/F = 0.06754463 p18 = eval(v18 )/F = 0.03812841 p19 = eval(v19 )/F = 0.06104964 Các vị trí xác suất qi nhiễm sắc thể vi q0 = 0.0716 q1 = 0.1195 q2 = 0.1531 q3 = 0.2008 q4 = 0.2731 q5 = 0.2865 q6 = 0.3317 q7 = 0.4042 q8 = 0.4165 q9 = 0.4741 q10 = 0.5467 q11 = 0.6017 q12 = 0.6097 q13 = 0.6826 q14 q15 q16 q17 q18 q19 = 0.7327 = 0.8058 = 0.8332 = 0.9008 = 0.9389 = 0.9999 Bây ta quay bánh xe Roulette 20 lần, lần chọn nhiễm sắc thể cho quần thể Giả sử thứ tự ngẫu nhiên 20 số phát sinh khoảng [0, 1] 14 0.8900 0.5050 0.3135 0.4253 0.0887 0.1631 0.7023 0.7976 0.8177 0.7652 0.6986 0.8122 0.7277 0.3092 0.6800 0.0966 0.1002 0.9801 0.0218 0.1072 Số r r = 0.8900 lớn q16 nhỏ q17 nghĩa nhiễm sắc thể v17 chọn vào quần thể mới; số thứ hai 0.1631 lớn q2 nhỏ q3 nghĩa nhiễm sắc thể v3 chọn,vv Như quần thể gồm nhiễm sắc thể sau: v0 = 101001000100001100010101110101(v17 ) v1 = 110011000101100111100110111101(v3 ) v2 = 001101110001110011110110000011(v14 ) v3 = 110011000010111110010001000001(v1 ) v4 = 011100101011010010011101010110(v10 ) v5 = 001101110001110011110110000011(v14 ) v6 = 000110011010110001000001001110(v16 ) v7 = 110011000010111110010001000001(v1 ) v8 = 110100000000011110010111110110(v6 ) v9 = 011110100110001010011100101011(v15 ) v10 = 001101110001110011110110000011(v14 ) v11 = 101101001110000001101110010010(v19 ) v12 = 010001000100000101000011000000(v9 ) v13 = 000110011010110001000001001110(v16 ) v14 = 110100000000011110010111110110(v6 ) v15 = 011011001100000100000000010110(v0 ) v16 = 110011000010111110010001000001(v1 ) v17 = 011110100110001010011100101011(v15 ) v18 = 100010001101000100011010001000(v13 ) v19 = 110011000010111110010001000001(v1 ) Bây ta áp dụng phép toán lai ghép cho cá thể quần thể (các vectơ vi ) Xác suất lai ghép Pc = 0.25 ta hy vọng trung bình 25% nhiễm sắc thể tham gia lai tạo Ta tiến hành theo cách sau: với nhiễm sắc thể quần thể ta phát sinh ngẫu nhiên số r khoảng [0, 1]; r < 0.25, ta chọn nhiễm sắc thể cho trước để lai tạo Giả sử thứ tự số ngẫu nhiên là: 15 0.3704 0.4278 0.8973 0.3560 0.7709 0.8631 0.6023 0.1641 0.9907 0.4452 0.0608 0.8143 0.3077 0.2892 0.6660 0.6116 0.2981 0.1289 0.3345 0.1792 Điều có nghĩa nhiễm sắc thể v2, v11, v9 v19 đem vào để lai ghép Ở số nhiễm sắc thể đem vào lai ghép chẵn, chúng lẻ ta loại bớt thêm vào nhiễm sắc thể Việc thêm vào loại bớt nhiễm sắc thể nên thực ngẫu nhiên tốt Bây ta cho cặp nhiễm sắc thể phối cách ngẫu nhiên, giả sử cặp nhiễm sắc thể phối với cặp (v11, v19 ) (v 2, v9 ) Cặp nhiễm sắc thể thứ v11 = 101101001110000001101110010010 v19 = 110011000010111110010001000001 Ta phát sinh số ngẫu nhiên pos thuộc khoảng [1; 30], 30 tổng chiều dài (số bit) nhiễm sắc thể Số pos cho biết vị trí điểm lai tạo Giả sử pos = 11, nhiễm sắc thể bị cắt sau bit thứ 11 thay cặp chúng: v”11 = 101101001110001010011100101011 v”19 = 011110100110000001101110010010 Cặp nhiễm sắc thể thứ hai v2 = 001101110001110011110110000011 v9 = 011110100110001010011100101011 số phát sinh pos = Các nhiễm sắc thể thay cặp chúng: v”2 = 001110100110001010011100101011 v”9 = 011101110001110011110110000011 Cuối quần thể hành là: v0 = 101001000100001100010101110101 v1 = 110011000101100111100110111101 v2 = 001110100110001010011100101011 v3 = 110011000010111110010001000001 v4 = 011100101011010010011101010110 16 v5 = 001101110001110011110110000011 v6 = 000110011010110001000001001110 v7 = 110011000010111110010001000001 v8 = 110100000000011110010111110110 v9 = 011101110001110011110110000011 v10 = 001101110001110011110110000011 v11 = 101101001110001010011100101011 v12 = 010001000100000101000011000000 v13 = 000110011010110001000001001110 v14 = 110100000000011110010111110110 v15 = 011011001100000100000000010110 v16 = 110011000010111110010001000001 v17 = 011110100110001010011100101011 v18 = 100010001101000100011010001000 v19 = 011110100110000001101110010010 Phép toán kế tiếp, đột biến thực sở bit Xác suất đột biến Pm = 0.01, ta hy vọng trung bình 1/100 số bit qua đột biến Có 600 bit(mxpop − size = 30x20) toàn quần thể, ta hy vọng trung bình bit đột biến hệ Mỗi bit có hội đột biến ngang bit quần thể, ta phát sinh ngẫu nhiên số r khoảng [0, 1], r < 0.01, ta đột biến bit Điều có nghĩa ta phải phát sinh 660 số ngẫu nhiên Giả sử có số nhỏ 0.01; vị trí bít số ngấu nhiên sau: Vị trí bit Số ngẫu nhiên 47 0.0082 339 0.0066 563 0.0072 Từ ta suy vị trí nhiễm sắc thể bit tương ứng Vị trí bit Số thứ tự nhiễm sắc thể 47 339 12 563 19 17 Số thứ tự bit nhiễm sắc thể 17 10 23 Điều có nghĩa nhiễm sắc thể bị ảnh hưởng phép đột biến Quần thể cuối ùng liệt kê dưới; bit đột biến tô đậm gạch dưới: v0 = 101001000100001100010101110101 v1 = 110011000101100101100110111101 v2 = 001110100110001010011100101011 v3 = 110011000010111110010001000001 v4 = 011100101011010010011101010110 v5 = 001101110001110011110110000011 v6 = 000110011010110001000001001110 v7 = 110011000010111110010001000001 v8 = 110100000000011110010111110110 v9 = 011101110001110011110110000011 v10 = 001101110001110011110110000011 v11 = 101101001010001010011100101011 v12 = 010001000100000101000011000000 v13 = 000110011010110001000001001110 v14 = 110100000000011110010111110110 v15 = 011011001100000100000000010110 v16 = 110011000010111110010001000001 v17 = 011110100110001010011100101011 v18 = 100010001101000100011000001000 v19 = 011110100110000001101110010010 Ta vừa hoàn thành bước lặp (nghĩa hệ) thủ tục di truyền Ta xam xét chút kết tiến trình tiến hóa quần thể Trong thời kì tiến hóa, ta giải mã nhiễm sắc thể tính giá trị hàm thích nghi từ giá trị vừa giải mã Ta được: eval(v0 ) = g(28.0464) = 9213.39771 eval(v1 ) = g(59.0513) = 6512.937407 eval(v2 ) = g(−53.84269) = 7100.96425 eval(v3 ) = g(58.9249) = 6527.84910 18 eval(v4 ) = g(−10.2824) = 9894.27132 eval(v5 ) = g(−56.3734) = 6822.03538 eval(v6 ) = g(−79.1436) = 3736.28433 eval(v7 ) = g(58.9249) = 6527.84910 eval(v8 ) = g(61.8979) = 6168.64491 eval(v9 ) = g(−6.8734) = 9952.75583 eval(v10 ) = g(−56.3734) = 6822.03538 eval(v11 ) = g(40.7100) = 8342.69263 eval(v12 ) = g(−46.2090) = 7864.72105 eval(v13 ) = g(−79.1436) = 3736.28433 eval(v14 ) = g(61.8979) = 6168.64491 eval(v15 ) = g(−14.8856) = 9778.41752 eval(v16 ) = g(58.9249) = 6527.84910 eval(v17 ) = g(−4.3426) = 9981.14100 eval(v18 ) = g(6.8192) = 9953.49818 eval(v19 ) = g(−4.3492) = 9981.08372 Chú ý quần thể có độ thích nghi F = 151612.86754 cao tổng độ thích nghi quần thể cũ Tiến trình lặp lại lần phép toán di truyền áp dụng, lượng giá hệ v.v Không khó để theo dõi cá thể tốt tiến trình tiến hóa Thông thường cài đặt thuật giải di truyền, cá thể tốt lưu trữ vị trí riêng biệt; cách đó, thuật giải trì cá thể tốt tìm suốt trình Ta cho điều kiện dừng số bước lặp đủ lớn (1 triệu lần lặp) Cá thể tốt sau chọn làm giải pháp tối ưu cho toán 2.2 Mã nguồn Java giải toán Bài toán lập trình theo hướng đối tượng, với đối tượng cá thể (class Solution.java) Mỗi cá thể có thuộc tính chiều dài nhiễm sắc thể (SIZE), mảng bit nhị phân, giá trị nhỏ lớn cá thể, cuối làm hàm thích nghi mõi cá thể Sau class chạy có thuộc tính kích thước quần thể (pop-size), xác suất lai ghép, xác suất đột biến cá thể để lưu trữ cá thể tốt Sau class Solution.java 19 package ga.chuyenbka; import static java.lang.Math.pow; import java.util.Random; public class Solution implements Comparable { //độ dài cá thể (tính bit) public static final int SIZE = 30; //kiểu mã hóa (nhị phân) public boolean[] genotype; //can duoi, can tren private final double a = -99; private final double b = 99; //khởi tạo cá thể public Solution() { genotype = new boolean[SIZE]; } //cách chọn giá trị ngẫu nhiên cho cá thể void random() { Random rand = new Random(); for (int i = 0; i < genotype.length; i++) { genotype[i] = 0.5 > rand.nextFloat(); } } //chuyển thành dạng chuỗi private String gene() { StringBuilder sb = new StringBuilder(); for (int i = 0; i < genotype.length; i++) { sb.append(genotype[i] == true ? : 0); } return sb.toString(); } //dot bien public Solution mut(int n) { //dot bien o bit thu n genotype[n] = !genotype[n]; return this; } //hàm thích nghi double fitness() { Long decimalValue; decimalValue = Long.parseLong(this.gene(), 2); //gia tri thuc cua ca the double doubleValue = a + (decimalValue * (b - a)) / (pow(2, SIZE) - 1); return f(doubleValue); } //ham muc tieu 20 double f(double x) { return pow(10, 9) - x * x; //return pow(x,4) - 3*x + 8; } //so sanh ca the de tien sap xep public int compareTo(Solution o) { double f1 = this.fitness(); double f2 = o.fitness(); if (f1 < f2) { return 1; } else if (f1 > f2) { return -1; } else { return 0; } } //hien thi ca the dang chuoi @Override public String toString() { Long decimalValue = Long.parseLong(this.gene(), 2); double doubleValue = a + (decimalValue * (b – a)) / (pow(2, SIZE) – 1); return “gene=” + gene() + ” decimal = ” + doubleValue + ” fit=” + fitness(); } } class chạy (ga-chuyenbka.java) /* *Bai toan tim gia tri on nhat cua ham so voi x khoang nao */ package ga.chuyenbka; import import import import static java.lang.Math.pow; java.util.Collections; java.util.LinkedList; java.util.Random; /** * * @author CHUYENBKA */ public final class GaChuyenbka { final Random rand = new Random(); //so luong ca the quan the final static int populationSize = 20; //do dai ca the final static int solutionSize = Solution.SIZE; //ti le ca the duoc chon de lai 21 final static double parentUsePercent = 0.25; //ti le bit dot bien final private static double mutRate = 0.01; static Solution bestSolution; //khoi tao quan the LinkedList population = new LinkedList(); public GaChuyenbka() { bestSolution = new Solution(); bestSolution.random(); for (int i = 0; i < populationSize; i++) { Solution c = new Solution(); c.random(); population.add(c); } System.out.println("Khoi tao quan the ban dau"); print(); } void print() { System.out.println(" print"); int i = 0; for (Solution c : population) { System.out.println(i + ": " + c); i++; } } //lai ghep cheo Solution newChild(Solution c1, Solution c2, int pivot) { Solution child = new Solution(); for (int i = 0; i < pivot; i++) { child.genotype[i] = c1.genotype[i]; } for (int j = pivot; j < Solution.SIZE; j++) { child.genotype[j] = c2.genotype[j]; } return child; } //tao quan the tiep theo void produceNextGen() { LinkedList newPopulation = new LinkedList(); //tinh tong thich nghi double sum = 0; for (int i = 0; i < population.size(); i++) { sum += population.get(i).fitness(); } //do thich nghi cua tung ca the Double[] p = new Double[population.size()]; 22 //tim ca the co thich nghi tot nhat de giu lai so sanh double best = population.get(0).fitness(); int index = 0; //thu tu cua phan tu tot nhat for (int i = 0; i < population.size(); i++) { p[i] = population.get(i).fitness() / sum; if (best < population.get(i).fitness()) { best = population.get(i).fitness(); index = i; } } if (bestSolution.fitness() < population.get(index).fitness()) { bestSolution = population.get(index); System.out.println(bestSolution); } //banh xe ru-let Double[] q = new Double[populationSize]; for (int i = 0; i < populationSize; i++) { q[i] = 0d; } for (int i = 0; i < populationSize; i++) { for (int j = 0; j q[j - 1]) { newPopulation.add(population.get(j)); break; } } } } //chon cac ca the the lai ghep LinkedList crossover = new LinkedList(); for (int i = 0; i < populationSize; i++) { r[i] = rand.nextDouble(); if (r[i] < parentUsePercent) { crossover.add(newPopulation.get(i)); } } 23 //qua trinh lai ghep if (crossover.size() > 0) { int n = ((crossover.size() % 2) == 0) ? crossover.size() : crossover.size() – 1; for (int i = 0; i < n; i = i + 2) { //diem ghep cheo int pivot = rand.nextInt(Solution.SIZE); Solution child1 = newChild(crossover.get(i), crossover.get(i + 1), pivot); Solution child2 = newChild(crossover.get(i + 1), crossover.get(i), pivot); //chen ca the moi vao quan the moi newPopulation.add(child1); newPopulation.add(child2); //xoa ca the cu newPopulation.remove(crossover.get(i)); newPopulation.remove(crossover.get(i + 1)); } } //dot bien gen (bit) int genSize = populationSize * solutionSize; Double[] mut = new Double[genSize]; for (int i = 0; i < genSize; i++) { mut[i] = rand.nextDouble(); if (mut[i] < mutRate) { int k = i / solutionSize; int n = i - k * solutionSize; newPopulation.get(k).mut(n); } } population = newPopulation; } public static void main(String[] args) { GaChuyenbka ga = new GaChuyenbka(); ga.run(); } void run() { final int maxSteps = 1000000; int count = 0; while (count < maxSteps) { count++; produceNextGen(); } System.out.println("\nResult"); System.out.println(bestSolution); } } 24 2.3 Màn hình kết chạy chương trình Màn hình sau khởi tạo quần thể ban đầu (ngẫu nhiên) Màn hình sau chạy bước lặp, cá thể tốt cập nhật dần 25 Dễ thấy cá thể tốt sau có giá trị 1, 44755.10−5 = 0.0000144, so sánh với giá trị (x = 0) giá trị chấp nhận Kết luận Về đồ án sở lý thuyết, nguyên lý chung giải thuật di truyền Trên sở sâu vào phân tích bốn trình giải thuật di truyền: lai ghép, đột biến, sinh sản chọn lọc tự nhiên Ứng dụng thực tế đồ án bước vận dụng kiến thức giải thuật di truyền vào giải toán thực tế máy tính Nội dung phần giới thiệu bước triển khai giải thuật di truyền vào toán tối ưu ví dụ minh họa chi tiết toán tối ưu đơn giản Tài liệu tham khảo Nguyễn Đình Thúc, Lập trình tiến hóa, Nhà xuất Giáo dục, Hà Nôi 2000 Darrell Whitley, "A Genetic Algorithm Tutorial", Computer Science Department, Colorado State University Fort Collins, CO 80523 bem2vnn@gmail.com 26 [...]... chung của giải thuật di truyền Trên cơ sở đó đã đi sâu vào phân tích bốn quá trình cơ bản của giải thuật di truyền : lai ghép, đột biến, sinh sản và chọn lọc tự nhiên Ứng dụng thực tế trong đồ án là bước vận dụng những kiến thức của giải thuật di truyền vào giải quyết các bài toán thực tế trên máy tính Nội dung của phần này giới thiệu các bước triển khai giải thuật di truyền vào bài toán tối ưu và ví dụ...Chương 2 ÁP DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN TỐI ƯU SỐ Chương này trình bày ví dụ minh họa thuật toán di truyền giải bài toán tối ưu Ta sẽ bắt đầu thảo luận một vài ý kiến chung trước khi đi vào chi tiết ví dụ Không mất tính tổng quát, ta giả sử những bài toán tối ưu là bài toán tìm giá trị lớn nhất... cao hơn tổng độ thích nghi của quần thể cũ Tiến trình lặp lại lần nữa và các phép toán di truyền được áp dụng, lượng giá thế hệ kế tiếp v.v Không khó để theo dõi cá thể tốt nhất trong tiến trình tiến hóa Thông thường trong các cài đặt thuật giải di truyền, cá thể tốt nhất được lưu trữ ở một vị trí riêng biệt; bằng cách đó, thuật giải có thể duy trì cá thể tốt nhất tìm được trong suốt quá trình Ta sẽ... thể v2, v11, v9 và v19 sẽ được đem vào để lai ghép Ở đây số nhiễm sắc thể được đem vào lai ghép là chẵn, nếu chúng là lẻ thì ta có thể loại bớt hoặc thêm vào 1 nhiễm sắc thể ngoài Việc thêm vào hoặc loại bớt 1 nhiễm sắc thể nên thực hiện ngẫu nhiên thì tốt hơn Bây giờ ta cho các cặp nhiễm sắc thể phối một cách ngẫu nhiên, giả sử 2 cặp nhiễm sắc thể phối với nhau là cặp (v11, v19 ) và (v 2, v9 ) Cặp... 100010001101000100011000001000 v19 = 011110100110000001101110010010 Ta vừa hoàn thành một bước lặp (nghĩa là một thế hệ) của thủ tục di truyền Ta xam xét một chút các kết quả của tiến trình tiến hóa quần thể mới Trong thời kì tiến hóa, ta giải mã từng nhiễm sắc thể và tính các giá trị của hàm thích nghi từ giá trị vừa giải mã Ta được: eval(v0 ) = g(28.0464) = 9213.39771 eval(v1 ) = g(59.0513) = 6512.937407 eval(v2 ) = g(−53.84269)... trí bít và số ngấu nhiên như sau: Vị trí bit Số ngẫu nhiên 47 0.0082 339 0.0066 563 0.0072 Từ đó ta suy ra vị trí của nhiễm sắc thể và bit tương ứng là Vị trí bit Số thứ tự của nhiễm sắc thể 47 2 339 12 563 19 17 Số thứ tự của bit trong nhiễm sắc thể 17 10 23 Điều này có nghĩa là 3 nhiễm sắc thể bị ảnh hưởng của phép đột biến Quần thể cuối ùng được liệt kê ở dưới; các bit đột biến được tô đậm và gạch... lần lặp) Cá thể tốt nhất sau cùng sẽ được chọn làm giải pháp tối ưu cho bài toán 2.2 Mã nguồn Java giải bài toán Bài toán được lập trình theo hướng đối tượng, với đối tượng ở đây là các cá thể (class Solution.java) Mỗi cá thể có các thuộc tính là chiều dài nhiễm sắc thể (SIZE), 1 mảng các bit nhị phân, giá trị nhỏ nhất và lớn nhất của các cá thể, và cuối cùng làm hàm thích nghi của mõi cá thể Sau đó... = N 198 − 99 −1 230 Như vậy nhiễm sắc thể 011011001100000100000000010110 có giá trị nguyên (cơ số 10) là 456146966, suy ra nó tương ứng với giá trị thực là -14.8856 Độ thích nghi của nhiễm sắc thể này là f (−14.8856) = 9778.4175 Để cực đai hóa hàm f bằng thuật toán di truyền, ta tạo 1 quần thể có pop-size = 20 nhiễm sắc thể Cả 30 bit trong tất cả các nhiễm sắc thể đều được tạo ngẫu nhiên Giả sử sau... tuyệt đối), ở đây ta chọn g(x) = 10000 − x2, khi đó f (x) và g(x) có cùng nghiệm tối ưu Độ dài miền xác định của biến x ở đây là 198, được chia thành 230 − 1 khoảng, nên mỗi khoảng có giá trị là 198 30 2 −1 11 Một nhiễm sắc thể tương ứng một số nguyên N chính là số khoảng tính từ nhiễm sắc thể 000 000 đến nó Nên giá trị mà nhiễm sắc thể đó biểu di n là x0 = N 198 − 99 −1 230 Như vậy nhiễm sắc thể 011011001100000100000000010110... 0.7976 0.8177 0.7652 0.6986 0.8122 0.7277 0.3092 0.6800 0.0966 0.1002 0.9801 0.0218 0.1072 Số r đầu tiên r = 0.8900 lớn hơn q16 nhỏ hơn q17 nghĩa là nhiễm sắc thể v17 được chọn vào quần thể mới; số thứ hai 0.1631 lớn hơn q2 và nhỏ hơn q3 nghĩa là nhiễm sắc thể v3 được chọn,vv Như vậy quần thể mới gồm những nhiễm sắc thể sau: v0 = 101001000100001100010101110101(v17 ) v1 = 110011000101100111100110111101(v3

Xem thêm  App Chụp Hình Có 3 Chú Gấu Trên Mặt Cực Dễ Thương, App Chụp Hình Có 3 Con Gấu Trên Mặt

Source: https://bem2.vn
Category: Ứng dụng hay

Rate this post

Bài viết liên quan

Để lại ý kiến của bạn:

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *