BỘ GIÁO DỤC ĐÀO TẠO
TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
--------o0o--------
iso 9001 : 2000
NGHIÊN CỨU TÍNH TOÁN MỀM VÀ ỨNG DỤNG
ĐỒ ÁN TỐT NGHIỆP HỆ ĐẠI HỌC CHÍNH QUY
Ngành: Công nghệ thông tin
Sinh viên thực hiện : BÙI THỊ OANH
Giáo viên hướng dẫn : PGS.TS.TRỊNH NHẬT TIẾN
Mã sinh viên : 090112
HẢI PHÒNG 2009
LỜI CẢM ƠN
Em xin chân thành cảm ơn sự giúp đỡ của PGS.TS.Trịnh Nhật Tiến, người đã
trực tiếp hướng dẫn, tận tình chỉ bảo tạo điều kiện cho em hoàn thành khóa luận
đúng thời hạn.
Em xin chân thành cảm ơn tất cả các thầy cô giáo trong khoa Công nghệ thông tin
- Trường ĐHDL Hải Phòng, những người đã nhiệt tình giảng dạy và truyền đạt
những kiến thức cần thiết trong suốt thời gian em học tập tại trường, để em hoàn
thành tốt khóa luận.
Cuối cùng em xin cảm ơn tất cả các bạn đã góp ý, trao đổi hỗ trợ cho em trong
suốt thời gian vừa qua.
Em xin chân thành cảm ơn!
Hải Phòng, tháng 07 năm 2009
Sinh viên

Bùi Thị Oanh
2
MỤC LỤC
LỜI CẢM ƠN...........................................................................................................................2
Danh mục các từ viết tắt..........................................................................................................3
LỜI NÓI ĐẦU..........................................................................................................................4

- Giải thuật di truyền (Genetic Algorithm)
4
Do thời gian không nhiều và khối lượng công việc tìm hiểu khá lớn nên trong
khuôn khổ đồ án tốt nghiệp này, để tìm hiểu cho sâu, em tập trung nghiên cứu giải
thuật di truyền.
Hiện nay, thuật toán di truyền cùng với logic mờ được ứng dụng rộng rãi trong
các lĩnh vực phức tạp, các vấn đề khó, sử dụng các kỹ thuật tìm kiếm lời giải, với
không gian tìm kiếm rất lớn, nhất là những 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, thuật giải di truyền đã trở thành đề tài
nghiên cứu thú vị và đem đến nhiều ứng dụng trong thực tiễn.
Xuất phát từ những vấn đề trên, khóa luận đã tìm hiểu, nghiên cứu giải thuật di
truyền. Sau đó sử dụng giải thuật di truyền cổ điển kết hợp với phương pháp thống
kê ngôn ngữ học giải quyết bài toán “Dò tìm mã DES”.
Khóa luận không tránh khỏi những thiếu sót, rất mong được sự giúp đỡ, chỉ bảo
của thầy cô và các bạn!
Chương 1: TÍNH TOÁN MỀM
1.1. KHÁI NIỆM TÍNH TOÁN MỀM
Tính toán mềm (Soft Computing) khác với tính toán cứng truyền thống (Hard
Computing) ở chỗ: không như tính toán cứng, tính toán mềm cho phép sự không
chính xác, tính bất định, gần đúng, xấp xỉ trong tính toán. Các mô hình tính toán
mềm thường dựa vào kinh nghiệm của con người, sử dụng dung sai cho phép của sự
không chính xác, tính bất định, gần đúng, xấp xỉ để tìm lời giải hiệu quả - đơn giản,
dễ hiểu, dễ thực hiện, chi phí thấp.
Tính toán mềm biểu thị một sự chuyển dịch, biến hoá quan trọng trong các hướng
tính toán. Sự chuyển dịch này phản ánh sự kiện trí tuệ con người, không như máy
tính, có khả năng đáng kể trong việc lưu trữ và xử lý thông tin không chính xác và
bất định, và đây mới là những thông tin thực tế và thường gặp.
Các ứng dụng thành công của tính toán mềm cho thấy tính toán mềm ngày càng
phát triển mạnh và đóng vai trò đặc biệt trong các lĩnh vực khác nhau của khoa học
và kỹ thuật. Tính toán mềm được ứng dụng trong hầu hết các chuyên ngành kỹ thuật

