Giải thuật di truyền giải bài toán người du lịch (TSP)

Giải thuật (thuật toán) di truyền (GA).

Thuật toán di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến hóa như di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo.

Di truyền là hiện tượng chuyển những tính trạng của cha mẹ cho con cái thông qua gen của bố mẹ. Trong sinh học, di truyền chuyển những đặc trưng sinh học từ một sinh vật cha mẹ đến con cái và nó đồng nghĩa với di chuyển gen, gen thừa nhận mang thông tin sinh học hay thông tin di truyền.

Tiến hóa nói đến quá trình hoàn thiện, biến đổi dần để hoàn thiện hơn các bộ phận, chức năng của các sinh vật để phù hợp hơn với điều kiện sinh tồn. Trong sinh học, tiến hóa là sự thay đổi đặc tính di truyền của một quần thể sinh học qua những thế hệ nối tiếp nhau. Các quá trình tiến hóa làm nảy sinh sự đa dạng ở mọi mức độ tổ chức sinh học bao gồm loài, các cá thể sinh vật và cả các phân tử như ADN và protein.

Giải thuật di truyền (GA) là phương pháp tìm kiếm tối ưu ngẫu nhiên bằng cách mô phỏng theo sự tiến hóa của con người hay của sinh vật. GA được ứng dụng rộng rãi trong giải quyết các bài toán tối ưu, như bài toán người du lịch, bài toán người bán hàng, và nhiều bài toán khác.

 

Bài toán người du lịch

Bài toán người du lịch là một bài toán quan trọng trong lĩnh vực tối ưu hóa và khoa học máy tính. Hãy cùng tìm hiểu về nó!

Mô tả bài toán:

+ Một người du lịch muốn thăm quan n thành phố T1, T2, …, Tn.

+ Người du lịch xuất phát từ một thành phố bất kỳ và muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua duy nhất một lần rồi quay trở lại thành phố xuất phát.

+ Gọi Cij là chi phí đi từ thành phố Ti đến Tj.

+ Yêu cầu: Tìm một hành trình thỏa mãn yêu cầu trên sao cho tổng chi phí là nhỏ nhất.

 

Thuật toán GA giải bài toán người du lịch

Bước 1: Tạo quần thể

Bước 2: Đánh giá

- Thoả mãn điều kiện (tìm được giá trị độ dài quãng được tốt nhất (nhỏ nhất) hoặc tiến hoá đủ 1000 thế hệ (số thế hệ do người dung thiết lập)) => Bước 6

-  Chưa thoả điều kiện => Bước 3

