Đề tài: Giải thuật Gen và bài toán tìm đường đi ngắn nhất

Trích dẫn Nội dung

Giải thuật gen (GAs) là giải thuật tìm kiếm, chọn lựa các giải pháp tối ưu để giải quyết các bài toán khác nhau dựa trên cơ chế chọn lọc tự nhiên của ngành di truyền học.

Trong cơ thể cơ thể sinh vật, các gen liên kiết với nhau theo cấu trúc dạng chuỗi gọi là nhiễm sắc thể , nó đặc trưng cho mỗi loài và quyết định sự sống còn của cơ thể đó. Trong tự nhiên một loài muốn tồn tại phải thích nghi với môi trường ,cơ thề sống nào thích nghi với môi trường hơn thì sẽ tồn tại và sinh sản với số lượng ngày càng nhiều hơn , trái lại những loài không thích nghi với môi trường sẽ dần dần bị diệt chủng .Môi trường tự nhiên luôn biến đổi ,nên cấu trúc nhiễm sắc thể cũng thay đổi để thích nghi với môi trường ,và ở thế hệ sau luôn có độ thích nghi cao hơn ở thế hệ trước .Cấu trúc này có được nhờ vào sự trao đổi thông tin ngẫu nhiên với môi trường bên ngoài hay giữa chúng với nhau . Dựa vào đó các nhà khoa học máy tính xây dựng nên một giải thuật tìm kiếm tinh tế dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hóa, gọi là giải thuật gen (Genetic Algorithms)

Mục tiêu nghiên cứu của GAs là :

-Trừu tượng hóa và diễn đạt chính xác về các quá trình thích nghi trong hệ thống tự nhiên .

-Thiết kế những phần mềm về hệ thống nhân tạo nhằm duy trì các cơ chế quan trọng của hệ thống tự nhiên .

Những mục tiêu này đã dẫn đến những khám phá quan trọng trong hệ thống khoa học tự nhiên lẫn nhân tạo .

Vấn đề trọng tâm của việc nghiên cứu GAs là tính mạnh mẻ của giải thuật ,sự cân bằng giữa tính hiệu quả và sự cần thiết để có thể tồn tại trong nhiều môi trường khác nhau.

GAs ra đời và phát triễn dựa trên quá trình tiến hóa trong tự nhiên và đã được ứng dụng thành công trong nhiều lĩnh vực nhất là tối ưu hóa và máy học .

II-GIẢI THUẬT GEN VỚI CÁC PHƯƠNG PHÁP TRUYỀN THỐNG :

GAs khác với những sự tối ưu hóa thông thường và những giải thuật tìm kiếm khác bởi 4 điểm sau :

1-GAs làm việc với sự mã hóa môt bộ các thông số , chứ không phải bản thân các thông số .

2-GAs tìm kiếm từ một số điểm dân cư , chứ không phải từ một điểm.

3-GAs sử dụng các thông tin trả giá (payoff) của hàm mục tiêu chứ không phải đạo hàm (derivatives) hay những tri thức phụ khác.

4-GAs sử dụng các luật chuyển đổi theo xác suất ,chứ không phải các luật chuyển đổi xác định.

GAs đòi hỏi một tập hợp các thông số tự nhiên của bài toán tối ưu để mã hóa thành các chuỗi có chiều dài hữu hạn , dựa trên một số hữu hạn các ký tự .

Để hiểu rõ ta xét bài toán tối ưu đơn giản sau đây :

Ví du: tối ưu hóa hàm f(x) = x2 trên khoảng nguyên [0,31].

Chúng ta muốn tìm cực đại của hàm f(x) = x2 trên đoạn số nguyên [0,31] .Bằng phương pháp truyền thống , chúng ta lần lượt tính bình phương của x theo các giá trị từ 0 đến 31 ,cho đến khi chúng ta chọn được giá trị cao nhất của hàm mục tiêu .

Với GAs bước đầu tiên của quá trình tối ưu hóa là mã hóa x thành một chuỗi có chiều dài xác định .Có nhiều cách đề mã hóa x , chúng ta hãy xét bài toán tối ưu với cách mã hóa tự nhiên .

Giả sử chúng ta có bài toán tắt mở một cái hộp đen ,với một dãy 5 công tắc ở đầu vào . Mỗi tổ hợp các trạng thái của 5 công tắc ứng với một tín hiệu ra ( output ) của hàm f , biễu diễn theo toán học là f = f(s) , trong đó s là một tổ hợp các trạng thái cụ thể của 5 công tắc . Mục tiêu của bài toán là phải đặt các công tắc như thế nào để đạt được giá trị tối đa có thể có của hàm f . Với những phương pháp khác của bài toán tối ưu , chúng ta có thể làm việc trực tiếp với bộ các thông số ( việc đặt các công tắc ) và bậc tắt các công tắc từ một trạng thái này sang trạng thái khác bằng cách dùng những qui tắc chuyển đổi theo phương pháp chuyên biệt . Với GAs ,đầu tiên chúng ta mã hóa dãy các công tắc theo một chuỗi có chiều dài xác định . Cách mã hóa đơn giản như sau : dùng chuỗi dài 5 ký tự gồm các giá trị 0 và 1 , với quy ước tắt = ‘0’ , mở = ’1’.Thí dụ :chuỗi 11110 nghĩa là 4 công tắc đầu mở , công tắc thứ 5 tắt .Bài toán tối ưu hóa hộp đen với 5 công tắc tắt-mở . GAs không yêu cầu bạn biết nguyên tắc làm việc của hộp đen .

Trong nhiều phương pháp tối ưu ,chúng ta di chuyển thận trọng từ một điểm trong không gian quyết định đến điểm kế bằng cách dùng vài luật chuyển đổi để xác định điểm kế tiếp . Phương pháp điểm-đến-điểm này khá nguy hiểm , vì chắc chắn sẽ chỉ ra những đỉnh sai trong không gian tìm kiếm đa hình (multimodal) .Trái lại GAs làm việc với một cơ sỡ dữ liệu phong phú gồm có nhiều điểm đồng thời (một dân số các chuỗi ),thực hiện leo nhiều điểm cùng lúc .Do đó , xác xuất gặp đỉnh sai được giảm nhiều so với các phương pháp điểm-đến-điểm .Bài toán hộp đen là một ví dụ .những kỹ thuật khác để giải quyết bài toán này có thể bắt đầu với một bộ các thiết lập các công tắc ,áp dụng vài quy tắc chuyển đổi , và sinh ra một dãy các công tắc thử mới