tailieunhanh - 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. | 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ìm 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 . 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. . 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 a Bi - Ai 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 a