Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
o0o
THUẬT TOÁN VÀ
THUẬT TOÁN VÀ
PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
THUẬT GIẢI DI TRUYỀN
THUẬT GIẢI DI TRUYỀN
VÀ ỨNG DỤNG
VÀ ỨNG DỤNG
TRONG BÀI TOÁN LẬP LỊCH
TRONG BÀI TOÁN LẬP LỊCH
GVHD : PGS. TS. ĐỖ VĂN NHƠN
HVTH : NGUYỄN THỊ MAI
MÃ HV : CH1301038
LỚP : CH KHÓA 8
Tp. HCM, Thaùng 01 naêm 2014
SVTH: Nguyễn Thị Mai 1
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
MỤC LỤC
SVTH: Nguyễn Thị Mai 2
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
LỜI CẢM ƠN
Em xin chân thành cảm ơn thầy PGS.TS Đỗ Văn Nhơn đã cung cấp cho em
những kiến thức quan trọng, nền tảng, giúp em định hướng tìm tòi, học tập và nắm
vững hơn những phương pháp giải quyết vấn đề, những thuật toán cơ bản và mở
rộng để ứng dụng vào những bài toán cụ thể trên máy tính và trong thực tế.
Trong bài này em xin trình bày nội dung về giải thuật di truyền qua những tìm
hiểu từ các giáo trình, bài báo, tài liệu và ứng dụng của thuật giải di truyền vào bài

- Khởi tạo quần thể ban đầu gồm N cá thể một cách ngẫu nhiên.
- Xây dựng hàm thích nghi làm tiêu chuẩn đánh giá cá thể
- Xác định xác suất lai tạo, xác suất đột biến.
- Xây dựng các phép lai tạo, chọn lọc, đột biến.
2. Các thành phần cơ bản của GA
Trong GA, một tập các biến của bài toán đưa ra được mã hóa sang một chuỗi
(hay một cấu trúc mã hóa khác) tương tự như một nhiễm sắc thể trong tự nhiên. Mỗi
chuỗi bao gồm một giải pháp có thể của bài toán. Giải thuật di truyền sử dụng các
toán tử được sinh ra bởi sự chọc lọc tự nhiên một quần thể các chuỗi nhị phân (hoặc
các cấu trúc khác), mã hóa khoảng tham số trên mỗi thế hệ, khảo sát các phạm vi
SVTH: Nguyễn Thị Mai 4
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
khác nhau của không gian tham số, và định hướng tìm kiếm đối với khoảng mà là
xác suất cao để tìm kiếm sự thực hiện tốt hơn. Thuật toán di truyền gồm có bốn quy
luật cơ bản là lai ghép, đột biến, sinh sản và chọn lọc tự nhiên. Sau đây, ta sẽ đi vào
chi tiết từ khâu đầu tiên là biểu diễn các cá thể.
2.1 Biểu diễn các cá thể
Biểu diễn cá thể là ánh xạ các tham số của bài toán lên một chuỗi có chiều dài
xác định. Khi thực hiện giải bài toán bằng thuật giải di truyền, việc đầu tiên ta cần
làm là xác định cách biểu diễn các cá thể. Tùy theo từng bài toán cụ thể mà có
những cách biểu diễn khác nhau sao cho phù hợp, thuận lợi khi giải toán.
2.1.1 Biểu diễn nhị phân
Mỗi cá thể tương ứng với một chuỗi bao gồm các bit 0 và 1. Ý nghĩa của các bit
này phụ thuộc vào từng tình huống cụ thể. Đây là cách biểu diễn đơn giản nhất và
thông dụng nhất.
Ví dụ 1: hai NST được biểu diễn dưới dạng nhị phân như sau:
Ví dụ 2: Cho bài toán: có n đồ vật với trọng lượng và giá trị khác nhau được cho
trước trong một cái túi có trọng lượng đã biết. Yêu cầu: hãy chọn ra các đồ vật để
cho vào túi sao cho tổng giá trị các đồ vật trong túi là lớn nhất.
Trong trường hợp này, ta đánh số đồ vật từ 1 đến n, mỗi cá thể được biểu diễn

