Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân tích chuỗi Markov của bài toán Leading Ones
Tóm tắt
Các thuật toán tiến hóa (EAs) là những kỹ thuật tìm kiếm tối ưu ngẫu nhiên, và việc nghiên cứu lý thuyết về thời gian đạt được lần đầu tiên là rất quan trọng trong các ứng dụng thực tiễn của EA. Chúng tôi điều tra thời gian đạt được lần đầu tiên của bài toán Leading Ones (LO) một cách lý thuyết trên thuật toán Tìm kiếm Địa phương Ngẫu nhiên (RLS) và (1 + 1)EA bằng cách sử dụng chuỗi Markov hấp thụ. Bài báo này báo cáo phương pháp tính toán thời gian đạt được lần đầu trên bài toán LO với (1 + 1)EA và RLS. Chúng tôi phát hiện ra rằng kết quả chỉ phụ thuộc vào độ dài của chuỗi, và số lần đạt được có thể được cho khoảng bằng hàm bậc hai. Trong các thí nghiệm số, chúng tôi đã chỉ ra sự đồng nhất giữa các kết quả tính toán thực tiễn và các kết quả lý thuyết. Kết quả của chúng tôi đưa ra ví dụ tốt để dự đoán thời gian chạy của các tính toán EA thực tiễn bằng phương pháp chuỗi Markov.
Từ khóa
#thuật toán tiến hóa #thời gian đạt được lần đầu tiên #bài toán Leading Ones #tìm kiếm địa phương ngẫu nhiên #chuỗi Markov hấp thụTài liệu tham khảo
Auger A, Doerr B (2011) Theory of randomized search heuristics. World Scientific, Singapore
Wegener I (2001) Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In: Sarker R, Mohammadian M, Yao X (eds) Evolutionary optimization. Kluwer Academic Pubishers, Dordrecht, pp 349–369
Iosifescu M (1980) Finite Markov chain processes and their applications. Wiley, New York
Levin DA, Peres Y, Wilmer EL (2008) Markov chains and mixing times. American Mathematical Society, Providence
Furutani H, Tagami H, Sakamoto M, Du Y (2014) Markov chain analyses of random local search and evolutionary algorithm. J Robot Netw Artif Life 1(3):220–224
Furutani H, Sakamoto M, Du Y, Aoki K (2015) Analysis of asymmetric mutation model in random local search. J Robot Netw Artif Life 2(1):1–4
Du Y, Aoki K, Sakamoto M, Yamamori K, Furutani H (2016) Asymmetric mutation model in genetic algorithm. Artif Life Robot 22:17–23
Jansen T, Sudholt D (2010) Analysis of an asymmetric mutation operator. Evolut Comput 18(1):1–26
Doerr B, Hebbinghaus N, Neumann F (2007) Speeding up evolutionary algorithms through asymmetric mutation operators. Evolut Comput 15(4):401–410
Droste S, Jansen T, Wegener I (2002) On the analysis of the (1 + 1) evolutionary algorithm. Theor Comput Sci 276:51–81
Du Y, Ma Q, Zhang Y, Sakamoto M, Furutani H (2014) Runtime analysis of OneMax problem in genetic algorithm. J Robot Netw Artif Life 1(3):225–230
Du Y, Ma Q, Zhang Y, Aoki K, Sakamoto M, Furutani H (2015) Hitting time analysis of OneMax problem in genetic algorithm. J Robot Netw Artif Life 2(2):131–134