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 1 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: popsize veval nessAverageFit i i SizePopulation 1 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ể ; 52(4): 64 - 68 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 2 Lai ghép (P1, P2) được 2 con là C1 và C2; Đột biến (C1, C2); Tính độ thích nghi của C1 và 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. 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 n i ixf 1 2 1 30 [-100, 100] 0 n i ixf 1 2 2 )5.0( 30 [-100, 100] 0 n i n i ii xxf 1 1 3 |||| 30 [-10, 10] 0 1 1 222 14 ))1()(100( n i iii xxxf 30 [-30, 30] 0 n i ii xxf 1 5 )||sin( 30 [-500, 500] -12569 52(4): 64 - 68 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 66 n i ii xxf 1 2 6 )10)2cos(10( 30 [-5, 5] 0 Hình 2: Đồ thị kích cỡ quần thể mô hình 2 Mô hình 3 Bước 1: Xét ngẫu nhiên 2 cá thể trong trong quần thể hiện tại, cá thể nào có độ thích nghi cao hơn sẽ được đưa vào quần thể mới. Bước 2: Loại bỏ 2 cá thể đã được xét ra khỏi quần thể hiện tại. Bước 3: Quay lại bước 1 cho đến khi các cặp cá thể đều được xem xét. Với mô hình này, tính cạnh tranh, đấu tranh sinh tồn giữa các cá thể trong quần thể được thể hiện rõ nhất. Cá thể nào có độ thích nghi tốt hơn trong cặp cá thể được chọn có cơ hội sống sót đến thế hệ sau. Tính đa dạng của quần thể cũng được được đảm bảo. Hình 3: Đồ thị kích cỡ quần thể mô hình 3 Kết quả thử nghiệm Tại mỗi lần chạy, cá thể có độ thích nghi cao nhất (giá trị hàm mục tiêu nhỏ nhất) được ghi nhận lại. Sau 20 lần chạy độc lập trên cùng một cấu hình máy tính, giá trị tốt nhất tìm được, trung bình cộng, cũng như thời gian chạy trung bình của các lần chạy này được tính và trình bày trong các bảng số liệu kết xuất dưới đây. Bảng 2 trình bày kết quả thử nghiệm sau 20 lần chạy độc lập. Với mỗi hàm, chương trình thử nghiệm theo cả ba mô hình đề xuất trên, giá trị trung bình của cá thể tốt nhất tìm được sau mỗi lần chạy được ghi trong cột tương ứng. Dưới đây là hình minh hoạ độ biến đổi của đồ thị giá trị của các hàm tương ứng với các mô hình đã đề xuất trên Hình 4: Đồ thị giá trị hàm f1 Hình 5: Đồ thị giá trị hàm f2 Bảng 2: Kết quả thử nghiệm thuật toán biến đổi kích cỡ quần thể dựa trên độ thích nghi trung bình Hàm thử nghiệm Kích cỡ cố định Mô hình 1 Mô hình 2 Mô hình 3 f1 361.7346 638.9141 535.2382 649.8801 f2 431.1500 651.5500 562.7500 604.5500 f3 4.8268 6.1828 11.7998 7.2641 f4 36424.8180 50776.1510 31100.1967 39853.0663 f5 -2674.3462 -2874.3432 -2541.4488 -2770.4161 Kết quả hội tụ - Hàm f1 0.0000 200.0000 400.0000 600.0000 800.0000 1000.0000 1200.0000 1400.0000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Lần chạy G iá t r ị h à m Cố định Mô hình 1 Mô hình 2 Mô hình 3 Kết quả hội tụ - Hàm f2 0.0000 200.0000 400.0000 600.0000 800.0000 1000.0000 1200.0000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Lần chạy G iá t r ị h à m Cố định Mô hình 1 Mô hình 2 Mô hình 3 52(4): 64 - 68 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 67 f6 100.5761 83.2940 104.5281 85.0702 Hình 6: Đồ thị giá trị hàm f3 Hình 7: Đồ thị giá trị hàm f4 Hình 8. Đồ thị giá trị hàm f5 Hình 9. Đồ thị giá trị hàm f6 Chúng tôi đưa vào kết quả chạy bởi thuật toán có kích cỡ quần thể cố định để so sánh. Dựa vào bảng dữ liệu kết xuất cũng như đồ thị kết quả trên ta có thể rút ra một số nhận xét như sau: Đối với các hàm f1, f2, và f3, các mô hình thay đổi kích cỡ quần thể đã đề xuất đều cho kết quả trung bình, cũng như kết quả tốt nhất giữa các lần thử nghiệm không tốt bằng kết quả của mô hình kích cỡ quần thể cố định. Đồng thời độ ổn định của các giải thuật là như nhau (độ lệch giữa kết quả tốt nhất và kết quả trung bình). Thời gian chạy giữa các giải thuật cũng là tương đương nhau (độ chênh lệch là không đáng kể). Các hàm f4, f5 và f6 có rất nhiều cực trị địa phương, khi đó kết quả của việc biến đổi kích cỡ quần thể đều cho kết quả tốt hơn thuật toán với kích cỡ quần thể cố định. 3) Thay đổi kích cỡ quần thể dựa trên số lần lặp Với kỹ thuật này chúng tôi cũng sử dụng tham số độ thích nghi trung bình của quần thể, nhưng điểm khác biệt của thuật toán này như sau: Trong repTime thế hệ đầu tiên ta để kích cỡ quần thể thay đổi theo cách như trên. (repTime là một số nguyên bất kỳ nằm trong khoảng (0..số lần lặp)). Trong repTime thế hệ tiếp theo kích cỡ quần thể lại được giữ cố định như giải thuật di truyền thông thường. Lặp lại quá trình trên cho đến khi thỏa điều kiện thì dừng thuật toán. Thuật toán cụ thể như sau: procedure BaseOnRepeatTime Begin Khởi tạo quần thể; Tính độ thích nghi của các cá thể: eval (vi); Tính độ thích nghi trung bình của quần thể AverageFitness; raise=true; i=0; While (i<RepeatTime) do Begin i=i+1 if (i mod repTime=0) if (raise) then Chọn PopulationSize cá thể có độ thích nghi tốt nhất đưa vào quần thể mới; raise=false; else raise=true; Lựa chọn ngẫu nhiên 2 cá thể P1 và P2 trong quần thể ; Lai ghép (P1, P2) được 2 con là C1 và C2; Đột biến (C1, C2); Tính độ thích nghi của C1 và C2; if (raise) then if (độ thích nghi của P1 và P2 < AverageFitness) then Loạ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ể; else Kết quả hội tụ - Hàm f3 0.0000 5.0000 10.0000 15.0000 20.0000 25.0000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Lần chạy G iá t r ị h à m Cố định Mô hình 1 Mô hình 2 Mô hình 3 Đồ thị hội tụ - Hàm f4 0.0000 20000.0000 40000.0000 60000.0000 80000.0000 100000.0000 120000.0000 140000.0000 160000.0000 180000.0000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Lần chạy G iá t r ị h à m Cố định Mô hình 1 Mô hình 2 Mô hình 3 Đồ thị hội tụ - Hàm f5 -4000.0000 -3500.0000 -3000.0000 -2500.0000 -2000.0000 -1500.0000 -1000.0000 -500.0000 0.0000 1 3 5 7 9 11 13 15 17 19 Lần chạy G iá t r ị h à m Cố định Mô hình 1 Mô hình 2 Mô hình 2 Đồ thị hội tụ - Hàm f6 0.0000 20.0000 40.0000 60.0000 80.0000 100.0000 120.0000 140.0000 160.0000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Lần chạy G iá t r ị h à m Cố định Mô hình 1 Mô hình 2 Mô hình 3 52(4): 64 - 68 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 68 Loại P1 và P2 ra khỏi quần thể; Bổ sung C1 và C2 vào quần thể; End End Hình 10: Đồ thị kích cỡ quần thể Các tham số thực nghiệm Thuật toán trên 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, số lần lặp là 2000 lần, thuật toán sử dụng toán tử lai ghép số học. Biến raise được sử dụng để xác định trong giai đoạn hiện tại, kích cỡ quần thể là cố định hay thay đổi, repTime=50. Thử nghiệm được tiến hành với 6 hàm BenchMark đã được trình bày ở trên. Kết quả thử nghiệm được cho trong bảng 3. Các cột 2 và 3 cho giá trị hàm mục tiêu của cá thể tốt nhất tìm được sau 20 lần chạy. Các cột 4 và 5 cho giá trị trung bình của cá thể tốt nhất trong 20 lần chạy. Nhận xét: Tương tự như kỹ thuật biến đổi kích cỡ quần thể dựa trên độ thích nghi trung bình, kỹ thuật này chỉ cho kết quả tốt hơn thuật toán với kích cỡ quần thể cố định đối với hàm có nhiều cực trị địa phương. IV. Thảo luận và kết luận Nhìn vào những kết quả trên, ta thấy các mô hình đưa ra chưa hoàn toàn cho kết quả tốt với tất cả các hàm thử nghiệm mà chỉ cho kết quả tốt với các hàm đa cực trị. Tuy nhiên những kết quả đó chỉ là những nghiên cứu ban đầu về giải thuật di truyền với kích cỡ quần thể thay đổi, chỉ sử dụng một loại toán tử lai ghép. Những mô hình đưa ra cần có thời gian nghiên cứu sâu hơn để có thể cho kết quả tốt hơn, chẳng hạn sử dụng các dạng toán tử lai ghép khác, các dạng toán tử chọn lọc khác, cũng như việc lựa chọn các tham số đầu vào phù hợp hơn. Bảng 3. Kết quả thử nghiệm khi thay đổi kích cỡ quần thể dựa trên số lần lặp Hàm thử nghiệm Giá trị tốt nhất Giá trị trung bình Kích cỡ cố định Kích cỡ biến đổi Kích cỡ cố định Kích cỡ biến đổi f1 155.6121 252.4066 361.7346 457.6235 f2 208.0000 226.0000 431.1500 452.2500 f3 2.3487 2.7201 4.8268 5.7816 f4 11605.4258 9812.4921 36424.8180 25168.4229 f5 -3235.2783 -4054.1986 -2674.3462 -3332.0388 f6 62.4577 53.9499 100.5761 84.8775 Tài liệu tham khảo [1] A.E. Eiben, E. Marchiori, V.A. Valkó, Evolutionary Algorithms with on-the-fly Population Size Adjustmen, Parallel Problem Solving from Nature PPSN VI, LNCS 1917, Springer, 2004. [2] Fernando G. Lobo, Claudio F. Lima, Revisiting Evolutionary Algorithms with on-the-fly Population Size Adjustmen, UALG-ILAB Technical Report N.200602, 2006. [3] Ulrich Bodemhofer, Generic Algorithms: Theory and Application, Lecture Notes, 2004 [4] Nguyễn Hoàng Phương, Nadipuram R.Prasad, Lê Linh Phong, Nhập môn trí tuệ tính toán, NXB KH&KT, 2002. [5] Nguyễn Đình Thúc, Lập trình tiến hoá, NXBGD, 2001. [6] Vũ Mạnh Xuân, Nguyễn Thanh Thủy, Biểu diễn toán tử lai ghép trong giải thuật di truyền mã hóa số thực, Tạp chí Khoa Học & Công Nghệ, ĐHTN. 52(4): 3 - 12 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 69 Summary Genetic algorithm with selection, crossover, mutation operators is used to found the solution of the natural evolutionary simulation problems. This paper studies and proposes several techniques in order to adjust parameters in the evolutionaryprocess. Keyword: Genetic algorithm, population size, crossover.