Các phương pháp dựa trên thuật toán di truyền

Giải thuật di truyền (GA) cũng như các mạng neuron, các thuật toán di truyền cũng dựa trên 1 ẩn dụ sinh học: Các thuật toán này xem việc học như là sự khó khăn trong 1 quần thể gồm những lời giải người mua việc đang tiến hóa của bài toán. Một hàm ‘thích nghi’ (fitness function) sẽ đánh giá mỗi lời giải để quyết định liệu nó mang đóng góp cho thế hệ những lời giải kế tiếp hay không. Sau đó, phê chuẩn những phép toán na ná có biến đổi gene trong sinh sản hữu tính, giải thuật sẽ tạo ra một quần thể những lời giải người mua việc mới

Giải thuật di truyền là như thế nào ?

Trình bày giải thuật di truyền tổng quát. Tùy theo từng bài toán mà nhà ngoại hình giải thuật sẽ phải mô tả yếu tố hơn về:

Phương pháp biểu diễn một cá thể trong quần thể những lời giải người tìm việc của bài toán, hay nói khác hơn là hình thức trình diễn 1 lời giải tiềm năng của bài toán. Không phải lời giải của mọi bài toán đều với thể được mã hóa 1 bí quyết dễ dàng và khi không dưới dạng biểu diễn mức bit như trong bài toán thỏa mãn CNF dưới đây.

Độ lớn của quần thể là số lượng ứng viên với trong quần thể. Thông thường những ứng viên của quần thể ban đầu được sắm 1 phương pháp ngẫu nhiên. Độ to của quần thể là ko đổi qua những thế hệ, vì vậy, sẽ mang một công đoạn tậu lọc và dòng bỏ một số lời giải người chọn việc sở hữu độ thích nghi thấp.

Điều kiện ngừng của vòng lặp: mang thể là chương trình đạt tới một số lần lặp một mực nào đó, hay đạt đến trung bình độ phải chăng nào đó của quần thể,…

Hàm đánh giá (fitness function): Dùng để đánh giá một ứng cử viên mang thấp hay không. Một ứng cử viên càng phải chăng tức là độ thích ứng của nó càng cao và tiến tới trở thành lời giải đúng của bài toán. Việc ngoại hình 1 hàm kiểm tra phải chăng là siêu quan yếu trong thuật toán di truyền. Một hàm kiểm tra không chính xác mang thể làm mất đi các người mua việc rẻ trong quần thể.

Chọn lựa bao nhiêu phần trăm lời giải tốt để giữ lại? Hay mua bao nhiêu lời giải ứng viên để kết hợp sở hữu nhau và sinh ra lời giải con. Phương pháp tạo thành viên mới từ thành viên hiện có, còn gọi là toán tử di truyền (genetic operators):

Các toán tử di truyền phổ biến là Lai ghép (cross-over): Toán tử lai ghép lấy hai lời giải người tậu việc và chia từng lời giải ra thành hai phần, sau đó bàn thảo các phần có nhau để tạo ra ứng viên mới.

Đột biến (mutation): Đột biến lấy 1 người sắm việc đơn lẻ và thay đổi 1 phương pháp tự nhiên một khía cạnh nào đó của nó. Độ thích nghi(fitness)

Ví dụ minh họa giải thuật và toán tử di truyền.

Trong ví dụ minh họa bằng hình 9.18, ta thấy tại thế hệ thiết bị n ta với một lời giải mang độ thích nghi siêu tốt (2), và vì vậy, nó ko được dùng trong quá trình tái sản xuất. Thay vào đó, lời giải với độ thích ứng cao nhất (13) sẽ được nhân đôi và đưa vào quá trình tái sản xuất. Hoặc ít phổ biến hơn là các toán tử di truyền: • Đảo ngược (inversion): Đảo ngược thứ tự các bit trong chiếc lời giải. • Trao đổi (Exchange): Trao đổi hai bit bất kỳ trong dòng lời giải sở hữu nhau.

Một toán tử di truyền tốt đóng 1 vai trò quan trọng trong thuật toán di truyền. Toán tử di truyền buộc phải bảo toàn các mối quan hệ cốt yếu trong quần thể; ví dụ, sự với mặt và sự độc nhất của mọi những thành phố trong hành trình của người bán hàng trong bài toán người đi bán hàng.

• Thay thế thành viên mới cho những thành viên hiện mang như thế nào? • …

Bài toán thỏa CNF

