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Ị

Thuật giải di truyền (GA) được hình thành dựa trên quan niệm cho rằng quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, tự nó đã mang tính tối ưu. Quá trình tiến hoá thể hiện tính tối ưu ở chỗ, thế hệ sau thường phát triển hoàn thiện hơn thế hệ trước. GA sử dụng các thuật ngữ của di truyền học.
Nội dung trích xuất từ tài liệu:
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Ị" …………..o0o………….. Báo cáo khoa học: PHƯƠNG PHÁP THUẬT GIẢI DI TRUYỀN VÀ TÌMMẶ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 Trường Đại học Giao thông Vận tải Tóm tắt: Bài viết trình bày khái quát về thuật giải di truyền và ứng dụng để giải bài toán tối ưu cắt dọc đường sắt đô thị. Summary: This article presents a general idea on genetic algorithms and using it in solving optimization problems on longitudinal profile of Mass Urban Transit. I. KHÁI QUÁT VỀ THUẬT GIẢI DI TRUYỀN Thuật giải di truyền (GA) được hình thành dựa trên quan niệm cho rằng quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, tự nó đã mang tính tối ưu. Quá trình tiến hoá thể hiện tính tối ưu ở chỗ, thế hệ sau thường phát triển hoàn thiện hơn thế hệ trước. GA sử dụng các thuật ngữ của di truyền học. Ta có thể nói về những cá thể (hay kiểu gen), trong một quần thể. Những cá thể này còn được gọi là các nhiễm sắc thể (NST). Trong GA chỉ xét những cá thể có một NST. Các NST được tạo thành từ các gen. Gen với những đặc trưng nhất định, có vị trí nhất định trong NST. Mỗi NST sẽ biểu diễn một lời giải của bài toán. Một tiến trình tiến hoá được thực hiện trên một quần thể các NST tương ứng với một quá trình tìmCT 1 lời giải. GA thuộc lớp các lời giải xác suất nhưng khác các thuật giải ngẫu nhiên, chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên. GA duy trì và xử lý một tập các lời giải (quần thể). GA khá mạnh hơn các phương pháp khác. II. CÁC PHƯƠNG THỨC BIẾN HOÁ CỦA GA 2.1. Tạo sinh: Dùng những thành phần của thế hệ trước để tạo thêm thành phần của thế hệ sau. Giống như trong thiên nhiên, những thành phần nào có hệ số thích nghi lớn hơn sẽ có cơ hội được chọn để thực hiện tạo sinh. 2.1.1. Quy tắc tạo sinh đường (TSĐ) Giá trị gen của thế hệ sau được chọn trong khoảng giữa 2 giá trị cá thể cha và mẹ. Nếu 2 cá thể cha mẹ là A, B, cá thể con là C thì thành phần gen thứ i của con cháu được xác định bằng công thức sau: Ci = min (Ai, Bi) + α |Bi - Ai| B Với Ai, Bi, Ci 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ùngmộ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àiNST. Điểm k sẽ chia NST của cá thể cha mẹ A thành A1, A2 và B thành B1, B2. Hai NST đượctạo mới nhờ gép phần đầu của cá thể A với phần cuối của cá thể B (A1 B2) và ngược lại, gépphần đầu của cá thể B với phần cuối của cá thể A (B1A2). 2.2.2. Lai ghép đa điểm: Là một dạng tổng quát của lai ghép đơn điểm. Ở đây, thay vì chỉchọn một điểm lai ghép ta chọn nhiều điểm lai ghép. 2.2.3. Lai gép mặt nạ: Là hình thức tổng quát nhất của lai ghép. Trong lai gép mặt nạ, liênkết với hai cá thể cha mẹ A, B là 2 mặt nạ mA, mB. Hai mặt nạ này có cùng chiều dài với A vàB. Mặt nạ có thể được phát sinh một cách ngẫu nhiên khi tiến hành lai ghép hoặc thừa kế từ thếhệ trước. Giá trị bit của mặt nạ sẽ quyết định thành phần gen nào của cá thể con sẽ được trích ratừ gen của cha mẹ. 2.3. Đột biến: Là việc thay đổi trị số của một số trong dẫy số, thí dụ 0 thành 1 hoặc 1 thành0 cho trường hợp dùng dãy số theo hệ nhị phân. So với lai ghép phương thức biến hoá dựa trênđột biến rất ít xảy ra.III. GIẢI BÀI TOÁN TỐI ƯU CẮT DỌC THEO PHƯƠNG PHÁP GA 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 ...