NGHIÊN CỨU TÍNH TOÁN MỀM VÀ ỨNG DỤNG

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (339.21 KB, 62 trang )

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

Tổng số lần xuất hiện của 15 bộ đôi đó là 0,2703 ∼ 0,27……………………………….54
Nếu tính cả dấu cách (∪), thì có thêm ba bộ đôi với tần suất xuất hiện
như sau: …………………………………………………………………………………………………………..54
Danh mục các từ viết tắt
NST Nhiễm sắc thể
GA Genetics Algorithms
DES Data Encryption Standard.
Danh mục các thuật ngữ thông dụng trong giải thuật di truyền
Trong tự nhiên Trong giải thuật di truyền
Gene Đặc tính, ký tự
Chromosome (Nhiễm sắc thể) Chuỗi
Allele (gene tương ứng) Giá trị của đặc tính
Locus (ổ gene) Vị trí chuỗi
Genetype (kiểu hình) Tập thông số, giải pháp luân phiên,
cấu trúc được giải mã
3
LỜI NÓI ĐẦU
Trong thực tế cuộc sống, các bài toán liên quan đến hệ thống nhận thức, tri thức
của con người, đều hàm chứa những đại lượng, thông tin, mà bản chất là không
chính xác, không chắc chắn, không đầy đủ…. cho các hệ thống ra quyết định.
Ví dụ: Sẽ chẳng bao giờ có thông tin, dữ liệu, cũng như các mô hình tính toán
đầy đủ và chính xác cho bài toán dự báo thời tiết.
Trong lĩnh vực khoa học cũng vậy, các hệ thống phức tạp trên thực tế thường
không thể mô tả đầy đủ, và chính xác bởi các phương trình toán học truyền thống.
Kết quả là những cách tiếp cận kinh điển dựa trên kỹ thuật phân tích, và các phương
trình toán học nhanh chóng không còn phù hợp. Vì thế công nghệ tính toán mềm
chính là giải pháp cần thiết trong lĩnh vực này.
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)
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

5
như kỹ thuật điện, kỹ thuật điều khiển, kỹ thuật hoá học, kỹ thuật xây dựng,… Kỹ
thuật điện là lĩnh vực đầu tiên ứng dụng tính toán mềm trong các lĩnh vực như điều
khiển mờ, xử lý ảnh mờ, mạch điện tử dùng logic, người máy,….
Khái niệm “Tính toán mềm” được Zadeh đưa ra lần đầu tiên vào năm 1994 được
mô tả như sau: “Một cách cơ bản, tính toán mềm không phải là thể thống nhất các
khái niệm và kỹ thuật. Đúng ra, nó là sự kết hợp của các phương pháp riêng biệt theo
cách này hay cách khác để thích nghi với nguyên lý của nó. Tại điểm giao đó, mục
đích cuối cùng của tính toán mềm là khai thác khả năng thứ lỗi (Tolerance) cho tính
không chính xác hay tính bất định để đạt được mục tiêu với chi phí thấp”. Một cách
đơn giản hơn, “Tất cả các tính toán có bao gồm tính không chính xác một cách có
chủ đích trong tính toán ở một hay nhiều mức và cho phép tính không chính xác này
làm thay đổi (làm giảm) độ chính xác của bài toán, hay “làm mềm” mục tiêu tối ưu ở
một số bước, đều bị coi là thuộc lĩnh vực tính toán mềm”.
1.2. PHÂN BIỆT TÍNH TOÁN MỀM VÀ TÍNH TOÁN CỨNG
Tính toán truyền thống, hay còn gọi là tính toán cứng, là phương pháp sử dụng
các kỹ thuật tính toán, dựa trên dữ liệu đầu vào để đưa ra kết quả cuối cùng một cách
chính xác theo yêu cầu của bài toán.
Bảng dưới đây đưa ra một số điểm khác biệt giữa tính toán mềm và tính toán
cứng, để chúng ta có được một hình dung cụ thể hơn về tính toán mềm.
Điểm so sánh Tính toán cứng Tính toán mềm
Dữ liệu xử lý – Xử lý bài toán dựa trên số
liệu chính xác.
– Ví dụ: Giá trị của A phải
là 0 hoặc 1: {0,1}
-Không đòi hỏi dữ liệu phải chính
xác.
-Ví dụ: Giá trị của A có thể nằm
trong khoảng từ 0 đến 1: [0,1]
Kết quả đầu ra – Yêu cầu đưa ra kết quả

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

Bảng 1: So sánh tính toán cứng và tính toán mềm
1.3. TẠI SAO CẦN PHẢI CÓ TÍNH TOÁN MỀM
Trong thực tế cuộc sống, các bài toán liên quan đến hệ thống nhận thức, trí tuệ
của con người đều hàm chứa những đại lượng, thông tin không chính xác, không
chắc chắn, không đầy đủ. Ví dụ: sẽ chẳng bao giờ có các thông tin, dữ liệu cũng như
các mô hình tính toán đầy đủ, và chính xác cho bài toán dự báo thời tiết. Nhìn chung
con người luôn ở trong bối cảnh không có thông tin chính xác, và đầy đủ cho các hệ
thống ra quyết định.
Trong lĩnh vực khoa học kỹ thuật cũng vậy, các hệ thống phức tạp trên thực tế
thường không thể mô tả một cách đầy đủ, và chính xác bởi các phương trình toán
học truyền thống. Kết quả là những cách tiếp cận kinh điển dựa trên kỹ thuật phân
tích, và các phương trình toán học nhanh chóng tỏ ra không còn phù hợp. Vì thế,
công nghệ tính toán mềm chính là giải pháp trong lĩnh vực này.
Một số đặc điểm của công nghệ tính toán mềm:
– Tính toán mềm căn cứ trên các đặc điểm, hành vi của con người, và tự nhiên để
đưa ra quyết định hợp lý trong điều kiện không chính xác, không chắc chắn.
– Các thành phần của tính toán mềm có sự bổ sung, hỗ trợ nhau.
7
– Tính toán mềm là một hướng nghiên cứu mở, bất kỳ một kỹ thuật mới nào được
tạo ra từ việc bắt chước trí thông minh của con người, đều có thể trở thành một
thành phần mới của tính toán mềm.
– Chính nhờ những đặc điểm đó mà tính toán mềm đang được nghiên cứu và ứng
dụng rộng rãi trong nhiều lĩnh vực, đặc biệt là: trí tuệ nhân tạo, khoa học máy
tính và học máy. Cụ thể:
◊ Không phải bài toán nào cũng có thuật toán có thể giải quyết được bằng tính
toán cứng.
◊ Không phải bài toán nào có thuật toán có thể giải quyết được bằng tính toán
cứng, cũng có thể thực hiện với chi phí và thời gian chấp nhận được.
◊ Khi bản thân dữ liệu là không chính xác thì không thể giải quyết được bằng
phương pháp chính xác.

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

