Cơ sở Toán học của giải thuật di truyền

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

VŨ THỊ THU HÀ

CƠ SỞ TOÁN HỌC CỦA GIẢI

THUẬT DI TRUYỀN

LUẬN VĂN THẠC SỸ TOÁN HỌC

THÁI NGUYÊN - NĂM 2010

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

VŨ THỊ THU HÀ

CƠ SỞ TOÁN HỌC CỦA GIẢI

THUẬT DI TRUYỀN

Chuyên ngành: TOÁN ỨNG DỤNG

Mã số: 60.46.36

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học:

TS. VŨ MẠNH XUÂN

THÁI NGUYÊN - NĂM 2010

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

i

Mục lục

Mở đầu 1

1 Tổng quan về giải thuật di truyền 3

1.1 Khái quát chung . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Các vấn đề cơ bản của giải thuật di truyền . . . . . . . . 8

1.2.1 Mã hoá - mô tả di truyền cho lời giải của bài toán 8

1.2.2 Tạo lập lời giải ban đầu (khởi tạo quần thể) . . . 9

1.2.3 Xây dựng hàm phù hợp . . . . . . . . . . . . . . 9

1.2.4 Các toán tử di truyền . . . . . . . . . . . . . . . . 9

1.3 Giải thuật di truyền kinh điển . . . . . . . . . . . . . . . 11

1.3.1 Mã hoá - Biểu diễn các biến bằng véc tơ nhị phân 11

1.3.2 Toán tử chọn lọc . . . . . . . . . . . . . . . . . . 12

1.3.3 Toán tử lai ghép . . . . . . . . . . . . . . . . . . 14

1.3.4 Toán tử đột biến . . . . . . . . . . . . . . . . . . 16

1.3.5 Hàm phù hợp . . . . . . . . . . . . . . . . . . . . 16

1.3.6 Giải thuật di truyền cổ điển . . . . . . . . . . . . 18

1.4 Giải thuật di truyền mã hóa số thực (RCGA) . . . . . . 20

1.4.1 Giới thiệu RCGA . . . . . . . . . . . . . . . . . . 20

1.4.2 Các toán tử của RCGA . . . . . . . . . . . . . . 20

1.4.3 Một số mô hình tiến hóa. . . . . . . . . . . . . . 23

2 Cơ sở toán học của giải thuật di truyền 26

2.1 Định lý sơ đồ của Holland. . . . . . . . . . . . . . . . . . 27

2.1.1 Một số khái niệm . . . . . . . . . . . . . . . . . . 27

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ii

2.2 Mô hình Markov của giải thuật di truyền . . . . . . . . . 31

2.2.1 Tính Markov . . . . . . . . . . . . . . . . . . . . 32

2.2.2 Một số kết quả . . . . . . . . . . . . . . . . . . . 35

2.2.3 Xích Markov trong GA . . . . . . . . . . . . . . . 36

2.3 Một số vấn đề khác . . . . . . . . . . . . . . . . . . . . . 40

2.3.1 Dạng biểu diễn ma trận của toán tử lai ghép trong

RCGA . . . . . . . . . . . . . . . . . . . . . . . . 40

2.3.2 Điều kiện thành công của toán tử lai ghép . . . . 44

2.3.3 Toán tử lai ghép SBX . . . . . . . . . . . . . . . 45

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . 49

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1

Mở đầu

Ngày nay sự phát triển mạnh như vũ bão của máy tính điện tử đã

làm thay đổi sâu sắc đến nhiều lĩnh vực của cuộc sống, với tốc độ tính

toán nhanh và chính xác, nhiều bài toán tính toán phức tạp trước đây

đã được giải quyết trọn vẹn. Hơn thế nữa, nhiều kỹ thuật tính toán dựa

trên sự mô phỏng hoạt động tự nhiên hay bắt chước suy nghĩ của con

người đã rất phát triển và tạo ra nhiều công cụ tính toán mới có hiệu

năng cao. Giải thuật di truyền (GA – Genetic Algorithm) là một trong

những công cụ chính trong hệ thống tính toán mềm hay còn gọi là trí

tuệ tính toán. GA được đề xuất từ khoảng những năm 70 của thế kỷ

trước dựa trên sự mô phỏng quá trình tiến hoá tự nhiên. GA chủ yếu

giải quyết vấn đề tìm nghiệm trong lớp các bài toán tối ưu có độ phức

tạp tính toán lớn. GA tìm kiếm lời giải của bài toán dựa trên một quần

thể được hiểu như một tập những lời giải và tiến hoá quần thể đó dựa

trên các toán tử di truyền như chọn lọc, lai ghép, đột biến. Sau khi được

giới thiệu, GA đã được các nhà toán học và tin học nghiên cứu và phát

triển rất nhanh, nhiều dạng biến thể cũng như vấn đề cải tiến các toán

tử được đề xuất và kết quả thử nghiệm cho thấy tính hiệu quả rõ rệt

của giải thuật này.

Tuy vậy, GA là một giải thuật xác suất, hầu hết nó chỉ đưa ra những

lời giải chấp nhận được trong thời gian ngắn mà chưa chắc đã đạt được

lời giải tối ưu. Kết quả của quá trình tiến hoá để chọn lời giải tốt nhất

phụ thuộc vào nhiều yếu tố ngẫu nhiên: quần thể khởi tạo ngẫu nhiên,

chọn cá thể để tiến hoá ngẫu nhiên, việc sinh ra cá thể mới cũng là ngẫu

nhiên, . . . Vì vậy việc nghiên cứu cơ sở toán học của giải thuật để đảm

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn