Đại Học Quốc Gia Tp. Hồ Chí Minh
TRƯỜNG ĐẠI HỌC BÁCH KHOA
--------------------

NGUYỄN THÀNH TRUNG

NGHIÊN CỨU CẢI TIẾN VÀ ÁP DỤNG GIẢI THUẬT MƠ
PHỎNG LUYỆN KIM CHO BÀI TỐN XẾP PHỊNG
SINH VIÊN TẠI KÝ TÚC XÁ
Chuyên ngành: Khoa Học Máy Tính

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 6 năm 2009


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học: PGS.TS Dương Tuấn Anh..................................
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 1: TS. Lê Ngọc Minh ....................................................
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 2: TS. Nguyễn Xuân Dũng ...........................................
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN
THẠC SĨ
TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày 4 tháng 9 năm 2009

ĐẠI HỌC QUỐC GIA TP. HCM

CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM

TRƯỜNG ĐẠI HỌC BÁCH KHOA
------------------

Độc Lập - Tự Do - Hạnh Phúc
---oOo--Tp. HCM, ngày tháng năm

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên: Nguyễn Thành Trung Giới tính: Nam / Nữ
Ngày, tháng, năm sinh: 12/03/1983

Nơi sinh: Hải Dương

Chuyên ngành: Khoa Học Máy Tình

MSHV: 00706151

1-TÊN ĐỀ TÀI: Nghiên cứu cải tiến và áp dụng giải thuật mô phỏng luyện kim cải
tiến cho bài tốn xếp phịng sinh viên tại ký túc xá
2- NHIỆM VỤ LUẬN VĂN:
………………………………………………………………………………….…
………………………………………………………………………………….…
…………………………………………………………………………………...
3- NGÀY GIAO NHIỆM VỤ: ……………………………………………………
4- NGÀY HOÀN THÀNH NHIỆM VỤ: . . . . . . . . . . . . . . . . . . . ………………
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN: PGS.TS Dương Tuấn Anh. . . . . . . ….


CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

CHỦ NHIỆM BỘ MÔN
QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)

Nội dung và đề cương luận văn thạc sĩ đã được Hội đồng chuyên ngành thông qua.
Ngày tháng năm
TRƯỞNG PHÒNG ĐT – SĐH

TRƯỞNG KHOA QL NGÀNH


LỜI CAM ĐOAN
Tơi xin cam đoan, ngồi trừ các tham khảo từ những tài liệu đã nêu rõ trong luận
văn, tất cả những nội dung trong luận văn đều do tôi thực hiện và chưa từng được nộp
ở một trường hay tổ chức nào khác để lấy bằng cấp.
Ngày 1 tháng 6 năm 2009
Nguyễn Thành Trung

-i-


LỜI CÁM ƠN
Em xin cám ơn thầy Dương Tuấn Anh, người đã tận tình hướng dẫn em thực
hiện luận văn tốt nghiệp này. Những hướng dẫn và gợi ý quý báu của thầy là nhân tố
quan trọng giúp luận văn này có thể hồn thành. Chúng em cũng xin cám ơn sự tận
tình của thầy đã hỗ trợ em, mặc dù quỹ thời gian của thầy khá bận rộn. Nếu trong q
trình làm việc chung, em có điều gì sơ sót, rất mong thầy bỏ qua và mong rằng thầy

trị chúng ta sẽ có nhiều cơ hội làm việc chung với nhau trong thời gian tới.
Con xin cảm ơn cha mẹ, những người luôn đứng sau lưng chúng con trong suốt
q trình học tập. Nếu khơng có cha mẹ, con đã khơng có những thành quả như ngày
hơm nay. Tuy nhiên, đây chỉ là những kết quả ban đầu, con xin cố gắng nhiều hơn nữa
trong tương lai để có thể đáp lại tấm lòng của cha mẹ và thầy cô.
Em cũng xin cảm ơn những thầy cô thuộc khoa Công nghệ thông tin, những
thầy cô thuộc trường Đại học Bách Khoa TP.HCM và cả những thầy cô đã từng dạy
dỗ em trong suốt quá trình học tập. Các thầy cô đã từng bước một nâng đỡ em về kiến
thức cũng như rèn luyện nhân cách con người. Em xin ghi nhớ công ơn này của các
thầy cô.
Xin cảm ơn các bạn cao học K2006 đã giúp đỡ em trong quá trình học tập. Thời
gian được bên nhau cùng làm việc và vui chơi quả thật là một kỷ niệm đẹp khơng thể
nào qn được trong q trình ngồi trên ghế nhà trường. Rất mong sẽ lại được gặp và
làm việc cùng nhau trong tương lai.

- ii -


TÓM TẮT
Hiện nay, ký túc xá của Trường Đại Học Bách Khoa Tp HCM, cũng như ký túc
xá của các trường đại học khác trong thành phố đều sắp xếp phòng ở cho sinh viên
trong ký túc xá ở đầu mỗi học kỳ, việc sắp xếp này thường được giao cho nhân viên
quản lý ký túc xá thực hiện bằng tay và chưa được tự động hoá. Hậu quả là tốn rất
nhiều thời gian nhưng khơng hiệu quả, trong đó hầu hết các ký túc xá đều không quan
tâm đến các sở thích của sinh viên như: sở thích về nghe nhạc, sở thích về thể thao, sở
thích về chọn bạn ở cùng phịng… Đã có nhiều cơng trình nghiên cứu về tự động hóa
việc xếp phịng cho sinh viên tại ký túc xá. Rất nhiều phương pháp được ứng dụng
cho các đề tài này như giải thuật leo đồi (hill- climbing), giải thuật mô phỏng luyện
kim (simulated annealing), giải thuật tìm kiếm Tabu, giải thuật di truyền, v.v… Trong
đó giải thuật mô phỏng luyện kim là một phương pháp rất thích hợp cho bài tốn tìm

lời giải tối ưu cho hệ ràng buộc. Tuy nhiên chất lượng lời giải của giải thuật mô phỏng
luyện kim thuần túy chưa tốt. Đề tài này nghiên cứu và ứng dụng kỹ thuật mô phỏng
luyện kim cải tiến để cung cấp một chương trình xếp phịng cho sinh viên tại ký túc xá
với tài nguyên là một số lượng phòng, số lượng giường có giới hạn cùng với một
lượng lớn sinh viên tương ứng; không những thế việc sắp xếp phải quan tâm đến các
nguyện vọng và sở thích của sinh viên. Ngồi ra, để đạt hiệu quả trong thực tế,
chương trình phải chạy trong thời gian chấp nhận được. Từ thực nghiệm các phương
pháp mô phỏng luyện kim cải tiến được ứng dụng trong đề tài này, lựa chọn ra giải
thuật phù hợp cho bài tốn xếp phịng sinh viên ký túc xá. Với những yêu cầu trên và
được áp dụng trên mẫu dữ liệu được tạo ra mô phỏng theo yêu cầu của ký túc xá Đại
Học Bách Khoa Tp HCM (khoảng trên 3000 sinh viên), chương trình đã cho kết quả
thực nghiệm khá hiệu quả.

