BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÀNH PHỐ HỒ CHÍ MINH

CÁC DẠNG CỦA THUẬT TOÁN DI TRUYỀN
(CLASSIFICATION OF GENETIC ALGORITHM)

Tiểu luận môn Các hệ cơ sở tri thức

NHÓM THỰC HIỆN: LÝ TRẦN THÁI HỌC
NGUYỄN MINH PHƯƠNG
LÊ XUÂN MẠNH
HOÀNG HỮU HẢO

GVHD: PGS. TS. LÊ HOÀNG THÁI

TP. HỒ CHÍ MINH - 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÀNH PHỐ HỒ CHÍ MINH

CÁC DẠNG CỦA THUẬT TOÁN DI TRUYỀN
(CLASSIFICATION OF GENETIC ALGORITHM)

Tiểu luận môn Các hệ cơ sở tri thức

Người hướng dẫn khoa học:
PGS.TS. LÊ HOÀNG THÁI

TP. HỒ CHÍ MINH – 2015

1


Mục lục
DANH MỤC CÁC TỪ VIẾT TẮT...................................................................................................................... 3
DANH MỤC CÁC HÌNH ..................................................................................................................................... 4
DANH MỤC CÁC BẢNG .................................................................................................................................... 5
CHƯƠNG 1. GIỚI THIỆU .................................................................................................................................. 6
CHƯƠNG 2. THUẬT TOÁN DI TRUYỀN ĐƠN GIẢN (SIMPLE GENETIC ALGORITHM - SGA) ..... 7
CHƯƠNG 3. THUẬT TOÁN DI TRUYỀN SONG SONG VÀ PHÂN TÁN (PARALLEL AND
DISTRIBUTED GENETIC ALGORITHM - PGA VÀ DGA) ......................................................................... 9
3.1. Mô hình song song kiếu chủ - tớ (Master – Slave) .................................................................................... 11
3.2. Thuật toán di truyền song song theo cách chia mịn hay mô hình thuật toán di truyền tế bào (Fine Grained
Parallel GA – Cellular GA) .............................................................................................................................. 12
3.3. Thuật toán di truyền xử lý song song bằng cách chia nhiều nhóm hay thuật toán di truyền phân tán, chia
thô (Multiple – Deme Parallel GA, Distributed GA or Coarse Grained GA) ................................................... 13
3.4. Các thuật toán song song thứ bậc (Hierarchical Parallel Algorithms) ....................................................... 15
CHƯƠNG 4: THUẬT TOÁN DI TRUYỀN DẠNG LAI (HYBRID GENETIC ALGORITHM - HGA) .. 18
4.1. Lai ghép chéo (Crossover) ......................................................................................................................... 19
4.2. Khởi tạo theo hướng Heuristic................................................................................................................... 19
4.3. Thủ tục RemoveSharp ............................................................................................................................... 20
4.4. Thủ tục LocalOpt ....................................................................................................................................... 21
4.5. Độ phức tạp của các thủ tục RemoveSharp và LocalOpt .......................................................................... 21
4.5.1. Độ phức tạp của các thủ tục RemoveSharp ...................................................................................... 21
4.5.2. Độ phức tạp của các thủ tục LocalOpt.............................................................................................. 22
CHƯƠNG 5: THUẬT TOÁN DI TRUYỀN THÍCH NGHI (ADAPTIVE GENETIC ALGORITHM-AGA)
.............................................................................................................................................................................. 23
5.1. Khởi tạo ..................................................................................................................................................... 23
5.2. Hàm đánh giá ............................................................................................................................................. 24
5.3. Hàm lựa chọn ............................................................................................................................................. 24

5.4. Hàm lai ghép .............................................................................................................................................. 25
5.5. Hàm đột biến.............................................................................................................................................. 25
CHƯƠNG 6: THUẬT TOÁN DI TRUYỀN NHANH (FAST MESSY GENETIC ALGORITHM – FmGA)
.............................................................................................................................................................................. 26
CHƯƠNG 7: THUẬT TOÁN DI TRUYỀN VỚI MẪU ĐỘC LẬP (INDEPENDENT SAMPLING
GENETIC ALGORITHM - ISGA) ................................................................................................................... 27
7.1. Giai đoạn độc lập lấy mẫu ......................................................................................................................... 27
7.2. Giai đoạn sinh sản ...................................................................................................................................... 28
CHƯƠNG 8: TỔNG KẾT.................................................................................................................................. 30
TRẢ LỜI CÂU HỎI CUỐI CHƯƠNG ............................................................................................................ 31

2


DANH MỤC CÁC TỪ VIẾT TẮT
Genetic Algorithm

GA

Simple Genetic Algorithm

SGA

Parallel Genetic Algorithm

PGA

Distributed Genetic Algorithm

DGA


3


DANH MỤC CÁC HÌNH
Hình 1. Sơ đồ của mô hình master-slave của GA xử lý song song................................ 10
Hình 2. Sơ đồ của di truyền song song theo cách chia mịn. .......................................... 14
Hình 3. Sơ đồ của Thuật toán di truyền xử lý song song bằng cách chia nhiều nhóm hay
thuật toán di truyền phân tán, chia thô .......................................................................... 14
Hình 4. Sơ đồ kết hợp mô hình xử lý song song nhiều nhóm (mức cao) và xử lý song
song bằng cách chia mịn (mức thấp) ............................................................................ 16
Hình 5. Sơ đồ xử lý Master – Slave (mức cao) và mô hình xử lý bằng cách chia nhiều
nhóm (mức thấp) .......................................................................................................... 16
Hình 6. Sơ đồ kết hợp xử lý song song bằng cách chia nhiều nhóm ở 2 mức ............... 16

4


DANH MỤC CÁC BẢNG
Bảng 1. Bảng so sánh các phương pháp song song hóa giải thuật di truyền.................. 16
Bảng 2. Bảng so sánh về phương thức thực hiện của giải thuật di truyền song song .... 17

5


CHƯƠNG 1. GIỚI THIỆU
Thuật toán di truyền (Genetic Algorithm - GA) là thuật toán tìm kiếm lời giải dựa trên cơ chế
chọn lọc và di truyền trong tự nhiên. Thuật toán là những thủ tục được thực hiện theo từng bước một để
tìm các giải pháp cho các vấn đề. Thuật toán di truyền cũng cung cấp các thủ tục như thế để giải quyết
vấn đề nhưng chúng được dựa trên các mô hình di truyền. Giải thuật di truyền đã được chứng minh về