Bài toán thỏa mãn dạng chuẩn hội (Conjunctive normal form – CNF) là 1 bài toán đơn giản: Một biểu thức của các mệnh đề (clause) ở dạng chuẩn hội hay CNF lúc nó là 1 dãy những biến mệnh đề được kết nối mang nhau bởi toán tử quan hệ and (∧). Mỗi mệnh đề sở hữu dạng là 1 tuyển (disjunction), gồm các toán tử quan hệ or (∨) trên các biến mệnh đề (literal). Ví dụ : Nếu ta sở hữu 6 biến mệnh đề a, b, c, d, e và f, thì biểu thức sau đây là 1 CNF:

Thỏa mãn CNF với nghĩa rằng chúng ta bắt buộc tìm ra một phép gán true hoặc false (1 hoặc 0) cho mỗi biến mệnh đề a, b, c, d, e, f sao cho biểu thức CNF có giá trị là TRUE. Một phương pháp trình diễn trùng hợp cho lời giải của bài toán này là một dãy sáu bit, mỗi bit theo đồ vật tự a, b, c, d, e, f trình diễn true (1) hoặc false (0) cho mỗi biến mệnh đề. Như vậy cái bit: 1 0 1 0 một 0 cho biết a, c, và e là true và b, d, và f là false, và do đấy lúc thay những giá trị này vào biểu thức (1-3), thì cho giá trị false.

Chúng ta muốn rằng những toán tử di truyền sinh ra những thế hệ lời giải sao cho biểu thức CNF mang trị true, vì thế mỗi toán tử buộc phải sinh ra 1 dòng 6-bit của phép gán true cho biểu thức. Cách biểu diễn lời giải dưới dạng 1 dòng các bit như trên sở hữu lại cho ta vô cùng 1 điều vô cùng thuận tiện là bất kỳ toán tử di truyền nào (lai ghép, đột biến, đảo ngược, hay trao đổi) đều tạo ra 1 chiếc bit mới là một lời giải khả dĩ hợp lệ.

Việc tậu lựa một hàm thích ứng cho quần thể những chuỗi bit này không bắt buộc hoàn toàn dễ dàng. Thoạt nhìn chuỗi bit, ta khó có thể xác định 1 hàm thích ứng để đánh giá được chất lượng của nó như thế nào, tức thị khó đoán được độ rẻ của nó so với đáp án đúng. Đáp án đúng ở đây chính là chuỗi bit sao cho biểu thức CNF với giá trị true.

Tuy nhiên sở hữu 1 số bí quyết khác. Nếu ta để ý đến biểu thức CNF (1-3), thì ta thấy rằng nó được tạo thành từ hội của 5 mệnh đề. Do ấy chúng ta với thể thiết lập một hệ phân hạng cho phép chúng ta gần hạng những lời giải (mẫu bit) tiềm năng trong khoảng giá trị từ 0 đến 5, tùy thuộc vào căn số đề mà loại đấy thỏa mãn. Do ấy mẫu: 1 một 0 0 1 0 sở hữu độ thích nghi là 1

0 1 0 0 một 0 với độ thích nghi là 2 0 1 0 0 1 1 với độ thích ứng là 3 1 0 một 0 một một mang độ thích ứng là 5, và nó chính là 1 lời giải.

Bài toán người đi bán hàng TSP

Bài toán người bán hàng (traveling salesperson problem – TSP) là một bài toán cổ điển đối mang AI và khoa học máy tính

Phát biểu của bài toán TSP: Một người bán hàng có nhiệm vụ lép thăm N thành thị như là 1 phần của lịch trình bán hàng. Đường đi giữa mỗi cặp thị thành với 1 chi phí (ví dụ như độ dài đoạn đường, giá vé máy bay). Hãy tìm ra đường đi có chi phí tốt nhất cho người bán hàng để bắt đầu lên đường tại 1 thành phố, thăm mọi các thị thành khác chỉ đúng 1 lần rồi quay lại thành thị xuất phát.

. Như chúng đã giới thiệu ở chương III, hầu hết ko gian trạng thái của nó đòi hỏi cần phê duyệt N! trạng thái để mang thể tậu ra lời giải tối ưu, trong ấy N là số thành thị nên đi qua. Khi N hơi to thì bài toán sẽ bị bùng nổ tổ hợp, bởi vậy người ta đặt vấn đề là mang buộc phải thiết hay ko cho việc chạy một máy trạm làm cho việc đắt tiền trong nhiều giờ để cho 1 lời giải thông minh hay chỉ cần chạy 1 PC rẻ tiền trong vài phút để sở hữu được những kết quả “đủ tốt”. Giải thuật di truyền chính là một giải pháp cho lựa chọn đồ vật hai.

