Giới thiệu nhẹ nhàng về thuật toán di truyền

Hình ảnh của một gen

Khi bắt đầu tiến hành nghiên cứu về trí thông minh nhân tạo, bạn có thể đã nghe về một thứ gọi là 'Thuật toán di truyền'. Sau khi thấy thuật ngữ này, bạn có thể miễn cưỡng đào sâu vào nó vì nó chứa từ 'thuật toán'. Đừng sợ! Trong bài viết này, tôi sẽ cho bạn thấy sự đơn giản của thuật toán di truyền và hy vọng sẽ truyền cảm hứng cho bạn để xây dựng một thuật toán cho riêng bạn.

Thuật toán di truyền là gì?

Thuật toán di truyền về cơ bản là một phương pháp lấy cảm hứng mạnh mẽ từ quá trình chọn lọc tự nhiên để tìm ra giải pháp tốt nhất cho một vấn đề.

Trong tự nhiên, chỉ có kẻ mạnh tồn tại, quá trình loại bỏ kẻ yếu được gọi là chọn lọc tự nhiên. Thuật toán di truyền sử dụng nguyên tắc tương tự để loại bỏ các giải pháp yếu kém và cuối cùng tạo ra giải pháp tốt nhất.

Thông thường, thuật toán di truyền được sử dụng khi bạn không thể biết giải pháp sẽ như thế nào. Chẳng hạn, bạn muốn tạo ra một chiếc xe có thể điều hướng qua các loại địa hình khác nhau. Bạn không thể biết chiếc xe đó sẽ trông như thế nào, nhưng bạn biết mục tiêu của chiếc xe. Trong trường hợp này, thuật toán di truyền có thể được sử dụng để tạo ra chiếc xe để di chuyển trên các địa hình khác nhau nhưng thiết kế xe sẽ được quyết định bởi thuật toán.

Quá trình làm việc của thuật toán di truyền

Như đã đề cập trước đây, thuật toán di truyền được truyền cảm hứng mạnh mẽ bởi chọn lọc tự nhiên để xem thuật toán di truyền hoạt động như thế nào, bạn thực sự nên nhìn vào cách chọn lọc tự nhiên hoạt động.

quá trình chọn lọc tự nhiên (đơn giản hóa)

Sơ đồ trên minh họa quá trình chọn lọc tự nhiên. Rõ ràng là quá trình này bao gồm 5 bước chính. Bước đầu tiên là chọn lọc, trong bước này, thiên nhiên sẽ chọn những cá thể có gen mạnh từ quần thể ban đầu, sau đó chúng bắt đầu bước sang giai đoạn tiếp theo là giao phối. Sau khi trải qua bước giao phối, chúng sẽ sinh ra một đứa trẻ, chúng tôi gọi đây là bước sinh sản. Đứa trẻ cụ thể đó sau đó bị đột biến để thêm một số biến thể của gen và cuối cùng trở lại quần thể.

Quá trình thuật toán di truyền khá giống với quy trình trên, khác biệt duy nhất là nó đã thêm một số chi tiết bổ sung.

quá trình làm việc thuật toán di truyền

Để bắt đầu, quá trình làm việc của thuật toán di truyền cũng bắt đầu bằng cách có một dân số ban đầu. Giai đoạn chính đầu tiên là tính toán thể lực, tính toán thể lực có thể được coi là một phần của quá trình lựa chọn vì về cơ bản nó được sử dụng để tính điểm số điểm của mỗi cá nhân để cho biết đó là một cá nhân mạnh hay yếu. Tất cả các thực thể mạnh sau đó được chọn và chuyển qua một giai đoạn gọi là giao thoa, giai đoạn này giống như giai đoạn giao phối trong sơ đồ trước đó. Trong giai đoạn này, 2 cha mẹ ngẫu nhiên được chọn từ danh sách thực thể mạnh để thực hiện một cái gì đó gọi là chéo mà chúng ta sẽ thảo luận sau. Sau khi thực hiện chéo, một đứa trẻ được tạo ra và cũng bị đột biến để thêm một số biến thể cho gen. Cuối cùng, đứa trẻ này gia nhập lại dân số và quá trình lặp lại một lần nữa.

