KỸ THUẬT TỰ THÍCH NGHI TRONG GIẢI THUẬT DI TRUYỀN ÁP DỤNG CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU

Tìm hiểu kỹ thuật tự thích nghi trong giải thuật di truyền. Ứng dụng giải thuật để giải quyết bài toán tối ưu đa mục tiêu một cách hiệu quả.

• Tác giả: Phạm Thu Trang
• Người hướng dẫn: TS. Vũ Mạnh Xuân
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Kỹ Thuật Tự Thích Nghi Trong Giải Thuật Di Truyền Áp Dụng Cho Bài Toán Tối Ưu Đa Mục Tiêu
• Loại tài liệu: Luận văn Thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng Quan Kỹ Thuật Tự Thích Nghi Trong GA Đa Mục Tiêu

Bài toán tối ưu đa mục tiêu xuất hiện rộng rãi trong nhiều lĩnh vực như kinh tế, nông nghiệp và kỹ thuật. Mục đích là tìm ra phương án tối ưu, đáp ứng đồng thời nhiều mục tiêu. Điểm khó khăn là các mục tiêu này thường xung đột lẫn nhau. Giải thuật di truyền (GA đa mục tiêu) là một hướng tiếp cận hiệu quả, mô phỏng quá trình tiến hóa tự nhiên. Kỹ thuật tự thích nghi trong GA được quan tâm đặc biệt, giúp điều chỉnh các tham số như xác suất lai ghép, đột biến, và kích thước quần thể. Luận văn này nghiên cứu kỹ thuật tự thích nghi, áp dụng cho bài toán tối ưu đa mục tiêu.

1.1. Bản chất của giải thuật di truyền đa mục tiêu GA

Giải thuật di truyền (GA) mô phỏng cơ chế tiến hóa của sinh vật. Các cá thể có khả năng thích nghi cao hơn sẽ có cơ hội sống sót và sinh sản cao hơn. GA sử dụng các thuật ngữ sinh học như chọn lọc tự nhiên, lai ghép và đột biến. GA phù hợp cho bài toán tối ưu đa mục tiêu do có khả năng tìm kiếm đồng thời nhiều phương án tối ưu. Sự đa dạng của quần thể được duy trì thông qua các toán tử di truyền, giúp tránh tình trạng hội tụ cục bộ.

1.2. Tại sao cần kỹ thuật tự thích nghi trong GA

Kỹ thuật tự thích nghi là một đặc trưng quan trọng của tiến hóa tự nhiên. Quá trình tiến hóa luôn hướng đến sự tối ưu, do đó, việc áp dụng tự thích nghi vào GA là một hướng đi tự nhiên. Các nghiên cứu đã tập trung vào việc điều chỉnh tự động các tham số của GA, như xác suất lai ghép, xác suất đột biến và kích thước quần thể. Mục tiêu là cải thiện hiệu suất của GA và tìm ra các giải pháp tối ưu tốt hơn.

II. Thách Thức Hạn Chế Khi Dùng GA Cố Định Tham Số

GA truyền thống với tham số cố định đối mặt với nhiều thách thức trong bài toán tối ưu đa mục tiêu. Việc lựa chọn tham số phù hợp thường đòi hỏi nhiều thử nghiệm và kiến thức chuyên môn. Tham số tối ưu cho một bài toán có thể không hiệu quả cho bài toán khác. Khả năng khám phá và khai thác không được cân bằng tốt, dẫn đến hội tụ cục bộ hoặc chậm trễ. Điều này thúc đẩy sự phát triển của các phương pháp tự động điều chỉnh tham số.

2.1. Khó khăn trong việc chọn tham số tối ưu cho GA

Việc lựa chọn tham số thích hợp cho GA (ví dụ: xác suất lai ghép, xác suất đột biến, kích thước quần thể) là một thách thức lớn. Các tham số này ảnh hưởng trực tiếp đến hiệu suất của GA. Thường cần nhiều thử nghiệm và kinh nghiệm để tìm ra bộ tham số phù hợp cho một bài toán cụ thể. Bộ tham số tối ưu cho một bài toán có thể không hiệu quả cho bài toán khác. Do đó, việc tự động điều chỉnh tham số là rất quan trọng.

2.2. Mất cân bằng giữa khám phá và khai thác trong GA

