Thứ năm, ngày 18 tháng 12 năm 2014 | 19:25

Thuật giải di truyền và ứng dụng trong tính toán thiết kế tối ưu hình thang lái ô tô

TS. Nguyễn Tuấn Anh
ThS. Vũ Văn Trung
KS. Trần Xuân Huy
Trường Đại học GTVT
Người phản biện: PGS. TS. Nguyễn Đăng Điệm

Tóm tắt: Thuật giải di truyền (TGDT) được các nhà khoa học phát triển dựa trên lý thuyết chọn lọc tự nhiên và lý thuyết di truyền học của Darwin để giải quyết các bài toán tối ưu hóa phi tuyến nhiều mục tiêu. Hiện nay, TGDT đã và đang được ứng dụng rộng rãi trên thế giới và đem lại nhiều kết quả tin cậy. Tuy nhiên ở Việt Nam, lý thuyết này còn khá mới mẻ và chưa được ứng dụng nhiều trong các lĩnh vực tối ưu hóa thiết kế kỹ thuật. Chính vì vậy, nhóm tác giả bước đầu tiếp cận, nghiên cứu ứng dụng TGDT nhằm giải quyết một số bài toán thiết kế tối ưu kỹ thuật để từng bước khai thác các tính năng ưu việt của thuật giải này và tạo một công cụ mới trong tính toán thiết kế.

Abstract: Genetic algorithm is developed by scientists based on the natural selected theory and genetic theory by Darwin in order to settle maths of multi function non-linear optimization . Currently, the genetic algorithm has been widely applying in the world and bring a good achievement, however; this theory is quite new in Viet Nam and it has not been used much and particularly in the field of optimization in technical design, therefore; authors has step by step approached, studied the application of the genetic algorithm to settle some technical optimization design maths for gradually implement the preeminent functions of this genetic algorithm and create a new tool in design calculation.

Trên thế giới, việc ứng dụng thuật giải di truyền (TGDT) để giải quyết các bài toán tối ưu trong lĩnh vực kỹ thuật đã được ứng dụng phổ biến và đạt được nhiều kết quả khả quan. TGDT là thuật toán tìm kiếm để giải quyết những bài toán tối ưu hóa dựa trên sự mô phỏng bắt trước cơ chế chọn lọc tự nhiên và cơ chế di truyền trong giới sinh vật. TGDT sử dụng nhiều thuật ngữ vay mượn của di truyền học, vì vậy có thể chưa quen thuộc đối với các kỹ sư. Trong tự nhiên, mỗi cơ thể sinh vật mang một số nhiễm sắc thể nào đó, nhưng trong TGDT thì đơn giản coi mỗi cá thể có một nhiễm sắc thể. Để dễ hiểu có thể coi khái niệm về một phương án thiết kế của ngành kỹ thuật tương đương như là một cá thể trong di truyền học. Trong di truyền học, mỗi nhiễm sắc thể được tạo thành từ các gen – biểu diễn trong một chuỗi tuyến tính, mỗi gen kiểm soát một hay một nhóm đặc trưng nào đó của cá thể. Mỗi nhiễm sắc thể coi như biểu diễn một lời giải của bài toán. Trong giới tự nhiên, một quá trình tiến hóa sẽ xảy ra trên một quần thể các nhiễm sắc thể. Điều này cũng tương tự như quá trình tìm kiếm lời giải tối ưu trong không gian các lời  giải có thể chấp nhận được.
TGDT mang nhiều đặc trưng của loại thuật toán đi tìm kiếm ngẫu nhiên nhưng điều khác biệt là nó kết hợp thêm cả các đặc tính của thuật toán tìm kiếm tất định (không ngẫu nhiên). Nó duy trì và xử lý liên tục một tập hợp (quần thể) các lời giải (các phương án có thể) chứ không chỉ xét mỗi lần một điểm trong không gian tìm kiếm. Do vậy mà TGDT có những ưu điểm hơn khi giải các bài toán tối ưu hóa thực tế với nhiều biến số và không gian tìm kiếm thực tế rất phức tạp, khó mô tả bằng các công thức toán học thông thường.
TGDT thực hiện tìm nghiệm tối ưu theo nhiều hướng bằng cách duy trì một tập hợp các nghiệm cho phép và tạo ra sự trao đổi thông tin giữa các hướng tìm kiếm đó. Tập hợp (quần thể) của các nghiệm cho phép được trải qua quá trình tiến hóa, tương ứng với mỗi đợt tìm kiếm (coi như một thế hệ) thì lại tái sinh các nghiệm tương đối tốt và loại bỏ các nghiệm xấu đi. Tiêu chí đánh giá mức độ tốt hay xấu của các nghiệm chính là giá trị tương ứng với nghiệm đó của hàm mục tiêu. Vậy hàm mục tiêu đóng vai trò giống như vai trò của điều kiện môi trường khắc nghiệt trong tự nhiên. TGDT dựa vào một phần đặc tính tiến hóa của loài người. Ngay cả lý thuyết về sự tiến hóa loài người cũng đã thay đổi khá nhiều từ khi Darwin đề ra đến nay. Do vậy, dĩ nhiên TGDT cũng liên tục được cải tiến và đến nay cũng chưa phải đã hoàn hảo. Tuy nhiên, nói chung một TGDT thường bao gồm 3 toán tử cơ bản: tái sinh, lai ghép và đột biến.

Đặc điểm chủ yếu của TGDT là khả năng xét duyệt toàn bộ nghiệm có thể, sau đó cho ra nghiệm tương đối tốt nhất trên cơ sở so sánh giữa các giá trị hệ số thích nghi, không để ý đến bản chất vật lý hay bản chất toán học của bài toán mà chỉ chú ý đến các nghiệm, đặc biệt là đến dãy số tượng trưng cho nghiệm (tương ứng khái niệm gen của di truyền học). Nói một cách khác thì TGDT làm việc trên sự mã hóa của một tập các tham số, chứ không phải chính bản thân các tham số đó. TGDT mang đặc điểm tìm kiếm ngẫu nhiên và sử dụng giá trị hàm mục tiêu chứ không dùng đạo hàm hay một đại lượng gần đúng của đạo hàm vì vậy cho phép xác định chính xác nghiệm đúng của bài toán tối ưu (không phải giá trị tối ưu địa phương) đây là ưu điểm nổi bất của TGDT khi ứng dụng trong các bài toán tối ưu phi tuyến phức tạp.

Chi tiết tham khảo Tạp chí GTVT số tháng 7/2013
Bia thang 7

Bình luận

You must be logged in to post a comment.

Tin khác :