Giải thuật di truyền (GAs) và các ứng dụng

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

GIẢI THUẬT DI TRUYỀN (GAs) VÀ CÁC ỨNG DỤNG
ThS. Trần Kim Hương
Khoa Sư phạm Toán-Tin, Trường Đại học Đồng Tháp
Email: tkhuong@dthu.edu.vn
ThS. Nguyễn Thị Ngọc Chi
Khoa Sư phạm Toán-Tin, Trường Đại học Đồng Tháp
Tóm tắt. Giải thuật di truyền (GAs) trong lĩnh vực tin học là một trong những
giải thuật thú vị, bởi vì nó mô phỏng qui luật đấu tranh sinh tồn của tự nhiên và
cũng là một giải thuật vô cùng hiệu quả đối với các loại bài toán tối ưu. Trong bài
viết này, chúng tôi trình bày những đặc điểm cơ bản nhất của GAs, nêu một vài ứng
dụng và một số công trình nghiên cứu về GAs đã được công bố ở trong nước.
1. Mở đầu
Nhà bác học Charles Darwin đã nêu ra lý thuyết về sự tiến hóa tự nhiên của các
loài vật, qua nhiều thế hệ sinh vật phát triển dựa trên nguyên lý của sự chọn lọc tự
nhiên “loài nào thích nghi thì sẽ tồn tại”, như ta thấy trong tự nhiên các loài vật sẽ
cạnh tranh nhau về nơi trú ẩn, thực phẩm,…các cá thể cùng loài còn cạnh tranh nhau
để thu hút bạn tình trong mùa sinh sản do đó những cá thể nào ít thích nghi thì ít có
cơ hội tồn tại hơn và những cá thể thích nghi được thì sẽ phát triển và cho ra nhiều
con cái. Trong quá trình sinh sản sẽ tổ hợp các đặc tính tốt từ tổ tiên, sau một vài thế
hệ những loài tiến hóa tự nhiên sẽ thích nghi hơn trong môi trường phát triển. Dựa
trên nền tảng lý thuyết tiến hóa tự nhiên này, đến năm 1975 Holland đã phát triển ý
tưởng này vào hệ thống nhân tạo, ông áp dụng nguyên tắc này để tối ưu hóa các vấn
đề và xây dựng thuật toán di truyền (GAs). Hiện nay GAs được xem như một công
cụ mạnh mẽ để giải quyết các vấn đề về tìm kiếm và tối ưu hóa phức tạp như thời
gian biểu, lập kế hoạch mua sắm, …Trong bài viết này, chúng tôi nêu ra cách thức
hoạt động và các ứng dụng của GAs để giải quyết các bài toán cụ thể.
2. Kết quả chính
2.1 Giải thuật di truyền (GAs)
GAs là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp
cho các bài toán tối ưu tổ hợp (combinatorial optimization), là một phân ngành của
giải thuật tiến hóa, vận dụng các nguyên lý của tiến hóa như: di truyền, đột biến,
chọn lọc tự nhiên, và trao đổi chéo. Nó sử dụng ngôn ngữ máy tính để mô phỏng
quá trình tiến hoá của một tập hợp những đại diện trừu tượng (gọi là những nhiễm
sắc thể), của các giải pháp có thể (gọi là những cá thể) cho bài toán tối ưu hóa vấn
đề. Tập hợp này sẽ tiến triển theo hướng chọn lọc những giải pháp tốt hơn.
GAs cũng như các thuật toán tiến hoá, đều được hình thành dựa trên một quan
niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm “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”. 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 thế hệ trước.
94

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

Ngày nay, GAs càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu hoá,
một lĩnh vực có nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng
thường khó và chưa có phương pháp hiệu quả để giải quyết.
2.1.1 Các tính chất của giải thuật di truyền
GAs là kỹ thuật chung, giúp giải quyết vấn đề bằng cách mô phỏng sự tiến hóa
của con người hay của sinh vật nói chung (dựa trên thuyết tiến hóa muôn loài của
Darwin), trong điều kiện qui định sẵn của môi trường. Mục tiêu của GAs không
nhằm đưa ra lời giải chính xác tối ưu mà là đưa ra lời giải tương đối tối ưu.
Một cá thể trong GAs sẽ biểu diễn một giải pháp của bài toán. Tuy nhiên,
không giống với trong tự nhiên là một cá thể có nhiều nhiễm sắc thể (NST) mà để
giới hạn trong GAs, ta quan niệm một cá thể có một NST. Do đó, khái niệm cá thể
và NST trong GAs coi như là tương đương.
Một NST được tạo thành từ nhiều gen, mỗi gen có thể có các giá trị khác nhau
để quy định một tình trạng nào đó. Trong GAs, một gen được coi như một phần tử
trong chuỗi NST.
Một tập hợp các cá thể có cùng một số đặc điểm nào đấy được gọi là quần thể.
Trong thuật giải di truyền, ta quan niệm quần thể là một tập các lời giải của một bài
toán.
2.1.2 Các bước cơ bản của giải thuật di truyền
Bắt đầu

Nhận các tham số
của bài toán

Khởi tạo quần thể
ban đầu

Tính giá trị thích nghi

Điều kiện
dừng

Sinh sản

Lai ghép

Lựa chọn giải pháp tốt
nhất

Đột biến

Kết
thúc

Hình 1: Sơ đồ thực hiện giải thuật di truyền đơn giản
Như trong hình 1, ta thấy giải thuật di truyền đơn giản được thực hiện qua năm
bước cơ bản sau:
1. [Bắt đầu ] Nhận các tham số cho thuật toán.
2. [Khởi tạo] Sinh ngẫu nhiên một quần thể gồm n cá thể ( là n lời giải cho bài
toán)
95

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

3. [Quần thể mới ] Tạo quần thể mới bằng cách lặp lại các bước sau cho đến
khi quần thể mới hoàn thành
[Thích nghi] Ước lượng độ thích nghi eval(x) của mỗi cá thể.
[Kiểm tra ] Kiểm tra điều kiện kết thúc giải thuật.
[Chọn lọc] Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích nghi của
chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn)
[Lai ghép] Với một xác suất lai ghép được chọn, lai ghép hai cá thể bố
mẹ để tạo ra một cá thể mới.
[Đột biến] Với một xác suất đột biến được chọn, biến đổi cá thể mới
5. [Chọn kết quả] Nếu điều kiện dừng được thỏa mãn thì thuật toán kết thúc và
trả về lời giải tốt nhất trong quần thể hiện tại
GAs có hai loại điều kiện dừng cơ bản (1) dựa trên cấu trúc nhiễm sắc thể,
kiểm soát số gen được hội tụ, nếu số gen hội tụ vượt quá số phần trăm nào đó của
tổng số gen, việc tìm kiếm sẽ kết thúc; (2) dựa trên ý nghĩa đặc biệt của một nhiễm
sắc thể, đo tiến bộ của giải thuật trong một số thế hệ cho trước, nếu tiến bộ này nhỏ
hơn một hằng số ε xác định, kết thúc tìm kiếm.
2.2 Nguyên lý hoạt động
Nền tảng lý thuyết của GAs dựa trên biểu diễn chuỗi nhị phân và lý thuyết sơ
đồ. Một sơ đồ là một chuỗi, dài bằng chuỗi nhiễm sắc thể, các thành phần của nó có
thể nhận một trong các giá trị của tập ký tự biểu diễn gen hoặc một ký tự đại diện
“*”. Sơ đồ biểu diễn một không gian con của không gian tìm kiếm. Không gian con
này là tập tất cả các chuỗi trong không gian lời giải mà với mọi vị trí trong chuỗi giá
trị của gen trùng với giá trị của sơ đồ [1]
Ví dụ: các chuỗi và sơ đồ có chiều dài 10.
Sơ đồ (*111100100) sẽ khớp với hai chuỗi:
{(0111100100), (1111100100)}
Và sơ đồ (*1*1100100) sẽ khớp với 4 chuỗi
{(0101100100), (0111100100), (1101100100), (1111100100)}
Đương nhiên, sơ đồ (1001110001) chỉ khớp với chính nó, và sơ đồ
(**********) khớp với tất cả các chuỗi có chiều dài 10. Rõ ràng là mỗi sơ đồ cụ thể
có tương ứng 2r chuỗi, với r là số ký tự đại diện ‘*’ có trong sơ đồ. Mặc khác, mỗi
chuỗi chiều dài m sẽ khớp với 2m sơ đồ.
Một chuỗi chiều dài m, sẽ có tối đa 2m sơ đồ. Trong một quần thể kích thước n,
có thể có tương ứng từ 2m đến nx2m sơ đồ khác nhau.
Các sơ đồ khác nhau có những đặc trưng khác nhau. Các đặc trưng này thể
hiện qua hai thuộc tính quan trọng bậc và chiều dài xác định.
Bậc của sơ đồ S (ký hiệu σ(S)) là chiều dài của chuỗi trừ đi số ký tự đại diện.
Bậc xác định đặc trưng của sơ đồ.
Ví dụ: ba sơ đồ chiều dài 10
S1=(***001*110)
S2=(****00**0*)
S3=(11101**001)
Có bậc tương ứng:
σ(S1)=6; σ(S2)=3; σ(S3)=8
96

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

Khái niệm bậc của sơ đồ giúp cho việc tính xác suất sống còn của sơ đồ do ảnh
hưởng của đột biến.
Chiều dài xác định của sơ đồ S (ký hiệu là δ(S)) là khoảng cách giữa hai vị trí
cố định ở đầu và cuối. Nó định nghĩa “độ nén” của thông tin chứa trong một sơ đồ.
Ví dụ:
δ(S1)=10-4=6; δ(S2)=9-5=4; δ(S3)=10-1=9
Như vậy, một sơ đồ chỉ có một vị trí cố định duy nhất thì sẽ có chiều dài xác
định là 0
Khái niệm chiều dài xác định của sơ đồ giúp tính xác suất sống còn của sơ đồ
do ảnh hưởng của phép lai.
GAs sử dụng một quần thể của các lời giải có thể. Mỗi lời giải được đại diện
bởi một NST, nó chỉ là một đại diện trừu tượng. Các NST được mã hóa thành các
chuỗi nhị phân, mỗi vị trí trên chuỗi tồn tại hai giá trị là “1” hoặc “0”. Chẳng hạn
như: 1 0 0 1 0 1 0 1 1 0.
Độ tốt của một cá thể được đánh giá bằng hàm mục tiêu g(x) với x là một NST.
Hàm mục tiêu g(x) sau khi được tính toán sẽ là cơ sở để đánh giá độ thích nghi của
cá thể. Hàm thích nghi f(x) là sẽ quyết định khả năng một cá thể được chọn lọc vào
thế hệ sau, việc ánh xạ g(x)→ f(x) có nhiều phương pháp ánh xạ khác nhau phụ
thuộc vào mục đích của bài toán.
2.3 So sánh GAs với kỹ thuật tối ưu khác
Hoạt động của GAs đơn giản là việc mô phỏng sự tiến hóa và chọn lọc tự
nhiên bằng máy tính bắt đầu từ một quần thể ngẫu nhiên. Bên cạnh đó để tối ưu ta
cần hàm lượng giá hoặc hàm thích nghi để chọn cá thể tốt và loại bỏ cá thể xấu.
Thuật toán di truyền (GAs) khác với kĩ thuật tối ưu khác ở chỗ [2]:
– GAs làm việc với bộ mã của biến chứ không phải làm việc trực tiếp trên
biến.
– Hầu hết các kĩ thuật tối ưu thông thường tìm kiếm từ một đỉnh, trong khi đó
GAs luôn hoạt động trên tập hợp đỉnh (điểm tối ưu), điều này là một ưu điểm của
GAs giúp tăng cơ hội tiếp cận tối ưu toàn cục và tránh hội tụ sớm tại điểm cục bộ
địa phương.
– GAs đánh giá hàm mục tiêu để phục vụ quá trình tìm kiếm, vì vậy có thể
ứng dụng cho bất kì bài toán tối ưu nào (liên tục hay rời rạc).
– GAs thuộc lớp các thuật toán xác suất, các thao tác cơ bản của GAs dựa trên
khả năng tích hợp ngẫu nhiên trong quá trình xử lý.
2.4 Ứng dụng của GAs
GAs được sử dụng cho những bài toán khó, và đã được ứng dụng thành công
cho một số bài toán như: lập kế hoạch, điều khiển tương thích, chương trình trò
chơi, các bài toán vận tải, bài toán người đi du lịch,…Sau đây là một vài ứng dụng
tiêu biểu của GAs [1].
 Bài toán người du lịch (TSP)
TSP được mô tả như sau: Một du khách muốn thăm những thành phố anh quan
tâm; mỗi thành phố thăm qua đúng một lần; rồi trở về điểm khởi hành. Biết trước
chi phí di chuyển giữa hai thành phố bất kỳ. Yêu cầu của bài toán là xây dựng một
lộ trình thỏa các điều kiện trên với tổng chi phí nhỏ nhất.

97

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

TSP là bài toán tối ưu tổ hợp, không gian tìm kiếm là tập các hoán vị của n
thành phố. Bất cứ hoán vị nào của n thành phố cũng là một lời giải chấp nhận được.
Lời giải tối ưu là một hoán vị với chi phí tối thiểu của hành trình. Không gian tìm
kiếm là n!. Có thể giải bài toán này bằng nhiều phương pháp: phương pháp nhánh
cận, phương pháp gần đúng hay những phương pháp tìm kiếm heuristic. Phương
pháp nhánh cận đã được chứng minh đạt sự tối ưu về lời giải, tuy nhiên phương
pháp này lại mất khá nhiều thời gian khi số đỉnh của đồ thị lớn.
Trong những năm gần đây, đã xuất hiện nhiều thuật toán đạt gần đến lời giải
tối ưu của bài toán TSP: láng giềng gần nhất, đảo gần nhất, đảo xa nhất…và TSP
cũng trở thành một đích ngắm của cộng đồng GAs.
Với bài toán này chúng ta sẽ đánh số các thành phố và dùng một vector nguyên
để biểu diễn một NST lộ trình v= biểu diễn một lộ trình: từ i1 đến i2…,
từ in-1 đến in và trở về i1 (v là một hoán vị của vector ), hàm lượng giá
chính là chi phí của lộ trình.
 Bài toán lập lịch
Lập lịch là bài toán tổ chức sản xuất. Một công ty cần sản xuất nhiều loại hàng
hóa; những hàng hóa này có thể được sản xuất theo những kế hoạch khác nhau. Mỗi
kế hoạch xử lý gồm một chuỗi thao tác; những thao tác này sử dụng một số tài
nguyên và cần thời gian chạy máy. Một lịch sản xuất là một kế hoạch thực hiện các
đơn đặt hàng. Trong đó, một số đơn đặt hàng có thể được thực hiện với cùng những
thao tác tương đương. Nhiệm vụ là lên kế hoạch, lập lịch sản xuất, để thực hiện các
đơn đặt hàng này nhanh nhất có thể.
Bài toán lập lịch là chọn một chuỗi các thao tác đồng thời chỉ định về thời gian
bắt đầu/ kết thúc và các tài nguyên cần thiết cho mỗi thao tác. Điều cần quan tâm
chính yếu là chi phí thời gian máy rỗi, năng lực lao động và các đơn đặt hàng cần
hoàn thành đúng hạn.Ý tưởng chính trong phương pháp là mã hóa biểu diễn của lịch
phân công là các toán tử di truyền phải thực hiện theo cách có ý nghĩa, và một bộ
giải mã phải luôn tạo ra một lời giải hợp lệ cho bài toán. Thủ tục giải mã mô phỏng
các thao tác của công việc theo cách mà khi một máy tính sẵn sàng chọn lựa, thì
thao tác cho phép đầu tiên từ danh sách ưu tiên được lấy ra. Ví dụ nếu danh sách ưu
tiên của máy m1 là: m1(40 o3 o1 o2 ‘chờ’ ‘nhàn rỗi’), thì thủ tục giải mã vào thời
điểm 40 có thể thực hiện đơn đặt hàng o3 trên máy m1. Nếu không được, thủ tục giải
mã sẽ thực hiện đơn đặt hàng o1 và o2 (nghĩa là, tìm ở o1 trước; nếu không được mới
tìm ở o2). Biểu diễn này bảo đảm tạo một lịch phân công hợp lệ.
 Lập thời khóa biểu cho trường học
Bài toán thời khóa biểu là một bài toán kết hợp nhiều ràng buộc không tầm
thường thuộc nhiều loại. Có nhiều phiên bản của bài toán thời khóa biểu, một trong
những bài toán này có thể được mô tả như sau: Có một danh sách các giáo viên, một
danh sách các khoảng thời gian, một danh sách các lớp. Bài toán cần tìm thời khóa
biểu tối ưu (giáo viên – thời gian – lớp); hàm mục tiêu phải thỏa những mục tiêu này
(các ràng buộc mềm) gồm: Có một số giờ được xác định trước cho mỗi giáo viên và
mỗi lớp; Chỉ một giáo viên trong một lớp vào một giờ nhất định; Một giáo viên
không thể dạy hai lớp cùng lúc; Đối với mỗi lớp được xếp thời khóa biểu vào một
khoảng thời gian, phải có một giáo viên…Ngoài ra còn có các mục tiêu sư phạm
như trải một số lớp ra nguyên tuần, những mục tiêu thuộc cá nhân như những giáo
98

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

GIẢI THUẬT DI TRUYỀN (GAs) VÀ CÁC ỨNG DỤNG
ThS. Trần Kim Hương
Khoa Sư phạm Toán-Tin, Trường Đại học Đồng Tháp
Email: tkhuong@dthu.edu.vn
ThS. Nguyễn Thị Ngọc Chi
Khoa Sư phạm Toán-Tin, Trường Đại học Đồng Tháp
Tóm tắt. Giải thuật di truyền (GAs) trong lĩnh vực tin học là một trong những
giải thuật thú vị, bởi vì nó mô phỏng qui luật đấu tranh sinh tồn của tự nhiên và
cũng là một giải thuật vô cùng hiệu quả đối với các loại bài toán tối ưu. Trong bài
viết này, chúng tôi trình bày những đặc điểm cơ bản nhất của GAs, nêu một vài ứng
dụng và một số công trình nghiên cứu về GAs đã được công bố ở trong nước.
1. Mở đầu
Nhà bác học Charles Darwin đã nêu ra lý thuyết về sự tiến hóa tự nhiên của các
loài vật, qua nhiều thế hệ sinh vật phát triển dựa trên nguyên lý của sự chọn lọc tự
nhiên “loài nào thích nghi thì sẽ tồn tại”, như ta thấy trong tự nhiên các loài vật sẽ
cạnh tranh nhau về nơi trú ẩn, thực phẩm,…các cá thể cùng loài còn cạnh tranh nhau
để thu hút bạn tình trong mùa sinh sản do đó những cá thể nào ít thích nghi thì ít có
cơ hội tồn tại hơn và những cá thể thích nghi được thì sẽ phát triển và cho ra nhiều
con cái. Trong quá trình sinh sản sẽ tổ hợp các đặc tính tốt từ tổ tiên, sau một vài thế
hệ những loài tiến hóa tự nhiên sẽ thích nghi hơn trong môi trường phát triển. Dựa
trên nền tảng lý thuyết tiến hóa tự nhiên này, đến năm 1975 Holland đã phát triển ý
tưởng này vào hệ thống nhân tạo, ông áp dụng nguyên tắc này để tối ưu hóa các vấn
đề và xây dựng thuật toán di truyền (GAs). Hiện nay GAs được xem như một công
cụ mạnh mẽ để giải quyết các vấn đề về tìm kiếm và tối ưu hóa phức tạp như thời
gian biểu, lập kế hoạch mua sắm, …Trong bài viết này, chúng tôi nêu ra cách thức
hoạt động và các ứng dụng của GAs để giải quyết các bài toán cụ thể.
2. Kết quả chính
2.1 Giải thuật di truyền (GAs)
GAs là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp
cho các bài toán tối ưu tổ hợp (combinatorial optimization), là một phân ngành của
giải thuật tiến hóa, vận dụng các nguyên lý của tiến hóa như: di truyền, đột biến,
chọn lọc tự nhiên, và trao đổi chéo. Nó sử dụng ngôn ngữ máy tính để mô phỏng
quá trình tiến hoá của một tập hợp những đại diện trừu tượng (gọi là những nhiễm
sắc thể), của các giải pháp có thể (gọi là những cá thể) cho bài toán tối ưu hóa vấn
đề. Tập hợp này sẽ tiến triển theo hướng chọn lọc những giải pháp tốt hơn.
GAs cũng như các thuật toán tiến hoá, đều được hình thành dựa trên một quan
niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm “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”. 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 thế hệ trước.
94

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

Ngày nay, GAs càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu hoá,
một lĩnh vực có nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng
thường khó và chưa có phương pháp hiệu quả để giải quyết.
2.1.1 Các tính chất của giải thuật di truyền
GAs là kỹ thuật chung, giúp giải quyết vấn đề bằng cách mô phỏng sự tiến hóa
của con người hay của sinh vật nói chung (dựa trên thuyết tiến hóa muôn loài của
Darwin), trong điều kiện qui định sẵn của môi trường. Mục tiêu của GAs không
nhằm đưa ra lời giải chính xác tối ưu mà là đưa ra lời giải tương đối tối ưu.
Một cá thể trong GAs sẽ biểu diễn một giải pháp của bài toán. Tuy nhiên,
không giống với trong tự nhiên là một cá thể có nhiều nhiễm sắc thể (NST) mà để
giới hạn trong GAs, ta quan niệm một cá thể có một NST. Do đó, khái niệm cá thể
và NST trong GAs coi như là tương đương.
Một NST được tạo thành từ nhiều gen, mỗi gen có thể có các giá trị khác nhau
để quy định một tình trạng nào đó. Trong GAs, một gen được coi như một phần tử
trong chuỗi NST.
Một tập hợp các cá thể có cùng một số đặc điểm nào đấy được gọi là quần thể.
Trong thuật giải di truyền, ta quan niệm quần thể là một tập các lời giải của một bài
toán.
2.1.2 Các bước cơ bản của giải thuật di truyền
Bắt đầu