mặt lý thuyết lẫn thực nghiệm và cho thấy được hiệu quả mạnh mẽ trong việc tìm kiếm giải pháp ở
những vấn đề phức tạp. Các thuật toán di truyền có khả năng cho tăng hiệu quả tìm kiếm trong kinh
doanh, khoa học và kỹ thuật. Các thuật toán sẽ ít phức tạp hơn nhưng mạnh mẽ hơn trong tìm kiếm khi
áp dụng nguyên lý di truyền. Trong tiểu luận này sẽ thảo luận các loại khác nhau của di truyền các thuật
toán như GA song song, phân tán, ….

6


CHƯƠNG 2. THUẬT TOÁN DI TRUYỀN ĐƠN GIẢN (SIMPLE GENETIC
ALGORITHM - SGA)
Đối với nhiều thuật toán tìm kiếm cần nhiều thông tin phụ trợ có liên quan đến cấu trúc dữ liệu
của bài toán để đưa ra kết quả đúng. Ví dụ đối với kỹ thuật tìm kiếm truyền thống hoặc thuật toán tham
lam thì cần quyền truy cập vào các thông số để tính toán, trong khi đó thuật toán di truyền thì không cần
phải truy cập tất cả. Đối với GA, có thể tìm kiếm kết quả đạt hiệu quả cao trong khi đang “mù” về cấu
trúc thông tin. GA sử dụng quy tắc chuyển đổi kiểu xác suất để hướng đến không gian tìm kiếm có khả
năng đạt kết quả có hiệu quả hơn.
Các cơ chế của thuật toán di truyền đơn giản không có gì phức tạp, đơn giản chỉ là sao chép
chuỗi và trao đổi một phần các chuỗi. Một thuật toán di truyền đơn giản mà mang lại kết quả tốt trong
nhiều vấn đề thực tế là gồm ba hoạt động. Đó là:


Sinh sản



Lai ghép




Đột biến

Sinh sản là một quá trình sao chép một phần chuỗi (còn gọi là gen) của các cá thể theo giá trị hàm
mục tiêu f. Ta có thể xem xét hàm mục tiêu f như một biện pháp tối đa hóa lợi nhuận, hữu ích, hay điều
tốt đẹp nào đó mà ta muốn có được. Chuỗi được sao chép theo kiểu xác suất để độ thích nghi có thể cao
hơn trong các thế hệ tiếp theo. Trong một thuật toán có thể được thực hiện sinh sản với nhiều phương
thức khác nhau. Cách đơn giản nhất có thể thực hiện sinh sản như sử dụng một vòng Roulette. Trong
vòng Roulette này mỗi chuỗi trong quần thể có có kích thước tỷ lệ thuận với độ thích nghi của mình.
Các bước chuẩn cho việc chạy thuật toán di truyền đơn giản là:
randomly generate population // tạo ra một cách ngẫu nhiên quần thể
select parents (using fitness function) // chọn cha mẹ (dùng hàm thích nghi)
selection methods: // phương pháp lựa chọn
roulette wheel// dựng vòng tròn roulette
tournament // chạy vòng tròn chọn số lượng cá thể
demetic// nhóm các cá thể
crossover parent chromosomes // lai ghép chéo
mutate offspring chromosomes // đột biến
add offspring back into pool // thêm cá thể con vào quần thể mới e
litism // xét quần thể ưu tú mới
(select parents) // chọn lại cá thể cha mẹ mới
SGA có tác dụng và hiệu quả khi: không gian tìm kiếm là lớn, phức tạp hoặc chưa được hiểu rõ.
Khó mã hóa để thu hẹp không gian tìm kiếm. Không có phân tích toán học. Các phương pháp tìm kiếm
truyền thống thất bại.
7


Ưu điểm của phương pháp SGA là dễ dàng có thể xử lý khó khăn và đạt mục tiêu; tất cả những
điều đó có thể được xử lý như các thành phần có trọng số trong hàm thích nghi, làm cho nó dễ dàng để
thích ứng với các tiến trình của SGA để cụ thể một yêu cầu có phạm vi rất rộng trong mục tiêu tổng thể.


8


CHƯƠNG 3. THUẬT TOÁN DI TRUYỀN SONG SONG VÀ PHÂN TÁN
(PARALLEL AND DISTRIBUTED GENETIC ALGORITHM - PGA VÀ DGA)
Thuật toán di truyền song song (Parallel Genetic Algorithm - PGA) là thực hiện song song của
nhiều tiến trình SGA khác nhau. Các thuật toán di truyền song song (PGAs) được phát triển để giảm
thời gian thực hiện tìm kiếm các giải pháp gần tối ưu trong các bài toán có không gian tìm kiếm lớn.
PGAs có lợi ích đáng kể về hiệu suất và khả năng mở rộng quy mô. PGAs có thể dễ dàng thực hiện trên
hệ thống máy tính không đồng nhất hoặc trên máy tính lớn cho phép chạy song song. Cách thức thực
hiện của PGAs phụ thuộc vào các yếu tố sau:


Hàm thích nghi và đột biến được áp dụng như thế nào?



Cá thể được lựa chọn cục bộ hoặc toàn thể được áp dụng ra sao?



Sử dụng một hay nhiều nhóm quần thể?



Nếu có nhiều quần thể, việc lai ghép các cá thể ra sao?

Cách đơn giản nhất của một PGA là tạo nhiều bản sao cho mỗi SGA là một phần tử xử lý (Processing
Element - PE). Mỗi PE khác nhau được bắt đầu với quần thể ban đầu, tiến hóa và dừng lại một cách độc
lập. PGA hoàn toàn ngừng khi tất cả PE dừng. PGA có nhiều phương pháp khác nhau để thực hiện:



PGA hoạt động kiểu độc lập (Independent PGA)



PGA cho phép di chuyển cá thể (Migration PGA)



PGA hoạt động theo kiểu phân vùng (Partition PGA)



PGA hoạt động theo kiểu phân đoạn (Segmentation PGA)



PGA hỗn hợp vừa phân đoạn và di chuyển cá thể (Segmentation–Migration PGA)

