ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH MÔN:
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
ĐỀ TÀI:
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN
CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
Giảng viên phụ trách: PGS, TS. ĐỖ VĂN NHƠN
Học viên thực hiện: Lê Phước Vinh
Mã học viên: CH1301116
TP. HỒ CHÍ MINH, THÁNG 10/2014
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
MỤC LỤC
DANH MỤC HÌNH 4
MỞ ĐẦU 5
I. Tổng quan về thuật giải Di truyền: 6
1. Thuật giải Di truyền: 6
2. Các yếu tố của thuật toán Di truyền đơn giản 6
3. Sơ đồ thực hiện thuật giải Di truyền 8
4. Mở rộng thuật giải Di truyền 9
5. Thuật giải Di truyền so với các phương pháp truyền thống 11
6. Các ứng dụng của thuật giải Di truyền 12
6.1. Tối ưu hoá và máy học: 12
6.2. Ghi ảnh y học với Thuật giải Di truyền 12
6.3. Bài toán sắp xếp lịch trực 13
6.4. Một số ứng dụng khác 13
II. Bài toán xếp lịch trực ở tổng đài 14
1. Giới thiệu bài toán xếp lịch trực 14
2. Quy trình, các ràng buộc và mô hình toán học 14
2.1. Mô tả quy trình làm việc ở tổng đài 14
2.2. Mô hình toán học 15

Intelligent) trong đó có Thuật giải Di truyền (Geneic Algorithms - GA) đã đem lại
những phương pháp mới để giải các bài toán mà nếu áp dụng phương pháp truyền
thống sẽ gặp nhiều khó khăn hoặc sẽ tốn nhiều chi phí.
Xuất phát từ nhu cầu thực tế Công ty FPT cần xếp lịch trực tổng đài cho các nhân
viên của công ty trong 1 tuần, 1 tháng. Trong nội dung bài thu hoạch này tôi xin trình
bày việc ứng dụng giải thuật Di truyền để giải quyết vấn đề trên.
2. Sự cần thiết của vấn đề:
Trong lĩnh vực lập lịch (hay lập thời khóa biểu), giải thuật Di truyền đã thu hút
được rất nhiều các nghiên cứu và đề xuất. Lý do cho xu hướng này có thể thấy là bài
toán lập lịch nhìn chung thuộc lớp các bài toán NP-khó (NP hard) và vì vậy, rất cần
các giải thuật xấp xỉ.
Về cơ bản, bài toán lập lịch được coi như là việc gán các mốc thời gian (time
slots) thực hiện cho các công việc (tasks) sao cho phù hợp với khả năng về tài nguyên
(resources). Tuy nhiên, sự đa dạng thể hiện ở các thể loại ràng buộc khác nhau và mỗi
một bài toán thực tế sẽ có những ràng buộc đặc trưng riêng.
3. Tổng lược kết quả đã có:
Các nghiên cứu đề xuất giải thuật Di truyền cho bài toán lập lịch luôn luôn là một
chủ đề nóng. Mục đích chính của chuyên đề này là tìm hiểu Thuật giải Di truyền, từ đó
đưa ra các phân tích, mô hình toán học, và cuối cùng là cài đặt cụ thể cho bài toán Xếp
lịch ở tổng đài FPT Telecom để thấy được tính khả thi khi áp dụng vào thực tế ở tổng
đài FPT.
Tôi xin chân thành cảm ơn thầy PGS, TS. Đỗ Văn Nhơn đã tận tình giảng dạy
giúp tôi hoàn thành tốt bài thu hoạch này.
GVHD: PGS, TS. Đỗ Văn Nhơn HVTH: Lê Phước Vinh, Mã HV: CH1301116
5
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
I. Tổng quan về thuật giải Di truyền:
1. Thuật giải Di truyền:
Giải thuật Di truyền (GA) là một trong những mô hình tính toán phổ biến và
thành công nhất trong lĩnh vực tính toán thông minh. Cùng với các kỹ thuật tính