- iii -


MỤC LỤC
CHƯƠNG 1. GIỚI THIỆU ĐỀ TÀI............................................................................................... 1
1.1.

Động cơ và mục tiêu.................................................................................................................. 1

1.2.

Giới thiệu nghiệp vụ của bài toán xếp phòng sinh viên tại ký túc xá....................................... 4

1.3.

Cấu trúc của báo cáo ................................................................................................................ 6


1.4.

Quy ước các thuật ngữ và ký hiệu ............................................................................................ 7

CHƯƠNG 2. CÁC CƠNG TRÌNH LIÊN QUAN VÀ CƠ SỞ LÝ THUYẾT CỦA GIẢI
THUẬT MÔ PHỎNG LUYỆN KIM.............................................................................................. 8
2.1.

Các cơng trình liên quan........................................................................................................... 8

2.2.

Giải thuật mơ phỏng luyện kim (Simulated Annealing) .......................................................... 9

CHƯƠNG 3. CÁC KỸ THUẬT MÔ PHỎNG LUYỆN KIM CẢI TIẾN................................. 14
3.1.

Các vấn đề của giải thuật mô phỏng luyện kim thuần túy ..................................................... 14

3.2.

Các giải thuật cải tiến lịch biểu làm nguội ............................................................................. 16

3.3.

Giải thuật mô phỏng luyện kim với nhiệt độ được ước lượng (Simulated Annealing With

Estimated Teperature)......................................................................................................................... 17
3.4.


Giải thuật mô phỏng luyện kim với cấu trúc lân cận tự thích ứng (Simulated Annealing with

Advanced Adaptive Neighborhood) .................................................................................................... 20
3.5.

Giải thuật mô phỏng luyện kim hai giai đoạn (A two-stage Simumated Annealing

Methodology) ....................................................................................................................................... 22
3.6.

Giải thuật mơ phỏng luyện kim cục bộ hóa (Localized Simulated Annealing (LSA)) ........... 24

3.7.

Giải thuật mô phỏng luyện kim thu thập thông tin (Informed Simulated Annealing (ISA)) 32

3.8.

Kỹ thuật mô phỏng luyện kim tái nung nóng (Reheat SA) .................................................... 45

3.9.

Tổng kết các kỹ thuật mô phỏng luyện kim cải tiến............................................................... 45

CHƯƠNG 4. THIẾT KẾ CHƯƠNG TRÌNH.............................................................................. 50
4.1.

Giới thiệu về các ràng buộc của hệ thống............................................................................... 50

4.2.


Hàm chi phí............................................................................................................................. 54

4.3.

Lịch biểu làm nguội sử dụng trong các giải thuật của chương trình ..................................... 55

4.4.

Lời giải lân cận ....................................................................................................................... 56

4.5.

Thiết kế hệ thống .................................................................................................................... 56

4.6.

Thiết kế dữ liệu cho chương trình .......................................................................................... 58

4.7.

Thiết kế giao diện người dùng ................................................................................................ 62

CHƯƠNG 5. HIỆN THỰC CHƯƠNG TRÌNH .......................................................................... 65
5.1.

Hiện thực các giải thuật mơ phỏng luyện kim trong chương trình........................................ 65

5.2.


Hiện thực giao diện người dùng ............................................................................................. 77

5.3.

Kết quả thực nghiệm .............................................................................................................. 80

CHƯƠNG 6. TỔNG KẾT VÀ ĐÁNH GIÁ ................................................................................. 86
- iv -


6.1.

Tổng kết .................................................................................................................................. 86

6.2.

Đánh giá .................................................................................................................................. 87

6.3.

Hướng phát triển của luận văn............................................................................................... 88

TÀI LIỆU THAM KHẢO ............................................................................................................. 90
BẢNG THUẬT NGỮ ANH VIỆT ĐỐI CHIẾU.......................................................................... 92

-v-


DANH MỤC HÌNH VÀ BẢNG
Danh mục hình

Hình 2-1: Lưu đồ giải thuật mơ phỏng luyện kim ....................................................................................... 13
Hình 3-1: Ví dụ về vấn đề tổng quát........................................................................................................... 15
Hình 3-2 : Giải thuật LSA.......................................................................................................................... 31
Hình 3-3 : Ví dụ về một sửa chữa .............................................................................................................. 35
Hình 3-4 : Giải thuật ISA cơ bản................................................................................................................ 46
Hình 3-5 : Giải thuật mơ phỏng luyện kim tái nung nóng............................................................................ 49
Hình 4-1: Mơ tả tổng quan hệ thống........................................................................................................... 57
Hình 4-2: Sơ đồ ERD cho cơ sở dữ liệu chương trình................................................................................. 58
Hình 4-3: Giao diện tổng quát của chương trình ......................................................................................... 62
Hình 5-1: Kỹ thuật chọn lời giải lân cận..................................................................................................... 67
Hình 5-2: Tính chi phí cho các giải thuật SA.............................................................................................. 68
Hình 5-3: Lịch biểu làm nguội cấp số nhân ................................................................................................ 70
Hình 5-4: Giải thuật mơ phỏng luyện kim thơng thường (Standard SA) ...................................................... 72
Hình 5-5: Giải thuật ISA – phần SA học hỏi .............................................................................................. 73
Hình 5-6: Giải thuật ISA – phần SA chạy................................................................................................... 74
Hình 5-7: Giải thuật mơ phỏng luyện kim tái nung nóng ............................................................................ 75
Hình 5-8: Giải thuật mơ phỏng luyện kim nhanh (VFSA) ........................................................................... 76
Hình 5-9: Form đăng nhập cho người dùng ................................................................................................ 77
Hình 5-10: Form đăng ký vào ở ký túc xá cho sinh viên ............................................................................. 78
Hình 5-11: Form cho phép chỉnh sửa lại chi phí phịng – sinh viên ............................................................. 78
Hình 5-12: Form cho phép thay đổi các thông số của giải thuật ISA ........................................................... 79
Hình 5-13: Kết quả xếp phịng cho sinh viên .............................................................................................. 80
Hình 5-14: Biểu đồ khi chạy giải thuật ISA với số bước chạy 5000 ............................................................ 82
Hình 5-15: Biểu đồ khi chạy giải thuật Reheat SA với số bước chạy 5000 .................................................. 82
Hình 5-16: Biểu đồ khi chạy giải thuật VFSA với số bước chạy 5000......................................................... 83
Hình 5-17: Biểu đồ khi chạy giải thuật Genearal SA với số bước chạy 5000 ............................................... 83
Hình 5-18: Biểu đồ so sánh sự thay đổi chi phí theo số lần lặp của 4 giải thuật ........................................... 84

Danh mục bảng
Bảng 4-1: Mô tả đặc tả dữ liệu của bảng sinh viên...................................................................................... 59

Bảng 4-2: Mô tả dữ liệu cho bảng phịng.................................................................................................... 59
Bảng 4-3 : Mơ tả dữ liệu cho bảng giường ................................................................................................. 59
Bảng 4-4 : Mô tả dữ liệu cho bảng xếp phòng ............................................................................................ 60
Bảng 4-5 : Mơ tả dữ liệu bảng tiêu chí chọn bạn......................................................................................... 60
- vi -


Bảng 4-6 : Mơ tả dữ liệu bảng tiêu chí chọn phịng..................................................................................... 60
Bảng 4-7 : Mơ tả dữ liệu bảng sở thích....................................................................................................... 61
Bảng 4-8 : Mơ tả dữ liệu bảng sinh viên đăng ký lại ................................................................................... 61
Bảng 4-9: Mô tả bảng chi phí cố định ........................................................................................................ 61
Bảng 4-10: Mơ tả bảng chi phí sở thích...................................................................................................... 61
Bảng 5-1: Bảng số liệu chạy các giải thuật với số bước chạy cho trước....................................................... 81
Bảng 5-2: Bảng đánh giá các giải thuật được hiện thực trong chương trình ................................................. 84
Bảng P-1: Bảng thuật ngữ Việt-Anh đối chiếu............................................................................................ 92

- vii -


CHƯƠNG I: GIỚI THIỆU ĐỀ TÀI

CHƯƠNG 1.
GIỚI THIỆU ĐỀ TÀI

Chương này tơi trình bày về động cơ và mục tiêu để thực hiện đề tài này.
Ngoài ra nghiệp vụ của bài tốn xếp phịng sinh viên tại ký túc xá cũng được giới
thiệu trong chương này.

1.1. Động cơ và mục tiêu
1.1.1 Sự cần thiết của việc cải tiến giải thuật mô phỏng luyện kim

Giải thuật mô phỏng luyện kim là một phương pháp giải quyết các vấn đề tối ưu
tổ hợp (combinational optimization problem) được giới thiệu bởi Kirkpatrick vào nă
1983 [1]. Đây là một giải thuật rất hữu hiệu để giải các bài toán tối ưu tổ hợp khác
nhau. Tuy nhiên giải thuật này cũng có những nhược điểm khác nhau. Một trong
những nhược điểm lớn nhất của giải thuật này đó là tốn rất nhiều thời gian để tìm ra
lời giải tối ưu và khó khăn trong việc tìm ra lịch biểu làm nguội (cooling schedule)
thích hợp cho mỗi bài tốn. Để tìm ra lịch biểu làm nguội hợp lý thì cần nhiều phép
thử. Nếu mà lịch biểu làm nguội khơng thích hợp được sử dụng thì sẽ khơng bảo đảm
tìm ra lời giải tối ưu. Có rất nhiều phương pháp cải tiến giải thuật mô phỏng luyện
kim do nhiều nhà nghiên cứu đưa ra. Mỗi phương pháp đều có những ưu điểm, nhược
điểm riêng nhưng rất khó so sánh chúng với nhau nếu không thông qua thực nghiệm.
Việc tìm ra một phương pháp cải tiến giải thuật mô phỏng luyện kim thông qua thực
nghiệm là rất cần thiết. Đó chính là động lực và cũng là một trong hai mục tiêu cốt lõi
của đề tài này: nghiên cứu cải tiến và ứng dụng giải thuật mô phỏng luyện kim vào bài
tốn xếp phịng sinh vien tại ký túc xá. Lý do mà chúng tơi chọn bài tốn xếp phịng
sinh viên tại ký túc xá se được trình bày bên dưới.
1.1.2 Nhu cầu của bài tốn xếp phịng sinh viên tại ký túc xá.
Năm nào cũng vậy, cứ vào đầu mỗi năm học, các trường đại học, cao đẳng lại có
thêm hàng ngàn tân sinh viên nhập học. Một số lượng lớn các sinh viên này sinh sống
ở các tỉnh khác nên phải ở trọ ở thành phố. Việc giải quyết nơi ăn chốn ở cho sinh
viên ngày càng được xã hội và lãnh đạo ở các trường quan tâm nhằm giải quyết chỗ ở
-1-


CHƯƠNG I: GIỚI THIỆU ĐỀ TÀI

ổn định cho sinh viên để các em có đủ điều kiện và mơi trường sống tốt để yên tâm
học tập. Ký túc xá vẫn là nơi ở được ưu tiên hàng đầu mà sinh viên lựa chọn. Không
những thế đây cũng là nơi các trường mong muốn sắp xếp cho sinh viên của mình vì
tính an tồn, kỷ luật, tiện lợi cũng như chi phí ở phải chăng, phù hợp với hồn cảnh

các sinh viên xa nhà. Mặc dù cho đến thời điểm hiện tại, các ký túc xá vẫn chưa đáp
ứng được đầy đủ nhu cầu của sinh viên nhưng việc mở rộng, nâng cấp hạ tầng ký túc
xá cũng như cung cách quản lý ký túc xá, sắp xếp phòng ở cho sinh viên đang được
lãnh đạo trường quan tâm và từng bước xây dựng. Ký túc xá đại học Bách Khoa tất
nhiên cũng khơng nằm ngồi tiến trình cải tiến và thay đổi đó. Tuy nhiên với một số
lượng sinh viên đơng đảo với nhiều loại hình đào tạo ( đại học, cao đẳng, cao học,
v.v… ) và chuyên ngành đa dạng như đại học Bách Khoa ( hơn 10 chuyên ngành ),
ngoài việc mở rộng xây dựng và hiện đại hóa ký túc xá, việc cải tiến quy trình quản lý
cũng cần được đặc biệt quan tâm. Trong đó, qui trình sắp xếp phịng ở cho sinh viên
sao cho đáp ứng được nguyện vọng, sở thích của sinh viên thực sự là một bài toán
phức tạp.
Hiện nay, hầu như các ký túc xá của các trường đại học trong thành phố đều
thực hiện việc xếp phòng cho sinh viên trong ký túc xá bằng tay ở đầu mỗi học kỳ.
Hậu quả là tốn rất nhiều thời gian nhưng không hiệu quả, trong đó hầu hết các ký túc
xá đều khơng quan tâm đến các sở thích của sinh viên như: nghe nhạc, chơi thể thao,
bạn ở cùng phòng… Điều này làm cho các sinh viên khơng thực sự hài lịng và thoải
mái trong khi ở ký túc xá như không được ở chung với những người bạn cùng khoa,
cùng quê hay cùng sở thích, … để có thể quan tâm và giúp đỡ lẫn nhau về tinh thần,
cùng học tập hay chia sẻ những sở thích giống nhau về thể thao, ca nhạc, v.v …
Chúng ta có thể chia việc xếp phòng này ra thành 2 giai đoạn khác nhau. Đầu
tiên là xếp phòng thỏa mãn ràng buộc cứng nghĩa là sắp xếp sao cho sinh viên nam thì
ở phịng dành cho nam, sinh viên nữ thì ở phịng dành cho nữ, sắp xếp sao cho không
vượt quá số người tối đa ở mỗi loại phòng, và phải ưu tiên sắp xếp các sinh viên thuộc
diện chính sách, sinh viên đăng ký lại. Với một số lượng phòng lớn và diện tích khác
nhau cũng như số lượng giường hữu hạn, việc sắp xếp hàng ngàn sinh viên vào các
phòng cùng với các ràng buộc cứng như trên không đơn giản. Thứ hai việc sắp xếp
-2-


CHƯƠNG I: GIỚI THIỆU ĐỀ TÀI


phải thỏa mãn càng nhiều càng tốt các ràng buộc mềm tức là thỏa mãn sở thích của
các sinh viên thì việc xếp phịng trở nên rất phức tạp và không thể giải quyết bằng
cách xếp bằng tay vì tốn quá nhiều thời gian và cơng sức. Lấy ví dụ là ký túc xá có
gần 3000 giường và mỗi sinh viên có khoảng 20 tiêu chí lựa chọn cần phải được thoả
mãn thì số ràng buộc cần phải thoả mãn cho tất cả các sinh viên là 60000, và số cách
sắp xếp 3000 sinh viên vào các giường là 3000! Đây là một con số tổ hợp quá lớn mà
nếu sắp xếp bằng tay thì với một vài nhân viên quản lý ký túc xá gần như không thực
hiện được trong thời gian ngắn để có thể khảo sát một lời giải thích hợp.
Trước những u cầu thực tế cần thiết đó, một chương trình xếp phịng cho sinh
viên ở ký túc xá chạy hồn toàn tự động cần được xây dựng là điều tất yếu. Yêu cầu
chung là chương trình phải chạy nhanh, đáp ứng được các ràng buộc của sinh viên, có
khả năng mở rộng, và dễ thêm bớt những ràng buộc do các thay đổi về nhu cầu của
sinh viên hoặc các thay đổi về chính sách quản lý ký túc xá. Chương trình cần được
tham khảo và phân tích kỹ càng từ nghiệp vụ thực tế để được hiện thực một cách đầy
đủ và nghiêm túc. Đây chính là động cơ và cũng chính là một trong hai mục tiêu cốt
lõi của đề tài: cung cấp một chương trình xếp phịng cho sinh viên tại ký túc xá Đại
hoc Bách Khoa với tài nguyên là một số lượng phòng, số lượng giường có giới hạn
cùng với một lượng lớn sinh viên tương ứng; không những thế việc sắp xếp phải quan
tâm đến các nguyện vọng và sở thích của sinh viên như chọn bạn cùng quê, cùng
khoa, cùng sở thích về thể thao hay âm nhạc, … và đáp ứng càng nhiều càng tốt các
ràng buộc mềm trên. Độ tối ưu của bài toán được đo trên số lượng các ràng buộc được
thỏa mãn theo thứ tự ưu tiên do người quản lý chương trình đưa ra.
Từ thực trạng đã nêu trên, tôi sẽ xây dựng một hệ thống cơ sở dữ liệu để quản lý
tài nguyên trong ký túc xá Đại học Bách Khoa như phịng, giường cũng như thơng tin
cá nhân về các sinh viên trong ký túc xá và chương trình thực hiện việc xếp phịng cho
sinh viên ở ký túc xá. Dữ liệu thu thập cho đề tài được xây dựng trên cơ sở số phòng,
số giường, số sinh viên và các ràng buộc mềm trên cơ sở tham khảo ý kiến của ban
giám đốc ký túc xá. Dữ liệu mẫu được thực hiện trên 3000 sinh viên và tài nguyên là
ký túc xá có ba dãy nhà, mỗi dãy nhà có chín lầu, ngồi lầu trệt là tầng dịch vụ, quản

lý hành chính, sân chơi thể thao thì mỗi lầu có 12 phịng và sức chứa của mỗi phòng là
-3-


CHƯƠNG I: GIỚI THIỆU ĐỀ TÀI

từ 8 đến 16 giường, một giường dành cho một sinh viên, … Các ràng buộc mềm được
quan tâm đến gồm có: sở thích về nghe nhạc, sở thích chơi thể thao, sinh viên có hút
thuốc hay khơng, sinh viên đi làm thêm có nhu cầu học khuya, các nguyện vọng chọn
bạn cùng phòng do cùng q, cùng khoa, cùng tuổi, sở thích chọn phịng như chọn
tầng, giá thuê (phòng),…
Để tránh trường hợp hệ thống được hiện thực một cách cứng nhắc, không mềm
dẻo và khó tùy biến, chỉ giới hạn cho mơ hình một ký túc xá nhất định nào đó, tơi sẽ
trình bày phương pháp luận và phương hướng giải quyết cho bài tốn xếp phịng tổng
qt trước nhất. Khi đi vào giai đoạn hiện thực, đề tài sẽ áp dụng phương pháp luận ấy
lên tập dữ liệu và hoàn cảnh cũng như thông tin đăng ký cụ thể tại ký túc xá trường
Đại học Bách Khoa.

1.2. Giới thiệu nghiệp vụ của bài tốn xếp phịng sinh viên tại ký túc xá
1.2.1 Giới thiệu về ký túc xá Đại học Bách Khoa
Hiện nay, số lượng sinh viên cư trú tại ký túc xá Đại học Bách Khoa khoảng
2500 sinh viên, trong đó có khoảng 800 sinh viên là nữ (chiếm 1/3 tổng số sinh viên).
Ký túc xá gồm có 3 dãy nhà: dãy A, dãy B, dãy C, mỗi dãy nhà có từ chín đến mười
hai tầng. Mỗi tầng có khoảng 12 phịng và số giường trong mỗi phòng dao động từ
bốn đến 8 giường tầng. Mỗi giường tầng có 2 tầng là tầng 1 và tầng 2. Vào đầu mỗi
học kỳ, ký túc xá cho phép các sinh viên mới nhập học được đăng ký vào ở ký túc xá
và đồng thời cho phép các sinh viên đang ở ký túc xá có quyền đăng ký thay đổi
phịng ở của mình.
1.2.2 Các chính sách quản lý việc đăng ký vào ở tại ký túc xá
Sau đây là một số chính sách mà ký túc xá hiện đang dùng để quản lý việc đăng