Bước 3: Lựa chọn (chọn các cá thể có độ thích nghi tốt nhất (quãng đường ngắn nhất) => Bước 4

Bước 4: Lai ghép => Bước 5

Bước 5: Đột biến => Bước 2 (lặp lại)

Bước 6: Kết thúc.

Cài đặt thuật toán bằng Java

1- Tạo Project

 

2- Class GA

 

3- Class GATSP (class main)

 

4- Kết quả

Kết luận:

Thuật toán di truyền (Genetic Algorithm - GA) là một phương pháp tối ưu hóa dựa trên nguyên tắc của tiến hóa sinh học. Dưới đây là một số ứng dụng thú vị của thuật toán di truyền:

- Giải bài toán người du lịch (Traveling Salesman Problem - TSP): Trong bài toán này, người du lịch cần tìm hành trình qua tất cả các thành phố một lần duy nhất và quay trở lại thành phố xuất phát sao cho tổng chi phí là nhỏ nhất. GA có thể áp dụng để tìm lời giải gần đúng cho TSP.

- Tối ưu hóa hàm số: GA có thể tìm kiếm giá trị tối ưu của hàm số trong không gian nhiều biến.

- Lập lịch sản xuất: Trong việc lập lịch sản xuất, GA có thể tối ưu hóa thời gian sản xuất, tối thiểu hóa chi phí và tối đa hóa hiệu suất.

- Thiết kế mạng neuron: GA có thể tối ưu hóa trọng số của mạng neuron để đạt được hiệu suất tốt nhất.

- Tối ưu hóa kích thước bộ lọc trong xử lý ảnh: GA có thể tìm kích thước và hình dạng của bộ lọc để cải thiện chất lượng ảnh.

- Tối ưu hóa các tham số trong máy học: GA có thể tìm giá trị tối ưu cho các tham số của mô hình máy học.

Thuật toán di truyền là một công cụ mạnh mẽ để giải quyết các bài toán tối ưu và tìm kiếm lời giải gần đúng trong nhiều lĩnh vực khác nhau.

* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*

Read More

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

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ể

Tuy nhiên trong quá trình tồn tại và phát triển, thuật toán di truyền đã được bổ sung rất nhiều các phương pháp lai ghép để nhằm thích ứng với nhiều kiểu bài toán và cũng là để tăng hiệu quả của thuật toán. Có thể kể một số phép lai cải tiến như sau:
- 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

#

* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*

Read More

Thuật toán di truyền và ứng dụng

Thuật toán di truyền và ứng dụng

Đầu thế kỷ 19, một lý thuyết được nêu ra bởi nhà khoa học Darwin: “Loài người có họ hàng với loài vượn” đã làm chấn động nền tảng khoa học. Trong đó, ý tưởng chủ đạo là sự tiến hóa của các muôn loài dựa trên sự chọn lọc tự nhiên. Lấy cảm hứng từ lý thuyết này, các nhà khoa học máy tính đã phát triển một thuật toán phỏng theo ý tưởng này nhằm giải quyết các bài toán tìm kiếm tối ưu có không gian cực lớn mà phương pháp vét cạn đơn thuần không giải quyết nổi.

GIẢ THUYẾT NHỮNG CON KHỈ VÀ SHAKESPEARE

Giả thuyết này được tạo ra bởi Nick Hoggard nói rằng khở đầu từ 100 con khỉ, số lượng khỉ sẽ gấp đôi sau vài ngày. Nếu một con khỉ, giả sử rằng mỗi giây gõ được 1 ký tự, và mỗi trang giấy là 2000 ký tự. Xác xuất chọn lựa để gõ 1 phím trên bàn phím của một con khỉ là như nhau. Với một giả thiết như vậy, thì sẽ mất khoảng 2,737,850 tỷ tỷ tỷ tỷ năm để có thể tạo ra một văn bản giống hệt với toàn bộ công trình văn học của Shakespeare.

Chúng ta không đi sâu vào giả thuyết này. Chỉ xét đơn cử một ví dụ: Giả sử rằng ta sinh ngẫu nhiên các chuỗi ký tự cùng độ dài với chuỗi “to be or not to be”, 18 ký tự kể cả khoảng trắng. Và giả sử các lựa chọn sinh ngẫu nhiên chỉ gồm 27 lựa chọn bao gồm các ký tự từ a đến z và một khoảng trắng. Như vậy số lượng các chuỗi ngẫu nhiên có thể sinh ra là 27^18 (lũy thừa) = 58,149,737,003,040,059,690,390,169. Rõ ràng đối với một số lượng các trường hợp như vậy, vét cạn là phương pháp hoàn toàn không khả thi.

Thuật toán di truyền đã được giới thiệu để giải quyết các bài toán tối ưu tìm kiếm trong không gian cực lớn như đã nếu ở trên.

THUẬT TOÁN DI TRUYỀN (GENETIC ALGORITHM)

Tư tưởng thuật toán này dựa trên ý tưởng về lai tạo và biến dị để tạo ra cá thể tốt hơn như sau:
Giả sử rằng khởi điểm ta có một quần thể các các thể. Các cá thể có thể “lai tạo”(crossover) với nhau và “biến dị”(mutate) để tạo ra cá thể mới. Các cá thể mới tốt hơn và dần thay thế những cá thể cũ. Như vậy sau một số thế hệ tiến hóa, chúng ta sẽ dần tạo ra cá thể tối ưu.

Ở đây sẽ có một số câu hỏi đặt ra, đó là:

Thế nào là tối ưu?

Đó là trạng thái mục tiêu mà ta cần đạt được. Nghĩa là, ta cần sinh ra một cá thể có trạng thái ứng với trạng thái mục tiêu. Ví dụ như sinh ra một chuỗi có nội dung là “to be or not to be”.

Thế nào là cá thể tốt hơn cá thể khác?

Đó là sự đánh giá độ mạnh yếu (fitness) được định nghĩa dựa trên khoảng cách từ một cá thể đến cá thể mục tiêu. Khoảng cách càng gần thì cá thể càng tốt.

Thế nào là sự lai tạo?

Mỗi cá thể được mã hóa thành một chuỗi các gene gọi là chromosome. Trong máy tính, chromosome thường được mô tả là một chuỗi bit (mỗi gene là một bit) hoặc một chuỗi các ký tự (mỗi gene là một ký tự). Sự lai tạo được thực hiện bằng cách lựa chọn hai cá thể trong quần thể để lai tạo. Để mô tả chọn lọc tự nhiên, cũng như để hướng tới việc cá thể sau tốt hơn cá thể trước, việc chọn lựa sẽ ưu tiên chọn các cá thể mạnh hơn hay nói cách khác, các cá thể mạnh hơn có nhiều cơ hội được lựa chọn để lai tạo hơn. Sự lai tạo giữa hai cá thể thực chất là việc ghép phần đầu chromosome của cá thể này với phần đuôi chromosome của cá thể kia.

Làm sao để mã hóa thành các chromosome?

Tùy vào từng bài toán sẽ có những cách mã hóa khác nhau. Đây cũng chính là mấu chốt của vấn đề, nếu ta có thể mã hóa bài toán thành dạng chromosome, bài toán có thể giải quyết bằng thuật giải di truyền.

Biến dị là gì?

Việc lai tạo đơn giản là các sự kết hợp giữa 2 chromosome cũ với nhau đến một lúc nào đó sẽ bị bão hòa và không thể tạo ra phần tử mới nữa. Lúc này đòi hỏi phải có một phẩn tử hoàn toàn mới để cung cấp sự đa dạng cho quần thể. Sự biến dị sẽ tạo nên cá thể mới so với quần thể, đảm bảo tính đa dạng cho quần thể. Sự biến dị không phải lúc nào cũng xảy ra mà chỉ xảy ra ở một tỷ lệ nhất định.

BÀI TOÁN SINH CHUỖI “TO BE OR NOT TO BE”.

• Trạng thái mục tiêu chính là chuỗi “to be or not to be”.
• Các trạng thái là các chuỗi được sinh ngẫu nhiên có cùng độ dài. Mỗi chuỗi này biểu diễn cho một chromosome bao gồm các gene nối tiếp nhau, mỗi gene là một ký tự. Sự lai tạo có thể được hình dung như sau:

• Nếu việc lai tạo được thực hiện ở chính giữa chuỗi, ta có cá thể mới sinh ra bằng cách lấy nửa đầu chuỗi 1 ghép với nửa sau chuỗi 2 để có: “ABCEDD”.
• Sự biến dị thực chất chỉ là việc thay đổi một số gene trong chuỗi được sinh ra. Ví dụ ký tự đầu của chromosome “ABCEDD” bị biến dị thành “ABCEFD”.

• Fitness của một trạng thái có thể được định nghĩa là số lượng các ký tự giống với trạng thái mục tiêu

THUẬT TOÁN

1. Khởi tạo quần thể ngẫu nhiên
2. Lặp:

        - Tính fitness cho mỗi cá thể so với mục tiêu
        - Lựa chọn ngẫu nhiên 2 cá thể theo quy luật chọn lọc tự nhiên. Ở đây, sau khi update fitness cho từng cá thể, ta tạo ra một mating pool để lấy 2 phần tử sao ngẫu nhiên từ pool này cho cá thể mạnh hơn có cơ hội được chọn lựa cao hơn.

Giải thuật sẽ được thực hiện qua các bước sau:

• Khởi tạo quần thể: Sinh ra ngẫu nhiên một quần thể gồm n cá thể (trong đó n là lời giải cho bài toán).
• Tính giá trị thích nghi: Ước lượng độ thích nghi của mỗi cá thể.
• Điều kiện dừng: Kiểm tra điều kiện để kết thúc giải thuật.
• Chọn lọc: Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn).
• Trao đổi chéo: Với một xác suất được chọn, trao đổi chéo hai cá thể bố mẹ để tạo ra một cá thể mới.
• Đột biến: Với một xác suất đột biến được chọn, biến đổi cá thể mới.
• Chọn kết quá: Nếu thỏa mãn điều kiện dừng thì giải thuật kết thúc và chọn được lời giải tốt nhất trong quần thể hiện tại.

Ta có thể thấy rằng, khi Điều kiện dừng chưa được thỏa mán, quần thể mới sẽ liên tục được tạo ra bằng cách lặp lại 3 bước Chọn lọc, Trao đổi chéo và Đột biến.

GAs có 2 điều kiện dừng cơ bản:

• Dựa trên cấu trúc nhiễm sắc thể, kiểm soát số gene được hội tụ, nếu số gene được hội tụ tại một điểm hoặc vượt quá điểm đó thì giải thuật kết thúc.
• Dựa trên ý nghĩa đặc biệt của nhiễm sắc thể, đo sự thay đổi của giải thuật sau mỗi thế hệ, nếu thay đổi này nhỏ hơn một hằng số xác định thì giải thuật kết thúc.

Ví dụ:

• Có 5 cá thể A,B,C,D,E lần lượt có fitness như sau: 1, 3, 2, 0, 4. 
• Như vậy mating pool như sau: A, B, B, B, C, C, E, E, E, E. 
• Rõ ràng nếu ta lấy ngẫu nhiên 1 phần tử trong pool này, tỷ lệ chọn ra E sẽ là cao nhất.
• Thực hiện lai ghép để tạo ra cá thể mới
• Thay thế cá thể cũ bằng cá thể mới tạo ra
• Nếu cá thể mới giống với mục tiêu hoặc giống ở mức chấp nhận được thì dừng. Ở đây, rất có thể chúng ta không tìm được kết quả tối ưu hoặc sẽ rất lâu mới tìm thấy trạng thái này, như vậy ta có quyền dừng ở trạng thái chấp nhận được để tiết kiệm thời gian.

THIẾT KẾ THUẬT TOÁN:

// khởi tạo quần thể với số lượng n cá thể, mỗi cá thể có chiều dài k
InitializePopulation(int len, int nPopulation);
while (foundTarget){
// tạo mating pool
var matingPool = UpdateFitnessAndCreateMatingPool();
// lấy 2 phần tử dựa vào mating pool
var p1 = population[matingPool[_rnd.Next(pool.Count)]];
var p2 = population[matingPool[_rnd.Next(pool.Count)]];
// ngẫu nhiên tìm điểm cắt
var splitPoint = _rnd.Next(_target.Length - 2) + 1;
// lai tạo để tạo ra phần tử mới
var newDNA = p1.CrossOver(p2, splitPoint);
// biến dị dựa trên tỷ lệ biến dị
newDNA.Mutate(mutationRate, materials);
// thay thế phần tử cũ
population[i] = newDNA;
// kiểm tra điều kiện dừng
if (newDNA.CompareTo(target) == target.Length)
foundTarget = true;
}

Như vậy, ta cần định nghĩa thêm một class DNA để đại diện cho một cá thể trong quần thể:

class DNA
{
public char[] Content { get; private set; } // chuỗi gene
// lai tạo ra dna mới
public DNA CrossOver(DNA dna, int splitPoint);
// biến dị theo tỷ lệ
public void Mutate(double mutationRate);
// hàm tính khoảng cách tới DNA khác
// hỗ trợ việc tính fitness
public int CompareTo(char[] content);
}

***********


Bài toán: Guessing Password — Đoán mật khẩu

Nào chúng ta bắt đầu ứng dụng giải thuật di truyền vào giải quyết bài toán đoán mật khẩu.

Về bài toán, sử dụng những ký tự trong bảng chữ cái để tái tạo lại mật khẩu. Cụ thể, ở bài này chúng ta sẽ bắt đầu với những ký tự: a-z, A-Z, !. để tái tạo nên mật khẩu: “Hello World!”.

Các bước giải bài toán:

• Khởi tạo quần thể: Sinh ra ngẫu nhiên một đoạn dài 11 ký tự (dài bằng với mục tiêu “Hello World”.
• Tính giá trị thích nghi: Đếm số ký tự trùng giữa đoạn tạo ra và “Hello World”.
• Điều kiện dừng: Kiểm tra xem số ký tự trùng bằng 11 hay không.
• Chọn lọc: Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn).
• Trao đổi chéo (Không thực hiện ở bài toán này): Với một xác suất được chọn, trao đổi chéo hai cá thể bố mẹ để tạo ra một cá thể mới.
• Đột biến: Với một xác suất đột biến được chọn, biến đổi cá thể mới.
• Chọn kết quá: Khi số ký tự trùng bằng 11 thì dừng giải thuật.

Chromosomes và Gene

Trong sinh học, nói một cách khái quát, trong một Chromosomes (nhiễm sắc thể) sẽ có thể chứa rất nhiều loại gene khác nhau.

Ở bài toán của chúng ta, tất cả những trình tự đoạn 11 ký tự ( độ dài bằng với “Hello World”) được gọi là Chromosomes. Và mỗi loại ký tự sẽ đại diện cho 1 loại Gene khác nhau.

geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
target = "Hello World"

Đầu tiên chúng ta khai báo biến geneSet chứa các ký tự trong bảng chữ cái, mỗi ký tự đại diện cho một loại Gene. Cùng với đó, khai báo biến target là đoạn ký tự mục tiêu “Hello World”.

Bước 1: Khởi tạo quần thể

import random

def initialize_chromosomes(length):
    chromosomes = []
    while len(chromosomes) < length:
        sampleSize = min(length - len(chromosomes), len(geneSet))
        chromosomes.extend(random.sample(geneSet, sampleSize))
    return ''.join(chromosomes)

Sử dụng random.sample để tạo ngẫu nhiên từ geneSet theo độ dài cho trước. Chúng ta có thể có test bằng initialize_chromosomes(11). Kết quả sẽ có dạng: ‘yTtumWSgfkM’

Chú ý: Vòng While sinh ra nhằm xử lý vấn đề nếu độ dài của Chromosomes dài hơn số lượng loại Gene ban đầu

Bước 2: Tính giá trị thích nghi

Chúng ta thấy rằng, Chromosomes có khả năng là những trường hợp như:

• Sekmo xosmd
• Seklo Wocle
• Fello Wosld
• Gello World
• Hello World

Có thể nhận ra ngay đoạn cuối cùng là đoạn chính xác. Nhưng làm sao chúng ta có thể “đo” được độ tối ưu của Chromosomes này?

Hàm lỗi (error function/ cost function/loss function) là một hàm số giúp đo độ tối ưu của một Chromosome. Ở hàm này, chúng ta đang hướng tới giá trị càng nhỏ càng tốt.

Với bài toán Đoán mật khẩu, để đo độ tối ưu, chúng ta đếm số kí tự sai khác trên cùng vị trí giữa Chromosome và đoạn kí tự mục tiêu “Hello World”. Vì vậy, hàm lỗi ở đây sẽ tối ưu ở số kí tự sai khác bằng 0.

Dùng quy luật trên để tính sai khác cho các trường hợp Chromosomes trên:

• Sekmo xosmd(6)
• Seklo Wocle(4)
• Fello Wosld(2)
• Gello World(1)
• Hello World(0)

def error_function(chromosome):
    return len(target) - sum(1 for expected, actual \
                             in zip(target, chromosome)  \
                             if expected == actual)

Hàm error_function sẽ tính số ký tự sai khác ở cùng một vị trí giữa Chromosome và “Hello World”. Có thể test hàm trên như sau: error_function(“Hello World”) sẽ cho kết quả bằng 0.

Bước 3: Điều kiện điểm dừng

Kiểm tra điều kiện điểm dừng là error_function có bằng 0 hay không.

Bước 4: Tiến hóa

Trong bước này, chúng ta sẽ gộp chung cả 3 kỹ thuật: chọn lọc, trao đổi chéo và đột biến. Mục tiêu của bước này là tạo ra thế hệ mới tối ưu hơn thế hệ cũ. Độ tối ưu sẽ được đo theo hàm lỗi. Chúng ta có thể mường tượng ra rằng, đây là một vòng lặp, mỗi vòng lặp sẽ thực hiện 3 kỹ thuật trên, sau đó check điều kiện dừng. Nếu không đáp ứng được thì vòng lặp sẽ tiếp tục cho đến khi đáp ứng được thì thôi.

Ở bài toán này, chúng ta sẽ chỉ sử dụng chọn lọc và đột biến. Phần về trao đổi chéo tôi sẽ có một bài riêng vì nó có chút phức tạp hơn.

def mutate(parent):
    index = random.randrange(0, len(parent))
    childGenes = list(parent)
    newGene, alternate = random.sample(geneSet, 2)
    childGenes[index] = alternate \
    if newGene == childGenes[index] \
    else newGene
    return ''.join(childGenes)

index sẽ là một số được chọn ngẫu nhiên tức là đột biến sẽ xảy ra một cách ngẫu nhiên trên Chromosome. newGene và alternate cũng sẽ được ngẫu nhiên tạo ra từ geneSet.