T
5
T
9
T
3
… là ký hiệu của hành trình từ T
8
T
5
T
9
T
3
…
Như vậy, mỗi chuỗi con sẽ biểu diễn cho một đỉnh của không gian tìm kiếm và
qua đó thể hiện được cách trả lời có thể có của bài toán. Sau đó, mỗi chuỗi NST sẽ
được giải mã lại để trả về các thông số ban đầu của bài toán.
2.1.3 Biểu diễn bằng giá trị
Phương pháp này thường được dùng trong các bài toán có chứa những giá trị
phức tạp. Trong mã hóa giá trị, mọi NST là một chuỗi chứa những giá trị nào đó.
Những giá trị này có thể có dạng bất kỳ liên quan đến bài toán, từ số nguyên, số
thực, ký tự cho đến các đối tượng phức tạp hơn.
Ví dụ: Ta biểu diễn 3 NST bằng giá trị như sau:
NST A được biểu diễn dưới dạng số thực
NST B được biểu diễn dưới dạng chuỗi ký tự
NST C được biểu diễn dưới dạng danh sách thuộc tính
2.1.4 Biểu diễn dưới dạng cây
Mã hóa theo cây được dùng chủ yếu cho các chương trình ( hoặc biểu thức) tiến
hóa, cho lập trình gen Trong mã hóa theo cây, mọi NST là một cây chứa các đối

và m
2
. Hai chuỗi nhiễm sắc thể con lúc này sẽ là m
11
+m
22
và m
21
+m
12
 Đưa hai cá thể mới này vào quẩn thể để tham gia các quá trình tiến
hóa tiếp theo.
2.4 Quá trình sinh sản (tái sinh)
Phép tái sinh: là quá trình các cá thể được sao chép dựa trên độ thích nghi của
nó. Phép tái sinh có thể mô phỏng như sau:
SVTH: Nguyễn Thị Mai 7
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
 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 thỏa mãn F ≥ Ftk đưa vào quần thể của thế hệ
mới.
Ví dụ: Mỗi cặp bố mẹ sinh hai con theo một trong hai phương pháp sau
 Vô tính
• Mỗi ấu nhi là một bản sao chính xác từ cha
• Mỗi ấu nhi là một bản sao chính xác từ mẹ
 Hữu tính (giao nhau)
• Một vài bits được sao từ mẹ, vài bits được sao chép từ cha

00001010101
11101010101
00001001000
11111000000
11101001000
00001010101
11001011000
00101000101
00111110000
11101001000
00001010101
10001000100
01101011001
00111110000
11101001000 11101011000
Các chuỗi ban đầu Mặt nạ lai ghép Các cá thể con
Lai ghép điểm đơn:
Lai ghép điểm kép:
Lai ghép đồng nhất:
Đột biến điểm:
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
3. Các toán tử
Hình 1. Các toán tử chung cho thuật giải di truyền
3.1 Toán tử chọn lọc
Mục đích của việc chọn này nhằm nhấn mạnh sự lọc cá thể trong quần thể
và hi vọng tạo ra quần thể con của nó có giá trị thích nghi cao hơn.
- Chọn lọc Bánh xe Roulette (Roulette Wheel Selection)
Công thức:
Trong đó, là giá trị thích nghi của cá thể
SVTH: Nguyễn Thị Mai 10

 Ví dụ là giá trị thích nghi cao nhất hiện tại. Nếu cá thể tiếp
theo có độ thích nghi mà > thì cá thể này được chọn vì cá thể
này được chọn với xác suất Boltzmann:
Trong đó: , g là số lượng generate hiện tại, G
là số lượng tối đa của g. Giá trị α được chọn nằm trong đoạn [0, 1]. Dừng lại
khi T = 0.
- Lấy mẫu ngẫu nhiên (Stochastic Universal Sampling)
SVTH: Nguyễn Thị Mai 12
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
Nếu muốn chọn ra N mẫu thì khoảng các giữa các mẫu được chọn là 1/N.
Ta cần tạo ngẫu nhiên một số = [0,1/N]. Số này là vị trí được chọn trong
quần thể tức là từ vị trí N, lấy N phần tử trong quần thể.
3.2 Toán tử đột biến
- Flip bit: chuyển đổi giá trị của gen được chọn. Ví dụ từ 0 đổi thành 1 và từ 1
đổi thành 0. Toán tử này chỉ được sử dụng với các gen nhị phân.
Cho hai chuỗi được chọn để đột biến:
Đảo giá trị của gen đã chọn từ 0 sang 1 và từ 1 thành 0. Kết quả của chuỗi đã
được đột biết là:

- Boundary (Giới hạn): Phép đột biến thay thế giá trị của gen đã chọn với giới
hạn tăng hoặc giảm. Toán tử này có thể sử dụng cho gen ở kiểu integer hoặc
float.
- Gaussian: Toán tử thêm một đơn vị giá trị phân phối ngẫu nhiên Gauss vào
gen đã chọn. Giá trị gen mới bị loại bỏ khỏi giới hạn trên và dưới của gen đó.
Toán tử này chỉ dùng cho gen kiểu integer và float.
3.3 Toán tử lai ghép
- Lai ghép một điểm (one-point crossover): lựa chọn ngẫu nhiên một điểm lai
ghép. Sau đó, sao chép toàn bộ phần trước điểm lai ghép của NST cha. Phần sau
điểm lai ghép được sao chép từ NST còn lại.
Ví dụ: Cho hai NST cha để lai ghép.

tìm r và cho ra NST con đáng tin cậy. Nếu sau n lần thử mà không tạo ra NST
con đáng tin cậy nào, NST cha xấu nhất được trả về như offstring1.
4. Các tham số
Xác suất lai ghép: là tham số cho biết tần suất thực hiện toán tử lai ghép. Nếu
không có lai ghép, cá thể con sẽ chính là bản sao của cá thể “cha mẹ”. Nếu xác suất
lai ghép bằng 100%, khi đó mọi cá thể con đều được tạo ra qua quá trình lai ghép.
Xác suất đột biến: là tham số cho biết tần suất đột biến của nhiễm sắc thể. Nếu
không có đột biến, thế hệ con được tạo ra ngay sau giai đoạn lai ghép mà không bị
thay đổi. Ngược lại, một hoặc một số phần của nhiễm sắc thể sẽ bị thay đổi. Nếu
xác suất đột biến là 100%, toàn bộ nhiễm sắc thể sẽ bị thay đổi. Nếu tham số này
bằng 0%, không có gì bị thay đổi hết
Kích thước quần thể: là tham số cho biết có bao nhiêu cá thể (NST) trong 1 thế
hệ của quần thể. Nếu có quá ít cá thể, khả năng thực hiện lai ghép rất nhỏ và khi đó
chỉ có một vùng tìm kiếm nhỏ mới được khảo sát. Ngược lại, việc kích thước quần
thể quá lớn cũng không tốt, do nó sẽ làm chậm quá trình giải bài toán.
5. Công thức
Tính độ thích nghi của mỗi nhiễm sắc thể v
i
(i=1… n)
SVTH: Nguyễn Thị Mai 15
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
n: kích thước quần thể
:hàm mục tiêu
Tìm tổng giá trị thích nghi của quần thể
Tính xác xuất chọn P
i
cho mỗI nhiễm sắc thể v
i
Tính xác suất tích luỹ p
i

động khác nhau. Trước một bài toán áp dụng thuật giải di truyền, ta cần phải xác
định rõ nhiễm sắc thể và cá thể cho vấn đề, và thông thường đó sẽ kết quả cuối
cùng. Việc phân tích sẽ dựa trên kết quả là cơ bản nhất.
Giai đoạn 2: Đánh giá cá thể
SVTH: Nguyễn Thị Mai 17
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
Chắc chắn rằng việc chọn cá thể sẽ thông qua kết quả, hay mục đích của vấn
đề. Dựa trên mức độ thích nghi của cá thể, bao gồm những vướng mắc mà cá thể
gặp phải. Thông thường, đặt mỗi vấn đề nhỏ tương ứng với một giá trị điểm thích
nghi, kết quả đánh giá gồm tổng các số điểm đó. Cá thể tốt nhất sẽ có số điểm thấp
nhất hoặc lớn nhất. Theo thuyết tiến hóa của Darwin, nhiễm sắc thể tốt nhất sẽ tồn
tại và tạo ra các cá thể con mới.
Giai đoạn 3: Lai ghép
Lai ghép nhằm nâng cao kết quả cá thể, do đó, toán tử lai ghép sẽ tạo điều
kiện cho tiến trình hội tụ nhanh hay chậm. Còn tùy thuộc vào cách tổ chức và phân
bố các nhiễm sắc thể mà chúng ta có xác suất lai ghép nhanh hay chậm.
Giai đoạn 4: Đột biến
Cũng giống như lai ghép, toán tử đột biến làm tăng nhanh quá trình hội tụ,
nhưng tăng một cách đột ngột, cũng có khi sẽ không gây tác dụng gì một khi không
thành công. Không ai có thể đánh giá được phương pháp đột biến nào tốt hơn, do đó
có một vài phương pháp đơn giản, cũng có vài trường hợp khá phức tạp.
Giai đoạn 5: Xét Điều kiện kết thúc
Thoát ra quá trình tiến hóa quần thể, dựa vào bài toán mà có các cách kết
thúc vấn đề khác nhau, một khi đã đạt đến mức yêu cầu. Một vài trường hợp thông
thường như sau:
-Kết thúc theo kết quả: một khi đạt đến mức giá trị yêu cầu thì chấm dứt
ngay quá trình thực hiện.
-Kết thúc dựa vào số thế hệ: chọn số thế hệ, quá trình sẽ dừng đúng ngay số
thế hệ đã qui định trước, không cần biết kết quả như thế nào.
SVTH: Nguyễn Thị Mai 18

 Danh sách khoa
 Danh sách khoá học
 Danh sách học phần học và các lớp trong học kỳ
 Danh sách lớp học
 Danh sách giáo viên
 Danh sách phòng học
 Danh sách môn học và số tiết
 Bảng phân công giáo viên giảng dạy tại các lớp
 Bảng yêu cầu ràng buộc của giáo viên vớI lịch dạy
 Bảng yêu cầu ràng buộc của lớp với lịch học
 Bảng yêu cầu ràng buộc của phòng với lịch sử dụng phòng đó