Thể dục là cái quái gì vậy

Trong thuật toán di truyền, thể dục đóng vai trò then chốt trong giai đoạn lựa chọn. Thể hình là điểm số điểm cao vì đã chọn một thực thể vượt qua những đặc điểm của nó. Ví dụ, nếu một người mắc bệnh hiểm nghèo, điểm thể lực của anh ấy sẽ thấp và ít có cơ hội sinh con vì những đứa trẻ của anh ta cũng sẽ thừa hưởng bệnh của anh ta. Do đó, nếu thể lực của giải pháp thấp, bạn có thể không muốn tạo một giải pháp khác dựa trên giải pháp đó vì kết quả sẽ tệ như giải pháp cũ.

Hãy thử tưởng tượng bạn đang gặp một vấn đề, vấn đề là tìm ra con đường tốt nhất để đội mũ trùm đỏ đi đến nhà bà ngoại. Chúng ta hãy giả sử rằng cô ấy muốn đến nhà bà của mình trong thời gian ngắn nhất có thể, do đó, sự phù hợp của tuyến đường có thể được tính bằng cách sử dụng thời gian cô ấy đi. Nếu có một tuyến đường có chiều dài 400 mét và cô ấy mất 10 phút để di chuyển thì thể lực của nó chắc chắn sẽ ít hơn thể lực của tuyến đường dài 500 mét nhưng chỉ mất 8 phút để đi du lịch như thể dục của một tuyến đường được tính toán dựa trên thời gian di chuyển, không phải chiều dài của nó. Do đó, tuyến đường dài 500 mét sẽ có nhiều khả năng được chọn để kết hợp với các tuyến đường khác.

Chọn một trong những tốt!

Chọn giải pháp thích hợp là giai đoạn lựa chọn của thuật toán di truyền. Sau khi tính toán điểm thể lực, bước tiếp theo là sử dụng một số phương pháp bí ẩn để chọn danh sách các giải pháp mà sau này có thể sử dụng để tạo ra một giải pháp tốt hơn.

Mặc dù bạn có thể tạo cách riêng để chọn giải pháp phù hợp, có một số phương pháp nổi tiếng mà bạn có thể sử dụng:

  • Lựa chọn cân đối
  • Lựa chọn giải đấu
  • Lựa chọn cắt ngắn
  • Lựa chọn đồng phục thể hình

Danh sách trên không phải là một danh sách đầy đủ, bạn có thể tìm hiểu thêm các phương pháp ở đây.

Hãy lấy phương pháp đầu tiên làm ví dụ. Không giống như tên của nó, khái niệm thực tế đằng sau phương pháp này rất đơn giản. Lựa chọn tỷ lệ phù hợp AKA lựa chọn bánh xe roulette, là phương pháp lựa chọn các giải pháp tiềm năng của hồi giáo để tái hợp.

Hãy tưởng tượng, nếu có 10 viên bi trong một cái túi, cụ thể là 5 viên bi xanh, 3 viên bi đỏ và 2 viên bi trắng. Bạn có thể dễ dàng tính toán rằng nếu bạn chọn ra một viên bi ngẫu nhiên từ túi, bạn sẽ có 5/10 cơ hội để chọn một màu xanh, 3/10 cho màu đỏ và 2/10 cho màu trắng. Đó là cách lựa chọn tỷ lệ thể dục hoạt động, tuy nhiên, quá trình này hơi khác một chút.

Trong lựa chọn tỷ lệ phù hợp, một số ngẫu nhiên được chọn trước tiên, sau đó nó sẽ được sử dụng để so sánh với mức độ phù hợp của giải pháp chọn ngẫu nhiên. Giá trị thể lực thường bị hạn chế đi từ 0 đến 1. Nếu giá trị ngẫu nhiên nhỏ hơn điểm thể lực đó thì giải pháp sẽ được chọn. Vì vậy, thể lực của một giải pháp càng cao thì cơ hội mà nó sẽ được chọn càng cao. Chẳng hạn, nếu một số ngẫu nhiên đi từ 0 đến 1, có 50% thì nó sẽ nhỏ hơn 0,5 và 80%, nó sẽ nhỏ hơn 0,8, tuy nhiên, nó sẽ không có khả năng nhỏ hơn 0,2, nghĩa là, nếu a giải pháp có 0,8 thể lực, có 80% nó sẽ được chọn để tái hợp và giải pháp có 0,2 thể lực sẽ chỉ có 20% được chọn. Mặc dù giải pháp thể dục 0,2 hiếm khi được chọn nhưng nó cũng giúp làm thay đổi các đặc điểm của giải pháp vì giải pháp đó có thể chứa một số thuộc tính cần thiết cho thành công sau này.

Biểu diễn chéo

Crossover là giai đoạn mà các giải pháp được lựa chọn được kết hợp để tạo thành các giải pháp mới. Cũng giống như giai đoạn chọn, cũng có nhiều kỹ thuật của chéo và bạn cũng có thể tìm thấy chúng ở đây.

Tương tự như giai đoạn lựa chọn, trong giai đoạn chéo, bạn cũng có thể phát minh ra các kỹ thuật chéo của riêng mình, tuy nhiên, cũng có một số kỹ thuật mà bạn có thể sử dụng:

  • Crossover một điểm
  • Giao nhau hai điểm
  • Đồng phục chéo
  • Crossover ba cha mẹ

Để hiểu rõ hơn, tôi sẽ giải thích kỹ thuật giao thoa thống nhất, đó là kỹ thuật mà tôi cho là kỹ thuật dễ thực hiện nhất.

Phương pháp trao đổi chéo thống nhất liên quan đến việc chọn ngẫu nhiên một phần gen của 2 giải pháp để kết hợp và tạo ra một giải pháp mới (hy vọng tốt hơn).

Bước đầu tiên trong giao thoa thống nhất là chọn 2 giải pháp ngẫu nhiên từ bộ giải pháp được chọn trong giai đoạn lựa chọn trước đó. Sau đó, mỗi phần của 2 giải pháp sẽ được chọn để thêm cơ sở giải pháp con vào một biến gọi là tỷ lệ pha trộn. Tỷ lệ pha trộn là thứ quyết định khả năng một giải pháp có khả năng được chọn để thêm vào giải pháp con. Chẳng hạn, có 2 giải pháp: A và B và bạn muốn giải pháp con có nhiều phần lấy từ giải pháp A, bạn có thể tăng tỷ lệ pha trộn, sau vòng lặp đó qua mọi phần của giải pháp A và B. Trong mỗi vòng lặp , tạo một số ngẫu nhiên mới và so sánh nó với tỷ lệ pha trộn, nếu nó nhỏ hơn tỷ lệ pha trộn thì chọn giải pháp Một phần khác chọn B. Tương tự, nếu tỷ lệ pha trộn là 0,5 thì A và B sẽ có khoảng 50% đang được đón.

Crossover thống nhất với tỷ lệ pha trộn 0,5

Hình trên, minh họa dung dịch C được tạo bằng dung dịch A và B với tỷ lệ pha trộn 0,5 hoặc 50%. Mỗi phần của cả hai giải pháp đều được quyết định chọn hay không dựa trên tỷ lệ pha trộn và tỷ lệ pha trộn được so sánh với một số ngẫu nhiên để quyết định. Nó giống như tung đồng xu để chọn nơi A nên sử dụng thay vì B và ngược lại.

Đột biến con!

Không không không, chúng tôi sẽ không biến con mình thành một số kẻ có móng vuốt kim loại và để chúng chết trên một thân cây ngẫu nhiên!

Thay vào đó, thêm đột biến cho một đứa trẻ cũng giống như giúp chúng

Bằng cách suy nghĩ khác biệt, một cá nhân có thể trở thành người lãnh đạo của bầy đàn hoặc một kẻ ngu ngốc hoàn toàn.

Một ví dụ về đột biến

