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á.
Nội dung trích xuất từ tài liệu:
Một số kỹ thuật điều chỉnh tham số trong giải thuật di truyền 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á thể khi sinh ra được gắn với độ tuổi (age) và thời gian sống (lifetime), sau mỗi bước tạo sinh, độ tuổi này được tăng lên và khi đến ngưỡng thì cá thể đó sẽ bị đào thải [1]. APGA (Genetic Algorithm Adaptive Population Size) được giới thiệu bởi Back, Eiben và van de Vaart năm 2000. Thuật toán này cũng sử dụng độ tuổi của cá thể song việc chọn lọc tạo sinh duy trì phần tử ưu tú. Cơ chế đánh giá thời gian sống (lifetime) của cá thể mềm dẻo hơn bởi việc đánh giá thời gian duy trì cá thể (RLT – Remaining LifeTime) và chiến lược chọn lọc tạo sinh có tính tinh hoa [1], [2]. 2.Thay đổi kích cỡ quần thể dựa trên độ thích nghi trung bình Chúng tôi đề xuất một kỹ thuật biến đổi kích cỡ quần thể ngay trong quá trình tiến hoá dựa trên độ thích nghi trung bình của quần thể. Với kỹ thuật này ta sử dụng thêm một tham số là độ thích nghi trung bình của quần thể. Độ thích nghi trung bình của quần thể được tính theo công thức sau: PopulationSize AverageFitness i 1 eval vi popsize trong đó PopulationSize là kích cỡ quần thể, vi là các cá thể trong quần thể tại thế hệ hiện tại, hàm eval là hàm lượng giá. Thuật toán cụ thể như sau: procedure BaseOnAverageFitness{ Khởi tạo quần thể; startpopsize=popsize; Tính độ thích nghi của các cá thể eval (vi); Tính AverageFitness; While (chưa thỏa điều kiện dừng) do Begin Lựa chọn ngẫu nhiên 2 cá thể P1 và P2 trong quần thể ; 1 Tạp chí KHOA HỌC & CÔNG NGHỆ 52(4): 64 - 68 Lai ghép (P1, P2) được 2 con là C1 và C2; Đột biến (C1, C2); If (độ thích nghi của P1 và P2 < AverageFitness) then Đào thải P1 và P2 ra khỏi quần thể; If (độ thích nghi của C1 và C2 > AverageFitness) then Bổ sung C1 và C2 vào quần thể; If (popsize =2* startpopsize) then Tạo sinh lại quần thể; Tính lại AverageFitness của quần thể mới; End; End; Các mô hình thử nghiệm Chúng tôi sử dụng 6 hàm sau đây để tiến hành thử nghiệm [6]. Các hàm thử nghiệm đều được xét với số chiều n = 30; miền S được giới hạn cho mỗi biến xi và cho trong bảng. Giá trị fmin là giá trị đúng tính trên miền xác định tương ứng với mỗi hàm. Trong thử nghiệm, chúng tôi sử dụng giải thuật di truyền mã hóa số thực (RCGA), với kích cỡ quần thể ban đầu là popsize=50, không gian tìm kiếm có số chiều là n=30, xác suất lai ghép pc=1, xác suất đột biến pm=0.01, và số lần lặp là 2000 lần. Để tiện so sánh, chỉ một toán tử lai ghép được sử dụng, đó là toán tử lai ghép số học – toán tử có độ ổn định cao và khả năng hội tụ tương đối tốt [1], [5], [6]. Khi thực hiện chương trình, chỉ có một cá thể con được đột biến theo xác suất đột biến pm, tỉ lệ hai con C1 và C2 được chọn để đột biến là như nhau. Sau đây giới thiệu 3 mô hình tạo sinh quần thể khi kích cỡ quần thể đạt đến giới hạn cho phép. 4 - 2009 Tính độ thích nghi của C1 và C2; Mô hình 1 Bước 1: Sắp xếp các cá thể trong quần thể hiện tại giảm dần theo độ thích nghi Bước 2: Đưa popsize-1 cá thể có độ thích nghi cao nhất trong quần thể cũ vào quần thể mới Bước 3: Đưa ngẫu nhiên 1 cá thể trong số các cá thể còn lại của quần thể cũ vào quần thể mới. Như vậy quần thể mới sẽ bao gồm gần như tuyệt đối các cá thể có độ thích nghi cao nhất sau một quá trình tiến hóa xác định. Hình 1: Đồ thị kích cỡ quần thể mô hình 1 Mô hình 2 Bước 1: Sắp xếp các cá thể trong quần thể hiện tại giảm dần theo độ thích nghi Bước 2: Đưa popsize/2 cá thể có độ thích nghi cao nhất trong quần thể cũ vào quần thể mới Bước 3: Tiếp tục đưa popsize - popsize/2 cá thể có độ thích nghi thấp nhất trong quần thể cũ vào quần thể mới. Trong trường hợp này, quần thể mới không bao gồm hầu hết các cá thể tốt nhất của quần thể cũ nhưng tính đa dạng trong quần thể lại được đảm bảo hơn. Bảng 1. Các hàm thử nghiệm Hàm thử nghiệm n S fmin 30 [-100, 100] 0 30 [-100, 100] 0 30 [-10, 10] 0 30 [-30, 30] 0 30 [-500, 500] -12569 n xi2 f1 i 1 n f2 0.5 ) 2 ( xi i 1 n n f3 | xi | i 1 | xi | i 1 n 1 f4 (100( xi 1 xi2 ) 2 ( xi i 1 1) 2 ) n f ...