Crossover hoạt động trong thuật toán di truyền cho TSP

Question

Tôi đang cố gắng để giải quyết vấn Travelling Salesman Problem (TSP) với Genetic algorithm

My Genome là hoán vị của đỉnh trong đồ thị (đường dẫn cho Salesman).

Tôi nên thực hiện thao tác chéo trên bộ gen của mình như thế nào?

Tôi có thể tìm thấy việc triển khai sự cố của mình ở đâu trong C#?

Answer 1

Bạn nên kiểm tra "Giải pháp thuật toán di truyền của TSP tránh chéo đặc biệt và đột biến" của Gokturk Ucoluk. PDF here. Nó cung cấp cho một cái nhìn tổng quan về các toán tử chéo đặc biệt cho hoán vị và đề xuất một đại diện thông minh của hoán vị hoạt động tốt với crossover tiêu chuẩn (tức là vượt qua hai hoán vị luôn tạo ra hai hoán vị).

Sự thấu hiểu chính là đại diện cho hoán vị như chuỗi đảo ngược của nó, ví dụ cho mỗi phần tử i, lưu trữ trong a[i] bao nhiêu yếu tố lớn hơn i là bên trái của i trong hoán vị. Không giống như biểu diễn trực tiếp, ràng buộc duy nhất trên a[i] là địa phương, tức là a[i] không thể lớn hơn N - i. Điều này có nghĩa là sự giao nhau đơn giản của hai chuỗi đảo ngược hợp lệ luôn tạo ra hai chuỗi đảo ngược hợp lệ - không cần xử lý đặc biệt các phần tử lặp lại.

Answer 2

Đây là cách tiếp cận a C# program cho những gì bạn đang tìm kiếm.

Liên quan đến sự quan tâm (hoặc thiếu) thực hiện chéo, tất cả sẽ xoay quanh logic lựa chọn cụ thể mà triển khai của bạn sẽ sử dụng (và/hoặc chính hàm đánh giá). tốc độ cải thiện). Trong nhiều trường hợp, hoạt động cross-over sẽ "giải cứu từ khối cắt" một số giải pháp hiệu quả/tối ưu trong một khu vực của biểu đồ nhưng bằng cách nào đó "bị kẹt" ở những người khác. Đây không phải là để nói rằng nếu thuật toán tổng thể đủ chậm và bao gồm một tỷ lệ phần trăm tốt của dung dịch, các giải pháp tương tự có thể không được phát hiện một lần nữa, nhưng cross-over cũng có thể làm tăng những khám phá này (và/hoặc cho phép bạn mắc kẹt một số địa phương khác ;-))

Không liên quan trực tiếp nhưng đáng chú ý đến bất kỳ ai nhìn vào GA, là thí nghiệm "cuối cùng" original "ultimate" experiment in GA ban đầu của GA bởi Giáo sư Alderman (danh tiếng RSA), người đã sử dụng phân tử DNA thực tế [ vào một chương trình C - chỉ đùa] để giải quyết một vấn đề đồ thị liên quan, đó là đồ thị của đồ thị Hamilton.

Sửa: Trong đọc lại câu hỏi tôi hiểu tại sao bạn hỏi nó hay chính xác hơn lý do tại sao bạn muốn một "Không bạn không muốn cross-over" reply ;-)
bạn genonme được gắn trực tiếp với biểu đồ chính nó (không có gì sai với điều đó, một số trước là), nhưng điều này mang lại cho trở ngại rằng hầu hết các kết nối chéo sẽ không khả thi, vì chúng có thể có các nút trùng lặp (truy cập cùng một thành phố hai lần hoặc nhiều hơn) và thiếu các nút (không truy cập vào một số thành phố) ... Hơn nữa, cross-overs khả thi sẽ ảnh hưởng đến các đồ thị tương tự, và do đó có thể chỉ gia tăng tìm kiếm, so với những gì mutat các ion sẽ phát hiện ra ...
Hum ... Sau đó, có thể giao nhau, trong triển khai cụ thể này sẽ không giúp thuật toán rất nhiều (và thực sự mất nhiều CPU để tạo, kiểm tra và thường loại bỏ chéo offsprings, CPU mà sẽ được sử dụng tốt hơn bằng cách affording lặp lại nhiều hơn, và một tốc độ làm mát chậm hơn ...). Trừ khi! Bạn tìm thấy một cách thông minh để thực hiện các thao tác chéo ;-)

Answer 3

Mục đích của việc chéo để mở rộng không gian tìm kiếm tiến hóa bằng cách kết hợp các kết hợp gen mới lạ.

Chỉ tiêu chí thực sự cần thiết cho quá trình tiến hóa là sản phẩm chéo có chứa các phần của cả cha lẫn mẹ và đại diện cho bộ gen hợp lệ.

Chỉ bạn biết quy tắc hợp lệ cho thuật toán của bạn để chỉ có thể chỉ định phương thức chéo sẽ hoạt động (trừ khi bạn muốn chia sẻ thêm chi tiết về quy tắc xác thực cho cấu trúc bộ gen của bạn).

Answer 4

"Crossover" trong thuật toán di truyền chỉ đề cập đến cách trộn hai chuỗi "chuỗi di truyền", mỗi chuỗi đại diện cho một giải pháp cụ thể cho vấn đề (cách trình tự ánh xạ tới giải pháp tùy thuộc vào bạn). Vì vậy, ví dụ, nói rằng bạn có một dân số mà bao gồm hai chuỗi sau:

AAAAAAAAAA 
BBBBBBBBBB 

Một cách để tái kết hợp hai "cha mẹ" chuỗi là để chọn ngẫu nhiên một điểm chéo (nói, vị trí 3), kết quả trong hai chuỗi những "đứa trẻ":

AAABBBBBBB 
BBBAAAAAAA 

Hoặc, bạn có thể chọn một cách ngẫu nhiên hai điểm chéo (nói, 3 và 8), kết quả là hai chuỗi này:

AAABBBBBAA 
BBBAAAAABB 

Đối với niềm vui và thêm v ariability, bạn cũng có thể giới thiệu về khả năng đột biến điểm thỉnh thoảng:

AAABBBABAA 
BBBAAAAABB 

Có không thực sự bất kỳ quy tắc cứng và nhanh liên quan đến cách bạn thực hiện chéo trong một thuật toán di truyền, giống như không có thực sự bất kỳ các quy tắc cứng nhắc và nhanh chóng điều khiển Evolution trong thế giới sinh học. Dù công trình, công trình.

Answer 5

Khi tôi học khóa đầu tiên tại trường đại học, tôi đã thực hiện một số phép tính (mất khoảng 30 trang) về tác động của các toán tử GA khác nhau đến sự hội tụ của giải pháp. Như tôi nhớ, sự giao nhau không phải là giải pháp tốt nhất cho TSP, giải pháp phù hợp hơn là đột biến, ngược lại là chuỗi con của các đỉnh.

dụ:

trước: Một BCDEF GH

sau: Một FEDCB GH

Answer 6

Thay vì sử dụng các tiêu chuẩn GA cross-over kỹ thuật (như outlined by MusiGenesis), nó tốt hơn để sử dụng ordered cross-over for the Travelling Salesman problem.

Cách tiếp cận thông thường không hoạt động tốt cho TSP vì chức năng tập thể dục rất nhạy cảm với các vị trí tương đối của các thành phố khác nhau trong tuyến phát triển hơn là vị trí tuyệt đối của chúng. Ví dụ: nếu bạn đã truy cập tất cả các thủ đô châu Âu, tuyến đường ngắn nhất không thực sự phụ thuộc vào việc bạn ghé thăm Bratislava 1, 2 hoặc 9. Điều quan trọng hơn là bạn ghé thăm nó immediately before or immediately after visiting Vienna thay vì ghé thăm Helsinki, Athens và 6 thủ đô khác ở giữa.

Tất nhiên, là mjv also points out, giao diện truyền thống cũng sẽ giới thiệu các bản trùng lặp trong tuyến đường của bạn. Nếu một phụ huynh có Paris ở vị trí thứ 2 và một vị trí khác có Paris ở vị trí 14, việc giao nhau có thể dẫn đến một lộ trình đã ghé thăm Paris hai lần (và bỏ lỡ một thành phố khác) và một tuyến đường khác không phát triển được. Nhà điều hành di truyền chéo chéo đã ra lệnh không bị vấn đề này. Nó bảo tồn các yếu tố và sửa đổi thứ tự.

Answer 7

Dưới đây là cách triển khai chính xác của tôi về phương thức "được ánh xạ một phần được ánh xạ" trong GA cho TSP.

Here là bài báo giải thích sự giao nhau được ánh xạ một phần theo lý thuyết và dưới đây là mã của tôi.

//construct a new individual with the genes of the parents 
//method used is cross over mapping 
//note that Individual datastrucuture contains an integer array called Genes which   //contains the route. 
// 
public Individual Breed(Individual father, Individual mother) 
{ 
    int[] genes = new int[father.Genes.Length]; 
    int[] map = new int[father.Genes.Length + 1]; //create a map to map the indices 
    int crossoverPoint1 = rand.Next(1, father.Genes.Length - 2); //select 2 crossoverpoints, without the first and last nodes, cuz they are always thje same 
    int crossoverPoint2 = rand.Next(1, father.Genes.Length - 2); 
    father.Genes.CopyTo(genes, 0); //give child all genes from the father 
    for (int i = 0; i < genes.Length; i++) //create the map 
    { 
     map[genes[i]] = i; 
    } 
    //int[] genesToCopy = new int[Math.Abs(crossoverPoint1 - crossoverPoint2)]; //allocate space for the mother genes to copy 
    if (crossoverPoint1 > crossoverPoint2) //if point 1 is bigger than point 2 swap them 
    { 
     int temp = crossoverPoint1; 
     crossoverPoint1 = crossoverPoint2; 
     crossoverPoint2 = temp; 
    } 
    //Console.WriteLine("copy mother genes into father genes from {0} to {1}", crossoverPoint1, crossoverPoint2); 
    for (int i = crossoverPoint1; i <= crossoverPoint2; i++) //from index one to the 2nd 
    { 
     int value = mother.Genes[i]; 
     int t = genes[map[value]]; //swap the genes in the child 
     genes[map[value]] = genes[i]; 
     genes[i] = t; 
     t = map[genes[map[value]]]; //swap the indices in the map 
     map[genes[map[value]]] = map[genes[i]]; 
     map[genes[i]] = t; 
    } 
    Individual child = new Individual(genes); 
    return child; 
}