GA cần cân bằng giữa khả năng khám phá không gian tìm kiếm (tìm kiếm các vùng tiềm năng) và khả năng khai thác (tập trung vào các vùng hứa hẹn). Nếu khả năng khám phá quá mạnh, GA có thể lãng phí thời gian tìm kiếm ở những vùng không tiềm năng. Nếu khả năng khai thác quá mạnh, GA có thể hội tụ cục bộ và bỏ qua các giải pháp tốt hơn ở những vùng khác. Kỹ thuật tự thích nghi giúp GA tự động điều chỉnh để cân bằng giữa hai khả năng này.

2.3. Hội tụ cục bộ và sự cần thiết của diversity preservation

Hội tụ cục bộ là một vấn đề phổ biến trong GA. Khi quần thể trở nên quá đồng nhất, GA có thể bị mắc kẹt ở một giải pháp cục bộ và không thể tìm ra giải pháp tối ưu toàn cục. Diversity preservation (duy trì sự đa dạng của quần thể) là rất quan trọng để tránh hội tụ cục bộ. Các kỹ thuật tự thích nghi có thể giúp duy trì sự đa dạng bằng cách điều chỉnh các toán tử di truyền và kích thước quần thể.

III. Cách Tiếp Cận Kỹ Thuật Tự Thích Nghi Trong Giải Thuật GA

Kỹ thuật tự thích nghi trong GA tập trung vào việc điều chỉnh các tham số và toán tử di truyền một cách tự động. Điều này có thể bao gồm điều chỉnh xác suất lai ghép, đột biến, kích thước quần thể, và thậm chí cả cấu trúc của các toán tử. Mục tiêu là làm cho GA trở nên linh hoạt hơn, phù hợp với các đặc điểm của bài toán và trạng thái hiện tại của quần thể. Các phương pháp dynamic parameter control được sử dụng rộng rãi.

3.1. Tự động điều chỉnh xác suất lai ghép và đột biến

Xác suất lai ghép và đột biến là hai tham số quan trọng ảnh hưởng đến hiệu suất của GA. Kỹ thuật tự thích nghi có thể điều chỉnh các tham số này dựa trên hiệu suất của các cá thể trong quần thể. Ví dụ, nếu quần thể đang hội tụ quá nhanh, xác suất đột biến có thể được tăng lên để tăng tính đa dạng. Ngược lại, nếu quần thể đang khám phá quá nhiều, xác suất lai ghép có thể được tăng lên để khai thác các vùng hứa hẹn.

3.2. Tự thích nghi kích thước quần thể cho hiệu quả tối ưu

Kích thước quần thể cũng là một yếu tố quan trọng. Quần thể quá nhỏ có thể không đủ đa dạng để khám phá không gian tìm kiếm hiệu quả. Quần thể quá lớn có thể làm tăng chi phí tính toán. Kỹ thuật tự thích nghi có thể điều chỉnh kích thước quần thể dựa trên hiệu suất của GA. Ví dụ, nếu GA đang hội tụ chậm, kích thước quần thể có thể được tăng lên để tăng tính đa dạng.

3.3. Các phương pháp dynamic parameter control phổ biến

Dynamic parameter control là một phương pháp phổ biến để tự động điều chỉnh tham số trong GA. Các phương pháp này sử dụng các quy tắc hoặc mô hình để điều chỉnh tham số dựa trên trạng thái hiện tại của quần thể. Ví dụ, một số phương pháp sử dụng hàm phản hồi để điều chỉnh tham số dựa trên hiệu suất của các cá thể. Các phương pháp khác sử dụng học máy để dự đoán các tham số tối ưu.

IV. Ứng Dụng Thực Tế Nghiên Cứu Kỹ Thuật Tự Thích Nghi Trong GA

Ứng dụng giải thuật di truyền rất đa dạng, từ kỹ thuật, kinh tế đến khoa học. Kỹ thuật tự thích nghi đã được áp dụng thành công trong nhiều bài toán tối ưu đa mục tiêu, chẳng hạn như thiết kế kỹ thuật, quản lý chuỗi cung ứng và lập lịch. Các nghiên cứu đã chứng minh rằng kỹ thuật tự thích nghi có thể cải thiện đáng kể hiệu suất của GA và tìm ra các giải pháp tối ưu tốt hơn. Việc xử lý ràng buộc cũng được cải thiện đáng kể.

4.1. Ứng dụng GA tự thích nghi trong thiết kế kỹ thuật

Trong thiết kế kỹ thuật, GA có thể được sử dụng để tối ưu hóa các tham số của một thiết kế để đáp ứng nhiều mục tiêu khác nhau, chẳng hạn như hiệu suất, chi phí và độ bền. Kỹ thuật tự thích nghi có thể giúp GA tìm ra các thiết kế tối ưu tốt hơn bằng cách tự động điều chỉnh các tham số của GA để phù hợp với các đặc điểm của bài toán thiết kế.

4.2. Quản lý chuỗi cung ứng và lập lịch sử dụng GA

GA cũng có thể được sử dụng trong quản lý chuỗi cung ứng và lập lịch để tối ưu hóa các quyết định như mức tồn kho, lịch trình sản xuất và vận chuyển. Kỹ thuật tự thích nghi có thể giúp GA thích ứng với các thay đổi trong môi trường chuỗi cung ứng và tìm ra các lịch trình tối ưu tốt hơn.

4.3. Cải thiện constraint handling với GA tự thích nghi

Constraint handling (xử lý ràng buộc) là một vấn đề quan trọng trong bài toán tối ưu. Các bài toán thực tế thường có nhiều ràng buộc, và việc tìm ra một giải pháp thỏa mãn tất cả các ràng buộc có thể rất khó khăn. Kỹ thuật tự thích nghi có thể giúp GA xử lý ràng buộc hiệu quả hơn bằng cách điều chỉnh các toán tử di truyền để ưu tiên các giải pháp thỏa mãn ràng buộc.

V. GA Lai Hybrid GA và Tương Lai Của Tự Thích Nghi Trong GA

GA lai kết hợp GA với các thuật toán tối ưu khác, chẳng hạn như thuật toán leo đồi hoặc thuật toán tìm kiếm lân cận. Sự kết hợp này có thể cải thiện hiệu suất của GA bằng cách tận dụng ưu điểm của cả hai thuật toán. Tương lai của kỹ thuật tự thích nghi trong GA hứa hẹn nhiều tiềm năng, đặc biệt là với sự phát triển của học máy trong GA và surrogate models.

5.1. Lợi ích của việc kết hợp GA với các thuật toán khác

Hybrid GA tận dụng điểm mạnh của nhiều thuật toán khác nhau. Ví dụ, thuật toán leo đồi có thể được sử dụng để cải thiện các giải pháp cục bộ, trong khi GA có thể được sử dụng để khám phá không gian tìm kiếm toàn cục. Sự kết hợp này có thể dẫn đến các giải pháp tốt hơn và thời gian tính toán ngắn hơn.

5.2. Ứng dụng học máy để cải thiện kỹ thuật tự thích nghi

Học máy trong GA có thể được sử dụng để dự đoán các tham số tối ưu cho GA hoặc để xây dựng surrogate models (mô hình thay thế) để đánh giá hiệu suất của các cá thể. Điều này có thể giúp GA tự thích nghi hiệu quả hơn và tìm ra các giải pháp tối ưu nhanh hơn.

5.3. Surrogate models và tiềm năng phát triển trong GA

Surrogate models là các mô hình đơn giản được sử dụng để ước lượng hiệu suất của các cá thể trong GA. Các mô hình này có thể được xây dựng bằng cách sử dụng các kỹ thuật học máy. Sử dụng surrogate models có thể giảm đáng kể thời gian tính toán cần thiết để đánh giá hiệu suất của các cá thể, đặc biệt là trong các bài toán có chi phí tính toán cao.

VI. Kết Luận Hướng Phát Triển Kỹ Thuật Tự Thích Nghi Cho GA

Kỹ thuật tự thích nghi là một hướng đi đầy hứa hẹn để cải thiện hiệu suất của GA trong bài toán tối ưu đa mục tiêu. Các nghiên cứu đã chứng minh rằng kỹ thuật tự thích nghi có thể giúp GA tìm ra các giải pháp tối ưu tốt hơn và thích ứng với các thay đổi trong môi trường. Hướng phát triển trong tương lai bao gồm việc nghiên cứu các phương pháp tự thích nghi mới, kết hợp với học máy và áp dụng cho các bài toán thực tế phức tạp hơn.

6.1. Tổng kết các ưu điểm của kỹ thuật tự thích nghi

