Giải thuật tiến hóa - thuật toán di truyền
Giải thuật tiến hóa - thuật toán di truyền
Nội dung:
1. Giải thuật tiến hóa
2. Thuật toán di truyền
3. Các quá trình cơ bản trong thuật toán di truyền
4. Các tham số của thuật toán di truyền
5. Cài đặt giải thuật di truyền
--------------------------------
1. Giải thuật tiến hóa
Giải thuật tiến hóa (Evolutionary Computations - EC) bao gồm: thuật toán di truyền (Genetic Algorithm - GA), thuật toán tiến hóa vi phân (Differential Evolution- DE), qui hoạch tiến hóa (Evolutionary programming - EP) và chiến lược tiến hóa (Evolution Strategies - ES) dựa trên nền tảng tiến hóa tự nhiên đó cũng là các phương pháp tự nhiên nhằm giải quyết bài toán tối ưu và tìm kiếm. Mục tiêu cơ bản của EC là cơ cấu tính toán nhằm tạo ra sự tiến hóa của quần thể gồm nhiều cá thể với mục đích quần thể sau “tốt hơn” quần thể trước. Các toán tử sử dụng trong EC bao gồm: lai ghép (crossover), đột biến (mutation) và chọn lọc (selection). Các toán tử này kết hợp với nhau trong một mô hình tiến hóa và được điều khiển bởi một vài tham số như kích cỡ quần thể, xác suất lai ghép, xác suất đột biến... Hình thức sử dụng rộng rãi EC là thuật toán di truyền (GA).
2. Thuật toán di truyền
Giống như giải thuật tiến hóa nói chung, thuật toán di truyền (GA) hình thành dựa trên quan niệm cho rằng quá trình tiến hóa tự nhiên là quá trình hoàn hảo và hợp lý nhất và tự nó đã mang tính tối ưu. Đây là một tiên đề đúng, không thể chứng minh được nhưng phù hợp với thực tế khách quan. Tính tối ưu trong tự nhiên thể hiện ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước nhờ hai quá trình cơ bản là sinh sản và chọn lọc tự nhiên. Những cá thể nào phát triển thích nghi với môi trường sẽ tồn tại và ngược lại, những cá thể nào không thích nghi với môi trường sẽ bị đào thải. Sự thay đổi của môi trường sẽ tác động đến quá trình tiến hóa và bản thân quá trình tiến hóa cũng có tác động và làm thay đổi môi trường. Cá thể mới sinh ra trong quá trình tiến hóa nhờ vào sự lai ghép ở thế hệ cha mẹ. Một cá thể mới có thể mang những đặc tính của cha mẹ ở thế hệ trước (di truyền) hoặc mang những đặc tính mới hoàn toàn (đột biến). Di truyền và đột biến là hai cơ chế quan trọng như nhau trong quá trình tiến hóa mặc dù xác suất để xảy ra hiện tượng đột biến nhỏ nhiều (hàng chục đến
hàng trăm lần tùy từng quá trình) so với hiện tượng di truyền. Mặc dù cơ chế là ngẫu nhiên nhưng thuật toán di truyền không phải là một thuật toán ngẫu nhiên. Thuật toán khai thác và tận dụng được một cách hiệu quả thông tin quá khứ để có được những kết quả mới đạt kết quả như mong muốn. Các cải tiến trong việc sử dụng thuật toán
di truyền đã làm tăng thêm hiệu quả của việc sử dụng thuật toán trong các bài toán phức tạp. Điều này thể hiện ở việc giảm thời gian tính toán ngày càng hiệu quả mà ta sẽ tìm hiểu cụ thể hơn ở dưới đây.
3. Các quá trình cơ bản trong thuật toán di truyền
a) Mã hóa dữ liệu: hay còn gọi là biểu diễn di truyền cho lời giải của bài toán: Đây là bước đầu tiên và rất quan trọng đối với việc tìm ra lời giải của bài toán. Mỗi lời giải của bài toán được biểu diễn dưới dạng một chuỗi ký tự hữu hạn hay còn được gọi là một nhiễm sắc thể. Các ký tự có thể là số nhị phân, số thập phân, … tùy vào từng bài toán cụ thể. Trong quá trình này, việc mã hóa cái gì, mã hóa như thế nào, trật tự các thành phần trong nhiễm sắc thể ra sao,… luôn là những thách thức cho những người giải bài toán.
b) Khởi tạo quần thể (xây dựng tập hợp nghiệm ban đầu): có thể ngẫu nhiên hoặc không ngẫu nhiên: Có nhiều cách để khởi tạo giá trị quần thể nghiệm ban đầu, tùy từng bài toán mà ta lựa chọn phương pháp phù hợp. Thông thường, hệ nghiệm ban đầu được chọn ngẫu nhiên trong không gian tìm kiếm. Tuy vậy, việc chọn này cũng cần phải xem xét về tương quan giữa độ thích nghi của các nhiễm sắc thể để tránh tình trạng nghiệm tìm ra là nghiệm tối ưu cục bộ hay còn gọi là cực trị địa phương. Còn vấn đề số lượng nghiệm của tập nghiệm hay qui mô của quần thể cũng cần được xem xét kỹ dựa vào độ phức tạp của bài toán, độ chính xác yêu cầu (cao hay thấp) và thời gian tính toán yêu cầu (nhanh hay chậm)
c) Xác định hàm thích nghi: hay hàm lượng giá cho mỗi nhiễm sắc thể hay chính là cho các phương án nghiệm trong tập nghiệm. Hàm này dùng để đánh giá độ thích nghi của các nhiễm sắc thể. Hàm thích nghi cần phải đánh giá được mức độ thích nghi cho tất cả các nghiệm khả thi và luôn được giả định là không âm, để thể hiện độ thích nghi của các cá thể. Công thức biểu diễn hàm cần phải thể hiện được tất cả các đặc tính mong muốn của nhiễm sắc thể, thông qua đó có thể chọn lọc được các quần thể nghiệm tốt nhất cho bài toán.
d) Quá trình lai ghép: đây là quá trình nhiễm sắc thể mới được hình thành dựa trên nhiễm sắc thể cha mẹ bằng cách lai ghép một hay nhiều đoạn nhiễm sắc thể cha mẹ với nhau. Phép lai ghép xảy ra với xác suất là p1 có thể được mô phỏng như sau:
- Chọn hai (hay nhiều) cá thể bất kỳ trong quần thể. Quần thể ở đây bao gồm các nhiễm sắc thể (cha mẹ) có độ dài bằng nhau.
- Chọn điểm lai là một điểm có vị trí bất kỳ (như nhau) trên nhiễm sắc thể chamẹ và thực hiện hoán đổi các đoạn gen của nhiễm sắc thể cha mẹ tại điểm lai này.
- Đưa hai cá thể này vào quần thể để thực hiện vào các quá trình tiến hóa tiếp theo.
Hình 1. Lai ghép hai cá thể
- Lai ghép có xét tới các đặc tính trội và lặn trong tự nhiên: Các đặc tính này được quy định trước trong khi biểu diễn cấu trúc nhiễm sắc thể. Bằng việc xem xét tới các đặc tính trội lặn, quá trình sản sinh ra các "quần thể chất lượng tốt" sẽ nhanh hơn và do đó thời gian tính toán cũng được rút ngắn.
- Lai ghép từng phần: Việc giữ lại những đoạn mã đã "tối ưu" trong nhiễm sắc thể cũng là một cách để quá trình lai ghép trở nên hiệu quả hơn
- Lai ghép có trật tự
- Lai ghép dựa trên vị trí
- Lai ghép chu trình
- Lai ghép thứ tự tuyến tính
- Lai ghép đa điểm: Với phương pháp này, chúng ta có thể cho 2 cá thể lai ghép ở 2 hay nhiều điểm lai ghép. Phương thức này làm cho thuật toán trở nên linh hoạt hơn, nhờ đó các thế hệ cá thể con cũng sẽ có chất lượng tốt hơn.
e) Quá trình đột biến: là quá trình cá thể con mang một hay một số tính trạng không có trong mã di truyền của cha mẹ. Quá trình này xảy ra với xác suất p2 (nhỏ hơn nhiều so với p1) có thể được mô tả như sau:
- Chọn ngẫu nhiên một cá thể bất kỳ trong quần thể
- Chọn một gen bất kỳ của cá thể vừa chọn
- Thay đổi giá trị gen đó (đối với cách mã hóa gen theo số nhị phân thì quá trình thay đổi giá trị là đổi giá trị từ 0 thành 1 hoặc từ 1 thành 0) rồi trả về quần thể để thực hiện các quá trình tiếp theo
Hình 2. Đột biến một nhiễm sắc thể
Tương tự như quá trình lai ghép, trong quá trình phát triển của thuật toán di truyền cũng đã được bổ sung rất nhiều cách thức để thực hiện quá trình gây đột biến ngày càng hiệu quả hơn:
- Đột biến đảo ngược (Inversion Mutation)
- Đột biến chèn (Insertion Mutation)
- Đột biến thay thế (Raplacement Mutation)
- Đột biến tương hỗ (Reciprocal Exchange Mutation)
- Đột biến dịch chuyển (Shift Mutation)
f) Quá trình chọn lọc: Quá trình mà các cá thể mới sinh ra được giữ lại hay bị loại bỏ khỏi quần thể dựa vào độ thích nghi của chúng. Độ thích nghi ở đây thường là một hàm gán một giá trị thực cho các cá thể trong quần thể. Đối với quá trình này có rất nhiều cách để xác định trình tự tính toán và thực hiện tùy vào cách lựa chọn độ thích nghi của cá thể nói riêng và của cả quần thể nói chung.
4. Các tham số của thuật toán di truyền
Kích cỡ hệ nghiệm (pop-size): số lượng cá thể phù hợp trong mỗi thế hệ Xác suất lai tạo (pc): xác suất để mỗi cá thể trong quần thể được tham gia quá trình lai ghép.
Xác suất đột biến (pm): xác suất để mỗi bit trong nhiễm sắc thể bị đột biến Thông thường, kích cỡ của quần thể phụ thuộc vào độ phức tạp của bài toán.
Bài toán càng phức tạp, nhiều ràng buộc - đơn hoặc đa mục tiêu - thì số lượng cá thể trong mỗi thế hệ càng phải lớn. Hai thông số xác suất trong quá trình di truyền có khoảng giá trị rất khác nhau. Đối với xác suất lai tạo, giá trị thường rơi trong khoảng 0,5 - 0,95 nhưng giá trị thông thường của xác suất đột biến thấp hơn nhiều, chỉ ở khoảng 0,001 - 0,05. Điều này cũng phản ánh đúng xác suất xảy ra hai quá trình trong thực tế.
Ưu điểm của thuật toán di truyền là một phương pháp tìm kiếm từ một quần thể các điểm chứ không phải một điểm. Điều này làm cho việc giải các bài toán đa mục tiêu hay việc tìm một tập hợp các phương án lân cận nghiệm trở nên dễ dàng. Thêm vào đó, việc đánh giá thông tin bằng hàm mục tiêu chứ không dùng đạo hàm hay các tri thức bổ sung cũng là một ưu điểm của thuật toán.
Hình 3. Sơ đồ quá trình tính toán của thuật toán di truyền
Nhận xét cụ thể các bước trong lưu đồ trên:
- Bước 1: Khởi tạo/lựa chọn các thông số cho quá trình tính toán: Bước này người lập trình tính toán phải lựa chọn các thông số như: số lượng cá thể trong quần thể, cách thức hóa bài toán cần tính toán dưới dạng các nhiễm sắc thể (độ dài của nhiễm sắc thể, kiểu số biểu diễn dữ liệu,…), số thế hệ tính toán, xác suất lai ghép, xác suất đột biến, hàm thích nghi,…
- Bước 2: Khởi tạo quần thể ban đầu: xác định bằng phương pháp tạo số ngẫu nhiên để tạo giá trị cho các nhiễm sắc thể cho quần thể ban đầu. Tùy vào cách biểu diễn của các nhiễm sắc thể mà ta chọn phương pháp tạo số ngẫu nhiên phù hợp
- Bước 3: Đánh giá các nhiễm sắc thể bằng hàm thích nghi đã xác định ở bước
1. Trong bước này, ngoài việc đánh giá các nhiễm sắc thể riêng rẽ, chúng ta còn có thể đánh giá độ thích nghi của một nhiễm sắc thể hay cả quần thể. Nếu một nhóm hay cả quần thể có độ thích nghi "trung bình" (theo tiêu chí của từng trường hợp của người lập trình) thấp thì có thể loại nhóm nhiễm sắc thể hay quần thể đó ra khỏi quá trình di truyền.
- Bước 4: Thực hiện quá trình di truyền thông qua các cơ chế lai ghép và đột biến. Có thể thực hiện lần lượt hai quá trình này hoặc thực hiện đồng thời theo các phương pháp đã đề cập bên trên. Trong quá trình thực hiện thuật toán di truyền, giai đoạn này là giai đoạn mà mỗi người có thể thực hiện theo những phương pháp rất khác nhau. Giai đoạn này cũng là giai đoạn quyết định tới sự thành công của thuật toán. Người thực hiện cũng có thể đưa ra những phương thức tiến hành lai ghép hay đột biến mới trong giai đoạn này. Trong quá trình thực hiện, để có được một bộ các thông số lai ghép hay đột biến hiệu quả, người lập trình thường phải trải qua nhiều bước tính toán thử. Khâu này phụ thuộc nhiều vào kinh nghiệm và kỹ năng tính toán của người lập trình.
- Bước 5: Tạo quần thể mới bằng quá trình chọn lọc. Quá trình này cũng dựa vào đánh giá các nhiễm sắc thể thông qua hàm thích nghi. Cá thể nào có độ thích nghi cao sẽ được giữ lại cho thế hệ kế tiếp. Cũng giống như ở bước 3, chúng ta có thể sử dụng những hàm thích nghi phù hợp để đánh giá từng cá thể đơn lẻ hoặc cả một nhóm các cá thể. Sau quá trình này, nhóm cá thể nào thỏa mã tiêu chuẩn đánh giá với mức độ từ cao xuống thấp sẽ được dưa vào quần thể mới.
- Bước 6: Đánh giá quần thể vừa có được trong bước 5. Thông thường có hai tiêu chí để dừng quá trình di truyền tại bước này. Thứ nhất, độ thích nghi của từng cá thể và cả quần thể thỏa mãn một điều kiện hội tụ đã được đặt ra ban đầu. Các điều kiện hội tụ thể hiện mức độ chấp nhận được của kết quả tìm được. Thứ hai, quần thể mới tạo thành là quần thể ở thế hệ thứ (N+1) với N là số thế hệ dự định tính toán đã giả thiết ban đầu. Trong khi thực hiện các quá trình di truyền, những người tính toán có thể đưa ra những tiêu chí riêng để dừng quá trình di truyền. Các tiêu chí đưa ra góp phần quyết định tới thành công của thuật toán.
5. Cài đặt giải thuật di truyền [Tham khảo tại đây]
>> Xem thêm phần cài đặt và ứng dụng thuật toán di truyển Tại đây
#