THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN VÀ PHƯƠNG PHÁP
GIẢI QUYẾT VẤN ĐỀ
Đề tài:
GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG
GVHD: PGS. TS. Đỗ Văn Nhơn
HVTH: Nguyễn Hữu Phước
MSHV: CH1301107
TP HCM, tháng 10 năm 2014
Nguyễn Hữu Phước CH1301107 Trang 1
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
LỜI NÓI ĐẦU
Ngày nay, cùng với sự phát triển mạnh mẽ của khoa học và công nghệ thì
khối lượng tri thức thu thập được ngày càng khổng lồ và cần phải được xử lý một
cách chính xác, nhanh và hiệu quả để phục vụ cho các hoạt động của xã hội.
Cũng chính từ đó, đòi hỏi phải có nhiều phương pháp (giải pháp) để giải quyết
được nhiều yêu cầu hay nhiều vấn đề đặt ra trong đời sống hàng ngày như công
tác lập lịch, tìm đường đi ngắn nhất trên bản đồ giao thông, so khớp đồ thị để ứng
dụng vào các lĩnh vực như hóa học, sinh học, điện tử, … hay nhiều vấn đề khác
đã và đang hình thành.
Những vấn đề trên đều gần giũi với đời sống hàng ngày và được nhiều nhà
nghiên cứu tìm hiểu, xây dựng nhiều giải pháp giải quyết khác nhau, tuy nhiên
vẫn chưa đạt được mong muốn vì còn một số hạn chế nhất định, ví dụ như độ
phức tạp của thuật toán quá lớn hoặc thời gian, hiệu quả chưa cao, …
Qua môn học, đặc biệt là sau quá tìm hiểu để hoàn thành bài thu hoạch do
thầy PGS TS. Đỗ Văn Nhơn hướng dẫn, em nhận thấy môn học này rất bổ ích và
đem lại nhiều kiến thức mới. Chúng em xin chân thành cảm ơn thầy!
Nguyễn Hữu Phước CH1301107 Trang 2
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
while (not Điều_Kiện_Kết_Thúc) do
Nguyễn Hữu Phước CH1301107 Trang 4
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
begin
T = T + 1;
Chọn lọc P(T) từ P(T-1);
Kết hợp các cá thể (bằng lai ghép & đột biến) trong P(T);
Đánh giá độ thích nghi cho các cá thể trong P(T);
end
end
Các toán tử và kỹ thuật được áp dụng trong thủ tục trên sẽ được mô tả chi tiết
hơn trong các phần tiếp theo.
2 Các thao tác cơ bản
Để giải một bài toán tối ưu bằng cách áp dụng thuật giải di truyền, ta thường
phải giải quyết 5 vấn đề:
• Biểu diễn di truyền hay chọn cách mã hóa các lời giải của bài toán
• Phát sinh quần thể ban đầu P(0).
• Chọn hàm đánh giá để xác định mức độ thích nghi của lời giải
• Áp dụng các toán tử di truyền (lai ghép, đột biến) để tạo ra các cá thể mới
• Xác định các tham số đầu vào của thuật giải. Chẳng hạn như kích thước
quần thể, xác suất lai ghép, xác suất đột biến,…
2.1Mã hóa
Mã hóa là việc xác định cách thức biểu diễn di truyền đối với lời giải của bài
toán. Việc mã hóa phụ thuộc nhiều vào từng bài toán cụ thể. Một số cách biểu
diễn thông dụng:
• Biểu diễn nhị phân: mỗi nhiễm sắc thể là một dãy số nhị phân. Mỗi gen có
thể được mã hóa nhờ một số lượng bit nào đó.
• Biểu diễn theo số tự nhiên: mỗi nhiễm sắc thể là một dãy các số tự nhiên.
Phương pháp này được dùng nhiều trong các bài toán tối ưu tổ hợp hay
hoán vị.
toán người du lịch, tại gen thứ k, ta chọn đỉnh gần nhất với đỉnh trong gen thứ k-
1 và chưa được chọn.
2.3Hàm đánh giá và hàm thích nghi
Trong hầu hết các bài toán áp dụng thuật giải di truyền, ta quy về việc tối ưu
cực đại (hoặc cực tiểu) một hàm một hoặc nhiều biến. Khi đó, độ tốt của cá thể là
giá trị hàm tương ứng của cá thể đó. Như vậy, nếu chọn một cá thể là nghiệm của
bài toán thì cá thể càng tốt khi giá trị hàm càng gần với giá trị tối ưu (cực đại
hoặc cực tiểu) càng tốt. Hàm để đánh giá độ tốt của cá thể hay lời giải gọi là hàm
mục tiêu.
Tuy nhiên, để chọn lọc các cá thể di truyền cho thế hệ tiếp theo, ta cần phải
biến đổi hàm mục tiêu sang hàm thích nghi. Điều này cũng tương tự như trong tự
nhiên, các cá thể thích nghi tốt với môi trường sống sẽ được bảo tồn cho thế hệ
kế tiếp.
Nguyễn Hữu Phước CH1301107 Trang 6
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
Độ thích nghi của cá thể được định nghĩa là khả năng cá thể đó được chọn lọc
vào thế hệ sau hoặc được chọn cho việc lai ghép, tạo ra cá thể mới.
Hàm mục tiêu là cơ sở để đánh giá độ thích nghi của các cá thể. Việc ánh xạ
từ hàm mục tiêu sang hàm thích nghi tùy thuộc vào mục đích của bài toán thực
tế.
2.4Các toán tử di truyền
Chọn lọc là quá trình chọn một cách ngẫu nhiên các cặp cá thể trong quần thể
để thực hiện việc lai tạo ra cá thể con cho thế hệ sau. Mục đích của chọn lọc là
chú trọng vào các cá thể có độ thích nghi cao với hi vọng rằng, các con của
chúng sẽ có độ thích nghi cao hơn nữa. Một số cơ chế chọn lọc thường được áp
dụng:
• Chọn lọc theo vòng Roulette (Roulette wheel selection)
• Chọn lọc cạnh tranh (Tournament selection)
• Chọn lọc thứ tự (Rank selection)
• Elitism selection
Parent 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0
Child 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0
Hình 3. Một số dạng đột biến
2.5Các tham số của thuật giải
Kích thước quần thể (PopSize) là số lượng cá thể trong mỗi thế hệ tiến hóa.
Giá trị của nó phụ thuộc vào sự phức tạp của từng bài toán cụ thể. Kích thước
quần thể lớn có thể giúp khám phá nhanh toàn bộ không gian tìm kiếm. Tuy
nhiên, nó yêu cầu chi phí cho việc tính toán, bộ nhớ và cả thời gian thực thi.
Trong thực tế, giá trị này thường được chọn là 100.
Xác suất lai ghép (p
c
) là tham số mô tả mức độ thường xuyên mà phép lai
ghép được thực hiện. Nếu p
c
= 100% thì mọi cá thể con đều được tạo ra từ việc
lai ghép. Điều này đôi khi là không tốt vì chúng ta muốn lưu giữ một phần của
quần thể trước nhằm duy trì tính đa dạng của quần thể. Nếu p
c
= 0% thì thế hệ
Nguyễn Hữu Phước CH1301107 Trang 8
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
sau chỉ là bản sao y nguyên của thế hệ trước, có nghĩa là không có sự tiến hóa. Số
lượng cá thể tham gia vào quá trình lai ghép là: p
c
* PopSize.
Xác suất đột biến (p
m
) là tham số quyết định mức độ thường xuyên mà các
phần tử của nhiễm sắc thể bị đột biến. Đột biến ngăn thuật giải di truyền rơi vào
cực trị cục bộ. Giá trị này càng lớn thì càng nhiều cá thể bị biến đổi làm mất tính
P q r s t
P Q R S t
Alen đại diện cho thuộc tính của một gen cụ thể. Mỗi vị trí của một kí tự đại
diện cho một alen. Các kí tự viết hoa và viết thường được đưa ra ở trên đại diện
cho các alen thay thế (alternative) tại mỗi vị trí. Trước tiên, trong tự nhiên mỗi
alen biểu thị các thuộc tính kiểu hình khác nhau. Chẳng hạn, Q có thể biểu diễn
cho gen tóc xám và q có thể là gen tóc đen. Như vậy, một cặp (Q, q) mô tả một
chức năng, vì thế, cần phải có cách để quyết định xem giá trị nào được chọn bởi
vì chẳng hạn, kiểu hình không thể cùng lúc tóc xám và tóc đen.
Một cách tiếp cận để loại bỏ xung đột dư thừa này là thông qua một cơ chế
gọi là gen trội. Tại một vị trí, một alen (gọi là gen trội) sẽ được ưu tiên hơn một
alen thay thế khác (gọi là gen lặn). Có thể nói rằng, một alen là trội nếu nó được
biểu hiện khi đi cặp với một vài alen khác. Biểu hiện nghĩa là nó xuất hiện trong
các kiểu hình.
Trong ví dụ trên, nếu giả sử tất cả các kí tự hoa là trội và tất cả các kí tự
thường là lặn thì kiểu hình được biểu thị của nhiễm sắc thể ví dụ trên sẽ là:
P q r S t
→ P Q R S t (gen được biểu hiện lên kiểu
hình)
p Q R S t
Gen trội luôn luôn được biểu hiện và gen lặn chỉ biểu hiện khi nó đi cặp với
cùng một gen lặn. Gen trội được biểu thị trong các phần tử dị hợp (Pp P) hoặc
đồng hợp (SS S) và gen lặn được biểu thị chỉ khi là đồng hợp lặn (tt t).
Do đó trội là một toán tử di truyền được sử dụng để tính toán kiểu hình các
giá trị alen có thể tại một vị trí gen.
Nhiễm sắc thể lưỡng bội cung cấp sự thuận lợi cho các cá thể khi môi trường
thay đổi qua một khoảng thời gian. Việc có 2 gene cho phép hai giải pháp khác
Nguyễn Hữu Phước CH1301107 Trang 10
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
nhau được nhớ (ghi lại) và chuyển qua cho con cháu. Một trong những gen này là
Hình 4.b. Đa bội loại 2 (multiploid type 2)
Một giá trị alen a tại điểm i trong mặt nạ biểu thị rằng gen thứ i trong thành
phần ứng với chỉ số a trở thành gen thứ i trong kiểu hình. Chiều dài của mặt nạ
có thể ngắn hơn chiều dài của nhiễm sắc thể, như hình 4.b.
Trong hình 4.b, nếu chiều dài của mặt nạ là m và nhiễm sắc thể có chiều dài
L, một gen tại vị trí “i” trong mặt nạ với giá trị là “a” chỉ ra rằng tập L/m gen liên
tục thứ i trong thành phần thứ a của nhiễm sắc thể là trội.
3.3Một số toán tử vi mô tái thiết lập thứ tự
3.3.1 Toán tử đảo (inversion)
Đảo là toán tử một ngôi, một trong các toán tử di truyền thực hiện việc tái sắp
xếp thứ tự. Toán tử đảo ngược là cơ chế tự nhiên chủ yếu để tái mã hóa một vấn
đề. Trong toán tử đảo ngược, hai điểm đánh dấu và chiều dài của nhiễm sắc thể
được cho trước, đoạn nhiễm sắc thể giữa hai điểm đánh dấu bị cắt và đảo ngược.
Để rõ ràng hơn, ta xét hai nhiễm sắc thể có chiều dài 8, hai điểm đánh dấu được
chọn ngẫu nhiên (là 2 và 6) như sau:
Sử dụng toán tử đảo, ta có kết quả:
Nguyễn Hữu Phước CH1301107 Trang 12
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
Toán tử đảo có thể sử dụng như một toán tử đột biến. Nó có một số biến thể sau:
• Đảo tuyến tính
• Đảo tuyến tính + cuối
• Đảo liên tục
• Đảo khối
Đảo tuyến tính là phép đảo như đã thấy ở ví dụ trên. Đảo tuyến tính+ cuối là
đảo tuyến tính với xác suất được chỉ ra là 0.75. Khi đảo tuyến tính không được
thực hiện, đảo cuối có thể được thực hiện với xác suất 0.125 tại đầu trái hoặc đầu
phải của chuỗi. Đảo tuyến tính + cuối khác đảo tuyến tính ở việc phá vỡ các alen
gần trung tâm của chuỗi và các alen nằm ở cuối chuỗi một cách không cân đối.
Trong chế độ đảo liên tục, phép đảo được áp dụng với một xác suất đảo cụ thể P
i
các loài khác nhau. Tuy nhiên, chỉ cần xét ví dụ trên con người là đủ để hiểu về
sự xác định giới tính. Giới tính được xác định trong một người bởi một trong 23
cặp nhiễm sắc thể của người. Nữ có hai nhiễm sắc thể đều là X và nam có hai
nhiễm sắc thể khác nhau là X và Y. Trong quá trình hình thành giao tử
(gametogenesis process), nam giới hình thành tinh trùng (mang nhiễm sắc thể X
hoặc Y) và nữ giới sở hữu trứng (mang nhiễm sắc thể X).
Lúc thụ tinh, nhiễm sắc thể X sinh bởi người nữ được kết hợp với nhiễm sắc
thể X hoặc Y sinh ra bởi người nam. Vì thế, phương pháp xác định giới tính trên
người rất đơn giản. Chiến lược tương tự cũng được áp dụng để xác định giới tính
trong tìm kiếm theo thuật giải di truyền. Sự thiết lập giới tính khác nhau chia một
loài thành 2 hay nhiều nhóm một cách có hiệu quả. Điều này cho phép chuyên
biệt hóa nam và nữ, do đó, kèm theo một loạt các hành vi cần thiết cho sự sống
một cách rộng rãi hơn với một quần thể cạnh tranh duy nhất. Các nghiên cứu
theo sự xác định giới tính và sự khác nhau về tìm kiếm thuật giải di truyền nhân
tạo vẫn còn đang tiếp diễn.
Khi tổ hợp các toán tử lai và toán tử đảo, ta thiết lập được một số phép lai có
thể tái thiết lập trật tự các gen. Ba phép lai theo dạng này được sử dụng nhiều
trong các bài toán thực tế là: lai so khớp từng phần (PMX), lai thứ tự (OX) và lai
chu trình (CX).
Nguyễn Hữu Phước CH1301107 Trang 14
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
3.3.5 Phép lai so khớp từng phần (Partially Matched Crossover – PMX)
Trong lai so khớp từng phần, hai chuỗi được sắp hàng, và hai điểm lai được
chọn ngẫu nhiên giống nhau dọc theo chiều dài của chuỗi. Hai điểm lai cho một
chọn lọc khớp được dùng để tác động thông qua toán tử trao đổi vị trí – vị trí.
Xét 2 nhiễm sắc thể:
Hai điểm lai được chọn ngẫu nhiên, quá trình lai PMX thực hiện thay đổi vị
trí. Giữa các điểm lai, các gen được hoán đổi, nghĩa là gen 3 và 2, gen 6 và 7, gen
5 và 9 thay đổi vị trí. Đây là ánh xạ từ mẹ B qua bố A. Bây giờ ánh xạ từ bố A
qua mẹ B, gen 7 và 6, gen 9 và 5, gen 2 và 3 thay đổi vị trí cho nhau. Do đó sau
Child A: 1 - - 4 - - - - -
Tương tự, gen tại vị trí thứ 4 của Parent B có giá là 8, giá trị này nằm tại vị trí 8
trong Parent A nên Child A sẽ là:
Child A: 1 - - 4 - - - 8 -
Tiếp tục thực hiện theo cách này, cho đến khi hoàn thành 1 chu trình, tức là quay
trở lại một gen đã chọn.
Child A: 1 - 3 4 - - - 8 -
Child A: 1 2 3 4 - - - 8 -
Nguyễn Hữu Phước CH1301107 Trang 16
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
Sau đó, các giá trị còn lại được lấy từ Parent B, ta được Child A như sau
Child A: 1 2 3 4 7 6 9 8 5
Thực hiện tương tự các bước trên để tạo con B, ta được:
Child B: 4 1 2 8 5 6 7 3 9
3.4Vùng thích nghi (Niche) và sự hình thành loài (Speciation)
Vấn đề muôn thuở của thuật toán di truyền là hội tụ sớm. Nghĩa là, một kiểu
gen không tối ưu kiểm soát quần thể kết quả trong đó mỗi cá thể hoặc giống hệt
nhau hoặc rất giống nhau. Hậu quả là quần thể sẽ không đủ đa dạng cho sự tiến
hóa xa hơn.
Nếu đơn giản chỉ tăng kích thước quần thể sẽ không đủ để tránh vấn đề trên,
vì bất cứ sự gia tăng quần thể nào sẽ phải chịu chi phí gấp đôi và cần nhiều thế hệ
hơn nữa để bài toán hướng đến giải pháp tối ưu.
Như vậy, thuật giải di truyền đối mặt với một vấn đề khó khăn. Đó là làm thế
nào để quần thể có thể hội tụ về một giải pháp mà vẫn duy trì tính đa dạng.
Những toán tử di truyền gây ra hội tụ - như phép lai hay sinh sản - phải được
thay đổi bằng cách nào đó.
Một hạn chế khác đối với thuật giải di truyền đó là thời gian tham gia vào
việc dẫn xuất ra một giải pháp. Nó không giống như những phương pháp khác
như là mạng neural, tìm kiếm leo đồi, các phương pháp dựa trên luật v.v , thuật
giải di truyền nặng về mặt ngẫu nhiên và không đảm bảo sẽ hướng đến kết quả
Lấn áp (Crowding)
Vấn đề đầu tiên - ngăn chặn 1 kiểu gen duy nhất chiếm cả quần thể - được
giải quyết bằng cách đảm bảo rằng 1 cá thể mới sẽ thay thế một trong nhữg kiểu
gen tương đồng của nó. Crowding cố gắng duy trì quần thể cân bằng. Cơ chế cho
sự thay thế này khá là đơn giản: chọn ngẫu nhiên CF cá thể và thông qua tính
toán khoảng cách hamming, quyết định cá thể thay thế thích hợp.
Ưu điểm của Crowding là đánh giá được các cá thể khi lựa chọn nạn nhân
thay thế, CF thường là 2 hoặc 3. Việc thay thế các cá thể tương đồng đóng vai trò
ngăn chặn lại một kiểu gen chiếm lĩnh toàn bộ quần thể, mặt khác, cho phép các
vùng ít thích nghi có thể hình thành bên trong quần thể chính
Crowding không tạo ra các vùng thích nghi một cách rõ ràng, cũng không cố
gắng khuyến khích chúng mà chỉ cho phép chúng hình thành.
Sharing
Một cách tiếp cận khác được thông qua trong sơ đồ Sharing, trong đó cá thể
bên trong quần thể sử dụng việc chia sẻ các tài nguyên hạn chế, vì chúng cố gắng
thích nghi.
Theo cách tương tự như Crowding, sự chiếm lĩnh của quần thể bởi kiểu gen
duy nhất không được khuyến khích bằng cách thay thế các cá thể tương đồng
nhau trong phần đông quần thể. Tuy nhiên Sharing không đơn giản là tính toán
như Crowding. Và một vấn đề rất cụ thể phải biết trước là có bao nhiêu đỉnh
trong không gian giải pháp.
Nguyễn Hữu Phước CH1301107 Trang 19
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
Sharing khuyến khích sự hình thành các vùng thích nghi và ngăn chặn viễn
cảnh không tốt của những cá thể từ những vùng thích nghi khác nhau kết cặp để
tạo ra cá thể con bằng cách sử dụng hình thức giao phối giới hạn.
Xác định hàm Sharing dựa trên sự tương đồng
Hoặc dựa trên tương đồng kiểu hình (giá trị được mã hóa) thay vì kiểu gen
Hai nhiễm sắc càng tương đồng, chúng càng phải chia sẻ giá trị thích nghi. Mỗi
nhiễm sắc thể x có một hệ số tính toán cho nó
vài cá thể, các phương pháp mới này bảo đảm tính duy nhất bằng cách so sánh cá
thể mới với mọi cá thể khác trong quần thể. Giống như Crowding, chúng không
cố gắng tạo các vùng thích nghi hay loài (species) rõ ràng mà cố ngăn chặn sự
chi phối lên quần thể bởi một hình thái duy nhất.
Không may, cả hai phương pháp này có chi phí cao vì việc so sánh các cá thể
là việc khá tốn kém.
Ngăn chặn sự loạn luân (Incest prevention)
Incest prevention cố mai mối (matchmake) cặp bố mẹ với ý định các con của
chúng sẽ lấy các gen tốt nhất từ bố mẹ chúng. Đó là kết hợp các bố mẹ khác nhau
sao cho tính đa dạng được giữ trong quần thể và vì vậy cho phép tiếp tục tiến
hóa.
Khi một quần thể tiến hóa, các cá thể càng trở nên tương tự nhau hơn và vì
vậy, khó mà tìm được cặp bố mẹ phù hợp hơn. Để tránh tình huống không có cặp
bố mẹ như vậy trong quần thể, cần một tập ngưỡng khác – có thể nới lỏng nếu có
sự khó khăn trong việc chọn bố mẹ.
Nguyễn Hữu Phước CH1301107 Trang 21
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
Hình 7. Đồ thị của một hàm đơn phương thức
Mã giả cho thuật toán chọn cặp bố mẹ
SET THRESHOLD
REPEAT
FOR EACH INDIVIDUAL DO
TEST INDIVIDUAL
ENTER PARENT POPULATION
IF NO-NEW-PARENTS THEN
LOWER THRESHOLD
FOR EACH INDIVIDUAL DO
REPEAT
SELECT PARENTS
UNTIL DIFFERENT ( )
rằng các cá thể phù hợp với các yêu cầu sẽ được sinh ra. Sau đây là mã giả của
thuật toán Pygmy.
REPEAT
FOR EACH INDIVIDUAL DO
TEST INDIVIDUALWITH MAIN FITNESS FUNCTION
ENTER PARENT POPULATION #1
IF UNSUCCESSFUL
TEST INDIVIDUALWITH SECONDARY FITNESS
FUNCTION
ENTER PARENT POPULATION #2
Nguyễn Hữu Phước CH1301107 Trang 23
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
FOR EACH INDIVIDUAL DO
SELECT PARENT FROM POPULATION #1
SELECT PARENT FROM POPULATION #2
CREATE NEW INDIVIDUAL
UNTIL END-CRITERION REACHED
Mỗi vùng thích nghi được thực hiện nhằm duy trì các cá thể trong một không
gian giải pháp. Dĩ nhiên, cũng có khả năng một con nào đó thừa hưởng những
đặc điểm tồi tệ nhất của bố mẹ chúng. Những đứa con này sẽ được bỏ qua bởi
thuật toán Pygmy nhưng bố mẹ chúng vẫn tồn tại được – vì chúng có khả năng
sinh ra các con tốt nên được duy trì.
Hạn chế kết cặp (Restricted Mating)
Mục đích của hạn chế việc kết cặp là khuyến khích sự hình thành loài và giảm
khả năng sinh sản chết (the production of lethals). Một cá thể chết (lethal) là một
con của cặp bố mẹ từ hai vùng thích nghi khác nhau. Mặc dù mỗi bố mẹ đều có
độ thích nghi cao nhưng sự kết hợp các nhiễm sắc thể của chúng có thể không
thích hợp nếu nó rơi vào thung lũng giữa hai đỉnh cực đại như hình 6.
Về mặt lý thuyết, nếu có hai bố mẹ tương tự nhau (nghĩa là từ cùng một
niche) được giao phối thì các con cái sẽ tương tự nhau. Tuy nhiên, điều này phụ
3.6Tối ưu tổ hợp
Có một lượng lớn các bài toán thuộc dạng tối ưu tổ hợp với các đặc trưng và
thuộc tính khác nhau. Mặc dù các vấn đề này hơi khác, chúng có thể được mô tả
theo một trong các loại sau:
• Xác định một hoán vị của một số mục liên quan tới bài toán
• Xác định một tổ hợp các mục
• Xác định cả hoán vị và tổ hợp các mục
• Bất kỳ một trong các đối tượng trên để ràng buộc.
Chẳng hạn, bản chất của các bài toán lập lịch dự án ràng buộc trên tài nguyên,
định tuyến xe và các bài toán lập lịch là xác định một hoán vị của vài mục theo
một số ràng buộc. Bản chất của bài toán lập lịch máy song song là xác định cả
hoán vị và tổ hợp của các mục theo một số ràng buộc.
Một đặc trưng chung của các bài toán là nếu hoán vị và/hoặc tổ hợp có thể
xác định được thì giải pháp có thể dễ dàng dẫn xuất ra bằng một thủ tục cụ thể
Nguyễn Hữu Phước CH1301107 Trang 25
Copyright: Tài liệu đại học ©