Nhận các tham số
của bài toán

Khởi tạo quần thể
ban đầu

Tính giá trị thích nghi

Điều kiện
dừng

Sinh sản

Lai ghép

Lựa chọn giải pháp tốt
nhất

Đột biến

Kết
thúc

Hình 1: Sơ đồ thực hiện giải thuật di truyền đơn giản
Như trong hình 1, ta thấy giải thuật di truyền đơn giản được thực hiện qua năm
bước cơ bản sau:
1. [Bắt đầu ] Nhận các tham số cho thuật toán.
2. [Khởi tạo] Sinh ngẫu nhiên một quần thể gồm n cá thể ( là n lời giải cho bài
toán)
95

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

3. [Quần thể mới ] Tạo quần thể mới bằng cách lặp lại các bước sau cho đến
khi quần thể mới hoàn thành
[Thích nghi] Ước lượng độ thích nghi eval(x) của mỗi cá thể.
[Kiểm tra ] Kiểm tra điều kiện kết thúc giải thuật.
[Chọn lọc] Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích nghi của
chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn)
[Lai ghép] Với một xác suất lai ghép được chọn, lai ghép hai cá thể bố
mẹ để tạo ra một cá thể mới.
[Đột biến] Với một xác suất đột biến được chọn, biến đổi cá thể mới
5. [Chọn kết quả] Nếu điều kiện dừng được thỏa mãn thì thuật toán kết thúc và
trả về lời giải tốt nhất trong quần thể hiện tại
GAs có hai loại điều kiện dừng cơ bản (1) dựa trên cấu trúc nhiễm sắc thể,
kiểm soát số gen được hội tụ, nếu số gen hội tụ vượt quá số phần trăm nào đó của
tổng số gen, việc tìm kiếm sẽ kết thúc; (2) dựa trên ý nghĩa đặc biệt của một nhiễm
sắc thể, đo tiến bộ của giải thuật trong một số thế hệ cho trước, nếu tiến bộ này nhỏ
hơn một hằng số ε xác định, kết thúc tìm kiếm.
2.2 Nguyên lý hoạt động
Nền tảng lý thuyết của GAs dựa trên biểu diễn chuỗi nhị phân và lý thuyết sơ
đồ. Một sơ đồ là một chuỗi, dài bằng chuỗi nhiễm sắc thể, các thành phần của nó có
thể nhận một trong các giá trị của tập ký tự biểu diễn gen hoặc một ký tự đại diện
“*”. Sơ đồ biểu diễn một không gian con của không gian tìm kiếm. Không gian con
này là tập tất cả các chuỗi trong không gian lời giải mà với mọi vị trí trong chuỗi giá
trị của gen trùng với giá trị của sơ đồ [1]
Ví dụ: các chuỗi và sơ đồ có chiều dài 10.
Sơ đồ (*111100100) sẽ khớp với hai chuỗi:
{(0111100100), (1111100100)}
Và sơ đồ (*1*1100100) sẽ khớp với 4 chuỗi
{(0101100100), (0111100100), (1101100100), (1111100100)}
Đương nhiên, sơ đồ (1001110001) chỉ khớp với chính nó, và sơ đồ
(**********) khớp với tất cả các chuỗi có chiều dài 10. Rõ ràng là mỗi sơ đồ cụ thể
có tương ứng 2r chuỗi, với r là số ký tự đại diện ‘*’ có trong sơ đồ. Mặc khác, mỗi
chuỗi chiều dài m sẽ khớp với 2m sơ đồ.
Một chuỗi chiều dài m, sẽ có tối đa 2m sơ đồ. Trong một quần thể kích thước n,
có thể có tương ứng từ 2m đến nx2m sơ đồ khác nhau.
Các sơ đồ khác nhau có những đặc trưng khác nhau. Các đặc trưng này thể
hiện qua hai thuộc tính quan trọng bậc và chiều dài xác định.
Bậc của sơ đồ S (ký hiệu σ(S)) là chiều dài của chuỗi trừ đi số ký tự đại diện.
Bậc xác định đặc trưng của sơ đồ.
Ví dụ: ba sơ đồ chiều dài 10
S1=(***001*110)
S2=(****00**0*)
S3=(11101**001)
Có bậc tương ứng:
σ(S1)=6; σ(S2)=3; σ(S3)=8
96

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