tối ưu (kết quả chính xác
hoàn toàn)
- Yêu cầu đưa ra kết quả gần tối
ưu (cho phép sự sai lệch nhất
định trong kết quả tìm được)
Kỹ thuật tính
toán
- Sử dụng kỹ thuật tính
toán truyền thống
- Kỹ thuật tính toán dựa trên
Heuristic được sử dụng phổ
6
biến
Thời gian tính
toán
- Thời gian tính toán
thường chậm hơn. Trong
một số trường hợp, không
thể đưa ra kết quả trong
thời gian chấp nhận được
- Thời gian tính toán nhanh hơn
với chi phí thấp hơn
Lĩnh vực áp dụng - Các bài toán yêu cầu lời
giải chính xác, không cho
phép sự sai lệch.
- Các bài toán không yêu cầu
lời giải chính xác, song phải
đưa ra kết quả trong một
khoảng thời gian nhất định
với chi phí nhất định

Với những ưu thế đó, tính toán mềm đang dần thể hiện vai trò của mình nhất là
trong việc giải quyết vấn đề mới.
1.4. CÁC KỸ THUẬT TRONG TÍNH TOÁN MỀM
Công nghệ tính toán mềm bao gồm 3 thành phần chính:
- Điều khiển mờ (Fuzzy Control)
- Mạng nơ-ron nhân tạo (Neural Network)
- Giải thuật di truyền (Genetic Algorithm)
1.4.1. Logic mờ (Fuzzy Logic – FL)
Khái niệm tập mờ (Fuzzy set) được Zadeh đưa ra vào năm 1965 với mục đích
cho phép các phần tử thuộc về một tập liên tục thay cho rời rạc. Kể từ đó, các ứng
dụng và phát triển dựa trên khái niệm tưởng chừng rất đơn giản này, đã mang lại
những kết quả khó có thể tin được, thậm chí khó có thể chỉ ra các ứng dụng, phát
triển hay sản phẩm nào không có liên quan đến khái niệm tập mờ. Ví dụ: chúng ta
thường nghe đến nhiều thuật ngữ như: máy giặt fuzzy, quạt fuzzy, xe máy fuzzy...
Khái niệm tập mờ có vai trò rất quan trọng trong việc giải quyết các bài toán tối
ưu, đưa ra các bài toán có tính thực tế, giải quyết bài toán với chi phí thấp và trong
thời gian nhanh hơn (mặc dầu chấp nhận việc có thể có sai số). Trong lĩnh vực an
8
toàn thông tin, tập mờ cũng được sử dụng rất rộng rãi. Tất cả các thuật toán, giải
thuật, kỹ thuật được giới thiệu dưới đây đều được xuất phát từ tập mờ.
1.4.2. Mạng Nơron (Neural Network – NN).
NN là mô hình tính toán dựa trên bộ não. Mô hình NN bao gồm các bộ xử lý _
các Nơron _ có mối liên kết chặt chẽ với nhau, tương tự như họat động của các
Nơron trong não người. Các Nơron được kết nối bởi các đường liên kết có đánh
trọng số, truyền tín hiệu từ nơron này đến nơron khác. Mỗi nơron nhận các tín hiệu
đầu vào (có trọng số) thông qua các đường kết nối và tạo một tín hiệu đầu ra.
Hình vẽ sau đây mô tả mô hình của mạng nơron điển hình:
9
W
1