W
2
W
3
Y
Neuro
n
X
1
X
2
X
3
y
y
y
Input Signals Weights Output Signals
Hình 1. Mô hình mạng Nơron điển hình
1.4.3. Chương trình tiến hóa (Evolutionary Computation – EC)
Kĩ thuật EC bao gồm rất nhiều các giải thuật khác nhau, ở đây, tiểu luận trình bày
một trong những giải thuật tiến hóa phổ biến nhất – giải thuật di truyền (Genetic
Allgothm –GA). Hình vẽ bên dưới mô tả hoạt động của một giải thuật di truyền điển
hình.
10
Population
New
Population
Mutation Mating
Selection
Hình 2 – Mô hình hoạt động của giải thuật di truyền.

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

nghi với môi trường sẽ dần bị tuyệt chủng.
Môi trường tự nhiên luôn luôn biến đổi, nên cấu trúc nhiễm sắc thể cũng thay đổi
để thích nghi với môi trường, và ở thế hệ sau luôn có độ thích nghi cao hơn thế hệ
trước. Cấu trúc này có được nhờ sự trao đổi thông tin ngẫu nhiên với môi trường bên
ngoài, hay giữa chúng với nhau. Dựa vào đó các nhà khoa học máy tính xây dựng
một giải thuật tìm kiếm tinh tế dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hóa,
gọi là giải thuật di truyền (Genetic Algorithms).
12
2.1.3. Tư tưởng của giải thuật di truyền
Có một số lớn các bài toán người ta chưa tìm thuật toán tương đối nhanh để giải
quyết chúng. Nhiều bài toán trong lớp này là các bài toán quy hoạch thường nảy sinh
trong các ứng dụng. Với bài toán quy hoạch thuộc loại khó, có thể tìm được thuật
toán “nhanh”, cho kết quả gần tối ưu. Đối với một số bài toán quy hoạch khó, ta
cũng có thể tìm thuật toán xác suất, thuật toán này không đảm bảo cho kết quả tối
ưu, nhưng bằng cách chọn ngẫu nhiên đủ nhiều “bằng chứng”, có thể giảm tùy ý xác
suất sai của kết quả.
Nói một cách trừu tượng, việc giải bài toán có thể xem như tìm kiếm trong không
gian với lời giải có thể. Vì cái đích của chúng ta là “lời giải tốt nhất”, ta có thể xem
phương pháp giải bài toán là quá trình tối ưu hóa. Đối với không gian nhỏ, phương
pháp “vét cạn” cổ điển là đủ dùng. Đối với các không gian lớn hơn, đòi hỏi những
phương pháp trí tuệ nhân tạo đặc biệt. Thuật toán di truyền (GA) nằm trong các
phương pháp đặc biệt đó.
13
Tư tưởng của thuật toán di truyền là xem xét, đánh giá các gene thế nào là tốt cho
mục tiêu, sử dụng nó tiếp cho thế hệ sau. Nói theo ngôn ngữ di truyền là giữ lại các
gene trội, loại bỏ các gene không tốt, hay là đào thải những thế hệ không tốt.
2.1.4. Hoạt động của giải thuật di truyền
Thuật toán di truyền dùng nhiều ngôn ngữ của ngành di truyền học. Chúng ta sẽ
nói về các “cá thể” trong một quần thể. Thường thì các cá thể này được gọi là xâu,
hoặc nhiễm sắc thể. Mỗi loài có một số lượng nhiễm sắc thể nhất định (Ví dụ: cơ thể

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

biến). Di truyền và đột biến là hai cơ chế quan trọng như nhau trong tiến hóa, dù đột
biến xảy ra với xác suất nhỏ hơn nhiều so với di truyền. Các thuật toán tiến hóa, tuy
có những đặc điểm khác biệt, nhưng đều mô phỏng các quá trình cơ bản: lai ghép,
đột biến, sinh sản và chọn lọc tự nhiên.
Như vậy, quá trình tiến hóa càng lâu thì càng có điều kiện cho các cá thể tốt được
sinh ra, và chất lượng của cá thể càng được nâng lên.
15
2.2. CẤU TRÚC GIẢI THUẬT DI TRUYỀN ĐƠN GIẢN
Trong thuật toán di truyền đơn giản, các cá thể hay còn gọi là NST (Nhiễm sắc
thể) được mã hóa thành một chuỗi nhị phân gồm giá trị 0 và 1. Một NST trong GA
cổ điển có dạng sau:
0 0 1 1 0 0 1 1 1
Mỗi NST biểu diễn một lời giải có thể có của bài toán. Một quá trình tiến hóa
được thực hiện trên một quần thể (một tập hợp NST) tương đương với sự tìm kiếm
trong không gian 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: tìm lời giải tốt nhất và khám phá không gian tìm kiếm mới.
GA cổ điển thực hiện tìm kiếm theo nhiều hướng bằng cách duy trì một tập lời
giải có thể, khuyến khích sự hình thành và trao đổi thông tin giữa các hướng. Tập lời
giải trải qua quá trình tiến hóa và cuối cùng cho ta một lời giải đủ tốt được chọn để
tái sinh, các lời giải tồi bị loại bỏ. Để phân biệt mức độ tốt xấu giữa các lời giải khác
nhau người ta dùng một hàm gọi là “hàm mục tiêu” hay “hàm thích nghi” vì hàm
này tương đương với môi trường sống hay thuyết tiến hóa.
Thuật toán di truyền đơn giản bao gồm ba toán tử sau:
16
• Tái tạo (Reproduction)
• Lai ghép (Crossover)
• Đột biến (Mutation)
2.2.1. Tái tạo
Tái tạo là một quá trình trong đó các chuỗi biểu diễn cá thể được sao chép lại tùy
theo giá trị hàm mục tiêu f (các nhà sinh vật học gọi hàm này là hàm thích nghi).

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

5.5%
3
30.9%
4
14.4%
1
2.2.2. Lai ghép
Mỗi khi một chuỗi được chọn để sinh ra, một bản sao chính xác của các chuỗi đó
sẽ được tạo ra. Các bản sao này được đưa vào bể ghép đôi (mating pool). Toán tử lai
ghép đơn giản có thể được tiến hành theo hai bước:
• Bước 1: Chọn ngẫu nhiên hai (hay nhiều) cá thể 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 trong khoảng từ 1 đến m-1 (ta gọi là
điểm lai). Điểm lai chia các chuỗi cha mẹ dài m thành 2 nhóm con dài m
1
và
m
2
. Hai chuỗi NST con mới là m
11
+ m
22
và m
12
+ m
21
Đư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.
Ví dụ: Về phép lai một điểm với xác suất Pc có thể mô phỏng như sau:
19

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.

2.3. SƠ ĐỒ GIẢI THUẬT DI TRUYỀN
Giải thuật di truyền bao gồm các bước sau:
– Bước 1: Khởi tạo quần thể (population) ban đầu của các NST.
– Bước 2: Xác định giá trị hàm mục tiêu cho mỗi chuỗi NST.
– Bước 3: Tạo các chuỗi NST mới bằng sinh sản từ các chuỗi NST hiện tại, có
tính đến ghép chéo và đột biến xảy ra (nếu có).
– Bước 4: Xác định hàm mục tiêu cho các chuỗi NST mới, và đưa nó vào trong
một dân số mới.
– Bước 5: Nếu điều kiện kết thúc thuật toán đã thỏa mãn thì dừng lại, và trả về
chuỗi NST tốt nhất cùng với giá trị hàm mục tiêu của nó, nếu không thì quay
về bước 3.
Sơ đồ giải thuật di truyền đơn giản:
21
Tạo quần thể ban
đầu của các
chuỗi NST
Xác định giá trị hàm mục tiêu
của các chuỗi NST
Tính toán các giá trị mục tiêu của chuỗi
NST mới và đưa nó vào quần thể mới
Tạo các chuỗi NST bằng cách sinh sản
từ các chuỗi NST hiện tại (có tính đến
ghép chéo và đột biến xảy ra)
Kiểm tra điều kiện kết
thúc thuật toán thỏa mãn
chưa?
Kết thúc
N
2.4. MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN DI TRUYỀN ĐƠN GIẢN
2.4.1. Cải tiến phương pháp chọn lọc

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

) ≤ f(i
2
) ≤ f(i
3
) thì NST i
1
sẽ chết và bị loại ra khỏi quần thể. Quá trình
này lặp lại cho đến hết NST còn lại.
2.4.2. Cải tiến toán tử lai ghép
2.4.2.1. Lai ghép ánh xạ từng phần (PMX – Partial Mappel Crossover)
Lai ghép ánh xạ từng phần có thể xem như một biến đổi của lai ghép 2 điểm giao
nhau bằng cách kết hợp với các thủ tục sửa chữa đặc biệt để giải quyết tính không
chính đáng (illegitimacy) có thể có. PMX gồm các bước sau:
• Chọn ngẫu nhiên 2 điểm cách nhau cùng với một chuỗi. Chuỗi con được định
nghĩa bởi 2 điểm cắt nhau được định nghĩa là ánh xạ từng phần.
• Trao đổi hai chuỗi con giữa các cá thể cha mẹ để tạo ra các thể con.
• Xác định quan hệ ánh xạ giữa các thành phần ánh xạ
• Hợp thức cá thể con với các quan hệ ánh xạ.
Ví dụ: Bài toán người chào hàng với 9 thành phố. Một NST biểu diễn toàn bộ
đường đi.
Cá thể cha: 93|8571|642
23
Cá thể mẹ: 35|2614|879
Đầu tiên hoán vị giữa cá thể cha (parent 1) và cá thể mẹ (parent 2)
Cá thể con 1: xx|2614|xxx
Cá thể con 2: xx|8571|xxx.
Ký hiệu “x” có thể được xem như ẩn số (unknown)
Hoán vị này cũng được định nghĩa một chuỗi những ánh xạ
2->8, 6 ->5, 1->7, 4->1.
Cuối cùng điều chỉnh với quan hệ ánh xạ, ta có thể điền thêm các thành phố (từ

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

Tương tục chúng ta được cá thể con khác:
Cá thể con 2: 57|2614|938.
2.4.2.3. Lai ghép dựa trên vị trí (Possition Base Crossover)
Lai ghép dựa trên vị trí thực chất là một loại đồng nhất cho mã hóa theo nghĩa đột
biến kết hợp với một thủ tục để sửa chữa. Trước tiên nó phát sinh ngẫu nhiên một
mặt nạ sau đó trao đổi các gene liên quan giữa cá thể cha và mẹ theo mặt nạ. Một
mặt nạ lai ghép là một chuỗi nhị phân đơn giản có kích thước NST như nhau. Sự
tương đương của mỗi bit tương ứng trong cá thể con, xác định cá thể cha mẹ nào sẽ
cung cấp bit đó.
Bởi vì lai ghép đồng nhất sẽ tạo ra cá thể con bất hợp lệ cho mã hóa đột biến, lai
ghép đột biến sẽ sử dụng một thủ tục sửa chữa để giải quyết tính bất hợp lệ.
Lai ghép dựa trên vị trí gồm các bước sau:
• Chọn ngẫu nhiên một tập hợp các vị trí từ một cá thể cha mẹ.
• Tạo ra một cá thể con bằng cách sao chép các ký hiệu từ cá thể cha mẹ tùy thuộc
vào bit của mặt nạ tại vị trí đó vào cá thể con.
25
Tổng số lần Open của 15 bộ đôi đó là 0,2703 ∼ 0,27 ………………………………. 54N ếu tính cả dấu cách ( ∪ ), thì có thêm ba bộ đôi với tần suất xuất hiệnnhư sau : ………………………………………………………………………………………………………….. 54D anh mục những từ viết tắtNST Nhiễm sắc thểGA Genetics AlgorithmsDES Data Encryption Standard. Danh mục những thuật ngữ thông dụng trong giải thuật di truyềnTrong tự nhiên Trong giải thuật di truyềnGene Đặc tính, ký tựChromosome ( Nhiễm sắc thể ) ChuỗiAllele ( gene tương ứng ) Giá trị của đặc tínhLocus ( ổ gene ) Vị trí chuỗiGenetype ( kiểu hình ) Tập thông số kỹ thuật, giải pháp luân phiên, cấu trúc được giải mãLỜI NÓI ĐẦUTrong thực tiễn đời sống, những bài toán tương quan đến mạng lưới hệ thống nhận thức, tri thứccủa con người, đều hàm chứa những đại lượng, thông tin, mà thực chất là khôngchính xác, không chắc như đinh, không không thiếu …. cho những mạng lưới hệ thống ra quyết định hành động. Ví dụ : Sẽ chẳng khi nào có thông tin, tài liệu, cũng như những quy mô tính toánđầy đủ và đúng chuẩn cho bài toán dự báo thời tiết. Trong nghành nghề dịch vụ khoa học cũng vậy, những mạng lưới hệ thống phức tạp trên thực tiễn thườngkhông thể miêu tả rất đầy đủ, và đúng mực bởi những phương trình toán học truyền thống lịch sử. Kết quả là những cách tiếp cận tầm cỡ dựa trên kỹ thuật nghiên cứu và phân tích, và những phươngtrình toán học nhanh gọn không còn tương thích. Vì thế công nghệ tiên tiến tính toán mềmchính là giải pháp thiết yếu trong nghành này. Công nghệ tính toán mềm gồm có 3 thành phần chính : – Điều khiển mờ ( Fuzzy Control ) – Mạng nơ-ron tự tạo ( Neural Network ) – Giải thuật di truyền ( Genetic Algorithm ) Do thời hạn không nhiều và khối lượng việc làm khám phá khá lớn nên trongkhuôn khổ đồ án tốt nghiệp này, để tìm hiểu và khám phá cho sâu, em tập trung chuyên sâu điều tra và nghiên cứu giảithuật di truyền. Hiện nay, thuật toán di truyền cùng với logic mờ được ứng dụng thoáng đãng trongcác nghành phức tạp, những yếu tố khó, sử dụng những kỹ thuật tìm kiếm lời giải, vớikhô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ìn nhận sựtối ưu của tác dụng thu được. Chính thế cho nên, thuật giải di truyền đã trở thành đề tàinghiên cứu mê hoặc và đem đến nhiều ứng dụng trong thực tiễn. Xuất phát từ những yếu tố trên, khóa luận đã tìm hiểu và khám phá, nghiên cứu và điều tra giải thuật ditruyền. Sau đó sử dụng giải thuật di truyền cổ xưa phối hợp với chiêu thức thốngkê ngôn ngữ học xử lý 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 sức, chỉ bảocủa thầy cô và những bạn ! Chương 1 : TÍNH TOÁN MỀM1. 1. KHÁI NIỆM TÍNH TOÁN MỀMTính toán mềm ( Soft Computing ) khác với tính toán cứng truyền thống lịch sử ( HardComputing ) ở chỗ : không như tính toán cứng, tính toán mềm được cho phép sự khôngchính xác, tính bất định, gần đúng, giao động trong tính toán. Các quy mô tính toánmềm thường dựa vào kinh nghiệm tay nghề của con người, sử dụng dung sai được cho phép của sựkhông đúng chuẩn, tính bất định, gần đúng, giao động để tìm lời giải hiệu suất cao – đơn thuần, dễ hiểu, dễ triển khai, ngân sách thấp. Tính toán mềm biểu lộ một sự vận động và di chuyển, biến hoá quan trọng trong những hướngtính toán. Sự vận động và di chuyển này phản ánh sự kiện trí tuệ con người, không như máytính, có năng lực đáng kể trong việc tàng trữ và giải quyết và xử lý thông tin không đúng chuẩn vàbất định, và đây mới là những thông tin thực tiễn và thường gặp. Các ứng dụng thành công xuất sắc của tính toán mềm cho thấy tính toán mềm ngày càngphát triển mạnh và đóng vai trò đặc biệt quan trọng trong những nghành nghề dịch vụ khác nhau của khoa họcvà kỹ thuật. Tính toán mềm được ứng dụng trong hầu hết những chuyên ngành kỹ thuậtnhư kỹ thuật điện, kỹ thuật tinh chỉnh và điều khiển, kỹ thuật hoá học, kỹ thuật thiết kế xây dựng, … Kỹthuật điện là nghành tiên phong ứng dụng tính toán mềm trong những nghành như điềukhiển mờ, giải quyết và xử lý ảnh mờ, mạch điện tử dùng logic, người máy, …. Khái niệm “ Tính toán mềm ” được Zadeh đưa ra lần tiên phong vào năm 1994 đượcmô tả như sau : “ Một cách cơ bản, tính toán mềm không phải là thể thống nhất cáckhái niệm và kỹ thuật. Đúng ra, nó là sự phối hợp của những chiêu thức riêng không liên quan gì đến nhau theocách này hay cách khác để thích nghi với nguyên tắc của nó. Tại điểm giao đó, mụcđích ở đầu cuối của tính toán mềm là khai thác năng lực thứ lỗi ( Tolerance ) cho tínhkhông đúng mực hay tính bất định để đạt được tiềm năng với ngân sách thấp ”. Một cáchđơn giản hơn, “ Tất cả những tính toán có gồm có tính không đúng mực một cách cóchủ đích trong tính toán ở một hay nhiều mức và cho phép tính không đúng mực nàylàm biến hóa ( làm giảm ) độ đúng chuẩn của bài toán, hay “ làm mềm ” tiềm năng tối ưu ởmột số bước, đều bị coi là thuộc nghành tính toán mềm ”. 1.2. PHÂN BIỆT TÍNH TOÁN MỀM VÀ TÍNH TOÁN CỨNGTính toán truyền thống cuội nguồn, hay còn gọi là tính toán cứng, là chiêu thức sử dụngcác kỹ thuật tính toán, dựa trên tài liệu nguồn vào để đưa ra hiệu quả sau cuối một cáchchính xác theo nhu yếu của bài toán. Bảng dưới đây đưa ra 1 số ít điểm độc lạ giữa tính toán mềm và tính toáncứng, để tất cả chúng ta có được một tưởng tượng đơn cử hơn về tính toán mềm. Điểm so sánh Tính toán cứng Tính toán mềmDữ liệu giải quyết và xử lý – Xử lý bài toán dựa trên sốliệu đúng chuẩn. – Ví dụ : Giá trị của A phảilà 0 hoặc 1 : { 0,1 } – Không yên cầu tài liệu phải chínhxác. – Ví dụ : Giá trị của A hoàn toàn có thể nằmtrong khoảng chừng từ 0 đến 1 : [ 0,1 ] Kết quả đầu ra – Yêu cầu đưa ra kết quảtối ưu ( hiệu quả chính xáchoàn toàn ) – Yêu cầu đưa ra tác dụng gần tốiưu ( được cho phép sự xô lệch nhấtđịnh trong hiệu quả tìm được ) Kỹ thuật tínhtoán – Sử dụng kỹ thuật tínhtoán truyền thống cuội nguồn – Kỹ thuật tính toán dựa trênHeuristic được sử dụng phổbiếnThời gian tínhtoán – Thời gian tính toánthường chậm hơn. Trongmột số trường hợp, khôngthể đưa ra tác dụng trongthời gian đồng ý được – Thời gian tính toán nhanh hơnvới ngân sách thấp hơnLĩnh vực vận dụng – Các bài toán nhu yếu lờigiải đúng mực, không chophép sự rơi lệch. – Các bài toán không yêu cầulời giải đúng mực, tuy nhiên phảiđưa ra tác dụng trong mộtkhoảng thời hạn nhất địnhvới ngân sách nhất địnhBảng 1 : So sánh tính toán cứng và tính toán mềm1. 3. TẠI SAO CẦN PHẢI CÓ TÍNH TOÁN MỀMTrong thực tiễn đời sống, những bài toán tương quan đến mạng lưới hệ thống nhận thức, trí tuệcủa con người đều hàm chứa những đại lượng, thông tin không đúng chuẩn, khôngchắc chắn, không vừa đủ. Ví dụ : sẽ chẳng khi nào có những thông tin, tài liệu cũng nhưcác quy mô tính toán rất đầy đủ, và đúng chuẩn cho bài toán dự báo thời tiết. Nhìn chungcon người luôn ở trong toàn cảnh không có thông tin đúng mực, và khá đầy đủ cho những hệthống ra quyết định hành động. Trong nghành nghề dịch vụ khoa học kỹ thuật cũng vậy, những mạng lưới hệ thống phức tạp trên thực tếthường không hề diễn đạt một cách khá đầy đủ, và đúng mực bởi những phương trình toánhọc truyền thống lịch sử. Kết quả là những cách tiếp cận tầm cỡ dựa trên kỹ thuật phântích, và những phương trình toán học nhanh gọn tỏ ra không còn tương thích. Vì thế, công nghệ tiên tiến tính toán mềm chính là giải pháp trong nghành này. Một số đặc thù của công nghệ tiên tiến tính toán mềm : – Tính toán mềm địa thế căn cứ trên những đặc thù, hành vi của con người, và tự nhiên đểđưa ra quyết định hành động hài hòa và hợp lý trong điều kiện kèm theo không đúng chuẩn, không chắc như đinh. – Các thành phần của tính toán mềm có sự bổ trợ, tương hỗ nhau. – Tính toán mềm là một hướng nghiên cứu và điều tra mở, bất kể một kỹ thuật mới nào đượctạo ra từ việc bắt chước trí mưu trí của con người, đều hoàn toàn có thể trở thành mộtthành phần mới của tính toán mềm. – Chính nhờ những đặc thù đó mà tính toán mềm đang được nghiên cứu và điều tra và ứngdụng thoáng rộng trong nhiều nghành, đặc biệt quan trọng là : trí tuệ tự tạo, khoa học máytính và học máy. Cụ thể : ◊ Không phải bài toán nào cũng có thuật toán hoàn toàn có thể xử lý được bằng tínhtoán cứng. ◊ Không phải bài toán nào có thuật toán hoàn toàn có thể xử lý được bằng tính toáncứng, cũng hoàn toàn có thể thực thi với ngân sách và thời hạn đồng ý được. ◊ Khi bản thân tài liệu là không đúng mực thì không hề xử lý được bằngphương pháp đúng mực. Với những lợi thế đó, tính toán mềm đang dần bộc lộ vai trò của mình nhất làtrong việc xử lý yếu tố mới. 1.4. CÁC KỸ THUẬT TRONG TÍNH TOÁN MỀMCông nghệ tính toán mềm gồm có 3 thành phần chính : – Điều khiển mờ ( Fuzzy Control ) – Mạng nơ-ron tự 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 đíchcho phép những thành phần thuộc về một tập liên tục thay cho rời rạc. Kể từ đó, những ứngdụng và tăng trưởng dựa trên khái niệm tưởng chừng rất đơn thuần này, đã mang lạinhững hiệu quả khó hoàn toàn có thể tin được, thậm chí còn khó hoàn toàn có thể chỉ ra những ứng dụng, pháttriển hay loại sản phẩm nào không có tương quan đến khái niệm tập mờ. Ví dụ : chúng tathườ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 xử lý những bài toán tốiưu, đưa ra những bài toán có tính thực tiễn, xử lý bài toán với ngân sách thấp và trongthời gian nhanh hơn ( mặc dầu gật đầu việc hoàn toàn có thể có sai số ). Trong nghành nghề dịch vụ antoàn thông tin, tập mờ cũng được sử dụng rất thoáng rộng. Tất cả những thuật toán, giảithuật, kỹ thuật được trình làng 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à quy mô tính toán dựa trên bộ não. Mô hình NN gồm có những bộ giải quyết và xử lý _các Nơron _ có mối link ngặt nghèo với nhau, tương tự như như họat động của cácNơron trong não người. Các Nơron được liên kết bởi những đường link có đánhtrọng số, truyền tín hiệu từ nơron này đến nơron khác. Mỗi nơron nhận những tín hiệuđầu vào ( có trọng số ) trải qua những đường liên kết và tạo một tín hiệu đầu ra. Hình vẽ sau đây miêu tả quy mô của mạng nơron nổi bật : NeuroInput Signals Weights Output SignalsHình 1. Mô hình mạng Nơron điển hình1. 4.3. Chương trình tiến hóa ( Evolutionary Computation – EC ) Kĩ thuật EC gồm có rất nhiều những giải thuật khác nhau, ở đây, tiểu luận trình bàymột trong những giải thuật tiến hóa thông dụng nhất – giải thuật di truyền ( GeneticAllgothm – GA ). Hình vẽ bên dưới diễn đạt hoạt động giải trí của một giải thuật di truyền điểnhình. 10P opulationNewPopulationMutation MatingSelectionHình 2 – Mô hình hoạt động giải trí của giải thuật di truyền. Bài này sẽ trình diễn những khái niệm cơ bản về giải thuật di truyền và vận dụng trongbài toán đơn cử. Chương 2 : GIẢI THUẬT DI TRUYỀN2. 1. KHÁI NIỆM GIẢI THUẬT DI TRUYỀNThuật toán di truyền ( Genetic Algorithm_GA ) là kỹ thuật chung giúp giải quyếtbà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 triết lý tiến hóa muôn loài của Darwin ) trong điều kiện kèm theo lao lý sẵn củamôi trường. GA là một thuật giải và tiềm năng của GA không nhằm mục đích đưa ra lời giảichính xác tối ưu, mà là đưa ra giải thuật tương đối tối ưu. 2.1.1. Đặc trưng của thuật toán di truyền tầm cỡ • Thuật toán di truyền lập luận ngẫu nhiên thay vì xác lập. • Thuật toán di truyền duyệt hàng loạt những giải pháp, sau đó chọn lấy giải pháp tươngđối tốt dựa trên thông số thích nghi. • Thuật toán di truyền không chú ý cụ thể yếu tố, mà chỉ quan tâm đến giải pháp, đặcbiệ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 thao tác với một mã hóa của tập hợp tham số, chứ khôngphải là một tham số. – Thuật toán di truyền tìm kiếm từ một quần thể những điểm, chứ không phải là mộtđiểm hoặc một vài điểm như chiêu thức tìm kiếm leo đồi ( Hill Climbing ). – Thuật toán di truyền nhìn nhận thông tin với hàm mục tiêu, mà không dựa vào đạohàm hay thông tin bổ trợ khác. – Thuật toán di truyền sử dụng những luật đổi khác theo Phần Trăm, mà không sử dụngluật quyết định hành động. 2.1.2. Cơ sở sinh học của giải thuật di truyềnTrong khung hình sinh vật, những gene link với nhau theo chính sá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 hành động sự sống còn của cơ thểđó. Trong tự nhiên một loài muốn sống sót phải thích nghi với thiên nhiên và 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íchnghi với môi trường tự nhiên sẽ dần bị tuyệt chủng. Môi trường tự nhiên luôn luôn đổi khác, nên cấu trúc nhiễm sắc thể cũng thay đổiđể thích nghi với thiên nhiên và môi trường, và ở thế hệ sau luôn có độ thích nghi cao hơn thế hệtrước. Cấu trúc này có được nhờ sự trao đổi thông tin ngẫu nhiên với môi trường tự nhiên bênngoài, hay giữa chúng với nhau. Dựa vào đó những nhà khoa học máy tính xây dựngmột giải thuật tìm kiếm tinh xảo dựa trên cơ sở tinh lọc tự nhiên và quy luật tiến hóa, gọi là giải thuật di truyền ( Genetic Algorithms ). 122.1.3. Tư tưởng của giải thuật di truyềnCó 1 số ít lớn những bài toán người ta chưa tìm thuật toán tương đối nhanh để giảiquyết chúng. Nhiều bài toán trong lớp này là những bài toán quy hoạch thường nảy sinhtrong những ứng dụng. Với bài toán quy hoạch thuộc loại khó, hoàn toàn có thể tìm được thuậttoán “ nhanh ”, cho tác dụng gần tối ưu. Đối với một số ít bài toán quy hoạch khó, tacũng hoàn toàn có thể tìm thuật toán Xác Suất, thuật toán này không bảo vệ cho tác dụng tốiưu, nhưng bằng cách chọn ngẫu nhiên đủ nhiều “ vật chứng ”, hoàn toàn có thể giảm tùy ý xácsuất sai của tác dụng. Nói một cách trừu tượng, việc giải bài toán hoàn toàn có thể xem như tìm kiếm trong khônggian với giải thuật hoàn toàn có thể. Vì cái đích của tất cả chúng ta là “ lời giải tốt nhất ”, ta hoàn toàn có thể xemphương pháp giải bài toán là quy trình tối ưu hóa. Đối với khoảng trống nhỏ, phươngpháp “ vét cạn ” cổ xưa là đủ dùng. Đối với những khoảng trống lớn hơn, yên cầu nhữngphương pháp trí tuệ tự tạo đặc biệt quan trọng. Thuật toán di truyền ( GA ) nằm trong cácphương pháp đặc biệt quan trọng đó. 13T ư tưởng của thuật toán di truyền là xem xét, nhìn nhận những gene thế nào là tốt chomục tiêu, sử dụng nó tiếp cho thế hệ sau. Nói theo ngôn từ di truyền là giữ lại cácgene trội, vô hiệu những gene không tốt, hay là đào thải những thế hệ không tốt. 2.1.4. Hoạt động của giải thuật di truyềnThuật toán di truyền dùng nhiều ngôn từ của ngành di truyền học. Chúng ta sẽnói về những “ thành viên ” trong một quần thể. Thường thì những thành viên này được gọi là xâu, hoặc nhiễm sắc thể. Mỗi loài có một số lượng nhiễm sắc thể nhất định ( Ví dụ : cơ thểngười có 46 nhiễm sắc thể ). Tuy nhiên, trong bài này, ta chỉ nói về những thành viên cóđúng một nhiễm sắc thể. Mỗi nhiễm sắc thể gồm có những đơn vị chức năng – gene – xếp liêntiếp ; mỗi gene tinh chỉnh và đ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àumắt ) hoàn toàn có thể được biểu lộ dưới nhiều mức độ khác nhau. Ta nói gene đó có nhiềutrạng thái ( gọi là state ). Mỗi nhiễm sắc thể ( thành viên ) sẽ biểu lộ một lời giải hoàn toàn 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 pháp luật bởi ngườilập trình ). Một quy trình tiến hóa được triển khai 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 khoảng trống những giải thuật hoàn toàn có thể. Sự tìm kiếmnày yên cầu sự cân đối giữa hai mục tiêu : Khai thác giải thuật tốt nhất, và khám phá14không gian tìm kiếm. Phương pháp “ leo núi ” là một ví dụ về kế hoạch khai thác lờigiải tốt nhất theo những hướng nâng cấp cải tiến. Tìm kiếm ngẫu nhiên là một ví dụ nổi bật củasự tò mò khoảng trống tìm kiếm, không chú trọng khai thác những miền hứa hẹn trongkhông gian tìm kiếm. Thuật toán di truyền là lớp những chiêu thức tìm kiếm tổngquát với sự cân đối đáng kể giữa khai thác và mày mò khoảng trống tìm kiếm. Thuật toán di truyền cũng như những thuật toán tiến hóa nói chung, hình thành dựatrên khái niệm cho rằng quy trình tiến hóa tự nhiên là tuyệt vời nhất, hài hòa và hợp lý nhất vàtự nó đã mang tính tối ưu. Quan niệm này hoàn toàn có thể được xem là một tiên đề đúng, không chứng tỏ được nhưng tương thích với thực tiễn khách quan. Quá trình tiến hóathể hiện tính tối ưu ở chỗ : thế hệ sau khi nào cũng tốt hơn, tăng trưởng hơn, hoàn thiệnhơn thế hệ trước. Tiến hóa tự nhiên được duy trì bằng hai quy trình cơ bản : sinh sảnvà tinh lọc tự nhiên. Xuyên suốt quy trình tiến hóa tự nhiên, là thế hệ mới luôn đượcsinh ra để bổ trợ và thay thế sửa chữa thế hệ cũ. Cá thể nào tăng trưởng hơn, thích ứng hơn với thiên nhiên và môi trường sẽ sống sót, thành viên nàokhông thích ứng với môi trường tự nhiên sẽ bị đào thải. Sự đổi khác môi trường tự nhiên là động lựctiến hóa. trái lại tiến hóa cũng ảnh hưởng tác động trở lại, góp thêm phần làm đổi khác môi trường tự nhiên. Trong thuật giải di truyền, những thành viên mới liên tục được sinh ra trong quá trìnhtiến hóa nhờ sự lai ghép ở thế hệ cha mẹ. Một thành viên mới hoàn toàn có thể mang những tínhtrạng của cha mẹ ( di truyền ), cũng hoàn toàn có thể mang những tính trạng trọn vẹn mới ( độtbiến ). Di truyền và đột biến là hai chính sách quan trọng như nhau trong tiến hóa, dù độtbiến xảy ra với Xác Suất nhỏ hơn nhiều so với di truyền. Các thuật toán tiến hóa, tuycó những đặc thù độc lạ, nhưng đều mô phỏng những quy trình cơ bản : lai ghép, đột biến, sinh sản và tinh lọc tự nhiên. Như vậy, quy trình tiến hóa càng lâu thì càng có điều kiện kèm theo cho những thành viên tốt đượcsinh ra, và chất lượng của thành viên càng được nâng lên. 152.2. CẤU TRÚC GIẢI THUẬT DI TRUYỀN ĐƠN GIẢNTrong thuật toán di truyền đơn thuần, những thành viên hay còn gọi là NST ( Nhiễm sắcthể ) được mã hóa thành một chuỗi nhị phân gồm giá trị 0 và 1. Một NST trong GAcổ điển có dạng sau : 0 0 1 1 0 0 1 1 1M ỗi NST trình diễn một lời giải hoàn toàn có thể có của bài toán. Một quy trình tiến hóađược thực thi trên một quần thể ( một tập hợp NST ) tương tự với sự tìm kiếmtrong khoảng trống giải thuật hoàn toàn có thể. Sự tìm kiếm này yên cầu sự cân đối giữa hai mụcđích : tìm giải thuật tốt nhất và mày mò khoảng trống tìm kiếm mới. GA cổ xưa thực thi tìm kiếm theo nhiều hướng bằng cách duy trì một tập lờigiải hoàn toàn có thể, khuyến khích sự hình thành và trao đổi thông tin giữa những hướng. Tập lờigiải trải qua quy trình tiến hóa và ở đầu cuối cho ta một lời giải đủ tốt được chọn đểtái sinh, những giải thuật tồi bị vô hiệu. Để phân biệt mức độ tốt xấu giữa những giải thuật khácnhau người ta dùng một hàm gọi là “ hàm mục tiêu ” hay “ hàm thích nghi ” vì hàmnày tương tự với thiên nhiên và môi trường sống hay thuyết tiến hóa. Thuật toán di truyền đơn giản gồm có ba toán tử sau : 16 • Tái tạo ( Reproduction ) • Lai ghép ( Crossover ) • Đột biến ( Mutation ) 2.2.1. Tái tạoTái tạo là một quy trình trong đó những chuỗi màn biểu diễn thành viên được sao chép lại tùytheo giá trị hàm mục tiêu f ( những nhà sinh vật học gọi hàm này là hàm thích nghi ). Toán tử này được xem là quy trình tinh lọc trong tự nhiên. Hàm mục tiêu f ( i ) đượcgán cho mỗi thành viên trong dân số. Việc sao chép lại những chuỗi tùy theo giá trị thíchnghi của chúng, có nghĩa là : Những chuỗi có giá trị thích nghi cao hơn sẽ có nhiềucơ hội góp phần những chuỗi con cho thế hệ tiếp theo. Thao tác sinh sản ( chọn cha mẹ ) được điều khiển và tinh chỉnh bằng cách quay bánh xeroulette, trong đó mỗi chuỗi trong dân số chiếm một khe có size tỉ lệ vớiđộ thích nghi ( fitness ) của nó trên bánh xe. Giả sử những chuỗi của quần thể bắt đầu đã khởi tạo trong bài toán hộp đen có cácgiá trị hàm thích nghi như trong bảng sau. Lấy tổng độ thích nghi của 4 chuỗi, chúngta đượ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.42 11000 576 49.23 01000 64 5.5174 10001 361 30.9 Tổng cộng 1170 100.0 Các chuỗi của bài toán mẫu và những giá trị thích nghiBánh xe roulette được đánh trọng số tương thích cho sự tái tạo của thế hệ này đượcthể hiện trên hình sau : Sự sinh sản đơn thuần phân bổ những chuỗi con cháu nhờ sử dụng bánh xe Roulettevới những khe hở tỉ lệ với độ thích nghi. Với bài toán hộp đen, để sinh sản tất cả chúng ta chỉ cần quay bánh xe Roulette 4 lần. Đối với bài toán đơn cử thì : Chuỗi 1 có giá trị thích nghi là 169 đại diện thay mặt cho 0.144. Tương tự với những chuỗicò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 trongthế hệ tiếp theo. 1849.2 % 5.5 % 30.9 % 14.4 % 2.2.2. Lai ghépMỗi khi một chuỗi được chọn để sinh ra, một bản sao đúng chuẩn của những chuỗi đósẽ được tạo ra. Các bản sao này được đưa vào bể ghép đôi ( mating pool ). Toán tử laighép đơn thuần hoàn toàn có thể được triển khai theo hai bước : • Bước 1 : Chọn ngẫu nhiên hai ( hay nhiều ) thành viên 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ố ít ngẫu nhiên trong khoảng chừng từ 1 đến m-1 ( ta gọi làđiểm lai ). Điểm lai chia những chuỗi cha mẹ dài m thành 2 nhóm con dài mvà. Hai chuỗi NST con mới là m11 + m22và m12 + m21Đưa hai thành viên mới này vào quần thể để tham gia những quy trình tiến hóatiếp theo. Ví dụ : Về phép lai một điểm với Phần Trăm Pc hoàn toàn có thể mô phỏng như sau : 19V í dụ về phép lai ( lấy từ [ 4 ] ) Cơ chế sinh sản và lai ghép chéo đơn thuần, gồm có những việc sinh số ngẫu nhiên, sao chép chuỗi và trao đổi những chuỗi thành phần. Tuy nhiên, điểm cần nhấn mạnh vấn đề 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 kỳ lạ thành viên con mang 1 số ít tính trạng không có trong mã ditruyề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 chothuật toán tránh được những cực trị cục bộ. Phép đột biến xảy ra với Phần Trăm Pm nhỏhơn rất nhiều so với Phần Trăm Pc. Một phép đột biến hoàn toàn có thể miêu tả như sau : • Bước 1 : Chọn ngẫu nhiên một thành viên cha mẹ bất kể trong quần thể. Giả sử NSTcủa cha mẹ đều có m gene • Bước 2 : Tạo 1 số ít ngẫu nhiên k trong khoảng chừng từ 1 đến m ( 1 ≤ k ≤ m ). Thay đổigene thứ k và trả thành viên này về quần thể để tham gia quy trình tiến hóa tiếp theoVí dụ về phép đột biến với Xác Suất Pm : 01101 ==> 0111120 Đột biến tại bít thứ 4N ếu sự sinh sản theo độ thích nghi tích hợp với sự ghép chéo làm cho giải thuật ditruyền có năng lượng giải quyết và xử lý tốt hơn, thì sự đột biến đóng vai trò quyết định hành động thứ 2 tronghoạt động của giải thuật di truyền. Sự đột biến là thiết yếu chính bới : mặc dầu sự sinh sảnvà ghép chéo đã tìm kiếm hiệu suất cao và tái tích hợp lại những gene với nhau, nhưng thỉnhthoảng chúng hoàn toàn có thể làm mất một vài gene hữu dụng nào đó ( ví dụ bít 1 hay bít 0 tạinhững vị trí đặc biệt quan trọng ). Trong những mạng lưới hệ thống gene tự tạo, toán tử đột biến sẽ chốnglại sự mất mát không được Phục hồi đó. Trong thuật toán di truyền đơn thuần, độtbiến là sự biến hóa ngẫu nhiên và không tiếp tục ( 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 giải trí ngẫu nhiên trongkhô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ộtchính sách bảo hiểm chống lại rủi ro tiềm ẩn mất mát những gene quan trọng. 2.3. SƠ ĐỒ GIẢI THUẬT DI TRUYỀNGiải thuật di truyền gồm có những bước sau : – Bước 1 : Khởi tạo quần thể ( population ) bắt đầu của những NST. – Bước 2 : Xác định giá trị hàm mục tiêu cho mỗi chuỗi NST. – Bước 3 : Tạo những chuỗi NST mới bằng sinh sản từ những chuỗi NST hiện tại, cótính đến ghép chéo và đột biến xảy ra ( nếu có ). – Bước 4 : Xác định hàm mục tiêu cho những chuỗi NST mới, và đưa nó vào trongmột dân số mới. – Bước 5 : Nếu điều kiện kèm theo kết thúc thuật toán đã thỏa mãn nhu cầu thì dừng lại, và trả vềchuỗi NST tốt nhất cùng với giá trị hàm mục tiêu của nó, nếu không thì quayvề bước 3. Sơ đồ giải thuật di truyền đơn thuần : 21T ạo quần thể banđầu của cácchuỗi NSTXác định giá trị hàm mục tiêucủa những chuỗi NSTTính toán những giá trị tiềm năng của chuỗiNST mới và đưa nó vào quần thể mớiTạo những chuỗi NST bằng cách sinh sảntừ những chuỗi NST hiện tại ( có tính đếnghép chéo và đột biến xảy ra ) Kiểm tra điều kiện kèm theo kếtthúc thuật toán thỏa mãnchưa ? Kết thúc2. 4. MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN DI TRUYỀN ĐƠN GIẢN2. 4.1. Cải tiến chiêu thức chọn lọcThuật toán di truyền đơn thuần vận dụng chiêu thức tinh lọc dùng bánh xeRoulette như đã trình diễn ở trên. Cùng với sự tăng trưởng của thuật toán di truyền cácnhà điều tra và nghiên cứu đã đề xuất kiến nghị một số ít chiêu thức tinh lọc khác : tinh lọc sắp xếphạng, tinh lọc cạnh tranh đối đầu … 2.4.1. 1. Chọn lọc xếp hạng ( Rank Selection ) Phương pháp này sắp hạng thành viên dựa trên độ thích nghi của chúng. Cá thể xấunhất có độ thích nghi 1, sau đó 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 đối đầu ( Tournament selection ) • Chọn lọc cạnh tranh đối đầu 2 : 22H ai NST khác nhau được chọn ngẫu nhiên và được so sánh với NST sống sót. NếuNST ikhông tốt hơn NST inghĩa là f ( i ) ≤ f ( i ), thì NST ichết đi và bị loại rakhỏi quần thể ( link được phá vỡ tùy ý ). Quá trình này lặp lại cho đến hết NSTcòn lại. • Chọn lọc cạnh tranh đối đầu 3 : Giống như trên, 3 NST khác nhau được chọn ngẫu nhiên và được so sánh. Nếuchúng ta có f ( i ) ≤ f ( i ) ≤ f ( i ) thì NST isẽ chết và bị loại ra khỏi quần thể. Quá trìnhnày lặp lại cho đến hết NST còn lại. 2.4.2. Cải tiến toán tử lai ghép2. 4.2.1. Lai ghép ánh xạ từng phần ( PMX – Partial Mappel Crossover ) Lai ghép ánh xạ từng phần hoàn toàn có thể xem như một biến hóa của lai ghép 2 điểm giaonhau bằng cách phối hợp với những thủ tục thay thế sửa chữa đặc biệt quan trọng để xử lý tính khôngchính đáng ( illegitimacy ) hoàn toàn có thể có. PMX gồm những bước sau : • Chọn ngẫu nhiên 2 điểm cách nhau cùng với một chuỗi. Chuỗi con được địnhnghĩa bởi 2 điểm cắt nhau được định nghĩa là ánh xạ từng phần. • Trao đổi hai chuỗi con giữa những thành viên cha mẹ để tạo ra những thể con. • Xác định quan hệ ánh xạ giữa những thành phần ánh xạ • Hợp thức thành viên con với những quan hệ ánh xạ. Ví dụ : Bài toán người chào hàng với 9 thành phố. Một NST trình diễn toàn bộđường đi. Cá thể cha : 93 | 8571 | 64223C á thể mẹ : 35 | 2614 | 879 Đầu tiên hoán vị giữa thành viên cha ( parent 1 ) và thành viên mẹ ( parent 2 ) Cá thể con 1 : xx | 2614 | xxxCá thể con 2 : xx | 8571 | xxx. Ký hiệu “ x ” hoàn toàn có thể được xem như ẩn số ( unknown ) Hoán vị này cũng được định nghĩa một chuỗi những ánh xạ2 -> 8, 6 -> 5, 1 -> 7, 4 -> 1. Cuối cùng kiểm soát và điều chỉnh với quan hệ ánh xạ, ta hoàn toàn có thể điền thêm những thành phố ( từcá thể cha mẹ khởi đầu ), mà không có yếu tố xích míc. Cá thể con thứ 1 : 93 | 2614 | xxxCá thể con thứ 2 : 3 x | 8571 | xx9 “ x ” tiên phong trong thành viên con thứ 1 ( sẽ là 6 nhưng vẫn có xích míc ) được thaybởi 5, tựa như ta vận 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 | 578C á thể con thứ 1 : 36 | 8571 | 2492.4.2.2. Lai ghép có trật tự ( OX – Order Crossover ) Lai ghép có trật tự hoàn toàn có thể được xem như một biến thể của PMX sử dụng thủ tục sửachữa khác, OX gồm những bước sau : • Chọn ngẫu nhiên 1 chuỗi con từ thành viên cha mẹ. • Đưa ra một thành viên con bằng cách sao chép chuỗi con vào những vị trí tương ứngtrong thành viên cha mẹ. • Xóa tổng thể những ký tự từ thành viên 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à thành viên con cần. • Đặt những ký hiệu vào những vị trí không cố định và thắt chặt của những thành viên con từ trái sangphải theo trật tự của chuỗi để tạo ra thành viên con. Ví dụ : Cá thể cha : 93 | 8571 | 642C á thể mẹ : 35 | 2614 | 87924 Đầu tiên phân đoạn giữa để cắt những điểm được sao chép vào thành viên con : Cá thể con 1 : xx | 8571 | xxxCá thể con 2 : xx | 2614 | xxxChuỗi mở màn từ điểm cắt thứ 2 của thành viên mẹ là : 8-7-9 – 3-5-2 – 6-1-4 Chuỗi sau khi loại những thành phố 8, 5, 7, 1 cũng ở trong thành viên con đầu tiênlà : 9-3-2 – 6-4 Cuối cùng chuỗi này được đặt vào thành viên con 1 tiên phong để tạo ra thành viên con ( bắt đầutừ điểm cắt thứ 2 ). Cá thể con 1 : 64 | 8571 | 932T ương tục tất cả chúng ta được thành viên con khác : Cá thể con 2 : 57 | 2614 | 938.2.4.2.3. Lai ghép dựa trên vị trí ( Possition Base Crossover ) Lai ghép dựa trên vị trí thực ra là một loại như nhau cho mã hóa theo nghĩa độtbiến tích hợp với một thủ tục để thay thế sửa chữa. Trước tiên nó phát sinh ngẫu nhiên mộtmặt nạ sau đó trao đổi những gene tương quan giữa thành viên cha và mẹ theo mặt nạ. Mộtmặt nạ lai ghép là một chuỗi nhị phân đơn thuần có kích cỡ NST như nhau. Sựtương đương của mỗi bit tương ứng trong thành viên con, xác lập thành viên cha mẹ nào sẽcung cấp bit đó. Bởi vì lai ghép giống hệt sẽ tạo ra thành viên con bất hợp lệ cho mã hóa đột biến, laighép đột biến sẽ sử dụng một thủ tục thay thế sửa chữa để xử lý tính bất hợp lệ. Lai ghép dựa trên vị trí gồm những bước sau : • Chọn ngẫu nhiên một tập hợp những vị trí từ một thành viên cha mẹ. • Tạo ra một thành viên con bằng cách sao chép những ký hiệu từ thành viên cha mẹ tùy thuộcvào bit của mặt nạ tại vị trí đó vào thành viên con. 25

Source: https://mindovermetal.org
Category: Ứng dụng hay