Kỹ thuật tự thích nghi giúp GA tự động điều chỉnh các tham số và toán tử để phù hợp với bài toán cụ thể. Điều này giúp cải thiện hiệu suất của GA, tránh hội tụ cục bộ và thích ứng với các thay đổi trong môi trường. Kỹ thuật này đặc biệt hữu ích cho các bài toán phức tạp với không gian tìm kiếm lớn.

6.2. Các hướng nghiên cứu tiềm năng trong tương lai

Các hướng nghiên cứu tiềm năng trong tương lai bao gồm việc phát triển các phương pháp tự thích nghi mới, kết hợp với học máy và áp dụng cho các bài toán thực tế phức tạp hơn. Nghiên cứu cũng có thể tập trung vào việc phát triển các surrogate models hiệu quả hơn và cải thiện constraint handling trong GA.

6.3. Tầm quan trọng của việc ứng dụng vào bài toán thực tế

Việc ứng dụng kỹ thuật tự thích nghi vào các bài toán thực tế là rất quan trọng để đánh giá hiệu quả của các phương pháp và xác định các hướng nghiên cứu tiềm năng. Các bài toán thực tế thường có các đặc điểm phức tạp mà các bài toán lý thuyết không thể mô phỏng được, do đó, việc ứng dụng vào thực tế là cần thiết để đảm bảo rằng các phương pháp tự thích nghi có thể giải quyết các vấn đề thực tế một cách hiệu quả.

Trích đoạn nội dung tài liệu

Chương 1 GIẢI THUẬT DI TRUYỂN Chương này sẽ giới thiệu về giải thuật di truyền và giải thuật di truyền mã hóa số thực: Các khái niệm, toán tử, mô hình tiễn hóa và so sánh giải thuật ải tra với một số giải thuật truyền thông khác. Các khái niệm và kết quả trong chương này được tham khảo trong [2], [3], [5], [12]. Tổng quan giải thuật di truyền (GA) Trong sinh học, tiến hóa là sự thay đổi đặc tính đi 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 nay sinh sự đa đạ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 hay Đrotein "Hình 1. Quá trình tiến hóa từ tỉnh tỉnh thành người GA trong Tin học được hình thành dựa trên quan niệm: Quá trình tiến 'hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất, và tự nó đã mang tính tối ưu. Quan niệm này được xem như một tiên đề đúng, không chứng minh được, nhưng phù hợp với thực tế khách quan. Quá trình tiền hoá thể hiện tính tối ưu.

ở chỗ, thế hệ sau bao giờ cũng tốt hơn thế hệ trước (phát triển hơn, hoàn thiện hơn). Xuyên suốt quá trình tiền hoá tự nhiên, các thế hệ mới luôn được sinh ra. để bổ sung thay thế thế hệ cũ. Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tôn tại, cá thể nào không thích ứng với môi trường sẽ bị đào thải.

Sự thay đối môi trường là động lực thúc đẩy quá trình tiến hoá. Ngược lại, tiến hoá cũng tác động trở lại góp phin làm thay đổi môi trường. [5] GA thực chất là một gi thuật tìm kiếm, chọn lựa các giải pháp tối tu để giai quyét cac bai todn thyc té khac nhau, da trén co ct ‘hon loc cia ty nhiền: từ tập lời giải ban đầu, thông qua nhiều bước tién hoá, hình thành tập lời giải mới phù hợp hơn, và cuối cùng dẫn đến lời giải tối ưu toàn cục. GA sử đụng các thuật ngữ vay mượn từ đi truyền học như: Cá thể, quần thể, lai ghép, đột biến,.

Các GA khác nhau tuy có nhiều điểm khác biệt, song đều mô phông 4 quả trình cơ bản: Lai ghép, đột biến, sinh sản và chọn lọc tự nhiên. "Thông thường, thuật giải đi truyền có thê mô tả v: Procedure GA; Begin t=0: Khởi tạo ngẫu nhiên quần thê P(); Tính độ thích nghỉ cho các cá thể thuộc P(); Repeat trt+i; Chọn các cá thể từ P(t-1); Lai tạo các cá thê 44 chon 8 tao ra P(t); Đột biến các cá thê trong P(t) theo xác sudt pr: Đánh giá độ phụ hợp của các cá thể trong tập P()) Until (théa diéu kién dimg) End. 'Giải thích: Tại lần lặp thứ t, GA xác định một tập hợp các lời giải có thể gọi là quan thé P(t) = {x‡,x‡,. Mỗi lời giải xƒ được đánh giá nhằm xác.