Ưu điểm của các phương pháp tiếp cận của PGA hoạt động độc lập là mỗi PE bắt đầu với một quần
thể độc lập. Đa quần thể như vậy làm giảm cơ hội phát triễn cá thể ưu tú dẫn đến tất cả PE sớm hội tụ
dẫn đến các giải pháp có chất lượng kém. Cách tiếp cận này chỉ đơn giản là dùng giải pháp tốt nhất sau
nhiều lần thực hiện SGA trên các quần thể ban đầu khác nhau.
Cách tiếp cận thứ hai là PGA, PGA cho phép di chuyển cá thể, tăng hiệu quả hơn so với phương
pháp tiếp cận độc lập là cho phép di chuyển nhiễm sắc thể giữa các PE để ngăn ngừa hội tụ xấu và chia
sẻ các giải pháp chất lượng cao. Di chuyển nhiễm sắc thể xảy ra sau một số lần lặp nhất định, với mỗi
PE gửi một bản sao của nhiễm sắc thể tốt nhất tại quần thể cục bộ của mình đến các PE khác. Nhiễm
sắc thể nhận được sẽ thay thế các nhiễm sắc thể xấu nhất tại quần thể cục bộ PE trừ trường hợp nhiễm
sắc thể giống hệt nhau đã tồn tại trong cá thể cục bộ.

PGA hoạt động theo kiểu phân vùng (Partition PGA) là phân chia không gian tìm kiếm vào vùng
con rời nhau và bắt buộc các PE tìm kiếm trong vùng con khác nhau. PGA hoạt động theo kiểu phân
đoạn (Segmentation PGA) là bắt đầu bằng cách phân chia việc tuyển chọn vào các tiến trình phụ. Sau
đó, kết hợp trở lại và tiến hành tuyển chọn ở tiến trình chính. Sự kết hợp của phân đoạn và di chuyển
9


chính là PGA hỗn hợp vừa phân đoạn và di chuyển cá thể. Việc tái tổ hợp xảy ra vào cuối mỗi giai đoạn,
các tiến trình phụ được chứa bởi một nhóm các PE đánh số theo thứ tự tăng dần.
PGA có thể được thực hiện theo phương thức xử lý song song kết hợp với hình thức chia để trị.
Trong cách tiếp cận xử lý song song, mô hình GA được thực hiện tuần tự song song trên một máy tính
bằng cách chia các nhiệm vụ thực hiện một bộ vi xử lý. Trong hình thức xử lý chia để trị, quần thể được
chia thành nhiều quần thể phụ và phân phối cho nhiều bộ xử lý. Các quần thể phụ có thể tồn tại độc lập
hay tương tác với nhau (chia thô hoặc phân phối GA - coarse grained or distributed GA) hoặc chỉ có
một quần thể với các quần thể thành viên khác (chia mịn GA - Fine grained GA). Sự tương tác giữa các
quần thể phụ tùy theo cấu trúc không gian của quần thể. Những mô hình duy trì sự đa dạng quần thể hơn
và giảm thiểu những hội tụ sớm. Nó cũng phù hợp với mô hình tiến hóa, với một độ lớn và sự độc lập
của các quần thể.
Hướng tiếp cận xử lý song song chủ yếu là đánh giá độ thích nghi bằng hình thức song song trên
quần thể chung. Việc lựa chọn và lai ghép được thực hiện bằng độc lập giữa các cá thể. Các tính toán
song song phổ biến nhất là sự đánh giá độ thích nghi vì chỉ đòi hỏi thông tin của cá thể được đánh giá,
do đó không có thông tin liên lạc nào khác. Đại diện cho hình thức này là mô hình chủ - tớ (Master Slave) (Hình 1). Các đối tượng Master chứa thông tin quần thể và cá thể lựa chọn. Các đối tượng Slave
đánh giá độ thích nghi và áp dụng các toán tử di truyền như lai ghép và đột biến. Thông tin sau khi tính
toán được Slave trả về cho Master. Mô hình này có hai chế độ hoạt động: đồng bộ và không đồng bộ.
Trong chế độ đồng bộ, các Master đợi đến khi nhận được các giá trị thích nghi của toàn bộ dân số, trước
thực hiện tạo thế hệ sau. Ngược lại, Master không dừng tiến trình của mình để đợi các tiến trình chậm
để đồng bộ. Lúc đó bộ nhớ máy tính được phân phối lại, các Master gửi thông tin cá thể đến với các bộ
xử lý Slave thực hiện đánh giá thích nghi, thu thập các kết quả và áp dụng các toán tử di truyền để tạo
thế hệ mới. Số của cá thể được giao cho từng bộ xử lý có thể là tĩnh hoặc động.


Hình 1. Sơ đồ của mô hình master-slave của GA xử lý song song.

Trong phương pháp hướng phân phối hay chia để trị, quần thể được chia thành một số quần thể
con được gọi là nhóm (demes). Các nhóm được tách rời nhau và cá thể cạnh tranh chỉ trong một nhóm.
Và hàm di cư được bổ sung sử dụng để di chuyển các cá thể từ nhóm này sang nhóm khác. Nếu cá thể
có thể di chuyển đến bất kỳ nhóm khác, lúc đó mô hình được gọi là mô hình đảo (island). Di cư có thể
10


được kiểm soát bằng nhiều cách khác nhau các thông số như tốc độ di chuyển, cấu trúc liên kết, kế hoạch
di cư như cá thể tốt nhất / tồi tệ nhất / xác suất di chuyển ngẫu nhiên và tần suất di cư.
Hướng tiếp cận khác thuật toán di truyền song song phân chia kiểu thô và mịn. Mô hình chia thô
PGA đề cập đến số lượng nhóm tương đối nhỏ với nhiều cá thể thuộc mỗi nhóm. Đặc trưng mô hình
này là thời gian xử lý tương đối dài để hình thành một thế hệ trong mỗi nhóm và thỉnh thoảng mới trao
đổi cá thể. Nhóm mô hình này được gọi là GA phân tán vì thường thực hiện theo kiểu phân tán bộ nhớ.
Trong trường hợp phương pháp di truyền song song mịn, số nhóm được chia từ quần thể lớn và yêu cầu
số lượng các bộ vi xử lý nhiều. Liên lạc giữa các nhóm được thực hiện bằng cách di cư hoặc lai chéo
nhóm.
Điều quan trọng nhất là trong khi phương pháp Master - Slave không ảnh hưởng đến hành vi của
các thuật toán, thì các phương pháp chia mịn và thô thay đổi cách hoạt động của GA. Ví dụ, trong Master
- Slave, phép lựa chọn cá thể thực hiện cả quần thể, nhưng trong chia mịn và thô, phép lựa chọn chỉ xem
xét một tập con của quần thể. Ngoài ra, trong Master
Slave bất kỳ hai cá thể trong quần thể có thể giao phối, nhưng trong phương pháp chia mịn và
chia thô, sự giao phối được giới hạn trong một tập con.

3.1. Mô hình song song kiếu chủ - tớ (Master – Slave)
Trong mục này, ta sẽ xem xét các mô hình của phương pháp song song Master - Slave. Thuật
toán sử dụng một quần thể và việc đánh giá các cá thể và/hoặc áp dụng các toán tử di truyền được thực
hiện song song. Mỗi cá thể có thể cạnh tranh và giao phối với bất kỳ cá thể khác (lựa chọn và giao phối
được thực hiện toàn bộ quần thể). Mô hình xử lý song song toàn cục (Global parallel GA) xem như đại

diện của Master - Slave (Hình. 1), các Master luu trữ thông tin quần thể và các Slave đánh giá thích
nghi.
Hoạt động phổ biến nhất của mô hình là song song đánh giá độ thích nghi của từng cá thể, vì các
cá thể độc lập với phần còn lại của quần thể, và không có nhu cầu giao tiếp trong giai đoạn này. Việc
đánh giá của cá thể theo hình thức xử lý song song bằng cách gán một phần nhỏ cá thể cho mỗi bộ vi xử
lý có sẵn. Việc liên lạc chỉ xảy ra khi mỗi slave nhận tập cá thể để đánh giá và khi slave tính xong giá
trị thích nghi. Nếu thuật toán dừng và chờ đợi nhận các giá trị thích nghi cho toàn quần thể trước khi tạo
thế hệ tiếp theo, được gọi là thuật toán đồng bộ. Lúc đó, độ chính xác như một SGA, chỉ có tốc độ là
khác biệt. Tuy nhiên, nếu thực hiện kiểu không đồng bộ, thuật toán không dừng lại để chờ đợi cho bất
kỳ bộ vi xử lý chậm, nhưng kết quả không còn chính xác như một SGA. Hầu hết các thuật toán cho
trường hợp này là đồng bộ.
Các mô hình xử lý song song toàn cục không thừa hưởng lợi thế của kiến trúc máy tính, và có
thể thực hiện hiệu quả hơn bằng cách chia sẻ bộ nhớ và phân phối bộ nhớ máy tính. Với một bộ đa xử
lý chia sẻ bộ nhớ, quần thể được lưu trữ trong bộ nhớ chia sẻ và mỗi bộ xử lý con có thể đọc thông tin
cá thể được giao và ghi các kết quả đánh giá lại mà không có bất kỳ xung đột. Đối với phân phối bộ
11


nhớ, quần thể được lưu trữ trong một bộ xử lý. Điều này cần một bộ xử lý làm nhiệm vụ Master sẽ chịu
trách nhiệm gửi thông tin cá thể đến bộ vi xử lý khác (Slave) để đánh giá, thu thập các kết quả, và áp
dụng các phương pháp di truyền để tạo thế hệ tiếp theo. Số lượng cá thể giao cho bất kỳ bộ xử lý có thể
được liên tục, nhưng trong một số trường hợp có thể cần thiết để cân bằng tải tính toán giữa các bộ vi
xử lý bằng cách sử dụng một lịch trình năng động. Sau đây là một mô tả của thuật toán:
produce an initial population of individuals //Thủ tục khỏi tạo quần thể
for all individuals do in parallel // Duyệt tất cả các cá thể trong hế thống song song
evaluate the individual’s fitness // tính toán giá trị thích nghi
end parallel for
while not termination condition do // trong khi chưa đạt điều kiện dừng
select fitter individuals for reproduction// chọn cá thể thích nghi cho sinh sản produce new
individuals // gọi thủ thục tạo cá thể mới

mutate some individuals // biến đổi các thể
for all individuals do in parallel // thực hiện với tất cả cá thể
evaluate the individual’s fitness // tính giá trị thích nghi cá thể mới
end parallel for
generate a new population by inserting some new good individuals// tạo thế hệ mới từ cá thể tốt
and by discarding some old bad individuals// loại bỏ cá thể xấu
end while
PGA kiểu Master - Slave dễ thực hiện và có hiệu quả tính toán cải thiện đáng kể. Bên cạnh đó,
phương pháp này có ưu điểm là không làm thay đổi hành vi tìm kiếm của GA, vì vậy ta có thể áp dụng
trực tiếp giống như SGA.

3.2. Thuật toán di truyền song song theo cách chia mịn hay mô hình thuật
toán di truyền tế bào (Fine Grained Parallel GA – Cellular GA)
Để minh họa cho mô hình này, ta dùng cấu trúc dạng lưới, Hypercube, 2-D Mesh, 2-D Grid,...,
mỗi cá thể trong mô hình này được đặt trên một hình xuyến lớn có một hoặc hai chiều, mỗi cá nhân
chiếm một vị trí trên lưới. Mô hình này được gọi là tế bào vì sự tương đồng so với chuyển dịch của tế
bào với các quy tắc chuyển đổi ngẫu nhiên. Đánh giá thích nghi được thực hiện đồng thời cho tất cả cá
thể và lựa chọn, sinh sản và giao phối diễn ra tại cục bộ trong nhóm hoặc nhóm láng giềng. Trong lúc
thực hiện, hốc hay nhóm cá thể đồng nhất về mặt di truyền bán cô lập nổi lên trên toàn mạng lưới như
là một kết quả của việc chậm khuếch tán cá thể. Hiện tượng này được gọi là cách ly và khoảng cách là
do xác suất của sự tương tác của hai cá thể bằng một hàm suy hao nhanh về khoảng cách của họ (Hình
2.). Sau đây là mô tả thuật toán của quá trình:
for each cell j in the grid do in parallel // với mọi cá thể trên lưới
generate a random individual j // phát sinh ngẫu nhiên cá thể j
12


end parallel for
while not termination condition do // khi chưa đạt điều kiện kết thúc
for each cell j do in parallel // với mỗi tế bào trên lưới

evaluate individual j // đánh giá cá thể j
select a neighboring individual k // chọn láng giềng k
produce offspring from j and k // sản sinh cá thể mới từ j và k
assign one of the offspring to j // gán 1 cá thể con cho j
mutate j with probability pmut // tạo đột biến theo xác suất pmut
end parallel for
end while
Trong trường hợp 1-D, các phần tử tế bào có tính tập trung về một nhóm phần tử trung tâm. Việc
lựa chọn hay kết hợp thường được chọn từ nhóm láng giềng với phần tử cần xét.

3.3. Thuật toán di truyền xử lý song song bằng cách chia nhiều nhóm hay
thuật toán di truyền phân tán, chia thô (Multiple – Deme Parallel GA, Distributed
GA or Coarse Grained GA)
Thuật toán di truyền bằng các chia nhiều nhóm có khả năng tinh vi hơn, vì chúng gồm không chỉ
thực hiện trên một quần xã mà còn trao đổi cá thể (Hình 3.). Trao đổi cá thể được gọi là di cư; được điều
khiển bởi một vài thông số. Thuật toán song song theo kiểu này là rất phổ biến, nhưng để hiểu được là
điều khó khăn nhất, bởi tác động của chức năng di cư không được hiểu đầy đủ. Mô hình này đã thay đổi
cơ bản phương thức hoạt động của GA và khác nhiều so với SGA.
Thuật toán di truyền xử lý song song bằng cách chia nhiều nhóm được biết đến với nhiều tên
gọi khác nhau. Điển hình như thuật toán di truyền phân tán (DGA), bởi vì thuật toán thường được thực
hiện trên bộ nhớ phân tán trên máy tính. Hoặc xét về tỷ lệ tính toán cao, thuật toán thỉnh thoảng được
gọi là Thuật toán di truyền xử lý song song bằng cách chia thô. Cuối cùng, thuật toán hoạt động đa nhóm
giống với “mô hình đảo” trong Di truyền học dân số, do đó thuật toán còn được gọi là di truyền song
song theo hình thức đảo. Vì kích thước của nhóm nhỏ hơn quần thể so với sử dụng bởi một GA tuần tự,
thuật toán GA song song sẽ hội tụ nhanh hơn.

13


Hình 2. Sơ đồ của di truyền song song theo cách chia mịn.


Hình 3. Sơ đồ của Thuật toán di truyền xử lý song song bằng cách chia nhiều nhóm hay thuật toán di
truyền phân tán, chia thô
Các đặc tính quan trọng của mô hình song song với nhiều nhóm này là việc sử dụng một vài
quần xã tương đối lớn và di cư. Đối mô hình đảo đặc trưng khoảng cách địa lý các quần thể con kích
thước tương đối lớn. Các quần thể con có thể trao đổi thông tin theo thời gian bằng cách cho phép một
số cá thể để di chuyển giữa các tiểu quần thể khác nhau. Tư tưởng chính cho cách tiếp cận này là định
kỳ tạo sự đa dạng vào các quần thể con để tránh hội tự sớm hoặc không hội tụ. Khi di chuyển cá thể diễn
ra giữa quần xã láng giềng gần nhất của mô hình được gọi là bước đệm. Trong khi mỗi tiểu quần thể
một thuật toán di truyền tuần tự chuẩn được thực hiện ở giai đoạn di cư. Một số cấu trúc liên kết di cư
đã được sử dụng: các cấu trúc vòng, 2-d và 3-d lưới, hình khối hyper và đồ thị ngẫu nhiên là phổ biến
nhất. Sau đây là một mô tả thuật toán của quá trình:
initialize P subpopulations of size N each // Tạo P quần thể con với kích thước N generation number =
1 // Gán thế hệ = 1
while not termination condition do// Trong khi chưa thỏa kiều kiện dừng
for each subpopulation do in parallel// Xét các quần thể con
evaluate and select individuals by fitness// Đánh giá và lựa chọn các thể theo hàm
thích nghi

14


if generation number mod frequency = 0 then// Nếu đạt ngưỡng di cư thì trao đổi
K cá thể
send Kindividuals from a neighboring population replace K individuals in the
subpopulation
endif
produce new individuals // Gọi hàm khởi tạo thế hệ mới
mutate individuals// Đột biến

end parallel for
generation number = generation number +1// Tăng biến thế hệ
end while
Trong đó frequency là tham số thực hiện cuộc trao đổi diễn ra.

3.4. Các thuật toán song song thứ bậc (Hierarchical Parallel Algorithms)
Phương pháp cuối cùng của thuật toán song song là kết hợp các phương pháp di truyền song
song lại với nhau hay còn gọi thuật toán song song thứ bậc, bởi vì khi vận dụng có tính phức tạp và yêu
cầu kỹ thuật phối hợp thuật toán ở 2 mức khác nhau và hi vọng nó hứa hẹn hiệu suất tốt hơn khi sử dụng
đơn lẻ.
Trên lý thuyết có thể phối hợp các phương pháp trên lại thành một thuật toán hoàn chỉnh. Tuy
nhiên, các nghiên cứu có thể đạt được ở các mức phối hợp nhu sau: Kết hợp mô hình xử lý song song
nhiều nhóm (mức cao) và xử lý song song bằng cách chia mịn (mức thấp) (Hình 4.); xử lý Master –
Slave (mức cao) và mô hình xử lý bằng cách chia nhiều nhóm (mức thấp) (Hình 5) hay xử lý song song
bằng cách chia nhiều nhóm ở 2 mức (Hình 6.)

15


Hình 4. Sơ đồ kết hợp mô hình xử lý song song nhiều nhóm (mức cao) và xử lý song song bằng cách
chia mịn (mức thấp)

Hình 5. Sơ đồ xử lý Master – Slave (mức cao) và mô hình xử lý bằng cách chia nhiều nhóm (mức thấp)

Hình 6. Sơ đồ kết hợp xử lý song song bằng cách chia nhiều nhóm ở 2 mức
Bảng 1. Bảng so sánh các phương pháp song song hóa giải thuật di truyền

Mô hình

Global Parallel (Mô

Coarse – Grained (Mô

Fined – Grained

hình chủ tớ)

hình chia thô)

(Mô hình chia mịn)

Tiêu chí
Cấu trúc thuật

Không phá vỡ cấu trúc

Phá vỡ cấu trúc thuật toán

Phá vỡ cấu trúc thuật

toán
Quần thể

thuật toán tuần tự.
Thuật toán chỉ thực

tuần tự.
Quần thể ban đầu được

toán tuần tự.

Quần thể ban đầu

hiện trên một quần thể.

chia thành nhiều quần thể

được chia thành nhiều

con nhỏ tương đối tiến hóa

quần thể rất nhỏ.

độc lập.
16


Thời gian thực

Thời gian cải thiện độ

Cải thiện độ thích nghi trung

hiện

thích nghi trung bình

bình trong các quần thể con

và giá trị của nó tương

nhanh hơn, nhưng dừng lại ở

tự như giải thuật tuần

giá trị nhỏ hơn so với giải

Mối tương quan

Không phát sinh thêm

Có sử dụng các hàm di trú

Các quần thể con rất

các quần thể

các hàm di trú.

để gởi các cá thể tốt nhất

nhỏ liên lạc với mật

trong các quần thể con cho

độ cao.

master. Master lại chọn lọc
lại các cá thể tốt nhất trong
các cá thể gởi lên đó, rồi gởi
Phương

thức sinh
sản

Chọn lọc, lai tạo, đột

cho toàn
slave.
Chọn
lọc,bộlaicác
tạo,
đột biến

Chọn lọc, lai tạo, đột

biến diễn ra trên toàn

diễn ra trên các quần thể

biến diễn ra trên các

bộ quần thể.

con độc lập.

quần thể con và các

quần thể láng
giềng với nó.
Ứng dụng thuật

Áp dụng cho các bài

Áp dụng cho bài toán

Áp dụng cho bài toán

toán

Genetic có tác vụ tính

Genetic lớn, các tác vụ

Genetic lớn, các tác

độ thích nghi tiêu tốn

gene và tác vụ tính độ thích vụ gene tiêu tốn nhiều

nhiều thời gian.

nghi tiêu tốn thời gian

thời gian.

Mô hình hóa cấu

Không đòi hỏi

Không đòi hỏi topology

Đòi

trúc

topology mạng phức

mạng phức tạp.

Kết quả

tạp.
Chất lượng kết quả

Chất lượng kết quả không

như thuật toán tuần tự.

tốt bằng giải thuật tuần tự.

hỏi
topology mạng

phức tạp.

Bảng 2. Bảng so sánh về phương thức thực hiện của giải thuật di truyền song song

Fined – Grained (Mô hình chia mịn)
Coarse – Grained

Phương

(Mô hình chia thô)

Cá thể

Đánh giá thích nghi

Thuật toán di truyền

Dùng thuật toán di truyền

Dùng mô hình thuật

thức đồng dùng mô hình đảo
bộ
Phương
thức

kiểu tế bào, đồng nhất việc toán di truyền Master
tạo ngẫu nhiên các tế bào

- Slave

Thuật toán di truyền

Phát sinh tế bào theo kiểu

Dùng mô hình thuật

dùng mô hình đảo

không đồng nhất

toán di truyền Master

không đồng bộ

- Slave
17


CHƯƠNG 4: THUẬT TOÁN DI TRUYỀN DẠNG LAI (HYBRID GENETIC
ALGORITHM - HGA)
Thuật toán di truyền dạng lai đã được thiết kế bằng cách kết hợp một biến thể lai ghép một thuật
toán di truyền hiện với một phương thức sử dụng theo dạng heuristic. Heuristic có thể vận dụng cho việc
tạo dân số ban đầu; trong áp dụng cho việc tạo thế hệ con cháu bằng cách chéo hoặc xáo trộn.
Hybrid Genetic Algorithm trong phần này được thiết kế để sử dụng cho việc áp dụng heuristic
vào Khởi tạo dân số và cải tiến vấn đề lai ghép cho bài toán du lịch (Traveling Salesman Problem TSP). Thuật toán vận dụng Heuristic vào khởi tạo bằng cách khởi tạo một bộ phận dân cư và phần còn
lại sẽ khởi tạo ngẫu nhiên. Các thế hệ kế tiếp thu được bằng chéo giữa hai cha mẹ được lựa chọn ngẫu
nhiên. Thuật toán được cải tiến với 02 thủ tục: RemoveSharp (loại bớt sự gia tăng chi phí) và LocalOpt
(sắp xếp để tìm đường đi có chi phí thấp) để tạo các cá thể con đạt mức tối thiểu của địa phương. Nếu
chi phí của cá thể con thu được ít hơn so với chi phí của bất kỳ một trong cha hoặc mẹ thì cá thể cha
hoặc mẹ đó được lấy ra khỏi quần thể và thêm cá thể con vào. Ngược lại, cá thể con bị loại bỏ. Đối với
lai ghép, mỗi vòng sẽ phát sinh một số ngẫu nhiên và nếu nhỏ hơn xác suất quy định thì việc sản sinh
thế hệ mới tiến hành.
Các thuật toán làm việc như dưới đây:
Bước 1:
Khởi tạo một bộ phận dân cư sử dụng bằng thủ tục InitializationHeuristics
Khởi tạo còn lại một phần của dân số ngẫu nhiên
Bước 2:

Áp dụng thủ tục RemoveSharp cho tất cả cá thể ban đầu
Áp dụng thủ tục LocalOpt cho tất cả cá thể ban đầu
Bước 3:
Chọn ngẫu nhiên hai cha mẹ
Áp dụng lai ghép giữa cha mẹ và tạo ra cá thể con
Áp dụng thủ tục RemoveSharp cho con cái
Áp dụng thủ tục LocalOpt cho con cái
Nếu TourCost (cá thể con) phụ huynh yếu bởi con đẻ
Bước 4:
Xáo trộn bất kỳ một tour du lịch lựa chọn ngẫu nhiên từ dân số Bước 5:
Lặp lại các bước 3 và 4 cho đến khi kết thúc số quy định của lần lặp lại.

18


4.1. Lai ghép chéo (Crossover)
Phương thức lai ghép chéo được sử dụng ở đây do Darrell Whitley đưa ra và là
một biến thể phương thức lai thông thường. Phương thức lai ghéo chéo này sử dụng một
“bản đồ cạnh” (edge map) để xây dựng một cá thể con mà kế thừa càng nhiều thông tin
càng tốt từ các cấu trúc của cha mẹ. Bản đồ này lưu trữ thông tin về tất cả các kết nối dẫn
vào và ra của một thành phố của bài toán. Do đó khoảng cách 2 đỉnh hay 1 cạnh là khoảng
cách giữa hai thành phố, mỗi thành phố sẽ có ít nhất hai và tối đa bốn cạnh (trong đó có
hai từ bố mẹ) giao nhau. Thuật toán là như sau:
Bước 1:
Chọn điểm ban đầu từ một trong hai đường đi của cha mẹ (có thể từ bước 4
bằng cách tạo ngẫu nhiên”. Đặt tên là “điểm hiện tại”.
Bước 2:
Hủy bỏ tất cả các lần xuất hiện của “điểm hiện tại” từ phía bên trái trong
danh sách các cạnh bản đồ.

Bước 3:
Nếu là “điểm hiện tại” có trong danh sách các cạnh (edgelist) của nó đi đến
bước 4 xử lý; nếu không, hãy đến bước 5.
Bước 4:
Xác định thành phố trong edgelist của “điểm hiện tại”, có cạnh ngắn nhất
với “điểm hiện tại”. Các thành phố với sự cạnh ngắn nhất được bao gồm trong tour
thành phố này trở thành “điểm hiện tại”. Dừng việc tạo ngẫu nhiên và đến bước 2.
Bước 5:
Nếu không còn thành phố chưa đến, sau đó DỪNG. Nếu không, ngẫu nhiên
chọn một thành phố chưa đến đi đến bước 2.
Sự khác biệt giữa thuật toán lai chéo của Darrell Whitley và thuật toán chuẩn là chỉ
trong bước thứ tư. Ông chọn thành phố với ít nhất cạnh đến các thành phố kế tiếp, trong
khi thông thường thì chọn thành phố gần nhất đến các thành phố hiện nay, điều này cho
thấy vận dụng heuristic trong lai chéo.
4.2. Khởi tạo theo hướng Heuristic
Thủ tục InitializationHeuristics (IH) được áp dụng trong TSP theo ý tưởng chính sau: Dùng thuật
toán tham lam để khởi tạo quần thể và cách sắp xếp thứ tự các thành phố phụ thuộc vào tọa độ x và y
19


của nó. Các tour du lịch được đại diện bằng danh sách kết nối với nhau. Danh sách ban đầu được lấy
theo thứ tự đầu vào InputList (danh sách nhập). Các danh sách kết nối đó thu được sau khi áp dụng
heuristic là OutputList. Trong khi quá trình đó áp dụng heuristic cho tất cả các thành phố trong InputList
sẽ được di chuyển từng một đỉnh một vào OutputList. Thuật toán cho TSP là như sau:
Bước 1:
Chọn bốn thành phố, có tọa độ x, y mang giá trị lớn nhất và nhỏ nhất và chuyển vào
OutputList từ InputList
Bước 2:
Từ các trình tự di chuyển có thể có của bốn thành phố, ta tìm chuỗi có chi phí tối thiểu
và thay đổi trình tự của bốn thành phố trong OutputList đến trình tự có mức tối thiểu.

Bước 3:
Chọn ngẫu nhiên một đỉnh còn lại trong Inputlist.
Bước 4:
Loại bỏ các đỉnh phía trước của InputList và chèn vào OutputList ở vị trí mà sự gia tăng
trong chi phí tour du lịch là tối thiểu. Giả sử M là chi phí của các tour du lịch trước khi chèn và
N là chi phí của chuyến đi sau khi chèn. Các vị trí chèn được lựa chọn như vậy mà NM là tối
thiểu.
Bước 5:
Lặp lại bước 4 cho đến khi tất cả các đỉnh trong InputList được chuyển đến các
OutputList. Tùy thuộc vào các tiêu chí phân loại trong Bước 3 kết quả được lấy sẽ khác nhau.
Áp dụng heuristic cho RemoveSharp và LocalOpt ta thu được cá thể con thêm vào bộ dân số ban
đầu.

4.3. Thủ tục RemoveSharp
Thủ tục RemoveSharp nhằm loại bỏ sự tăng mạnh mẽ trong chi phí tour do một thành phố bị
xem là cá thể xấu. Thủ tục trải qua các bước dưới đây:
Bước 1:
Một danh sách (NEARLIST) chứa m thành phố gần nhất đến một thành phố đã chọn.
Bước 2:
RemoveSharp loại bỏ thành phố được lựa chọn từ các tour du lịch và tạo thành một tour
du lịch với N - 1cities.
Bước 3:
Bây giờ các thành phố được chọn sẽ được lồng vào trong tour trước hoặc sau khi bất kỳ
một của thành phố ở NEARLIST và chi phí của các tour du lịch mới được tính cho mỗi trường
hợp.
Bước 4:
20


Theo trình tự đó, chi phí thấp nhất sẽ được chọn.

Bước 5:
Các bước trên được lặp lại cho mỗi thành phố trong tour

4.4. Thủ tục LocalOpt
Thuật toán LocalOpt sẽ chọn q thành phố liên tiếp (Sp + 0, Sp + 1,....., Sp + q-1) từ các tour du
lịch và nó sắp xếp các thành phố Sp + 1, Sp + 2,. . . . , Sp + q-2 trong một theo cách đó khoảng cách tối
thiểu là giữa các thành phố Sp + 0 và Sp + q-1 bằng cách tìm kiếm tất cả các thỏa thuận có thể. Giá trị
của p thay đổi từ 0 đến n-q, trong đó n là số của thành phố.

4.5. Độ phức tạp của các thủ tục RemoveSharp và LocalOpt
4.5.1. Độ phức tạp của các thủ tục RemoveSharp
Như đã thảo luận ở bước 2 của thủ tục, khi một thành phố được loại bỏ trong quá RemoveSharp
sẽ có sự sụt giảm trong chi phí tour. Giả sử trình tự của các thành phố được - - -P - C - N - - - - - - - AP
- A - AN - - - C là thành phố phải được loại bỏ để thực hiện RemoveSharp. Ví dụ P là thành phố trước
khi đến thành phố C và N thành phố bên cạnh nó. RemoveSharp sẽ di chuyển các thành phố C đến mới
vị trí, nếu độ tăng chiều dài chuyến đi sau khi di chuyển đến vị trí mới là ít hơn so với việc giảm chi phí
do loại bỏ từ vị trí giữa P và N. Nếu thành phố A là trong danh sách gần đó, RemoveSharp sẽ kiểm tra
khả năng chuyển đến các địa điểm trước A (như AP) và sau A (tức là AN). Việc giảm chiều dài tour du
lịch sẽ là:
DECREASE = Khoảng cách (P, C) + Khoảng cách (C, N) – Khoảng cách (P, N) Nếu C được di
chuyển đến vị trí trước đến A (ví dụ AP), tăng chi phí tour sẽ là: INCREASEP = Khoảng cách (AP, C)
+ Khoảng cách (C, A) - Khoảng cách (AP, A) Nếu C là di chuyển vị trí bên cạnh A tức là AN tăng trong
chi phí tour sẽ là: INCREASEN = Khoảng cách (A, C) + Khoảng cách (C, AN) - Khoảng cách (A, AN)
Khi áp dụng RemoveSharp, DECREASE được tính một lần, trong khi INCREASEN và
INCREASEP được tính cho mỗi thành phố trong NEARLIST. Phức tạp thời gian cho DECREASE,
INCREASEN và INCREASEP là như nhau và để cho nó được x. INCREASEN và INCREASEP nên
được so sánh với DECREASE cho mỗi thành phố trong các NEARLIST.
Nếu y là thời gian thực hiện cho một so sánh. Tất cả những tính toán cần phải được thực hiện
cho tất cả các thành phố trong tour.
Thời gian thực hiện với RemoveSharp = n * (x + 2m * x + 2m * y)

Ở đây, m là kích thước của NERALIST, x được thời gian cho DECREASE, INCREASEN và
INCREASEP và y thời gian thực hiện để so sánh là các hằng số. Do đó, Độ phức tạp đối với thủ tục
RemoveSharp là O (n)

21


4.5.2. Độ phức tạp của các thủ tục LocalOpt
Độ phức tạp của LocalOpt thay đổi theo giá trị của q, số liên tiếp thành phố thực hiện cho
LocalOpt tại một thời điểm. Khi sắp xếp q thành phố theo một trình tự được kết hợp từ q-2 thành phố
xen giữa.
Ta có (q-2)! bộ kết hợp, trong đó mỗi trường hợp có q-1 bổ sung để thực hiện đánh giá chi phí
trình tự và một so sánh để kiểm tra xem chuỗi là tối thiểu hay không.
Do đó, chuỗi n liên tiếp của các thành phố q có độ phức tạp của LocalOpt là n * (((q-2)! * (q-1))
(phép bổ sung) + (q-2)! (phép so sánh)
Trong đó: n là một biến.
Xét với q nhỏ (q≤6) thì độ phúc tạp của LocalOpt là O(n)

22


CHƯƠNG 5: THUẬT TOÁN DI TRUYỀN THÍCH NGHI (ADAPTIVE GENETIC
ALGORITHM-AGA)
Các thuật toán di truyền thích nghi (AGA) là thuật toán di truyền cho phép các tham số thay đổi,
chẳng hạn như quy mô dân số, xác suất lai ghép, hay xác suất đột biến,… trong quá trình GA chạy thực
hiện.
Một biến thể đơn giản như sau: Tỷ lệ đột biến có thể thay đổi theo quy mô dân số; có thể tăng
khi quy mô dân số tăng và ngược lại, giảm ngay sau khi một sự cải tiến của dân số xảy ra. Thuật toán
tiến hành như sau:
Bước 1:

Khởi tạo dân số ban đầu
Tạo dân số bằng hệ số ngẫu nhiên
Bước 2:
Thực hiện di truyền
Lựa chọn: tạo chiến lược trong không gian lấy mẫu mở rộng
Lai ghép: Có thứ tự ưu tiên trong lai ghép
Đột biến: Tìm kiếm và cho đột biến có tính chất cục bộ
Bước 3:
Áp dụng tìm kiếm cục bộ và lặp lại theo phương pháp leo đồi
Bước 4:
Áp dụng heuristic cho việc tinh chỉnh thông số GA (các giá lai ghép và các đột biến).
Bước 5:
Dừng điều kiện
Nếu số thế hệ đạt tối đa hoặc xác định được một giải pháp tối ưu sau đó dừng lại; nếu
không, chuyển sang Bước 2.
Khác với SGA, các tham số xác xuất lai ghép pc và xác suất đột biến pm cố định, thuật toán này
cho phép tự động thay đổi 02 tham số pc và pm bằng cách vận dụng heuristic để thuật toán có tính thích
nghi và cho kết quả tốt hơn.

5.1. Khởi tạo
Xác định số nguyên H là số nhiễm sắc thể của quần thể ngẫu nhiên ban đầu, và ta có thể áp dụng
dạng mã hóa số thực. Mỗi nhiễm sắc thể bao gồm n gen. Xem xét các thiết lập bởi hàm sau:
Trong đó xi…x là các giá trị gen, (ui, wi) là miền giá trị tương ứng xi

23


Hàm tạo ra số ngẫu nhiên từ Ω và kiểm tra tính khả thi của nó. Nếu nó là khả thi thì là một thành
viên của dân số ban đầu, nếu không, chúng ta tạo một số ngẫu nhiên khác từ Ω cho đến khi có được giải
pháp khả thi. Khi số mẫu đạt mức hữu hạn, thì ta có H nhiễm sắc thể khả thi ban đầu.

5.2. Hàm đánh giá
Thông qua hàm đánh giá eval (V), ta thiết lập được xác suất cho mỗi nhiễm sắc thể V, do đó xác
suất lựa chọn có tỷ lệ thuận với độ thích nghi của nó. Bằng cách lựa chọn bánh xe roulette, nhiễm sắc
thể có một giá trị thích nghi cao có một cơ hội cao để được lựa chọn nhằm tạo ra các cá thể con cho các
thế hệ tiếp theo. Để đánh giá tốt xấu, ta thiết lập α ∈ (0,1) và xác định hàm đánh giá như sau:

5.3. Hàm lựa chọn
Việc lựa chọn được tạo theo các bước sau, có thể xem như một giải pháp mở rộng của vòng tròn
roulette.
Bước 1: Theo các quy tắc mà hàm lựa chọn quy định lựa chọn thể với một xác suất tương ứng
với độ thích nghi. NST với độ thích nghi cao sẽ được lựa chọn để tạo ra các thể con cho thế hệ tiếp, hai
cá nhân được lựa chọn, gọi cha mẹ. Ta xác định xác suất sinh sản cho vj (k).

j = 1 có nghĩa là nhiễm sắc thể tốt nhất và j = H có nghĩa là nhiễm sắc thể xấu nhất.
Bước 2: Đối với vj (k), j = 1, 2, Λ, H tính toán xác suất qj:

Bước 3: Tạo số ngẫu nhiên r(0, qH). Nếu qj-1 j = 1,2,..H
Bước 4: Lặp lại bước 2 và bước 3, ta có thể có được H nhiễm sắc thể sao chép, xác định bởi

24