Ở bài toán này, tiêu dùng chiếc bit để trình diễn cho lời giải của bài toán không phải là một bí quyết hay. Chẳng hạn, ta với chín tỉnh thành cần kẹ thăm 1, 2, …9, ta xem mỗi thành thị như một loại 4 bit 0001, 0010,… 1001. Khi đấy 1 lời giải khả dĩ sẽ có hình thức như sau: 0001 0010 0011 0100 0101 0110 0111 1000 1001.

Với cách trình diễn như vậy, việc ngoại hình những toán tử di truyền sẽ trở thành rất khó khăn. Toán tử lai ghép một mực là không được, vì chuỗi mới được tạo từ hai cha mẹ khác nhau hầu như sẽ không biểu diễn một đường đi trong đấy ghẹ thăm mỗi tỉnh thành đúng một lần. Trong thực tế, với lai ghép, một số đô thị có thể bị xóa bỏ trong khi những thị thành khác được xẹp thăm nhiều hơn 1 lần, và do đó đấy ko buộc phải là một lời giải hợp lệ. Còn toán tử đột biến thì thế nào? Giả sử bit trái nhất của tỉnh thành trang bị sáu, 0110, được đột biến thành 1? 1110, hay là 14, thì nó không còn là một thị thành hợp lệ.

Một phương pháp tiếp cận khác là sẽ bỏ qua trình diễn dạng loại bit và đặt cho mỗi thành phố một tên theo bảng chữ chiếc hoặc số, thí dụ 1, 2, …9; xem đường đi qua những thành thị là 1 sự sắp vật dụng tự của chín ký số này, và sau ấy sắm toán tử di truyền ưng ý để tạo ra những đường đi mới. Ở đây ta thấy phép trao đổi (exchange) trùng hợp hai thị thành trong đường đi với thể sử dụng được, còn phép toán lai ghép (crossover) thì không. Việc trao đổi các đoạn của 1 đường đi với các đoạn khác của cộng đường đi đó, hoặc bất cứ toán tử nào sắp xếp lại những chữ mẫu của đường đi ấy (mà không xóa bỏ, thêm, hay nhân đôi bất cứ thành thị nào) đều có thể sử dụng được. Tuy nhiên, những phương pháp này gây cạnh tranh cho việc đưa vào thế hệ con cháu những thành phần “tốt hơn” của những chiếc trong những đường đi qua của những thành thị của hai bố mẹ khác nhau.

Nhiều nhà nghiên cứu đã đưa ra các toán tử lai ghép với khả năng khắc phục các vấn đề này, trong đó với toán tử lai ghép với đồ vật tự (order crossover) do Davis đưa ra vào năm 1985. Lai ghép mang đồ vật tự xây dựng con cháu bằng phương pháp chọn một dãy con các thành thị trong đường đi của một mẫu cha mẹ. Nó cũng bảo toàn đồ vật tự khá những đô thị từ cha mẹ kia. Đầu tiên, sắm hai điểm cắt, diễn tả bởi dấu “|”, điểm cắt này được chen vào 1 cách khi không vào cộng một vị trí của mỗi cái cha mẹ.

Những điểm cắt này là ngẫu nhiên, nhưng một lúc được chọn, thì những vị trí như nhau sẽ được dùng cho cả hai cha mẹ. Ví dụ, sở hữu hai cái cho má p1 và p2, với những điểm cắt sau thành thị vật dụng ba và vật dụng bảy:

p1 = (1 9 2 | 4 6 5 7 | 8 3) p2 = (4 5 9 | 1 8 7 6 | 2 3) Hai chiếc con c1 và c2 sẽ được sinh ra theo bí quyết sau. Đầu tiên, các đoạn giữa hai điểm cắt sẽ được chép vào những chiếc con: c1 = (x x x | 4 6 5 7 | x x) c2 = (x x x | 1 8 7 6 | x x)

Bước kế tiếp là khởi đầu từ điểm cắt đồ vật hai của một trong hai mẫu cha mẹ, giả dụ ta đang muốn hoàn tất mẫu c1, thì ta sẽ khởi đầu từ điểm cắt trang bị hai của dòng p2, ta chép các đô thị từ điểm cắt này theo vật dụng tự vào các chỗ còn trống của c1, bỏ qua những thành phố mà c1 đã mang (các ký số được in đậm và nghiêng trong lược đồ bên dưới). Khi tới cuối cái p2, thì quay lại đầu loại p2 tiếp tục chép sang c1 cho tới khi c1 đủ.