định độ phù hợp của nó. Sau đồ một tập hợp các lời giải được hình thành nhờ sự lựa chọn các lời giải phù hợp hơn. Một số phin tử của tập hợp này được tái sản xuất thông qua lai ghép và đột biến. Từ đó hình thành quân thê mới P(t+1) vớihy vọng chứa các cá thê phù hợp hơn quản thê trước đó.

Các vấn đê cơ ban trong GA [3] 1. Mã hóa ca thé Mỗi cá thể tương ứng với một lời giải của bài toán đã cho. Những cá thể này còn được gọi là chuỗi hay các nhiễm sắc thể (NST). Các NST này được chia nhỏ thành các gen và sắp xếp theo một đãy tuyến tính.

Mã hóa là vấn đề cần giải quyết trước khi giải bài toán với GA. Tuy thuộc vào nội đung của mỗi bài toán mà ta có cách mã hoá khác nhau. Các phương pháp mã hoá hay được sử đụng: + Mã hoá đạng chuỗi nhị phân: Day là phương mã hóa truyền thống hay cô điển. Trong phương pháp này, mỗi NST là một chuỗi các bit 0 và 1 ‘Vi dy: Chudi 1101110101111101110 là một lời giải đã được mã hóa nhị phân.

+ Mã hoá thứ tự Được sit dung trong bài toán có có liên quan đến thứ tự như bài toán du lich hay bai toán lập lịch. Ở đây mỗi NST là một chuỗi các số nguyên thể hiện thứ tự phânbổ lời giãi của bài toán. Vĩ dụ: NST 342165879 Đối với những bài toán có liên quan đến thứ tự này, việc thao tác trên các NST chính là hoán đổi vị trí các số trong chuỗi đã cho nhằm làm thay đôi trình tự của nó, + Mã hoá theo giá trị Được sử dụng trong các bài toán mà mỗi lời giải là tập các giá trị (ví đụ tập số thực). Trong phương pháp này, mỗi NST là một chuỗi các giá trị có mối quan hệ tương ứng với bài toán.

+ Mã hoá đạng cây Được sử đụng chủ yếu trong các biểu thức toán học. Trong phương pháp. mã hoá này, mỗi NST là một cây của một nhóm đối tượng nào đó. + Mã hoá số thực Trong phương pháp này, mỗi NST được mã hóa là một véc tơ thực trong.

không gian R", chẳng hạnx = (x,,1;. Cách mã ‘hoa nay rit ty nhién déi với các bài toán tối ưu số và được phát triển rất mạnh. trong thời gian gin đây 1. Khởi tạo quần thể Tập hợp các cá thể là lời giải của một bài toán tạo thành một quân thẻ.

Tập lời giải ban đầu thường được khối tạo ngẫu nhiên từ miền xác định của các lời giải. Cách tạo lập quân thê ban đầu phụ thuộc vào cách nã hóa cá thé, chẳng hạn với cách Mã hóa số thực thì quân thể ban đầu được tạo bằng cách. tạo ngẫu nhiênm véc tơ thực trong không gian R" 1. Ham thich nghi Ham thích nghỉ là một hàm đánh giá độ tốt/xáu của cá thễ, được đùng để so sánh giữa các cá thê xem cá thể nào tốt hơn.

Sau mỗi thế hệ tiến hóa, GA. dang hàm này để quyết định giữ lại hay loại bỏ cá thể nào, cũng như trong quả trình lai ghép hay chọn lọc, cá thể nào có giá trị hàm thích nghỉ tốt hơn sẽ được ưu tiên chọn lựa 1. Các toán tử di truyền a. Toán tử chọn lọc Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay đổi các cá thể trong quân thê.

Những cá thể tốt, thích nghỉ với điều kiện sống thì có khả năng sống sốt cao hơn và ngược lại, những có thể không thích nghỉ với điều kiện sống thì đần bị đào thải. Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh trong tự nhiên, chọn loc trong GA chinh 14 quá trình chọn các cá thể cô độ thích nghỉ (cụ thể là giá trị hàm thích nghị) tốt hơn để đưa vào thế tệ tiếp theo hoặc cho lai ghép, với mục đích là sinh ra cá thê mới tốt hơn. "Toán tử chọn lọc thường giữ lại 50% các cá thể phù hợp nhất. người ta cũng phát triển nhiều sơ đồ chọn khác nhau nhằm tăng tính đa dạng.

