ĐẠ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
1.1 Khái quát chung . . . . . . . . . . . . . . . . . . . . . .
1.2 Các vấn đề cơ bản của giải thuật di truyền . . . . . . . .
1.2.1 Mã hoá - mô tả di truyền cho lời giải của bài toán
1.2.2 Tạo lập lời giải ban đầu (khởi tạo quần thể) . . .
1.2.3 Xây dựng hàm phù hợp . . . . . . . . . . . . . .
1.2.4 Các toán tử di truyền . . . . . . . . . . . . . . . .
1.3 Giải thuật di truyền kinh điển . . . . . . . . . . . . . . .
1.3.1 Mã hoá - Biểu diễn các biến bằng véc tơ nhị phân
1.3.2 Toán tử chọn lọc . . . . . . . . . . . . . . . . . .
1.3.3 Toán tử lai ghép . . . . . . . . . . . . . . . . . .
1.3.4 Toán tử đột biến . . . . . . . . . . . . . . . . . .
1.3.5 Hàm phù hợp . . . . . . . . . . . . . . . . . . . .
1.3.6 Giải thuật di truyền cổ điển . . . . . . . . . . . .
1.4 Giải thuật di truyền mã hóa số thực (RCGA) . . . . . .
1.4.1 Giới thiệu RCGA . . . . . . . . . . . . . . . . . .
1.4.2 Các toán tử của RCGA . . . . . . . . . . . . . .
1.4.3 Một số mô hình tiến hóa. . . . . . . . . . . . . .
3
3
8
8
9
9
9
11
11
12
14
16
16
18
20
20
20
23
2 Cơ sở toán học của giải thuật di truyền
2.1 Định lý sơ đồ của Holland. . . . . . . . . . . . . . . . . .
2.1.1 Một số khái niệm . . . . . . . . . . . . . . . . . .
26
27
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 . . . . . . . . .
2.2.1 Tính Markov . . . . . . . . . . . . . . . . . . . .
2.2.2 Một số kết quả . . . . . . . . . . . . . . . . . . .
2.2.3 Xích Markov trong GA . . . . . . . . . . . . . . .
2.3 Một số vấn đề khác . . . . . . . . . . . . . . . . . . . . .
2.3.1 Dạng biểu diễn ma trận của toán tử lai ghép trong
RCGA . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Điều kiện thành công của toán tử lai ghép . . . .
2.3.3 Toán tử lai ghép SBX . . . . . . . . . . . . . . .
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . .
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
31
32
35
36
40
40
44
45
48
49
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
2
bảo chắc chắn sẽ đạt được lời giải tối ưu toàn cục của bài toán là việc
làm rất khó khăn mặc dù điều này hợp với quy luật tự nhiên và thử
nghiệm đều cho kết quả tốt. Cho tới nay người ta mới chỉ đạt được một
số kết quả sơ bộ về sự hội tụ của giải thuật chủ yếu dựa trên định lý sơ
đồ của Hollan và dựa trên mô hình Markov.
Đề tài này nhằm tập trung nghiên cứu cơ sở toán học của GA, tìm
hiểu và trình bày một cách có hệ thống một số kết quả nghiên cứu về
mô hình toán học của GA cũng như đánh giá sự hội tụ của giải thuật.
Do điều kiện nghiên cứu cũng như khả năng lập trình còn hạn chế nên
chưa đặt ra việc thử nghiệm trên những bài toán cụ thể.
Đề tài gồm những nội dung chính sau:
Chương 1 trình bày những vấn đề tổng quan về giải thuật di truyền,
nguyên lý chung, giải thuật di truyền kinh điển dựa trên mã hoá nhị
phân và giải thuật di truyền mã hoá số thực. Mô tả tường minh giải
thuật cũng như một số dạng toán tử di truyền tiêu biểu.
Chương 2 trình bày những vấn đề nghiên cứu về cơ sở toán của giải
thuật bao gồm định lý sơ đồ của Hollan, mô hình Markov của giải thuật
và một số phân tích toán học của các toán tử.
Như đã nêu trên, do GA là thuật toán xác suất chứ không tiền định
nên việc phân tích mô hình toán học của nó là cực kỳ khó khăn. Luận
văn này chỉ đặt ra mục tiêu là tìm hiểu và trình bày lại một cách hệ
thống những nội dung cơ bản như đã nêu.
Dù rất cố gắng song do còn nhiều hạn chế về thời gian, kiến thức,. . . nên
luận văn này không tránh khỏi những thiếu sót. Em rất mong được sự
góp ý của các thầy cô cùng các bạn học viên để hoàn thiện hơn nữa hoặc
có thể thác triển tiếp đề tài này.
Trong suốt quá trình làm đề tài em nhận được sự giúp đỡ của rất
nhiều các thầy cô giáo của Đại học Thái Nguyên và các bạn học viên
lớp CHTK2, đặc biệt là sự hướng dẫn rất tận tình của thầy giáo TS.Vũ
Mạnh Xuân. Em xin chân thành cảm ơn.
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
3
Chương 1
Tổng quan về giải thuật di truyền
1.1
Khái quát chung
Giải thuật di truyền (Gennetic algorithims - GA) là kỹ thuật chung
giúp giải quyết vấn đề - bài toán bằng cách mô phỏng sự tiến hoá của
con người hay của sinh vật nói chung trong điều kiện quy định sẵn của
môi trường.
Giải thuật di truyền cũng như các thuật toán tiến hoá nói chung hình
thành dựa trên quan niệm cho rằng, quá trình tiến hoá tự nhiên là quá
trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Quan
niệm này có thể được xem như một tiên đề đúng không chứng minh được
nhưng phù hợp với thực tế khách quan. Quá trình tiến hoá thể hiện tính
tối ưu ở chỗ, thế hệ sau bao giờ cũng tốt hơn (phát triển hơn, hoàn thiện
hơn) thế hệ trước. Tiến hoá tự nhiên được duy trì nhờ 2 quá trình cơ
bản: sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hoá tự
nhiên các thế hệ mới luôn được sinh ra để bổ sung, thay thế thế hệ cũ.
Cá thể nào không thích ứng được với môi trường sẽ bị đào thải. Sự thay
đổi môi trường cũng là động lực thúc đẩy quá trình tiến hoá. Ngược lại,
tiến hoá cũng tác động trở lại góp phần làm thay đổi môi trường.
Các cá thể mới sinh ra trong quá trình tiến hoá nhờ sự lai ghép thế
hệ cha mẹ. Một cá thể mới có thể mang những tính trạng của cha mẹ (di
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
4
truyền), cũng có thể mang những tính trạng hoàn toàn khác (đột biến).
Di truyền và đột biến là 2 cơ chế có vai trò quan trọng như nhau trong
quá trình tiến hoá. Dù rằng đột biến xảy ra xác suất nhỏ hơn nhiều so
với hiện tượng di truyền.
Giải thuật di truyền sử dụng các thuật ngữ vay mượn của di truyền
học. Ta có thể nói về các cá thể (hay kiểu gen, cấu trúc) trong một quần
thể, các cá thể này cũng còn được gọi là các chuỗi hay các Nhiễm sắc
thể (NST). Trong GA, ta chỉ nói về những cá thể có 1 NST; các NST
được tạo thành từ các đơn vị - các gen - biểu diễn trong một chuỗi tuyến
tính, mỗi gen kiểm soát một (số) đặc trưng. Gen với những đặc trưng
nhất định có vị trí nhất định trong NST. Bất cứ đặc trưng nào của mỗi
cá thể có thể tự biểu hiện một cách phân biệt, và gen có thể nhận một
số giá trị khác nhau (các giá trị về tính năng). Một vấn đề - bài toán đặt
ra sẽ được mã hoá thành các chuỗi bit với chiều dài cố định. Nói một
cách chính xác là các thông số của bài toán sẽ được chuyển đổi và biểu
hiện lại dưới dạng các chuỗi bit. Các thông số này có thể là các biến của
một hàm hoặc hệ số của một biểu thức toán học. Người ta gọi các chuỗi
bit này là mã genome (gen) ứng với mỗi cá thể, các gen đều có cùng
chiều dài. Nói ngắn gọn, một lời giải sẽ được biểu diễn bằng một chuỗi
bit cũng giống như mỗi cá thể đều được quy định bằng gen của cá thể
đó vậy. Đối với thuật giải di truyền một cá thể chỉ có 1 gen duy nhất
và 1 gen cũng chỉ phục vụ cho một cá thể duy nhất. Mỗi kiểu (nhóm)
gen (ta gọi là 1NST) sẽ biểu diễn một lời giải của bài toán đang giải (ý
nghĩa của 1 NST cụ thể được người sử dụng xác định trước), một tiến
trình tiến hoá được thực hiện trên 1 quần thể các NST tương ứng với
một quá trình tìm kiếm lời giải trong không gian lời giải. Tìm kiếm đó
cần cân đối hai mục tiêu (có vẻ mâu thuẫn nhau). Khai thác những lời
giải tốt nhất và khảo sát không gian tìm kiếm. GA là phương pháp tìm
kiếm (độc lập miền) tạo được sự cân đối đáng kể giữa việc khai thác và
khảo sát không gian tìm kiếm.
Thực ra, GA thuộc lớp các giải thuật xác suất, nhưng lại rất khác
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
5
những giải thuật ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực
tiếp và ngẫu nhiên. 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
(ta gọi là một quần thể) - tất cả những phương pháp khác phần lớn xử
lý một điểm trong không gian tìm kiếm. Chính vì vậy, GA mạnh hơn
các phương pháp tìm kiếm hiện có rất nhiều.
GA thực hiện tiến trình tìm kiếm lời giải tối ưu theo nhiều hướng
bằng cách duy trì một quần thể các lời giải và thúc đẩy sự thành hình
và trao đổi thông tin giữa các hướng này. Quần thể trải qua tiến trình
tiến hoá, ở mỗi thế hệ lại tái sinh các lời giải tương đối "tốt"; trong khi
các lời giải tương đối "xấu" thì chết đi. Để phân biệt các lời giải khác
nhau; hàm mục tiêu được dùng để đóng vai trò môi trường.
Các thuật toán, tuy có những điểm khác biệt, nhưng đều mô phỏng
các quá trình cơ bản: lai ghép, đột biến, sinh sản và chọn lọc tự nhiên.
* Quá trình lai ghép (Crossover): Phép lai là quá trình hình thành
nhiễm sắc thể mới trên cơ sở nhiễm sắc thể cha - mẹ, bằng cách ghép
một hay nhiều đoạn gen, hai (hay nhiều) nhiễm sắc thể cha - mẹ với
nhau. Phép lai xảy ra xác suất Pc có thể mô phỏng như sau:
• Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kỳ trong quần thể. Giả
sử các nhiễm sắc thể của cha - mẹ đều có m gen.
• Tạo một số ngẫu nhiên trong khoảng từ 1 đến m − 1 (ta gọi là
điểm lai). Điểm lai chứa các chuỗi cha - mẹ dài m thành hai nhóm chuỗi
con dài m1 và m2 . Hai chuỗi nhiễm sắc thể con mới sẽ là m11 + m22 và
m21 + m12.
• Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến
hoá tiếp theo.
* Quá trình đột biến (Mutation)
Đột biến là hiện tượng cá thể con mang một (số) tính trạng không
có trong mã di truyền của cha - mẹ. Phép đột biến xảy ra với xác suất
Pm , nhỏ hơn rất nhiều so với xác suất lai Pc . Phép đột biến có thể mô
phỏng như sau:
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
6
• Chọn ngẫu nhiên một cá thể bất kỳ cha - mẹ trong quần thể.
• Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m, 1 ≤ k ≤ m.
• Thay đổi gen thứ k và trả cá thể này về quần thể để tham gia quá
trình tiến hoá tiếp theo.
* Quá trình sinh sản và chọn lọc (Selection)
Phép tái sinh là quá trình trong đó, các cá thể được sao chép trên cơ
sở độ thích nghi của nó. Độ thích nghi là một hàm gán một giá trị thực
cho các cá thể trong quần thể. Quá trình này có thể được mô phỏng như
sau:
• Tính độ thích nghi của từng cá thể trong quần thể hiện hành, lập
bảng cộng dồn các giá trị thích nghi (theo số thứ tự gán cho từng cá
thể). Giả sử quần thể có n cá thể. Gọi độ thích nghi của cá thể thứ i là
Fi, tổng dồn thứ i là Fti , tổng độ thích nghi của toàn quần thể là Fm.
• Tạo một số ngẫu nhiên F trong đoạn từ 0 đến Fm .
• Chọn cá thể thứ k đầu tiên thoả mãn F ≥ Ftk đưa vào quần thể
của thế hệ mới.
Phép chọn là quá trình loại bỏ các cá thể xấu trong quần thể để chỉ
giữ lại trong quần thể các cá thể tốt. Phép chọn có thể được mô phỏng
như sau:
• Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần.
• Loại bỏ các cá thể cuối dãy để chỉ giữ lại n cá thể tốt nhất. (Ta giả
sử quần thể có kích thước cố định n).
Một giải thuật di truyền, giải một bài toán được cho phải có 5 thành
phần sau:
+ Một cấu trúc dữ liệu I biểu diễn không gian lời giải của bài toán.
+ Phương pháp khởi tạo quần thể ban đầu P (0).
+ Hàm định nghĩa độ thích nghi eval (.) đóng vai trò môi trường.
+ Các phép toán di truyền như đã mô phỏng trên.
+ Và các tham số giải thuật di tryền sử dụng (kích thước quần thể,
xác suất lai, đột biến,...).
* Cấu trúc giải thuật di truyền tổng quát.
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
7
Bắt đầu
Khởi tạo quần thể
Mã hoá các biến
Đánh giá độ thích nghi
Chọn lọc
Lai ghép
Đột biến
Thoả điều kiện dừng
Không
Thoả
Kết quả
Kết thúc
Hình 1.1: Sơ đồ cấu trúc thuật toán di truyền
Bắt đầu:
t=0
Khởi tạo P (t)
Tính độ thích nghi cho các cá thể thuộc P (t).
Khi (điều kiện dừng chưa thoả) lặp.
t = t + 1;
Tái sinh P 0 (t) từ P (t − 1);
Lai Q(t) từ P (t − 1);
Đột biến R(t) từ P (t − 1);
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
8
Chọn lọc P (t) từ P (t − 1) ∪ Q(t) ∪ R(t) ∪ P (t);
Hết lặp
Kết thúc.
1.2
Các vấn đề cơ bản của giải thuật di truyền
1.2.1
Mã hoá - mô tả di truyền cho lời giải của bài toán
Việc mô tả di truyền cho lời giải cho bài toán gồm hai phần cơ bản:
Xây dựng cấu trúc gen cho mỗi lời giải của bài toán để từ mỗi
lời giải ta có thể mã hoá thành một NST (chuỗi các gen).
Giải mã các NST để nhận được lời giải.
Đây là vấn đề cần giải quyết trước khi giải bài toán với GA. Tuỳ
thuộc vào nội dung của mỗi bài toán mà ta có cách mã hoá khác nhau.
Sau đây là các phương pháp mã hoá hay được sử dụng:
Mã hoá dạng chuỗi nhị phân: đây là phương pháp thông dụng và cơ
bản nhất được sử dụng ngay từ bước ban đầu khi nghiên cứu GA. Trong
phương pháp này mỗi NST là một chuỗi các bit 0 và 1.
Mã hoá thứ tự: được sử dụng trong bài toán có sắp xếp thứ tự. Ở đây
mỗi NST là một chuỗi các số nguyên thể hiện thứ tự phân bố lời giải
của bài toán.
Mã hoá theo giá trị: được sử dụng trong các bài toán mà mỗi lời giải
là tập các giá trị (ví dụ tập số thực). Trong phương pháp này, mỗi NST
là một chuỗi các giá trị có mối quan hệ tương ứng với bài toán.
Mã hoá dạng cây: được sử dụng chủ yếu trong các biểu thức toán học,
trong phương pháp mã hoá này mỗi NST là một cây của một nhóm đối
tượng nào đó.
Mã hoá số thực: Mỗi NST được mã hoá là một véc tơ trong không
gian Rm chẳng hạn X = (a1 , a2, ..., am) với các ai ∈ R. Cách mã hoá này
thường tự nhiên đối với các bài toán tối ưu số và được phát triển rất
mạnh trong thời gian gần đây.
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
9
1.2.2
Tạo lập lời giải ban đầu (khởi tạo quần thể)
Tập lời giải ban đầu thường được khởi tạo ngẫu nhiên từ miền xác
định của các lời giải. Cách tạo lập tập lời giải ban đầu phụ thuộc rất
nhiều vào cách mã hoá NST.
Với phương pháp mã hoá nhị phân: xây dựng NST bằng cách tạo
ngẫu nhiên chuỗi các bit 0 hoặc 1.
Với phương pháp mã hoá thứ tự: xây dựng NST ban đầu bằng cách
hoán vị ngẫu nhiên các thứ tự.
Với phương pháp mã hoá theo giá trị: tạo ngẫu nhiên từng giá trị
trong miền xác định của lời giải để tạo ra chuỗi NST ban đầu.
Với mã hoá số thực: tạo ngẫu nhiên N véc tơ thực trong Rm .
1.2.3
Xây dựng hàm phù hợp
Hàm phù hợp đánh giá khả năng phù hợp của tập lời giải theo yêu
cầu bài toán. Hàm này được xây dựng cho từng bài toán với yêu cầu cụ
thể. Thông thường trong các bài toán tối ưu hàm này chính là hàm mục
tiêu của bài toán.
1.2.4
Các toán tử di truyền
a. Toán tử chọn lọc
Trong quá trình thực hiện của giải thuật di truyền, sau mỗi lần tiến
hoá ta chỉ giữ lại các cá thể có độ phù hợp cao còn các cá thể phù hợp
thấp bị loại bỏ. Toán tử chọn lọc thường giữ lại 50% các cá thể phù hợp
nhất. Tuy nhiên người ta cũng phát triển nhiều sơ đồ chọn khác nhau
nhằm là tăng tính đa dạng của quần thể, tránh sự hội tụ sớm.
b. Toán tử lai ghép
Bước 1: Tạo ra tập NST để tạo sinh từ quần thể bằng cách chọn
ngẫu nhiên N NST từ M NST (M là kích cỡ quần thể).
Có nhiều cách chọn:
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
10
Chọn ngẫu nhiên theo thứ tự: lặp N lần việc tạo ngẫu nhiên ra một
số nguyên i thuộc khoảng [1, M] để chọn NST thứ i.
Chọn theo trọng số: tạo trọng số tích luỹ cho M NST theo công thức:
pi =
i
;
M
P
k
(với bài toán tìm min)
(1.1)
M −i+1
; (với bài toán tìm max)
M
P
k
(1.2)
k−1
pi =
k−1
Sau khi có trọng số tích luỹ cho NST, ta lần lượt tạo các xác suất
ngẫu nhiên r và duyệt từ NST đầu tiên đến khi gặp NST có trọng số
tích luỹ lớn hơn r thì chọn nó.
Bước 2: Sau khi chọn được N NST, lần lượt lấy ra từng cặp NST để
lai ghép tạo ra hai NST mới. Một số dạng toán tử lai ghép hay dùng là :
Lai ghép 1 điểm: chọn ngẫu nhiên một vị trí sau đó hoán vị phần
đứng sau vị trí vừa chọn giữa hai NST cha và mẹ để nhận được hai NST
con.
Lai ghép hai điểm: chọn ngẫu nhiên hai vị trí trong một NST, sau đó
hoán vị các giá trị đứng giữa hai điểm đã chọn của hai NST cha mẹ để
nhận được hai NST con.
Lai ghép mặt nạ: tạo một mặt nạ ngẫu nhiên có số bit bằng chiều dài
của NST. Ta sẽ hoán vị các giá trị của hai NST cha và mẹ ở những vị
trí tương ứng với vị trí bit 1 của mặt nạ.
c. Toán tử đột biến: Toán tử đột biến được xây dựng để tránh việc
nhận được giá trị tối ưu cục bộ. Đột biến gây ra thay đổi ngẫu nhiên
trên từng bit của NST để tạo ra một NST mới.
d. Tạo sinh: Chọn các cá thể từ quần thể hiện thời làm quần thể mới
cho lần lặp kế tiếp.
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
11
1.3
Giải thuật di truyền kinh điển
Giải thuật di truyền kinh điển sử dụng mã hóa nhị phân, mỗi cá thể
được mã hóa là một chuỗi nhị phân có chiều dài cố định.
1.3.1
Mã hoá - Biểu diễn các biến bằng véc tơ nhị phân
Ta sử dụng véc tơ nhị phân có độ dài L như một NST để biểu diễn
giá trị thực của biến x ∈ [lx , ux ]. Độ dài L của NST phụ thuộc vào yêu
cầu cụ thể của bài toán. Một bit mã hoá x ứng với một giá trị trong
khoảng [0, 2L] sẽ được ánh xạ lên giá trị thực thuộc miền [lx , ux ]. Nhờ
đó ta có thể kiểm soát miền giá trị của các biến và tính chính xác của
chúng. Tỷ lệ co giãn của ánh xạ được tính như sau:
g=
u x − lx
2L
Giá trị x tương ứng với chuỗi NST nhị phân là:
x = lx + decimal(N ST ) ∗ g
Trong đó, decimal(NST) là giá trị thập phân của chuỗi NST nhị phân.
Chẳng hạn ta muốn tìm cực tiểu một hàm k biến f (x1, . . . , xk ) : Rk → R.
Giả sử thêm là mỗi biến xi có thể nhận giá trị trong miền Di = [ai , bi] ⊆
R và f (x1, . . . , xk ) > 0 với mọi xi thuộc Di . Ta muốn tối ưu hoá hàm f
với độ chính xác cho trước là 6 số lẻ đối với giá trị của các biến.
Rõ ràng là để đạt được độ chính xác như vậy mỗi miền Di được phân
cắt thành (bi − ai ) ∗ 106 miền con bằng nhau. Gọi mi là số nguyên nhỏ
nhất sao cho: (bi − ai ) ∗ 106 ≤ 2mi − 1
Như vậy, mỗi biến xi được biểu diễn bằng một chuỗi nhị phân có chiều
dài mi . Biểu diễn như trên, rõ ràng thoả mãn điều kiện về độ chính xác
yêu cầu. Công thức sau tính giá trị thập phân của mỗi chuỗi nhị phân
biểu diễn biến xi
Xi = ai + decimal(1100...012).
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
bi − ai
2 mi − 1
http://www.lrc-tnu.edu.vn
12
trong đó decimal(chuỗi2) cho biết giá trị thập phân của chuỗi nhị phân
đó. Bây giờ, mỗi nhiễm sắc thể (là một lời giải) được biểu diễn bằng
k
P
chuỗi nhị phân có chiều dài L =
mi
i=1
trong đó m1 bit đầu tiên biểu diễn các giá trị trong khoảng [a1 , b1]; ...; mk
bit cuối cùng biểu diễn giá trị trong khoảng [ak , bk ].
Để khởi tạo quần thể, chỉ cần đơn giản tạo pop-size (kích cỡ quần thể)
nhiễm sắc thể ngẫu nhiên theo từng bit. Phần còn lại của thuật giải di
truyền rất đơn giản: trong mỗi thế hệ, ta lượng giá từng nhiễm sắc thể
(tính giá trị hàm f trên các chuỗi biến nhị phân đã được giải mã), chọn
quần thể mới thoả phân bố xác suất dựa trên độ thích nghi và thực hiện
các phép đột biến và lai để tạo các cá thể thế hệ mới. Sau một số thế
hệ, khi không còn cải thiện thêm được gì nữa, nhiễm sắc thể tốt nhất sẽ
được xem như lời giải của bài toán tối ưu (thường là toàn cục). Thông
thường, ta cho dừng thuật giải di truyền sau một số bước lặp cố định
tuỳ thuộc vào điều kiện về tốc độ về tài nguyên máy tính.
1.3.2
Toán tử chọn lọc
a) Sử dụng bánh xe Roulette
Có nhiều cách để thực hiện toán tử chọn lọc, nói chung đều theo tư
tưởng cá thể có độ thích nghi cao hơn thì khả năng được chọn nhiều
hơn. Nhưng có lẽ đơn giản và hiệu quả nhất là sử dụng bánh xe Roulette
(roulette wheel), mỗi cá thể trong quần thể chiếm một khe có độ rộng
tỷ lệ thuận với giá trị phù hợp. Độ rộng của khe được tính bằng tỷ lệ %
giá trị phù hợp của một cá thể trên tổng giá trị phù hợp toàn quần thể.
Gọi fi là độ phù hợp của cá thể thứ i trong quần thể gồm N cá thể
fi
khi đó cá thể i sẽ được chọn với xác suất pi = N . Trên vòng tròn
P
fi
i=1
Roulette mỗi chuỗi trong quần thể chiếm một khe có độ rộng tỷ lệ với
độ phù hợp của chuỗi. Độ rộng của khe được tính theo tỷ lệ phần tră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
13
độ phù hợp của chuỗi với tổng độ phù hợp của toàn quần thể là 100%.
b. Thủ tục xếp hạng các cá thể.
Trong thủ tục này các cá thể được sắp xếp theo giá trị của hàm mục
tiêu. Cá thể đầu tiên là cá thể tốt nhất và cá thể cuối cùng là cá thể
tồi nhất. Trong thủ tục này cá thể thứ (N − j) trong dãy sẽ có xác suất
j
chọn lựa là pN −j = N
P
k
k=1
Các bước tiến hành của thủ tục là:
- Sắp xếp các chuỗi theo thứ tự giảm dần của hàm mục tiêu (bài toán
cực đại) hoặc theo thứ tự tăng dần của hàm mục tiêu (bài toán cực tiểu).
- Tính độ phù hợp của chuỗi theo hình
Độ phù hợp
của chuỗi fi
Hình 1.2: Thủ tục xếp hạng tuyến tính
c. Thủ tục chọn lọc cạnh tranh
Trong thủ tục này chúng ta tiến hành như sau:
- Chọn t cá thể từ quần thể hiện tại một cách ngẫu nhiên và chọn cá
thể tốt nhất trong t cá thể đó để sao chép sang quần thể tạm thời.
- Lặp lại bước trên N lần chúng ta sẽ có quần thể tạm thời.
Giá trị t được gọi là kích cỡ của chọn lọc cạnh tranh. Khi t = 2 chúng
ta chọn lọc cạnh tranh nhị phân.
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
14
1.3.3
Toán tử lai ghép
a. Lai ghép một điểm
Lai ghép một điểm được thực hiện rất đơn giản. Với hai cá thể cha mẹ
đã chọn P1 , P2; toán tử này cần sinh ngẫu nhiên một vị trí k(1 < k < L),
sau đó hai cá thể con được tạo thành bằng cách tráo đổi các gen của
cặp cha mẹ tính từ điểm cắt. Chẳng hạn
P1 = (1 1 1 0 0 0 1 0 1 0)
P2 = (0 1 0 1 1 0 0 1 1 1)
là hai chuỗi nhị phân độ dài 10, giả sử điểm cắt đã chọn là k = 7, thế
thì hai con được sinh ra là :
C1 = (1 1 1 0 0 0 1 1 1 1)
C2 = (0 1 0 1 1 0 0 0 1 0)
Thủ tục lai ghép đơn giản như sau :
Procedure lai1diem(k; P1, P2; var C1, C2);
Begin
For i := 1 to k do
Begin
C1[i] := P 1[i];
C2[i] := P 2[i];
End;
For i := k + 1 to L do
Begin
C1[i] := P 2[i];
C2[i] := P 1[i];
End;
End;
b. Lai ghép nhiều điểm
Lai ghép nhiều điểm được thực hiện tương tự như lai ghép một điểm.
Với hai cá thể cha mẹ đã chọn P1 , P2 ; toán tử này cần sinh ngẫu nhiên k
vị trí i1 , ..., ik ; có thể giả thiết thêm i1 < i2 < ... < ik . Các điểm cắt này
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
15
chia các cá thể đã chọn thành các đoạn được đánh số chẵn lẻ; sau đó hai
cá thể con được tạo thành bằng cách tráo đổi các gen của cặp cha mẹ
tuỳ theo các đoạn chẵn hay lẻ đã nêu. Trong lai ghép nhiều điểm thì lai
ghép hai điểm cắt được quan tâm nhiều nhất.
Chẳng hạn
P1 = (1 1 1 0 0 0 1 0 1 0)
P2 = (0 1 0 1 1 0 0 1 1 1)
là hai chuỗi nhị phân độ dài 10, giả sử các điểm cắt đã chọn là 2, 5, 8 thế
thì hai con được sinh ra là:
C1 = (1 1 1 0 0 0 1 1 1 1)
C2 = (0 1 0 1 1 0 0 0 1 0)
Thủ tục lai ghép được viết tương tự như trên.
c. Lai ghép mặt nạ
Loại lai ghép này còn gọi là lai ghép đều; với hai cá thể cha mẹ đã
chọn P1 , P2 trước hết phát sinh một chuỗi nhị phân ngẫu nhiên cũng có
độ dài L gọi là chuỗi mặt nạ. Sau đó các con được tạo ra dựa trên chuỗi
mặt nạ này để quyết định lấy thành phần của cá thể cha hay mẹ. Chẳng
hạn gen thứ i của cá thể con C1 được lấy là gen thứ i của P1 nếu bit
mặt nạ tương ứng là 1 và lấy gen thứ i của P2 nếu bit mặt nạ là 0. Cá
thể con C2 được tạo ngược lại.
Ví dụ: Với
P1 = (1 1 1 0 0 0 1 0 1 0)
P2 = (0 1 0 1 1 0 0 1 1 1)
là hai chuỗi nhị phân độ dài 10, giả sử chuỗi bít nhị phân (mặt nạ) được
khởi tạo ngẫu nhiên là U = (0 1 1 0 0 1 1 0 0 1) thế thì hai con được sinh
ra là :
C1 = (0 1 1 1 1 0 1 1 1 0)
C2 = (0 1 0 0 0 0 0 0 1 1)
tục lai ghép như sau :
Procedure lai_mat_na(U, P1, P2; var C1, C2);
Begin
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
16
For i := 1 to L do
Begin
If U [i] = 1 then
Begin C1[i] := P 1[i]; C2[i] := P 2[i]; End
Else
Begin C1[i] := P 2[i]; C2[i] := P 1[i]; End;
End;
End;
1.3.4
Toán tử đột biến
Toán tử đột biến làm thay đổi các thông tin của quần thể ở mức bit
(gen). Đột biến làm thay đổi giá trị của một bit bất kỳ theo xác suất pm .
Mỗi bit đều có cơ hội đột biến như nhau. Thuật toán đột biến thường
dùng là:
FOR i := 1 TO m DO
IF random[0, 1] < pm THEN invert(P arent[i]);
trong đó invert(u) là hàm đảo ngược bit u.
1.3.5
Hàm phù hợp
Biến đổi hàm mục tiêu thành hàm phù hợp:
Do giá trị phù hợp trong giải thuật di truyền là không âm, nên để áp
dụng GA cho bài toán tối ưu ta cần phải chuyển giá trị hàm mục tiêu
thành hàm phù hợp.
Nếu bài toán tối ưu là cực tiểu hàm mục tiêu g(x) thì ta chuyển sang
hàm phù hợp như sau:
C
max − g(x) g(x) < Cmax
f (x) =
0
ngược lại
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
- Xem thêm -