9/21/2021

Tính toán tiến hóa | Tài liệu, chuyên ngành


Trong CTDL hay thuật toán ứng dụng các bạn đã biết tới bài toán người du lịch (TSP) là 1 bài toán NP-Khó, tức là để có thể đưa ra lời giải của bài toán chúng ta chỉ có cách là duyệt toàn bộ. Tuy nhiên thì điều này chỉ thỏa mãn và hợp lí với những bài mà N nhỏ khi N lớn thì không gian tìm kiếm tăng nhanh và việc duyệt toàn bộ để tìm ra kết quả tối ưu là gần như không thể. Trong các môn CTDL hay thuật toán ứng dụng chúng ta cũng chỉ được làm quen bài toán TSP với những giá trị N nhỏ để thực hiện duyệt toàn bộ tìm ra lời giải tối ưu của bài toán.

Tuy nhiên khi N tăng thậm chí là N rất lớn chúng ta vẫn có thể tìm được lời giải tối ưu của bài toán này (chỉ là có thể thôi nha) bằng các giải thuật tiến hóa. Các giải thuật tiến hóa đang được phát triển và sử dụng rộng rãi trong việc giải quyết các bài toán tối ưu NP-Khó, NP-Đầy đủ.


Có thể các bạn hơi ngỡ ngàng nhưng tính toán tiến hóa là 1 nhánh của trí tuệ nhân tạo nghiên cứu các giải thuật tối ưu tìm kiếm dựa trên học thuyết tiến hóa Darwin.

Có nhiều bạn đọc từ đầu tới giờ cứ tưởng như là chúng ta đang làm quen với môn sinh học mất, nhưng chỉ là lấy ý tưởng từ sinh học thôi nha, giải thuật tiến hóa là các giải thuật mình thấy rất là hay và lab cô Bình là lab tối ưu làm rất nhiều về giải thuật tiến hóa, bạn nào quan tâm tới vấn đề tối ưu thì có thể xin vào lab cô Bình nha, mình sẽ có riêng 1 bài viết khác về lab cô Bình nên bài viết này mình không lan man nhiều về vấn đề này.

Môn học này theo mình biết thì hiện tại chỉ có cô Bình dạy thôi, cô dạy môn này thì nói chung là rất thoải mái cả về giờ giấc lẫn cách học, chủ yếu là các bạn sẽ được phân vào các nhóm nghiên cứu trên lab của cô để làm bài tập lớn thôi, giữa kì các bạn sẽ trình bày về 1 cái gì đó mà mình học được trong nhóm cùng các anh/chị như là trình bày lại 1 bài báo mà mình đọc được hay là trình bày cách giải quyết 1 đề tài được các anh/chị trong nhóm giao. Về cơ bản thì không nhất thiết phải sử dụng các giải thuật di truyền mà các bạn có thể sử dụng các giải thuật heuristic, trình bày về các giải thuật heuristic cô đều chấp nhận và đồng ý hết. 

Dưới đây mình chia sẻ tới các bạn 1 số bài giảng, tài liệu dành cho môn học này gồm có slide bài giảng, và 1 số bài báo đã được public về k-coverage, q-coverage: 

  • Slide môn học tính toán tiến hóa: PDF | PPTX | ZIP (các bạn lên mang slide đi in ra nha, nhớ khi in dùng bản powerpoint - pptx nha để có thể in được full các phần, bản pdf nhiều trang các hình ảnh sẽ bị đè nên chữ)

1 comment: