RedHot_RuaDaiKa
New Member
Download miễn phí Thuật giải di truyền – Genetic Algorithm
Quy tắc biểu diễn gen qua chuỗi nhị phân : Chọn chuỗi nhị phân ngắn nhất nhưng đủ thể hiện được tất cả kiểu gen.
Thực chất, đây chính là một quy tắc cũ mà bạn đã biết ở tập 1 khi bàn về chọn kiểu biến. Lấy ví dụ, để chuyển biến X nguyên có giá trị trong khoảng [32,63] về chuỗi nhị phân, có thể bạn sẽ chọn dùng một chuỗi nhị phân dài 6 bit (vì 6 bit đủ để biểu diễn một số trong khoảng [0,63]). Dĩ nhiên , chọn chiều dài 6 bit là đúng nhưng chưa tối ưu. Thực chất, một con số trong khoảng [32,63] chỉ cần 5 bit là đủ. Tại sao vậy? Vì với 5 bit, ta chỉ có thể biểu diễn được một số Y trong khoảng [0,31]? Nhưng ta nhận xét rằng, với mọi số X trong khoảng [32,63] ta đều xác định được một quy tắc để tương ứng với một số Y trong khoảng [0,31]. Cụ thể là Y = X – 32. Và thay vì biểu diễn trực tiếp số X, ta biểu diễn thông qua trung gian Y. Khi đã có Y ta sẽ dễ dàng suy ra X thông qua quy tắc trên
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ản là, nếu vùng đất của chúng ta có nhiều đồi nhỏkhác bên cạnh ngọn đồi cao nhất thì sẽ có khả năng thuật toán của chúng ta bị "kẹt" ở một ngọn đồi nhỏ.
Do tư tưởng là "càng ngày càng lên cao" nên khi lên đến đỉnh một ngọn đồi nhỏ thuật toán sẽ không thể đi
tiếp được (vì không thể lên cao được nữa, muốn tìm đến một ngọn đồi cao hơn thì phải xuống đồi hiện tại,
mà xuống đồi thì không đúng tư tưởng càng ngày càng lên cao).
Bạn hãy tưởng tượng một máy tính giải quyết vấn đề-bài toán theo kiểu leo đồi là một người leo đồi với tư
tưởng "càng leo càng cao". Nếu chỉ có một người leo đồi thì có khả năng người đó sẽ bị "kẹt" trên một đỉnh
đồi thấp. Có lẽ bạn đã đoán được tư tưởng tiếp theo! Như vậy, nếu có nhiều người leo đồi cùng leo ở nhiều
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
địa điểm khác nhau thì khả năng có một người leo đến đỉnh núi cao nhất sẽ cao hơn. Càng nhiều người thì
khả năng đến đỉnh núi cao nhất sẽ cao hơn. Nhưng tư tưởng này cũng chưa có gì mới mẻ, đơn giản chỉ là
dùng nhiều máy tính để chia việc ra mà thôi. Hơn nữa, với không gian tìm kiếm cỡ 10
30
như bài toán mở
khóa, chúng ta cần dùng bao nhiêu siêu máy tính? Mà quan trọng hơn nữa, cho dù có nhiều người leo
đồi, nhưng nếu số lượng người leo đồi quá ít so với số lượng đồi thì khả năng tất cả người leo đồi đều bị
"kẹt" cũng vẫn còn rất cao.
Đến đây thì rất có thể trong đầu các bạn chợt nảy lên một ý nghĩ. Tại sao không cho nhiều "thế hệ" người
leo đồi? Nghĩa là, nếu toàn bộ người leo đồi đầu tiên (giả sử 1000 người chẳng hạn) đều không đạt đến
đỉnh đồi cao nhất thì ta sẽ cho 1000 người leo đồi khác tiếp tục leo. Tuy nhiên, sẽ nảy sinh một vấn đề, có
khả năng là trong nhóm người leo đồi mới, có những người lại đi leo lại những ngọn đồi mà nhóm trước đã
leo rồi. Bạn nghĩ thế nào? Vậy thì hãy ghi nhận lại những ngọn đồi đã leo để những nhóm sau còn thừa
hưởng được kết quả của nhóm trước. Hay nói một cách tổng quát hơn : hãy làm sao để những người giỏi
nhất (leo cao nhất) trong số những người leo đồi đầu tiên truyền lại "kinh nghiệm" leo đồi của mình cho
1000 người thế hệ sau để sao cho 1000 người "hậu duệ" này sẽ leo cao hơn họ. Và nếu 1000 người sau lại
thất bại, những người giỏi nhất trong số họ sẽ lại truyền "kinh nghiệm" của mình cho thế hệ 1000 người tiếp
nữa để những người thế hệ 3 này leo cao hơn nữa. Tiến trình cứ thế tiếp tục cho đến lúc đến một thế hệ
nào đó, có một người leo đến đỉnh đồi cao nhất hay hết thời gian cho phép. Trong trường hợp hết thời
gian cho phép thì trong toàn bộ các thế hệ, người nào leo cao nhất sẽ được chọn.
Thế đấy, bạn đã hiểu được tư tưởng chính của thuật giải di truyền rồi đó. Rất đơn giản, thay vì chỉ phát sinh
một lời giải, ban đầu ta phát sinh một lúc nhiều (thậm chí rất nhiều) lời giải cùng lúc. Sau đó, trong số lời giải
được tạo ra, chọn ra những lời giải tốt nhất để làm cơ sở phát sinh ra nhóm các lời giải sau với nguyên tắc
"càng về sau" càng tốt hơn. Quá trình tiếp diễn cho đến lúc tìm được một lời giải tối ưu.
Đó là tư tưởng sơ khởi ban đầu của thuật giải di truyền. Càng về sau, người ta càng hoàn thiện hơn
phương pháp luận của ý tưởng này, dẫn đến sự ra đời của một hệ thống hoàn chỉnh các phương pháp,
nguyên lý dùng trong thuật giải di truyền. Người có công đầu trong lĩnh vực này là giáo sư John Holland.
Ông đã đưa ra lý thuyết này tiên trong một cuốn sách mang tên "Adaptation in Natural and Artificial
Systems", xuất bản năm 1975. Phần đọc thêm của chương sẽ cung cấp cho các bạn đầy đủ thông tin về
John Holland.
2. THUẬT GIẢI DI TRUYỀN
Từ phần này trở đi, chúng ta sẽ cùng nhau tìm hiểu thuật giải di truyền – một mô hình khá mới mẻ, có nhiều
ứng dụng hấp dẫn và vẫn được tiếp tục nghiên cứu trên khắp thế giới – thuật giải cho phép chúng ta tạo ra
được những chương trình máy tính có khả năng tự lập trình cho chính nó.
Thuật giải di truyền (GA) là kỹ thuật chung giúp giải quyết vấn đề-bài toán bằng cách mô phỏng sự tiến hóa
của con người hay của sinh vật nói chung (dựa trên thuyết tiến hóa muôn loài của Darwin) trong điều kiện
qui định sẵn của môi trường. GA là một thuật giải, nghĩa là mục tiêu của GA không nhằm đưa ra lời giải
chính xác tối ưu mà là đưa ra lời giải tương đối tối ưu.
Trong các tài liệu về GA, người ta thường đề cập đến hai thuật ngữ là "thuật giải di truyền" và "lập trình di
truyền". Theo các tài liệu này, "thuật giải di truyền" chỉ sử dụng cấu trúc dữ liệu là chuỗi số nhị phân còn
"lập trình di truyền" nghĩa là sử dụng cấu trúc dữ liệu tổng quát. Sở dĩ có cách hiểu như thế vì ý niệm thuật
giải di truyền xuất hiện trước và ban đầu người ta chỉ áp dụng nó với cấu trúc dữ liệu là chuỗi nhị phân. Về
sau, người ta mới đưa ra cách áp dụng thuật giải này trên các cấu trúc dữ liệu tổng quát hơn nên gọi là lập
trình di truyền. Theo chúng tôi, trong tài liệu này, chúng tui quan niệm rằng, "thuật giải di truyền" là một
phương pháp giải quyết vấn đề-bài toán bằng cách mô phỏng quá trình tiến hóa-thích nghi của sinh vật.
Còn "lập trình di truyền" là kỹ thuật lập trình sử dụng "thuật giải di truyền" để giải quyết vấn đề-bài toán trên
máy tính. Do đó, khi nói đến "thuật giải di truyền" chúng ta chỉ lưu tâm đến khía cạnh thuật giải mà không
quan tâm đến việc cài đặt nó ra sao. Ngược lại, khi nói đến "lập trình di truyền" ta quan tâm nhiều hơn đến
việc cài đặt.
Theo đề xuất ban đầu của giáo sư John Holland, một vấn đề-bài toán đặt ra sẽ được mã hóa thành các
chuỗi bit với chiều dài cố định. Nói một cách chính xác là các thông số của bài toán sẽ được chuyển đổi và
biểu diễn lại dưới dạng các chuỗi nhị phân. Các thông số này có thể là các biến của một hàm hay hệ số
của một biểu thức toán học. Người ta gọi các chuỗi bit này là mã genome ứng với mỗi cá thể, các genome
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
đều có cùng chiều dài. Nói ngắn gọn, một lời giải sẽ được biểu diễn bằng một chuỗi bit, cũng giống như mỗi
cá thể đều được quy định bằng gen của cá thể đó vậy. Như vậy, đối với thuật giải di truyền, một cá thể chỉ
có một gen duy nhất và một gen cũng chỉ phục vụ cho một cá thể duy nhất. Do đó, gen chính là cá thể và cá
thể chính là gen nên ta sẽ dùng lẫn lộn thuật ngữ gen và cá thể từ đây về sau.
Ban đầu, ta sẽ phát sinh một số lượng lớn, giới hạn các cá thể có gen ngẫu nhiên - nghĩa là phát sinh một
tập hợp các chuỗi bit ngẫu nhiên. Tập các cá thể này được gọi là quần thể ban đầu (initial population). Sau
đó, dựa trên một hàm nào đó, ta sẽ xác định được một giá trị gọi là độ thích nghi - Fitness. Giá trị này, để
đơn giản cho bạn đọc lúc đầu, có thể tạm hiểu chính là độ "tốt" của lời giải hay độ cao trong tìm...