Báo cáo nghiên cứu khoa học: Chiến lược tiến hóa song song

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
3.2.3. Mô hình khuếch tán (Diffusion model)…………………17
CHƢƠNG III: SỬ DỤNG KHUNG CHIẾN LƢỢC TIẾN HÓA ĐỂ GIẢI
QUYẾT BÀI TOÁN SPHERE…………………………………………………17
1.
Sử dụng khung ES giải quyết bài toán sphere…………………….17
1.1 Định nghĩa bài toán Sphere……………………………………17
1.2 Khung bài toán Sphere………………………………………...18
2.
Kết quả thực nghiệm………………………………………………..20

Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN

2

Chiến lược tiến hóa song song

LỜI NÓI ĐẦU
Ngày nay song song với qúa trình phát triển khoa học công nghệ va kỹ
thuật thì ngành khoa học tính toán đã đóng vai trò quan trọng. Nó đã đạt được
nhiều thành tựu rực rỡ với những bước tiến nhảy vọt. Việc áp dụng các thành tựu
này vào các lĩnh vực đời sống, xã hội của con người ngày càng tăng và có ảnh
hưởng tới hầu hết các công việc trong đời sống hàng ngày, công nghệ thông tin là
một trong những ngành khoa học đó. Trên thế giới cũng như ơ Việt Nam, công
nghệ thông tin đã trở thành một ngành công nghiệp mũi nhọn, nó là một ngành
khoa học không thể thiếu trong việc áp dụng vào các hoạt động xã hội như: Quản
lý, Kinh tế, Thông tin…đặt biệt là để giải quyết các vấn đề mà trước đây tưởng
như không thể làm được.
Tối ưu hóa là một trong những bài toán kinh điển trong nhiều lĩnh vực của
cuộc sống từ nhu cầu đơn giản của từng cá nhân đến nhu cầu phức tạp của các tổ
chức kinh tế, chính trị và xã hội. Tuy nhiên các bài toán tố ưu trên thực tế lại hiếm
khi đòi hỏi sự tối ưu tuyệt đối mà chỉ đòi hỏi sự tối ưu đủ tốt theo một tiêu chuẩn
nào đó. Hơn nữa, việc tìm ra sự tối ưa tuyệt đối nhiều lúc không thể thực hiện
được do bài toán đặt ra quá phức tạp. Chẳng hạn trong sản xuất kinh doanh, người
ta thường tìm cách tối thiểu chi phí sản xuất. Và dĩ nhiên, họ chỉ cần một giải pháp
mà theo đó, chi phí giảm đến một mức độ nào đó là đủ chứ không nhất thiết phải
thực sự thấp nhất. Đây chính là một điều kiện rất thuận lợi để áp dụng “chiến lược
tiến hóa”.
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.

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
CHƢƠNG I: TỔNG QUAN VỀ CHIẾN LƢỢC TIẾN HOÁ
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:
 Thuật toán di truyền duy trì một tập hợp các lời giải có thể do đó có nhiều
cách để chọn lời giải thích hợp.
 Thuật toán di truyền giúp tìm ra lời giải tối ưu trong điều kiện thời gian và
không cho phép.
 Thuật toán di truyền duyệt xét toàn bộ các lời giải của vấn đề, thay vì chỉ để
ý đến lời giải chính xác và duy nhất như toán học giải thích đã dùng trước
đây.
Nhƣợc điểm của giải thuật di truyền:
 Thuật toán di truyền cổ điển đòi hỏi biểu diễn lời giải dưới dạng xâu nhị
phân. Trong khi đó, lời giải của các bài toán trong thực tế thường có cấu
trúc tự nhiên như mảng, bản ghi, cây.
 Các kết quả mà Thuật toán di truyền mang lại không được chính xác như
các phương pháp tìm kiếm khác.
 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.

Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN

4

Chiến lược tiến hóa song song
 Đối với những bài toán có nhiều ràng buộc phức tạp thì các bài toán từ di
truyền truyền thống tỏ ra kém hiệu quả.
 Nếu chọn mô hình không phù hợp, thuật tóan di truyền sẽ hội tụ sớm hơn
và cuộc tìm kiếm lời giải chấm dứt sau một thời gian ngắn. Những cuộc tìm
kiếm ngắn thường không tạo ra kết quả tốt, cũng giống như những gì đã
xảy ra trong thực tế.
Để khắc phục những nhược điểm trên, Ingo Rechenberg(1973) đã đưa ra 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 đó là
“Chiến lược tiến hóa”.
2. Tổng quan về 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 thuật toán di truyền cổ điển còn
có 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
Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN

5