Đại diện kiểu gen

Một trong những quyết định quan trọng nhất cần thực hiện trong khi triển khai thuật toán di truyền là quyết định cách biểu diễn mà chúng tôi sẽ sử dụng để đại diện cho các giải pháp của mình. Người ta đã quan sát thấy rằng đại diện không đúng có thể dẫn đến hiệu suất kém của GA.

Vì vậy, việc lựa chọn một đại diện thích hợp, xác định đúng các ánh xạ giữa không gian kiểu hình và kiểu gen là điều cần thiết cho sự thành công của một GA.

Trong phần này, chúng tôi trình bày một số biểu diễn thường được sử dụng nhất cho các thuật toán di truyền. Tuy nhiên, cách biểu diễn rất cụ thể về vấn đề và người đọc có thể thấy rằng một cách biểu diễn khác hoặc kết hợp các cách biểu diễn được đề cập ở đây có thể phù hợp với vấn đề của mình hơn.

Biểu diễn nhị phân

Đây là một trong những cách biểu diễn đơn giản nhất và được sử dụng rộng rãi nhất trong GAs. Trong kiểu biểu diễn này, kiểu gen bao gồm các chuỗi bit.

Đối với một số vấn đề khi không gian giải pháp bao gồm các biến quyết định Boolean - có hoặc không, biểu diễn nhị phân là đương nhiên. Lấy ví dụ vấn đề Knapsack 0/1. Nếu có n mục, chúng ta có thể biểu diễn một nghiệm bằng một chuỗi nhị phân gồm n phần tử, trong đó phần tử ^thứ x cho biết mục x có được chọn (1) hay không (0).

Đối với các bài toán khác, cụ thể là những bài toán liên quan đến số, chúng ta có thể biểu diễn các số bằng biểu diễn nhị phân của chúng. Vấn đề với kiểu mã hóa này là các bit khác nhau có ý nghĩa khác nhau và do đó các toán tử đột biến và giao nhau có thể gây ra những hậu quả không mong muốn. Điều này có thể được giải quyết ở một mức độ nào đó bằng cách sử dụngGray Coding, vì sự thay đổi trong một bit không có ảnh hưởng lớn đến giải pháp.

Đại diện có giá trị thực

Đối với các vấn đề mà chúng ta muốn xác định các gen bằng cách sử dụng các biến liên tục thay vì rời rạc, biểu diễn có giá trị thực là tự nhiên nhất. Tuy nhiên, độ chính xác của các số có giá trị thực hoặc dấu phẩy động này bị giới hạn trong máy tính.

Biểu diễn số nguyên

Đối với các gen có giá trị rời rạc, chúng ta không phải lúc nào cũng giới hạn không gian nghiệm thành nhị phân 'có' hoặc 'không'. Ví dụ: nếu chúng ta muốn mã hóa bốn khoảng cách - Bắc, Nam, Đông và Tây, chúng ta có thể mã hóa chúng thành{0,1,2,3}. Trong những trường hợp như vậy, biểu diễn số nguyên là mong muốn.

Biểu diễn hoán vị

Trong nhiều bài toán, lời giải được biểu diễn bằng thứ tự các phần tử. Trong những trường hợp như vậy, biểu diễn hoán vị là phù hợp nhất.

Một ví dụ kinh điển của cách biểu diễn này là vấn đề nhân viên bán hàng lưu động (TSP). Trong điều này, nhân viên bán hàng phải đi một vòng quanh tất cả các thành phố, thăm chính xác mỗi thành phố một lần và quay trở lại thành phố xuất phát. Tổng khoảng cách của chuyến tham quan phải được giảm thiểu. Giải pháp cho TSP này tự nhiên là một thứ tự hoặc hoán vị của tất cả các thành phố và do đó sử dụng một biểu diễn hoán vị có ý nghĩa cho vấn đề này.