Chiến lược tiến hóa song song
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO NGHIÊN CỨU KHOA HỌC
Đề tài: Chiến Lược Tiến Hóa Song Song
Giảng viên : Đỗ Trung Kiên
Sinh viên: Cao Thị Việt Hòa
Lớp K54B
Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN
1
Chiến lược tiến hóa song song
Phụ lục
CHƯƠNG I: TỔNG QUAN VỀ CHIẾN LƯỢC TIẾN HOÁ………………..3
1. Tổng quan giải thuật di truyền………………………………………3
2. Tổng quan về chiến lược tiến hóa…………………………………...4
2.1 Chiến lược tiến hóa là gì……………………………………4
2.2 Lịch sử phát triển của thuật toán chiến lược tiến hóa………5
2.3 Tính chất của thuật toán chiến lược tiến hóa. ……………...5
2.4 Kỹ thuật chiến lược tiến hóa……………………………….5
2.5 Giải thuật chiến lược tiến hóa………………………………6
3. Ví dụ minh họa……………………………………………...............6
CHƯƠNG II: XÂY DỰNG KHUNG ES………………………………………..7
1. Thiết kế khung ES………………………………………………….7
1.1 Các lớp đòi hỏi (Requires)……………………………………...7
1.2 Các lớp cung cấp (Provided)…………………………………...8
2. Khung thuật toán tuần tự………………………………………….14
3. Khung thuật toán song song……………………………………….16
3.1 Mô hình phần cứng………………………………………….....16
3.2 Mô hình phần mềm…………………………………………….16
3.2.1. Mô hình máy chủ-khách (Master-slave)………………...16
3.2.2. Mô hình đảo (Island model)…………………………….17

Xuất phát từ một số nhược điểm của giải thuật di truyền: Các cá thể trong quần thể
trong thuật toán di truyền chỉ là các chuỗi nhị phân. Do đó, rất khó khăn khi áp dụng
thuật toán di truyền cổ điển cho các bài toán trong không gian nhiều chiều và mỗi
NST có độ dài rất lớn,…Vì thế mà các nhà khoa học đã tìm kiếm các phát triển của
giải thuật di truyền để khắc phục các nhược điểm này. Trong khóa Đề tài nghiên
cứu khoa học này tôi đi sâu vào nghiên cứu “Chiến lược tiến hóa”.
Chiến lược tiến hóa là một phát triển của giải thuật di truyền, là một kỹ thuật tối ưu
hóa dựa trên những ý tưởng của sự thích nghi và tiến hóa.
CHƯƠNG I: TỔNG QUAN VỀ CHIẾN LƯỢC TIẾN HOÁ
Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN
3
Chiến lược tiến hóa song song
1. Tổng quan giải thuật di truyền.
Thuật toán di truyền (Genetic Algorithms) là kỹ thuật giúp giải quyết bài
toá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 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 luôn thay đổi của
môi trường sống. Thuật toán di truyền là một hướng tiếp cận tính toán gần đúng,
nghĩa là mục tiêu của thuật toán di truyền 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. Thuật toán di truyền về bản chất là thuật
toán tìm kiếm dựa theo quy luật của quá trình tiến hóa tự nhiên. Giải thuật kết hợp
sự sống sót của cấu trúc khỏe nhất trong số các cấu trúc biểu diễn các nhiễm sắc thể
với một sự trao đổi thông tin được lựa chọn ngẫu nhiên để tạo thành một thuật toán
tìm kiếm. Thuật toán di truyền nằm trong lĩnh vực tính toán tiến hóa, sử dụng các
biểu diễn nhị phân và các sơ đồ để mô hinhg hóa sự chọn lọc, lai ghép và đột biến.
Các phát triển của giải thuật di truyền:
- Các chiến lược tiến hóa (Evolution strategy) viết tắt là ESs.
- Lập trình tiến hóa (Evolutionary Programming) viết tắt là EP.
- Lập trình di truyền (Genetic Programming) viết tắt là GP.
- Các chương trình tiến hóa (Evolution Programs) viết tắt là Eps.
Ưu điểm của giải thuật di truyền:

