Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ HỢP NGHIÊN CỨU GIẢI THUẬT DI TRUYỀN VÀ
ỨNG DỤNG VÀO BÀI TOÁN TÁI TẠO ẢNH
CHÂN DUNG ĐỐI TƢỢNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 NGƢỜI HƢỚNG DẪN KHOA HỌC: TS NGUYỄN NGỌC CƢƠNG

Thái Nguyên -
2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên MỞ ĐẦU
1. Tính cấp thiết của đề tài
Con người là đối tượng nghiên cứu rất phong phú và phức tạp của nhiều
lĩnh vực khoa học khác nhau. Mỗi ngành khoa học, mỗi lĩnh vực khoa học chỉ
nghiên cứu về con người với góc độ, khía cạnh riêng để phục vụ thiết thực cho
ngành khoa học đó. Bài toán tái tạo ảnh chân dung đối tượng từ những thông tin
đặc tả về đối tượng không những phục vụ công tác quản lý con người mà còn

3. Nội dung của luận văn
Đề tài tập trung vào việc tìm hiểu các kiến thức cơ bản về giải thuật di
truyền và bước đầu ứng dụng nó vào giải bài toán tái tạo ảnh chân dung khuôn
mặt đối tượng theo hướng tiếp cận sau: sử dụng giải thuật di truyền để mã hóa
khuôn mặt thành chuỗi gene, dựa trên những mô tả chi tiết của nhân chứng để
tạo ra các khuôn mặt gần giống nhất với nhận định của nhân chứng. Sau khi
quan sát khuôn mặt tái tạo được, nhân chứng có thể thay đổi, bổ sung các chi tiết
khác. Các khuôn mặt tiếp tục được đánh giá bằng một hàm thích nghi. Độ thích
nghi được đo bằng sự vi phạm các ràng buộc như ràng buộc giữa khuôn mặt và
các bộ phận trên khuôn mặt, tỉ lệ co dãn, sinh các bộ phận và lai ghép tùy chọn
là các véc tơ đa chiều. Mỗi ràng buộc được thể hiện thông qua độ lệch và độ dãn
biên của các bộ phận được ghép.
Trên cơ sở đó, nội dung của luận văn gồm ba chương sau phần Mở đầu:
- Chƣơng 1: Khái quát về giải thuật di truyền và bài toán tái tạo ảnh
chân dung (từ trang 4 đến trang 32)
Trong chương này trình bày khái quát về giải thuật di truyền: mã hóa
nghiệm của bài toán, các toán tử di truyền, sơ đồ thuật toán di truyền, nền tảng
toán học của giải thuật di truyền, mô hình hóa giải thuật di truyền bằng xích
Markov. Phần tiếp theo của chương tìm hiểu ứng dụng giải thuật di truyền để
giải bài toán tối ưu hóa, một số cải tiến của giải thuật di truyền và những đóng
góp quan trọng của giải thuật di truyền trong thực tế.
Phần thứ 2 của chương trình bày khái quát về bài toán tái tạo ảnh chân
dung đối tượng.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - Chƣơng 2: Ứng dụng giải thuật di truyền vào bài toán tái tạo ảnh
chân dung đối tƣợng (từ trang 33 đến trang 58)
Chương 2 trình bày một số đặc điểm của bài toán nhận dạng khuôn mặt,

