Từ các cá thể đượ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 thể 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 đoạn [0, m -1], p là vị trí điểm ghép. | Từ các cá thể đượ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 thể 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 đoạn 0 m -1 p là vị trí điểm ghép. Cặp gồm hai nhiễm sắc thể a a1 . ap ap 1 . am a bi . bp bp 1 . bm được thay bởi hai con là a a1 . ap bp 1 . bm b b1 . bp ap 1 . am 3. Đột biến Ta thực hiện toán tử đột biến trên các cá thể có được sau quá trình lai ghép. Đột biến là thay đổi trạng thái một số gien nào đó trong nhiễm sắc 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 đị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í i trong nhiễm sắc thể a a1 . ai . am Ta sinh ra một số thực nghiệm ngẫu nhiên pi trong 0 1 . Qua đột biến a được biến thành a như sau a a 1 . a i . a m Trong đó C a i ai nếu pi pm L1 - ai nếu pi 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í dụ 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 0 31 . Để 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 f 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 này ta thấy cá thể 2 có độ thích nghi cao nhất 576 nên nó đượ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ố liệu cá thể Quần thể ban đầu x Độ thích nghi f x x2 Số lần được chọn 1 0 1 1 0 1 13 169 1 2 1 1 0 0 0 24 576 2 3 0 1 0 0 0 8 64 0 4 1 0 0 1 1 19 361 1 Thực hiện qúa trình lai ghép với xác suất lai ghép pc 1 cả 4 cá thể sau chọn lọc đều được lai ghép. Kết quả lai ghép được cho trong bảng sau. Trong bảng này
