Trong quá trình học phổ thông cũng như ở ĐH, chắc nhiều lần các bạn gặp phải một số bài toán như “bài toán người du lịch”, “bài toán người bán sản phẩm”, “bài toán cái túi”…. Những bài toán kiểu kiểu như vậy này thì rất nhiều, nhưng chủ yếu khác nhau ở cách mô tả, sót lại đều phải có có những điểm chung, theo mình nhận thấy như sau:

Bạn Đang Xem: Thuật toán di truyền – Ứng dụng giải một số bài toán kinh điển (phần 1)

• Nghiệm là một tập hợp
• Nghiệm là tối ưu, không phải nghiệm duy nhất
• Nghiệm được lấy từ một tập hợp là tất cả những trường hợp có thể xẩy ra dựa trên những tham gia của đề bài.

Đây là những đặc điểm do mình nhìn thấy trên ý kiến di truyền và tiến hóa (chưa chắc đã đúng :v)

Để giải dạng toán này thì có rất nhiều thuật toán (nói rứa thôi chứ tôi cũng không biết hết) (yaoming), nhưng trong nội dung bài viết này mình xin giới thiệu một thuật toán khá thú vị (theo mình là rứa) để xử lý: Thuật toán di truyền (mình lại thích gọi là thuật toán tiến hóa hơn)

Nghe có vẻ liên quan đến Sinh vật học, nên trước tiên mình sẽ nói sơ sơ qua một số lý thuyết về môn này, cái môn mà mình giỏi nhất hồi đi học, nhất là mấy chương cuối (ifyouknow…)

Di truyền

“Di truyền” là “hiện tượng kỳ lạ chuyển những tính trạng của cha mẹ cho con cháu thông qua gen của bố mẹ”. Trong sinh vật học, di truyền chuyển những đặc trưng sinh vật học từ một sinh vật cha mẹ đến con cháu và nó đồng nghĩa với vận chuyển gen, gen thừa nhận mang thông tin sinh vật học hay thông tin di truyền. (Wikipedia)

Tiến hóa

Xem Thêm : PCI là gì? PCI khác gì với PCIe? Nó quan trọng như thế nào đối với PC

Tiến hóa nói đến quá trình hoàn thiện, chuyển đổi dần để hoàn thiện hơn các phòng ban, chức năng của nhiều sinh vật để phù hợp hơn với tham gia sinh tốn cũng đang dần thay đổi.

Trong sinh vật học, tiến hóa là sự việc thay đổi đặc tính di truyền của một quần thể sinh vật học qua những thế hệ tiếp nối nhau. Các quá trình tiến hóa làm phát sinh sự đa dạng ở mọi mức độ tổ chức sinh vật học gồm có loài, các cá thể sinh vật và cả những phân tử như ADN và protein.

Tiến hóa do lựa chọn tự nhiên là một quá trình có thể suy ra từ ba thực kiện về các quần thể sinh vật học:

1. Nhiều cá thể con được sinh ra hơn số lượng có thể sống sót
2. Các tính trạng khác nhau giữa các cá thể, dẫn tới tỉ lệ tồn tại và sinh sản khác nhau
3. Những sự khác biệt về đặc điểm trên là có tính di truyền.

Do đó, khi những cá thể của một quần thể chết đi, chúng được thay thế bằng những hậu duệ của thế hệ cha mẹ nhưng có thể thích ứng tốt hơn để tồn tại và sinh sôi trong môi trường thiên nhiên mà sự lựa chọn tự nhiên diễn ra. Quá trình này tạo ra và bảo tồn những đặc điểm được cho là phù hợp hơn cho chức năng mà chúng đảm nhiệm.

Cho tới nay, sự lựa chọn tự nhiên là nguyên nhân duy nhất cho việc thích ứng, tuy nhiên không phải là nguyên nhân duy nhất cho việc tiến hóa. Những nguyên nhân khác của tiến hóa gồm có sự đột biến và dịch chuyển di truyền. Vào vào đầu thế kỷ 20, di truyền học kết phù hợp với lý thuyết tiến hóa nhờ lựa chọn tự nhiên của Darwin thông qua di truyền học quần thể. Tầm quan trọng của lựa chọn tự nhiên như một nguyên nhân tiến hóa đã được chấp thuận đồng ý trong những nhánh khác của sinh vật học.

(Wikipedia) – (Đọc mệt nghỉ rồi hehe)

Thuật toán di truyền

Xem Thêm : Chứng chỉ A2 Flyers Cambridge là gì? Cấu trúc đề, tài liệu luyện thi tại nhà cho con

Giải thuật di truyền (GA-Genetic Algorithm) là kỹ thuật phỏng theo quá trình thích ứng tiến hóa của nhiều quần thể sinh vật học dựa trên thuyết giáo Darwin. GA là phương pháp tìm kiếm tối ưu tình cờ bằng phương pháp mô phỏng theo sự tiến hóa của con người hay của sinh vật. Tư tưởng của thuật toán di truyền là mô phỏng các hiện tượng kỳ lạ tự nhiên, là thừa kế và đấu tranh tồn tại.

GA thuộc lớp các giải thuật xuất sắc nhưng lại rất khác các giải thuật tình cờ vì chúng phối hợp các thành phần tìm kiếm trực tiếp và tình cờ. Khác biệt quan trọng giữa tìm kiếm của GA và các phương pháp tìm kiếm khác là GA duy trì và xử lý một tập các lời giải, gọi là một quần thể (population). Trong GA, việc tìm kiếm giả thuyết thích hợp được khai mạc với một quần thể, hay một tập hợp có lựa chọn ban sơ của nhiều giả thuyết. Các cá thể của quần thể ngày nay khởi nguồn cho quần thể thế hệ kế tiếp bằng những hoạt động lai ghép và đột biến tình cờ – được lấy mẫu sau các quá trình tiến hóa sinh vật học. Ở từng bước, các giả thuyết trong quần thể ngày nay được ước tính liên hệ với đại lượng thích ứng, với những giả thuyết phù thống nhất được chọn theo xác suất là các hạt giống cho việc sản sinh thế hệ kế tiếp, gọi là cá thể (individual). Cá thể nào phát triển hơn, thích ứng hơn với môi trường thiên nhiên sẽ tồn tại và trái lại sẽ bị đào thải. GA có thể dò tìm thế kỷ mới có độ thích ứng tốt hơn. GA xử lý các bài toán quy thống kê học thông qua các quá trình cơ bản: lai tạo (crossover), đột biến (mutation) và lựa chọn (selection) cho những cá thể trong quần thể. Dùng GA yên cầu phải xác định được: khởi tạo quần thể ban sơ, hàm thẩm định và đánh giá các lời giải theo mức độ thích ứng – hàm mục tiêu, các toán tử di truyền tạo hàm sinh sản.

Sơ đồ thuật toán của GA:

Thuật giải GA đã và đang rất được ứng dụng để xử lý các bài toán trong rất nhiều ngành nghề của cuộc sống cũng như trong kỹ thuật.

Vậy thì nó liên quan gì đến những bài toán đã nêu (???) Nếu đủ 100 views (câu view tí hehe), phần tiếp theo mình sẽ show full code ví dụ để giải một trong các bài toán trên (yaoming)

Tham khảo: http://www.epu.edu.vn/ https://vi.wikipedia.org

Mr.Nara