r í s '
r\hỉ
JQ' '■
ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CÔNG NGHỆ
ĐỖ THỊ MINH HUỜNG
ỨNG DỤNG
PHƯƠNG PHÁP TÍNH TOÁN TIẾN HOÁ
ĐỂ GIẢI BÀI TOÁN
LẬP LỊCH GIA CÔNG CHI TIÊT MÁY
Chuyên ngành: Công nghệ thông tin
Ma số : 01.01.10
LUẬN VĂN THẠC s ĩ
Người hướng dẫn khoa học
TIẾN Sĩ HOÀNG XUÂN HUẤN
Hà Nội - Năm 2002
MỤC LỤC
Mở đẩu ị
Chương 1 Thuật toán di truyền và tính toán tiến hoá

3
1.1.Sơ lược về lịch sử 3
1.2.Thuật toán di truyền cổ điển 4
1.2.1.Cấu trúc của thuật toán di truyền cổ điển
4
1.2.2.Cơ sở toán học của thuật toán di truyền cổ điển 7
1.2.2.1 .Khái niệm lược đồ 7
1.2.2.2. Tính chất của lược đồ 8
1.2.2.3. Mối quan hộ giữa lược đồ và quá trình tiến hoá của thuật toán di truyền
cổ điển 9
1.2.3.So sánh thuật toán di truyền cổ điển với một số thuật toán truyền thống

3.1 .Mô hình của bài toán 45
3.2.Mô tả thuật toán cho bài toán

.

46
3.3.Lược đồ tính toán tiến hoá 47
3.3.1. Mã hoá 47
3.3.2.Cấu trúc nhiễm sắc thể và kiểu gien 43
3.3.3.Khởi tạo quần thổ ban đầu

48
3.3.4.Xác định hàm thích nghi 49
3.3.5.Quá trình tiến hoá 50
Chương 4 Thiết kế phần mềm 53
4.1.Cách xAy dựng phần mềm 53
4.1.1 .Sơ đồ phân cấp chức năng 53
4.1.2.Chức năng 1: Nhập tên tệp dữ liệu cho bài toán 53
4.1.3.Chức năng 2: Nhập tham số khởi tạo 54
4.1.4.Chức năng 3:Tìm qui trình gia công 55
4.1.5.Chức năng 4:Võ sơ đồ qui trình tối ưu
59
4.1.6.Chức năng 5: Thoát khỏi chương trìn h 60
4.2.Kết quả chạy kiểm tra trên một số tệp dữ liệu 60
4.2.1.Tệpdll.lx t 60
4.2.2.Tệp dl2.txt 62
4.2.3.Tệp dl3.txt 63
Kết luận 65
Tài liệu tham khảo 66
n v ' 9

