Thuật toán di truyền: Tỷ lệ đột biến cao dẫn đến thời gian chạy thấp hơn

Question

Tôi đã triển khai thuật toán di truyền để giải quyết Vấn đề bán hàng du lịch nâng cao (trọng lượng của các cạnh thay đổi theo thời gian trong ngày). Hiện nay tôi đang đánh giá các thông số khác nhau của mô phỏng của tôi và tôi stumbled khi một mối tương quan Tôi không thể giải thích cho bản thân mình:

Một tỷ lệ đột biến cao hơn dẫn đến một thời gian chạy thấp hơn. Cá nhân tôi sẽ giả định ngược lại, vì tỷ lệ đột biến cao hơn tạo ra nhiều hoạt động hơn. (Tỷ lệ đột biến 25% nhanh hơn 12% so với 5%)

Kết quả tốt nhất đạt được với tỷ lệ đột biến 8% (5% tốt hơn 10% và 25% thực hiện tồi tệ nhất (trừ 0%)) A giá trị thể dục thấp hơn ist tốt hơn.

Số đếm lặp được thiết lập bởi tham số hệ được thiết lập để 10.000 trong tất cả các trường hợp thử nghiệm.

Mỗi trường hợp thử nghiệm được thực thi 10 lần.

thực hiện của tôi (trong python) của đột biến trông như thế này:

def mutate(self,p): 
    for i in self.inhabitants: 
     r = random() 
     if r <= p: 
      i.mutate() 

p là tỷ lệ đột biến

Các đột biến trông như thế này

def mutate(self): 
    r1 = randint(0,self.locations.size()-1) 
    r2 = randint(0,self.locations.size()-1) 
    self.locations.swap(r1,r2) 

Tại sao một đột biến cao hơn tỷ lệ dẫn đến thời gian thực hiện nhanh hơn?

Edit: Tôi thực sự chạy các bài kiểm tra tương tự trên Raspberry Pi của tôi (đó là chậm hơn 9 lần) và nó kết quả trong các kết quả tương tự:

Answer 1

Mỗi chu kỳ i các đột biến có một xác suất p _i cung cấp giải pháp có thể chấp nhận và thời gian cần để đánh giá chu kỳ là T _i. Cả hai p _i và T _i tăng với tỷ lệ đột biến. Do đó, thời gian chạy dự kiến ​​của thuật toán của bạn là tổng số Σ p _i T _i trong số chu kỳ mong muốn cần thiết để tìm câu trả lời. Tỷ lệ đột biến cao hơn làm tăng kích thước của mỗi cụm từ, nhưng giảm số lượng thuật ngữ để tổng hợp. Có một tỷ lệ đột biến tối ưu giúp giảm thiểu số tiền này.

Answer 2

Nó là không thể biết mà không nhìn thấy mã đầy đủ của bạn, nhưng sau có vẻ hợp lý:

Khi tỷ lệ đột biến là thấp hơn sau đó, sau một vài thế hệ, người dân trở nên nhiều hơn nữa đồng nhất hơn là khi đột biến tỷ lệ cao hơn.Bên dưới giả định rằng bạn đang sử dụng một số biến thể lấy mẫu bánh xe roulette, một quần thể đồng nhất hơn có nghĩa là mỗi "spin" của bánh xe roulette mất trung bình dài hơn khi bạn có dân số đa dạng hơn (nơi tương đối ít thành viên sẽ thống trị phân phối tập thể dục và do đó có xu hướng được lựa chọn sau khi quét qua ít thành viên của dân số hơn).

Để chắc chắn hơn, bạn có thể sử dụng công cụ lược tả chẳng hạn như cProfile để xem chính xác nơi các chu kỳ CPU đó đang hoạt động.