Bài này sẽ trình bày các khái niệm cơ bản về giải thuật di truyền và áp dụng trong
bài toán cụ thể.
Chương 2: GIẢI THUẬT DI TRUYỀN
2.1. KHÁI NIỆM GIẢI THUẬT DI TRUYỀN
Thuật toán di truyền (Genetic Algorithm_GA) là kỹ thuật chung giúp giải quyết
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
(dựa vào lý thuyết tiến hóa muôn loài của Darwin) trong điều kiện quy đị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.
2.1.1. Đặc trưng của thuật toán di truyền kinh điển
• Thuật toán di truyền lập luận ngẫu nhiên thay vì xác định.
• Thuật toán di truyền duyệt toàn bộ các giải pháp, sau đó chọn lấy giải pháp tương
đối tốt dựa trên hệ số thích nghi.
• Thuật toán di truyền không để ý chi tiết vấn đề, mà chỉ chú ý đến giải pháp, đặc
biệt là dãy số tượng trưng cho giải pháp.
Goldberg và Zbiniev Michalewicz nêu ra đặc trưng của GA như sau:
11
- Thuật toán di truyền làm việc với một mã hóa của tập hợp tham số, chứ không
phải là một tham số.
- Thuật toán di truyền tìm kiếm từ một quần thể các điểm, chứ không phải là một
điểm hoặc một vài điểm như phương pháp tìm kiếm leo đồi (Hill Climbing).
- Thuật toán di truyền đánh giá thông tin với hàm mục tiêu, mà không dựa vào đạo
hàm hay thông tin bổ sung khác.
- Thuật toán di truyền sử dụng các luật biến đổi theo xác suất, mà không sử dụng
luật quyết định.
2.1.2. Cơ sở sinh học của giải thuật di truyền
Trong cơ thể sinh vật, các gene liên kết với nhau theo cơ chế dạng chuỗi gọi là
nhiễm sắc thể (NST), nó đặc trưng cho mỗi loài và quyết định sự sống còn của cơ thể
đó. Trong tự nhiên một loài muốn tồn tại phải thích nghi với môi trường hơn, thì sẽ
tồn tại và sinh sản với số lượng ngày càng nhiều hơn, trái lại những loài không thích