ký vào ở ký túc xá. Các chính sách này là cơ sở để phân tích và thiết kế hệ thống quản
lý cũng như xếp phịng ở ký túc xá.
Chính sách của ký túc xá là thông báo sớm đến sinh viên thời hạn đăng ký mới.
Sau đó dựa trên các yêu cầu trong bản đăng ký của sinh viên, sinh viên nào đăng ký
trước sẽ được đáp ứng trước. Mỗi sinh viên khi đăng ký được phép đánh thứ tự độ ưu
tiên các tiêu chí lựa chọn phịng ở: các đặc tính của các phịng như dãy, tầng, phịng,
tầng giường, giá thuê; các tiêu chí về chọn bạn cùng phòng: cùng khoa, cùng quê,
-4-


CHƯƠNG I: GIỚI THIỆU ĐỀ TÀI

cùng năm học, cùng tuổi, bạn thân và các sở thích như nghe nhạc, chơi thể thao, học
khuya, hút thuốc, chơi game.
- Thông báo sớm cho sinh viên
Để tránh xảy ra trình trạng quá tải trong q trình đăng ký xếp phịng, ban quản
lý ký túc xá thông báo đến các sinh viên mới trúng tuyển thời gian đăng ký xếp phòng
vào ký túc xá ngay khi có kết quả tuyển sinh và làm thủ tục nhập học. Song song đó,
ban quản lý thơng báo đến các sinh viên hiện đang ở ký túc xá có nhu cầu thay đổi
phịng vào giữa học kỳ hè. Nhờ đó, sinh viên có thể tham khảo và đăng ký sớm để
tránh các sinh viên đăng ký ồ ạt vào đầu năm học.
- Đăng ký trước, đáp ứng trước
Đây là một trong những cơ chế khuyến khích học viên nộp hồ sơ đăng ký vào ở
ký túc xá sớm. Cơ chế này được áp dụng vì tính thực tiễn của nó, bởi vì các sinh viên
sẽ khơng hài lịng nếu người nộp đơn sau được xử lý cho phép vào ở cịn người nộp
đơn trước thì khơng. Do đó, mỗi một hồ sơ được gán một nhãn thời gian (time
stamped) lên hồ sơ của sinh viên khi sinh viên này đóng tiền đặt chỗ trong ký túc xá.
Ngồi ra, những sinh viên đã từng được ở ký túc xá nếu có nhu cầu thay đổi phịng sẽ
được ưu tiên xét với hệ số ưu tiên cao để khi tiến hành xếp phòng, các sinh viên này sẽ
được ưu tiên xếp trước. Tỉ lệ ưu tiên này được cụ thể bằng hệ số ở lâu năm (senior),

cách xác định hệ số này sẽ được trình bày ở phần sau.
- Ưu tiên cho sinh viên thuộc gia đình chính sách
Đối với hầu hết các ký túc xá, các sinh viên thuộc diện gia đình chính sách sẽ
được ưu tiên sắp xếp chỗ ở trong ký túc xá, tức là ưu tiên được xếp phịng trước. Tuy
nhiên, để đảm bảo tính cơng bằng thì sự ưu tiên này chỉ đảm bảo sinh viên diện chính
sách được xếp phịng chứ ưu tiên này sẽ khơng được tính trong các tiêu chuẩn chọn
phịng ở phù hợp.
- Giới tính
Trên thực tế, khi thiết kế phịng, các phòng được thiết kế khác nhau dành riêng
cho sinh viên nam và sinh viên nữ. Do đó, người quản lý phải xác định rõ là sinh viên
đăng ký vào ở phòng nam hay phòng nữ để việc sắp xếp phòng ở được hợp lý.
-5-


CHƯƠNG I: GIỚI THIỆU ĐỀ TÀI

- Hút thuốc
Các sinh viên hút thuốc/ khơng hút thuốc thường khơng thích ở chung với nhau.
Do đó, khi sắp xếp phịng, người quản lý cần quan tâm đến hồ sơ đăng ký của sinh
viên xem sinh viên đó đăng ký ở phịng có hút thuốc hay không hút thuốc để sắp xếp
cho phù hợp. Những sinh viên không hút thuốc sẽ được sắp xếp ở chung với nhau và
tương tự, các sinh viên hút thuốc sẽ được sắp xếp ở chung phòng.
- Loại phòng
Khi đưa vào sử dụng, các ký túc xá đều thiết kế các phòng với nhiều loại khác
nhau, cụ thể các phịng có thể khác nhau về số lượng giường trong phịng cũng như
các phịng có vị trí ở các tầng, dãy khác nhau. Thông thường trong đơn xin đăng ký
các sinh viên phải điền vào phần chọn loại phòng như: diện tích phịng (số giường
trên một phịng), tầng và giá thuê.

1.3. Cấu trúc của báo cáo

Sau đây là cấu trúc của bài báo cáo của chúng tôi. Bài báo cáo của chúng tôi chia
thành sáu chương như sau:
- Chương 1: trình bày về động cơ và mục tiêu để thực hiện đề tài này. Sau đó là
phần giới thiệu về nghiệp vụ của bài tốn xếp phịng sinh viên tại ký túc xá được khảo
sát trong đề tài này.
- Chương 2: trình bày về các cơng trình liên quan đến đề tài này và cơ sở lý
thuyết của giải thuật mơ phỏng luyện kim SA.
- Chương 3: trình bày các kỹ thuật mô phỏng luyện kim cải tiến được quan tâm
và qua đó đánh giá các kỹ thuật này.
- Chương 4: trình bày các thiết kế để hiện thực của chương trình trong đề tài
này. Cụ thể trong chương này có các kỹ thuật mơ phỏng luyện kim cải tiến được lựa
chọn để hiện thực để so sánh đánh giá trong đề tài này, thiết kế về cơ sở dữ liệu và
thiết kế về giao diện chương trình.
- Chương 5: trình bày chi tiết về việc hiện thực các giải thuật mơ phỏng luyện
kim trong chương trình và các phần khác của chương trình. Ngồi ra kết quả thực
nghiệm cũng được đưa ra trong chương này.
-6-


