Lập trình di truyền và Phân tích hồi quy

49 Chương 5: Lập trình di truyền và Phân tích hồi quy 5.1. Sơ lược về lập trình di truyền 5.1.1. Thuyết tiến hóa Năm 1859, nhà sinh vật học người Anh Charles Darwin ñã ñề xuất Thuyết tiến hóa ñể lý giải nguồn gốc sự sống của các loài sinh vật trên thế giới. Theo quan ñiểm của Thuyết tiến hóa, sinh vật trên thế giới phát triển dựa trên sự chọn lọc tự nhiên, dần dần thích nghi với môi trường sống. Qua các thế hệ, những cá thể nào thích nghi với môi trường sống sẽ tồn tại và duy trì những ñặc tính của mình cho thế hệ sau, những cá thể kém thích nghi sẽ dần dần bị tuyệt chủng. Với sự phát triển của ngành di truyền học, người ta khám phá ra rằng: tất cả những ñặc tính của một sinh vật ñều ñược lưu giữ trong chất liệu di truyền của sinh vật. ðó chính là gen. Trong quá trình sinh sản của sinh vật, gen của hai cá thể lai ghép với nhau ñể tạo ra gen của cá thể thế hệ sau. Gen này làm cho cá thể có những ñặc tính hỗn hợp của thế hệ trước. Cũng có khi trong quá trình phát triển của sinh vật, một ñoạn nào ñó trên gen do tác ñộng của môi trường sống bị ñột biến, làm xuất hiện ñặc tính mới nơi cá thể, và ñặc tính này ñược truyền lại cho các thế hệ sau. Như vậy, từ một vài cá thể nguyên thủy ban ñầu, trải qua hàng trăm triệu năm tiến hóa, với sự tác ñộng của chọn lọc tự nhiên, cùng với các quá trình lai ghép, ñột biến giữa các cá thể sinh sống trong quần thể sinh vật qua các thế hệ, ñã giúp hình thành nên các loài sinh vật ña dạng phong phú, thích nghi tốt với môi trường sống như ngày nay. 50 5.1.2. Giải thuật di truyền [17] Lấy ý tưởng từ Thuyết tiến hóa của Charles Darwin, John Holland ñã phát triển một kỹ thuật trí tuệ nhân tạo ñể giúp tìm ra lời giải gần ñúng cho một bài toán. Kỹ thuật này ñược gọi là giải thuật di truyền [17]. Trong giải thuật di truyền, bài toán cần giải quyết chính là môi trường sống. Những lời giải “ứng cử viên” của bài toán là các cá thể trong quần thể. Thông qua các phép toán chọn lọc, lai ghép, ñột biến và ñặc biệt là một hàm thích nghi dùng ñể tính toán ñộ thích nghi của từng cá thể, quẩn thể lời giải sẽ tiến hóa qua các thế hệ và dần dần cho ra những lời giải chính xác hơn cho bài toán ban ñầu. Tư tưởng chính của giải thuật di truyền ñược trình bày trong bảng 5.1. Bảng 5.1. Giải thuật di truyền của John Holland. - Bước 1: initialize(Q0), // khởi tạo quần thể ban ñầu - Bước 2: e = evaluate(Q0), i = 0 // ñánh giá quần thể ban ñầu - Bước 3: Lặp khi e chưa ñạt lời giải ưng ý * Bước 3.1: Qi+1 = select(Qi) // tạo quần thể thế hệ kế tiếp bằng // cách chọn lọc cá thể từ quần thể cũ * Bước 3.2: alter(Qi+1) // thay ñổi quần thể mới bằng cách // lai ghép, ñột biến trên các cá thể * Bước 3.3: e = evaluate(Qi+1) // ñánh giá quần thể mới * Bước 3.4 : i = i + 1 5.1.3. Lập trình di truyền [17] Chương trình máy tính ñược tạo ra ñể giúp con người giải quyết một vấn ñề nào ñó. Nó là cách thức giải quyết vấn ñề ñược trình bày ở dạng sao cho máy tính có thể hiểu ñược. Công việc trình bày này ñược gọi là lập trình. ðó luôn là một công việc khó, ñòi hỏi nhiều thời gian và công sức của con người. Vì vậy khi phát triển trí tuệ 51 nhân tạo, người ta luôn mong muốn tìm ra phương pháp ñể máy tính có thể tự lập trình. Chương trình bấy giờ không phải do con người viết nữa, mà chính máy tính sẽ làm nhiệm vụ này. Như ñã biết, ý tưởng của giải thuật di truyền là ñể máy tính tự tìm lời giải gần ñúng cho một bài toán. Trong trường hợp bài toán ñược ñặt ra là tìm chương trình ñể giải quyết một vấn ñề, khi ñó lời giải tìm ñược chính là chương trình ñể giải quyết vấn ñề ñó. Tập cá thể chính là những chương trình máy tính làm “ứng cử viên” cho việc giải quyết vấn ñề. Với xuất phát ñiểm ban ñầu là một vài chương trình ngẫu nhiên, cũng thông qua các phép toán chọn lọc, lai ghép, ñột biến và hàm thích nghi, qua một số thế hệ tiến hóa, kết quả thu ñược sẽ là những chương trình ñể giải quyết gần ñúng một vấn ñề nào ñó. Như vậy, giải thuật di truyền hoàn toàn có thể trở thành một công cụ làm cho máy tính có khả năng tự lập trình. Công cụ này do John Koza ñề xuất vào ñầu thập niên 1990 và ñược gọi là lập trình di truyền [17]. ðây có thể nói là một hướng nghiên cứu rất ñược quan tâm hiện nay. ðể hiện thực hóa lập trình di truyền, mỗi cá thể là một chương trình máy tính ñược biểu diễn dưới dạng cây cú pháp có số lượng nút và ñộ sâu khác nhau. Các phép toán lai ghép, ñột biến ñược thực hiện trên các nhánh của cây cú pháp này. Ban ñầu, ý tưởng của lập trình di truyền chỉ gói gọn trong phạm vi lập trình tự ñộng, tìm chương trình máy tính giải quyết bài toán. Nhưng sau một thời gian phát triển, ý tưởng này ñược mở rộng ra cho nhiều lĩnh vực khác có cách biểu diễn cá thể tương tự: dạng cây. Vì vậy, có thể hiểu nôm na: lập trình di truyền chính là giải thuật di truyền với các cá thể trong quần thể ñược biểu diễn dưới dạng cây. 52 5.2. Những thành phần của lập trình di truyền 5.2.1. Cá thể Trong giải thuật di truyền, mỗi cá thể là một lời giải “ứng cử viên” cho bài toán cần giải quyết. Thông thường, mỗi cá thể ñược biểu diễn dưới dạng một chuỗi bit có ñộ dài như nhau. Tùy theo mỗi bài toán sẽ có cách diễn giải chuỗi bit này khác nhau. Việc lai ghép, ñột biến cá thể ñược thực hiện trên chuỗi bit này. Trong khi ñó, ñối với lập trình di truyền, mỗi cá thể ñược biểu diễn dưới dạng cây (gọi là cây cá thể) có số lượng nút và ñộ sâu khác nhau. Tùy theo mỗi bài toán, các nút mang ý nghĩa khác nhau. ðiều này làm tăng khả năng khả năng biểu diễn lời giải cho những loại bài toán khác nhau. Cây cá thể ñược xây dựng dựa trên hai tập: tập toán tử F và tập toán hạng T. - Tập toán tử F (Function): bao gồm những nút không phải là lá của cây cá thể, gọi là nút toán tử. Mỗi nút toán tử có ngôi quy ñịnh số nhánh con của nút trong cây. F = { {Tập toán tử số học: +, -, *, /, …}, {Tập toán tử logic: NOT, AND, OR, …}, {Tập các cấu trúc chương trình: IF-THEN-ELSE, WHILE-DO, …}, {Tập các hàm của chương trình} } Ví dụ tập toán tử F dùng ñể xây dựng cây cú pháp chương trình. Nút toán tử + có hai ngôi, nút toán tử IF-THEN-ELSE có ba ngôi. 53 - Tập toán hạng T (Terminal): bao gồm những nút lá của cây cá thể, gọi là nút toán hạng. Các nút toán hạng không có nhánh con. T = { {Tập các hằng số}, {Tập các ký hiệu} } Ví dụ tập toán hạng T dùng ñể xây dựng cây cú pháp chương trình. Lấy ví dụ một ñoạn chương trình máy tính như sau: if (a < 10) then c = a + b; else c = a – b; Tập toán tử F = {+, -, <, IF-THEN-ELSE }, tập toán hạng T = {a, b, c, số nguyên}. Dựa trên F và T, cây cá thể của ñoạn chương trình này ñược xây dựng như hình 5.1. Hình 5.1. Cây cá thể biểu diễn ñoạn chương trình ñược xây dựng từ tập F và T. 54 5.2.2. Quần thể Quần thể là tập hợp các cá thể. Sau khi ñã biểu diễn lời giải bài toán bằng các cá thể, bước tiếp theo là khởi tạo quần thể ban ñầu làm tiền ñề cho quá trình tiến hóa trên quần thể sau này. Có hai cách thức ñể khởi tạo quần thể ban ñầu: - Khởi tạo bằng thuật toán GROW [17]: mỗi cá thể ñược khởi tạo ngẫu nhiên với các nhánh của cây có ñộ sâu tùy ý nhưng không vượt quá một giới hạn cho trước. Bảng 5.2. Thuật toán GROW khởi tạo quần thể ban ñầu. initialise(node, depth) Nếu (depth = 1) child = selectNode(F). Ngược lại nếu depth = MAX_DEPTH child = selectNode(T). Ngược lại child = selectNode(F U T). Cuối nếu Nếu child là nút toán tử Lặp i từ 1 ñến số ngôi của child initialise(child, depth + 1) Cuối lặp Cuối nếu 55 - Khởi tạo bằng thuật toán FULL [17]: mỗi cá thể ñược khởi tạo ngẫu nhiên với các nhánh của cây có ñộ sâu ñúng bằng một giới hạn cho trước. Bảng 5.3. Thuật toán FULL khởi tạo quần thể ban ñầu. initialise(node, depth) Nếu (depth = 1) child = selectNode(F). Ngược lại nếu depth = MAX_DEPTH child = selectNode(T). Ngược lại child = selectNode(F). Cuối nếu Nếu child là nút toán tử Lặp i từ 1 ñến số ngôi của child initialise(child, depth + 1) Cuối lặp Cuối nếu 5.2.3. Hàm thích nghi Hàm thích nghi dùng ñể tính toán ñộ thích nghi của cá thể, cho phép so sánh ñộ thích nghi của các cá thể trong quần thể với nhau. Tùy theo bài toán, ñộ thích nghi có cách thức tính và thang ño khác nhau. Thông thường, ñộ thích nghi thô (Raw Fitness) của cá thể ñược tính theo công thức 5.1. Theo công thức này, ñộ thích nghi càng nhỏ (tiến về giá trị 0) thì cá thể càng thích nghi với môi trường, tức cho lời giải gần ñúng với bài toán. 56 iii EvaluatedExpectedFitness −= Công thức 5.1. Tính ñộ thích nghi thô của cá thể. Trong ñó: - Fitnessi: ñộ thích nghi của cá thể i trong quần thể. - Expectedi: giá trị mong ñợi (chính xác theo bài toán) của cá thể i trong quần thể. - Evaluatedi: giá trị thật của cá thể i trong quần thể. 5.2.4. Toán tử di truyền 5.2.4.1. Chọn lọc Chọn lọc là toán tử quan trọng nhất của giải thuật di truyền. Trong lập trình di truyền, toán tử chọn lọc tương tự như trong giải thuật di truyền. Sau mỗi thế hệ tiến hóa, toán tử chọn lọc thực hiện việc sàng lọc quần thể. Những cá thể ñược chọn lọc sẽ ñược sao chép lại ñể trở thành cá thể trong quần thể mới. Những cá thể càng thích nghi với môi trường sẽ có cơ hội ñược chọn lọc cao hơn những cá thể kém thích nghi. Toán tử này cho phép giữ lại những cá thể tốt nhưng vẫn không loại bỏ hoàn toàn những cá thể xấu. Những cá thể xấu vẫn có cơ hội, dù thấp, ñể ñược chọn lọc. ðiều này giúp cho quần thể luôn giữ ñược ñộ ña dạng cần thiết, một yếu tố rất quan trọng trong quá trình tiến hóa. Theo quy luật của Thuyết tiến hóa, toán tử chọn lọc làm cho khả năng thích nghi của các cá thể trong quần thể ngày càng tăng lên qua mỗi thế hệ. Theo Koza [17], 10% cá thể thích nghi nhất trong quần thể nên ñược giữ lại qua mỗi thế hệ. Tỷ lệ này có ảnh hướng nhiều ñến tốc ñộ của giải thuật di truyền. Vì việc tính ñộ thích nghi cho các cá thể mất khá nhiều thời gian. Với những cá thể ñược chọn lọc, ñộ thích nghi của chúng không thay ñổi qua các thế hệ. Do ñó, việc tính toán lại ñộ thích nghi cho những cá thể này là không cần thiết. 57 5.2.4.2. Lai ghép Toán tử lai ghép ñược thực hiện trên hai cá thể của quần thể. Hai cá thể này có thể giống hoặc khác nhau. Một nhánh bất kỳ trong mỗi cá thể ñược chọn và hoán ñổi cho nhau ñể hình thành nên hai cá thể mới trong thế hệ kế tiếp. Hai cá thể mới này chính là sự pha trộn ngẫu nhiên giữa hai cá thể ban ñầu ñược chọn ñể thực hiện lai ghép. Ví dụ mô tả quá trình lai ghép hai cá thể biểu diễn cây logic. (NOT D1) OR (D0 AND D1) (D1 OR (NOT D0)) OR ((NOT D0) AND (NOT D1)) Hình 5.2. Hai cá thể trước khi thực hiện lai ghép [17]. ((NOT D0) AND (NOT D1)) OR (D0 AND D1) (D1 OR (NOT D0)) OR (NOT D1) Hình 5.3. Hai cá thể sau khi thực hiện lai ghép [17]. 58 Lai ghép cũng là một toán tử quan trọng trong lập trình di truyền. Theo Thuyết tiến hóa, cá thể con hình thành từ việc lai ghép hai cá thể bố mẹ tốt có tỷ lệ tốt cao hơn so với tỷ lệ xấu. Toán tử này ñược sử dụng phổ biến trong quá trình tiến hóa của quần thể. Nó cũng giúp tạo ra sự ña dạng trong quần thể. Theo công trình nghiên cứu của mình [17], Koza ñề xuất tỷ lệ sử dụng toán tử lai ghép trên quần thể là 90%. ðiều này có nghĩa là với quần thể gồm 100 cá thể, ở mỗi thế hệ, trung bình việc lai ghép ñược thực hiện trên 90 cá thể (45 cặp). 5.2.4.3. ðột biến Việc lai ghép lòng vòng giữa các cá thể trong quần thể một lúc nào sẽ dẫn ñến ñộ thích nghi của quần thể không thể tăng lên ñược nữa. ðể giải quyết vấn ñề này, một vài cá thể phải ñột biến ñể tạo ra một sự ña dạng mới trong quần thể. Toán tử ñột biến ñược dùng ñể thực hiện việc này. ðột biến ñược áp dụng trên một cá thể ngẫu nhiên. Khi ñó, một nhánh bất kỳ của cá thể sẽ bị loại bỏ và thay thế bằng một nhánh mới ñược tạo bằng thuật toán GROW hoặc FULL. Tỷ lệ sử dụng toán tử ñột biến trong quần thể ở mỗi thế hệ là không nhiều. Koza ñề nghị ở mỗi thế hệ, chỉ nên áp dụng ñột biến trên 1% số cá thể trong quần thể. Ví dụ mô tả quá trình ñột biến ở một cá thể biểu diễn cây logic. (NOT D1) OR (D0 AND D1) Hình 5.4. Cá thể trước khi thực hiện ñột biến [17]. 59 ((NOT D0) AND (NOT D1)) OR (D0 AND D1) Hình 5.5. Cá thể sau khi thực hiện ñột biến [17]. 5.2.5. Các tham số ảnh hưởng ñến quá trình tiến hóa 5.2.5.1. Kích thước quần thể Kích thước quần thể là một tham số có ảnh hưởng lớn ñến mức ñộ ña dạng của quần thể. Kích thước quần thể càng lớn, mức ñộ ña dạng khi khởi tạo quần thể ban ñầu càng lớn. ðộ ña dạng tăng sẽ làm tăng khả năng tìm ra ñược những lời giải chính xác cho bài toán. Tuy nhiên kích thước quần thế quá lớn sẽ ảnh hưởng không nhỏ ñến tốc ñộ thực hiện của giải thuật di truyền. Số lượng cá thể nhiều ñòi hỏi mất nhiều thời gian hơn cho quá trình khởi tạo quần thể ban ñầu. Quần thể lớn sẽ làm tăng số lần lai ghép, ñột biến, dẫn tới quá trình tiến hóa của quần thể qua từng thế hệ chậm lại. Koza [17] ñề xuất kích thước quần thể thông thường là 500 cá thể. 5.2.5.2. Số thế hệ tiến hóa Một tham số quan trọng khác trong lập trình di truyền là số thế hệ tiến hóa của quần thể. Qua mỗi thế hệ tiến hóa, ñộ thích nghi của quần thể ngày càng tăng, số lượng các lời giải gần chính xác càng nhiều. Nhưng không phải lúc nào thời gian cũng cho phép quần thể phát triển cho ñến khi thu ñược lời giải tối ưu. Vì vậy việc xem xét, 60 cân nhắc giữa mức ñộ gần ñúng của lời giải và thời gian cho phép ñể thu ñược lời giải là ñáng quan tâm. Koza [17] ñề xuất số thế hệ tiến hóa thông thường là 50 lần. 5.3. Phân tích hồi quy bằng lập trình di truyền 5.3.1. Phương pháp phân tích hồi quy Phân tích hồi quy là một phương pháp dùng ñể tìm mối liên hệ toán học (thường thông qua một hàm số) giữa một ñại lượng gốc (Dependent Variable) với một tập những biến số thành phần (Independent Variables) dựa trên tập dữ liệu thực nghiệm. Nói một cách hình tượng, ñây là quá trình ñi tìm ñồ thị hàm số gần ñúng “ñi qua” các ñiểm cho trước trên ñồ thị, tức một ñường cong có “khoảng cách tương ñối” ñến tất cả các ñiểm là nhỏ nhất. Hình 5.6. Minh họa phương pháp phân tích hồi quy [19]. Phân tích hồi quy ñược tiến hành qua hai bước: - Bước 1: tìm hàm cơ sở, quan sát và xem xét tập ñiểm trên ñồ thị ñể quyết ñịnh một hàm số cơ sở dùng là nền tảng cho việc phân tích. ðây là quá trình tìm dạng của hàm số kết quả. Thông thường có hai dạng là: tuyến tính và phi tuyến. Dạng của hàm số tìm ñược ở bước này sẽ ảnh hưởng rất lớn ñến ñộ 61 phức tạp của bước tối ưu hóa kế tiếp. Dạng tuyến tính ñơn giản nhưng kết quả thường không như mong muốn, vì ña số các trường hợp mối quan hệ giữa các ñại lượng cần tìm là phi tuyến. Bước tìm hàm cơ sở thường ñược thực hiện dựa trên phán ñoán của chuyên gia. - Bước 2: tối ưu hóa hàm cơ sở, tinh chỉnh các hệ số của hàm cơ sở tìm ñược ở bước 1 ñể thu ñược hàm số kết quả tối ưu. Quá trình tinh chỉnh thường dựa trên phương pháp bình phương tối tiểu: tìm các hệ số của hàm cơ sở sao cho tổng bình phương khoảng cách từ hàm cơ sở ñến tập ñiểm thực nghiệm là nhỏ nhất. Các hệ số cần tìm là nghiệm của hệ phương trình 5.2. ∑∑ −= 22 ))(( ii yxfR Công thức 5.2. Hệ phương trình của phương pháp bình phương tối tiểu [19]. Trong ñó: • xi, yi: tọa ñộ ñiểm thứ i trong tập ñiểm thực nghiệm. • f: hàm cơ sở tìm ñược ở bước 1. Nếu hàm cơ sở tìm ñược ở bước 1 có dạng phi tuyến, giải hệ phương trình 5.2 là một vấn ñề nan giải. Vì vậy trong nhiều trường hợp, kết quả ñạt ñược chỉ mang tính gần ñúng. Kết quả phân tích hồi quy phụ thuộc rất lớn vào sự phân bố của tập dữ liệu thực nghiệm. Tập dữ liệu này phải có tính “toàn diện”, phản ánh ñược một phần nào ñó tính chất (dạng) của hàm số. Các ñiểm dữ liệu phải phân bố toàn cục chứ không rơi vào một vùng cục bộ nào ñó của ñồ thị. 62 Ngoài ra, một vấn ñề cần phải quan tâm về tập dữ liệu thức nghiệm, ñó là sai số của tập dữ liệu này không ñược mang tính hệ thống, các sai số này phải phân bố trên toàn cục và mang tính ngẫu nhiên. 5.3.2. Áp dụng lập trình di truyền vào bài toán phân tích hồi quy [2] Phân tích hồi quy là một công việc phức tạp ñòi hỏi những chuyên gia có nhiều kinh nghiệm trong lĩnh vực sử dụng kết quả phân tích. Chuyên gia cần phải am hiểu tập dữ liệu thực nghiệm ñể có thể ñưa ra ñược hàm cơ sở phù hợp. Lập trình di truyền ñược dùng ñể tìm lời giải gần ñúng cho những bài toán phức tạp, với ñiều kiện những lời giải cho bài toán có thể biểu diễn ñược dưới dạng cây. Hàm số cần tìm trong phân tích hồi quy hoàn toàn phù hợp với ñiều kiện này. Nó có thể ñược biểu diễn dưới dạng cây biểu thức. Vì vậy việc áp dụng lập trình di truyền vào bài toán phân tích hồi quy là khả thi. 5.3.2.1. Biểu diễn cá thể Trong bài toán phân tích hồi quy, cá thể là những hàm số “ứng cử viên” ñược biểu diễn bằng cây biểu thức. Quá trình xây dựng cây biểu thức ñược thực hiện theo thuật toán GROW hoặc FULL (trình bày trong bảng 5.2 và bảng 5.3). Tập toán tử F và toán hạng T như sau: F = { {Tập toán tử số học: +, -, *, /, ^, log, exp, sin, cos, …} } T = { {Tập biến số của hàm cần tìm}, {Tập số thực R} } 63 5.3.2.2. Hàm thích nghi ðối với mỗi hàm số “ứng cử viên”, ñộ thích nghi ñược tính dựa trên phương pháp bình phương tối tiểu. Hàm số càng chính xác khi tổng bình phương khoảng cách của nó ñến tất cả các ñiểm trên ñồ thị càng nhỏ. Ơ ñây, tập dữ liệu thực nghiệm ñược sử dụng. ðộ thích nghi ñược tính theo công thức 5.3. ∑ ∑ −== 22 ))(( YXfRFitness ii Công thức 5.3. ðộ thích nghi của cá thể trong bài toán phân tích hồi quy. Trong ñó: - Fitnessi: ñộ thích nghi của cá thể i trong quần thể. - fi: hàm nhiều biến mà cá thể i biểu diễn. - X, Y: tập dữ liệu thực nghiệm.