………… o0o…………
Báo cáo khoa học: "PHƯƠNG PHÁP
THUẬT GIẢI DI TRUYỀN VÀ TÌM
MẶT CẮT DỌC TỐI ƯU ĐƯỜNG SẮT
ĐÔ THỊ"

PHƯƠNG PHÁP THUẬT GIẢI DI TRUYỀN
VÀ TÌM MẶT CẮT DỌC TỐI ƯU ĐƯỜNG SẮT ĐÔ THỊ

PGS. TS. PHẠM VĂN KÝ
ThS. NCS. NGUYỄN HỮU THIỆN

i
= min (A
i
, B
i
) + α |BB
i
- A
i
|
Với A
i
, B
i
, C
i
lần lượt là thành phần gen thứ i của cha mẹ A, B và cá thể con C, α là hệ số
tỷ lệ được chọn ngẫu nhiên trong đoạn [0,1], có thể mở rộng giá trị α trong đoạn [-d, 1+d] với
d ≥ 0.
2.1.2 Quy tắc tạo sinh tức thời
Là 1 dạng mở rộng của TSĐ, cách tạo ra cá thể con cũng tương tự TSĐ, chỉ khác là dùng một dãy α
i
để tạo ra các cá thể.
2.2. Lai ghép (crossover)
2.2.1. Lai gép đơn điểm: Là dạng lai ghép đơn giản nhất, có thể áp dụng cả đối với kiểu dữ
liệu chuỗi nhị phân lẫn số thực. Trước hết ta chọn ra 2 cá thể cha mẹ A, B, được chọn lọc ra từ
tập cá thể. Xác định một vị trí lai ghép k ngẫu nhiên thuộc đoạn [2, N-1] với N là chiều dài

Xét mặt cắt dọc (MCD) cần nghiên cứu tối ưu, ví dụ gồm 7 đoạn như hình vẽ dưới. Ta sẽ
ghi vào bảng, chi phí cho từng đoạn theo từng phương án. Vấn đề là phải tìm được một phương
án MCD trên tuyến nghiên cứu có giá trị Hàm mục tiêu là Tổng chi phí nhỏ nhất.
TCT1

3.1. Nhiễm sắc thể. Mỗi nhiễm sắc thể đại diện cho một phương án. Một nhiễm sắc thể
gồm một số gen. Trong ví dụ này Nhiễm sắc thể chính là một chuỗi gồm 7 gen, mà mỗi gen là
chi phí của mỗi đoạn từ đoạn 1 đến đoạn 7.
Ví dụ: Nhiễm sắc thể biểu thị phương án: 0-13-23-33-43-53-63-7 là: 145 135 140 120 130 165 98
Trong đó mỗi giá trị số 145, 135, 98 được gọi là một gen,
Cả chuỗi số 145, 135, 140, 120, 130, 165, 98 được gọi là một nhiễm sắc thể.
3.2. Hàm mục tiêu. Trong bài toán đang xét hàm mục tiêu chính là tổng chi phí các đoạn từ
đoạn 1 đến đoạn 7. Cũng có thể nói đó là "giá trị" của nhiễm sắc thể.
3.3. Chọn quần thể ban đầu. Chọn 9 phương án cắt dọc, có nghĩa là 9 cá thể ban đầu, cũng
có nghĩa là 9 nhiễm sắc thể.
CT 1
175
145 135 140 120 130 165 98
130 145 115 140 136 165 80
130 130 115 135 140 165 80
145 125 128 130 136 98
130 100 128 130 136 165 80
120 145 145 115 136 165 80
145 130 155 120 126 160 155
130 126 155 115 120 185 98
120 130 155 130 135 175 155
3.4. Bằng cách thay đổi trật tự (order) của các ô này, ta sẽ tìm được giá trị nhỏ nhất của


Bảng giá trị chi phí các đoạn (Đơn vị tiền tệ)
Doan 1 Doan 2 Doan 3 Doan 4 Doan 5 Doan 6 Doan 7
PA
Chi
phi
PA
Chi
phi
PA
Chi
phi
PA
Chi
phi
PA
Chi
phi
PA
Chi
phi
PA
Chi
phi
0-1.3 145 1.3 - 2.3
135
2.3 - 3.3
140
3.3 - 4.3
120

0-1.2 130 1.3 - 2.2
125
2.3 - 3.2
115
3.3 - 4.2
115
4.3 - 5.2
126
5.3 - 6.2
160
6.3 – 7

1.2 - 2.2
100
2.2 - 3.2
144
3.2 - 4.2
140
4.2 - 5.2
136
5.2 - 6.2
165
6.2 – 7

1.1 - 2.2
145
2.1 - 3.2
160
3.1 - 4.2
130

1.1 - 2.1
130
2.1 - 3.1
155
3.1 - 4.1
130
4.1 - 5.1
135
5.1 - 6.1
175
6.1 - 7
155
TCT1
(Kết quả tính toán theo GA)
IV. KẾT LUẬN
GA cho kết quả rất sát với phương pháp quy hoạch động. Trong ví dụ này là cực tiểu hàm
mục tiêu y bằng 868 (GA) so với 865 (QHĐ), sai số khoảng 0.35%.
Có thể sẽ là phức tạp trong việc tìm ra mô hình GA cho bài toán, như ý nghĩa các nhiễm
sắc thể, các gen khi mới tiếp cận với phương pháp này.
Phương pháp GA là một phương pháp mở, cùng một bài toán có thể xây dựng nhiều mô
hình khác nhau.
Đây là phương pháp mạnh, giải nhiều dạng bài toán phức tạp của ngành.
Tài liệu tham khảo
[1]. Hoàng Kiếm, Lê Hoàng Thái. Thuật giải di truyền. NXB Giáo dục, 2000.
2]. Masatoshi Sakawa. Genetic Algorithms and Fuzzy Multiobjective Optimization. Klower Academic, [
2002. . Evolutionary Algorithms in Engineering and Computer Science, John Wiley & Sons Ltd, 1999 ♦ [3]
CT 1