tailieunhanh - Một số kỹ thuật điều chỉnh tham số trong giải thuật di truyền

Giải thuật di truyền với các toán tử chọn lọc, lai ghép, đột biến là giải thuật tìm kiếm lời giải của bài toán mô phỏng quá trình tiến hoá tự nhiên. Bài báo này nghiên cứu và đề xuất một số kỹ thuật hiệu chỉnh tham số của giải thuật ngay trong quá trình tiến hoá. | 52(4): 69 - 71 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 MỘT SỐ KỸ THUẬT ĐIỀU CHỈNH THAM SỐ TRONG GIẢI THUẬT DI TRUYỀN Vũ Mạnh Xuân (Trường ĐH Sư phạm – ĐH Thái Nguyên), Lê Quang Hùng, Lê Thị Thuỷ (Khoa Công nghệ thông tin – ĐH Thái Nguyên) Tóm tắt. Giải thuật di truyền với các toán tử chọn lọc, lai ghép, đột biến là giải thuật tìm kiếm lời giải của bài toán mô phỏng quá trình tiến hoá tự nhiên. Bài báo này nghiên cứu và đề xuất một số kỹ thuật hiệu chỉnh tham số của giải thuật ngay trong quá trình tiến hoá. Mở đầu Giải thuật di truyền (GA - Genetic Algorithm) thực hiện việc tìm kiếm lời giải dựa trên sự mô phỏng quá trình tiến hoá của tự nhiên. GA sử dụng các toán tử chọn lọc (Selection), lai ghép (Crossover), đột biến (Mutation) và các tham số khác như kích cỡ quần thể, xác suất lai ghép, xác suất đột biến. Tự thích nghi là một đặc tính quan trọng của tự nhiên và lẽ tất nhiên cũng được sớm quan tâm trong giải thuật di truyền. Điều chỉnh các tham số của giải thuật ngay trong quá trình tiến hoá là một trong những vấn đề được chú ý và phát triển. Kích cỡ quần thể (Population Size) là tham số đầu tiên cần chú ý, nếu kích cỡ quần thể quá nhỏ thì tính đa dạng của quần thể bị hạn chế; còn nếu quá lớn sẽ hao phí tài nguyên của máy tính và làm chậm quá trình. Trong hầu hết các nghiên cứu về GA người tathường chọn kích cỡ là một số cố định trong suốt quá trình thực hiện. Gần đây, giải thuật di truyền mã hoá số thực RCGA (Real-Coded Genetic Algorithm) phát triển mạnh và một số giải pháp biến đổi kích cỡ quần thể được giới thiệu [1], [2], với cách tiếp cận chủ yếu dựa trên cơ chế định tuổi của cá thể. Bài báo này đề xuất một vài kỹ thuật điều chỉnh kích cỡ quần thể trong quá trình thực hiện giải thuật dựa trên độ thích nghi trung bình của quần thể. 1. Một số kết quả liên quan GAVaPS (Genetic Algorithm with Varying Population Size) được giới thiệu bởi Arabas, Michalewicz và Mulawka năm 1994. Thuật toán này biến đổi kích cỡ quần thể dựa trên độ tuổi của cá thể. Cụ thể là cá .