dể thiết kế phần mềm cho bài toán lập lịch gia công chi tiết máy.
Bố cục của luận văn gồm 4 chương như sau:
Chương 1: Thuật toán di truyền và tính toán tiến hoá
Giới thiệu tóm tắt phương pháp tính toán tiến hoá: bắt đầu từ giải thuật di
truyền cổ điển đến sự phát triển hiện thời và tính toán tiến hoá. Đồng thời luận
văn cũng nêu những mặt mạnh, yếu của nó và so sánh với thuật toán di truyền
cổ điển.
Chương 2: Bài toán lập lịch gia công chi tiết máy và các phương
pháp giải truyền thống.
Phái biểu bài toán và đặc điểm giải bài toán. Trình bày phương pháp giải
Ihông dụng truyền thống Johnson, đồng thời có minh hoạ bằng ví dụ.
Chương 3: ứng dụng thuật toán tiến hon để giải bài toán lập lịch gia
công chỉ tiết máy.
'ìỉn r/ rỉtm r r /i/irỉo 'Ịịf/ /lỉ iá / i ỊÓịJị_ (c á n fir'll /in á rỉ? r /iả i t à i /d á n /â /i íir h ợ in cônr/ r / i i ỉiê l m á i/
2
Trong chương này, tác giả trình bày việc áp đụng phương pháp tiến hoá
cho bài toán lập lịch gia công chi tiết máy.
Trước hết, tác giả phân tích bài toán để tìm ra cách mã hoá (cách biểu
diễn nhiễm sắc thể) sao cho tự nhiên, dễ hiểu, dễ thao tác. Tiếp theo là các
toán tử di truyền được dùng cho bài toán. Luận văn cũng đưa ra cách khởi tạo
quẩn thể ban đầu và thuật toán tiến hoá (trong các phần này đều có ví dụ minh
hoạ).
Chương 4: Thiết kế phần mềm.
Trình bày việc thiết kế phàn mềm bằng ngôn ngữ PASCAL. Tác giả cũng
ncu rõ các giao diện trong phần mềm, cách sử dụng các giao diện và các chức
năng của phần mềm.
Phần mềm này đã được chạy và kiểm tra trên một số tệp dữ liệu thực. Kết
quả cho tương đối khả quan. Các kết quả chạy thử được đưa vào cuối chương
để xem xét và đánh giá.
ỉ/nff

'ìíiư / r ỉm ự / / ị Ỉ! t ỜỈỊ Ị r/ /i / i á / i ỉ ín /t /c ó n t iê n ỉ to n tlô r/iả ì /ĩà i /n á n (â /i ỉi r ỉi r/ia c â u f/ c/ứ_ /i r ? m á Ị/
4
1.2. Thuật toán di truyền cổ điển
Thuậl toán di truyền cổ điển là các kỹ thuật phỏng Iheo quá trình tiến hoá
tự thích nghi của các quần thể sinh học dựa trên học thuyết Darwin.
Tư tưởng của thuật toán di truyền cổ điển là làm theo tự nhiên. Thuật
toán di truyền cổ điển và sự tiến hoá tự nhiên có cùng một nguyên lý. Trong
sự tiến hoá tự nhiên, mỗi loài sinh vật đều phải tìm cách thích nghi tốt nhất với
một môi trường sống phức tạp luôn luôn thay đổi. Sự thích nghi đó dược đúc
kết và ghi lại trong cấu trúc nhiễm sắc thể của chúng. Rõ ràng, những sinh vật
thuộc thế hệ sau được sinh ra (tính trung bình) sẽ thích nghi với môi trường
tốt hơn thế hệ cha, mẹ chúng. Thuật toán di truyền cổ điển được bắt chước
lương tự như sự tiến hoá tự nhiên.
1.2.1. Cấu trúc của thuật toán di truyền cổ điển
Thuật toán đi truyền cổ điển được J.H.Holland giới thiệu để giải bài toán
tối ưu:
Ị ìnax f(x) / xeM Ị, trong đó M là hình hộp írong không gian số thực n
chiều, f(x) dương với mọi xeM.
• Cấu trúc nhiễm sắc thể và kiêu gien
Trong GA cổ điển, mỗi X trong M được mã hoá bởi một chuỗi nhị phíìn
độ dài m: z = (Z|, Z2 , zm) gọi là nhiễm sắc thể-viết tắt là NST (hay còn gọi là
cá thể), mỗi Zj được gọi là một gien và chỉ nhận một trong hai giá trị 1 hoặc 0.
Ví dụ về một NST trong GA cổ điển:
1 1 0 0 1 0 1
0 0
1
Mỏi kiểu gien (tức là một NST cụ thể) biểu thị một lời giải có thể của
bài toán, một quá trình tiến hoá được thực hiện trên một quần thể (một tập hợp
NST) tương dương với sự tìm kiếm trong một không gian các lời giải có thể.
'ÌỈỊH/ ( /m ư / ịilu ừ ìiự / / i/i á /i /in h /c á n /tr u / ị n ó r/ô {/¡ải /<ài /n ó n lâ /i /ích r/ia r ô ìtợ c /t i /¡ r ì m á i/

Ihich nghi". Mot tap lofi giai mod diroc xay dung (vong lap thu t+1) bang cach
"chon loc" cac ca the Ihich nghi hon ta duoc tap ldi giai trung gian. San do
mot so ca the trong tap loi giai da duoc chon bi bie'n d6i bang phtrong phap
"lai ghep" va "dot bien" de tao thanh cac ldi giai mcfi cho thcihe thur t+1.
• Phep chon loc
Phep chon loc la mot qua trinh chon cac ca the de tham gia vao cac pha
tiep theo cua qua trinh tien hoa. Viec lira chon cac ca th£ tir mot qu&i the dua
tren do thich nghi cua ca the do, nghia la nhirng ca the nao co gia tri ham thich
nghi cao co nhieu kha nang duoc chon d^ tai tao trong cac the he ti6p theo.
Phep chon loc co the duoc bieu di6n du6i dang mot banh xe x6 so, do la
mot hlnh tron trong do m6i ca th^ trong th€ h6 hien thcfi chie'm mot phAn
tuong ung vcfi gia tri cua ham muc tieu cua no. Cac gia tri nay chinh la cac
xac sua't chon loc cua m6i ca the v, duoc tinh theo c6ng thiic p; = eva!(Vj)/F
(trong do evaKv^ la gia tri cua ham thich nghi cua m6i cac the vi? F la tong cac
gia tri cua cac ham thich nghi cua qucin the).
• Phep trao doi cheo
Phep Irao doi cheo (con goi la phep lai ghep), ket hap cac dac tinh tren
NST cua bo va me de tao thanh hai ca the m6i bang cach trao d6i cac doan
gien tuong ung tren cac NST cua bo va me.
V6i hai NST x = (x,, x2, , xm)
va y = (y „y2v ,y m)
Chon diem tuong giao k (co the lAy ngau nhieu) ta se duoc hai NST mdi:
x* = (x ,x k, yk+„ ym)
va y’ = (y„ ,yk,x k+1, x j.
Vi du: vdi hai NST bo, me
Parent 1
1
0
1
0 1 0

Với mỗi vị trí i trong NST:
x = (x,,x2, X;, , xm)
Ta sinh ra một số thực ngẫu nhiên Pj trong [0,1]. Sau phép đột biến ta
được NST mới:
x' = (x'„ x'2, x’J
Xi
1 - X :
Trong đó Xị'
nếu p, > pr
nếu Pi < p,
1.2.2. Cơ sở toán học của thuật toán di truyền cổ điển
Cơ sở lý thuyết của thuật toán di truyền cổ điển dựa trên biểu diễn chuỗi
nhị phân và khái niệm lược dồ.
Khái niệm lược đồ là một khái niệm quan trọng trong việc biểu diễn các
cá thể có những thuộc tính giống nhau. Sự phát triển hay suy tàn của các cá
thể đều được lý giải một cách khoa học trong lý thuyết lược đồ. Đây cũng
chính là sự lý giải cho tính hiệu quả của GA cổ điển mà chủ yếu là thông qua
các phép: chọn lọc, lai ghép và đột biến.
I.2.2.I. Khái niệm lược đồ
Một lược đồ được xây dựng bằng cách bổ sung các ký hiệu không quan
tâm vào bộ ký tự của gien. Một lược đồ đại diện cho tất cả các chuỗi mà
mọi vị trí (trừ các vị trí "*") đều giống nó.
ẩ ữ ỳ / tt r / ịt ỉ ttM ự / /ih á / i / ín /t /c á n /ic n fw á (ĩ? r /iả i f-à i /o á n ỉâ/< (icỈỊ r/ia rô n ợ r / t i / i ê ĩ )ỊinỊẨ'
8
Trường hợp đặc biệt:
Lược đồ (01011100) chỉ đại diện cho duy nhất một chuỗi (01011100).
Lược đồ (********) đại diện cho mọi chuỗi có độ đài 8.
Rõ ràng, mỗi lược đồ đều đại diện cho 2r chuỗi, trong đó r là số các ký tự
không quan tâm ở trong lược đồ đó. Ngược lại, mỗi chuỗi có độ dài m có
thể phù hợp với 2m lược đồ khác nhau.

một lược đồ khi trao đổi chéo.
1.2.2.3. Mối quan hệ giữa lược đồ và quá trình tiến hoá của
thuật toán dỉ truyền cổ điển
Trong cấu trúc của thuật toán di truyền cổ điển, quá trình giả lập tiến hoá
được lặp bốn bước sau:
l.t <-t+l
2. Chọn P(t) từ P(t+1)
3. Thay đổi P(t)
4. Đánh giá P(t)
Ta thấy:
- Bước ( t <— t+1 ) chỉ có tác dụng tăng đồng hồ tiến hoá lên một nhịp.
- Bước (đánh giá P(t)) chỉ đánh giá quần thể hiện hành.
Như vậy, hoạt động chủ yếu của quá trình tiến hoá xảy ra trong hai bước
còn lại của chu kỳ tiến hoá, đó là: chọn lọc P(t) và thay đổi P(t), hai bước này
tương đương với việc thực hiện ba phép: chọn lọc, lai ghép và đột biến của
thuật toán di truyền. Chúng ta sẽ xem xét sự ảnh hưởng của lược đồ tới ha
phcp trên.
//j tợ f/n n ( / /iliá /i l íì i/i /c á n /ir n ỉto á rfô t /i ả i feài foá )Ị ỉâ /i ỉir /i (fia c ô n g r ỉt i /ir í/ ỉìtá/ìf
10
• Với phép chọn lọc
Xét tập lời giải S(t) tại thế hệ thứ t của quá trình tiến hoá (ở đây ta gọi
ngắn gọn là quần thể). Ký hiệu Ç(S,t) là số các chuỗi trong tập lời giải tại thế
hệ thứ t ứng với lược đồ s (ở đây ta gọi mỗi chuỗi này là cá thể). Ta cần xác
định £,(S,t+l) là số các cá Ihể trong quần thể tại thế hệ thứ t+1 ứng với lược đồ
s.
Ta ký hiệu eval(S,t) là độ thích nghi của lược đồ tại thế hệ thứ t và nó
được tính theo công thức sau:
eval(S,t)=£eval(v¡j)/p ( i=l pop_size; j=l p).
Trong đó p là số cá thể trong quần thể ứng với lược đồ s tại thế hộ thứ t.
Mỗi cá thể được chọn lọc ra để thực hiện phép tái sinh với xác

Trong khi đó, lược đồ S2 bị loại bỏ, tức là không có cá thể con nào phù
hợp với lược đồ này, vì các vị trí xác định của lược đồ s2 nằm ở hai đầu của
điểm bắt chéo và do vậy chúng bị tách ra và đặt vào hai cá thể con khác nhau.
Nhận xét về các yếu tố ảnh hưởng đến sự loại bỏ một lược đồ:
- Độ dài xác định của lược đồ đóng vai trò quan trọng đối với sự tồn tại
và sự loại bỏ của một lược đồ. Độ dài xác định 5(S) càng lớn thì nguy cơ lược
đồ bị loại bỏ càng cao.
- Điểm bắt chéo được chọn ngẫu nhiên trong (m-1) vị trí (m là độ dài
của chuỗi nhị phân biểu diễn cá thể) nên xác suất bị loại bỏ của lược đồ s (ký
hiệu là pd(S)) còn phụ thuộc vào xác suất chọn điểm bắt chéo.
Do đó ta có: pd(S) = 5(S)/(m-1 ).
Vậy xác suất tồn tại của lược đồ s (ký hiệu là Ps(S)) là:
Ps(S)= 1 -5(S)/(m-l).
’i ím / r fm m /ih i ù ì tự / / ị h á /ị /Í ii/i /c á n /ic n /io á ftp f/in i /'-à i /ná)! /â /i ỉir /i (/in rô 1 1 Ịf r /t i ỉ iô ĩ v tá t /
12
- Xác suất trao đổi chéo pc cũng ảnh hưởng tới xác suất loại bỏ lược đồ
s, vì chỉ cổ pc số cá thể tham gia trao đổi chéo.
Kết hợp cả ba yếu tố ảnh hưởng trên ta có công thức tồn tại của lược đồ
S:
Ps(S) = 1 - Pc X ô(S)/(m-l).
- Khi điểm bắt chéo được chọn giữa các vị trí xác định của lược đồ thì
lược đồ đó vãn có một khả năng rất nhỏ tồn tại. Chẳng hạn, trong ví dụ trên,
nếu như hai chuỗi tham gia trao đổi chéo đều bắt đầu bằng "010" và kết thúc
bằng "10" thì lược đồ S2 sẽ bị loại bỏ sau khi trao đổi chéo. Nhưng khả năng
trôn xảy ra là rất nhỏ, nên công thức xác suất tồn tại lược đồ s thay đổi như
sau:
ps(S )> l-p c x8(S)/(m-l).
Sau khi trao đổi chéo, phương trình sinh trưởng của lược đồ có dạng sau:
Ç(S,t+l) > Ç(S,t) X eval(S,t)/ F(t) X [1 - pc X 8(S)/(m-l)]
(2)

toán truyền thống rất phổ biến, đó là: thuật toán “vét cạn”, thuật toán ‘leo đồi”
và thuật toán ‘luyện kim”.
Như chủng la đã biết, trong thuật toán “vét cạn” (tìm kiếm theo bề rộng
hoặc theo độ sãu), về mặt nguyên tắc các phương pháp tìm được nghiệm của
bài toán nếu bài toán có nghiệm, song trong thực tế, rất nhiều bài toán không
thể áp dụng được phương pháp này, vì ta phải phát triển một không gian trạng
thái quá lớn, trước khi đi tới trạng thái đích, mà do những hạn chế về thời gian
tính toán và dung lượng bộ nhớ, không cho phép chúng ta làm được điều đó.
Trong thuật toán ‘leo đồi” sử dụng kỹ thuật “nâng cấp lặp”, kỹ thuật này
áp đụng cho một điểm đơn (điểm hiện tại) trong không gian tìm kiếm. Trong
Ề r ỉm ụ / / ị / t r ờ i ! Ị r/ / ị h á / ị U n / ị /n á n / ¡ fin /ị n á r lô ( / i ả i ỉ ' à i / o á n ỉâ / i / i r / t g i a r â n (/ r / u ’ ỉ i ô ĩ m á t /
14
một lÀn nAiig cấp, một điổm mới dược chọn trong số các diổm lAn cận của
diểm hiện hành nếu nlnr điổm đó cho kết quả tốt hơn của hàm mục tiêu. Việc
tìm kiếm sẽ kết thúc khi không thể nâng cấp thêm được nữa. Rõ ràng thuật
toán leo đồi chỉ cho ta kếl quả tối ưu cục bộ, kết quả này phụ thuộc vào sự lựa
chọn của điểm xuất phát, mặt khác ta không có được Ihông tin sai số vẻ kết
quả tìm được so với kết quả tối ưu toàn cục.
Để khắc phục nhược điểm trên, thuật toán leo đồi đã được cải tiến bằng
cách tăng số lượng các điểm xuất phát (điểm xuất phát cho mỗi lần chạy có
thể được chọn ngẫu nhiên hoặc được chọn tuỳ theo kết quả của các lần chạy
trước). Sự thành công hay thất bại của mỗi lần chạy (cho ta kết quả tối ưu toàn
cục hay cục bộ), phụ thuộc vào sự lựa chọn điểm xuất phát và hình dáng của
"mặt cong" của hàm giá. Nếu mặt cong chỉ có một số ít cực đại địa phương thì
tối ưu toàn cục được tìm ra rất nhanh. Chính vì vậy mà kể cả sau khi đã được
cải tiến thì khả năng tìm được lời giải tốt nhất cho mỗi lần chạy cũng là rất
nhỏ.
Trong thuật toán luyện kim, người ta dùng kỹ thuật thay đổi entropy của
hệ. Ở phương pháp này người ta đã điều khiển tốc độ hội tụ của quần thể
bằng cách biến đổi nhiệt động học với một tham số nhiệt độ T toàn cục. Để

chọn P(t) từ P(l-l) được thay bằng hai bước:
+ Bước 1 : chọn r cá thể một cách độc lập (không nhất thiết khác nhau),
để cho tái tạo.
+ Bước 2: chọn r cá thể phân biệt để loại bỏ.
Việc chọn lọc trên được thực hiện dựa theo độ thích nghi của các cá thể,
các cá thể có độ thích nghi trên trung bình có nhiều khả năng được chọn để tái
lạo hơn, các cá thể có độ thích nghi dưới trung bình có khả năng được chọn để
loại bỏ cao hơn. Sau khi thực hiện hai bước trên ta có ba nhóm cá thể không
nhất thiết rời nhau trong quán thể:
'ìín r/
(filin/
/i/ii i'(U i(/ / l ỉ i á / i /i n ỉ ) / c á n ( i f ) Ị /t o á r fr
(/ini
/ t à i /o á n /ó / ị
ỉirh
r /ia
cỘỊự/ rỉti
/ i é ĩ m á t /
16
- r cá thổ (không nhất thiết khác nhau) đổ tái tạo.
- r cá thể (khác nhau) để loại bỏ.
- các cá thể còn lại (trung hoà).
Số cá thể trung hoà trong một thế hệ có từ pop_size - 2r đến pop_size-r,
luỳ thuộc vào số các cá thể cha, mẹ phân biệt được chọn và số các cá thể sinh
và tử.
Sau đó quần thể mới P(t+1) được xây dựng, gồm pop_size - r cá thể và r
cá thể con của r cá thể cha, mẹ sinh ra.
• Giải thuật modGAl
Procedure modG A1
Begin

* ưu điểm của modGAl
Tránh được có nhiều bản sao của một cá thể trong quần thổ mới (nó
có thể xảy ra nhưng rất hãn hữu). Vì vậy nó hạn chế được sự hội tụ sớm của
thuật toán GA_old.
1.2.4.2. Cải tiến về hàm mục tiêu
• Chuyển đổi hàm mục tiêu thành hàm thích nghi
ở đây các bài toán được xét đều giả thiết rằng: hàm mục tiêu có miền giá
trị thuộc tập dương và ta chỉ xét các bài toán tối ưu tìm giá trị lớn nhất của
hàm. Nhưng các bài toán đã gặp trong thực tế là đa dạng, vì vậy để giải quyết
được vấn đề này ta xél hai trường hợp sau:
+ Trường hợp I: Nếu là bài toán tối ưu yêu cẩu làm cực tiểu hàm f(x),
ta đưa về bài toán làm cực đại hàm g(x) với g(x) = -f(x). Khi đó giá trị xopl làm
cực đại hàm g(x) cũng chính là điểm làm cực tiểu hàm f(x).
J 8
+ Trường hợp 2: Nếu hàm mục tiêu f có cả giá trị âm, thì ta có thổ cộng
them một hằng số dương c nào đó sao cho f(x) có miền giá trị thuộc lập
dương.
• Phép sửa đổi hàm phù hợp theo từng bước lặp
Phương pháp sửa đổi này có liên quan đến tính chất của hàm cần được
tối ưu. Có nhiều hướng tiếp cận vấn đề này, chẳng hạn: phương pháp luyện
kim kỹ thuật Ihay đổi entropy của hệ. ở phương pháp này người ta đã điều
khiển tốc độ hội tụ của quần thể bằng cách biến đổi nhiệt động học với một
tham số nhiệt độ toàn cục.
Phương pháp được nhiều người quan tâm nhất là: biến đổi chính hàm
phù hợp, bằng cách đưa ra một phép vị tự để thay đổi hàm phù hợp.
Goldberg đã phân phép vị tự thành ba loại sau đây:
+ Phép vị tự tuyến tính:
Hàm phù hợp fj' dược sửa đổi giá trị theo công thức : f|'=a X fj + b, ỏ
đó f| là giá trị ban đầu của hàm phù hợp, a, b là các tham số.
Thường các tham số a, b phải được chọn sao cho:

thời gian và tài nguyên.
Sau đay ỉà một thuật toán đi truyền cải tiến với kích thước quần thể thay
đổi (ta gọi là mođGA2). Thuật toán này đưa ra khái niệm tuổi thọ của mộí cá
tliể - là số thế hệ mà cá thể đó tồn tại. Tuổi thọ của cá thể phụ thuộc vào độ
thích nghi của cá thể đó và nó ảnh hưởng đến kích Ihước của quán thể Irong
quá trình tiến hoá. Hướng tiếp cận phương pháp chọn lọc này có vẻ phù hợp
với quy luật của tự nhiên. Hơn nữa trong phương pháp này các cá thể con có
cơ hội cạnh tranh sinh tồn với các cá thể cha, mẹ của chúng.
y/ý/y r ỉttn ự /lỉn M iự i / 1 / 1 Ó/ 1 /Íh /ị /c á n /iô)! /ifìá fỉ(‘ ợ iả i /'à i /d á n iâ /i fir/t f/ia r e n n r /u ' fi r / lìư íự
20
Trong thuật toán này, tại thời điểm t, quẩn thể P(t) gồm có pop_size(t) cá
thể. Trong bước "tái kết hợp P(t)", một quần thể "bổ trợ mới" được xây dựng:
Auxpop_size(l) = [pop_size(t) X p], trong đó p là xác suất sinh sản.
Mọi cá thể trong quẩn thể có thể được chọn để sinh sản ra thế hệ con
(Ihực hiện trao đổi chéo và đột biến) với xác suất bằng nhau.
Tham số tuổi thọ của mỗi cá thể được gán một lần trong bước đánh giá
P(l) (sau khi khởi tạo hoặc sau bước tái kết hợp). Tham số này không thay đổi
trong suốt quá trình tiến lioá (từ lúc cá thể dược sinh ra cho đến khi bị loại
bỏ). Nếu ta gọi D(t) là số cá thể bị chết tại thế hệ t, thì kích thước của quần thể
sau vòng lặp là :
pop_siz,e(t+l) = Auxpop_size(t) + pop_size(t) - D(t)
• Nội dung của modGA2:
Procedure modGA2
Begin
t = 0
khởi tạo P(t)
đánh giá P(t)
while ( not điều_kiện_dừng ) do
begin
t= t+1