Mục lục
Mở đầu
1

2

GIẢI THUẬT DI TRUYỀN (GENETIC ALGORITHM)
1.1 Lịch sử của giải thuật di truyền . . . . . . . . . . . . . . . .
1.2 Tóm tắt giải thuật di truyền . . . . . . . . . . . . . . . . . .
1.3 Cách biểu diễn bài toán trong giải thuật di truyền . . . . . .
1.3.1 Biểu diễn Gen bằng chuỗi nhị phân. . . . . . . . . .
1.3.2 Biểu diễn gen bằng chuỗi số thực . . . . . . . . . . .
1.3.3 Biểu diễn gen bằng cấu trúc cây . . . . . . . . . . .
1.4 Các phương pháp chọn (Selection) . . . . . . . . . . . . . . .
1.4.1 Chọn lọc Roulette (Roulette Wheel Selection) . . . .
1.4.2 Chọn lọc cạnh tranh (Tournament Selection) . . . . .
1.5 Các phương pháp lai tạo (crossover) và đột biến (mutation)
1.5.1 Lai ghép (Crossover) . . . . . . . . . . . . . . . . . .
1.5.2 Đột biến (Mutation) . . . . . . . . . . . . . . . . . .
1.6 Các tham số cần sử dụng trong giải thuật di truyền . . . . .
1.7 Điều kiện dừng giải thuật di truyền . . . . . . . . . . . . . .

2 ÁP
SỐ
2.1
2.2
2.3

.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

3
3
3

5
6
7
7
7
8
8
9
9
9
10
10

DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN TỐI ƯU
Minh họa chi tiết thuật toán . . . . . . . . . . . . . . . . . . . . . . . .
Mã nguồn Java giải bài toán . . . . . . . . . . . . . . . . . . . . . . . .
Màn hình kết quả chạy chương trình . . . . . . . . . . . . . . . . . . .

11
11
19
25

Kết luận

26

Tài liệu tham khảo

26


1


Lời mở đầu
Với khả năng hiện nay, máy tính đã giúp con người giải quyết được rất nhiều bài
toán khó mà trước kia thường bó tay. Mặc dù vậy vẫn còn một số lớn các bài toán thú
vị nhưng chưa có thuật giải hợp lý để giải chúng. “Giải thuật di truyền” được phát triển
dựa trên sự mô phỏng quá trình tiến hóa của sinh học, được bắt đầu bằng Nils Aall
Baricelli mô phỏng quá trình tiến hóa trong trò chơi năm 1954. Sau đó đến Alex Fraser
xuất bản cuốn sách Artificial Selection (chọn lọc nhân tạo). Nhưng John Holland mới
là người đầu tiên thực sự đặt tên cho giải thuật là “giải thuật di truyền” bằng việc
xuất bản cuốn sách năm 1975. Từ đây giải thuật đã có tên là “giải thuật di truyền”,
cùng với đó là sự phát triển mạnh mẽ hoàn thiện lý thuyết “giải thuật di truyền” và
ứng dụng của giải thuật trong những bài toán thực tế. Giải thuật di truyền đã được
ứng dụng thành công trong nhiều lĩnh vực như kế hoạch hóa và tìm đường, quan sát
máy, thiết kế chế tạo máy, các hệ thống điều khiển ống dẫn dầu, học máy (machine
learning). . . cùng những nghiên cứu sâu hơn về sử dụng giải thuật di truyền trong các
bài toán mang tính tổng chất quát hơn như phân tích biệt số tuyến tính, mô phỏng dự
báo. . .
Nội dung đồ án gồm 2 phần chính
• Phần 1: Thuật giải di truyền. Phần này trình bày chi tiết về thuật giải di truyền
cũng như nguyên lý và cơ chế hoạt động của nó.
• Phần 2: Áp dụng vào bài toán tối ưu. Phần này trình bày cách áp dụng thuật
giải di truyền vào giải bài toán tối ưu. Theo đó là ví dụ minh họa chi tiết cũng
như mã nguồn của chương trình minh họa.
Do thời gian gấp rút, chưa có nhiều kinh nghiệm nên bài báo cáo khộng thể tránh
những sai sót. Mong thầy cô, bạn đọc góp ý để bài báo cáo được trọn vẹn hơn. Và cuối
cùng em xin chân thành cảm ơn các thầy cô giáo trong viện đã chỉ dạy em trong thời
gian qua, đặc biệt thầy Nguyễn Quang Thuận đã trực tiếp chỉ dẫn tận tình giúp đỡ

em hoàn thành báo cáo này.
Hà Nội, Ngày 01 tháng 12 năm 2015
Phạm Ngọc Chuyển

2


Chương 1

GIẢI THUẬT DI TRUYỀN (GENETIC
ALGORITHM)

1.1

Lịch sử của giải thuật di truyền

Trước tiên ý niệm về thuật giải di truyền đã được một số nhà sinh vật học đưa ra từ
những năm 50-60, thế kỷ XX. Alex Fraser là người tiên phong nêu lên sự tương đồng
giữa sự tiến hóa của sinh vật và chương trình tin học giả tưởng về genetic algorithm.
Tuy nhiên, John Henry Holland mới là người triển khai ý tưởng và phương thức giải
quyết vấn đề dựa theo sự tiến hóa của con người. Từ những bài giảng, bài báo của
mình, ông đã đúc kết các ý tưởng vào trong cuốn sách đầu tay Adaptation in Natural
and Artifical systems (mô phỏng theo tự nhiên và hệ thống nhân tạo ), xuất bản năm
1975. Dựa trên lý thuyết cơ bản về GA của Holland, Keneth De Jong đã triển khai,
chứng minh và những thành quả do ông thực hiện đã góp phần quan trọng trong việc
tạo ra nền tảng toán học cho lý thuyết thuật giải di truyền. Sau này là John koza đã
tiếp nối, phát triển giải thuật di truyền. Lần đầu tiên Holland nghiên cứu các thuật
giải này, chúng hoàn toàn không có tên. Do nguồn gốc của phương pháp này là từ các
gen di truyền, Holland đã đặt tên cho nó là “thuật giải di truyền“.


1.2

Tóm tắt giải thuật di truyền

Thuật giải di truyền (GA) là kỹ thuật chung giúp giải quyết vấn đề 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 trên thuyết
tiến hóa muôn loài của Darwin) trong điều kiện qui định sẵn của môi trường. GA là
một thuật giải, nghĩa là 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.
Theo đề xuất ban đầu của giáo sư John Holland, một bài toán đặt ra sẽ được mã
hóa thành các chuỗi bit với chiều dài cố định. Nói một cách chính xác là các thông số
của bài toán sẽ được chuyển đổi và biểu diễn lại dưới dạng các chuỗi nhị phân. Các
thông số này có thể là các biến của một hàm hoặc hệ số của một biểu thức toán học.
Người ta gọi các chuỗi bit này là mã gen ứng với mỗi cá thể, các gen đều có cùng chiều
dài. Nói ngắn gọn, một lời giải sẽ được biểu diễn bằng một chuỗi bit, cũng giống như
mỗi cá thể đều được quy định bằng gen của cá thể đó vậy. Như vậy, đối với thuật giải
di truyền, một cá thể chỉ có một gen duy nhất và một gen cũng chỉ phục vụ cho một
3


cá thể duy nhất.
Ban đầu, ta sẽ phát sinh một số lượng lớn, giới hạn các cá thể có gen ngẫu nhiên.
Nghĩa là phát sinh một tập hợp các chuỗi bit ngẫu nhiên. Tập các cá thể này được gọi
là quần thể ban đầu (initial population). Sau đó, dựa trên một hàm nào đó, ta sẽ xác
định được một giá trị gọi là độ thích nghi - Fitness. Giá trị này, có thể hiểu là độ "tốt"
của lời giải. Vì phát sinh ngẫu nhiên nên độ "tốt" của lời giải hay tính thích nghi của
các cá thể trong quần thể ban đầu là không xác định.
Để cải thiện tính thích nghi của quần thể, người ta tìm cách tạo ra quần thể mới.
Có hai thao tác thực hiện trên thế hệ hiện tại để tạo ra một thế hệ khác với độ thích
nghi tốt hơn. Thao tác đầu tiên là sao chép nguyên mẫu một nhóm các cá thể tốt từ

thế hệ trước rồi đưa sang thế hệ sau (selection). Thao tác này đảm bảo độ thích nghi
của thế hệ sau luôn được giữ ở một mức độ hợp lý. Các cá thể được chọn thông thường
là các cá thể có độ thích nghi cao nhất. Thao tác thứ hai là tạo các cá thể mới bằng
cách thực hiện các thao tác sinh sản trên một số cá thể được chọn từ thế hệ trước,
thông thường cũng là những cá thể có độ thích nghi cao. Có hai loại thao tác sinh sản:
một là lai tạo (crossover), hai là đột biến (mutation). Trong thao tác lai tạo, từ gen
của hai cá thể được chọn trong thế hệ trước sẽ được phối hợp với nhau (theo một số
quy tắc nào đó) để tạo thành hai gen mới.
Thao tác chọn lọc và lai tạo giúp tạo ra thế hệ sau. Tuy nhiên, nhiều khi do thế hệ
khởi tạo ban đầu có đặc tính chưa phong phú và chưa phù hợp nên các cá thể không
rải đều được hết không gian của bài toán. Từ đó, khó có thể tìm ra lời giải tối ưu cho
bài toán. Thao tác đột biến sẽ giúp giải quyết được vấn đề này. Đó là sự biến đổi ngẫu
nhiên một hoặc nhiều thành phần gen của một cá thể ở thế hệ trước tạo ra một cá thể
hoàn toàn mới ở thế thệ sau. Nhưng thao tác này chỉ được phép xảy ra với tần suất rất
thấp (thường dưới 0.01), vì thao tác này có thể gây xáo trộn và làm mất đi những cá
thể đã chọn lọc và lai tạo có tính thích nghi cao, dẫn đến thuật toán không còn hiệu quả.
Thế hệ mới được tạo ra lại được xử lý như thế hệ trước (xác định độ thích nghi và
tạo thế hệ mới) cho đến khi có một cá thể đạt được giải pháp mong muốn hoặc đạt
đến thời gian giới hạn.
Tóm lại: Một thuật giải di truyền (hay một chương trình tiến hóa bất kỳ) giải một
bài toán cụ thể phải gồm năm thành phần sau đây:
– Một cấu trúc dữ liệu I biểu diễn không gian lời giải của bài toán,
– Phương pháp khởi tạo quần thể ban đầu P(0),
– Hàm định nghĩa độ thích nghi eval(.) đóng vai trò môi trường,
– Các phép toán di truyền,
– Các tham số khác (kích thước quần thể, xác suất lai tạo, xác suất đột
biến. . . ).
4



Lược đồ GA:

1.3

Cách biểu diễn bài toán trong giải thuật di truyền

Để áp dụng giải một bài toán bằng giải thuật di truyền, thao tác quan trọng nhất –
là phải biết chọn cấu trúc dữ liệu phù hợp. Để giải bài toán trong giải thuật di truyền,
ta thường chọn sử dụng một trong 3 loại cấu trúc dữ liệu sau: Chuỗi nhị phân, chuỗi số
thực và cấu trúc cây. Trong đó chuỗi nhị phân và chuỗi số thực thường được sử dụng
nhiều hơn.

5


1.3.1

Biểu diễn Gen bằng chuỗi nhị phân.

Giả sử ta muốn biểu diễn số thực x nằm trong khoảng [min, max] bằng một chuỗi
nhị phân A dài L bit. Lúc đó, ta sẽ chia miền [min, max] thành 2L − 1 vùng, kích
thước một vùng là :
max −min
g=
2L − 1
Người ta gọi g là độ chính xác của số thực được biểu diễn bằng cách này (vì g quy
định giá trị thập phân nhỏ nhất của số thực mà chuỗi nhị phân dài L bit có thể biểu
diễn được). Giá trị của số thực x được biểu diễn qua chuỗi nhị phân sẽ được tính như
sau:
x = min + Decimal(A) ∗ g,

trong đó Decimal(A) là hàm để tính giá trị thập phân nguyên dương của chuỗi nhị
phân A. Hàm này được tính theo công thức sau:
Decimal(A) = aL−1 .2L−1 + . . . + a2 .22 + a1 .21 + a0 .20 ,
với ai là bit thứ i trong chuỗi nhị phân tính từ phải sang trái (bit phải nhất là bit 0).
Ví dụ: Tìm giá trị lớn nhất của hàm f (x) = x.sin(10πx) + 1 với x ∈ [−1, 2].
Sử dụng vectơ bit làm nhiễm sắc thể để biểu diễn giá trị thực của biến x. Chiều dài
vectơ phụ thuộc vào độ chính xác cần có, trong ví dụ này, ta tính chính xác đến 6 số
lẻ.
Miền giá trị của x có chiều dài 2 - (-1) = 3; với yêu cầu về độ chính xác 6 số lẻ
như thế phải chia khoảng [−1, 2] thành ít nhất 3.106 khoảng có kích thước bằng nhau.
Điều này có nghĩa là cần có 22 bit cho vevtơ nhị phân (nhiễm sắc thể) vì
2097152 = 221 < 3000000 < 222 = 4194304.
Ánh xạ chuỗi nhị phân (b21 b20 . . . b0 ) từ cơ số 2 sang cơ số 10:
21

bi 2i )2 = x

(b21 b20 . . . b0 )2 = (
i=0

Tìm số thực x tương ứng
x = −1 + x .

222

3
−1

với -1 là lân cận dưới của miền giá trị và 3 là chiều dài của miền.
Ví dụ, nhiễm sắc thể (1000101110110101000111) biểu diễn số 0.637197 vì x’ =

(1000101110110101000111)2 = 228896710 và
x = −1.0 + 2288967.

3
= 0.637197
4194303

6


1.3.2

Biểu diễn gen bằng chuỗi số thực

Đối với những vấn đề bài toán có nhiều tham số, việc biểu diễn gen bằng chuỗi số
nhị phân đôi lúc sẽ làm cho kiểu gen của cá thể trở nên quá phức tạp, dẫn đến việc thi
hành các thao tác trên gen trở nên kém hiệu quả. Khi đó, người ta sẽ chọn biểu diễn
kiểu gen dưới dạng một chuỗi số thực. Tuy nhiên, chọn biểu diễn kiểu gen bằng chuỗi
số thực cần lưu ý quy tắc đảm bảo tiết kiệm không gian đối với từng thành phần gen.
Quy tắc này lưu ý chúng ta phải tiết kiệm về mặt không gian bộ nhớ đối với các
từng thành phần gen. Giả sử nghiệm của bài toán được cấu thành từ 3 thành phần,
thành phần X thực có giá trị trong khoảng [1.0, 2.0], thành phần Y nguyên trong
khoảng [0, 15] và thành phần Z trong khoảng [5, 8], thì chúng ta không nên chọn biểu
diễn kiểu gen bằng một chuỗi 3 thành phần số thực. Vì như chúng ta đã biết, ít nhất
mỗi số thực được phải được biểu diễn bằng 4 byte, chỉ với 3 số thực, ta đã tốn hết 12
byte. Như vậy với trường hợp cụ thể này, ta nên chọn biểu diễn bằng chuỗi nhị phân,
trong đó dùng khoảng 10 bit cho thành phần X (độ chính xác khoảng 0.001), 4 bit
cho thành phần Y và 2 bit cho thành phần Z, tổng cộng chỉ chiếm có 16 bit = 2 byte.
Chúng ta đã tiết kiệm được rất nhiều bộ nhớ!


1.3.3

Biểu diễn gen bằng cấu trúc cây

Cấu trúc cây thường được dùng trong trường hợp bản thân cấu trúc dữ liệu của bài
toán cũng có dạng cây. Đây là một trường hợp phức tạp nên hiếm khi được sử dụng.
Trong phạm vi đồ án này, em sẽ không khảo sát nhiều về kiểu dữ liệu này. Các thao
tác trên cây của thuật giải di truyền thường phụ thuộc nhiều vào bài toán đang xét.
Do đó, ở đây ta sẽ không trình bày một cách tổng quát. Một loại cây thường được sử
dụng trong thuật giải di truyền là dạng cây hai nhánh (ở đây ta dùng chữ hai nhánh
để phân biệt với loại cây nhị phân – thường dùng trong sắp xếp và tìm kiếm). Để hiểu
được cấu trúc cây, bạn cần có một ít kiến thức về con trỏ. Bạn có thể tìm thấy những
thông tin này trong các tài liệu về cấu trúc dữ liệu.

1.4

Các phương pháp chọn (Selection)

Chọn lọc cá thể thông qua kết quả, hay mục đích của vấn đề dựa trên mức độ thích
nghi của cá thể. Vì vậy, cần đánh giá độ thích nghi của cá thể để tìm ra cá thể tốt nhất.
Thông thường, đặt mỗi vấn đề nhỏ tương ứng với một giá trị điểm thích nghi , kết quả
đánh giá gồm tổng các số điểm đó. Cá thể tốt nhất sẽ có điểm thấp nhất hoặc lớn nhất.
Theo thuyết Darwin, cá thể tốt nhất sẽ tồn tại và tạo ra các cá thể con mới. Có
nhiều phương pháp để chọn các nhiễm sắc thể tốt nhất. Sau đây là vài phương pháp
trong số đó.

7


1.4.1


Chọn lọc Roulette (Roulette Wheel Selection)

Các cá thể được chọn theo độ thích nghi của chúng. Nhiễm sắc thể tốt hơn có cơ
hội cao hơn để tham dự vào thế hệ tiếp theo.
Thuật giải chọn lọc roulette(Davis, [1991,8]) như sau:
− Tính độ thích nghi eval(vi ) của mỗi nhiễm sắc thể vi (i = 1..popsize);
− Tính tổng độ thích nghi của mọi thành viên trong quần thể:
popsize

F =

eval(vi );
i=1

− Tính xác suất chọn pi cho mỗi nhiễm sắc thể vi :
pi =

eval(vi )
;
F

− Tìm vị trí xác suất qi của mỗi nhiễm sắc thể vi :
i

qi =

pj .
j=1


Tiến trình chọn lọc được thực hiện bằng cách quay bánh xe ru-lét pop-size lần; mỗi
lần chọn một nhiễm sắc thể từ quần thể hiện hành vào quần thể mới theo cách sau:
− Phát sinh ngẫu nhiên một số r trong khoảng [0; 1];
− Nếu r < qi thì chọn nhiễm sắc thể đầu tiên; ngược lại thì chọn nhiễm sắc thể
thứ i(2 ≤ i ≤pop-size) sao cho qi−1 < r ≤ qi .
Hiển nhiên, có thể sẽ có một số nhiễm sắc thể được chọn nhiều lần. Các nhiễm sắc
thể tốt nhất có nhiều bản sao hơn, các nhiễm sắc thể trung bình không thay đổi, các
nhiễm sắc thể kém nhất thì chết đi.

1.4.2

Chọn lọc cạnh tranh (Tournament Selection)

Có nhiều cách chọn lọc cạnh tranh, sau đây là 2 cách chọn phổ biến
− Chọn lọc cạnh tranh 2 (2-Tournament Selection): Hai nhiễm sắc thể khác nhau
được chọn ngẫu nhiên và được so sánh với nhiễm sắc thể tồn tại. Nếu nhiễm sắc thể
v1 không tốt hơn nhiễm sắc thể v2 nghĩa là : f (v1 ) ≤ f (v2 ), thì nhiễm sắc thể v1 chết
8


đi và bị loại ra khỏi quần thể. Quá trình này lặp lại đến hết N nhiễm sắc thể còn lại.
− Chọn lọc cạnh tranh 3 (3-Tournament Selection): Ba nhiễm sắc thể khác nhau
được chọn ngẫu nhiên và được so sánh với nhiễm sắc thể tồn tại. Nếu chúng ta có:
f (v1 ) ≤ f (v2 ) và f (v1 ) ≤ f (v3 ), thì nhiễm sắc thể v1 chết đi và bị loại ra khỏi quần
thể . Quá trình này lặp lại đến hết N nhiễm sắc thể còn lại.

1.5

Các phương pháp lai tạo (crossover) và đột biến (mutation)


Lai ghép và đột biến là hai phép cơ bản được thực hiện trong giải thuật di truyền
trên nhiều vấn đề. Có nhiều phuơng pháp lai ghép và đột biến. Ở đây chúng ta chỉ
miêu tả một số thường dùng.

1.5.1

Lai ghép (Crossover)

Lai ghép ở một vị trí (Single point crossover)
Từ hai nhiễm sắc thể cha mẹ ban đầu ta cắt ở một vị trí sau đó ghép lại với nhau
thành nhiễm sắc thể con

Lai ghép ở hai vị trí (Two point crossover)
Từ hai nhiễm sắc thể cha mẹ ban đầu ta cắt ở hai vị trí sau đó ghép chúng với
nhau thành nhiễm sắc thể con.

1.5.2

Đột biến (Mutation)

Chọn một số bit sau đó thay đổi giá trị các bít đó, tạo ra nhiễm sắc thể mới.

9


1.6

Các tham số cần sử dụng trong giải thuật di truyền

Kích thước quần thể: Pop-size, là số cá thể duy trì qua mỗi thế hệ tiến hóa của

thuật giải di truyền.
Xác suất lai ghép: Pc là xác suất một cá thể được chọn cho phép lai ghép. Xác suất
này cho ta số nhiễm sắc thể pop-size∗Pc mong đợi được dùng trong tác vụ lai tạo. Ta
tiến hành theo cách sau đây:
Đối với mỗi nhiễm sắc thể trong quần thể mới:
− Phát sinh ngẫu nhiên một số r trong khoảng [0;1]
− Nếu r < Pc chọn nhiễm sắc thể đó để lai tạo.
Bây giờ, ta ghép đôi các nhiễm sắc thể đã chọn được một cách ngẫu nhiên: đối
với mỗi cặp nhiễm sắc thể được ghép đôi, ta phát sinh ngẫu nhiên một số nguyên pos
trong khoảng [1; m] (m là tổng chiều dài - số bit của một nhiễm sắc thể). Số pos cho
biết vị trí của điểm lai.
Một tham số khác là Pm cho ta số bit đột biến Pm ∗ m∗pop-size mong đợi. Mỗi bit
(trong tất cả các nhiễm sắc thể trong quần thể) có cơ hội bị đột biến như nhau. Vì thế
ta tiến hành theo cách sau:
Đối với mỗi nhiễm sắc thể trong quần thể hiện hành (sau khi lai) và với mỗi bit
trong nhiễm sắc thể:
− Phát sinh ngẫu nhiên số r trong khoảng [0;1]
− Nếu r < Pm đột biến bit đó.

1.7

Điều kiện dừng giải thuật di truyền

Sau quá trình tiến hóa quần thể, dựa vào bài toán mà có các cách kết thúc vấn đề
khác nhau, một khi đã đạt đến mức yêu cầu. Một vài trường hợp thông thường như sau:
− Dừng theo kết quả: Một khi đạt đến mức giá trị yêu cầu thì chấm dứt ngay quá
trình thực hiện.
− Dừng dựa vào số thế hệ: Chọn số thế hệ, quá trình sẽ dừng đúng ngay số thế hệ
đã quy định trước, không cần biết kết quả thế nào.
− Tính theo thời gian: Không cần biết đã bao nhiêu thế hệ hay kết quả thế nào,

chỉ dựa vào số giờ quy định mà kết thúc.
− Tổ hợp: Dùng nhiều phương án khác nhau cho vấn đề.

10


Chương 2

ÁP DỤNG THUẬT TOÁN DI TRUYỀN GIẢI
BÀI TOÁN TỐI ƯU SỐ

Chương này trình bày ví dụ minh họa thuật toán di truyền giải bài toán tối ưu. Ta
sẽ bắt đầu thảo luận một vài ý kiến chung trước khi đi vào chi tiết ví dụ.
Không mất tính tổng quát, ta giả sử những bài toán tối ưu là bài toán tìm giá
trị lớn nhất. Bài toán tìm giá trị nhỏ nhất hàm f chính là tìm giá trị lớn nhất hàm
g = −f :
min[f (x)] = max[g(x)] = max[−f (x)].
Hơn nữa ta có thể giả định rằng hàm mục tiêu f có giá trị dương trên miền xác định
của nó, nếu không, ta có thể cộng thêm một hằng số C dương, nghĩa là:
maxg(x) = max[g(x) + C]
(vế trái và vế phải cùng đạt max tại 1 điểm x0 ).
Bài toán
Tìm giá trị lớn nhất của hàm số f (x) = 1 − x2 , với x ∈ R

2.1

Minh họa chi tiết thuật toán

Ta thiết lập các thông số ban đầu cho bài toán:
− Miền xác định của x: vì theo yêu cầu bài toán x không có ràng buộc gì nên ta

chọn 1 khoảng đủ lớn để làm miền xác định, giả sử chọn x ∈ [−99, 99] (để thuận tiện
cho việc trình bày ở bài báo cáo);
− Chiều dài nhiễm sắc thể: 30 bit;
− Kích thước quần thể: 20 nhiễm sắc th;ể
− Xác suất lai tạo: 0.25, xác suất đột biến: 0.01;
− Ta chọn hàm thích nghi sao cho nó luôn dương (nếu không khi tính tổng độ thích
nghi sẽ phải lấy giá trị tuyệt đối), ở đây ta chọn g(x) = 10000 − x2 , khi đó f (x) và
g(x) có cùng nghiệm tối ưu.
Độ dài miền xác định của biến x ở đây là 198, được chia thành 230 − 1 khoảng, nên
mỗi khoảng có giá trị là
198
.
30
2 −1

11


Một nhiễm sắc thể tương ứng một số nguyên N chính là số khoảng tính từ nhiễm sắc
thể 000...000 đến nó. Nên giá trị mà nhiễm sắc thể đó biểu diễn là
x0 = N.

198
− 99.
−1

230

Như vậy nhiễm sắc thể 011011001100000100000000010110 có giá trị nguyên (cơ số 10)
là 456146966, suy ra nó tương ứng với giá trị thực là -14.8856. Độ thích nghi của nhiễm

sắc thể này là f (−14.8856) = 9778.4175
Để cực đai hóa hàm f bằng thuật toán di truyền, ta tạo 1 quần thể có pop-size =
20 nhiễm sắc thể. Cả 30 bit trong tất cả các nhiễm sắc thể đều được tạo ngẫu nhiên.
Giả sử sau quá trình khởi tạo ta có quần thể sau đây
v0 = 011011001100000100000000010110
v1 = 110011000010111110010001000001
v2 = 001000001100101100110111111010
v3 = 110011000101100111100110111101
v4 = 011100001000011110000100010101
v5 = 111101001101111101110001111011
v6 = 110100000000011110010111110110
v7 = 100011011011100000110111001101
v8 = 000010100000100100011111000100
v9 = 010001000100000101000011000000
v10 = 011100101011010010011101010110
v11 = 001111110111110111101111010010
v12 = 111110100001001000010011111111
v13 = 100010001101000100011010001000
v14 = 001101110001110011110110000011
v15 = 011110100110001010011100101011
v16 = 000110011010110001000001001110
v17 = 101001000100001100010101110101
v18 = 001001100110111001111001100011
v19 = 101101001110000001101110010010

12


Ta tính giá trị thực mà chúng biểu diễn và độ thích nghi của chúng như sau:
eval(v0 ) = g(−14.8856) = 9778.41752

eval(v1 ) = g(58.9249) = 6527.84910
eval(v2 ) = g(−73.6360) = 4577.73531
eval(v3 ) = g(59.0528) = 6512.75899
eval(v4 ) = g(−11.9655) = 9856.82511
eval(v5 ) = g(90.3938) = 1828.95527
eval(v6 ) = g(61.8979) = 6168.64491
eval(v7 ) = g(10.6112) = 9887.40143
eval(v8 ) = g(−91.2380) = 1675.61508
eval(v9 ) = g(−46.2090) = 7864.72105
eval(v10 ) = g(−10.2824) = 9894.27132
eval(v11 ) = g(−49.8929) = 7510.69269
eval(v12 ) = g(94.4139) = 1085.997858
eval(v13 ) = g(6.8192) = 9953.497861
eval(v14 ) = g(−56.3734) = 6822.03538
eval(v15 ) = g(−4.3426) = 9981.14100
eval(v16 ) = g(−79.1436) = 3736.28433
eval(v17 ) = g(28.0464) = 9213.39771
eval(v18 ) = g(−69.2756) = 5200.89067
eval(v19 ) = g(40.8968) = 8327.45097
Bây giờ ta xây dựng hệ thống kiến trúc bánh xe ru-let cho tiến trình chọn lọc. Tổng
độ thích nghi của quần thể là
19

eval(vi ) = 136404.5836
i=0

Xác suất chọn lọc pi của mỗi nhiễm sắc thể vi là
p0 = eval(v0 )/F = 0.0716868
p1 = eval(v1 )/F = 0.0478565
p2 = eval(v2 )/F = 0.0335599

13


p3 = eval(v3 )/F = 0.0477458
p4 = eval(v4 )/F = 0.0722616
p5 = eval(v5 )/F = 0.0134083
p6 = eval(v6 )/F = 0.0452231
p7 = eval(v7 )/F = 0.0724858
p8 = eval(v8 )/F = 0.0122841
p9 = eval(v9 )/F = 0.0576573
p10 = eval(v10 )/F = 0.07253620
p11 = eval(v11 )/F = 0.05506187
p12 = eval(v12 )/F = 0.00796159
p13 = eval(v13 )/F = 0.07297040
p14 = eval(v14 )/F = 0.05001324
p15 = eval(v15 )/F = 0.07317306
p16 = eval(v16 )/F = 0.02739119
p17 = eval(v17 )/F = 0.06754463
p18 = eval(v18 )/F = 0.03812841
p19 = eval(v19 )/F = 0.06104964
Các vị trí xác suất qi của mỗi nhiễm sắc thể vi là
q0 = 0.0716
q1 = 0.1195
q2 = 0.1531
q3 = 0.2008
q4 = 0.2731
q5 = 0.2865
q6 = 0.3317

q7 = 0.4042

q8 = 0.4165
q9 = 0.4741
q10 = 0.5467
q11 = 0.6017
q12 = 0.6097
q13 = 0.6826

q14
q15
q16
q17
q18
q19

= 0.7327
= 0.8058
= 0.8332
= 0.9008
= 0.9389
= 0.9999

Bây giờ ta quay bánh xe Roulette 20 lần, mỗi lần chọn một nhiễm sắc thể cho quần
thể mới. Giả sử thứ tự ngẫu nhiên của 20 số phát sinh trong khoảng [0, 1] là

14


0.8900
0.5050
0.3135

0.4253
0.0887

0.1631
0.7023
0.7976
0.8177
0.7652

0.6986
0.8122
0.7277
0.3092
0.6800

0.0966
0.1002
0.9801
0.0218
0.1072

Số r đầu tiên r = 0.8900 lớn hơn q16 nhỏ hơn q17 nghĩa là nhiễm sắc thể v17 được
chọn vào quần thể mới; số thứ hai 0.1631 lớn hơn q2 và nhỏ hơn q3 nghĩa là nhiễm sắc
thể v3 được chọn,vv... Như vậy quần thể mới gồm những nhiễm sắc thể sau:
v0 = 101001000100001100010101110101(v17 )
v1 = 110011000101100111100110111101(v3 )
v2 = 001101110001110011110110000011(v14 )
v3 = 110011000010111110010001000001(v1 )
v4 = 011100101011010010011101010110(v10 )
v5 = 001101110001110011110110000011(v14 )

v6 = 000110011010110001000001001110(v16 )
v7 = 110011000010111110010001000001(v1 )
v8 = 110100000000011110010111110110(v6 )
v9 = 011110100110001010011100101011(v15 )
v10 = 001101110001110011110110000011(v14 )
v11 = 101101001110000001101110010010(v19 )
v12 = 010001000100000101000011000000(v9 )
v13 = 000110011010110001000001001110(v16 )
v14 = 110100000000011110010111110110(v6 )
v15 = 011011001100000100000000010110(v0 )
v16 = 110011000010111110010001000001(v1 )
v17 = 011110100110001010011100101011(v15 )
v18 = 100010001101000100011010001000(v13 )
v19 = 110011000010111110010001000001(v1 )
Bây giờ ta sẽ áp dụng phép toán lai ghép cho những cá thể trong quần thể mới (các
vectơ vi ). Xác suất lai ghép Pc = 0.25 vì thế ta hy vọng trung bình 25% nhiễm sắc thể
sẽ tham gia lai tạo. Ta tiến hành theo cách sau: với mỗi nhiễm sắc thể trong quần thể
mới ta phát sinh ngẫu nhiên một số r trong khoảng [0, 1]; nếu r < 0.25, ta chọn một
nhiễm sắc thể cho trước để lai tạo. Giả sử thứ tự các số ngẫu nhiên là:

15


0.3704
0.4278
0.8973
0.3560
0.7709

0.8631

0.6023
0.1641
0.9907
0.4452

0.0608
0.8143
0.3077
0.2892
0.6660

0.6116
0.2981
0.1289
0.3345
0.1792

Điều đó có nghĩa là nhiễm sắc thể v2 , v11 , v9 và v19 sẽ được đem vào để lai ghép. Ở
đây số nhiễm sắc thể được đem vào lai ghép là chẵn, nếu chúng là lẻ thì ta có thể loại
bớt hoặc thêm vào 1 nhiễm sắc thể ngoài. Việc thêm vào hoặc loại bớt 1 nhiễm sắc thể
nên thực hiện ngẫu nhiên thì tốt hơn. Bây giờ ta cho các cặp nhiễm sắc thể phối một
cách ngẫu nhiên, giả sử 2 cặp nhiễm sắc thể phối với nhau là cặp (v11 , v19 ) và (v 2, v9 )
Cặp nhiễm sắc thể thứ nhất là
v11 = 101101001110000001101110010010
v19 = 110011000010111110010001000001
Ta phát sinh một số ngẫu nhiên pos thuộc khoảng [1; 30], 30 là tổng chiều dài (số
bit) của nhiễm sắc thể. Số pos cho biết vị trí điểm lai tạo. Giả sử pos = 11, các nhiễm
sắc thể này bị cắt sau bit thứ 11 và được thay bằng cặp con của chúng:
v”11 = 101101001110001010011100101011
v”19 = 011110100110000001101110010010

Cặp nhiễm sắc thể thứ hai là
v2 = 001101110001110011110110000011
v9 = 011110100110001010011100101011
và số phát sinh là pos = 2. Các nhiễm sắc thể này được thay bằng cặp con của chúng:
v”2 = 001110100110001010011100101011
v”9 = 011101110001110011110110000011
Cuối cùng quần thể hiện hành là:
v0 = 101001000100001100010101110101
v1 = 110011000101100111100110111101
v2 = 001110100110001010011100101011
v3 = 110011000010111110010001000001
v4 = 011100101011010010011101010110
16


v5 = 001101110001110011110110000011
v6 = 000110011010110001000001001110
v7 = 110011000010111110010001000001
v8 = 110100000000011110010111110110
v9 = 011101110001110011110110000011
v10 = 001101110001110011110110000011
v11 = 101101001110001010011100101011
v12 = 010001000100000101000011000000
v13 = 000110011010110001000001001110
v14 = 110100000000011110010111110110
v15 = 011011001100000100000000010110
v16 = 110011000010111110010001000001
v17 = 011110100110001010011100101011
v18 = 100010001101000100011010001000
v19 = 011110100110000001101110010010

Phép toán kế tiếp, đột biến được thực hiện trên cơ sở từng bit một. Xác suất đột
biến Pm = 0.01, vì thế ta hy vọng trung bình 1/100 số bit sẽ qua đột biến. Có 600
bit(mxpop − size = 30x20) trong toàn quần thể, ta hy vọng trung bình 6 bit được đột
biến mỗi thế hệ. Mỗi bit có cơ hội đột biến ngang nhau vì thế đối với mỗi bit trong
quần thể, ta phát sinh ngẫu nhiên một số r trong khoảng [0, 1], nếu r < 0.01, ta đột
biến bit này.
Điều này có nghĩa ta phải phát sinh 660 số ngẫu nhiên. Giả sử có 3 trong số này
nhỏ hơn 0.01; vị trí bít và số ngấu nhiên như sau:
Vị trí bit Số ngẫu nhiên
47
0.0082
339
0.0066
563
0.0072
Từ đó ta suy ra vị trí của nhiễm sắc thể và bit tương ứng là
Vị trí bit Số thứ tự của nhiễm sắc thể
47
2
339
12
563
19
17

Số thứ tự của bit trong nhiễm sắc thể
17
10
23



Điều này có nghĩa là 3 nhiễm sắc thể bị ảnh hưởng của phép đột biến.
Quần thể cuối ùng được liệt kê ở dưới; các bit đột biến được tô đậm và gạch dưới:
v0 = 101001000100001100010101110101
v1 = 110011000101100101100110111101
v2 = 001110100110001010011100101011
v3 = 110011000010111110010001000001
v4 = 011100101011010010011101010110
v5 = 001101110001110011110110000011
v6 = 000110011010110001000001001110
v7 = 110011000010111110010001000001
v8 = 110100000000011110010111110110
v9 = 011101110001110011110110000011
v10 = 001101110001110011110110000011
v11 = 101101001010001010011100101011
v12 = 010001000100000101000011000000
v13 = 000110011010110001000001001110
v14 = 110100000000011110010111110110
v15 = 011011001100000100000000010110
v16 = 110011000010111110010001000001
v17 = 011110100110001010011100101011
v18 = 100010001101000100011000001000
v19 = 011110100110000001101110010010
Ta vừa hoàn thành một bước lặp (nghĩa là một thế hệ) của thủ tục di truyền. Ta
xam xét một chút các kết quả của tiến trình tiến hóa quần thể mới. Trong thời kì tiến
hóa, ta giải mã từng nhiễm sắc thể và tính các giá trị của hàm thích nghi từ giá trị
vừa giải mã. Ta được:
eval(v0 ) = g(28.0464) = 9213.39771
eval(v1 ) = g(59.0513) = 6512.937407
eval(v2 ) = g(−53.84269) = 7100.96425

eval(v3 ) = g(58.9249) = 6527.84910
18


eval(v4 ) = g(−10.2824) = 9894.27132
eval(v5 ) = g(−56.3734) = 6822.03538
eval(v6 ) = g(−79.1436) = 3736.28433
eval(v7 ) = g(58.9249) = 6527.84910
eval(v8 ) = g(61.8979) = 6168.64491
eval(v9 ) = g(−6.8734) = 9952.75583
eval(v10 ) = g(−56.3734) = 6822.03538
eval(v11 ) = g(40.7100) = 8342.69263
eval(v12 ) = g(−46.2090) = 7864.72105
eval(v13 ) = g(−79.1436) = 3736.28433
eval(v14 ) = g(61.8979) = 6168.64491
eval(v15 ) = g(−14.8856) = 9778.41752
eval(v16 ) = g(58.9249) = 6527.84910
eval(v17 ) = g(−4.3426) = 9981.14100
eval(v18 ) = g(6.8192) = 9953.49818
eval(v19 ) = g(−4.3492) = 9981.08372
Chú ý rằng quần thể mới có độ thích nghi F = 151612.86754 cao hơn tổng độ thích
nghi của quần thể cũ.
Tiến trình lặp lại lần nữa và các phép toán di truyền được áp dụng, lượng giá thế hệ
kế tiếp .v.v... Không khó để theo dõi cá thể tốt nhất trong tiến trình tiến hóa. Thông
thường trong các cài đặt thuật giải di truyền, cá thể tốt nhất được lưu trữ ở một vị trí
riêng biệt; bằng cách đó, thuật giải có thể duy trì cá thể tốt nhất tìm được trong suốt
quá trình. Ta sẽ cho điều kiện dừng ở đây là số bước lặp đủ lớn (1 triệu lần lặp). Cá
thể tốt nhất sau cùng sẽ được chọn làm giải pháp tối ưu cho bài toán.

2.2


Mã nguồn Java giải bài toán

Bài toán được lập trình theo hướng đối tượng, với đối tượng ở đây là các cá thể
(class Solution.java). Mỗi cá thể có các thuộc tính là chiều dài nhiễm sắc thể (SIZE),
1 mảng các bit nhị phân, giá trị nhỏ nhất và lớn nhất của các cá thể, và cuối cùng làm
hàm thích nghi của mõi cá thể. Sau đó trong class chạy chính có các thuộc tính là kích
thước quần thể (pop-size), xác suất lai ghép, xác suất đột biến và một cá thể để lưu
trữ cá thể tốt nhất.
Sau đây là class Solution.java

19


package ga.chuyenbka;
import static java.lang.Math.pow;
import java.util.Random;
public class Solution implements Comparable<Solution> {
//độ dài mỗi cá thể (tính bằng bit)
public static final int SIZE = 30;
//kiểu mã hóa (nhị phân)
public boolean[] genotype;
//can duoi, can tren
private final double a = -99;
private final double b = 99;
//khởi tạo cá thể
public Solution() {
genotype = new boolean[SIZE];
}
//cách chọn giá trị ngẫu nhiên cho cá thể

void random() {
Random rand = new Random();
for (int i = 0; i < genotype.length; i++) {
genotype[i] = 0.5 > rand.nextFloat();
}
}
//chuyển thành dạng chuỗi
private String gene() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < genotype.length; i++) {
sb.append(genotype[i] == true ? 1 : 0);
}
return sb.toString();
}
//dot bien
public Solution mut(int n) {
//dot bien o bit thu n
genotype[n] = !genotype[n];
return this;
}
//hàm thích nghi
double fitness() {
Long decimalValue;
decimalValue = Long.parseLong(this.gene(), 2);
//gia tri thuc cua ca the do
double doubleValue = a + (decimalValue * (b - a)) / (pow(2, SIZE) - 1);
return f(doubleValue);
}
//ham muc tieu


20


double f(double x) {
return pow(10, 9) - x * x;
//return pow(x,4) - 3*x + 8;
}
//so sanh 2 ca the de tien sap xep
public int compareTo(Solution o) {
double f1 = this.fitness();
double f2 = o.fitness();
if (f1 < f2) {
return 1;
} else if (f1 > f2) {
return -1;
} else {
return 0;
}
}
//hien thi ca the dang chuoi
@Override
public String toString() {
Long decimalValue = Long.parseLong(this.gene(), 2);
double doubleValue = a + (decimalValue * (b - a)) / (pow(2, SIZE) - 1);
return "gene=" + gene() + " decimal = " + doubleValue + " fit=" + fitness();
}
}

và class chạy chính (ga-chuyenbka.java)
/*

*Bai toan tim gia tri on nhat cua ham so voi x trong khoang nao do
*/
package ga.chuyenbka;
import
import
import
import

static java.lang.Math.pow;
java.util.Collections;
java.util.LinkedList;
java.util.Random;

/**
*
* @author CHUYENBKA
*/
public final class GaChuyenbka {
final Random rand = new Random();
//so luong ca the trong quan the
final static int populationSize = 20;
//do dai ca the
final static int solutionSize = Solution.SIZE;
//ti le ca the duoc chon de lai

21


final static double parentUsePercent = 0.25;
//ti le bit dot bien

final private static double mutRate = 0.01;
static Solution bestSolution;
//khoi tao quan the
LinkedList<Solution> population = new LinkedList<>();
public GaChuyenbka() {
bestSolution = new Solution();
bestSolution.random();
for (int i = 0; i < populationSize; i++) {
Solution c = new Solution();
c.random();
population.add(c);
}
System.out.println("Khoi tao quan the ban dau");
print();
}
void print() {
System.out.println("-- print");
int i = 0;
for (Solution c : population) {
System.out.println(i + ": " + c);
i++;
}
}
//lai ghep cheo
Solution newChild(Solution c1, Solution c2, int pivot) {
Solution child = new Solution();
for (int i = 0; i < pivot; i++) {
child.genotype[i] = c1.genotype[i];
}
for (int j = pivot; j < Solution.SIZE; j++) {

child.genotype[j] = c2.genotype[j];
}
return child;
}
//tao quan the tiep theo
void produceNextGen() {
LinkedList<Solution> newPopulation = new LinkedList<>();
//tinh tong do thich nghi
double sum = 0;
for (int i = 0; i < population.size(); i++) {
sum += population.get(i).fitness();
}
//do thich nghi cua tung ca the
Double[] p = new Double[population.size()];

22


//tim ca the co do thich nghi tot nhat de giu lai so sanh
double best = population.get(0).fitness();
int index = 0; //thu tu cua phan tu tot nhat
for (int i = 0; i < population.size(); i++) {
p[i] = population.get(i).fitness() / sum;
if (best < population.get(i).fitness()) {
best = population.get(i).fitness();
index = i;
}
}
if (bestSolution.fitness() < population.get(index).fitness()) {
bestSolution = population.get(index);

System.out.println(bestSolution);
}
//banh xe ru-let
Double[] q = new Double[populationSize];
for (int i = 0; i < populationSize; i++) {
q[i] = 0d;
}
for (int i = 0; i < populationSize; i++) {
for (int j = 0; j <= i; j++) {
q[i] += p[j];
}
}
//quay banh xe rulet de chon
Double[] r = new Double[populationSize];
for (int i = 0; i < populationSize; i++) {
r[i] = rand.nextDouble();
if (r[i] < q[0]) {
newPopulation.add(population.get(0));
} else {
for (int j = 1; j < populationSize; j++) {
if (r[i] < q[j] && r[i] > q[j - 1]) {
newPopulation.add(population.get(j));
break;
}
}
}
}
//chon cac ca the the lai ghep
LinkedList<Solution> crossover = new LinkedList<>();
for (int i = 0; i < populationSize; i++) {

r[i] = rand.nextDouble();
if (r[i] < parentUsePercent) {
crossover.add(newPopulation.get(i));
}
}

23


//qua trinh lai ghep
if (crossover.size() > 0) {
int n = ((crossover.size() % 2) == 0) ? crossover.size() : crossover.size() - 1;
for (int i = 0; i < n; i = i + 2) {
//diem ghep cheo
int pivot = rand.nextInt(Solution.SIZE);
Solution child1 = newChild(crossover.get(i), crossover.get(i + 1), pivot);
Solution child2 = newChild(crossover.get(i + 1), crossover.get(i), pivot);
//chen ca the moi vao quan the moi
newPopulation.add(child1);
newPopulation.add(child2);
//xoa ca the cu
newPopulation.remove(crossover.get(i));
newPopulation.remove(crossover.get(i + 1));
}
}
//dot bien gen (bit)
int genSize = populationSize * solutionSize;
Double[] mut = new Double[genSize];
for (int i = 0; i < genSize; i++) {
mut[i] = rand.nextDouble();

if (mut[i] < mutRate) {
int k = i / solutionSize;
int n = i - k * solutionSize;
newPopulation.get(k).mut(n);
}
}
population = newPopulation;
}
public static void main(String[] args) {
GaChuyenbka ga = new GaChuyenbka();
ga.run();
}
void run() {
final int maxSteps = 1000000;
int count = 0;
while (count < maxSteps) {
count++;
produceNextGen();
}
System.out.println("\nResult");
System.out.println(bestSolution);
}
}

24


2.3

Màn hình kết quả chạy chương trình


Màn hình sau khởi tạo quần thể ban đầu (ngẫu nhiên)

Màn hình sau khi chạy các bước lặp, cá thể tốt nhất sẽ được cập nhật dần.

25