4. Hướng giải quyết bài toán
4.1 Ý tưởng
Dựa vào thuật toán di truyền cổ điển.
Cấu trúc dữ liệu: Một lịch là một ma trận với n cột và K dòng (số lớp). Mỗi phần
tử của ma trận chỉ ra rằng giáo viên dạy lớp này đang dạy môn nào đó.
Minh họa cấu trúc dữ liệu
SVTH: Nguyễn Thị Mai 20
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
SVTH: Nguyễn Thị Mai 21
Thuật toán và phương pháp giải quyết GVHD: PGS.TS Đỗ Văn Nhơn
4.2 Các ràng buộc
 Ràng buộc cứng:
 Một giáo viên chỉ dạy được một lớp trong cùng một quãng thời gian.
 Các lớp chỉ có một môn học trong cùng một quãng thời gian
 Tất cả các bài học của một môn nào đó dạy tại một lớp phải được dạy
bởi cùng một giáo viên.
 Một giáo viên không thể dạy quá 20 giờ mỗi tuần.
 Ràng buộc mềm:
 Một lớp có thể có các giờ trống

vấn đề cơ bản phức tạp của những đối tượng liên quan tới việc học của lớp.
Khi đã có được kết quả cuối cùng là lịch học cho từng lớp một cách hoàn
chỉnh, chúng sẽ được dùng làm thông tin cho giai đoạn sau.
 Giai đoạn 2 : tổng hợp lại các ràng buộc còn lại và đã được đơn giản hóa
trong giai đoạn trước. Kết quả của giai đoạn này chính là mục tiêu cuối cùng
của bài toán. Đó là lịch học của các lớp trong một cơ sở.
Cả hai giai đoạn tuy có mục tiêu và dữ liệu khác nhau, nhưng về cách giải
quyết có tính tương tự nhau, nên không khác gì nhiều khi áp dụng vào mô hình
thuật giải di truyền.
Giai đoạn 1 - Xếp lịch học các lớp
Chọn mô hình cá thể lớp học
Lịch học của một lớp có hai thành phần chính, bao gồm: các môn học và các giờ
học trong tuần. Việc đặt ngẫu nhiên các môn học với các giờ học sẽ tạo thành một
lịch học cho từng lớp. Như vậy một lớp học tương ứng sẽ có nhiều lịch học khác
nhau, do đó ta chọn mỗi lịch học làm cá thể trong thuật giải di truyền.
Và trong hai thành phần đó, thì các giờ học là thành phần ổn định hơn về số
lượng cũng như về giá trị của chúng, cho nên ta chọn môn học làm đơn vị nhiễm
sắc thể trong cá thể. Vì đối với môn học việc làm nhiễm sắc thể là phù hợp với tính
không ổn định của nó : với số lượng các môn phụ thuộc từng lớp học, cũng giống
như số lượng nhiễm sắc thể trong cá thể, có chiều dài không nhất thiết phải cố định
hay bằng nhau. Ngoài ra chưa kể đến tính phức tạp của môn học về số tiết phải học
luôn bị thay đổi, trong khi giá trị các giờ học thì ngược lại, có thể xác định một cách
rõ ràng và nhanh chóng.
Mô hình cá thể trong lịch lớp
SVTH: Nguyễn Thị Mai 25