Vì sao lại phải tạo ra tận 2 đột biến? Câu trả lời là đột biến có thể vô nghĩa tại 1 điểm nên cần 1 đột biến khác thay thế.

Hàm hỗ trợ

Xây dựng hàm display giúp hiển thị sự thay đổi qua từng thế hệ và thời gian chạy tương ứng

import datetime

def display(guess):
    timeDiff = datetime.datetime.now() - startTime
    fitness = error_function(guess)
    print("{0}\t{1}\t{2}".format(guess, fitness, str(timeDiff)))

Main

Sau đây sẽ là phần chạy main cho giải thuật GAs:

random.seed(1)
startTime = datetime.datetime.now()
bestParent = initialize_chromosomes(len(target))
bestFitness = error_function(bestParent)
display(bestParent)
while True:
    child = mutate(bestParent)
    childFitness = error_function(child)
     
    if bestFitness <= childFitness:
        continue
    display(child)   
    if childFitness == 0:
        break
    bestFitness = childFitness
    bestParent = child

Kết quả:

hJYVdpgEBDO 11 0:00:00
HJYVdpgEBDO 10 0:00:00
HJYVdpgEBDd 9 0:00:00.001003
HJYVopgEBDd 8 0:00:00.001003
HJYVopgErDd 7 0:00:00.004010
HJYVopgErld 6 0:00:00.005012
HJlVopgErld 5 0:00:00.008021
HJlVo gErld 4 0:00:00.008021
HelVo gErld 3 0:00:00.009036
HelVo gorld 2 0:00:00.010026
Hello gorld 1 0:00:00.017045
Hello World 0 0:00:00.020052

Khởi tạo quần thể với Chromosome đầu tiên bestParent . Tính hàm lỗi cho Chromosome này cho chúng ta kết quả là 11, cho thấy chưa có vị trí nào giữa Chromosome khởi tạo và “Hello World” trùng nhau.

Chúng ta sẽ thấy rằng, việc chọn lọc đã diễn ra ở điều kiện vòng lặp, tức là cứ mỗi khi hàm lỗi giảm là sẽ giữ lại bestParent thay thế cho Chromosome cũ kém tối ưu hơn.

Kết luận

Chúng ta đã cùng nhau xây dựng một giải thuật di truyền và hiểu các bước diễn ra bên trong giải thuật.

Giải thuật trên gần như là dạng đơn giản nhất. Nếu có bài tiếp theo, tôi sẽ giới thiệu thêm về một số vấn đề bên trong và xử lý những bài toán phổ biến và có đôi chút phức tạp hơn.

#

* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*

Read More

[Algorithms] Giới thiệu thuật toán Di truyền [GA]

Giới thiệu thuật toán Di truyền

1. Sự chọn lọc tự nhiên và Di truyền 

- Trong một khu nhà bỏ trống có nhiều mèo và chuột. Ban đầu chuột có hai loại: lông trắng hoặc đen. Sau thời gian sống với mèo ban đêm chuột đen ít bị mèo nhìn thấy nên sống lâu hơn và sinh đẻ thêm do đó phát triển, trong đó chuột trắng ngày càng tuyệt giống vì bị mèo ăn thịt và không có nhiều để sinh đẻ thêm.

- Trong thực tế chỉ có những sinh vật biết tiến hóa để thích nghi với hoàn cảnh sẽ tồn tại và phát triển

- Trong tự nhiên, các cá thể khỏe, có khả năng thích nghi tốt với môi trường sẽ được tái sinh và nhân bản ở các thế hệ sau. 

- Mỗi cá thể có một cấu trúc gen đặc trưng cho phẩm chất của cá thể đó, gọi là nhiễm sắc thể (chroniosome). Như vậy mỗi nhiễm sắc thể được tạo thành từ các đơn vị gen. 

- Trong quá trình sinh sản, các cá thể con thừa hưởng các phẩm chất của cả cha và mẹ, cấu trúc gen của nó mang một phần cấu trúc gen của cha và mẹ (gọi là lai ghép). 

- Trong quá trình tiến hóa, có thể xảy ra hiện tượng đột biến, nghĩa là trong cấu trúc gen của cá thể con có thể chứa các gen mà cả cha và mẹ đều không có. 

- Lai ghép và đột biến được gọi chung là di truyền. 

- Trong quá trình tiến hóa của một giống loài, có các quần thể, mỗi một quần thể sẽ gồm nhiều cá thể. Một quần thể ứng với một giai đoạn phát triển gọi là một thế hệ. 