Với giải thuật lai ghép này, những đường đi của thế hệ con sẽ được bảo đảm là những đường đi hợp lệ, đi qua mỗi tỉnh thành một lần duy nhất. Tóm lại, trong lai ghép trang bị tự, những mảnh của 1 đường đi được truyền từ 1 cha mẹ, p1, sang một con, c1, trong khi gần xếp của những đô thị còn lại của con c1 được thừa kế từ ba má kia, p2. Điều này ủng hộ cho trực quan hiển nhiên là thiết bị tự của các thành phố đóng vai trò quan yếu trong việc tạo ra đường đi có mức giá phải chăng nhất, và do vậy việc truyền lại những đoạn thông tin sở hữu vật dụng tự này từ những bố mẹ với độ thích ứng cao sang con chiếc là 1 điều vô cùng quan trọng. Ngoài toán tử lai ghép vật dụng tự trên, còn sở hữu vô cùng đa dạng toán tử lai ghép và đột biến khác được đưa ra để giải quyết bài toán này. Bảng 9.5 liệt kê các toán tử lai ghép,

Danh sách những toán tử đột biến cho bài toán TSP.

Đánh giá giải thuật

Các thí dụ vừa nêu trên làm cho vượt trội các vấn đề có tính duy nhất của thuật toán di truyền về biểu diễn tri thức, tậu toán tử di truyền, và ngoại hình hàm thích nghi. Biểu diễn được tậu phải tương trợ cho những toán tử di truyền. Một điểm dáng để ý nữa là những toán tử di truyền phải được kiểu dáng sao cho bảo lưu được những mảnh thông tin có ý nghĩa trong lời giải tiềm năng từ thế hệ này sang những thế hệ tiếp theo.

Một sức mạnh quan yếu của thuật toán di truyền là bản chất đồng thời trong tìm kiếm của nó. Các thuật toán này thực hành 1 dạng mạnh của leo núi (hill climbing) trong đấy duy trì phổ biến lời giải (trong quần thể những lời giải), chiếc bỏ những lời giải ko với triển vọng, và tăng chất lượng của những lời giải tốt. Hình 9.19 phỏng theo Holland (1986), cho thấy nhiều lời giải tụ họp về các điểm hợp lý trong không gian tậu kiếm.

Trong hình này, trục hoành trình diễn các điểm với thể có trong ko gian lời giải, trong khi trục tung phản ảnh chất lượng của các lời giải đó. Các điểm chấm nằm trên cung là những thành viên của quần diễn đạt tại. Khởi đầu, các lời giải được rải trong không gian những lời giải sở hữu thể có. Sau 1 vài thế hệ, chúng có thiên hướng cụm lại kế bên các vùng có chất lượng lời giải cao hơn.

Các thuật toán di truyền được xem là leo núi song song

(theo Holland 1986) Tuy nhiên, với sức mạnh như vậy, giải thuật genetic cũng không thể áp dụng cho toàn bộ các bài toán sở hữu thể có. Vì như ta thấy qua hai ví dụ trên, lời giải của bài toán buộc phải được trình diễn dưới một dạng mẫu phù hợp cho các toán tử di truyền hoạt động. Trong thực tế mang phổ biến bài toán ko thể khiến được điều này. Vì vậy, khi nghiên cứu về giải thuật này, mang siêu rộng rãi câu hỏi đã được đưa ra nhằm hiểu rõ hơn nữa về thực chất hoạt động của nó:

• Liệu chúng ta sở hữu thể đưa ra những đặc điểm về những loại bài toán mà giải thuật di truyền (GA) với thể thực hành tốt • Các chiếc bài toán nào thì ko ưa thích với GA. • Dựa vào đâu để ta với thể nói là GA thực hành phải chăng hay ko thấp đối mang 1 loại bài toán nào đó? • Liệu sở hữu những qui luật nào thể hiện hành vi của GA ở mức vĩ mô? Hay cụ thể hơn, là liệu với bất kỳ sự phán đoán nào về sự đổi thay của độ thích ứng của những nhóm con trong quần thể theo thời gian? • Có phương pháp nào để diễn tả những hiệu ứng khác nhau của các toán tử di truyền như lai ghép, đột biến, đảo ngược, v.v… • Trong các trường hợp nào (bài toán nào, toán tử di truyền nào) thì GA sẽ thực hiện thấp hơn những phương pháp nghiên cứu của TTNT truyền thống. Những câu hỏi này (và còn rộng rãi hơn nữa) vẫn đã và đang được những nhà kỹ thuật như Holland, Mitchell, Golderg,… nghiên cứu.

TỔNG KẾT

Giới thiệu tổng quát về 1 nhánh nghiên cứu mới của Trí Tuệ Nhân Tạo, đó là Học máy. Học được khái niệm như là bất cứ sự đổi thay nào trong một hệ thống cho phép nó tiến hành thấp hơn trong lần đồ vật hai khi lặp lại cộng một nhiệm vụ hoặc với một nhiệm vụ khác rút ra từ cộng một quần thể các nhiệm vụ đó.