chương 1 trình bày một số khái niệm về giải thuật đi truyền, mô hình thiết kế giải thuât, các toán tử trong GA. Thuật toán đi truyền. quả được tham khảo trong các tài liệu [2, 3,4. 8] Giải thuật đi truyền GA(GENETIC ALGORITHM) do DE.
Goldberg đề xuất, sau d6 được L. Michalevicz phát triển là kỹ thuật phỏng theo quá trình thích nghỉ tiến hôa của các quần thể sinh học đựa trên học thuyết Danwin, day cũng chính là một trong các thuật toán tiến hóa. Thuật toán tiến hóa là các chương trình máy tính cô đùng các thuật toán tìm kiếm, tối ưu hôa dựa trên nguyên lý tiến hóa tự nhiê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.
Tư tưởng cũa thuật toán đi truyền là mô phỏng các hiện tượng tự nhiên, là kế thừa và đấu tranh sinh tổn. GA thuộc lớp các giải thuật xuất sắc nhưng lại rất khác các giải thuật ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên. Khác biệt quan trọng giữa tìm kiếm của GA và các phương pháp tìm kiếm khác là GA đuy trì và xử lý một tập các lời giải, gọi là một quần thể (population). Trong GA, việc tìm kiếm giả thuyết thích hợp được bắt đầu với một quần thễ, hay một tập hợp có chọn lọc ban đầu của các giả thuyết.
Các cá 'thể của quân thê hiện tại khởi nguồn cho quân thê thế hệ kế tiếp bằng các hoạt động lai ghép và đột biến ngẫu nhiên — được lấy mẫu sau các quá trình tiến hóa sinh học. Ở mỗi bước, các giả thuyết trong quân thể hiện tại được ước lượng liên hệ với đại lượng thích nghị, với các giả thuyết phù hợp nhất được chọn theo xác suất là các hạt giống cho việc sẵn sinh thé hệ kế tiếp, gọi là cả thé (individual). Ca thé nao phat triển hơn, thích ứng hơn với môi trường sẽ tôn tại và ngược lại sẽ bị đào thải. GA có thể đò tìm thế hệ mới có độ thích nghỉ tốt hơn.
GA giải quyết các bài toán quy hoạch toán học thông qua các quả trình co bản: lại tạo (crossover), đột biến (mutation) va chon loc (eelection) cho các cá thể trong quản thể. Dùng GA đồi hỏi phải xác định được: khởi tạo quần thể ban đầu, hàm đánh giá các lời giải theo mức độ thích nghỉ ~ hàm mục tiêu, các toán tử đi truyền tạo him sinh sẵn. Trong công nghệ thông tin, GA là một thành phần của Tính toán tiến hồa (Evoluonary computation — EC), một lĩnh vực được coi là có tốc độ phát triển nhanh của trí tuệ nhân tạo. Có thể chia EC thành 5 hướng nghiên cứu như sau - GA (Genetic Algorithm - GA): Dựa vào quá trình di truyền trong tự nhiên để cải tiền lời giải qua các thế hệ bắt nguồn từ một tập các lời giải ban đầu.
~ Quy hoạch tién hoa (Evolutionary Programming - EP): Dựa vào quy luật tiến hoá, tìm phương pháp kết hợp đủ khả năng giải quyết trọn vẹn một bài toán từ một lớp các phương pháp giải quyết được một số phần của bài toán. - Các chiến lược tiến hoá (Evolutionary Strategies - ES): Dựa trên một số chiến lược ban đầu, tiến hoá để tạo ra những chiến lược mới phù hợp với môi trường thực tế một cách tốt nhất. - Lập trình di truyền (Genetic Programming - GP): Mé réng GA trong lĩnh vực các chương trình của máy tính. Mục đích của né 14 dé sinh ra một cách tự động các chương trình máy tính giải quyết một cách tối ưu một vấn đề cụ thể.
- Các hệ thống phân loai (Classifier Systems- CS): Các GA đặc biệt được đùng trong việc học máy và việc phát hiện các quy tắc trong các hệ dựa. trên các quy tắc. GA cũng như các thuật toán tiến hoá đều được hình thành dựa trên một quan niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm "Quá trình tiền hoá tự nhiênlà quá trình hoàn hảo nhất, hợp lý nhất và tự nô đã mang tính tối ưu".
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. Sự hình thành và phát triên của GA trên thế giới có thê được điểm qua. các mốc thời gian quan trọng như sau: ‘Nim 1960, ý tưỡng đầu tiên về Tính toán tiến hoá được Rechenberg giới thiệu trong công trình *Evolution Strategies” (Các chiến lược tiến hoá), Ý tưởng này sau đó được nhiều nhà nghiên cứu phát trién Năm 1975, Giải thuật gen do John Holland phat minh va được phát triển. bởi ông cùng với các đồng nghiệp và những sinh viên.
Cuốn sách "Adaption in Natural and Artificial Systems" (Sự thích nghỉ trong các hệ tự nhiên và nhân tạo) đã tổng hợp các kết quả của quá trình nghiên cứu và phát triển đó. ‘Nim 1992, John Koza di ding GA để xây dựng các chương tình giải quyết một số bài toán và gọi phương pháp này là “lập trình gen” Ngày nay GA càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu hoá, một lĩnh vực cô nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng thường khó và chưa có giải thuật hiệu quả đề giải cơ bản 1.1 Ca thé, nhiễm sắc thể Trong GA, một cá thể biểu diễn một phương án của bài toán. Trong trường hợp tổng quát, một cá thể có nhiều Nhiễm sắc thê(NST), ở đây ta quan. niệm một cá thể chỉ cô một NST.
Do dé khái niệm cá thé va NST trong GA coi như là tương đương. Một NST được tạo thành từ nhiều gen, mỗi gen cô thể có các giá trị khác nhau để quy định một tính trạng nào đó. Trong GA, một gen được coi như một phẩn tử trong chuỗi NST.2 Quan thé Quần thê là một tập hợp các cá thể có cùng một số đặc điểm nào day "Trong GA ta quan niệm quản thể là một tập các lời giải của một bài toán.3 Chom lc (Selection) "Trong tự nhiên, quá trình chon loc 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ỉ được với điều kiện.
sống thì có khả năng đầu tranh lớn hơn, đo đó có thể tổn tại và sinh sản. cá thể không thích nghỉ được với điều kiện sống thì đần mất đi. nguyên lý của quá trình chọn lọc và đầu tranh sinh tôn trong tự nhiên, chọn lựa các cá thê trong GA chính là cách chọn các cá thể có độ thích nghỉ tốt để. đưa vào thể hệ tiếp theo hoặc dé cho lai ghép, với ï mục đích là sinh ra các cá thể mới tốt hơn.
Có nhiều cách để lựa chọn nhưng cuối cùng đều nhằm đáp ứng mục tiêu là các cáthê tốt sẽ có khả năng được chọn cao hơn.4 Lai ghép (Cross-over) Lai ghép trong tự nhiên là sự kết hợp các tính trạng của bố mẹ để sinh. ra thé hệ con. Trong GA, lai ghép được coi là một sự tổ hợp lại các tính chất (hành phẩn) trong hai lời giải cha mẹ nào đồ đễ sinh ra một lời giải mới mà có đặc tính mong muốn là hơn thể hệ cha mẹ. Đây là một quá trình xây ra.
chủ yếu trong GA.5 Dét bién (Mutation) Đột biến là một sự biến đổi tại một (hay một số) gen của NST ban đầu để 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. Đột biến có thể tạo ra một cá thê mới tốt hơn hoặc xấu hơn cá thê ban đầu. trong GA thì ta luôn 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ệ.3 Mô hình GÀ 'Với các khái niệm được giới thiệu ở trên, GA được mô tả bối sơ đỗ sau đây NMOGepartoan TS SE ee + Se Sinn săn cực chọn gig eran sar "Như vậy giải thuật GA được xây dung qua các bước cơ bản sau đây 1.
Xác lập các tham số ban đầu của bài toán. Khởi tạo: Sinh nhiên một quân thể gồm 7 ca thé (là z lời giải "ban đầu của bài toán). Xác lập quân thể mới: tạo quản thể mới bằng cách lặp lại các bước sau cho đến khi quần thê mới hoàn thành, bao gồm: 3.1 Tính độ thích nghỉ của mỗi cá thẻ.2 Kiểm tra điêu kiệnkết thúc giải thuật.3 Chọn lọc các cá thé bé mẹ từ quản th cũ theo độ thích nghỉ của chúng (Cá thể có độ thích nghỉ càng cao thì càng có nhiều khả năng được chon), 3.4 Tiến hành lai ghép các cặp bố-me với một xác suất lai ghép được chọn đễ tạo ra một cá thê mới.5 Tiến hành đột biến với xác suất đột biến được chọn xác định cá thể đột biến. Kiểm tra điều kiện đừng: Nếu điều kiện được thỏa mãn thì thuật toán kết thúc và trả về lời giải tốt nhất chính là quan thể hiện tại.4 Các tham số cũa GÀ 1.1 Kích thước quân thể Kích thước quân thể cho biết cô bao nhiêu cá thể trong một quần thể (trong một thế hệ).
Qua các nghiên cứu cũng như các thử nghiệm đã cho thấy kích thước quần thể không nên quá bé cũng như không quá lớn. Nếu c quá ít cá thể thả ít có khả năng thực hiện lai giống và chỉ một phần nhỏ không gian tim kiểm được đùng. Như vậy sẽ đễ xây ra trường hợp bỏ qua các lời giải tốt. "hưng quá nhiều cá thể cũng không tốt vì GA sẽ chạy chậm đi, ảnh hưởng đến hiệu quả của giải thuật.
Các nghiên cứu cũng đã chỉ ra không có lợi khi tăng kích thước quần thễ lên quá một giới hạn cho phép.2 Xác suất lai ghép Xác suất lai ghép cho biết việc lai ghép tạo ra thể hệ mới được thực hiện. thường xuyên như ếnào. Nề xác suất lai ghép là z,, khi đồ khả năngđể một cá thê được lai ghép là ø,. u không thực hiện lai ghép, con sinh ra sẽ g ống hoàn toàn bồ mẹ.
Nếu được lai ghép, con sinh ra sẽ có một phần giống 'bổ và một phân giống mẹ.3 Xác suất đột biến Xác suất đột biến cho bi các gen của NST thay đổi thường xuyên như xác suất đột biến là p„, khi đó khả năng để mỗi gen của một kỷ bị đột biến là m„. Toán tử đột biến có tác đụng ngăn ngửa GA rơi vào tình trạng cực trị địa phương, tuy nhiên nếu thực hiện đột bi với xác suất quá cao sẽ biển GA thành giải thuật tìm kiểm ngẫu nhiên. hân xé Xuất phát từ sơ đỏ thực hiện GA, chúng ta cô thể có một số nhận xét như sau: + GA lập luận mang tính chất ngẫu nhiên để từ giải pháp tối ưu cho. những vấn đề phức tạp, thay vì xác định như toán học giải tích.