tailieunhanh - Phân tích tính hội tụ của thuật toán di truyền lai mới

Bài báo này phân tích các thuộc tính hội tụ của NHGA bằng cách áp dụng các tính chất của xích Markov. Trên cơ sở phân tích xích Markov của thuật toán di truyền, chúng tôi đã chứng minh tính hội tụ tới tối ưu toàn cục của phương pháp mã hóa số tự nhiên. | Tạp chí Tin học và Điều khiển học, , (2013), 165–172 PHÂN TÍCH TÍNH HỘI TỤ CỦA THUẬT TOÁN DI TRUYỀN LAI MỚI LỤC TRÍ TUYÊN1 , NGUYỄN HỮU MÙI2 , VŨ ĐÌNH HÒA2 1 Viện Công nghệ Thông tin, Viện Hàn Lâm Khoa học và Công nghệ Việt Nam 2 Khoa Công nghệ Thông tin, Đại học Sư phạm Hà nội Tóm t t. Trong một bài báo gần đây, chúng tôi đã trình bày một thuật toán di truyền lai mới (NHGA) cho bài toán lập lịch Job Shop (JSP). Phương pháp mã hóa chúng tôi sử dụng là mã hóa số tự nhiên thay cho mã hóa nhị phân. Cách mã hóa này có nhiều ưu điểm, nhưng vấn đề hội tụ của nó vẫn còn là vấn đề mở trong nhiều năm nay. Bài báo này phân tích các thuộc tính hội tụ của NHGA bằng cách áp dụng các tính chất của xích Markov. Trên cơ sở phân tích xích Markov của thuật toán di truyền, chúng tôi đã chứng minh tính hội tụ tới tối ưu toàn cục của phương pháp mã hóa số tự nhiên. T khóa. Lập lịch, giải thuật di truyền, hội tụ toàn cục, xích Markov. Abstract. In this paper, we propose a new hybrid genetic algorithm (NHGA) for the job shop scheduling problem (JSP). The method of encoding we used was Natural coding instead of traditional binary coding. This manner of coding has a lot of advantages but its convergence has been still an open issue so far. This paper analyzes the convergence properties of the NHGA by applying the properties of Markov chain. Based on Markov chain analysis of the genetic algorithm, we show that the proposed algorithm converges to the global optimum in term of Natural coding. Key words. Job shop scheduling, genetic algorithm, global convergence, Markov chain. 1. GIỚI THIỆU Thuật toán di truyền (GA) phỏng theo các quá trình tiến hoá tự thích nghi của các quần thể sinh học để tối ưu hoá các hàm mục tiêu. Thuật toán này được phát triển bởi John Holland [5], GA được đặc trưng bởi các chiến lược tìm kiếm dựa trên quần thể và các toán tử di truyền: chọn lọc, đột biến và trao đổi chéo. Nakano và Yamada [11] nằm trong số những người đầu tiên đã áp dụng GA cổ điển .