Khái niệm bậc của sơ đồ giúp cho việc tính xác suất sống còn của sơ đồ do ảnh
hưởng của đột biến.
Chiều dài xác định của sơ đồ S (ký hiệu là δ(S)) là khoảng cách giữa hai vị trí
cố định ở đầu và cuối. Nó định nghĩa “độ nén” của thông tin chứa trong một sơ đồ.
Ví dụ:
δ(S1)=10-4=6; δ(S2)=9-5=4; δ(S3)=10-1=9
Như vậy, một sơ đồ chỉ có một vị trí cố định duy nhất thì sẽ có chiều dài xác
định là 0
Khái niệm chiều dài xác định của sơ đồ giúp tính xác suất sống còn của sơ đồ
do ảnh hưởng của phép lai.
GAs sử dụng một quần thể của các lời giải có thể. Mỗi lời giải được đại diện
bởi một NST, nó chỉ là một đại diện trừu tượng. Các NST được mã hóa thành các
chuỗi nhị phân, mỗi vị trí trên chuỗi tồn tại hai giá trị là “1” hoặc “0”. Chẳng hạn
như: 1 0 0 1 0 1 0 1 1 0.
Độ tốt của một cá thể được đánh giá bằng hàm mục tiêu g(x) với x là một NST.
Hàm mục tiêu g(x) sau khi được tính toán sẽ là cơ sở để đánh giá độ thích nghi của
cá thể. Hàm thích nghi f(x) là sẽ quyết định khả năng một cá thể được chọn lọc vào
thế hệ sau, việc ánh xạ g(x)→ f(x) có nhiều phương pháp ánh xạ khác nhau phụ
thuộc vào mục đích của bài toán.
2.3 So sánh GAs với kỹ thuật tối ưu khác
Hoạt động của GAs đơn giản là việc mô phỏng sự tiến hóa và chọn lọc tự
nhiên bằng máy tính bắt đầu từ một quần thể ngẫu nhiên. Bên cạnh đó để tối ưu ta
cần hàm lượng giá hoặc hàm thích nghi để chọn cá thể tốt và loại bỏ cá thể xấu.
Thuật toán di truyền (GAs) khác với kĩ thuật tối ưu khác ở chỗ [2]:
– GAs làm việc với bộ mã của biến chứ không phải làm việc trực tiếp trên
biến.
– Hầu hết các kĩ thuật tối ưu thông thường tìm kiếm từ một đỉnh, trong khi đó
GAs luôn hoạt động trên tập hợp đỉnh (điểm tối ưu), điều này là một ưu điểm của
GAs giúp tăng cơ hội tiếp cận tối ưu toàn cục và tránh hội tụ sớm tại điểm cục bộ
địa phương.
– GAs đánh giá hàm mục tiêu để phục vụ quá trình tìm kiếm, vì vậy có thể
ứng dụng cho bất kì bài toán tối ưu nào (liên tục hay rời rạc).
– GAs thuộc lớp các thuật toán xác suất, các thao tác cơ bản của GAs dựa trên
khả năng tích hợp ngẫu nhiên trong quá trình xử lý.
2.4 Ứng dụng của GAs
GAs được sử dụng cho những bài toán khó, và đã được ứng dụng thành công
cho một số bài toán như: lập kế hoạch, điều khiển tương thích, chương trình trò
chơi, các bài toán vận tải, bài toán người đi du lịch,…Sau đây là một vài ứng dụng
tiêu biểu của GAs [1].
 Bài toán người du lịch (TSP)
TSP được mô tả như sau: Một du khách muốn thăm những thành phố anh quan
tâm; mỗi thành phố thăm qua đúng một lần; rồi trở về điểm khởi hành. Biết trước
chi phí di chuyển giữa hai thành phố bất kỳ. Yêu cầu của bài toán là xây dựng một
lộ trình thỏa các điều kiện trên với tổng chi phí nhỏ nhất.

97

HỘI NGHỊ NCKH KHOA SP TOÁN-TIN

THÁNG 05/2015

