Thuật toán di truyền - Đột biến
Giới thiệu về đột biến
Nói một cách dễ hiểu, đột biến có thể được định nghĩa là một sự thay đổi ngẫu nhiên nhỏ trong nhiễm sắc thể, để có được một giải pháp mới. Nó được sử dụng để duy trì và giới thiệu sự đa dạng trong quần thể di truyền và thường được áp dụng với xác suất thấp -pm. Nếu xác suất rất cao, GA sẽ được giảm xuống thành một tìm kiếm ngẫu nhiên.
Đột biến là một phần của GA có liên quan đến việc "khám phá" không gian tìm kiếm. Người ta đã quan sát thấy rằng đột biến là yếu tố cần thiết cho sự hội tụ của GA trong khi sự trao đổi chéo thì không.
Toán tử đột biến
Trong phần này, chúng tôi mô tả một số toán tử đột biến được sử dụng phổ biến nhất. Giống như các toán tử chéo, đây không phải là một danh sách đầy đủ và nhà thiết kế GA có thể tìm thấy sự kết hợp của các phương pháp này hoặc toán tử đột biến cụ thể cho vấn đề hữu ích hơn.
Đột biến lật bit
Trong đột biến lật bit này, chúng tôi chọn một hoặc nhiều bit ngẫu nhiên và lật chúng. Điều này được sử dụng cho các GA được mã hóa nhị phân.
Đặt lại ngẫu nhiên
Đặt lại ngẫu nhiên là một phần mở rộng của phép lật bit cho biểu diễn số nguyên. Trong trường hợp này, một giá trị ngẫu nhiên từ tập hợp các giá trị cho phép được gán cho một gen được chọn ngẫu nhiên.
Hoán đổi đột biến
Trong đột biến hoán đổi, chúng ta chọn ngẫu nhiên hai vị trí trên nhiễm sắc thể và hoán đổi các giá trị. Điều này là phổ biến trong mã hóa dựa trên hoán vị.
Đột biến tranh giành
Đột biến xáo trộn cũng phổ biến với các biểu diễn hoán vị. Trong trường hợp này, từ toàn bộ nhiễm sắc thể, một tập hợp con của các gen được chọn và giá trị của chúng được xáo trộn hoặc xáo trộn một cách ngẫu nhiên.
Đột biến đảo ngược
Trong đột biến đảo ngược, chúng tôi chọn một tập hợp con của các gen giống như trong đột biến xáo trộn, nhưng thay vì xáo trộn tập hợp con, chúng tôi chỉ đảo ngược toàn bộ chuỗi trong tập hợp con.