Thuật toán Di truyền - Genetic Algorithm.pptx

thuật toán di truyền GA

1. Thuật toán Di truyền - Genetic Algorithm Presentation Title

2. Phần 1: Cực trị hàm số f(x) 01 Phần 2: Thuật toán GA và lập trình Python 02

3. Phần 1: Cực trị hàm số f(x) PART 01

4. Giới thiệu bài toán hàm số f(x) = x^4 - 4x^2. Cực trị của hàm số là những điểm mà giá trị của hàm đạt cực đại hoặc cực tiểu. Bài toán cần giải quyết Sử dụng đạo hàm Hình vẽ minh họa

5. Phần 2: Thuật toán GA và lập trình Python PART 02

6. Giới thiệu bài toán gene gà Chúng ta cần tìm ra một giống gà có các tiêu chí như cân nặng, sản lượng trứng, tuổi thọ, hệ miễn dịch và chất lượng thịt đạt mức cao nhất. Bài toán gene gà Mỗi tiêu chí của gene gà được đánh giá ở ba mức: thấp (10 điểm), vừa (20 điểm) và cao (30 điểm). Ví dụ, một con gà có cân nặng cao sẽ được 30 điểm, sản lượng trứng cao cũng sẽ được 30 điểm. Tổng điểm của các tiêu chí sẽ quyết định chất lượng của một cá thể trong quần thể. Các tiêu chí đánh giá Thuật toán di truyền được sử dụng để giải quyết bài toán gene gà có ứng dụng thực tế trong lĩnh vực nông nghiệp. Giúp người chăn nuôi chọn lọc và lai tạo giống gà có chất lượng cao, từ đó nâng cao hiệu quả sản xuất và lợi nhuận. Ứng dụng thực tế

7. Lập quần thể ban đầu Khởi tạo ngẫu nhiên một tập hợp cá thể Mỗi cá thể được biểu diễn bằng gen ở đây là 1 chuỗi nhị phân Quần thể càng đa dạng, khả năng tìm nghiệm tối ưu càng cao Tạo ngẫu nhiên 6 cá thể gà con mang đặc tính khác nhau

8. Chọn cha mẹ để lai ghép Những con gà khỏe (fitness cao) có xác suất được chọn để sinh sản cao hơn. 1 Cơ chế Roulette Wheel Selection (Vòng quay may mắn): fitness lớn → xác suất chọn lớn. 2 Phương pháp chọn lọc Tournament Selection: chọn ngẫu nhiên vài cá thể, lấy con khỏe nhất. 3 Phương pháp chọn lọc Ưu tiên “gà giỏi” để tạo thế hệ sau, nhưng vẫn giữ cơ hội nhỏ cho “gà yếu” → tránh bị kẹt ở nghiệm cục bộ. 4 Ý nghĩa

9. Xây dựng điều kiện dừng Giải thuật dừng khi: Đạt đến số thế hệ tối đa. Giá trị fitness không cải thiện sau N thế hệ liên tiếp. Hoặc tìm được cá thể đạt fitness ≥ ngưỡng mong muốn. Ý nghĩa: tiết kiệm tài nguyên, tránh chạy vô hạn mà không cải thiện. Điều kiện dừng

10. Lai ghép và đột biến Lấy 2 cá thể cha mẹ → kết hợp gen để sinh ra cá thể con. Với biểu diễn nhị phân, chọn điểm cắt giữa chuỗi, đổi chéo đoạn gen. Lai ghép Thay đổi ngẫu nhiên 1 phần gen của cá thể. đổi 1 bit trong gen nhị phân, hoặc cộng thêm một giá trị ngẫu nhiên nhỏ vào gen số thực. Đột biến Lai ghép: tạo thế hệ mới từ đặc điểm của cả cha lẫn mẹ. Đột biến: duy trì đa dạng di truyền, tránh quần thể bị “thoái hóa” hoặc kẹt ở cực trị địa phương. Ý nghĩa

11. Kết quả và ý nghĩa 01 Sau khi chạy chương trình thuật toán di truyền, chúng ta tìm được các cá thể có chất lượng cao nhất trong quần thể. Kết quả tìm được 02 Thuật toán di truyền đã chứng minh hiệu quả trong việc giải quyết bài toán gene gà. Tuy nhiên, thuật toán cũng có một số hạn chế như thời gian chạy dài và cần nhiều tham số để điều chỉnh. Đánh giá hiệu quả 03 Cho thấy thuật toán di truyền (Genetic Algorithm) bắt chước tiến hóa tự nhiên để tối ưu bài toán phức tạp. Ý nghĩa

12. THANKS! Presentation Title