Nghiên cứu phương pháp cải tiến chiến lược chọn lọc tự nhiên trong giải thuật SEAMO2 để giải các bài toán tối ưu đa mục tiêu

Bài viết Nghiên cứu phương pháp cải tiến chiến lược chọn lọc tự nhiên trong giải thuật SEAMO2 để giải các bài toán tối ưu đa mục tiêu tập trung nghiên cứu, phân tích đánh giá một số trường hợp xảy ra trong chiến lược chọn lọc và thay thế cá thể vào quần thể của giải thuật SEAMO2 để tìm phương pháp cải tiến giải thuật để giải bài toán cái túi đa mục tiêu.
Nội dung trích xuất từ tài liệu:
Nghiên cứu phương pháp cải tiến chiến lược chọn lọc tự nhiên trong giải thuật SEAMO2 để giải các bài toán tối ưu đa mục tiêu TNU Journal of Science and Technology 227(11): 196 - 205 STUDY ON NATURAL FILTER SELECTION STRATEGY IMPROVEMENT METHOD IN SEAMO2 TO SOLVE OPTIMIZATION MAXIMUM OBJECTIVES PROBLEMS Tran Hai Thanh*, Le Hoang Hiep, Doan Ngoc Phuong TNU - University of Information and Communication Technology ARTICLE INFO ABSTRACT Received: 17/9/2020 The paper focuses on studying, analyzing and evaluating some cases occurring in the strategy of selecting and replacing individuals in the Revised: 26/8/2022 population of the SEAMO2 algorithm to find solutions to improve the Published: 26/8/2022 algorithm to solve the multi-objective bag problem. By using the substitution of the random selection in the algorithm's substitution KEYWORDS strategy is the worst (most substitution) instance in a limited space of instances. In comparison with the old method performed before, the new Computer science improvement of SEAMO2_LG shows that in the first generations of the The problem of multi-purpose population (or when running the algorithm with short runs), then finding bag suitable individuals to replace will help the population converge to the Pareto boundary faster or when running with long runs (large number of Individual generations), in the last generations (when the population has reached the Random optimal threshold), the restriction of search space will save time. Population NGHIÊN CỨU PHƢƠNG PHÁP CẢI TIẾN CHIẾN LƢỢC CHỌN LỌC TỰ NHIÊN TRONG GIẢI THUẬT SEAMO2 ĐỂ GIẢI CÁC BÀI TOÁN TỐI ƢU ĐA MỤC TIÊU Trần Hải Thanh*, Lê Hoàng Hiệp, Đoàn Ngọc Phƣơng Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên THÔNG TIN BÀI BÁO TÓM TẮT Ngày nhận bài: 17/9/2020 Bài báo tập trung nghiên cứu, phân tích đánh giá một số trường hợp xảy ra trong chiến lược chọn lọc và thay thế cá thể vào quần thể của giải Ngày hoàn thiện: 26/8/2022 thuật SEAMO2 để tìm phương pháp cải tiến giải thuật để giải bài toán Ngày đăng: 26/8/2022 cái túi đa mục tiêu. Thông qua việc sử dụng, thay thế trường hợp lựa chọn ngẫu nhiên trong chiến lược chọn cá thể thay thế của giải thuật đó TỪ KHÓA là lựa chọn cá thể xấu nhất (đáng thay thế nhất) trong một khoảng không gian giới hạn các cá thể. Kết quả thực nghiệm so với phương Khoa học máy tính pháp cũ được thực hiện trước đó, cải tiến mới SEAMO2_LG cho thấy Bài toán cái túi đa mục tiêu trong các thế hệ đầu của quần thể (hoặc khi chạy giải thuật với các lần Cá thể chạy ngắn) thì việc tìm cá thể phù hợp để thay thế sẽ giúp cho quần thể hội tụ về biên Pareto nhanh hơn hoặc khi chạy với các lần chạy dài (số Ngẫu nhiên thế hệ lớn) thì ở các thế hệ cuối (khi quần thể đã đạt ngưỡng tối ưu) thì Quần thể việc hạn chế không gian tìm kiếm sẽ giúp tiết kiệm thời gian. DOI: https://doi.org/10.34238/tnu-jst.3617 * Corresponding author. Email: ththanh@ictu.edu.vn http://jst.tnu.edu.vn 196 Email: jst@tnu.edu.vn TNU Journal of Science and Technology 227(11): 196 - 205 1. Giới thiệu Trên thực tế, tồn tại rất nhiều bài toán yêu cầu tối ưu hóa đồng thời nhiều mục tiêu (thường là cạnh tranh lẫn nhau) ví dụ như: định tuyến các phương tiện giao thông để xác định các tuyến đường tối ưu nhằm cung cấp dịch vụ cho một tập hợp các khách hàng có thể liên quan đến một số mục tiêu khác nhau: tổng quãng đường đi (hoặc thời gian thực hiện), lượng xe sử dụng, độ hài lòng của khách hàng (giao hàng trong khoảng thời gian đã thỏa thuận trước),… hay việc đi chợ mua thức ăn cần đảm bảo sao cho đủ lượng calo cần thiết, chất lượng bữa ăn đảm bảo, số tiền chi tiêu không vượt quá giới hạn,… Giải thuật di truyền (GA - Genetic Algorithm) là một trong những mô hình tính toán phổ biến và thành công nhất trong lĩnh vực tính toán thông minh [1] – [3]. Cùng với các kỹ thuật tính toán thông minh khác như tính toán mờ (fuzzy computing), mạng Nơ-ron (Neural Networks), hệ đa tác tử (Multi- agent systems), trí tuệ bầy đàn (Swarm intelligence), giải thuật di truyền ngày càng phát triển, được áp dụng rộng rãi trong các lĩnh vực của cuộc sống [4] – [7]. Đối với bài toán đa mục tiêu, đã có nhiều phương pháp nghiên cứu đề xuất ra các thuật toán để giải quyết bài toán như: MOGA, NSGA2, SPEA2, SEAMO2,… [8] – [11] trong đó giải thuật SEAMO2 là hiệu quả hơn cả. Với giải thuật SEAMO2, việc thay thế cá thể vào quần thể (thực hiện chiến lược chọn lọc tự nhiên) thì độ hội tụ về tập nghiệm tối ưu (với lần chạy ngắn) là chưa cao và khi quần thể nghiệm đã đạt ngưỡng tối ưu (với lần chạy dài) thì sẽ mất nhiều thời gian để loại cá thể không phù hợp. Chính vì vậy, nhóm tác giả mạnh dạn nghiên cứu phương pháp cải tiến chiến lược chọn lọc tự nhiên trong giải thuật SEAMO2 để giải các bài toán tối ưu đa mục tiêu trong nghiên cứu này. Mục tiêu của bài báo là: - Nghiên cứu các toán tử trong giải thuật di truyền (hay giải thuật tiến hóa nói chung) đặc biệt là toán tử chọn lọc tự nhiên để chọn lọc và thay thế các lời giải nhằm tối ưu tập lời giải thu được giúp cho giải thuật di truyền giải quyết hiệu quả các bài ...