CHƯƠNG I: GIỚI THIỆU ĐỀ TÀI

- Chương 6: nêu lên tổng kết và đánh giá về các giải thuật mô phỏng luyên kim
được ứng dụng trong đề tài và qua đó đánh giá về đề tài.
Sau đó là phần tài liệu tham khảo và bảng thuật ngữ Anh-Việt đối chiếu.

1.4. Quy ước các thuật ngữ và ký hiệu
Trong lĩnh vực mơ phỏng luyện kim (Simulated Annealing), có một số thuật ngữ
tiếng Anh khi chuyển qua tiếng Việt sẽ không phản ánh một cách hồn tồn ngữ
nghĩa của nó. Do đó, trong luận văn này, chúng ta quy ước sử dụng một số thuật ngữ
tiếng Anh ở dạng gốc của nó: Simulated Anealing, Hill-Climbing, Tabu Search ...

Tuy nhiên, những thuật ngữ này sẽ được in nghiêng.
- Các từ ngữ viết tắt sử dụng trong luận văn:
SA: Mô phỏng luyện kim.
KTX: Ký túc xá.
CSA: Classical Simulated Annealing
FSA: Fast Simulated Annealing
VFSA: Very Fast Simulated Annealing
RHSA: Reheat Simualted Annealing
LSA: Localized Simulated Annealing
ISA: Informed Simulated Annealing

-7-


CHƯƠNG II: CÁC CƠNG TRÌNH LIÊN QUAN VÀ CƠ SỔ LÝ THUYẾT CỦA GIẢI THUẬT
MÔ PHỎNG LUYỆN KIM

CHƯƠNG 2.
CÁC CÔNG TRÌNH LIÊN QUAN VÀ CƠ SỞ LÝ THUYẾT
CỦA GIẢI THUẬT MƠ PHỎNG LUYỆN KIM
Chương này trình bày các cơng trình liên quan đến đề tài này. Sau đó là phần
giới thiệu về giải thuật mơ phỏng luyện kim. Đây chính là cơ sở lý thuyết của giải
thuật mô phỏng luyện kim cải tiến được khảo sát trong đề tài này.

2.1.Các cơng trình liên quan
Trước khi luận văn này thực hiện, có một luận văn thạc sĩ của Elena Sttanni hiện
thực hệ thống tối ưu bài tốn xếp phịng cho sinh viên ở ký túc xá dùng giải thuật mô
phỏng luyện kim [6], tại trường Đại học University of New Mexico vào tháng 12 năm
2000. Luận văn này hiện thực khối chức năng tối ưu hố kết quả xếp phịng cho hệ
thống Housing Management System (HMS)., một chương trình thương mại dùng để

quản lý ký túc xá, trong đó có một khối chức năng về xếp phòng, HMS dựa trên hệ
quản trị cơ sở dữ liệu là FoxPro. Luận văn của Elena Sttanni tối ưu hố kết quả xếp
phịng tại ký túc xá trường đại học University of New Mexico (UNM), (ký túc xá có
khoảng 2000 sinh viên). Hệ thống được xây dựng bằng giải thuật mô phỏng luyện
kim với lịch biểu làm nguội cấp số nhân. Hệ thống này đã đạt được những thành tựu
đáng kể ban đầu nhưng còn một số điểm cần phải cải thiện như số bước chạy của giải
thuật người sử dụng không thể xác định trước. Ngoài ra hệ thống chỉ hiện thực duy
nhất một lịch biểu làm nguội là cấp số nhân nên không so sánh được các lịch biểu làm
nguội khác nhau trong giải thuật SA. Hơn nữa các chính sách quản lý của ký túc xá
UNM hoàn toàn khác với điều kiện xã hội tại Việt Nam như các chính sách ưu tiên
cho phép các sinh viên thuộc diện chính sách vào ở tại ký túc xá bao gồm sinh viên ở
vùng xa, vùng xâu, sinh viên là con gia đình liệt sỹ, thường binh, sinh viên có gia đình
thuộc diện xố đói, giảm nghèo…
Vào năm 2004, một luận văn tương tự cũng được thực hiện tại trường Đại học
Bách khoa Tp.HCM của tác giả Lê Trung Hiếu. Luận văn này đã nghiên cứu ứng
-8-


CHƯƠNG II: CÁC CƠNG TRÌNH LIÊN QUAN VÀ CƠ SỔ LÝ THUYẾT CỦA GIẢI THUẬT
MÔ PHỎNG LUYỆN KIM

dụng giải thuật giải thuật mơ phỏng luyện kim cho bài tốn xếp phòng tại ký túc xá
Đại học Bách Khoa. Trong luận văn của mình, tác giả Lê Trung Hiếu đã hiện thực
giải thuật SA với hai lịch biểu làm nguội và kết quả đạt được cũng khá khả quan. Tuy
nhiên chương trình thực thi cịn hơi chậm ( mất 4 giờ với số bước chạy là 10000 ).
Vào năm 2005, tôi và Trần Nhật Tuấn thực hiện luận văn đại học áp dụng giải
thuật mô phỏng luyện kim cải tiến (cụ thể là Imformed Simulated Annealing) cho bài
tốn xếp phịng ký túc xá đại học Bách Khoa [22]. Kỹ thuật này chia quá trình luyện
kim thành hai giai đoạn: học hỏi và tìm kiếm trực tiếp. Giai đoạn học hỏi sẽ giúp
chúng ta thu được danh sách các cặp biến-giá trị có xác suất năm trong lời giải tối ưu

nhiều nhất. Giai đoạn tìm kiếm trực tiếp sẽ dựa trên danh sách trên để tìm ra lời giải
tối ưu. Kết quả thu được nhìn chung là tốt nhưng chương trình có nhược điểm là thời
gian thực thi chậm (mất 2 tiếng với số bước chạy là 10000).
Mục tiêu của luận văn này là ứng dụng giải thuật mô phỏng luyện kim cải tiến
hơn nhằm rút ngắn thời gian thực thi của chương trình cũng như cải thiện chất lượng
lời giải.
Trước khi vào phần chính của luận văn, cơ sở lý thuyết của giải thuật mô phỏng
luyện kim và các kỹ thuật cải tiến giải thuật luyện kim sẽ được trình bày sơ lược, phần
này làm cơ sở kỹ thuật để hiện thực bài tốn xếp phịng sinh viên ở ký túc xá. Chương
tiếp theo sẽ giới thiệu kỹ các kỹ thuật cải tiến được lựa chọn để hiện thực trong luận
văn này nhăm so sánh, đánh giá và từ đó được chọn lựa kỹ thuật tối ưu cho bài tốn
xếp phịng này.

