So sánh và đối chiếu Phương pháp Monte-Carlo và các thuật toán tiến hóa

Question

Mối quan hệ giữa Monte-Carlo Method và Evolutionary Algorithms là gì? Trên khuôn mặt của nó, họ dường như là phương pháp mô phỏng không liên quan được sử dụng để giải quyết các vấn đề phức tạp. Những loại vấn đề nào phù hợp nhất? Họ có thể giải quyết cùng một tập hợp các vấn đề không? Mối quan hệ giữa hai (nếu có) là gì?

Answer 1

"Monte Carlo" là, theo kinh nghiệm của tôi, một thuật ngữ quá tải nặng nề. Mọi người dường như sử dụng nó cho bất kỳ kỹ thuật nào sử dụng trình tạo số ngẫu nhiên (tối ưu hóa toàn cầu, phân tích kịch bản (Google "mô phỏng Excel Monte Carlo"), tích hợp ngẫu nhiên (the Pi calculation mà mọi người sử dụng để chứng minh MC). trong câu hỏi của bạn, rằng bạn đang nói về kỹ thuật Monte Carlo để tối ưu hóa toán học: Bạn có một số chức năng thể dục với một số thông số đầu vào và bạn muốn giảm thiểu (hoặc tối đa hóa) chức năng đó. (có một mức tối thiểu toàn cầu duy nhất mà bạn sẽ đến bất kể bạn bắt đầu bằng đầu vào nào) thì tốt nhất bạn nên sử dụng kỹ thuật giảm thiểu xác định như phương pháp gradient liên hợp. Nhiều kỹ thuật phân loại học máy liên quan đến việc tìm kiếm các tham số giảm thiểu tối thiểu hình vuông lỗi cho hyperplane đối với tập huấn luyện. Hàm đang được giảm thiểu trong trường hợp này là một parabaloid trơn tru, được xử lý tốt, trong không gian n chiều. Tính gradient và cuộn xuống dốc. Dễ như ăn bánh.

Nếu, tuy nhiên, các thông số đầu vào của bạn là rời rạc (hoặc nếu chức năng thể dục của bạn có gián đoạn) thì không còn có thể tính toán độ dốc chính xác nữa. Điều này có thể xảy ra nếu chức năng thể dục của bạn được tính toán bằng cách sử dụng dữ liệu dạng bảng cho một hoặc nhiều biến (nếu biến X nhỏ hơn 0,5, hãy sử dụng bảng này khác sử dụng bảng đó). Ngoài ra, bạn có thể có một chương trình mà bạn nhận được từ NASA được tạo thành từ 20 mô-đun được viết bởi các nhóm khác nhau mà bạn chạy dưới dạng công việc theo lô. Bạn cung cấp nó với đầu vào và nó phun ra một số (nghĩ hộp đen). Tùy thuộc vào các thông số đầu vào mà bạn bắt đầu với bạn có thể kết thúc ở mức tối thiểu sai. Các kỹ thuật tối ưu hóa toàn cầu cố gắng giải quyết các loại vấn đề này.

Thuật toán tiến hóa tạo thành một lớp kỹ thuật global optimization. Kỹ thuật tối ưu hóa toàn cầu thường liên quan đến một số loại "leo đồi" (chấp nhận một cấu hình với chức năng tập thể dục cao hơn (tồi tệ hơn)). Leo đồi này thường liên quan đến một số ngẫu nhiên/stochastic-ness/monte-carlo-ness. Nói chung, các kỹ thuật này có nhiều khả năng chấp nhận cấu hình tối ưu ít hơn sớm và, khi tiến trình tối ưu hóa, chúng ít có khả năng chấp nhận cấu hình kém hơn.

Thuật toán tiến hóa dựa trên các tương tự tiến hóa một cách lỏng lẻo. Mô phỏng ủ được dựa trên các chất tương tự để ủ kim loại. Kỹ thuật tạo hạt cũng được lấy cảm hứng từ các hệ thống sinh học. Trong mọi trường hợp, bạn nên so sánh kết quả với việc lấy mẫu các cấu hình ngẫu nhiên đơn giản (a.k.a. "monte carlo") ... điều này thường mang lại kết quả tương đương.

Lời khuyên của tôi là bắt đầu sử dụng kỹ thuật dựa trên gradient xác định vì chúng thường yêu cầu đánh giá chức năng ít hơn nhiều so với kỹ thuật stochastic/monte-carlo. Khi bạn nghe thấy bước móng ngựa nghĩ ngựa không phải ngựa vằn. Chạy tối ưu hóa từ một số điểm bắt đầu khác nhau và, trừ khi bạn đang đối phó với một vấn đề đặc biệt khó chịu, bạn nên kết thúc với mức tối thiểu gần như nhau. Nếu không, sau đó bạn có thể có ngựa vằn và nên xem xét sử dụng một phương pháp tối ưu hóa toàn cầu.

Answer 2

Tôi nghĩ rằng phương pháp Monte Carlo là tên chung cho các phương pháp này, trong đó sử dụng số ngẫu nhiên để giải quyết các vấn đề tối ưu hóa. Bằng cách này, ngay cả các thuật toán tiến hóa là một loại phương pháp Monte Carlo nếu chúng sử dụng các số ngẫu nhiên (và trên thực tế chúng làm).

phương pháp Monte Carlo khác bao gồm: đô thị, wang-landau, ủ song song, vv

OTOH, phương pháp tiến hóa sử dụng 'kỹ thuật' mượn từ thiên nhiên như đột biến, cross-over vv