của quân thể, tránh sự hội tụ sớm. Toán từ lại ghép Là quá trình hình thành nhiễm sắc thê mới trên cơ sỡ các NST cha — mẹ. Tương tự như trong sinh học, việc lai ghép giữa hai NST sẽ cho ra các NST con thừa hưởng một phân từ cá thê cha và một phần từ cá thê mẹ. Toán tử lai ghép là toán tử di truyền cơ bản trong GA.

Mỗi toán tử lai ghép sẽ cô xác suất xây ra tương ứng của nó. Các nghiên cứu trong sinh học đã chỉ ra rằng, trong tự nhiên xác suất lai ghép thường xây ra rất cao, khoảng. 99,97%, Tuy nhiên trên thực tế, khi áp dung vào các bài toán tin học thì xác suất này thường không cao đến mức đó. Việc xác định xác suất lai ghép hoàn.

toàn phụ thuộc vào vấn đề cần giải quyết. Toán tử đột biến 'Đột biến là sự biến đôi tại một (hoặc một số) gen cia NST đễ tạo ra một 'NST mới. Đột biến có xác suất xây ra thấp hơn lai ghép rất nhiều nhưng đóng vai trò rất lớn đến sự tối ưu của cá thể. Thông thường, toán tử đột biển đông.

vai tò như là người mỡ đường, nghĩa là khi các toán tử lai ghép được đùng nhiều đần đến sự lặp đi lặp lại các cá thê có độ thích nghỉ gần gần nhau, toán. tử đột biến có nhiệm vụ phá vỡ sự cân bằng đó, thúc đây quần thê phát triển. và các cá thê sẽ phong phú, đa đạng hơn. Tuy nhiên, đột biến có thể tạo ra cá 'thể mới tốt hơn hoặc xấu hơn cá thể mẹ ban đầu, song ta luôn mong muốn tạo ra những phép đột biến cho phép cãi thiện lời giải qua từng thể hệ tiền hóa.

4 Tạo sinh Chọn các cá thể trong quân thê hiện thời làm quần thể mới cho lần lặp kế tiếp 1. Các tham số của GA a. Kích thước quần thể Kích thước quân thể cho biết có bao nhiêu cá thể trong quân thể ở mỗi thế hệ. Các nghiên cứu và thử nghiệm cho thấy, kích thước quần thê không.

riên quá bé hoặc quá lớn. Bởi nếu có ít cá thể thì sẽ đẫn đến việc làm giảm. không gian tìm kiếm, khi đó đễ rơi vào cục bộ địa phương, vô tình bỏ qua các lời giải tốt. Ngược lại, nếu kích thước quần thể quá lớn sẽ đẫn đến việc chỉ phí về thời gian sẽ lớn hơn, ảnh hưởng đến hiệu quả tính toán của giải thuật.

Xác suất lai ghép Xác suất lai ghép cho biết tính thường xuyên của việc lai ghép tạo ra thế hệ mới được thực hiện như thế nào. Xác suất lai ghép là p, cho biết khả năng. để một cá thé trong quan thể tham gia lai ghép. Khi áp đụng lai ghép thì cá.

con sinh ra sẽ có một phần giống bồ và một phần giống mẹ. Xác suất đột biến Đây là xác suất cho biết tính thường xuyên của việc các gen trong NST thay đổi như thế nào. Nếu xác suất đột biết là pạ, khi đó khả năng để mỗi gen. của một NST bất kỳ bị đột biến là p„.

Tác dụng của toán tử đột biến là ngăn. ngừa giải thuật đi truyền rơi vào tình trạng cực trị địa phương. Tuy nhiên, ta cũng không nên thực hiện giải thuật với xác suất đột biến quá cao vì sẽ biến giải thuật đi truyền thành giải thuật tìm kiếm mù. d Điều kiện dừng trong GA Trong GA, điều kiện đừng của thuật toán có thễ đo người lập trình lựa chọn.

Thông thường có các điều kiện đừng sau: + Dừng đựa vào kết quả: Khi tôn tại cá thê đạt đến xấp xi ngưỡng yêu cầu. thì đừng thuật toán.