2.2. Giải thuật mô phỏng luyện kim (Simulated Annealing)
Giải thuật mơ phỏng luyện kim là một giải thuật tìm kiếm cục bộ (local search)
có khả năng thốt khỏi điểm tối ưu cục bộ. Đây là một giải thuật rất được ưu thích khi
giải quyết các bài tốn tối ưu tổ hợp do tính dễ hiện thực, tính hội tụ về lời giải tối ưu
cũng như có khả năng tránh các bẫy tối ưu cục bộ (local optimum).
Ý tưởng cơ bản của giải thuật được nêu ra đầu tiên bởi Metropolis vào năm
1953 trong một giải thuật mơ phỏng q trình làm nguội vật liệu trong lò nhiệt – gọi là
quá trình luyện kim. Nếu một vật liệu rắn được nung cho vượt qua điểm sơi của nó,
-9-


CHƯƠNG II: CÁC CƠNG TRÌNH LIÊN QUAN VÀ CƠ SỔ LÝ THUYẾT CỦA GIẢI THUẬT
MƠ PHỎNG LUYỆN KIM

rồi sau đó làm lạnh cho trở lại trạng thái bình thường (trạng thái mà năng lượng thấp
nhất) thì cấu trúc của vật liệu phụ thuộc vào tốc độ làm lạnh. Lấy ví dụ, nếu ta làm
lạnh chậm thì có thể tạo ra được tinh thể lớn nhưng nếu làm lạnh nhanh sẽ làm cho

tinh thể có một số sai sót. Giải thuật của Metropolis mơ phỏng q trình thay đổi năng
lượng của hệ thống theo quá trình làm lạnh cho đến khi nó đạt trạng thái ổn định.
Q trình giả lập của Metropolis tạo ra một sự xáo trộn và tính tốn sự thay đổi
năng lượng. Nếu năng lượng giảm, hệ thống sẽ chuyển qua trạng thái mới đó. Nếu
năng lượng tăng, trạng thái mới chỉ được chấp nhận với một xác suất như sau:
Định luật của nhiệt động học phát biểu rằng tại nhiệt độ t, xác suất cho một sự
gia tăng về mức năng lượng E là:
P( E ) = exp(- E /kt) (2.1) trong đó k là hằng số Boltzmann.
Một số bước lặp sẽ được thực hiện ở mỗi giá trị nhiệt độ và sau đó nhiệt độ được
giảm đi. Công việc này sẽ được lặp nhiều lần cho đến khi hệ thống ngưng tụ về một
trạng thái ổn định.
Vào năm 1983, Kirkpatrick và Cerny đề nghị rằng quá trình giả lập này có thể
được sử dụng để tìm ra các lời giải cho các bài toán tối ưu và mục tiêu ở đây là hội tụ
về lời giải tối ưu. Họ đã chỉ ra rằng giải thuật Metropolis có thể được áp dụng cho
những bài tốn tối ưu bằng cách ánh xạ những phần tử của quá trình luyện kim vật lý
lên những phần tử của bài toán tối ưu. Giải thuật SA được sử dụng rộng rãi để giải
quyết các bài tốn tối ưu hóa tổ hợp, đặc biệt trong vấn đề xếp lịch, định thời trong
giáo dục như xếp thời khóa biểu, xếp lịch thi, bài tốn TSP (Traveling Salesman
Problems), job-shop-scheduling.
2.2.1 Liên hệ giữa q trình luyện kim thực sự và mô phỏng luyện kim
Mô phỏng nhiệt động học

Tối ưu tổ hợp

Các trạng thái của hệ thống

Các lời giải khả thi

Năng lượng


Chi phí

Chuyển trạng thái

Các lời giải lân cận

Nhiệt độ

Thông số điều khiển
- 10 -


CHƯƠNG II: CÁC CƠNG TRÌNH LIÊN QUAN VÀ CƠ SỔ LÝ THUYẾT CỦA GIẢI THUẬT
MÔ PHỎNG LUYỆN KIM

Trạng thái ổn định

Lời giải

Với cách dùng ánh xạ này, bất cứ bài tốn tối ưu tổ hợp nào cũng có thể chuyển
thành bài toán áp dụng giải thuật SA.
2.2.2 Giải thuật Simulated Annealing
Để có thể áp dụng được kỹ thuật SA, ta phải diễn tả bài tốn trong khung thức
của sự tìm kiếm cục bộ, bằng cách định nghĩa:
- Một không gian lời giải (solution space)
- Một cơ cấu xác định vùng lân cận (neighbourhood structure)
- Một hàm chi phí (cost function)
Định nghĩa này sẽ xác định một quang cảnh lời giải mà trong đó có thể dị tìm
bằng cách di chuyển từ lời giải hiện hành sang lời giải lân cận.
-


Sau đây là giải thuật SA tổng quát (theo [8])

Chọn lời giải ban đầu là s0
Chọn nhiệt độ ban đầu là t0 > 0
Chọn hệ số giảm nhiệt độ là 
repeat
repeat
Chọn ngẫu nhiên một lời giải s thuộc miền lời giải lân cận của lời
giải s0 // s là lời giải lân cận của lời giải ban đầu s0


= f(s) – f(s0) // tính tốn sự thay đổi của hàm chi phí

if  < 0 then
s0 = s
else
sinh ra một giá trị ngẫu nhiên x ∈ [0,1]
if x < exp(-  / t) then
s0 = s
endif
endif
until iterration_count=nrep
t =  (t)
until stopping_condition = true
// s0 là lời giải gần như tối ưu

Giải thuật này được thể hiện bằng lưu đồ giải thuật ở hình 2-1.
- 11 -



CHƯƠNG II: CÁC CƠNG TRÌNH LIÊN QUAN VÀ CƠ SỔ LÝ THUYẾT CỦA GIẢI THUẬT
MÔ PHỎNG LUYỆN KIM

