Tham khảo tài liệu 'tri tuệ nhân tạo part 3', kỹ thuật - công nghệ, tự động hoá phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Phủti l. GIẢI QUYẾT VẮN ĐỂ BANG TÌM KIÊM 61 Từ các cá thê dược chọn đế lai ghép người ta cặp đôi chúng một cách ngẫu nhiên. Trong trường hợp các nhiễm sắc the là các chuỗi nhị phân có độ dài cô định m ta có thê thực hiện lai ghép như sau VỚI mỗi cặp. sinh ra một sô nguyên ngẫu nhiên p trên doạn 0. m -1 p là vị trí điểm ghép. Cặp gồm hai nhiễm sắc thể a ctl. a l aJ T . ctm a bị. 6 1 1. èm dược thay bơi hai con là a a . cq bm b blK CỈ 1H. ữm 3. Đót biên Ta thực hiện toán tử dột biến trên các cá thể có được sau quá trình lai ghép. Đột biên là thay dồi trạng tháj một sô gien nào dó trong nhiễm sac thè. Mỗi gien chịu đột biến với xác suất pm. Xác suất đột biến pm do ta xác dịnh và là xác suất thấp. Sau đây là toán tớ đột biên trên các nhiêm săc thể chuôi nhị phân. VỚI mỗi vị trí ì trong nhiễm sắc thê a . ũ . íim ta sinh ra một sô thực ngẫu nhiên p trong 0 1 Qua đột biến a được biên thành à như sau a a . o. a m trong dó Jai nếuPi Pm 1 -Hi nê upj pm Sau quá trình chọn lọc lai ghép đột biến một thế hộ mổi được sinh ra. Công việc còn lại của thuật toán di truyền bây giò chỉ là lặp lại các bước trên. Ví du. Xét bài toán tìm max của hàm f x X2 với X là sô nguyên trên đoạn Đê sử dụng TTDT ta mã hoá mỗi sô nguyên X trong đoạn 0 31 bởi một sô nhị phân độ dài 5 chẩng hạn chuỗi 11000 là mã của sô nguyên 24. Hàm thích nghi được xác định là chính hàm x - X2. Quẩn thê ban đầu gồm 4 cá thê cỡ của quần thê là n - 4 . Thực hiện quá trình chọn lọc. ta nhận được kết quả trong bảng sau. Trong bảng 62 TRÍ TUỆ NHẰN TẠO này ta thây cá thế 2 có độ thích nghi cao nhất 576 nên nó dưực chọn 2 lần cá thể 3 có độ thích nghi thấp nhất 64 không được chọn lần nào. Mồi cá thê 1 và 4 được chọn 1 lổn. Bảng kết quả chọn lọc Số hiệu cá thể Quần thề ban đẩu X Độ thích nghi f x - X2 Số tắn được chọn 1 0 1 1 c 1 13 169 1 2 110 0 0 24 576 2 i 3 0 10 0 0 8 64 ũ 10 0 11 19 361 1 Thực hiện qúa trình lai ghép với xác suât lai ghép p . 1 cả 4 cá thê sau chọn lọc đều được lai ghép. Két quá lai ghép dược cho .