- Sự chọn lọc tự nhiên và di truyền là quá trình biến đổi các thế hệ theo xu hướng các thế hệ càng về sau thì càng “khỏe mạnh” và “thích nghi” tốt với môi trường nhiều hơn. 

- Môi trường thay đổi dẫn đến thích nghi cao hơn, do đó đặc trưng của quần thể cũng có thể thay đổi theo hướng “cao hơn” hoặc thậm chí ngược lại hoàn toàn là bị tuyệt chủng. 

- Genetic Algorithms tạm dịch là Thuật giải di truyền (ngắn gọn gọi là GA) bắt nguồn từ ý niệm tiến hóa để tồn tại và phát triển trong tự nhiên. 

- GA là phương thức giải quyết vấn đề bắt chước lối hành xử của con người để tồn tại và phát triển. Nó giúp tìm ra giải pháp tối ưu hay tốt nhất trong điều kiện thời gian và không gian cho phép. 

- GA xét đến toàn bộ các giải pháp, bằng cách xét trước nhất một số giải pháp sau đó loại bỏ những thành phần không thích hợp và chọn những thành phần thích nghi hơn để tạo sinh và biến hóa nhằm mục đích tạo ra nhiều giải pháp mới có hệ số thích nghi ngày càng cao 

- Hệ số thích nghi để dùng làm tiêu chuẩn đánh giá các giải pháp. 

2. Thuật toán di truyền (TTDT - GA)

- TTDT cho máy tính thực hiện là bắt trước sự chọn lọc tự nhiên và di truyền nhằm thực hiện bài toán dự báo với một mục đích nào đấy không nhất thiết ứng dụng trong lĩnh vực y học. TTDT đã có nhiều thành công trong lĩnh vực tối ưu (optimization) và học máy (machine learning). 

- Trong TTDT, mỗi một cá thể được mã hóa bởi một cấu trúc dữ liệu (tức là cách biểu diễn nhiễm sắc thể trong máy tính) mô tả một cấu trúc gen cho từng cá thể. 

- Trong TTDT cổ điển, nhiễm sắc thể là một chuỗi nhị phân. Nghĩa là mỗi một cá thể là một chuỗi nhị phân. 

- TTDT sử dụng các toán tử sau đây để làm việc trên các quần thể (để bắt chước sự chọn lọc và di truyền của tự nhiên trong việc biến đổi các thế hệ): 

  + Toán tử tái sinh (reproduction), còn gọi là toán tử chọn lọc (selection). Các cá thể tốt được chọn lọc để đưa vào thế hệ sau. Sự chọn lọc này căn cứ vào độ thích nghi với môi trường của mỗi cá thể. Vậy ta cần đến một hàm cho biết độ thích nghi ứng với từng cá thể, hàm này gọi là hàm thích nghi (fitness function)
  + Toán tử lai ghép (crossover). Hai cá thể cha và mẹ trao đổi các gen với nhau để tạo ra cá thể con.
  + Toán tử đột biến (mutation). Một cá thể thay đổi một số gen để biến đổi thành một cá thể mới.

Tất cả các toán tử trên khi thực hiện đều mang tính ngẫu nhiên.

Cấu trúc cơ bản của thuật toán di truyền như sau:

Procedure Genetic_Algorithm;
 Begin
   t =0;
   Khởi tạo thế hệ ban đầu P(t);
   Đánh giá P(t) (theo hàm thích nghi)

   Repeat
      (1) t = t + 1;
      (2) Sinh ra thế hệ mới P(t) từ thế hệ P(t-1) bởi
         (i) Chọn lọc;
         (ii) Lai ghép;
         (iii) Đột biến;
      (3) Đánh giá P(t) (theo hàm thích nghi);
   Until điều kiện kết thúc được thỏa mãn; 

End;

Trong thủ tục trên, điều kiện kết thúc vòng lặp có thể là một số thế hệ đủ lớn nào đó, hoặc độ thích nghi của cá thể tốt nhất trong các thế hệ kế tiếp nhau thì khác nhau không đáng kể. Khi thuật toán dừng, cá thể tốt nhất trong thế hệ cuối được chọn làm “nghiệm” cần tìm. Nghiệm này thường dùng để dự báo.

Tiếp theo ta sẽ nghiên cứu về các toán tử chọn lọc, di truyền (lai ghép và đột biến) trong các lệnh (i), (ii), (iii) của thuật toán di truyền.