Chƣơng 1
KHÁI QUÁT VỀ GIẢI THUẬT DI TRUYỀN VÀ BÀI TOÁN
TÁI TẠO ẢNH CHÂN DUNG
Chương này tìm hiểu những khái niệm cơ bản về giải thuật di truyền, cơ sở
toán học của giải thuật di truyền, những cải tiến của giải thuật di truyền và các
ứng dụng của nó trong thực tiễn. Phần cuối chương là những nét khái quát về bài
toán tái tạo ảnh chân dung đối tượng.
1.1. Khái quát về giải thuật di truyền
1.1.1. Những khái niệm cơ bản về giải thuật di truyền đơn giản
Giải thuật di truyền (Genetic Algorithm-GA) thuộc lớp các giải thuật tìm
kiếm tiến hóa. Khác với phần lớn các giải thuật khác tìm kiếm theo điểm, giải
thuật di truyền thực hiện tìm kiếm song song trên một tập được gọi là quần thể
các lời giải có thể. Thông qua việc áp dụng các toán tử gene, giải thuật GA tráo
đổi thông tin giữa các cực trị và do đó làm giảm thiểu khả năng kết thúc giải
thuật tại một cực trị địa phương.
Ý tưởng áp dụng các nguyên lý của Darwin để tự động giải bài toán xuất
hiện từ những năm 40 của thế kỷ 20, rất lâu trước khi máy tính ra đời [8]. Từ
những năm đó Turing đã đề xuất “phép tìm kiếm tiến hóa hay tìm kiếm gene”
(Genetical or evolutionary search). Trong những năm 1960, ba khuynh hướng
phát triển của ý tưởng cơ sở này đã diễn ra ở các nơi khác nhau. Tại Mỹ, Fogel,
Owens và Walsh đề xuất hướng nghiên cứu lập trình tiến hóa (Evolutionary
programming) cùng thời điểm với phương pháp của Holland có tên gọi là giải
thuật di truyền (Genetic Algorithm)[9, 10]. Trong khi đó tại Đức, Rechenberg và
Schwefel đặt nền móng cho chiến lược tiến hóa (Evolution Strategies). Trong
khoảng 15 năm sau đó, các hướng nghiên cứu này được phát triển một cách
riêng biệt. Cho đến những năm 1990, các hướng nghiên cứu này được nhìn nhận
lại như những thể hiện khác nhau của một công nghệ chung là tính toán tiến hóa

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên thực nghiệm đưa ra trên quan điểm hướng ứng dụng và xem giải thuật di truyền
như công cụ tối ưu hóa.
Trong mục này, chúng ta sẽ trình bày những khái niệm cơ bản liên quan tới
giải thuật di truyền.
Trong hầu hết các giải thuật di truyền thông thường có hai thành phần phụ
thuộc vào bài toán: mã hóa bài toán và hàm đánh giá.
Bước đầu tiên trong bất kỳ một giải thuật di truyền nào là bước tạo sinh
quần thể xuất phát. Trong giải thuật di truyền chính tắc, mỗi thành viên của quần
thể này là một chuỗi nhị phân độ dài l tương ứng với mã hóa nghiệm của bài
toán. Mỗi chuỗi như vậy được xem như một nhiễm sắc thể. Trong hầu hết các
trường hợp, quần thể này được sinh ra một cách ngẫu nhiên. Sau khi sinh ra
quần thể xuất phát, mỗi cá thể của quần thể được đánh giá và được gán cho một
giá trị thích nghi (fitness value).
Khái niệm đánh giá (evaluation) và thích nghi (fitness) đôi khi được sử
dụng như cặp từ đồng nghĩa. Tuy nhiên, người ta thường phân biệt giữa hàm
đánh giá (evaluation function) và hàm thích nghi (fitness function) được sử dụng
trong các giải thuật di truyền. Trong mục này, hàm đánh giá (hay hàm mục tiêu)
cung cấp độ đo hiệu quả của việc thiết lập giá trị các tham số cụ thể. Hàm thích
nghi biến đổi độ đo hiệu quả này thành việc phân bổ cơ hội tái tạo cho các cá
thể. Việc đánh giá một chuỗi biểu diễn tập các tham số là hoàn toàn độc lập với
việc đánh giá các chuỗi khác. Tuy nhiên, mức độ thích nghi (fitness) của một
chuỗi luôn luôn được xác định trong mối tương quan với các thành viên khác
trong quần thể hiện tại.
Trong giải thuật di truyền, mức độ thích nghi có thể được xác định bằng
ff
i
/

Con-A (1 x 2)
Chuỗi 2

Chuỗi 2

Con-B (2 x 1)
Chuỗi 3

Chuỗi 2

Con-A (2 x 4)
Chuỗi 4

Chuỗi 4

Con-B (2 x 4)
…

…

…
…

…

…


thích nghi của nó trên bánh xe. Quần thể trung gian được tạo nên nhờ việc quay
liên tiếp bánh xe để chọn ra các cá thể theo cơ chế “lấy mẫu ngẫu nhiên có thay
thế” (stochastic sampling with replacement). Cơ chế lựa chọn như vậy được gọi
là lựa chọn tỷ lệ (proportional selection) và xác suất để một phần tử b được lựa
chọn xác định bởi công thức:
0))(/)(()(
1



n
i
i
bfbfbp

Với
b
và các
i
b
là các cá thể nằm trong quần thể hiện tại.
Quá trình lựa chọn cũng có thể thực hiện bằng cơ chế “remainder stochastic
sampling”. Khi đó mỗi chuỗi i với
ff
i
/
lớn hơn 1 sẽ được sao chép vào quần
thể trung gian với số lần bằng phần nguyên của
ff
i

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Khi quá trình lựa chọn, tái tổ hợp và đột biến hoàn thành, quần thể tiếp theo
lại được đưa vào chu trình lặp với các bước như trên. Như vậy một thế hệ mới
đã được sinh ra khi thực hiện giải thuật di truyền.
Tóm lại, có 6 khía cạnh cần được xem xét trước khi áp dụng giải thuật di
truyền để giải một bài toán, cụ thể là:
 Mã hóa lời giải thành cá thể dạng chuỗi
 Hàm xác định giá trị độ phù hợp
 Sơ đồ chọn lọc các cá thể bố mẹ
 Toán tử lai ghép
 Toán tử đột biến
 Chiến lược thay thế hay còn gọi là toán tử tái tạo
Có nhiều lựa chọn khác nhau cho từng vấn đề nêu trên. Phần tiếp theo sẽ
đưa ra cách lựa chọn theo J. H. Holland khi thiết kế phiên bản giải thuật di
truyền đầu tiên. Giải thuật này được gọi là giải thuật di truyền đơn giản (Simple
Genetic Algorithm-SGA).
Giải thuật di truyền như mô tả trên có thể được viết dưới dạng giả mã như
sau:
GIẢI THUẬT DI TRUYỀN
Khởi tạo quần thể ban đầu X={x
1
,…,x
k
}
While (điều kiện kết thúc chưa thỏa mãn) do
Đánh giá mức độ thích nghi của các cá thể trong X (evaluation)
Lựa chọn một số cặp nghiệm (gọi là cha-mẹ) P


khiển của giải thuật SGA.
Trong thực tế GA đã được dùng để giải quyết những vấn đề phức tạp, tuy
nhiên với mục đích làm sáng tỏ cách hoạt động của các toán tử trong giải thuật
di truyền chúng ta sẽ xem xét một ví dụ đơn giản đó là: “Tìm đáp số cho phương
trình
64
2
X
(*).
Bước 1: Qui định số lượng các đáp số và ấn định ký hiệu cho từng đáp số.
HT thập phân
1
2
3
4
5
6
7
8
HT nhị phân
0001
0010
0011
0100
0101
0110
0111
1000
Bước 2: Chỉ định số đáp số và ký hiệu các đáp số cho bài tóan
Sau đây là 4 số có thể là đáp số cho bài toán (*)


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (1)
(2)
(3)
thích nghi
1
00100
4
952
2
10101
21
623
3
01010
10
964
4
11000
24
488
Bảng 1.3. Hệ số thích nghi tương ứng với từng đáp số
Bước 4: Biến hóa các đáp số để tìm các đáp số có hệ số thích nghi tối ưu.
Trong bốn số 4, 21, 10 và 24 thì 2 số 10 và 4 có hệ số thích nghi cao hơn do đó
chúng sẽ được chọn để tạo sinh và biến hóa, đồng thời số 21 và 24 có hệ số thích
nghi thấp nhất sẽ bị loại.
Tiến hành lai ghép hai số 4 và 10 tại điểm giữa hàng thứ hai và thứ ba:

quay lại Bước 4 và Bước 5 nữa, chúng ta sẽ báo cáo kết quả là 8.
Bước 7: Kết quả với X = 8, chúng ta sẽ có X
2
= 8
2
= 64
1.1.2. Nền tảng toán học của giải thuật di truyền

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Qua ví dụ trên chúng ta nhận thấy sự phối hợp của hai mẫu bít có hệ số
thích nghi lớn hơn là
00100
và
01010
sản sinh ra những chuỗi mới có giá trị tốt
hơn. Điều này đã được Holland (1968, 1975) nhận xét và đưa ra khái niệm giản
đồ (schema). Giản đồ là mẫu tương tự mô tả một tập con các chuỗi với sự giống
nhau tại một số vị trí trong chuỗi.
Không mất tính tổng quát chúng ta xét các chuỗi trên tập ký tự
}1,0{V
.
Để thuận tiện chúng ta ký hiệu chuỗi là những ký tự hoa còn các ký tự của chuỗi
chúng ta dùng các ký tự thường. Ví dụ chuỗi 7 bít A = 0111000 có thể được biểu
diễn một cách tượng trưng như sau:
7654321
aaaaaaaA 
.
Trong giải thuật SGA, mỗi chuỗi cá thể được biểu diễn một cách hình thức

H
là một chuỗi
L
gien lấy từ tập ký tự

V
. Các giá trị
1
hoặc
0
có trong giản đồ
H
gọi là các vị trí cố định của giản đồ. Một thể hiện của giản
đồ
H
là một chuỗi
L
gien lấy từ tập ký tự
V
có các gien trùng với các gien của
giản đồ
H
tại các vị trí cố định. Dễ nhận thấy có
L
3
giản đồ có độ dài
L
. Một
cách tổng quát với tập ký tự gồm
C

4*)*1*011( o
.
Độ dài của giản đồ
H
, ký hiệu là (
H
), là khoảng cách từ vị trí xác định
đầu tiên tới vị trí xác định cuối cùng của giản đồ. Ví dụ giản đồ
**1*011H
có
độ dài
4
, giản đồ
******0
có độ dài là
0
và giản đồ
0*0**1*
có độ dài bằng
5
.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Gọi
),( tHm
là số thể hiện của giản đồ
H
có trong quần thể tại thế hệ









mc
pHo
L
H
p
f
Hf
tHmtHm ).(
1
)(
.1
)(
).,()1,(

(1)
Thật vậy, từ biểu thức (1), dễ thấy các giản đồ bậc nhỏ với độ dài ngắn và
có giá trị độ phù hợp trung bình lớn hơn giá trị độ phù hợp trung bình của toàn
quần thể sẽ có số thể hiện tăng và có vai trò quan trọng trong giải thuật di
truyền.
Hiệu ứng của toán tử tái tạo đối với giản đồ có trong quần thể rất dễ xác
định. Giả sử tại một thời điểm
t

fHfntHmtHm /)(.).,()1,(
, ở đây
)(Hf
là giá trị sức
khỏe trung bình của các chuỗi chứa giản đồ
H
tại thời điểm
t
. Vì giá trị sức
khỏe trung bình của toàn thể quần thể là
nff
j
/


nên chúng ta có thể viết
phương trình phát triển giản đồ như sau:
f
Hf
tHmtHm
)(
).,()1,( 
(2)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bằng lời chúng ta có thể phát biểu là số mẫu của các giản đồ phát triển theo
tỉ số của giá trị sức khỏe trung bình của giản đồ và giá trị sức khỏe của toàn bộ
quần thể. Như vậy đối với những giản đồ có giá trị sức khỏe trung bình lớn hơn


Như vậy một cách định lượng toán tử lai tạo làm tăng số mẫu của giản đồ
có sức khỏe lớn hơn giá trị sức khỏe trung bình của toàn quần thể theo hàm số
mũ và giảm số mẫu của các giản đồ có sức khỏe bé hơn giá trị sức khỏe trung
bình của toàn quần thể cũng theo hàm số mũ một cách song song đối với tất cả
các giản đồ có trong quần thể.
Để xem xét giản đồ nào bị ảnh hưởng bởi toán tử tạp lai, giản đồ nào không
bị ảnh hưởng, chúng ta nghiên cứu một chuỗi cụ thể với độ dài
7L
và hai giản
đồ tồn tại trong chuỗi đó như sau:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên **10***
0****1*
0111000
2
1



H
H
A

Rõ ràng cả hai giản đồ đều tồn tại trong chuỗi
A
và chúng đều có bậc là 2,

1
H
sẽ bị phá hủy với xác suất
6/5)1/()(
1
 LHp
d

và
chúng chỉ tồn tại với xác suất là
6/1
s
p
. Một cách tổng quát chúng ta có thể
tính xác suất tồn tại qua toán tử tạp lai đối với bất kì giản đồ nào
)1/()(1  LHp
s

. Nếu tính thêm cả xác suất ghép đôi (xác suất tạp lai)
c
p
lúc
này chúng ta có xác suất tồn tại qua toán tử tạp lai của bất kỳ giản đồ nào là
1
)(
.1


l
H


(4)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Toán tử cuối cùng chúng ta cần nghiên cứu là toán tử đột biến. Sử dụng
định nghĩa về toán tử đột biến là sự thay thế ngẫu nhiên và độc lập với nhau của
các gien trong chuỗi với xác suất là
m
p
, chúng ta có ngay là xác suất tồn tại của
một gien trong chuỗi là
m
p1
. Để cho một giản đồ tồn tại thì tất cả các vị trí xác
định trong giản đồ phải tồn tại. Số vị trí xác định trong giản đồ
H
chính là bậc
của giản đồ
)(Ho
. Nhân xác suất tồn tại của từng gien
m
p1
trong giản đồ lên
)(Ho
lần chúng ta có được xác suất tồn tại của giản đồ
H
qua toán tử đột biến là
)(

l
H
p
f
Hf
tHmtHm ).(
1
)(
.1
)(
).,()1,(


Định lý 1.1. thể hiện rằng những giản đồ bậc thấp, có độ dài ngắn và có giá
trị sức khỏe trung bình lớn hơn giá trị sức khỏe trung bình của toàn quần thể sẽ
có số mẫu tăng theo hàm số mũ trong thế hệ tiếp theo. Kết luận quan trọng này
được biết tới như định lý giản đồ hay định nghĩa nền tảng của giải thuật di
truyền (Fundamental Theorem of Genetic Algorithms).
Những giản đồ bậc thấp, độ dài ngắn và có sức khỏe tốt được gọi là các
khối xây dựng. Thông qua các toán tử của giải thuật di truyền những khối này
được thử, kết hợp với nhau rồi thử lại để tạo ra những chuỗi có sức khỏe tốt hơn.
Nói cách khác những khối này kết hợp với nhau để tạo ra những chuỗi tốt hơn.
Giả định này đã chỉ ra rằng khi làm việc với những khối xây dựng chúng ta
sẽ giảm được độ phức tạp của bài toán. Thay cho việc phải xây dựng một chuỗi
có sức khỏe tốt bằng việc thử tất cả các tổ hợp của các khối xây dựng, chúng ta
chỉ việc xây dựng các chuỗi tốt dần lên từ các khối của các chuỗi đã có trong các
lần thử trước.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


với các trạng thái ở thời điểm trước thời điểm
s
. Điều này có nghĩa là sự tiến
triển của hệ trong tương lai chỉ phụ thuộc vào hiện tại và độc lập với quá khứ.
Đó chính là tính Markov.
Về phương diện toán học tính Markov được định nghĩa như sau.
Định nghĩa 1.1. Gọi
P
là một ma trận vuông
)( kk 
với các phần tử
}, ,1,:{
,
kjiP
ji

. Một quá trình ngẫu nhiên
, ),(
10
XX
có không gian trạng thái
hữu hạn
}, ,{
1 k
ssS 
được gọi là xích Markov với ma trận chuyển dịch
P
, nếu
}, ,1{,, kjin 
và

P
. Một véc tơ hàng
), ,(
1 k


được gọi là phân phối dừng của xích Markov, nếu nó thỏa mãn
(i)
0
i

đối với
ki , ,1
và
1
1



k
i
i

.
(ii)

P.
, nghĩa là
j
k

khi
kích thước quần thể
n
tiến tới vô hạn, ta có



n
lim
*

Theo định nghĩa 1.3, một giải thuật GA được gọi là hội tụ khi xích Markov
biểu diễn giải thuật có phân phối dừng và phân phối này tập trung toàn bộ xác
suất vào một trạng thái. Giải thuật SGA đã được các tác giả Nix và Vose mô
hình hóa và chứng minh là không đảm bảo sự hội tụ.
Gọi
L
là độ dài chuỗi. Khi đó
L
r 2
là tổng số các chuỗi nhị phân có thể.
Gọi
n
là số cá thể có trong quần thể, khi đó số các quần thể có thể (số các trạng
thái của xích Markov) là:
!)!1(
)!1(
1
1
nr

p
, xác suất lai ghép
c
p
và cách thức sử dụng các toán tử đột biến và lai ghép.
Với các toán tử
F
và
M
đã được định nghĩa, xác suất chuyển dịch được tính
toán như sau:
jy
z
r
y
jy
y
i
i
ji
z
F
F
M
nP
,
1
0
,
,

p
là khác 0, xác suất để xích Markov đạt tới tất cả
các trạng thái là khác 0. Do đó, các phần tử của ma trận chuyển dịch P là dương.
Điều này làm cho xích Markov có tính ergodic. Theo định lý về xích Markov

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên [13, 14], các xích Markov ergodic có phân phối dừng. S. Cofey tiếp theo đã
chứng minh phân phối dừng này có các phần tử đều lớn hơn 0. Như vậy, do số
lượng các trạng thái lớn, phân phối dừng không tập trung toàn bộ xác suất của
nó vào một trạng thái nào. Nói cách khác, giải thuật GA không hội tụ vì là giải
thuật có phân phối dừng nhưng phân phối này không tập trung tất cả xác suất
vào một trạng thái.
Để tạo ra một giải thuật GA có khả năng hội tụ và nâng cao hiệu quả tìm
kiếm của giải thuật GA, W. M. Spears sử dụng sơ đồ mã hóa gray thay thế sơ đồ
mã hóa nhị phân nhằm giảm thiểu hiệu ứng phá hủy các giản đồ của toán tử lai
ghép. Các tác giả [13, 14] sử dụng sơ đồ mã hóa số thực trong giải thuật di
truyền. Trong sơ đồ này mỗi gien của cá thể là một số thực nằm trong một
khoảng xác định. Với sơ đồ mã hóa số thực, có khá nhiều các toán tử lai ghép số
học và các toán tử đột biến số thực đã được đề xuất.
V. Estivill-Castro chỉ ra vai trò đảm bảo sự hội tụ của toán tử chọn lọc
trong giải thuật di truyền. J. E. Baker phân tích hiệu ứng của toán tử chọn lọc
trong giải thuật GA. T. Back phân tích sức ép chọn lọc của các giải thuật tiến
hóa trong đó có giải thuật di truyền. Sức ép chọn lọc là độ chênh lệch của giá trị
độ phù hợp trung bình của quần thể bố mẹ và quần thể hiện tại. T. Blickle và L.
Thiele phân tích sự mất đa dạng của toán tử chọn lọc sử dụng các sơ đồ chọn lọc
khác nhau. Các tác giả giả định là các cá thể trong quần thể có phân bố liên tục.
Tuy nhiên, hiệu ứng của phân bố liên tục và rời rạc là khác nhau đối với các
quần thể hữu hạn.

đến mọi lĩnh vực của tự nhiên và xã hội.
Trong mục này, tác giả sẽ đề cập chi tiết việc áp dụng giải thuật di truyền
cho bài toán tối ưu một hàm
f
có
n
biến,
), ,,(
21 n
xxxf
. Biết rằng mỗi biến
i
x
có
thể lấy các giá trị từ miền
];[
iii
baD 
là tập con của tập các số thực
R
và yêu cầu
độ chính xác là k chữ số thập phân đối với các giá trị biến.
1.1.3.1. Biểu diễn các biến nhờ các véc tơ nhị phân
Tham biến
x
thuộc
];[
maxmin
UU
được biểu diễn bởi chuỗi nhị phân có chiều

sẽ được xác định theo công thức:
gstringdecimalUx *)(
2min

(6)
Trong đó
)(
2
stringdecimal
biểu diễn giá trị thập phân của chuỗi nhị phân
2
string
,
g
được xác định bởi công thức (5).
Để mã hóa tập các biến, ta ghép nối mã các biến riêng lẻ lại với nhau. Mỗi
mã tương ứng với một chiều dài các bit riêng và xác định một giá trị tương ứng
của nó nằm trong miền
];[
maxmin
UU

1.1.3.2. Ánh xạ giá trị hàm mục tiêu sang giá trị thích nghi
Giá trị thích nghi
)(if
được xác định đối với mỗi cá thể trong quần thể. Giá
trị này càng lớn thì cá thể được coi là hợp lý. Hàm thích nghi có thể là hàm
không liên tục, hàm dương hay phi tuyến. Vì hàm thích nghi phải nhận giá trị
không âm, do đó cần phải xây dựng ánh xạ hàm mục tiêu đang xét trong bài toán


nhất trong quần thể hiện tại hoặc lớn nhất sau k vòng lặp.
Khi hàm mục tiêu gốc tăng hoặc đang xét bài toán cực đại hóa một hàm
hữu dụng
)(xu
, chúng ta có thể chuyển sang hàm thích nghi như sau:





khác
CxukhiCxu
xf
0
0)()(
)(
minmin
(8)
Ở đây
min
C
là tham số đầu vào, có thể là trị tuyệt đối của
u
bé nhất trong
quần thể hiện tại hoặc trong
k
vòng lặp cuối cùng hoặc là một hàm của biến
quần thể.
1.1.3.3. Điều chỉnh độ thích nghi
Một vấn đề quan trọng là điều chỉnh số con cháu. Điều này đặc biệt quan


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ở đây
mult
C
là số các bản sao cần thiết đối với một thành viên tốt nhất trong
quần thể. Đối với các quần thể nhỏ (n = 50 đến 100),
mult
C
thường được chọn từ
1.2 đến 2 và tỏ ra khá hiệu quả. Biểu thức (10) bảo đảm rằng mỗi thành viên với
độ thích nghi trung bình sẽ cho một con hay một cháu đối với lần phát sinh tiếp
theo. Biểu thức (11) kiểm soát số con cháu được nạp vào làm thành viên với độ
thích nghi gốc cực đại.
Với chiến thuật tỷ lệ hóa đơn giản như trên, chúng ta ngăn ngừa được sự
chi phối của các cá thể siêu khỏe ở giai đoạn đầu và sau đó tạo ra được cạnh
tranh lành mạnh giữa các cá thể gần bằng nhau ở giai đoạn cuối của giải thuật di
truyền.
1.1.3.4. Các bƣớc của giải thuật di truyền giải bài toán cực tiểu hàm
f

Với cách biểu diễn biến nêu trên, để tìm lời giải tối ưu của bài toán cực tiểu
hàm với n biến có thể thực hiện thuật giải như sau:
máy tính và độ chính
xác yêu cầu)

Trích đoạn Các bƣớc của giải thuật di truyền giải bài toán cực tiểu hàm f Các toán tử cao cấp Các công cụ và mô hình để thực hiện giải pháp trên Các chức năng chính của hệ thống Kết quả thử nghiệm chƣơng trình tái tạo ảnh khuôn mặt chân dung đối tƣợng sử dụng giải thuật di truyền

---