áp dụng chéo và đột biến vào biểu đồ (thuật toán di truyền)

Question

Tôi đang chơi arround với thuật toán di truyền mà tôi muốn phát triển biểu đồ. Bạn có biết cách áp dụng giao thoa và đột biến khi nhiễm sắc thể là biểu đồ không?

Hoặc tôi có thiếu mã hóa cho biểu đồ cho phép tôi áp dụng giao thoa "thường xuyên" và đột biến trên chuỗi bit không?

cảm ơn rất nhiều! Bất kỳ trợ giúp nào, ngay cả khi nó không liên quan trực tiếp đến vấn đề của tôi, được đánh giá cao!

Manuel

Answer 1

Tôi thích Sandor's suggestion của việc sử dụng Ken Stanley NEAT algorithm.

NEAT được thiết kế để phát triển các mạng nơron với các cấu trúc liên kết tùy ý, nhưng đó chỉ là các biểu đồ hướng về cơ bản. Có nhiều cách để phát triển mạng nơron trước NEAT, nhưng một trong những đóng góp quan trọng nhất của NEAT là nó cung cấp một cách để thực hiện sự giao nhau có ý nghĩa giữa hai mạng có các toplog khác nhau.

Để thực hiện điều này, NEAT sử dụng historical markings gắn với mỗi gen để "xếp hàng" các gen của hai bộ gen trong quá trình chéo (một nhà sinh học quá trình gọi synapsis). Ví dụ:

crossover with different topologies in NEAT http://natekohl.net/media/neat-crossover.png

(Trong ví dụ này, mỗi gen là một hộp và đại diện cho một kết nối giữa hai nút Số ở phía trên cùng của mỗi gen là lịch sử đánh dấu cho gen đó..)

Tóm tắt: Lining gen dựa trên dấu hiệu lịch sử là một cách chủ yếu để thực hiện chéo giữa hai mạng mà không có phân tích topo đắt tiền.

Answer 2

Vâng, tôi đã không bao giờ chơi với một thực hiện như vậy, nhưng cuối cùng cho chéo bạn có thể chọn một chi nhánh của một trong những biểu đồ và trao đổi nó với một chi nhánh từ biểu đồ khác.
Đối với đột biến, bạn có thể ngẫu nhiên thay đổi một nút bên trong biểu đồ, với xác suất nhỏ.

Answer 3

Bạn cũng có thể thử Genetic Programming. Một đồ thị sẽ là thứ gần nhất với cây và GP sử dụng cây ... nếu bạn vẫn muốn sử dụng GA thay vì GP thì hãy xem sự giao nhau được thực hiện như thế nào trên GP và có thể cho bạn ý tưởng cách thực hiện nó trên đồ thị của GA của bạn:

Crossover http://www.geneticprogramming.com/Tutorial/cross1.gif

Sau đây là cách chéo cho cây (và đồ thị) hoạt động:

1. bạn chọn 2 mẫu cho giao phối.
2. Bạn chọn một nút ngẫu nhiên từ một phụ huynh và trao đổi nó với một nút ngẫu nhiên trong phụ huynh khác.
3. Cây kết quả là con cái.

Answer 4

Như những người khác đã đề cập, một cách phổ biến để biểu đồ chéo (hoặc cây) trong GA là hoán đổi đồ thị con (subtrees). Đối với đột biến, chỉ ngẫu nhiên thay đổi một số nút (w/xác suất nhỏ).

Hoặc, nếu bạn đại diện cho biểu đồ dưới dạng ma trận kề, thì bạn có thể hoán đổi/thay đổi các phần tử trong ma trận (loại giống như sử dụng chuỗi bit hai chiều).

Answer 5

Tôi không chắc chắn nếu sử dụng chuỗi bit là ý tưởng hay nhất, tôi muốn thể hiện ít nhất trọng số với giá trị thực. Tuy nhiên bitstrings cũng có thể làm việc.

Nếu bạn có một topo cố định, sau đó cả hai chéo và đột biến là khá dễ dàng (giả sử bạn chỉ phát triển các trọng của mạng):

Crossover: mất một trọng lượng từ một phụ huynh, phần còn lại từ người kia, có thể được thực hiện rất dễ dàng nếu bạn đại diện cho trọng số dưới dạng mảng hoặc danh sách. Để biết thêm chi tiết hoặc các lựa chọn thay thế, hãy xem http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29.

Đột biến: chỉ cần chọn một số trọng số và điều chỉnh chúng một chút.

Phát triển một số nội dung khác (ví dụ: chức năng kích hoạt) tương tự như vậy.

Nếu bạn cũng muốn phát triển cấu trúc liên kết thì mọi thứ trở nên thú vị hơn nhiều. Có một số khả năng đột biến bổ sung, như thêm nút (có khả năng kết nối với hai nút đã tồn tại), tách một kết nối (thay vì A-> B có A-> C-> B), thêm kết nối, hoặc đối lập trong số này.

Nhưng giao nhau sẽ không quá dễ dàng (ít nhất là nếu số lượng nút không cố định), vì bạn có thể muốn tìm các nút "khớp" (nơi khớp có thể là bất kỳ thứ gì, nhưng có thể liên quan đến tương tự " vai trò ", hoặc một vị trí tương tự trong mạng). Nếu bạn cũng muốn làm điều đó tôi muốn khuyên bạn nên nghiên cứu kỹ thuật đã tồn tại. Một cái mà tôi biết và thích được gọi là NEAT. Bạn có thể tìm thấy một số thông tin về nó ở
http://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies
http://nn.cs.utexas.edu/?neat
và http://www.cs.ucf.edu/~kstanley/neat.html