3. Toán tử Chọn lọc

Việc chọn lọc các cá thể từ một quần thể dựa vào độ thích nghi của mỗi cá thể. Các cá thể có độ thích nghi cao có nhiều khả năng được chọn lựa (những cá thể khỏe mạnh có nhiều khả năng được phối giống). Hàm thích nghi chỉ cần là một hàm thực dương, nó có thể không tuyến tính, không liên tục, không khả vi.

Giả sử thế hệ hiện thời là P(t) gồm n cá thể { x[1], x[2], ..., x[n] }. 

Số n được gọi là cỡ của quần thể. 

Với cá thể x[*], ta tính độ thích nghi f(x[*]). Tính tổng độ thích nghi của toàn bộ quần thể: 

F = f(x[1]) + f(x[2]) + ... + f(x[n]);

Mỗi lần chọn lọc, ta thực hiện hai bước sau:
  Bước 1: Sinh một giá trị thích nghi ngẫu nhiên là một số thực q trong khoảng (0, F);
  Bước 2: x[k] là cá thể được chọn nếu k là số nhỏ nhất sao cho tổng độ thích nghi của k cá thể đầu tiên không nhỏ hơn q, tức là f(x[1]) + f(x[2]) + ... + f(x[k]) >= q.

Rõ ràng với cách chọn này, các cá thể có độ thích nghi càng cao (gây ra tổng lớn hơn q) thì càng được chọn. Các cá thể có độ thích nghi cao có thể có một hay nhiều bản sao, các cá thể có độ thích nghi thấp có thể không có mặt trong thế hệ sau (nó bị chết đi).

4. Toán tử lai ghép

Trên các cá thể được chọn lọc (sau khi thực hiện xong toán tử chọn lọc), ta tiến hành toán tử lai ghép. Với cỡ của quần thể là n, ta đưa ra một xác suất lai ghép là pc. Xác suất này đưa ra hy vọng là có n.pc cá thể được lai ghép.

Với mỗi cá thể, ta thực hiện hai bước sau đây:
  Bước 1: Sinh ra một xác suất lai ghép là số thực r nào đó trong đoạn [0, 1]
  Bước 2: Nếu r < pc thì cá thể đó được chọn để lai ghép

Từ các cá thể được chọn để lại ghép, ta cặp đôi chúng một cách ngẫu nhiên. Trong trường hợp nhiễm sắc thể là các chuỗi nhị phân có độ dài cố định, giả sử là m, ta có thể thực hiện phép lai ghép như sau:

Với mỗi cặp, sinh ra một vị trí ngẫu nhiên làm điểm bắt đầu ghép là một số nguyên p trong đoạn [0, m-1].

Tổng quát, giả sử có hai cặp nhiễm sắc thể của hai cá thể được chọn lai ghép:

  a = (a[1], ..., a[p], a[p+1], ..., a[m])
  b = (b[1], ..., b[p], b[p+1], ..., b[m])

Cặp này được thay thế bởi hai đoạn con của nhau từ vị trí thứ p+1:

  a’ = (a[1], ..., a[p], b[p+1], ..., b[m])
  b’ = (b[1], ..., b[p], a[p+1], ..., a[m])

5. Toán tử đột biến

Ta thực hiện đột biến trên các cá thể sau khi đã lai ghép. Đột biến là thay đổi trạng thái của một số gen nào đó trong nhiễm sắc thể. Một gen chịu một xác suất đột biến là pm. Xác suất đột biến pm do ta xác định và là xác suất thấp.

Tổng quát với nhiễm sắc thể là chuỗi nhị phân. Với mỗi vị trí i trong nhiễm sắc thể:
   a = (a[1], ..., a[p], a[p+1], ..., a[m])

ta sinh ra một số thực ngẫu nhiên pi trong đoạn [0,1]. Đột biến a được biến thành á như sau:

  a’ = (a’[1], ..., a’[*], ..., a’[m])

  trong đó:

   a’[*] = a[*] nếu pi >= pm và a’[*] = 1 – a[*] nếu pi < pm.

Sau quá trình chọn lọc, lai ghép, đột biến, một thế hệ mới được sinh ra. Công việc còn lại của thuật toán là chỉ việc lặp lại các bước trên.

[Xem thêm tại đây]

tham khảo tnxm.net

Read More