tên gọi là phương pháp tính toán tiến hóa.
2.1 Chiến lược tiến hóa là gì?
Trong khoa học máy tính, chiến lược tiến hóa (ES) là một kỹ thuật tối ưu hóa
dựa trên những ý tưởng của sự thích nghi và tiến hóa.
Chiến lược tiến hóa là một lớp con của việc tìm kiếm trực tiếp rất tự nhiên
(và tối ưu), là những phương thức thuộc vào lớp của những thuật toán tiến hóa
(EAs). Nó sử dụng sự đột biến, sự lai ghép, và sự lựa chọn thích ứng tới một quần
thể của những cá thể chứa những giải pháp được đề xuất theo trình tự để tiến hóa
lặp lại tốt hơn và những giải pháp tốt hơn.
Dữ liệu đặc trưng của từng cá thể là những tham số sẽ được tối ưu hóa trong
một quá trình tiến hóa cơ bản. Những tham số sẽ được sắp xếp trong những vector
của những số thực, những thao tác cho sự lai ghép(tréo hóa) và đột biến được định
nghĩa.
2.2 Lịch sử phát triển của thuật toán chiến lược tiến hóa
- Chiến lược tiến hóa (ES) được phát triển tại trường đại học Kỹ Thuật
Berlin vào những năm 1960 và 1970 bởi Ingo Rechenberg (Rechenberg 1973).
Hans Peter Schwefel (Schwefel 1981), giới thiệu sự lai ghép và những quần thể với
nhiều hơn một cá thể, và cung cấp được sự so sánh của ESs với kỹ thuật tối ưu hóa
truyền thống hơn.
2.3 Tính chất của thuật toán chiến lược tiến hóa
- Chiến lược tiến hóa không dựa vào sự mô phỏng chi tiết của những
phương pháp được tìm thấy với sự tiến hóa tự nhiên. Mà có thể đã được kết luận
bởi việc quan sát những thuật ngữ: tiến hóa và chiến lược.
- Trong sự tiến hóa không có chiến lược.
- Chiến lược tiến hóa đơn thuần tập chung vào dịch những cơ chế cơ bản
của sự tiến hóa sinh học cho những vấn đề kỹ thuật tối ưu.
2.4 Kỹ thuật chiến lược tiến hóa
Có 5 kỹ thuật chính như sau:
Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN
5

Khung thuật toán gồm hai phần cơ bản là Provides và Requires.
Lớp Required chỉ định thông tin liên quan đến vấn đề (bài toán). Để cho toàn
bộ khung hoạt động thì các lớp này phải được bổ xung thông tin về bài toán phụ
thuộc .
Lớp Provided thực thi phía bên trong khung bao hàm các thủ tục chung cho
các bài toán giải bằng giải thuật di truyền. Thông thường đối với mỗi giải thuật thì
thường có một số giải pháp, tất cả các mô hình tuần tự được nhóm vào lớp
Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN
6
Chiến lược tiến hóa song song
Solver_Seq. Các mô hình song song được nhóm vào các lớp Solver_Lan và
Solver_Wan.
1.1 Các lớp đòi hỏi (Requires)
Các lớp đòi hỏi được sử dụng để lưu trữ dữ liệu cơ bản của thuật toán. Ta có
thể hình dung các lớp Requre được xây dựng giống như một cái sườn, cái mẫu, và
đối với từng bài toán cụ thể lại phải đắp thêm những thông tin riêng của bài toán đó
cho hoàn chỉnh.
Nhóm các lớp Requires bao gồm các lớp sau:
• Lớp bài toán (Problem)
Diễn tả thông tin bài toán cần giải quyết. Dưới đây là các thủ tục chính trong
lớp bài toán
Trong đó:
- Toán tử chồng cout: Đưa ra các thông số của bài toán pbm theo luồng os.
- Toán tử chồng cin: nhận vào các thông số của bài toán pbm từ luồng is.
• Lớp lời giải (Solution)
Lớp lời giải diễn tả lời giải của bài toán, trong quá trình tiến hoá, chúng ta luôn
duy trì một quần thể các lời giải có thể của bài toán và áp dụng các thao tác của quá
trình tiến hoá lời giải trên quần thể để tìm ra lời giải tối ưu cho bài toán. Dưới đây là
các thủ tục chính trong lớp lời giải:
Trong đó