Omarine Schoolsheet 2016 phiên bản 2.0 sử dụng thuật giải di truyền để xử lý triệt để bài toán Thời khóa biểu. Khác biệt quan trọng giữa thuật giải di truyền và các phương pháp tối ưu cổ điển là thuật giải di truyền xử lý tổng thể một quần thể các lời giải dựa vào quá trình tiến hóa tự nhiên với máy học, trong khi các phương pháp tối ưu cổ điển hoặc chỉ xử lý một điểm trong không gian hoặc đơn giản là mượn máy tính như một công cụ tính nhanh các bài toán đã có lý thuyết áp dụng trong một phạm vi hẹp
Hình trên là cửa sổ hiển thị tiến độ và dữ liệu của thuật giải di truyền trong quá trình tạo thời khóa biểu. Phần thông tin về thuật giải di truyền chia thành 3 nhóm
Population: Quần thể trải qua 4 vòng(Round) xử lý các ràng buộc, thời điểm trong hình trên là đang ở vòng cuối cùng. Popsize là số cá thể trong quần thể. Generations là số thế hệ.
Violates of best Individual: Nhóm này trình bày số vi phạm ràng buộc của cá thể tốt nhất trong quần thể tại thời điểm đang xét, chi tiết cho từng ràng buộc.
Mutant parameters: Các tham số đột biến điều chỉnh được của hệ thống
Quần thể có kích thước thay đổi
Một điều quan trọng của thuật giải di truyền là phải cân đối giữa tính đa dạng của quần thể và độ chọn lọc, là hai thuộc tính trái ngược nhau. Quần thể quá đa dạng thông thường làm suy yếu chọn lọc một cách tương đối, như thế sẽ không tiến hóa được. Ngược lại, chọn lọc quá mạnh sẽ phiến diện, dễ bị lừa vào tối ưu cục bộ, diễn giải theo ngôn ngữ của lý thuyết lược đồ thì các biến đổi sau này dù thế nào cũng không ra khỏi những lược đồ mà không chứa lời giải tối ưu. Cách thức chọn lọc của phép tái sinh tỏ ra kém hiệu quả do tạo ra nhiều bản sao y hệt của cùng một cá thể, làm giảm tính phong phú của quần thể và gây bất lợi lớn trong thời kỳ trăm hoa đua nở, là thời kỳ mà cần mở rộng lược đồ của không gian tối ưu toàn cục. Mặt khác, những cá thể trùng lặp lại sinh sản nhiều, chúng đẻ ra những siêu cá thể có độ thích nghi cao bất thường. Quần thể chỉ còn lại một ít các gia đình đơn điệu và thuật giải nhanh chóng hội tụ về tối ưu cục bộ, việc tìm kiếm lời giải tối ưu toàn cục trở thành thất bại. Vậy tại sao các siêu cá thể lại có hại? Thứ nhất, độ thích nghi của chúng chỉ là độ thích nghi giả do hàm mục tiêu được xác định không hoàn toàn chính xác. Ngay cả trường hợp ánh xạ là rõ ràng có thể vẫn cần đến các mục tiêu trung gian trong từng giai đoạn của các bài toán con mà trong đó tồn tại một vài mục tiêu không thật sự tường minh. Còn lại những bài toán đơn giản mà tính được chính xác hàm mục tiêu thì dường như không cần đến thuật giải di truyền và máy học. Khi tối ưu toàn cục chưa được định hình thì các siêu cá thể hầu như chắc chắn gây lệch lược đồ. Thứ hai, chúng có độ thích nghi cao chỉ có tính chất thời điểm nhưng lại không mang trong mình gen di truyền tiềm năng.
Thuật giải di truyền với quần thể có kích thước thay đổi sẽ dung hòa cả hai mục đích trên. Vào thời kỳ sinh trưởng(thường trong các thế hệ đầu) kích thước quần thể tăng lên, có lúc lên tới vài trăm cá thể, lớn hơn nhiều so với kích thước khởi tạo quần thể trong chương trình là 20. Kích thước tăng là do nhu cầu sinh sản tự nhiên của quần thể, các phép lai tạo và đột biến có khả năng sinh nhiều con có độ thích nghi trên trung bình được sống trong quần thể mới. Quần thể trở nên đa dạng, các lược đồ được hình thành phong phú. Sự đa dạng có tác dụng ngăn chặn cực tiểu(hoặc cực đại) cục bộ. Chúng ta hình dung một trái bóng lăn trên sân cỏ, nó lăn xuống một vùng trũng nhỏ sẽ là cực tiểu cục bộ vì đó chưa phải là điểm thấp nhất trên toàn sân cỏ. Nhưng cùng lúc đó có nhiều trái bóng khác còn tiếp tục lăn trên các vùng tối ưu trải rộng. Đến giai đoạn hội tụ, sự đa dạng không còn là cần thiết nữa, thay vào đó cần tăng cường chọn lọc. Bước vào giai đoạn này quần thể chỉ còn đi theo một hướng cuối cùng, nhu cầu phát sinh lược đồ không còn quan trọng nữa. Quần thể tăng trưởng chậm hơn, số cá thể dưới trung bình nhiều hơn làm kích thước quần thể giảm xuống, điều này có lợi lớn là giảm chi phí tính toán. Thuật giải bắt đầu hội tụ và kích thước quần thể ít thay đổi(tuy nhiên trong một vài tình huống ngẫu nhiên hiếm, kết hợp hoặc không kết hợp với tham số hệ thống, quần thể lại tìm thấy hướng đi mới tốt hơn và bùng nổ tiếp tục, sau đó đi theo hướng hội tụ mới). Chúng ta lại hình dung về một bài toán tối ưu cực đại, mục tiêu là leo lên đỉnh núi cao nhất. Cực đại cục bộ xảy ra khi chúng ta trèo lên một ngọn đồi. Còn không, khi một nhóm đã tới được ngọn núi cao nhất thì khả năng leo núi nhanh lại là điều mong ước. Trong quần thể có kích thước thay đổi, các khái niệm về tuổi và thời gian sống của các cá thể tạo nên phép chọn không tầm thường. Cách chọn này có thể loại bỏ các siêu cá thể gây hại. Những siêu cá thể này khi hết khả năng sinh sản(trái bóng đã nằm yên trong vùng trũng nhỏ) vẫn tồn tại qua vài thế hệ và trở nên già, khi tuổi của chúng vượt quá thời gian sống, chúng sẽ bị loại khỏi quần thể cho dù có độ thích nghi cao. Khi quần thể đi tới lân cận tối ưu toàn cục, các siêu cá thể lại đáng tuyên dương. Tại sao lại như vậy? Đơn giản vì chúng ta muốn thế. Các toán tử di truyền bao gồm lai tạo, đột biến tri thức và đột biến ngẫu nhiên được điều chỉnh để tăng tốc về cuối. Khi các siêu cá thể hết khả năng sinh sản thì cũng là lúc bài toán được giải quyết xong.
Máy thông minh hơn hay con người thông minh hơn?
Trả lời: Máy thông minh hơn.
Chúng ta biết rằng một số lớp bài toán có thể giải được bằng lý thuyết có những hạn chế. Chẳng hạn lớp bài toán Quy hoạch tuyến tính đòi hỏi hàm mục tiêu và các hàm ràng buộc phải là tuyến tính, tập lời giải phải là tập lồi. Nhưng thuật giải di truyền có thể giải bất cứ bài toán tối ưu nào. Không giống các phương pháp tiến hóa khác nặng về áp đặt tri thức điều khiển, chọn lọc tham lam và tuyệt chủng, chỉ phù hợp với các bài toán ít phức tạp, thuật giải di truyền dành để giải các bài toán khó hơn, sử dụng chọn lọc tự nhiên và bảo tồn, tập trung nhiều vào máy học hay trí tuệ máy, trí tuệ nhân tạo. Chọn cả những cá thể yếu nhất và loại bỏ cả những cá thể mạnh nhất, tôn trọng ngẫu nhiên là cốt lõi của thuật giải di truyền.
Mặc dù chương trình máy tính là do con người làm ra nhưng máy có thể học độc lập với con người, nó học được những ánh xạ phi tuyến, rời rạc phức tạp một cách kỳ diệu mà con người phải bó tay.
Phần trên đã giới thiệu về quần thể. Chúng ta chỉ có thể mô tả các quá trình sinh sản, chọn lọc, rồi tiến hóa và đi vào hội tụ của quần thể nhưng chính xác khi nào kích thước quần thể sẽ tăng và sẽ tăng lên bao nhiêu, chắc chắn quần thể sẽ tiến hóa hay thoái hóa trong thế hệ kế tiếp, khi nào hội tụ thì chỉ máy tính mới có thể biết. Bản thân tôi cũng không biết. Nó thông minh hơn tôi đấy!
Tiến hóa của tiến hóa, tối ưu hóa tối ưu
Nguyên lý tiến hóa của thuật giải di truyền là sinh sản và chọn lọc. Nhưng bản thân chiến lược tiến hóa cũng phải được tiến hóa cho phù hợp với từng giai đoạn của quá trình tiến hóa tổng thể. Kích thước quần thể thay đổi là một ví dụ tốt về khả năng tự điều chỉnh số cá thể. Nhưng như thế chưa đủ. Các tham số khác của hệ thống như xác suất thi hành các toán tử đột biến, tốc độ đột biến, nhiệt độ cũng cần được thay đổi. Xem xét khởi tạo lại thế hệ cũng đáng được quan tâm.
Nhiệt độ luyện thép, tuyển chọn hơn thanh lọc, tính nhân văn và sâu sắc
Tuyển chọn là một cải tiến của Omarine Schoolsheet 2016 2.0 so với thuật giải di truyền gốc(từ nay gọi là thuật giải di truyền cổ điển). Thuật giải di truyền cổ điển chỉ chọn lọc đầu ra(thanh lọc) sau khi các cá thể đã sinh sản trong quần thể. Về nguyên lý, trong những điều kiện nhất định ít nhất là phải giảm xác suất thi hành các toán tử sinh sản xuống rất thấp sao cho tỉ lệ sinh ra các con xấu không triệt tiêu thanh lọc trong vai trò cải thiện quần thể thì thuật giải vẫn có thể hội tụ. Ngược lại thanh lọc chỉ thực hiện trên một quần thể yếu kém và quần thể ngày càng suy thoái. Ngay cả khi điều kiện hội tụ được đảm bảo, thời lượng cho quá trình tiến hóa là rất lớn và số thế hệ cần thiết coi như tăng đến vô hạn. Như vậy đối với yêu cầu thực tế là không chấp nhận được. Omarine Schoolsheet 2016 2.0 bổ sung cơ chế tuyển chọn đầu vào. Khác với các chiến lược tiến hóa nghiêm khắc và phiến diện yêu cầu con phải hơn cha mẹ, chương trình chấp nhận cả những đứa con “xấu” làm thành viên của quần thể. Như đã nêu trên, một cá thể xấu chỉ là đánh giá chủ quan của hàm thích nghi(coi như không bao giờ chuẩn xác), mặt khác chất liệu di truyền quan trọng hơn độ thích nghi nhất thời. Đó là tính nhân văn và sâu sắc.
Tuy nhiên, nhận tất cả chắc chắn sẽ bao gồm những cá thể xấu thật rồi lại phải loại bỏ chúng sẽ gây hệ lụy. Chương trình sử dụng nhiệt độ luyện thép để điều chỉnh. Nhiệt độ càng thấp thì rủi ro nhận một thành viên xấu càng ít đi. Nhiệt độ được tính như sau:
temperature = MAX_T / generations;
Generations là số thế hệ thực tế.
MAX_T là hằng nhiệt độ lớn nhất, là giá trị của biến nhiệt độ trong thế hệ đầu tiên
Vào thời kỳ đầu của quá trình tiến hóa, số thế hệ nhỏ và nhiệt độ là cao. Số thành viên mới được chấp nhận nhiều, điều này phù hợp yêu cầu cần đa dạng hóa quần thể ban đầu. Số thành viên mới được chấp nhận như thế ít dần khi nhiệt độ hạ thấp trong những giai đoạn sau.
Xác suất nhận được tính theo công thức:
p = exp((nViolatesP - nViolatesC) / temperature);
nViolatesP là giá trị hàm của số vi phạm ràng buộc của cha mẹ
nViolatesC là giá trị hàm của số vi phạm ràng buộc của con
Nếu con vi phạm càng nhiều hơn cha mẹ, hoặc con vi phạm nhiều hơn cha mẹ và nhiệt độ càng thấp thì xác suất nhận p càng nhỏ. Tất nhiên nếu con hơn cha mẹ thì luôn được chấp nhận. Nếu hàm thích nghi(là biến thể của hàm vi phạm) không chính xác cũng không thành vấn đề vì đây mới chỉ là tuyển chọn đầu vào. Chúng ta còn nhiều biện pháp di truyền khác, trong đó có chọn lọc tại cuối mỗi thế hệ.
Xác suất đột biến tri thức tăng lên theo hàm số mũ
Chọn lọc sẽ tăng lên trong các thế hệ về sau. Đi cùng với tăng cường chọn lọc là áp dụng mạnh hơn các toán tử đột biến heuristic. Công thức xác suất đột biến như sau:
p = BASE + INCREASE / (1 + exp((MAX_GENERATIONS_STANDARD - generations) /\
(MAX _GENERATIONS_STANDARD / RATE_GENERATIONS)));
BASE và INCREASE là các hằng đặc trưng cho xác suất cơ bản và phần xác suất tăng lên
MAX_GENERATIONS_STANDARD là hằng đặc trưng cho số thế hệ chuẩn tối đa
RATE_GENERATIONS là hằng tỉ lệ về số thế hệ, chương trình định nghĩa giá trị này là 10
Công thức trên đảm bảo ban đầu số hạng bên phải của tổng xác suất gần như bằng 0. Xác suất p chỉ có giá trị là BASE
Trong các thế hệ cuối, số hạng bên phải của tổng xác suất tăng lên rất nhanh và tiến tới giới hạn là INCREASE
Xác suất đột biến ngẫu nhiên giảm xuống theo hàm số mũ
Ngược lại với đột biến tri thức, đột biến ngẫu nhiên cần lớn lúc đầu để đa dạng hóa quần thể và giảm mạnh trong giai đoạn cuối để tránh hỗn loạn
p = BASE * (1.0 / (1 + exp((generations- MAX_GENERATIONS_STANDARD) /\
(MAX _GENERATIONS_STANDARD / RATE_GENERATIONS))) + RATE_PROBABILITY_REDUCE));
RATE_PROBABILITY_REDUCE là hằng tỉ lệ về xác suất, nhỏ hơn 1
Công thức trên đảm bảo ban đầu thừa số bên phải của tích xác suất gần như bằng 1 + RATE_PROBABILITY_REDUCE. Xác suất p đạt giá trị lớn nhất là BASE * (1 + RATE_PROBABILITY_REDUCE)
Trong các thế hệ cuối, thừa số bên phải của tích xác suất giảm xuống rất nhanh và tiến tới giới hạn là RATE_PROBABILITY_REDUCE, xác suất p trở thành BASE giảm đi 1 / RATE_PROBABILITY_REDUCE lần
Share on Twitter Share on Facebook Share on Linked In
Contact: tuyen@omarine.org
Comments
There are currently no comments
New Comment