1
a
2
a
L
. Thường
GVHD: PGS, TS. Đỗ Văn Nhơn HVTH: Lê Phước Vinh, Mã HV: CH1301116
6
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
thì nó là các ký tự nhị phân tuy nhiên cũng có thể là các ký tự mở rộng của bảng
chữ cái, thỉnh thoảng sử dụng đọc số.
Thuật toán Di truyền sử dụng ngôn ngữ riêng để mô tả, chuỗi A được gọi là
nhiễm sắc thể, những thành phần của chuỗi như a
1
, a
2
, được gọi là gen, giá trị mà
gen nhận được gọi là thuộc tính gen, trong hầu hết các chuỗi nhị phân phổ biến là
0 hoặc 1, ví dụ như trong nhiễm sắc thể A= 11110000 thì 4 gen đầu có thuộc tính
1 còn 4 gen sau có thuộc tính 0.
Fitness Function (hàm mục tiêu): Fitness Function có nhiệm vụ tìm ra chuỗi
tối ưu. Tính chất tốt của chuỗi được đặc trưng trong GA ở chức năng của nó, các
tính chất này được gọi là chức năng mục tiêu (objective function) và số lượng sẽ
được tối ưu hóa. Một chức năng cần thiết được dùng gọi là chức năng thích hợp
(Fitness Function). Trong GA, Fitness Function là 1 chức năng chính đơn lẻ của
objective function, nó có nhiệm vụ quyết định chuỗi nào được dùng để nhân lên
hoặc chuỗi nào là không cần thiết và sẽ bị loại bỏ. Fitness Function thường xuyên
được xác định để tăng chuỗi thích hợp từ đó có những kết quả tương ứng phù hợp
hơn. Kiểu Di truyền (genotype) là sự biểu Diễn lại chuỗi, kết quả tạo ra gọi là
phenotype. Thường thì trong thuật giải Di truyền,

Thuật toán cụ thể cho bài toán
GA (Fitness, Fitness_threshold, p, r, m)
{
// Fitness: hàm gán thang điểm ước lượng cho một giả thuyết.
// Fitness_threshold: Ngưỡng xác định tiêu chuẩn dừng giải thuật tìm kiếm.
// p: Số cá thể trong quần thể giả thuyết.
GVHD: PGS, TS. Đỗ Văn Nhơn HVTH: Lê Phước Vinh, Mã HV: CH1301116
8
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
// r: Phân số cá thể trong quần thể được áp dụng toán tử lai ghép ở mỗi bước.
// m: Tỉ lệ cá thể bị đột biến.
o Khởi tạo quần thể: P ← Tạo ngẫu nhiên p cá thể giả thuyết
o Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)
o while [max Fitness(h)] < Fitness_threshold do
Tạo thế hệ mới, P
S
1. Chọn cá thể: chọn theo xác suất (1 – r)p cá thể trong quần thể P thêm
vào P
S
. Xác suất Pr(h
i
) của giả thuyết h
i
thuộc P được tính bởi công thức:
2. Lai ghép: chọn lọc theo xác suất cặp giả thuyết từ quần thể P,
theo Pr(h
i
) đã tính ở bước trên. Ứng với mỗi cặp <h
1
, h

• Các cá thể trong quần thể hầu như không thay đổi trạng thái mà chỉ có một vài
cá thể có sự thay đổi trong mỗi bước.
• Để duy trì được tính đa dạng trong quần thể thì Fitness của mỗi cá thể được
chia sẻ lẫn nhau giữa các cá thể có cùng kiểu Di truyền. Vì thế những cá thể khác
nhiều so với các cá thể còn lại sẽ được tăng cường Fitness trong khi các cá thể tương
tự nhau trong quẩn thể sẽ bị giảm Fitness.
• Thao tác lai ghép thay thế: việc cắt một phần giả thuyết và đem ghép lại với
nhau không phải là cách tốt để tạo ra cá thể mới. ví dụ bài toán người du lịch, trong
trường hợp này lời giải tiềm ẩn là sự hoán vị, ví dụ kết quả là 362154, thì có nghĩa là
đi tới thành phố 3 trước rồi tới thành phố 6, kế đến là 2, nếu áp dụng lai ghép điểm
đơn giữa 2 danh sách thì sẽ không đưa ra được một hành trình hợp lệ.
• Sử dụng toàn bộ quần thể: trong hầu hết các giải thuật Di truyền thì đáp án cho
bài toán chính là một cá thể tốt nhất trong quần thể còn những cá thể khác được sử
dụng nhằm giúp cho quá trình tìm kiếm nhưng bị loại bỏ khi kết thúc thuật toán. Điều
này không hoàn toàn tốt. Trong thuật toán đầu tiên được đưa ra bởi Holland [5] thì
mỗi cá thể của quần thể là một lớp – một luật IF-THEN, quần thể là một hệ thống các
lớp, trong quá trình chọn thì mỗi cá thể là một giả thuyết hoàn hảo. Một tiến trình khác
mà cũng sử dụng toàn bộ quần thể đó là tiến trình do Yao và Liu đề xuất sử dụng
chuỗi hạt mạng Neural. Nó được sử dụng khi tồn tại một số lớp mà để giải quyết cùng
một bài toán. Một lớp phổ biến được cho rằng tốt hơn cho tiến trình so với các lớp
khác. Yao và Liu đề xuất sử dụng 4 phương pháp khác nhau để kết hợp kết quả của
mạng Neural. Họ sử dụng sự chia sẻ Fitness tuyệt đối để kích thích quá trình học với
các mẫu khác nhau.
Phần tiếp theo sau đây sẽ phân tích cách hoạt động của giải thuật, so sánh và giải
thích tại sao nó tốt hơn so với các phương pháp truyền thống.
GVHD: PGS, TS. Đỗ Văn Nhơn HVTH: Lê Phước Vinh, Mã HV: CH1301116
10
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
5. Thuật giải Di truyền so với các phương pháp truyền thống
Chúng ta xét bài toán đơn giản sau đây: tối ưu hoá hàm y = f(x) trên khoảng xác

11
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
• Các Thuật giải Di truyền chỉ sử dụng thông tin về các tiêu chuẩn tối ưu của
hàm mục tiêu chứ không dùng các thông tin hỗ trợ nào khác.
• Các Thuật giải Di truyền sử dụng các luật chuyển đổi mang tính xác suất chứ
không phải là các luật chuyển đổi mang tính xác định.
• Các Thuật giải Di truyền thường dễ cài đặt, áp dụng. Tuy nhiên không phải lúc
nào cũng cho lời giải chính xác. Một số Thuật giải Di truyền có thể cung cấp lời giải
tiềm năng cho một bài toán xác định để người sử dụng lựa chọn.
6. Các ứng dụng của thuật giải Di truyền.
Ban đầu Thuật giải Di truyền ra đời được áp dụng cho tối ưu hoá và học máy là
chủ yếu. Đến nay nó đã phát triển mạnh và có nhiều ứng dụng thực tế, đặc biệt là các
bài toán về trí tuệ nhân tạo. Ví dụ: ta có thể tối ưu công việc dự báo thời tiết sao cho
chính xác nhất dựa trên các thông số khí tượng do được. Năm 1967 Beglay xây dựng
máy chơi cờ Hexapawn dựa trên Thuật giải Di truyền và nhận ra rằng Thuật giải Di
truyền có thể thực hiện tốt mà không phụ thuộc độ phức tạp của trò chơi.
6.1. Tối ưu hoá và máy học:
Trong lĩnh vực tối ưu hóa có nhiều bài toán được áp dụng Thuật giải Di truyền
và đã thành công như tối ưu hoá hàm một biến, tối ưu hóa hàm nhiều biến, hay như bài
toán người du lịch, bài toán hộp đen, các bài toán kinh doanh, nhận dạng điều khiển hệ
thống . Sau đây sẽ giới thiệu một số bài toán tối ưu hóa:
David E.Golderg đã ứng dụng GA để tối ưu hóa bài toán điều khiển hệ thống
đường ống dẫn khí thiên nhiên [5]. Trong bài toán này, mục tiêu là cực tiểu hóa năng
lượng do quá trình nén, phụ thuộc vào áp suất tối đa và áp suất tối thiểu và các ràng
buộc tỉ lệ áp suất.
Tối ưu hoá kết cấu: Mục tiêu của bài toán này là cực tiểu hóa trọng lượng của kết
cấu, phụ thuộc vào các ràng buộc về ứng suất lớn nhất và ứng suất nhỏ nhất của mỗi
thanh. Một bộ mã cho khung kết cấu theo ma trận tiêu chuẩn được dùng để phân tích
mỗi thiết kế tạo ra bởi Thuật giải Di truyền.
Trong lĩnh vực máy học, Thuật giải Di truyền được sử dụng cho việc tìm hiểu

xuất giải thuật Di truyền cho bài toán lập lịch luôn luôn là một chủ đề nóng.
6.4. Một số ứng dụng khác
• Thiết kế mạng nơron, kiến trúc lẫn trọng số.
• Quỹ đạo cho người máy.
• Các hệ phi tuyến động - phỏng đoán, phân tích dữ liệu.
• Tìm dạng của các phân tử protein.
• Cải tiến chương trình LISP (lập trình gen).
GVHD: PGS, TS. Đỗ Văn Nhơn HVTH: Lê Phước Vinh, Mã HV: CH1301116
13
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
II. Bài toán xếp lịch trực ở tổng đài
1. Giới thiệu bài toán xếp lịch trực
Mục tiêu chủ yếu của đề tài này là nghiên cứu về Thuật giải Di truyền, từ
đó đề xuất xây dựng mô hình bài toán hỗ trợ ra quyết định: hỗ trợ lập lịch trực tại
Tổng Đài của FPT.
Đối với bài toán này, người trưởng phòng hàng tháng phải lập lịch cho hàng
trăm nhân viên của mình sao cho tất cả các nhân viên điều có tổng số ca trực và ca
nghỉ bằng nhau. Bên cạnh đó các quy định của tổng đài yêu cầu số ca trực và số ca
nghỉ của từng ngày phải gần bằng nhau (theo một tỷ lệ nhất định). Trên thực tế, trưởng
phòng sẽ sắp lịch trực theo tuần (một lần có thể 4 tuần hoặc 5 tuần), và bài toán được
nêu ra ở đây là sẽ giải quyết lịch trực này theo tuần cho hàng trăm nhân viên của tổng
đài.
Để giải quyết bài toán, đầu tiên đầu tiên tôi đã mô hình hóa toán học bài toán
với 2 tập ràng buộc: cứng và mềm. Dựa trên mô hình toán học, từ đó thiết kế giải
thuật Di truyền để tìm các lời giải cho bài toán. Sau đó tiến hành chạy thử nghiệm
nhiều lần trên bộ dữ liệu thực để kiểm tra phương án tốt nhất.
2. Quy trình, các ràng buộc và mô hình toán học
2.1. Mô tả quy trình làm việc ở tổng đài
Tại tổng đài hổ trợ khách hàng của FPT Telecom, hàng ngày các nhân viên
của tổng đài sẽ được trực theo ca quy định, hiện tại có 3 ca trực là: Ca Sáng, Ca

- Tập T các ngày trong khoảng thời gian cần xếp trong tuần.
- Mảng trạng thái giới tính S
s
: giới tính của nhân viên s.



=
nam :1
nữ:0
S
s
- Mảng trạng thái R
s,t,r
: trạng thái của nhân viên s trong ngày thứ t trực ca r.







=
đêm ca :3
chiều ca :2
sáng ca:1
nghỉ :0
R
rt,s,
Các biến số (Variables):

ts,
Ràng buộc cứng:
- HC1: Mỗi nhân viên sẽ phải trực 6 ca trong tuần.
||1|,|16
||
,,
SsTtx
T
r
rts
≤≤≤≤∀=
∑
- HC2: Nhân viên trực đêm sẽ được nghỉ hôm sau.
||1|,|10R3R
r1,ts,rt,s,
SsTt
≤≤≤≤∀=→=
+
- HC3: Nữ không trực đêm.
||1|,|1,13R
rt,s,
SsTtS
s
≤≤≤≤∀=→=
Ràng buộc mềm:
- SC1: Số người trực ca đêm mỗi ngày là 4 người.
||1|,|14
||
1
3,,

- SC3: Tổng số người nghỉ trong 1 ngày không được chênh lệch quá 1 người
so với số người nghỉ trung bình trên một ngày.
||1|,|11
,
||
1
0,,
SsTtzS
ts
S
s
rts
≤≤≤≤∀≤−
∑
=
=
3. Áp dụng giải thuật Di truyền vào bài toán xếp lịch
Trong phần này sẽ mô tả thiết kế giải thuật Di truyền để giải quyết bài toán
xếp lịch ở Tổng đài FPT Telecom.
Giải thuật bắt đầu bằng việc khởi tạo ngẫu nhiên một quần thể các giải pháp
(lịch trực). Quần thể sẽ được tiến hóa qua nhiều thế hệ. Qua mỗi thế hệ, cá thể tốt
GVHD: PGS, TS. Đỗ Văn Nhơn HVTH: Lê Phước Vinh, Mã HV: CH1301116
16
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
nhất được lưu giữ cho quần thể tiếp theo. Sau khi tiến hóa xong, cá thể tốt nhất
trong quần thể cuối cùng sẽ là phương án xếp lịch của bài toán. Thiết kế tập trung
vào các vấn đề sau:
- Biểu Diễn giải pháp: Biểu Diễn các giá trị trong một nhiễm sắc thể.
- Hàm đánh giá: Định nghĩa độ thích nghi của một giải pháp.
- Các toán tử tiến hóa: định nghĩa phương pháp biến đổi nhiễm sắc thể trong

… nv
n
: nhân viên từ 1 đến n
- 0, 1, 2, 3: tương ứng với ca trực (nghỉ, ca sáng, ca chiều, ca đêm)
3.2. Đánh giá cá thể
Việc đánh giá cá thể (giải pháp) liên quan tới kiểm tra tính khả thi thiết
lập bởi các ràng buộc cứng và mềm. Để đánh giá độ tốt của một cá thể, đầu tiên
phải căn cứ vào tổng số lần vi phạm ràng buộc cứng: Nếu hai cá thể cùng vi phạm
ràng buộc cứng, mức độ vi phạm ràng buộc cứng sẽ được dùng để đánh giá, vi
phạm ít hơn có nghĩa là độ thích nghi cao hơn. Đối với các ràng buộc mềm, SC3
sẽ được ưu tiên xem xét trước (và được coi là hàm mục tiêu), sau đó là SC1 và
GVHD: PGS, TS. Đỗ Văn Nhơn HVTH: Lê Phước Vinh, Mã HV: CH1301116
17
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
SC2. Để lựa chọn cá thể cho thế hệ tiếp theo của giải thuật tiến hóa, tôi sử dụng
phép lựa chọn lai ghép ngẫu nhiên (random selection).
Sau quá trình tiến hóa, chọn cá thể tốt nhất làm phương án cho bài
toán. Giải pháp này cần phải thỏa mãn các ràng buộc cứng và các cá thể không thể
vi phạm ràng buộc này.
3.3. Các toán tử
Toán tử chọn lọc dùng để chọn ra những cá thể tốt, sau đó lai ghép
chúng với nhau sinh ra thế hệ con tiếp theo. Điều này cũng giống như trong tự
nhiên với hy vọng rằng: các hai thể tốt lai với nhau thì con cháu chúng sẽ tốt hơn
so với hai cá thể tồi hơn lai với nhau. Tôi đã dùng phép chọn lọc ngẫu nhiên
(random selection). Theo cách này, cứ mỗi cặp ngẫu nhiên 2 cá thể, sẽ chọn ra cá
thể tốt hơn của cặp để tham gia lai ghép.
Toán tử lai ghép có vai trò sống còn trong xác định hành vi của các giải
thuật tiến hóa (EAs). Thông thường, hai cá thể được lựa chọn và các đặc tính của
chúng được kết hợp để sinh ra hai cá thể con (offspring). Ghi chú, các cơ chế
tương tự thường xảy ra trong tự nhiên, trong đó lai ghép cho phép thế hệ tiếp theo

kết quả của giải thuật.
Kế hoạch chạy thử nghiệm như sau:
+ Giải thuật Di truyền: Số quần thể 200, số cá thể trong 1 quần thể
là 100. Xác xuất lai ghép và đột biến lần lượt là 0.1 và 0.05.
+ Chạy thử nghiệm 6 lần, mỗi lần khởi tạo quần thể và cá thể một
cách ngẫu nhiên. Qua các lần chạy cho thấy giải thuật Di truyền có 2 lần ra được
kết quả tốt nhất (độ thích nghi: 1).
4.3. Giao Diện của và kết quả của chương trình
Chương trình được thiết kế trên môi trường .NET ngôn ngữ C#
Hình 2 – Giao Diện chính của chương trình Sắp Lịch Trực tự động
GVHD: PGS, TS. Đỗ Văn Nhơn HVTH: Lê Phước Vinh, Mã HV: CH1301116
19
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
Hình 3 – Kết quả Lịch Trực sau khi xuất ra bảng dạng HTML
GVHD: PGS, TS. Đỗ Văn Nhơn HVTH: Lê Phước Vinh, Mã HV: CH1301116
20
ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP LỊCH TỔNG ĐÀI FPT
III. Kết luận
Chuyên đề này tập trung nghiên cứu các ứng dụng của thuật giải Di truyền,
một thuật giải đa năng và có rất nhiều ứng dụng trong ngành khoa học máy tính
hiện đại. Từ thiết kế máy bay, đầu máy xe lửa đến hỗ trợ cải tiến, xây dựng các
thuật giải khác như Mạng Nơron, logic mờ,
Trong đó bài toán sắp xếp lịch trực (hay lập thời khóa biểu), giải thuật Di
truyền đã thu hút được rất nhiều các nghiên cứu và đề xuất. Đây vừa là một bài
toán lập nhiều kế hoạch công tác có liên quan đến nhau, vừa là bài toán cấp phát tài
nguyên. Để giải quyết vấn đề này, tôi đã mô hình hóa toán học bài toán. Từ đó
dùng giải thuật Di truyền với biểu Diễn nhiễm sắc thể số nguyên để xây dựng
chương trình hỗ trợ ra quyết định.
Tuy nhiên những cài đặt ở phần trên chỉ dừng lại ở mức cơ bản có thể chấp
nhận được, và cho thấy được tính khả thi của bài toán khi áp dụng vào thực tế để