Thuật toán di truyền - Nguyên tắc cơ bản
Phần này giới thiệu các thuật ngữ cơ bản cần thiết để hiểu GAs. Ngoài ra, cấu trúc chung của GA được trình bày trong cả haipseudo-code and graphical forms. Người đọc nên hiểu đúng tất cả các khái niệm được giới thiệu trong phần này và ghi nhớ chúng khi đọc các phần khác của hướng dẫn này.
Thuật ngữ cơ bản
Trước khi bắt đầu thảo luận về Thuật toán di truyền, điều cần thiết là phải làm quen với một số thuật ngữ cơ bản sẽ được sử dụng trong suốt hướng dẫn này.
Population- Nó là một tập hợp con của tất cả các giải pháp có thể (được mã hóa) cho vấn đề đã cho. Dân số cho một GA tương tự với dân số cho con người ngoại trừ việc thay vì con người, chúng tôi có các Giải pháp Ứng viên đại diện cho con người.
Chromosomes - Một nhiễm sắc thể là một trong những giải pháp như vậy cho vấn đề đã cho.
Gene - Một gen là một vị trí thành phần của nhiễm sắc thể.
Allele - Đó là giá trị mà một gen nhận được cho một nhiễm sắc thể cụ thể.
Genotype- Kiểu gen là quần thể trong không gian tính toán. Trong không gian tính toán, các giải pháp được trình bày theo cách có thể dễ dàng hiểu và thao tác bằng hệ thống máy tính.
Phenotype - Kiểu hình là quần thể trong không gian giải pháp thế giới thực trong đó các giải pháp được biểu diễn theo cách chúng được biểu diễn trong các tình huống thế giới thực.
Decoding and Encoding - Đối với các vấn đề đơn giản, phenotype and genotypekhông gian giống nhau. Tuy nhiên, trong hầu hết các trường hợp, không gian kiểu hình và kiểu gen là khác nhau. Giải mã là một quá trình biến đổi một giải pháp từ kiểu gen sang không gian kiểu hình, trong khi mã hóa là một quá trình chuyển từ kiểu hình sang không gian kiểu gen. Việc giải mã phải nhanh chóng vì nó được thực hiện nhiều lần trong GA trong quá trình tính toán giá trị phù hợp.
Ví dụ, hãy xem xét vấn đề Knapsack 0/1. Không gian Kiểu hình bao gồm các giải pháp chỉ chứa số mục của các mục được chọn.
Tuy nhiên, trong không gian kiểu gen, nó có thể được biểu diễn dưới dạng một chuỗi nhị phân có độ dài n (với n là số mục). A0 at position x đại diện cho điều đó xthmục được chọn trong khi số 1 đại diện cho điều ngược lại. Đây là trường hợp không gian kiểu gen và kiểu hình khác nhau.
Fitness Function- Một hàm phù hợp được định nghĩa đơn giản là một hàm lấy giải pháp làm đầu vào và tạo ra tính phù hợp của giải pháp làm đầu ra. Trong một số trường hợp, chức năng thể dục và chức năng mục tiêu có thể giống nhau, trong khi ở những trường hợp khác, nó có thể khác tùy theo vấn đề.
Genetic Operators- Những điều này làm thay đổi thành phần di truyền của thế hệ con. Chúng bao gồm trao đổi chéo, đột biến, chọn lọc, v.v.
Cấu trúc cơ bản
Cấu trúc cơ bản của GA như sau:
Chúng tôi bắt đầu với một quần thể ban đầu (có thể được tạo ra một cách ngẫu nhiên hoặc được gieo mầm bởi các nhà nghiên cứu khác), chọn các cặp bố mẹ từ quần thể này để giao phối. Áp dụng các toán tử giao thoa và đột biến trên bố mẹ để tạo ra các lò xo mới. Và cuối cùng những con suối tắt này thay thế các cá thể hiện có trong quần thể và quá trình này lặp lại. Bằng cách này, các thuật toán di truyền thực sự cố gắng bắt chước sự tiến hóa của con người ở một mức độ nào đó.
Mỗi bước sau đây được đề cập thành một chương riêng biệt ở phần sau của hướng dẫn này.
Mã giả tổng quát cho GA được giải thích trong chương trình sau:
GA()
initialize population
find fitness of population
while (termination criteria is reached) do
parent selection
crossover with probability pc
mutation with probability pm
decode and fitness calculation
survivor selection
find best
return best