Omarine Schoolsheet 2016 2.0 – Thuật giải di truyền(phần 3)

Ánh xạ cothuật giải di truyền có nét tương đồng quý giá: từ một quần thể ban đầu bất kỳ, thuật giải di truyền tiến hóa quần thể tới quần thể tối ưu toàn cục trong không gian quần thể có các quần thể tối ưu cục bộ; tương ứng, xuất phát từ một điểm tùy ý, ánh xạ co hình thành nên dãy Cauchy hội tụ về một điểm bất động duy nhất trong không gian metric đầy đủ có các dãy Cauchy hội tụ tới các điểm khác nhau. Quần thể tối ưu toàn cục tương ứng với điểm bất động duy nhất, quần thể ban đầu tương ứng với điểm xuất phát của dãy Cauchy của ánh xạ co, còn một quần thể tối ưu cục bộ tương ứng với một điểm giới hạn của một dãy Cauchy nói chung trong không gian metric. Một dãy Cauchy như một đường đi tới một tối ưu cục bộ, trong đó dãy Cauchy của ánh xạ co là đường đi tới tối ưu cục bộ mong đợi hay tối ưu toàn cục, là điểm bất động duy nhất của ánh xạ co trong không gian metric.Nói cách khác, với mỗi quần thể ban đầu, thuật giải di truyền tạo ra một dãy tiến hóa, nhưng tất cả các dãy cùng nhắm tới quần thể tối ưu toàn cục; tương ứng, với mỗi điểm xuất phát, ánh xạ co hình thành một dãy Cauchy, nhưng tất cả các dãy đều hội tụ về một điểm bất động duy nhất.

Định nghĩa metric

Để tạo không gian metric cho các quần thể, chúng ta phải định nghĩa cho nó một metric. Bài toán tối ưu nói chung là xử lý hàm mục tiêu, nhưng để đơn giản và không mất tính tổng quát chúng ta lấy ví dụ cho một bài toán chỉ có các ràng buộc. Gọi tập tất cả các quần thể của bài toán là G. Cho rằng P là một quần thể, chúng ta định nghĩa bán kính r của P như sau: r(P) = v(P) + 1, trong đó v(P) là số vi phạm ràng buộc trung bình của các cá thể trong P. Chúng ta có một metric d có thể như thế này:

ditruyen1

với mọi P1, P2 ϵ G.

ditruyen2

Hình vẽ chỉ là minh họa để so sánh khoảng cách giữa các quần thể, và mô tả khoảng cách giữa các quần thể kế nhau co dần. Ý nghĩa đầy đủ của khoảng cách là theo định nghĩa của hàm d. Nếu mỗi quần thể là tâm của một quả cầu với bán kính của quần thể như đã định nghĩa, thì khoảng cách giữa hai quần thể là tổng hai bán kính của hai quả cầu của chúng, nói chung không phải là khoảng cách hình học giữa hai tâm của hai quả cầu. Metric mà lấy khoảng cách bằng chiều dài đoạn thẳng nối giữa hai điểm chỉ là một trường hợp riêng, đó là metric Euclid. Ở đây metric d được định nghĩa trừu tượng hơn. Số vi phạm của một quần thể P là v(P) ≥ 0, vì thế bán kinh của P là r(P) = v(P) + 1 ≥ 0 + 1 = 1. Nếu P1, P2 ϵ G và P1 ≠ P2 thì d(P1, P2) = r(P1) + r(P2) ≥ 1 + 1 = 2. Giá trị 1 được đưa vào để làm cốt cho đối tượng, để phân biệt các phần tử khác nhau trong không gian metric: mọi điểm khác nhau trong không gian đều có khoảng cách khác (lớn hơn) 0.

Rõ ràng:

  • d(P1, P2) ≥ 0
  • d(P1, P2) = 0 ⇔ P1 = P2
  • d(P1, P2) = d(P2, P1)
  • d(P1, P2) + d(P2, P3) = r(P1) + r(P2) + r(P2) + r(P3) ≥ r(P1) + r(P3) = d(P1, P3)

Vậy (G, d) là một không gian metric.

Điều kiện ánh xạ co