TSP là bài toán tối ưu tổ hợp, không gian tìm kiếm là tập các hoán vị của n
thành phố. Bất cứ hoán vị nào của n thành phố cũng là một lời giải chấp nhận được.
Lời giải tối ưu là một hoán vị với chi phí tối thiểu của hành trình. Không gian tìm
kiếm là n!. Có thể giải bài toán này bằng nhiều phương pháp: phương pháp nhánh
cận, phương pháp gần đúng hay những phương pháp tìm kiếm heuristic. Phương
pháp nhánh cận đã được chứng minh đạt sự tối ưu về lời giải, tuy nhiên phương
pháp này lại mất khá nhiều thời gian khi số đỉnh của đồ thị lớn.
Trong những năm gần đây, đã xuất hiện nhiều thuật toán đạt gần đến lời giải
tối ưu của bài toán TSP: láng giềng gần nhất, đảo gần nhất, đảo xa nhất…và TSP
cũng trở thành một đích ngắm của cộng đồng GAs.
Với bài toán này chúng ta sẽ đánh số các thành phố và dùng một vector nguyên
để biểu diễn một NST lộ trình v= biểu diễn một lộ trình: từ i1 đến i2…,
từ in-1 đến in và trở về i1 (v là một hoán vị của vector ), hàm lượng giá
chính là chi phí của lộ trình.
 Bài toán lập lịch
Lập lịch là bài toán tổ chức sản xuất. Một công ty cần sản xuất nhiều loại hàng
hóa; những hàng hóa này có thể được sản xuất theo những kế hoạch khác nhau. Mỗi
kế hoạch xử lý gồm một chuỗi thao tác; những thao tác này sử dụng một số tài
nguyên và cần thời gian chạy máy. Một lịch sản xuất là một kế hoạch thực hiện các
đơn đặt hàng. Trong đó, một số đơn đặt hàng có thể được thực hiện với cùng những
thao tác tương đương. Nhiệm vụ là lên kế hoạch, lập lịch sản xuất, để thực hiện các
đơn đặt hàng này nhanh nhất có thể.
Bài toán lập lịch là chọn một chuỗi các thao tác đồng thời chỉ định về thời gian
bắt đầu/ kết thúc và các tài nguyên cần thiết cho mỗi thao tác. Điều cần quan tâm
chính yếu là chi phí thời gian máy rỗi, năng lực lao động và các đơn đặt hàng cần
hoàn thành đúng hạn.Ý tưởng chính trong phương pháp là mã hóa biểu diễn của lịch
phân công là các toán tử di truyền phải thực hiện theo cách có ý nghĩa, và một bộ
giải mã phải luôn tạo ra một lời giải hợp lệ cho bài toán. Thủ tục giải mã mô phỏng
các thao tác của công việc theo cách mà khi một máy tính sẵn sàng chọn lựa, thì
thao tác cho phép đầu tiên từ danh sách ưu tiên được lấy ra. Ví dụ nếu danh sách ưu
tiên của máy m1 là: m1(40 o3 o1 o2 ‘chờ’ ‘nhàn rỗi’), thì thủ tục giải mã vào thời
điểm 40 có thể thực hiện đơn đặt hàng o3 trên máy m1. Nếu không được, thủ tục giải
mã sẽ thực hiện đơn đặt hàng o1 và o2 (nghĩa là, tìm ở o1 trước; nếu không được mới
tìm ở o2). Biểu diễn này bảo đảm tạo một lịch phân công hợp lệ.
 Lập thời khóa biểu cho trường học
Bài toán thời khóa biểu là một bài toán kết hợp nhiều ràng buộc không tầm
thường thuộc nhiều loại. Có nhiều phiên bản của bài toán thời khóa biểu, một trong
những bài toán này có thể được mô tả như sau: Có một danh sách các giáo viên, một
danh sách các khoảng thời gian, một danh sách các lớp. Bài toán cần tìm thời khóa
biểu tối ưu (giáo viên – thời gian – lớp); hàm mục tiêu phải thỏa những mục tiêu này
(các ràng buộc mềm) gồm: Có một số giờ được xác định trước cho mỗi giáo viên và
mỗi lớp; Chỉ một giáo viên trong một lớp vào một giờ nhất định; Một giáo viên
không thể dạy hai lớp cùng lúc; Đối với mỗi lớp được xếp thời khóa biểu vào một
khoảng thời gian, phải có một giáo viên…Ngoài ra còn có các mục tiêu sư phạm
như trải một số lớp ra nguyên tuần, những mục tiêu thuộc cá nhân như những giáo
98

5/5 - (1 vote)
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments