Thuật toán di truyền, dân số lớn so với số nhỏ

Question

Tôi tự hỏi liệu có quy tắc chung về ngón tay cái để định cỡ dân số hay không. Ive đọc trong một cuốn sách có chiều dài nhiễm sắc thể là một điểm khởi đầu tốt. Am i chính xác trong giả định sau đó rằng nếu tôi đã có một phương trình với 5 biến, tôi nên có một dân số 10?

Im cũng tự hỏi nếu sau đây là đúng:

Larger Kích Dân.

Ưu điểm: Tính đa dạng lớn hơn để có nhiều khả năng nhận các đặc điểm mang lại sự tập thể dục tốt.

Nhược điểm: Cần thời gian xử lý lâu hơn.

vs

Kích thước dân số nhỏ hơn.

Ưu điểm: Số lượng lớn hơn các thế hệ trải qua trên một đơn vị thời gian.

Nhược điểm: Đột biến sẽ phải nổi bật hơn để đền bù cho dân số nhỏ hơn ??

EDIT

Một chút thông tin bổ sung, nói rằng tôi có một phương trình trong đó có 5 thông số chưa biết. Đối với mỗi tham số tôi có bất cứ nơi nào giữa 10-50 giá trị tôi muốn thử gán cho mỗi biến này. Vì vậy, ví dụ

variable1 = 20 giá trị khác nhau variable2 = 15 giá trị khác nhau ...

Tôi nghĩ một GA sẽ là một cách tiếp cận khá cho một vấn đề chẳng hạn như không gian tìm kiếm là khá lớn, trường hợp ví dụ tồi tệ nhất cho ở trên sẽ là 312.500.000 hoán vị (trừ khi tôi đã hơi say lên?) n!/(nk)! trong đó n = 50 và k = 1 => 50 * 50 * 50 * 50 * 50

tiếc là số tham số/dải giá trị cần kiểm tra có thể thay đổi rất nhiều vì vậy tôi đang tìm một số quy tắc chung tôi nên đặt dân số bao nhiêu.

Cảm ơn sự giúp đỡ của bạn + nếu có thêm thông tin bạn cần/thích thảo luận ở một trong các phòng chat, hãy cho tôi một tiếng hét.

Answer 1

Tôi không chắc chắn nơi bạn đọc 2x chiều dài nhiễm sắc thể là một điểm khởi đầu tốt, nhưng tôi đoán đó là một cuốn sách tập trung vào các vấn đề lớn hơn.

Nếu bạn chỉ có năm biến, thuật toán di truyền có lẽ không phải là lựa chọn phù hợp để hội tụ khi có giải pháp. Với chiều dài nhiễm sắc thể năm bạn có thể sẽ thấy rằng bạn rất nhanh chóng đạt tới điểm không xác định (điều này sẽ thay đổi trong lần chạy tiếp theo) tối thiểu cục bộ và từ từ lặp lại khoảng trống đó cho đến khi bạn tìm thấy mức tối thiểu địa phương thực sự.

Tuy nhiên, nếu bạn khăng khăng sử dụng GA, tôi khuyên bạn nên bỏ quy tắc chung cho vấn đề này và thực sự nghĩ về việc bắt đầu dân số như thước đo giải pháp cuối cùng bạn mong đợi một giải pháp ngẫu nhiên.

Lý do nhiều nguyên tắc phụ thuộc vào độ dài nhiễm sắc thể là vì đó là proxy phù hợp cho điều này, nếu tôi có hàng trăm biến và chuỗi tạo dna ngẫu nhiên sẽ trở nên lý tưởng hơn nếu tôi chỉ có một biến.

Ngoài ra, nếu bạn lo lắng về cường độ tính toán, tôi sẽ tiếp tục và nói rằng đó không phải là vấn đề vì bạn đang xử lý một bộ giải pháp nhỏ như vậy. Tôi cho rằng quy tắc ngón tay cái tốt hơn cho các nhóm nhỏ hơn như thế này sẽ nằm dọc theo các dòng:

(ln(chromosome_length*(solution_space/granularity)/mutation_rate))^2 

Có thể với sự cố không đổi về quy mô cho vấn đề cụ thể.

Đó chắc chắn không phải là một nguyên tắc lớn của ngón tay cái (không có quy tắc là) nhưng đây là logic của tôi cho nó:

• chiều dài nhiễm sắc thể chỉ là một proxy cho kích thước của không gian giải pháp, vì vậy có tính đến kích thước của không gian giải pháp nhất thiết sẽ tăng độ chính xác của proxy này
• Tỷ lệ đột biến nhỏ hơn đòi hỏi kích thước quần thể lớn hơn để bù đắp cho thực tế là bạn dễ bị bắt trong minima địa phương
• Bất kỳ quy tắc nào cũng cần chia tỷ lệ logarit thuật toán di truyền giống như tìm kiếm cây trong không gian giải pháp của bạn.
• Thuật ngữ bình phương chủ yếu là kết quả của việc thử điều này, nhưng có vẻ như tỉ lệ lôgarít hơi hung hãn, mặc dù hình dạng chung có vẻ đúng.

Tuy nhiên tôi cho rằng lựa chọn tốt hơn là bắt đầu với số lượng hợp lý (100) và thử lặp lại lên xuống cho đến khi bạn tìm thấy kích thước dân số cân bằng chính xác với tốc độ thực thi.

Answer 2

Giống như hầu hết các thông số thuật toán di truyền, kích thước dân số phụ thuộc nhiều vào vấn đề. Có một số yếu tố có thể giúp chỉ ra hướng bạn nên có kích thước dân số lớn hay nhỏ nhưng rất nhiều thời gian thử nghiệm các giá trị khác nhau so với giải pháp đã biết trước khi chạy nó trên vấn đề của bạn là một ý tưởng hay (nếu đây là tất nhiên là có thể).

Quy mô dân số 10 có vẻ khá nhỏ. Bạn nói rằng bạn có một phương trình với năm biến. Vấn đề của bạn có được biểu thị bằng một nhiễm sắc thể gồm 5 giá trị không? Nó có vẻ nhỏ đối với nhiễm sắc thể và nếu đây là trường hợp có thể sử dụng thuật toán di truyền có thể không phải là cách tốt nhất để giải quyết vấn đề. Có lẽ nếu bạn cung cấp thêm một chút chi tiết về vấn đề của bạn và cách bạn đại diện cho nó, mọi người có thể có ý tưởng tốt hơn về cách tư vấn cho bạn.

Tôi cũng muốn thêm rằng khuyết điểm của bạn đối với các kích thước dân số lớn và nhỏ không chính xác. Một quy mô dân số lớn hơn mất nhiều thời gian để xử lý hơn một nhỏ nhưng vì nó thường có thể giải quyết vấn đề nhanh hơn thì tổng thời gian xử lý không nhất thiết phải lâu hơn. đạt được, nó phụ thuộc rất nhiều vào vấn đề. Với đột biến kích thước dân số nhỏ hơn không cần phải nổi bật hơn. Đột biến thường được sử dụng để ngăn chặn các thuật toán di truyền trở thành bị mắc kẹt trong một tối đa địa phương và thường nên là một giá trị rất nhỏ. Một dân số nhỏ có nhiều khả năng bị mắc kẹt ở mức tối đa địa phương nhưng nếu bạn có một giá trị đột biến quá cao, bạn có thể vô hiệu hóa sự cải thiện tự nhiên của thuật toán di truyền.