Các bước di chuyển dự tuyển được chọn một cách ngẫu nhiên và tất cả những
bước di chuyển có cải thiện đều được chấp nhận một cách tự động. Còn các bước di
chuyển khác được chấp nhận một xác suất exp(-  / t), với  là mức thay đổi ở hàm
chi phí và t là một thông số điều khiển.
Cần lưu ý rằng chất lượng của các lời giải thì nhạy cảm đối với cách thức thông
số nhiệt độ t được điều chỉnh - còn được gọi là lịch biểu làm nguội (cooling schedule
theo [8]).
Lịch biểu làm nguội được định nghĩa bằng:
- Một nhiệt độ khởi đầu t0.
- Các điều kiện dừng
- Hàm giảm thiểu 
- Số lần lặp lại tại mỗi nhiệt độ nrep.
Tất cả những giá trị trên tuỳ thuộc vào từng bài tốn ứng dụng cụ thể vì chúng
phải được chọn theo dạng của không gian lời giải.
2.2.3 Lịch biểu làm nguội
Lịch biểu làm nguội (cooling schedule) của giải thuật mơ phỏng q trình luyện
kim bao gồm bốn thành phần như sau:
- Nhiệt độ ban đầu.
- Nhiệt độ cuối cùng
- Độ giảm dần của nhiệt độ
- Tại mỗi nhiệt độ số lần thực hiện các phép thay đổi trạng thái để đạt được kết quả tối
ưu.
Theo [6] có nhiều cách phân loại lịch biểu làm nguội khác nhau đó là: làm nguội
cấp số nhân (Geometric cooling), làm nguội với nhiều tỉ lệ giảm nhiệt độ (Multiple
cooling Rates), tái nung nóng cấp số nhân (Geometric reheating).
Chúng ta phải có một lịch biểu làm nguội hiệu quả để có thể rút ngắn thời gian

mà giải thuật cần để tìm ra lời giải tối ưu. Cho nên có rất nhiều lịch biểu làm nguội đã
được khảo sát. Trong đó lớp lịch biểu làm nguội thường được áp dụng trong thực tế là
:
- xác suất chấp nhận ban đầu cao
- 12 -


CHƯƠNG II: CÁC CƠNG TRÌNH LIÊN QUAN VÀ CƠ SỔ LÝ THUYẾT CỦA GIẢI THUẬT
MÔ PHỎNG LUYỆN KIM

- xác suất chấp nhận kết thúc thấp
- tốc độ làm nguội từ 0.8 -> 0.99
- số bước lặp bằng số lời giải lân cận.

Hình 2-1: Lưu đồ giải thuật mơ phỏng luyện kim

- 13 -


CHƯƠNG III: CÁC KỸ THUẬT MÔ PHỎNG LUYỆN KIM CẢI TIẾN

CHƯƠNG 3.
CÁC KỸ THUẬT MÔ PHỎNG LUYỆN KIM CẢI TIẾN

Chương này trước hết trình bày các vấn đề về độ hiệu quả của giải thuật mô
phỏng luyện kim thuần túy. Sau đó sẽ là phần giới thiệu các kỹ thuật cải tiến giải thuật
mô phỏng luyện kim khác nhau. Các kỹ thuật mô phỏng luyện kim cải tiến đượ giới
thiệu trong chương này gồm có:
- Các kỹ thuât cải tiến lịch biểu làm nguội
- Kỹ thuật mô phỏng luyện kim với nhiệt độ được ước lượng

- Kỹ thuật mô phỏng luyện kim với cấu trúclân cận tự thích ứng
- Kỹ thuật mô phỏng luyện kim hai giai đoạn
- Kỹ thuật mơ phỏng luyện kim tái nung nóng
- Kỹ thuật mơ phỏng luyện kim cục bộ hóa
- Kỹ thuật mơ phỏng luyện kim thu thập thông tin

3.1. Các vấn đề của giải thuật mô phỏng luyện kim thuần túy
Giải thuật SA rất tốt vì tính hội tụ và hiệu quả trong việc thoát khỏi các điểm tối
ưu cục bộ. Tuy nhiên có giải thuật này có 2 vấn đề:
- Việc tìm ra lời giải gần tối ưu các lời giải được khảo sát gần như là một phân
bố đều. Thế nhưng thời gian đạt được điều này đôi khi lớn hơn thời gian xem xét tất
cả lời giải. Điều này là khơng thực tiễn. Trong thực tế, chỉ có thể sử dụng một lịch
biểu làm nguội ngắn cho nên xác suất tìm ra lời giải gần tối ưu là rất thấp trong một
vài trường hợp.
- Muốn thoát khỏi tối ưu cục bộ cần phải di chuyển qua lời giải kế cận. Tuy
nhiên một vài bước chuyển khơng hiệu quả vì khơng dẫn quá trình tìm kiếm tới lời
giải tốt hay tối ưu. Một lịch biểu làm nguội ngắn không cho phép khảo sát đủ các
bước chuyển này, vì thế mà xác suất tìm ra lời giải tốt hay tối ưu bị giảm sút.
- 14 -


CHƯƠNG III: CÁC KỸ THUẬT MÔ PHỎNG LUYỆN KIM CẢI TIẾN

Chúng ta sẽ xem xét ví dụ cho dưới đây với hình vẽ 3.1. Trong đó mỗi nút trên
đồ thị biểu thị một lời giải, Opt là lời giải tối ưu. Mỗi cạnh giữa hai nút chỉ ra rằng hai
nút này là lân cận nhau. Mục tiêu cần tìm là Opt hoặc Sd (một lời giải tốt).

Hình 3-1: Ví dụ về vấn đề tổng quát
Nếu một lịch biểu đủ dài, q trình tìm kiếm có thể tìm ra Opt vì tính hội tụ của
giải thuật mơ phỏng luyện kim. Nhưng nếu một lịch biểu làm nguội ngắn được dùng

sẽ xuất hiện vấn đề là khơng dẫn q trình tìm kiếm tới lời giải tốt hay tối ưu. Trường
hợp lịch biểu chỉ gồm 4 bước lặp và bắt đầu từ S1 xác suất tìm ra Opt sẽ là 0. Theo lịch
biểu này có khả năng tìm ra Sd qua 2 con đường Ps (S1,Sd) và P1(S1,Sd) được biểu thị
bằng đường chấm chấm trên hình 3.1. Giả sử rằng quá trình tìm kiếm theo Ps (S1,Sd).
Nếu bước chuyển khơng thích hợp được chấp nhận nghĩa là di chuyển qua nút không
thuộc đường này thì xác suất tìm ra Sd sẽ thành 0.
Có rất nhiều hướng tiếp cận để làm giảm sự ảnh hưởng của những vấn đề này.
Thông dụng nhất là cố gắng tìm ra một lịch biểu tốt. Muốn vậy phải cân bằng quá
trình tìm kiếm theo hai hướng. (1) Phân bố đều xấp xỉ tại nhiệt độ hơi cao tìm ra phần
của khơng gian tìm kiếm chứa lời giải tối ưu hay gần tối ưu. (2) Tìm lời giải tốt hơn
hoặc tốt nhất ở không gian cục bộ hiện tại. Thật khơng may hai khía cạnh này lại mâu
thuẫn nhau vì sự giới hạn của thời gian tìm kiếm.
Một cân bằng tốt khơng dễ dàng đạt được bởi vì nó khác nhau đối với từng bài
tốn khác nhau. Ngồi ra chúng ta không biết chắc cái này tốt hơn cái khác trừ khi
- 15 -