Thuật giải di truyền bắt đầu với quần thể P0. Sau mỗi thế hệ, thuật giải tạo ra một quần thể mới từ quần thể hiện hành (nếu chỉ xem như quần thể biến đổi thì phù hợp hơn với ý nghĩa của sự tiến hóa, nhưng trong ngữ cảnh của ánh xạ co, thuật giải tạo ra một quần thể mới). Cho f là một hàm mà ánh xạ mỗi quần thể Pn ở thế hệ thứ n tới quần thể Pn+1 trong thế hệ kế tiếp, chúng ta có f(Pn) = Pn+1, hiển nhiên là f : G → G. Dễ thấy nếu quần thể thực sự tiến hóa, nghĩa là số vi phạm của nó giảm sau mỗi thế hệ, và do đó khoảng cách giữa các quần thể co dần, thì f có tiềm năng là một ánh xạ co.

Điều kiện định lý điểm bất động Banach

Nếu f là một ánh xạ co trên G, thì điều kiện để f có điểm bất động duy nhất trong GG phải không rỗng và đầy đủ. G có quần thể ban đầu P0 nên nó không rỗng. Điều kiện G là đầy đủ cũng dễ thực hiện vì chỉ cần dãy quần thể (Pn) hội tụ tới một quần thể bất kỳ, và bởi vì quần thể nào cũng thuộc G nên do đó G là không gian metric đầy đủ.

Trong thực hành, kết quả này không phải lúc nào cũng đạt được. Đó là trường hợp các thiết lập hệ thống không làm cho quần thể tiến hóa mà suy thoái thì dãy quần thể không hội tụ mà phân kỳ. Tuy nhiên, trong hầu hết các trường hợp, thuật giải sẽ hội tụ tới một quần thể nào đó (không xét tới tối ưu). Đó là khi quá trình tiến hóa không còn tiến triển, thuật giải “dừng chân” tại một quần thể mà các quần thể của dãy (Pn) sau đó có khoảng cách tới nó bằng 0, và do đó nhỏ hơn một số Ꜫ > 0 tùy ý. Trong tất cả các phần bên dưới, chúng ta giả định không gian của các quần thể là không gian metric đầy đủ.

Ánh xạ co đọ sức với lược đồ tối ưu toàn cục

Tại sao điểm bất động duy nhất là quần thể tối ưu toàn cục?

Theo định nghĩa của metric d, ánh xạ co f sẽ đi tới điểm bất động duy nhất P* từ mọi P0 ϵ G, theo hướng làm tăng độ thích nghi eval của quần thể. Giả sử P* không phải là quần thể tối ưu toàn cục, như thế sẽ tồn tại một P0eval(P0) > eval(P*), nhưng rồi f không thể đi ngược từ P0 về P*.

Nếu f có điểm bất động duy nhất, thì thuật giải có lược đồ tối ưu toàn cục. Ngược lại, nếu quá trình tiến hóa không tạo được lược đồ chứa lời giải tối ưu thì f không thể là ánh xạ co. Ví dụ, giả sử lời giải tối ưu là (10100101) nhưng thuật giải chỉ tạo được không gian lời giải khớp với lược đồ (10*0**11), thì mọi phép toán di truyền không khi nào sinh được lời giải tối ưu. Thuật giải chỉ có thể hội tụ tới tối ưu cục bộ, tại điểm mà không thể cải thiện được quần thể trong mọi cách và f không thực hiện được vai trò của ánh xạ co để đi tới điểm bất động duy nhất.

Tuy nhiên, nếu xét trong không gian con S biểu diễn bởi lược đồ nói trên thì hạn chế f|S vẫn có thể là một ánh xạ co trên S. Quả thực, tối ưu cục bộ trên G là tối ưu toàn cục trên S. Do đó, điều cần thiết là phải bổ sung các khối kiến trúc theo cách riêng của thuật giải di truyền. Một khi có đủ không gian cho bài toán, mỗi bước đi của ánh xạ co tạo tiền đề quan trọng cho thế hệ kế tiếp tiến thẳng tới tối ưu toàn cục.