Như bạn có thể thấy, đứa trẻ màu đỏ đang đi trên một con đường khác so với những đứa trẻ khác. Lý do cho điều này là bởi vì, khi đứa trẻ màu đỏ đang theo đàn, chúng tôi đã thêm một số đột biến cho nó và do đó, giúp nó chọn một con đường khác. Tất nhiên, con đường khác nhau đó cũng có thể là một ngõ cụt, nhưng rõ ràng, trong trường hợp này, con đường đang dẫn đến thành công! Đó là mục đích thực sự của giai đoạn đột biến.

Để biến đổi một đứa trẻ, cũng có một loạt các kỹ thuật mà bạn có thể sử dụng:

  • Đột biến chuỗi bit
  • Lật bit
  • Không đồng phục
  • Đồng phục

Bạn có thể tìm thấy nhiều hơn ở đây.

Để hiểu rõ hơn về điều này, tôi sẽ trình diễn kỹ thuật đột biến chuỗi bit bit.

Hãy tưởng tượng, bạn đang tạo một bot để tránh các vật thể ở phía trước nó. Bot sẽ phải tránh tất cả các đối tượng để đến đích cuối cùng và trạng thái tự nhiên của nó đang tiến về phía trước. Để tránh đối tượng, gen của nó sẽ là một chuỗi các chuỗi 'trái' và 'phải' chỉ ra cách bot sẽ di chuyển.

Đột biến chuỗi bit bit của nhà cung cấp thường được sử dụng cho chuỗi nhị phân vì phương thức này lật 1 hoặc nhiều bit được chọn ngẫu nhiên trong gen. Ví dụ:

Ví dụ về đột biến chuỗi bit

Bây giờ, hãy thử chuyển đổi 1 và 0 thành trái và phải và nghĩ xem bot sẽ hoạt động như thế nào. Vì bot có thể bị mắc kẹt khi gặp một vật thể lớn, đột biến sẽ giúp con cái của nó chọn một hướng mới để di chuyển và tránh vật thể đó. Hãy tưởng tượng, trong nhiều thế hệ, bot chỉ rẽ phải khi gặp một vật thể và chết, nhưng, ở thế hệ tiếp theo, bot đột nhiên rẽ trái khi một chuỗi bên phải trong gen của nó bị lật sang trái và bot cuối cùng đã đến đích. Về cơ bản, cách thức hoạt động của "đột biến chuỗi bit".

Kết thúc quá trình

Sau khi đột biến đứa trẻ, nó sẽ tham gia trở lại với đứa trẻ bị đột biến khác để cải tổ một quần thể mới và toàn bộ quá trình bắt đầu lại.

Vậy khi nào thì nó dừng lại? Câu trả lời cực kỳ đơn giản, khi nào bạn ngừng thực hành gõ bàn phím bằng 10 ngón tay? Khi kỹ năng đánh máy của bạn là hoàn hảo tất nhiên. Điều tương tự với thuật toán di truyền, quá trình sẽ dừng lại nếu thể lực của một giải pháp nào đó đạt được thể lực mong muốn. Chẳng hạn, bạn muốn bot trong ví dụ trước đến đích với lượng thời gian nhỏ nhất có thể.

Bạn đặt ngưỡng thể lực thành 4 phút, nếu thời gian kết thúc của bot là hơn 4 phút, điều đó có nghĩa là quá trình sẽ lặp lại cho đến khi thời gian kết thúc của bot nhỏ hơn hoặc bằng 4 phút.

Phần kết luận

Đó là phần cuối của bài viết của tôi, tôi hy vọng rằng sau bài viết này, bạn sẽ có cái nhìn sâu sắc hơn về thuật toán di truyền đã truyền cảm hứng để xây dựng một trong những thứ của riêng bạn.

Dưới đây là một số liên kết để bạn khám phá thêm về thuật toán di truyền:

  • Video của Daniel Shiffman về thuật toán di truyền:
  • Ví dụ của tôi về việc sử dụng thuật toán di truyền để đoán mật mã
  • hướng dẫn về hướng dẫn về thuật toán di truyền
  • Video Goran Muric về một ví dụ sử dụng thuật toán di truyền để tìm đường dẫn