Thuật toán di truyền là cấu trúc toán học dùng quy trình kế thừa gen. Đã áp dụng thành công cho nhiều vấn đề phân tích. Khai thác dữ liệu kết nối hiểu biết con người với phân tích tự động thông tin để tìm mẫu hoặc quan hệ then chốt.
Cho CSDL lớn biểu diễn qua nhiều biến, mục tiêu tìm hiệu quả mẫu thú vị nhất trong CSDL. Thuật toán di truyền dùng nhận diện mẫu thú vị trong một số phần mềm. Thường dùng trong khai thác dữ liệu để tăng cường thực thi thuật toán khác, như thuật toán cây quyết định, quy tắc liên kết khác.
Thuật toán di truyền cần cấu trúc dữ liệu cụ thể. Hoạt động trên quần thể với đặc trưng định nghĩa dạng categorical. So sánh với di truyền: quần thể (gene) chứa đặc trưng. Cách thực hiện thuật toán di truyền: dùng toán tử (lai ghép, crossover, chọn lọc) với đặc trưng đột biến để cải thiện tạo ra tổ hợp có thể tốt hơn.
Quy trình thuật toán di truyền:
Chọn ngẫu nhiên cha mẹ.
Lai ghép qua crossover.
Lai tạo là chọn thực thể đơn lẻ nào tồn tại. Nói cách khác, hàm mục tiêu hoặc đặc trưng chọn lọc cần thiết quyết định sinh tồn. Crossover mô tả thay đổi sản xuất tương lai của thực thể.
Chọn cá thể sống sót cho thế hệ tiếp theo qua hàm độ thích nghi (fitness function).
Đột biến là dịch vụ thay đổi ngẫu nhiên thuộc tính của thực thể ngẫu nhiên chọn trong các phép toán tiếp theo.
Lặp lại cho đến đạt mức độ thích nghi cho trước, hoặc số lần lặp hiện tại đạt đến.
Tham số thuật toán di truyền: kích thước quần thể, tỷ lệ crossover, tỷ lệ đột biến.
Ưu Điểm Thuật Toán Di Truyền
Thuật toán di truyền rất dễ tạo và xác thực, làm cho chúng hấp dẫn nếu dùng.
Thuật toán song song, nghĩa là dùng cho quần thể lớn hiệu quả. Thuật toán cũng hiệu quả: nếu bắt đầu với giải pháp gốc kém, nhanh tiến đến giải pháp tốt nhất.
Sử dụng đột biến làm phương pháp đủ để nhận diện tối ưu toàn cục ngay trong quy tắc vấn đề phi tuyến tính phức tạp. Phương pháp không cần kiến thức về phân phối thông tin.
Nhược Điểm Thuật Toán Di Truyền
Thuật toán di truyền cần ánh xạ tập dữ liệu từ nơi thuộc tính có giá trị rời rạc cho thuật toán làm việc. Thường có thể nhưng mất nhiều thông tin chi tiết khi xử lý biến liên tục.
Có giới hạn kích thước tập dữ liệu có thể xem xét với thuật toán di truyền.
Với tập dữ liệu rất lớn, lấy mẫu cần thiết, dẫn đến nhiều kết quả khác nhau qua nhiều lần chạy trên cùng tập dữ liệu.
Việc mã hóa thông tin thành dạng categorical có thể vô tình dẫn đến thiên lệch trong bản ghi.