MỤC LỤC
DANH MỤC CÁC HÌNH VẼ
LỜI NÓI ĐẦU 5
Chương I. Giới thiệu chung về xử lý ảnh và phương pháp nâng
cao chất lượng hình ảnh7
1. Giới thiệu chung về xử lý ảnh 7
2. Giới thiệu ảnh nhị phân 9
2.1. Một số khái niệm 9
2.2. Đặt bài toán nâng cao chất lượng ảnh bằng các phép toán hình thái11
2.3. Đặt bài toán nâng cao chất lượng ảnh bằng kỹ thuật tìm xương và làm mảnh13
3. Khái quát về phương pháp nâng cao chất lưởng hình ảnh 14
Chương II: Các khái niệm cơ bản về toán học hình thái 16
1. Quan hệ giữa khái niệm tập hợp và phép toán hình thái 16
1.1. Một số khái niệm cơ bản về tập hợp 17
1.2. Các phép toán logic trên ảnh nhị phân 20
2. Phép toán làm béo (Dilation) và làm gầy (Erosion) 21
2.1. Làm béo 21
2.2. Làm gầy 23
2.3. Phép toán Opening và Closing 23
2.4. Biến đổi Hit or Miss 27
3. Một số thuật toán dựa trên phép toán hình thái 28
3.1. Trích chọn biên 28
3.2. Tô miền 30
3.3. Tách các thành phần liên thông 31
3.4. Làm mảnh 33
3.5. Làm dầy 34
3.6. Tìm xương của ảnh 35
Chương III: Thuật toán di truyền 37
1. Thuật toán di truyền là gì? 37
2. Sử dụng thuật toán di truyền trong toán học hình thái 37
3. Hoạt động của thuật toán di truyền 38
3.1. Quá trình lai ghép (phép lai) 41
3.2. Quá trình đột biến (phép đột biến) 43
3.3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn) 44
4. Mô hình thuật toán 44
Chương IV: Một cách tiếp cận di truyền trong bài toán phân rã phân tử cấu trúc 46
1. Tiếp cận ngẫu nhiên 50
2. Cấu trúc dữ liệu 51
3. Giải thuật dựa trên thuật toán tìm kiếm di truyền 55
Chương V: Thực nghiệm 61
1. Mô tả bài toán và giả thuyết 61
2. Giao diện chính của chương trình 61
3. Một số kết quả thử nghiệm 62
Chương VI: Kết luận 67
72 trang |
Chia sẻ: maiphuongdc | Lượt xem: 1937 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Luận văn Tìm hiểu phép toán hình thái, phương pháp di truyền và ứng dụng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
p toán opening:
-
A B
là tập con của A
- Nếu C là tập con của D thì
C B
là tập con của
D B
-
A B B A B
Tương tự như vậy, phép toán closing thỏa mãn các tính chất sau:
- A là tập con của
A B
- Nếu C là tập con của D thì
C B
là tập con của
D B
-
A B B A B
Trang 26
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Các phép toán hình thái còn được sử dụng để xây dựng các bộ lọc. Ví
dụ như trong bài toán nhận dạng vân tay người, ảnh cần nhận dạng có nhiễu
(như thể hiện trong hình II.2.7(a). Các nhiễu là các chấm trắng nhỏ (khác với
ví dụ trước, trong ví dụ này nội dung của ảnh được thể hiện bởi các điểm ảnh
sáng còn nền là các điểm ảnh sẫm mầu). Mục tiêu của quá trình tiền xử lý ảnh
trước khi nhận dạng là việc lọc các thành phần nhiễu nhưng đồng thời phải
đảm bảo sự ảnh hưởng đến các thành phần vân tay ít nhất có thể. Để lọc các
thành phần nhiễu, ta sử dụng phần tử cấu trúc được mô tả trong hình II.2.7(b)
Toàn bộ hình II.2.7 thể hiện từng bước của quá trình lọc ảnh. Các nhiễu được
hoàn toàn loại bỏ trong phép toán làm gầy ở giai đoạn đầu do kích thước của
các điểm nhiễu là nhỏ hơn kích thước của phần tử cấu trúc và sau đó được
khôi phục lại nguyên dạng như ảnh lúc đầu. Chú ý rằng, sau quá trình này gần
như toàn bộ các thành phần nhiễu đã bị lọc bỏ.
Hình II.2.7. Xử lý nhiễu trong ảnh vân tay
Trang 27
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2.4. Biến đổi Hit or Miss
Biến đổi Hit or Miss là một công cụ cơ bản để dò tìm ảnh. Tôi giới
thiệu khái niệm này với sự trợ giúp của hình I.2.8. Trong hình, tập A bao gồm
3 ảnh X, Y, Z. mục tiêu là tìm vị trí của một trong 3 ảnh trên, giả sử là X
Giả sử gốc của mỗi ảnh là tại trung tâm của ảnh. Giả sử X được bao bởi
một cửa sổ nhỏ W. Ta định nghĩa nền của tập X trên ảnh W là tập tất cả các
điểm ảnh thuộc W mà không thuộc X, ký hiệu là W-X như được mô tả trong
hình II.2.8(b). Trong hình II.2.8(c) mô tả phần bù của tập A. Hình II.2.8(d)
thể hiện tập A gầy . Nhớ lại rằng tập gầy A bởi X là tập tất cả các vị trí của
điểm gốc X sao cho X hoàn toàn nằm trong tập A. Hiểu theo cách hình học
thuần túy thì AӨX có thể coi như là tập hợp tất cả các điểm gốc của X mà tại
đó X giao (match) với tập A. Hình II.2.8 thể hiện việc làm gầy phần bù tập A
bởi phần tử cấu trúc (W − X ) . Phần tối phía ngoài trong hình II.2.8(e) là
phần bị ăn mòn.
Trang 28
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.2.8. Phép toán Hit or Miss
Chú ý rằng trong hình II.2.8(d) và (e), tập tất cả các vị trí mà X hoàn
toàn nằm trong A là giao của ảnh gầy A bởi X với ảnh gầy AC bởi (W − X )
như trong hình II.2.8(f). Nói một cách khác nếu ký hiệu B là tập cấu thành lên
X và nền của nó, tập các điểm phù hợp (match) của B trong A, ký hiệu là
được định nghĩa bởi:
Chúng ta có thể ký hiệu B=(B1, B2), trong đó B1 là tập được tạo thành
từ B và đối tượng, còn B2 được tạo thành từ B và nền. Khi đó, công thức trên
có dạng biến đổi khác:
3. Một số thuật toán dựa trên phép toán hình thái
3.1. Trích chọn biên
Biên của A được ký hiệu là β(A) có thể đạt được bằng cách ban đầu làm
gầy A bởi B sau đó thực hiện phép trừ A.
() ( )AAAB
(II.3-1)
với B là phần tử cấu trúc thích hợp.
Hình II.3.1. mô tả cơ chế của thuật toán trích chọn biên. Sử dụng thuật toán
trên đối với đối tượng đơn giản A và phần tử cấu trúc B, kết quả đạt được là
biên của đối tượng A như đã thấy ở hình II.3.1(d)
Trang 29
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.3.1. Trích chọn biên
Mặc dù phần tử cấu trúc B ở trong ví dụ được cho bởi hình II.3.1 là một
trong các phần tử cấu trúc được sử dụng nhiều nhất, tuy nhiên, tùy theo đặc
điểm của ảnh cần được trích chọn, mà ta chọn các phần tử cấu trúc khác cho
phù hợp. Biên của hình A trong ví dụ này có độ dày là 1 điểm ảnh, nhưng với
phần tử cấu trúc kích thước là 5 x 5, thì biên của A sẽ có độ dày là 2 và 3
điểm ảnh. Như vậy, với các phần tử cấu trúc khác nhau thì cho ta kết quả khác
nhau. Do vậy, việc chọn các phần tử cấu trúc tuỳ thuộc vào mục tiêu cũng
như các ứng dụng cụ thể.
Hình II.3.2 cho ta một ứng dụng thuật toán tách biên cụ thể hơn. Trong
ví dụ này, phần tử 1 đại diện cho điểm ảnh trắng, phần tử 0 tương ứng với
điểm ảnh đen. Do phần tử cấu trúc là phần tử cấu trúc trong ví dụ ở hình
II.3.1, cho nên biên của ảnh đạt được chỉ có kích thước là một điểm ảnh.
Trang 30
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.3.2. Ảnh được trích chọn biên
3.2. Tô miền
Trong hình I.3.3, tập A chứa một tập con mà các phần tử liên thông 8.
Xuất phát với một điểm p nằm bên trong, mục tiêu là tô toàn bộ miền có biên
bởi các điểm đó.
Ta xây dựng thuật toán như sau:
1( )
c
k kX X B A
(I.3-2)
Trong đó X0=P và B là phần tử cấu trúc đối xứng như ở trên hình I.3.3.
Thuật toán kết thúc tại bước k nếu Xk= Xk-1. Miền được tô chính là hợp của
tập A và Xk
Trang 31
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.3.3. Ví dụ thuật toán tô miền
3.3. Tách các thành phần liên thông
Trong rất nhiều ứng dụng, việc phân tích ảnh đòi hỏi ta phải tách các
thành phần liên thông để phục vụ cho tác vụ xử lý. Ví dụ như trong ứng dụng
nhận dạng mặt người, việc đầu tiên cần phải xử lý là phải tách các thành phần
liên thông, sau đó thực hiện việc nhận dạng trên các thành phần đó.
Giả sử A chứa thành phần liên thông Y và p là một điểm của Y đã được
biết trước.
Thuật toán được mô tả bởi phương trình sau:
Xk = (Xk-1 B) A k = 1,2,3, .... (I.3-3)
Trong đó X0 = p và B là phần tử cấu trúc thích hợp. Nếu Xk= Xk-1 thì
thuật toán hội tụ Y = Xk.
Phương trình trên trên có cấu trúc giống như phương trình (II.3-2), tuy
nhiên trong phương trình (II.3-3), thành phần A tham gia thuật toán, ngược
Trang 32
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
lại, trong phương trình (II.3-2) thành phần bù của tập A tham gia thuật toán.
Hình II.3.4. Tìm các thành phần liên thông trong ảnh
Thành phần liên thông được sử dụng rộng rãi trong chẩn đoán tự động.
Hình II.3.5(a) thể hiện ảnh X quang cấu trúc xương của một con cá. Mục tiêu
là phải xác định được vật lạ trong quá trình xử lý cá trước khi đóng gói và gửi
đi. Trong trường hợp này, các điểm ảnh thể hiện đối tượng (xương và vật lạ)
có mật độ nhiều hơn so với mật độ các điểm ảnh cấu thành nền. Như vậy dẫn
tới mức xám của đối tượng so với nền của ảnh sẽ có sự chênh lệch. Bằng cách
đưa ra một ngưỡng đơn, ta có thể táchđược đối tượng ra khỏi nền. Kết quả
của quá trình tách nền được thể hiện trên hình II.3.5(b).
Đặc trưng quan trọng nhất của các hình phía dưới đó chính là các điểm
cấu thành xương chứ không phải là các cô lập, các vật lạ. Chúng ta có thể giả
thuyết rằng chỉ có các điểm còn lại sau khi ta thực hiện phép toán làm gầy bởi
phần tử cấu trúc 5x5 là thành phần của xương. Kết quả của quá trình làm gầy
là ảnh II.3.5(c). Chúng ta thực hiện việc đánh nhãn các đối tượng còn lại bằng
cách tách các thành phần liên thông. Có tất cả 15 thành phần liên thông trong
Trang 33
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
đó có 3 thành phần bị loại bỏ do kích thước quá nhỏ không có ý nghĩa. Kết
hợp với ảnh gốc ban đầu, ta dễ dàng xác định được vị trí của các vật lạ.
Hình II.3.5. Xác định vật thể lạ trong ảnh
3.4. Làm mảnh
Mảnh của tập A gây bởi phần tử cấu trúc B, được ký hiệu là A
B,
được định nghĩa thông qua biến đổi hit-or-miss:
A
B = A – (A*B)
= A
(A*B)
c
(II.3-4)
Như trong phần trước đã nói, chúng ta chỉ quan tâm đến các mẫu phù
hợp với các phần tử cấu trúc, bởi vậy không một phép toán nền nào được yêu
cầu trong biến đổi hit-or-miss. Một cách biểu diễn hình học hữu ích cho việc
làm mảnh ảnh A là dựa trên dãy các phần tử cấu trúc:
{B} = {B1,B2,..., Bn}
Trong đó Bi chính là phần tử Bi-1 nhưng được xoay đi. Sử dụng khái
niệm này, chúng ta có thể xây dựng quá trình làm mảnh bởi một dãy các phần
tử cấu trúc.
Trang 34
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
A ⊗ {B} = ((...(( A⊗ B1) ⊗ B2)...) ⊗ Bn) (II.3-5)
Hình II.3.6. Làm mảnh ảnh
Quá trình để làm mảnh A bắt đầu bằng việc làm mảnh A bởi B1, sau đó
tiếp tục với B2, quá trình làm mảnh kết thúc cho đến khi không có sự thay đổi
nào xảy ra.
Hình II.3.6(a) thể hiện tập tất cả các phần tử cấu trúc thường được sử
dụng cho quá trình làm mảnh và II.3.6(b) biểu diễn ảnh A sau khi được làm
mảnh bởi dãy các phần tử cấu trúc trong hình II.3.6(a).
3.5. Làm dầy
Quá trình làm dầy một ảnh được thể hiện bởi công thức
(I.3-6)
Trong đó B là phần tử cấu trúc phù hợp. Tương tự như quá trình làm
Trang 35
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
mảnh, làm dầy có thể được định nghĩa dưới dạng một dãy các phép toán.
A ⊙ {B} = ((...(( A⊙ B1) ⊙ B2)...) ⊙ Bn) (I.3-7)
Các phần tử cấu trúc được sử dụng trong phép toán làm dầy có cùng
cấu trúc như các phần tử cấu trúc trong hình II.3.6(a), nhưng có sự chuyển đổi
giá trị tại mỗi điểm ảnh. Nói cách khác là tương phản của nhau. Tuy nhiên
thuật toán làm dầy hiếm khi được sử dụng trong thực tế. Thay vào đó người ta
thường làm mảnh nền của ảnh để thu được hiệu quả làm dầy ảnh.
Hình II.3.7. Làm dầy ảnh
3.6. Tìm xƣơng của ảnh
Như trong hình (II.3.8) ký hiệu xương là S A( ) . Xương của ảnh A có
thể được biểu diễn dưới tập các phép toán làm gầy kết hợp với phép toán
opening:
0
( ) ( )
K
k
i
S A S A
(II.3-8)
với
( ) ( ) ( )kS A A kB A kB B
(II.3-9)
Trong đó B là phần tử cấu trúc và
Trang 36
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
( ) (...( ) ) ...)A kB A B B B
(II.3-10)
với K là bước áp dụng cuối cùng trước khi A bị suy biến thành tập
rỗng. Hay nói cách khác thì:
K= max{k|(A
kB) } (II.3-11)
Hình II.3.8. Tìm xương của ảnh
Công thức cho bởi hai phương trình trên thể hiện rằng S(A) có thể đạt được
bằng cách lấy hợp của các tập xương con Sk(A) . Nó cũng chỉ ra rằng A có thể
được xây dựng lại từ các tập con này bằng cách sử dụng phương trình
0
( ( ) )
K
k
i
A S A kB
(II.3-12)
Trang 37
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
CHƢƠNG III. THUẬT TOÁN DI TRUYỀN
1. Thuật toán di truyền là gì?
Có rất nhiều bài toán tối ưu mà người ta chưa tìm được thuật toán đa
thức để giải quyết chúng ví dụ như bài toán xếp lịch, bài toán sắp xếp đồ vật
hay các bài toán quy hoạch. Đối với các bài toán dạng này, người ta thường
tìm một lời giải cho kết quả chấp nhận được. Với một số bài toán quy hoạch
khó, ta cũng có thể dùng các thuật toán xác suất, những thuật toán này không
đảm bảo cho ra kết quả tối ưu, nhưng bằng cách chọn ngẫu nhiên đủ nhiều
“bằng chứng”, ta có thể giảm tùy thích xác suất sai của kết quả.
Nói một cách trừu tượng, việc giải một bài toán có thể xem như việc
tìm kiếm trong một không gian các 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ể coi công việc này là một 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; còn những
không gian lớn hơn đòi hỏi các phương pháp trí tuệ nhân tạo đặc biệt. Các
thuật toán di truyền nằm trong số các phương pháp đặc biệt đó.
2. Sử dụng thuật toán di truyền trong toán học hình thái
Thuật toán di truyền là một trong những kỹ thuật phổ biến trong các bài
toán hình thái có những ràng buộc yêu cần việc tối ưu hóa một tiêu chuẩn nào
đó. Ngoài bài toán phân rã phần tử cấu trúc sẽ được trình bày chi tiết trong
chương 3, người ta còn dùng thuật toán di truyền trong việc thiết kế các bộ lọc
cho ảnh đa cấp xám và thiết kế các giải thuật đối với các ảnh nhị phân. Hơn
nữa MM còn cung cấp các nền tảng cho việc phát triển giả thuyết di truyền.
Chúng ta sẽ mô tả những ý tưởng đó như sau:
Phân rã phần tử cấu trúc
Một phần tử cấu trúc có thể được phân rã thành các phần tử cấu trúc có
kích thước nhỏ hơn. Điều này rất có ích trong một số ứng dụng như: lưu trữ
Trang 38
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
hay tăng tốc độ tính toán.
Thiết kế các bộ lọc cho ảnh đa cấp xám
Thiết kế bộ lọc cho ảnh đa cấp xám là một bài toán tối ưu khó giải bằng
thuật toán đa thức. Các tác giả Harvay và Marshall trong tài liệu [21,22,23,24]
đã trình bày một cách tiếp cận thuật toán di truyền trong việc thiết kế bộ lọc
ảnh đa cấp xám. Hơn nữa, nghiên cứu đó đã dẫn tới một cách tiếp cận mang
tính cách mạng trong việc thiết kế giải thuật hình thái để tìm một dãy các
phép toán hình thái phù hợp.
Thiết kế giải thuật hình thái cho ảnh nhị phân
Yu [25] đã trình bày một cách tiếp cận đơn giản cho bài toán phân đoạn
ảnh sử dụng thuật toán di truyền. Ảnh được xem như là một tập hợp các đối
tượng được nhúng vào một nền thuần nhất và bị gây nhiễu. Quá trình phân
đoạn ảnh được thực hiện trên các ảnh 16x16 không chồng lấn. Các ảnh con
sau khi được phân đoạn sẽ được kết hợp lại với nhau để đưa ra được phân
đoạn lớn của ảnh. Hàm thích nghi đo độ tương tự của mỗi cá thể ảnh đối với
ảnh gốc ban đầu. Nó cũng bao gồm cả hàm phạt để giảm tần số nhiễu trong
các kết quả được phân đoạn.
3. Hoạt động của thuật toán di truyền
Hoạt động của thuật toán di truyền dựa trên thuyết chọn lọc tự nhiên.
Theo thuyết này thì quá trình tiến hóa tự nhiên là quá trình hoàn hảo nhất.
Quá trình tiến hóa diễn ra trên nhiều thế hệ, thế hệ sau được sinh ra thường tốt
hơn thế hệ trước do được kế thừa những mặt tốt của bố mẹ. Xuất phát từ ý
tưởng đó, thuật toán di truyền đã được ra đời, kế thừa những tư tưởng của lý
thuyết chọn lọc tự nhiên. 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òn được gọi là xâu hoặc nhiễm sắc thể. Mỗi tế bào
trong cơ thể của một loại nào đó chứa một số nhất định nhiễm sắc thể (ví dụ
Trang 39
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
trong cơ thể người có 46 nhiễm sắc thể); tuy nhiên, trong bài này thì ta chỉ nói
về các cá thể chỉ chứa đúng một nhiễm sắc thể. Mỗi nhiễm sắc thể bao gồm
các đơn vị - gen – xếp liên tiếp; mỗi gen điều khiển sự thừa kế của một hoặc
vài tính trạng. Gen của tính trạng nhất định có vị trí xác định trên nhiễm sắc
thể, vị trí đó được gọi là loci (vị trí trên xâu). Một tính trạng bất kỳ (thí dụ
màu mắt) có thể được thể hiện với nhiều mức độ khác nhau; ta nói gen đó có
nhiều trạng thái (gọi là allete).
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 gen của nó, được quy ước
bởi người lập trình); một qúa 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á 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 (không
phụ thuộc vào miền xác định) 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.
Trang 40
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình III.1. Mô phỏng quá trình tiến hóa
Thuật toán dị 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 quan 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 như 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
Trang 41
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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ì nhờ 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, các thế hệ mới luôn được sinh ra để
bổ xung 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 thúc đẩy quá trình 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á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ế có vai trò
quan trọng như nhau trong tiến hóa, dù rằng đột biến xay ra với xác xuất nhỏ
hơn nhiều so với hiện tượng 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 đề mô phỏng bốn 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ác cá thể càng được nâng lên.
3.1. Quá trình lai ghép (phép lai)
Phép lai là quá trình hình thành nhiếm sắc thể mới trên cơ sở các nhiễm
sắc thể của cha mẹ, bằng cách ghép một hay nhiều đoạn gen của hai (hay
nhiều) nhiễm sắc thể cha mẹ với nhau.
Lai ghép một điểm
Trên nhiễm sắc thể của cơ thể cha mẹ sẽ chọn ra một vị trí (điểm lai).
Dữ liệu ở các phía của điểm lai sẽ được hoán chuyển cho nhau giữa hai nhiễm
sắc thể của cha mẹ. Kết quả ta sẽ có nhiễm sắc thể của thế hệ con.
Trang 42
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình III.2. Lai ghép một điểm
Lai ghép hai điểm
Trên cơ thể của cha mẹ được xác định hai điểm lai ghép. Mọi dữ liệu
giữa hai điểm lai ghép đó được hoán đổi cho nhau trong nhiễm sắc thể của hai
cha mẹ, tạo ra hai nhiễm sắc thể của thế hệ con
Hình II.3. Lai ghép hai điểm
Cắt và ghép
Không giống như hai kiểu trên, với phương pháp lai “cắt và ghép” cho
ta kết quả hai cơ thể con có độ dài nhiễm sắc thể khác nhau, lý do của sự khác
biệt này chính là mỗi nhiễm sắc thể của cha mẹ đều có điểm lai khác nhau.
Trang 43
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Ví dụ về phép lai
Ví dụ về một phép lại một điểm với xác suất Pc có thể mô phỏng như
sau:
Hình III.5. Ví dụ về phép lai
- Chọn ngẫu nhiên hai (hay nhiều) các thể bất kì trong quần thể. Giả
sử các nhiễm sắc thể của cha mẹ đều có m gen.
- 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 chuỗi con dài m1 và m2.
Hai chuỗi nhiễm sắc thể con mới sẽ là m11+m22 và m12+m21.
- Đư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.
Trang 44
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3.2. Quá trình đột biến (phép độ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ô phỏng như sau:
Hình III.6 Đột biến tại bít thứ 6
- Chọn ngẫu nhiên một cá thể cha mẹ bất kì trong quần thể.
- Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m (1≤k≤m).
- Thay đổi gen thứ k và trả cá thể này về quần thể để tham gia quá trình
tiến hóa tiếp theo.
3.3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn)
Phép tái sinh là quá trình trong đó các cá thể được sao chép trên cơ sở
độ thích nghi của nó. Còn phép chọn là quá trình loại bỏ các cá thể xấu trong
quần thể để giữ lại trong quần thể các cá thể tốt. Phép chọn lọc có thể mô
phỏng như sau:
- Sắp xếp quần thể theo thứ tự độ tốt giảm dần.
- Loại bỏ các cá thể cuối dãy để chỉ giữ lại m cá thể có độ thích nghi tốt
nhất, ở đây ta giả sử quần thể có kích thước cố định m.
4. Mô hình thuật toán
Trang 45
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Trang 46
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình III.7. Mô tả hoạt động thuật toán
Điều kiện kết thúc thuật toán thường bao gồm:
Số lượng thế hệ được sinh ra.
Một cá thể thỏa mãn các tiêu chuẩn của bài toán.
Giá trị thích nghi cao nhất của cá thể được tìm thấy.
Trang 47
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
CHƢƠNG IV. MỘT CÁCH TIẾP CẬN DI TRUYỀN
TRONG BÀI TOÁN PHÂN RÃ PHẦN TỬ CẤU TRÚC
Trong một số hệ thống song song cổ điển thì việc sử dụng các phần tử
cấu trúc lớn là không hiệu quả, ví dụ như trên hệ thống SIMD, chỉ cho phép
thực hiện các phép toán trên các lân cận nhỏ hơn nhiều so với kích thước của
phần tử cấu trúc; hoặc các đặc trưng khác nhau của những hệ thống mục đích
chung (serial) và hệ thống song song, yêu cầu những kỹ thuật khác nhau để
phát huy những tính chất phần cứng đặc thù của mỗi hệ thống.
Định nghĩa 1. Cho một tập các phần tử cấu trúc cơ bản Fi {i=1,..,M}.
Phần tử cấu trúc B được gọi là lồi trên tập Fi đối với phép toán dãn ảnh nếu
như B có thể biểu diễn được dưới dạng một chuỗi các phép toán làm béo liên
tiếp trên tập các phần tử cấu trúc cơ bản.
1 2 3 ...k k k kmB F F F F
, với kj [1..M], cho j=1,...,m (1)
Ngược lại nếu B không thể biểu diễn dưới dạng chuỗi các phép toán
dãn ảnh trên tập phần tử cấu trúc cho trước thì B được gọi là không lồi. Trong
trường hợp này b có thể được biểu diễn dưới dạng:
1 2 3 ...... ZB C C C C
(2)
đại diện cho một phép toán boolean nào đó ví dụ như phép hợp hay phép
giao.
Trong phần này, chúng tôi đề cập đến vấn đề sử dụng cách tiếp cận
ngẫu nhiên dựa trên thuật toán di truyền: bắt đầu từ một tập quần thể (các cá
thể) của các lời giải có khả năng được xác định thông qua thuật toán vét cạn,
một quá trình lặp biến đổi các cá thể hiện tại và/hoặc tạo ra các cá thể mới
phù hợp với tập các toán tử di truyền được áp dụng một cách ngẫu nhiên. Các
cá thể tối thiểu hóa hàm giá có xu hướng thay thế các cá thể khác và sau một
Trang 48
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
số bước lặp đủ lớn, thì thuật toán có xu hướng hội tụ tới lời giải tối ưu. Trong
thực tế, mục đích chính của công việc này chính là để phát triển công cụ có
thể cho câu trả lời sơ bộ về vấn đề phân rã tối ưu của tập các phần tử cấu trúc
không lồi thành chuỗi các phép toán cơ sở.
Một số tính chất quan trọng của phép toán dãn ảnh
( ) ( ) ( )A B C A B A C
( ) ( ) ( )A B C A B A C
Như vậy, các phần tử cấu trúc không lồi được phân rã sử dụng chuỗi
phép hợp của tập phần tử cấu trúc lồi.
Dưới đây ta sẽ xét một ví dụ chứng tỏ sự ưu việt của việc phân rã các
phần tử cấu trúc lớn thành các phần tử cấu trúc nhỏ hơn.
Trong phép toán dãn ảnh để thực hiện phép dãn ảnh A B ta phải cần
thực hiện card(A)*card(B) phép toán. Giả sử A , B lần lượt là ma trận
(3)
Số phép toán cần thực hiện là 15.12=180 phép toán
Nhưng nếu bằng cách nào đó ta có thể phân rã tập B thành 2 tập con
nhỏ hơn như ví dụ dưới đây:
Và sử dụng luật kết hợp:
1 2 1 2 2( ) ( )R A B A B B A B B R B
(4)
Trang 49
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Trong đó:
Như vậy số phép tính để tính là: 15*3+25*4=145.
Ta xét một ví dụ khác đối với các phần tử cấu trúc không lồi. Như phần
trước đã trình bày, phần tử B không lồi có thể được biểu diễn thành chuỗi các
phần tử cấu trúc cơ bản liên kết với nhau bởi phép toán dãn ảnh và phép toán
logic.
1 2B C C
(5)
(6)
Trong đó, C1, C2 là các tập lồi trên tập các phần tử cấu trúc cơ bản cho
trước IS.
(7)
Do vậy, theo cách này, phép toán dãn ảnh của phần tử cấu trúc B tác
động lên ảnh A
1 2( )R A B A C C
(8)
có thể được thực hiện với 6 phép dãn cơ bản và 1 phép hợp logic. Đây là giải
pháp 1 mức, chỉ bao gồm một mức đơn của hợp các phép dãn, hay còn gọi là
tổng của các phép nhân. Hiển nhiên rằng, giải pháp đa mức có thể dẫn đến
một kết quả tốt hơn.
Trang 50
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Ví dụ việc sử dụng tính chất quy tắc của chuỗi R= A
B có thể được
biểu diễn theo giải pháp hai mức:
(9)
Giải pháp được mô tả ở trên chỉ đòi hỏi 5 phép dãn ảnh và một phép
hợp logic.
Một ứng dụng khác có thể liệt kê ra ở đây đó chính là việc lưu trữ. Ví
dụ như ta có một ảnh thể hiện một nét bút. Thay vì việc ta lưu trữ toàn bộ ảnh
của nét bút đó, ta chỉ cần lưu trữ các thành phần của nó. Một ví dụ khác, giả
sử ta muốn lưu trữ hình một chiếc bút, ta phân chia thành ba phần khác nhau:
đầu bút, thân bút và cuối bút. Ta xét thân bút để thấy rõ tại sao ta có thể lưu
trữ chiếc bút với ít bộ nhớ hơn. Do thân bút là bộ phận đều nhất theo nghĩa
hình khối, thay vì ta lưu trữ cả thân bút, ta chỉ cần lưu giữ chiều dài và chiều
rộng của thân bút. Như vậy tiết kiệm được không gian lưu trữ.
Qua
Các file đính kèm theo tài liệu này:
- 8LV09_CNTT_KHMTPhamDangTu.pdf