Chúng ta biết rằng tối ưu toàn cục là sức mạnh của thuật giải di truyền. Nhắc lại ví dụ bài toán cực đại là leo lên đỉnh núi cao nhất trong các đỉnh núi. Ngoài việc duy trì một quần thể, thuật giải di truyền còn có phép chọn kết hợp tiến hóa với ngăn chặn tối ưu cục bộ. Tuy nhiên, phép chọn của thuật giải di truyền vẫn dựa trên độ thích nghi và xử lý từng cá thể. Nếu có một số nhóm cá thể trên một số quả núi thì phải mất một thời gian để loại bỏ các cá thể trên quả núi thấp và để các cá thể trên quả núi cao leo lên cao hơn. Nếu hình dung cả quần thể là một phần tử thì có cảm giác quần thể phải vòng xuống phía dưới để đi miết từ quả núi này sang quả núi kia. Nhưng ánh xạ co vốn đã coi cả quần thể là một điểm, và quan trọng hơn, metric d không quan tâm đến khoảng cách hình học, do đó ánh xạ co có thể nhảy thẳng từ quả núi này sang quả núi kia sau một vài lần khởi động lại bộ số ngẫu nhiên tại một bước nào đó. Lý do là vì trong một mức độ nhất định, việc khởi động lại bộ số ngẫu nhiên có thể làm xoay chuyển lược đồ. Rõ ràng, ánh xạ co là một phép chọn bổ trợ rất hiệu quả cho thuật giải di truyền.

Nhận xét

∃ 0 ≤ q < 1 sao cho

d(f(P1), f(P2)) ≤ qd(P1, P2)         Ɐ P1, P2 ϵ G

Trong mục “Điều kiện ánh xạ co” bên trên, chúng ta mới chỉ yêu cầu khoảng cách giữa các quần thể co dần, có nghĩa là

d(f(P1), f(P2)) < d(P1, P2),

điều kiện này không tương đương với điều kiện của ánh xạ co, nó chỉ gần như một trường hợp khi hằng Lipschitz q lớn sát tới 1, ví dụ q = 0.9999.

Theo các bất đẳng thức về tốc độ hội tụ của ánh xạ co trong định lý điểm bất động Banach thì khi q lớn như vậy sẽ không có gì đảm bảo về tốc độ hội tụ. Nói cách khác, thuật giải có thể hội tụ rất chậm, và thời gian có thể lên tới vô hạn.

Ngoài ra, hằng Lipschitz còn có ý nghĩa khác, nó yêu cầu ánh xạ f phải co đều, có nghĩa là một hằng q áp dụng cho mọi thế hệ. Sự co đều của ánh xạ là quan trọng vì thuật giải có thể học để ánh xạ f nhảy qua rãnh khi cần thiết.

  • Mặc dù có thể nhảy qua rãnh, ánh xạ f khó nhảy qua được khe lớn. Đó là khi thuật giải chuyển lược đồ, nó cần một giai đoạn giảm độ thích nghi của quần thể. Nói một cách khái quát, quá trình tiến hóa của quần thể không đơn giản như dãy đơn điệu tăng theo độ thích nghi của ánh xạ co, do đó ánh xạ co không thể liên tục đi theo thuật giải. Khi độ thích nghi của quần thể giảm xuống, ánh xạ co cần phải dừng lại, nó đợi thuật giải chuyển đổi xong lược đồ và tăng trở lại độ thích nghi của quần thể cho tới khi độ thích nghi của quần thể cao hơn độ thích nghi của quần thể hiện hành của ánh xạ co, rồi ánh xạ co nhảy thẳng đến đó. Như vậy, một bước của ánh xạ co tương ứng với một số vòng lặp của thuật giải. Nói cách khác, một thế hệ của ánh xạ co trải qua một số thế hệ của thuật giải.
  • Một yếu tố nữa, nếu hàm mục tiêu bị lệch quá mức thì điểm bất động nếu có, không phải là quần thể tối ưu toàn cục của bài toán. Tuy nhiên, trong một phạm vi cho phép sẽ không có ảnh hưởng vì thuật giải di truyền dựa trên nguyên lý tự nhiên và chính tính ngẫu nhiên sẽ hoàn trả một dung sai mà khử được độ lệch của hàm mục tiêu. Nghĩa là thuật giải sẽ không chọn một lời giải tất định nào đó mà chuyển cho chúng ta một không gian rất nhỏ chứa lời giải tối ưu thực sự. Thủ tục cuối cùng chỉ đơn giản là nhặt lấy một phương án tốt nhất trong đó với tìm kiếm cục bộ, chẳng hạn hệt như phương pháp thỏa mãn ràng buộc thông thường.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.