S
ố hóa bởi Trung tâm Học liệu
1
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG
NGUYỄN THỊ HỒNG GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG VÀO BÀI
TOÁN LẬP THỜI KHÓA BIỂU
1.1.2 Giải thuật di truyền 12
1.2 Các khái niệm cơ bản về GA 13
1.2.1 Nhiễm sắc thể 13
1.2.2 Quần thể, thế hệ, toán tử di truyền, tiến hóa 15
1.2.3 Hàm thích nghi 15
1.2.4 Chọn lọc 15
1.2.5 Lai ghép 18
1.2.6 Đột biến 20
1.2.7 Chiến lƣợc nạp lại quần thể 21
1.3 Mô hình GA 23
1.4 Không gian tìm kiếm và điều kiện dừng của GA 24
1.4.1 Không gian tìm kiếm 24
1.4.2 Điều kiện dừng của GA 25
1.5 Đặc điểm và ứng dụng của GA 25
1.5.1 Đặc điểm của GA 25
1.5.2 Ứng dụng của GA 26
CHƢƠNG 2. BÀI TOÁN THUỘC LỚP NP 27
VÀ BÀI TOÁN LẬP THỜI KHÓA BIỂU 27
S
ố hóa bởi Trung tâm Học liệu
3
2.1 Lớp các bài toán NP 27
2.1.1 Một số khái niệm: 27
2.1.2 NP-khó và NP-đầy đủ 27
2.1.3 Tối ƣu hóa đa mục tiêu 28
2.2. Bài toán lập thời khóa biểu 29
2.2.1 Một số khái niệm cơ sở 33
2.2.2 Mô hình bài toán 34
CHƢƠNG 3. XÂY DỰNG BÀI TOÁN THỜI KHOÁ BIỂU DỰA TRÊN GIẢI
tính toán tiến hóa
3
EP
Evolutionary Programming
quy hoạch tiến hóa
4
ES
Evolutionary Strategies
các chiến lƣợc tiến hóa
5
GP
Genetic Programming
lập trình di truyền
6
CS
Classifier Systems
các hệ thống phân loại
7
MOOP
Multi-objective Optimization Problem
Tối ƣu hóa đa mục tiêu
8
NST
nhiễm sắc thể
9
Selection
chọn lọc
10
5
DANH MỤC CÁC BẢNG
Bảng1: Mã hóa nhị phân độ dài 20 bit 13
Bảng2: Mã hóa hoán vị 2 NST A&B 14
Bảng3: Mã hóa giá trị các NST A, B, C 14
Bảng4: Mặt nạ lai ghép đồng nhất 19
Bảng 5: Lai ghép một điểm cắt mã hóa hoán vị 20
Bảng 6: Phép đảo bit mã hóa nhị phân 20
Bảng 7: Hoán vị thứ tự mã hóa hoán vị 21
Bảng 8: Thay đổi giá trị trong mã hóa giá trị 21
Bảng 9: Bảng chỉ số 34
Bảng 10: Bảng kiểm tra ràng buộc về phòng 40
Bảng 11: Bảng kiểm tra ràng buộc về giảng viên 40
Bảng 12: Bảng kiểm tra ràng buộc về lớp sinh viên 41
S
ố hóa bởi Trung tâm Học liệu
6
DANH MỤC CÁC HÌNH
Hình 1: Xác suất của mỗi NST theo kiểu lựa chọn Roulet 16
Hình 2: Lựa chọn xếp hạng 17
Hình 3: Lai ghép một điểm cắt mã hóa nhị phân 18
Hình 4: Lai ghép hai điểm cắt mã hóa nhị phân 18
trên danh sách, trên cây hoặc đồ thị ) hoặc các thuật toán tìm kiếm có thông tin
đƣợc sử dụng nhiều trong không gian tìm kiếm nhỏ. Đối với không gian tìm kiếm
lớn, việc tìm kiếm các lời giải tối ƣu cho bài toán gặp nhiều khó khăn. Do đó, cần
thiết phải có những thuật giải tốt và sử dụng kỹ thuật trí tuệ nhân tạo khi giải quyết
các bài toán có không gian tìm kiếm lớn. Thuật giải di truyền (Genetic Algorithm -
GA) là một trong những kỹ thuật tìm kiếm lời giải tối ƣu đã đáp ứng đƣợc yêu cầu
của nhiều bài toán và ứng dụng. Cùng với logic mờ, GA đƣợc ứng dụng rất rộng rãi
trong các lĩnh vực phức tạp. Sự kết hợp giữa GA và logic mờ đã chứng tỏ đƣợc hiệu
quả trong các vấn đề khó mà trƣớc đây thƣờng đƣợc giải quyết bằng các phƣơng
pháp thông thƣờng hay các phƣơng pháp cổ điển, nhất là trong các bài toán cần có
sự lƣợng giá, đánh giá sự tối ƣu của kết quả thu đƣợc. Chính vì vậy, GA đã trở
thành một trong những đề tài nghiên cứu thu hút đƣợc nhiều sự quan tâm và hiện
nay đã và đang đem đến rất nhiều ứng dụng trong thực tiễn.
Xuất phát từ thuyết tiến hóa muôn loài của Darwin, GA là một 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 hóa của con ngƣời hay của
sinh vật nói chung trong những điều kiện đƣợc qui định sẵn của môi trƣờng. GA là một
thuật giải và mục tiêu của GA 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.
John Holland (1975) và Goldberg (1989) đã đề xuất và phát triển GA, là thuật
giải tìm kiếm dựa trên cơ chế chọn lọc và di truyền tự nhiên. Thuật giải này sử dụng
các nguyên lý di truyền về sự thích nghi và sự sống các cá thể thích nghi nhất trong
tự nhiên.
Do tính hấp dẫn và tính thời sự của khai phá dữ liệu, đặc biệt là giải thuật di
truyền, tôi đã chọn đề tài “Giải thuật di truyền và ứng dụng vào bài toán lập thời
S
ố hóa bởi Trung tâm Học liệu
8
khóa biểu” làm luận văn cao học của mình. Trong đó tập trung nghiên cứu các kỹ
thuật lập lịch và chọn ra một kỹ thuật tiêu biểu đề thực hiện bài toán thời khóa biểu
9
Chương 1. GIẢI THUẬT DI TRUYỀN TRONG KHAI PHÁ DỮ LIỆU
1.1 Quá trình khai phá dữ liệu và giải thuật di truyền (GA)
1.1.1 Quá trình khai phá dữ liệu
Theo Bách khoa toàn thƣ Việt Nam, tri thức là “kết quả của quá trình nhận
thức của con người về đối tượng được nhận thức, làm tái hiện trong tư tưởng của
con người những thuộc tính, những mối quan hệ, những quy luật vận động, phát
triển của đối tượng và diễn đạt bằng ngôn ngữ tự nhiên hay hệ thống ký hiệu khác”.
Phát hiện tri thức là một quá trình bao gồm một dãy các bƣớc lặp sau:
1. Làm sạch dữ liệu
2. Tích hợp dữ liệu
3. Chọn lựa dữ liệu
4. Chuyển đổi dữ liệu
5. Khai phá dữ liệu
6. Đánh giá các mẫu
7. Trình diễn tri thức
Trong đó, khai phá dữ liệu là bƣớc quan trọng nhất trong tiến trình phát hiện
tri thức.
Dữ liệu là những mô tả về sự vật, con ngƣời và sự kiện trong thế giới thực.
Dữ liệu bao gồm số, ký tự, văn bản, hình ảnh, đồ họa,…có một giá trị nào đó
đối với ngƣời sử dụng và chúng đƣợc lƣu trữ, xử lý trong máy tính.
Theo liệu bách khoa toàn thƣ, “khai phá dữ liệu ” là khâu chủ yếu trong quá
trình phát hiện tri thức từ dữ liệu để trợ giúp cho việc làm quyết định trong quản lý.
S
ố hóa bởi Trung tâm Học liệu
10
Khai phá dữ liệu (Data Mining-DM) là một khái niệm ra đời vào những năm
2.Phân lớp dữ liệu và hồi quy
Mục tiêu của phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu.
Quá trình gồm hai bƣớc: xây dựng mô hình, sử dụng mô hình để phân lớp dữ liệu.
Mô hình đƣợc sử dụng để dự đoán nhãn lớp khi mà độ chính xác của mô hình chấp
nhận đƣợc.
Phƣơng pháp hồi quy tƣơng tự nhƣ phân lớp dữ liệu. Nhƣng khác ở chỗ nó
dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự đoán các giá trị
rời rạc.
3.Phân cụm dữ liệu
Mục tiêu của phân cụm dữ liệu là nhóm các đối tƣợng tƣơng tự nhau trong
tập dữ liệu vào các cụm, sao cho những đối tƣợng thuộc cùng một lớp là tƣơng
đồng nhau.
4.Khai phá luật kết hợp
Mục tiêu của phƣơng pháp này là phát hiện và đƣa ra mối liên hệ giữa các
giá trị dữ liệu trong CSDL. Đầu ra của giải thuật luật kết hợp là tập luật kết hợp tìm
đƣợc. Phƣơng pháp khai phá luật kết hợp gồm có hai bƣớc:
Bƣớc 1: Tìm ra tất cả các tập mục phổ biến. Một tập mục phổ biến đƣợc xác
định thông qua việc tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu.
Bƣớc 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, luật phải thoả
mãn độ hỗ trợ và độ tin cậy cực tiểu.
5. Mạng nơron
Đây là một trong những kỹ thuật DM đƣợc ứng dụng phổ biến hiện nay.
S
ố hóa bởi Trung tâm Học liệu
12
Kỹ thuật này phát triển dựa trên một nền tảng toán học vững vàng, khả năng huấn
luyện trong kỹ thuật này dựa trên mô hình thần kinh trung ƣơng của con ngƣời.
Kết quả mà mạng nơron học đƣợc có khả năng tạo ra các mô hình dự báo, dự
đoán với độ chính xác và độ tin cậy cao. Nó có khả năng phát hiện ra đƣợc các xu
Programming).
Năm 1996, thƣ viện các hàm C++ cho GA (GALib) đã đƣợc Mathew Wall,
trƣờng Đại học Massachussets (Massachusetts Institute of Technology) đƣa ra.Đây
là các công cụ sử dụng giải thuật di truyền cho tối ƣu hoá các chƣơng trình có sử
dụng sự biểu diễn hay các toán tử di truyền.
1.2 Các khái niệm cơ bản về GA
1.2.1 Nhiễm sắc thể
Nhiễm sắc thể (NST) hay còn gọi là cá thể. Các sinh vật sống đều cấu tạo từ
các tế bào, và tất cả các tế bào này đều bao gồm một tập hợp các nhiếm sắc thể
giống nhau. Các NST này là một chuỗi các ADN, quy định đặc tính của cả cá thể.
Mỗi NST bao gồm rất nhiều GEN, mỗi gen quy định một trạng thái nào đó.
Trong bài toán tối ƣu, cá thể tƣơng ứng với một lời giải tiềm tàng. Việc mã
hóa và giải mã gen, biến đổi giữa kiểu gen và kiểu hình đƣợc quyết định bởi tính
chất của bài toán. Nhƣng thông thƣờng có một số phƣơng pháp mã hóa NST thƣờng
gặp sau:
1.2.1.1 Mã hóa nhị phân
Đây là cách mã hóa nhị phân phổ biến nhất.Mỗi một nhiễm sắc thể là một
chuỗi bit nhị phân 0 & 1. Mỗi một bit có thể biểu diễn một đặc tính nào đó của lời
giải, và số bit cần để mã hóa đƣợc tính toán hợp lý để chuỗi nhị phân không quá dài,
mà chỉ vừa đủ cho biểu diễn thông tin cần thiết cho lời giải.
Chronosome A
00110101000010111010
Chronosome B
10111100110010001011
Bảng1: Mã hóa nhị phân độ dài 20 bit
S
ố hóa bởi Trung tâm Học liệu
14
Mã hoá theo giá trị thƣờng dùng cho các bài toán đặc biệt. Trong cách mã
hoá này ta thƣờng phải phát triển các toán tử đột biến và lai ghép cho phù hợp với
từng bài toán.
S
ố hóa bởi Trung tâm Học liệu
15
1.2.2 Quần thể, thế hệ, toán tử di truyền, tiến hóa
Quần thể (population) trong tự nhiên là một tập hợp các cá thể có cùng một
số đặc điểm nào đấy. Trong giải thuật di truyền ta quan niệm quần thể là một tập
các lời giải tiềm tàng của một bài toán.
Khái niệm thế hệ (generation) gắn chặt với khái niệm quần thể. Mỗi thế hệ
đƣợc xác định bởi một quần thể chƣa tham gia vào quá trình tiến hóa tiếp theo.
Các toán tử di truyền (GA operator) là các toán tử thao tác đối với các cá thể
nhằm tạo ra các cá thể mới.
Quá trình tiến hóa (evolution) là việc áp dụng các toán tử di truyền đối với
các cá thể, chuyển quần thể từ thế hệ này sang thế hệ tiếp theo, với một bộ phận cá
thể hoặc toàn bộ quần thể đã đƣợc biến đổi.
1.2.3 Hàm thích nghi
Trong tự nhiên, chỉ có những cá thể nào thích nghi đƣợc với môi trƣờng thì
mới tồn tại, không nó sẽ bị diệt vong. GA đƣa ra khái niệm hàm thích nghi, hay
hàm sức khỏe để đánh giá một cá thể so với quần thể. Dựa vào giá trị hàm thích
nghi của mỗi cá thể, thuật toán di truyền mới có thể chọn lựa đƣợc các cá thể tốt cho
các thế hệ sau. Hàm thích nghi cũng là một tiêu chí đánh giá mức độ tiến hóa của
quần thể.
1.2.4 Chọn lọc
Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh sinh tồn trong tự
nhiên, chọn lựa các cá thể trong GA chính là cách chọn các cá thể có độ thích nghi
tốt để đƣa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục đích là sinh ra các cá
thể mới tốt hơn. Tuy nhiên, quá trình chọn lọc mang rất nhiều yếu tố ngẫu nhiên. Có
Hoặc lựa chọn kiểu bánh xe Roulet có thể mô tả theo thuật toán sau:
S
ố hóa bởi Trung tâm Học liệu
17
(1) [SUM] Tính tổng giá trị thích nghi S của tất cả các cá thể hay nhiễm sắc
thể trong toàn quần thể.
(2) [SELECT] sinh một số ngẫu nhiên trên đoạn (0 S) ta đƣợc r.
(3) [LOOP] duyệt lại toàn bộ quần thể, tính tổng hàm thích nghi từ 0, ta gọi
là s. Khi nào s > r thì ta dừng lại với nhiễm sắc thể hiện tại.
1.2.4.2 Lựa chọn xếp hạng
Theo cơ chế lựa chọn trên khi sự khác biệt giữa các hàm thích nghi lớn,các
NST có độ thích nghi kém sẽ rất ít có cơ hội đƣợc lựa chọn, nhất là khi có các NST
tốt có độ thích nghi trên 90%.
Cơ chế lựa chọn xếp hạng đƣợc mô tả nhƣ sau:
- Sắp xếp các NST trong quần thể theo độ thích nghi từ thấp đến cao.
- Đặt lại độ thích nghi cho quần thể đã sắp xếp theo kiểu: NST thứ nhất có độ
thích nghi là 1, nhiễm săc thể thứ hai có độ thích nghi là 2, v.v…, NST thứ pop_size
có độ thích nghi là pop_size.
(a) Trạng thái quần thể trƣớc khi (b) Trạng thái quần thể sau
sắp xếp khi sắp xếp
Hình 2: Lựa chọn xếp hạng
Theo phƣơng pháp này việc một NST đƣợc chọn nhiều lần nhƣ trong lựa
chọn theo kiểu bánh xe Roulet đã giảm đi. Nhƣng nó có thể dẫn đến sự hội tụ chậm
và NST có độ thích nghi cao cũng không khác mấy so với các NST khác.
1.2.4.3 Lựa chọn trận đấu
Hay còn đƣợc gọi là lựa chọn theo trạng thái ổn định. Cơ chế lựa chọn:
S
+ Chuỗi nhị phân của con sẽ đƣợc lai ghép ngẫu nhiên hoặc từ mẹ hoặc từ
cha. Hay nói cách khác, ta sẽ xây dựng một mặt nạ lai ghép. Nó cũng là một chuỗi
nhị phân các bit 0&1.
+ Duyệt mặt nạ: ở vị trí bit mặt nạ = 1 thì gen ở vị trí tƣơng ứng của mẹ đƣợc
lai ghép cho con, nếu bit mặt nạ = 0 thì gen ở vị trí tƣơng ứng của cha đƣợc lai ghép
cho con.
Hình 5: Lai ghép đồng nhất mã hóa nhị phân
Cụ thể hơn ta có bảng sau: Bảng4: Mặt nạ lai ghép đồng nhất
- Lai ghép số học: Cá thể con đƣợc sinh ra bằng một phép toán logic nào đó
(AND,OR,…) với cặp NST bố mẹ.
Hình 6: Lai ghép số học mã hóa nhị phân
1.2.5.2 Lai ghép theo mã hóa hoán vị
Lai ghép một điểm cắt:
S
ố hóa bởi Trung tâm Học liệu
20
- Vị trí cắt đƣợc chọn một cách ngẫu nhiên
- Con mới đƣợc sinh ra sẽ có phần gen đầu cho đến vị trí cắt giống mẹ.
- Duyệt NST cha từ đầu, gen nào chƣa có trong NST của con thì đƣa vào.
Bảng 5: Lai ghép một điểm cắt mã hóa hoán vị
toán di truyền. Nó dƣờng nhƣ quyết định khả năng và tốc độ hội tụ của thuật toán di
truyền. Dựa vào chiến lƣợc nạp lại quần thể có thể phân loại các thuật toán di
truyền. Sau đây là một số chiến lƣợc nạp lại quần thể:
1.2.7.1 Chiến lược nạp lại quần thể
Tạo ra số NST mới bằng kích thƣớc quần thể và quần thể mới bao gồm toàn
các NST mới này, không có NST nào của thế hệ trƣớc.
Hình 7: Chiến lược nạp lại hoàn toàn
Đây là chiến lƣợc đơn giản nhất. Mỗi NST chỉ tồn tại trong một thế hệ, sang
thế hệ tiếp theo sẽ đƣợc thay mới hoàn toàn. Nhƣ vậy sẽ xảy ra trƣờng hợp là các
S
ố hóa bởi Trung tâm Học liệu
22
NST tốt sẽ không đƣợc giữ lại, do đó chiến lƣợc này không phải là chiến lƣợc phù
hợp cho việc cải thiện lời giải qua các thế hệ.
1.2.7.2 Chiến lược nạp lại ngẫu nhiên
Tạo ra số NST mới ít hơn kích thƣớc quần thể và thay thế một cách ngẫu
nhiên các NST ở thế hệ trƣớc bằng NST ở thế hệ sau:
Hình 8: Chiến lược nạp lại ngẫu nhiên
Chiến lƣợc này luôn đảm bảo toàn bộ số con đƣợc sinh ra sẽ đƣợc nạp vào,
nhƣng số lƣợng con mới đƣợc sinh ra ít, và chiến lƣợc ngẫu nhiên không đảm báo
các NST tốt của thế hệ trƣớc sẽ đƣợc giữ lại, và có thể nó sẽ đƣợc thay thế bởi một
NST tồi hơn rất nhiều so với nó. Nạp lại ngẫu nhiên vẫn khả thi hơn chiến lƣợc nạp
lại hoàn toàn khi các NST có thể tồn tại lớn hơn hoặc bằng hai thế hệ.
1.2.7.3 Chiến lược nạp lại theo mô hình cá thể ưu tú
Tạo ra số NST mới ít hơn kích thƣớc quần thể và thay thế chúng cho các bố
mẹ có độ thích nghi thấp:
1. Xác lập các tham số ban đầu của bài 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 ban đầu
của bài toán).
3. Xác lập 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, bao gồm:
- Tính độ thích nghi của mỗi cá thể.
S
ố hóa bởi Trung tâm Học liệu
24
- Kiểm tra điều kiện kết thúc giải thuật.
- Chọn lọc các 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).
- Tiến hành lai ghép các cặp bố-mẹ với một xác suất lai ghép đƣợc chọn để
tạo ra một cá thể mới.
- Tiến hành đột biến với xác suất đột biến đƣợc chọn xác định cá thể đột biến.
4. Kiểm tra điều kiện dừng: Nếu điều kiện đƣợ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 chính là quần thể hiện tại.
1.4 Không gian tìm kiếm và điều kiện dừng của GA
1.4.1 Không gian tìm kiếm
Khi giải một bài toán, các bộ lời giải sẽ đƣợc sinh ra và lời giải hoặc bộ lời
giải tốt nhất sẽ đƣợc xem là đáp án của bài toán. Không gian của tất cả các lời giải
khả thi đƣợc gọi là không gian tìm kiếm (hay không gian trạng thái). Mỗi một điểm
trong không gian tìm kiếm biểu diễn cho 1 lời giải tiềm tàng. Mỗi lời giải tiềm tàng
đƣợc đánh dấu bằng giá trị hay sức khỏe của nó trong bài toán. Với GA, lời giải tốt
nhất sẽ đƣợc tìm ra trong số rất nhiều các lời giải tiềm tàng.
Tìm kiếm một lời giải tƣơng ứng với việc tìm một giá trị cực nào đó (lớn
nhất hoặc nhỏ nhất) trong không gian tìm kiếm. Đôi khi không gian tìm kiếm là rất
tốt, nhƣng chỉ là một số. Trong tiến trình sử dụng GA, quá trình tìm kiếm lời giải sẽ
sinh ra những điểm khác trong quá trình tiến hóa.
- Giải thuật di truyền chỉ cần đánh giá hàm mục tiêu để phục vụ quá trình tìm
kiếm chứ không đòi hỏi các thông tin bổ trợ các.
- Các thao tác cơ bản trong giải thuật di truyền dựa trên khả năng tích hợp
tính ngẫu nhiên trong quá trình xử lý.
Copyright: Tài liệu đại học ©