người có 46 nhiễm sắc thể). Tuy nhiên, trong bài này, ta chỉ nói về các cá thể có
đúng một nhiễm sắc thể. Mỗi nhiễm sắc thể bao gồm các đơn vị - gene – xếp liên
tiếp; mỗi gene điều khiển sự thừa kế của một hoặc vài tính trạng bất kỳ (thí dụ màu
mắt) có thể được thể hiện dưới nhiều mức độ khác nhau. Ta nói gene đó có nhiều
trạng thái (gọi là state).
Mỗi nhiễm sắc thể (cá thể) sẽ biểu thị một lời giải có thể của một bài toán
(ý nghĩa của mỗi nhiễm sắc thể, nghĩa là kiểu gene của nó được quy định bởi người
lập trình). Một quá trình tiến hóa được thực hiện trên một quần thể nhiễm sắc thể, là
tương đương với sự tìm kiếm trong một không gian các lời giải có thể. Sự tìm kiếm
này đòi hỏi sự cân bằng giữa hai mục đích: Khai thác lời giải tốt nhất, và khám phá
14
không gian tìm kiếm. Phương pháp “leo núi” là một ví dụ về chiến lược khai thác lời
giải tốt nhất theo các hướng cải tiến. Tìm kiếm ngẫu nhiên là một ví dụ điển hình của
sự khám phá không gian tìm kiếm, không chú trọng khai thác các miền hứa hẹn trong
không gian tìm kiếm. Thuật toán di truyền là lớp các phương pháp tìm kiếm tổng
quát với sự cân bằng đáng kể giữa khai thác và khám phá không gian tìm kiếm.
Thuật toán di truyền cũng như các thuật toán tiến hóa nói chung, hình thành dựa
trên khái niệm cho rằng quá trình tiến hóa tự nhiên là hoàn hảo nhất, hợp lý nhất và
tự nó đã mang tính tối ưu. Quan niệm này có thể được xem là một tiên đề đúng,
không chứng minh được nhưng phù hợp với thực tế khách quan. Quá trình tiến hóa
thể hiện tính tối ưu ở chỗ: thế hệ sau bao giờ cũng tốt hơn, phát triển hơn, hoàn thiện
hơn thế hệ trước. Tiến hóa tự nhiên được duy trì bằng hai quá trình cơ bản: sinh sản
và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hóa tự nhiên, là thế hệ mới luôn được
sinh ra để bổ sung và thay thế thế hệ cũ.
Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại, cá thể nào
không thích ứng với môi trường sẽ bị đào thải. Sự thay đổi môi trường là động lực
tiến hóa. Ngược lại tiến hóa cũng tác động trở lại, góp phần làm thay đổi môi trường.
Trong thuật giải di truyền, các cá thể mới liên tục được sinh ra trong quá trình
tiến hóa nhờ sự lai ghép ở thế hệ cha mẹ. Một cá thể mới có thể mang những tính
trạng của cha mẹ (di truyền), cũng có thể mang những tính trạng hoàn toàn mới (đột

Toán tử này được xem là quá trình chọn lọc trong tự nhiên. Hàm mục tiêu f(i) được
gán cho mỗi cá thể trong dân số. Việc sao chép lại các chuỗi tùy theo giá trị thích
nghi của chúng, có nghĩa là: Những chuỗi có giá trị thích nghi cao hơn sẽ có nhiều
cơ hội đóng góp các chuỗi con cho thế hệ tiếp theo.
Thao tác sinh sản (chọn cha mẹ) được điều khiển bằng cách quay bánh xe
roulette, trong đó mỗi chuỗi trong dân số chiếm một khe có kích thước tỉ lệ với
độ thích nghi (fitness) của nó trên bánh xe.
Giả sử các chuỗi của quần thể ban đầu đã khởi tạo trong bài toán hộp đen có các
giá trị hàm thích nghi như trong bảng sau. Lấy tổng độ thích nghi của 4 chuỗi, chúng
ta được 1170. Ta có tỉ lệ % độ thích nghi của từng chuỗi trong quần thể:
STT Chuỗi Độ thích nghi % trong tổng số
1 01101 169 14.4
2 11000 576 49.2
3 01000 64 5.5
17
4 10001 361 30.9
Tổng cộng 1170 100.0
Các chuỗi của bài toán mẫu và các giá trị thích nghi
Bánh xe roulette được đánh trọng số phù hợp cho sự tái tạo của thế hệ này được
thể hiện trên hình sau:
Sự sinh sản đơn giản phân bố các chuỗi con cháu nhờ sử dụng bánh xe Roulette
với các khe hở tỉ lệ với độ thích nghi.
Với bài toán hộp đen, để sinh sản chúng ta chỉ cần quay bánh xe Roulette 4 lần.
Đối với bài toán cụ thể thì:
Chuỗi 1 có giá trị thích nghi là 169 đại diện cho 0.144. Tương tự với các chuỗi
còn lại, bằng cách này chuỗi thích nghi hơn sẽ có một lượng con cháu lớn hơn trong
thế hệ tiếp theo.
18
49.2%
2

Ví dụ về phép lai (lấy từ [4])
Cơ chế sinh sản và lai ghép chéo đơn giản, bao gồm các việc sinh số ngẫu nhiên,
sao chép chuỗi và trao đổi các chuỗi thành phần. Tuy nhiên, điểm cần nhấn mạnh là
điểm sinh sản và trao đổi thông tin có cấu trúc (dù là một cách ngẫu nhiên) cả quá
trình ghép chéo làm cho giải thuật di truyền tăng thêm sức mạnh.
2.2.3. Đột biến
Đột biến là hiện tượng cá thể con mang một số tính trạng không có trong mã di
truyền của cha mẹ. Mục đích của phép đột biến trong thuật toán di truyền là giúp cho
thuật toán tránh được các cực trị cục bộ. Phép đột biến xảy ra với xác suất Pm nhỏ
hơn rất nhiều so với xác suất Pc. Một phép đột biến có thể mô tả như sau:
• Bước 1: Chọn ngẫu nhiên một cá thể cha mẹ bất kỳ trong quần thể. Giả sử NST
của cha mẹ đều có m gene
• Bước 2: Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m (1 ≤ k ≤ m). Thay đổi
gene thứ k và trả cá thể này về quần thể để tham gia quá trình tiến hóa tiếp theo
Ví dụ về phép đột biến với xác suất Pm:
01101==> 01111
20
Đột biến tại bít thứ 4
Nếu sự sinh sản theo độ thích nghi kết hợp với sự ghép chéo làm cho giải thuật di
truyền có năng lực xử lý tốt hơn, thì sự đột biến đóng vai trò quyết định thứ 2 trong
hoạt động của giải thuật di truyền. Sự đột biến là cần thiết bởi vì: cho dù sự sinh sản
và ghép chéo đã tìm kiếm hiệu quả và tái kết hợp lại các gene với nhau, nhưng thỉnh
thoảng chúng có thể làm mất một vài gene hữu ích nào đó (ví dụ bít 1 hay bít 0 tại
những vị trí đặc biệt). Trong các hệ thống gene nhân tạo, toán tử đột biến sẽ chống
lại sự mất mát không được khôi phục đó. Trong thuật toán di truyền đơn giản, đột
biến là sự thay đổi ngẫu nhiên và không thường xuyên (với xác suất nhỏ) trị số vị trí
của một chuỗi. Trong việc mã hóa nhị phân của bài toán hộp đen có nghĩa là chỉ cần
đổi 1 thành 0 và ngược lại. Tự thân nó sự đột biến là một hoạt động ngẫu nhiên trong
không gian chuỗi, khi được dùng cùng với sự sinh sản và ghép chéo nó sẽ là một
chính sách bảo hiểm chống lại nguy cơ mất mát những gene quan trọng.

Thuật toán di truyền đơn giản áp dụng phương pháp chọn lọc dùng bánh xe
Roulette như đã trình bày ở trên. Cùng với sự phát triển của thuật toán di truyền các
nhà nghiên cứu đã đề xuất một số phương pháp chọn lọc khác: chọn lọc sắp xếp
hạng, chọn lọc cạnh tranh…
2.4.1.1. Chọn lọc xếp hạng (Rank Selection)
Phương pháp này sắp hạng cá thể dựa trên độ thích nghi của chúng. Cá thể xấu
nhất có độ thích nghi 1, kế tiếp là 2,3…. Cá thể tốt nhất có độ thích nghi n (n là số
NST có trong quần thể).
2.4.1.2. Chọn lọc cạnh tranh (Tournament selection)
• Chọn lọc cạnh tranh 2:
22
Y
Hai NST khác nhau được chọn ngẫu nhiên và được so sánh với NST tồn tại. Nếu
NST i
1
không tốt hơn NST i
2
nghĩa là f(i
1
) ≤ f(i
2
), thì NST i
1
chết đi và bị loại ra
khỏi quần thể (liên kết được phá vỡ tùy ý). Quá trình này lặp lại cho đến hết NST
còn lại.
• Chọn lọc cạnh tranh 3:
Giống như trên, 3 NST khác nhau được chọn ngẫu nhiên và được so sánh. Nếu
chúng ta có f(i
1

cá thể cha mẹ ban đầu), mà không có vấn đề mâu thuẫn.
Cá thể con thứ 1: 93|2614|xxx
Cá thể con thứ 2: 3x|8571|xx9
“x” đầu tiên trong cá thể con thứ 1 (sẽ là 6 nhưng vẫn có mâu thuẫn) được thay
bởi 5, tương tự ta áp dụng với mọi ẩn x chưa biết còn lại, ta được:
Cá thể con thứ 1: 93|2614|578
Cá thể con thứ 1: 36|8571|249
2.4.2.2. Lai ghép có trật tự (OX – Order Crossover)
Lai ghép có trật tự có thể được xem như một biến thể của PMX sử dụng thủ tục sửa
chữa khác, OX gồm các bước sau:
• Chọn ngẫu nhiên 1 chuỗi con từ cá thể cha mẹ.
• Đưa ra một cá thể con bằng cách sao chép chuỗi con vào những vị trí tương ứng
trong cá thể cha mẹ.
• Xóa tất cả các ký tự từ cá thể cha mẹ thứ 2, lúc này đã có trong chuỗi con.
Chuỗi còn lại chứa ký hiệu mà cá thể con cần.
• Đặt các ký hiệu vào những vị trí không cố định của các cá thể con từ trái sang
phải theo trật tự của chuỗi để tạo ra cá thể con.
Ví dụ:
Cá thể cha: 93|8571|642
Cá thể mẹ: 35|2614|879
24
Đầu tiên phân đoạn giữa để cắt các điểm được sao chép vào cá thể con:
Cá thể con 1: xx|8571|xxx
Cá thể con 2: xx|2614|xxx
Chuỗi bắt đầu từ điểm cắt thứ 2 của cá thể mẹ là: 8-7-9-3-5-2-6-1-4
Chuỗi sau khi loại các thành phố 8, 5, 7, 1 cũng ở trong cá thể con đầu tiên
là: 9-3-2-6-4
Cuối cùng chuỗi này được đặt vào cá thể con 1 đầu tiên để tạo ra cá thể con (bắt đầu
từ điểm cắt thứ 2).
Cá thể con 1: 64|8571|932