TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO KHOA HỌC
ĐỀ TÀI:
GIẢI THUẬT DI TRUYỀN SONG SONG VÀ ỨNG DỤNG GIẢI
BÀI TOÁN MAX- SAT
Giảng viên hướng dẫn : Thầy Đỗ Trung Kiên
Sinh viên thực hiện : Nguyễn Thị Lụa – K54C
Đỗ Văn Quang – K55B
Trần Đăng Doanh- K55B
Đề tài: thuật toán di tuyền song song và ứng dụng giải quyết bài toán Max-sat
MỤC LỤC
LỜI MỞ ĐẦU……………………………………………………………………2
Chương I : Tổng quan ….………………………………………………………..3
1. Tổng quan thuật toán di truyền ………………………………………………4
1.1 Khái niệm……………………………………………………………………..4
1.2 Cấu trúc của thuật toán di truyền …………………………………………….7
2. Ví dụ minh họa………………………………………………………………12
2.1 Bài toán Max-sat …………………………………………………………….12
2.2 Giải thuật di truyền giải quyêt bài toán Max-sat……………………………..14
Chương II : Xây dựng thuật toán di truyền ……………………………………...14
1. Khung thiết kế thuật toán di truyền ………………………………………...15
1.1 Lớp provides – lớp cung cấp………………………………………………..15
1.2 Lớp Requide – Lớp yêu cầu ………………………………………………..16
2. Khung thuật toán tuần tự …………………………………………………….20
3. Khung thuật toán song song ………………………………………………….22
3.1 Lựa chọn phần cứng ………………………………………………………….22
3.2 Lựa chọn phần mềm………………………………………………………….22
Chương III : sử dụng khung thuật toán di truyền giải quyết bài toán Maxsat……26
1. cài đặt bài toán Max-sat………………………………………………………...26
1.1 file cấu hình .cfg……………………………………………………………….26

Thuật toán di truyền cổ điền là các kỹ thuật phỏng theo quá trình thích nghi
tiến hóa của các quần thể sinh học dựa trên học thuyết Darwin.
Tư tưởng của thuật toán di truyền là mô phỏng các hiện tượng tự nhiên: Kế
thừa và đấu tranh sinh tồn để cái tiến lời giải và khảo sát không gian lời giải khái
niệm kế thừa và đấu tranh sinh tồn được giải thích qua thí dụ về sự tiến hóa của
một quần thể thỏ như sau:
Có một quần thể thỏ, trong đó có một số con nhanh nhẹn và thông minh hơn
những con khác. Những chú thỏ nhanh nhẹn và thông minh có xác suất bị chồn
cáo ăn thịt nhỏ hơn, do đó cũng tồn tại dể làm những gì tốt nhất có thể : Tạo thêm
nhiều thỏ tốt. Dĩ nhiên, một số thỏ chậm chạp đần độn cũng sống sót vì may mắn.
Quần thể những chú thỏ còn sống sót sẽ bắt đầu sinh sản. Việc sinh sản này sẽ tạo
ra một hỗn hợp tốt về "nguyên liệu di truyền thỏ". Một số thỏ chậm chạp có con
với những con thỏ nhanh, một số nhanh nhẹn có con với thỏ nhanh nhẹn, một số
thông minh với thỏ đần độn… Và trên tất cả thiên nhiên lại ném vào một con thỏ
"hoang dã" bằng cách làm đột biến nguyên liệu di truyền thỏ. Những chú thỏ con
do kết quả này sẽ nhanh hơn và thông minh hơn những con thỏ trong quần thể gốc
vì có nhiều bố mẹ nhanh nhẹn và thông minh hơn đã thoát chết khỏi chồn cáo.
Khi tìm kiếm lời giải tối ưu , thuật toán di truyền cũng thực hiện các bước
tương ứng với câu chuyện đấu tranh sinh tồn của loài thỏ.
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
4
Đề tài: thuật toán di tuyền song song và ứng dụng giải quyết bài toán Max-sat
Thuật toán di truyền sử dụng các thuật ngữ vay mượn của di truyền học. Ta có
thể nói về các cá thể (hay kiểu gen, cấu trúc) trong một quần thể, những cá thể này
cũng còn được gọi là chuỗi hay các nhiễm sắc thể.
Mỗi kiểu gen (ta gọi là một nhiễm sắc thể) sẽ biểu diễn một lời giải của bài
toán đang giải (ý tưởng của một nhiễm sắc thể cụ thể được người sử dụng xác
định trước), một tiến trình tiến hóa được thực hiện trên một quần thể các nhiễm
sắc thể tương ứng với một quá trình tìm kiếm lời giải trong không gian lời giải.
Tìm kiếm đó cần cân đối hai mục tiêu: Khai thác những lời giải tốt nhất và khảo

nghi của cá thể trong quần thể ban đầu là không xác định.
Để cải thiện tính thích nghi của quần thể người ta tìm cách tạo ra quần thể
mới. Có hai cách thao tác thực hiện trên thế hệ hiện tại để tạo ra một thế hệ khác
với độ thích nghi tốt hơn.
Thao tác đầu tiên là sao chép nguyên mẫu một nhóm các cá thể tốt từ thế hệ
trước rồi đưa sang thế hệ sau (selection). Thao tác này đảm bảo độ thích nghi của
thế hệ sau luôn được giữ ở một mức độ hợp lý. Các cá thể được chọn thông
thường là các cá thể có độ thích nghi cao nhất.
Thao tác thứ hai là tạo ra cá thể mới bằng cách thực hiện các thao tác sinh sản
trên một số cá thể được chọn từ thế hệ trước, thông thường cũng là những cá thể
có độ thích cao. Có hai loại thao tác sinh sản: một là thao tác lai tạo (crossover),
hai là đột biến (mutalion). Trong thao tác lai tạo, từ gen của hai cá thể được chọn
trong thế hệ trước sẽ được phối hợp với nhau (theo một quy tác nào đó) để tạo
thành hai gen mới.
Thao tác chọn lọc và lai tạo giúp tạo ra thế hệ sau. Tuy nhiên, nhiều khi do thế
hệ khởi tạo ban đầu có đặc tính chưa phong phú và chưa phù hợp nên các cá thể
không rải đều được không gian của bài toán (tương tự như trường hợp leo đồi, các
người leo đồi tập trung dồn vào một góc trên vùng đất). Từ đó, khó có thể tìm ra
lời giải tối ưu cho bài toán. Thao tác đột biến sẽ giúp giải quyết được vấn đề này.
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
6
Đề tài: thuật toán di tuyền song song và ứng dụng giải quyết bài toán Max-sat
Đó là sự biến đổi ngẫu nhiên một hoặc nhiều thành phần gen của một cá thể ở thế
hệ trước tạo ra một cá thể hoàn toàn mới ở thế hệ sau. Nhưng thao tác này chỉ
được phép sảy ra với tần xuất rất thấp (thường dưới 0.01), vì thao tác này có thể
gây xáo trộn và làm mất đi những cá thể chọn lọc và lai tạo có tính thích nghi cao,
dẫn đến thuật toán không còn hiệu quả.
Thế hệ mới được tạo ra lại được xử lý như thế hệ trước cho đến khi có một cá
thể đạt được giải pháp mong muốn hoặc đạt đến thời gian giới hạn.
1.2 Cấu trúc của giải thuật di truyền như sau:

t
n
}. Mỗi lời giải x
t
i
được đánh giá "độ thích nghi ", hay độ "tốt" của
lời giải.
Phép chọn lọc (select): Phép chọn là quá trình loại bỏ các cá thể xấu trong quần
thể để chỉ dữ lại trong quần thể các cá thể tốt.
Phép chọn được mô phỏng:
 Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần.
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
8
Đề tài: thuật toán di tuyền song song và ứng dụng giải quyết bài toán Max-sat
 Loại bỏ các cá thể cuối dãy để chỉ giữ lại n cá thể tốt nhất. Giả sử ở đây
quần thể có kích thước cố định n.
Có nhiều phương pháp chọn lọc Nhiễm sắc thể:
o Chọn lọc Roulette (Roulett Wheel Selection).
o Chọn lọc xếp hạng (Rank Selection).
o Chọn lọc cạnh tranh (Tournament Selection)
Quá trình sinh sản: Có hai loại thao tác sinh sản
 Phép lai tạo (Crossover): là quá trình hình thành nhiễm sắc thể mới trên cơ sở
nhiễm sắc thể cha mẹ bằng cách ghép một hay nhiều đoạn gen của hai hay nhiều
nhiễm sắc thể cha mẹ với nhau.
Có những phương pháp lai ghép sau:
o Lai ghép ánh xạ từng phần (PMX Partial Mapped Crossover).
o Lai ghép có trật tự (OX order Crossover).
o Lai ghép dựa trên vị trí (Position Based Crossover).
o Lai ghép dựa trên thứ tự (Order Base Crossover).
o Lai ghép có chu trình (CX cycle Crossover).

0 1 1 1 0 0 1 1 1 0
Thì việc trao đổi chéo các nhiễm sắc thể sau gen thứ năm sẽ tạo ra hai con:
Child 1:
1 0 1 0 1 0 1 1 1 0
Child 2:
0 1 1 1 0 1 1 0 0 1
 Phép đột biến (mutalion): Phép đột biến là hiện tượng cá thể con mang một
(hoặc một số) tính trạng có trong mã di truyền của cha mẹ, tức là sự sửa đổi một
hoặc một vài gen của một nhiễm sắc thể chọn bằng cách thay đổi ngẫu nhiên với
xác suất là tỷ lệ đột biến.
Không ai có thể đánh giá được phương pháp đột biến nào tốt hơn, do đó có
một vài phương pháp đơn giản, cũng có vài trường hợp khá phức tạp. Người ta
thường chọn một trong những phương pháp sau :
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
10
Đề tài: thuật toán di tuyền song song và ứng dụng giải quyết bài toán Max-sat
o Đột biến đảo ngược (Inversion Mutation).
o Đột biến chèn (Insertion Mutation)
o Đột biến thay thế (Displacement Mutation).
o Đột biến tương hỗ (Reciprocal Exchange).
o Đột biến chuyển dịch (Shift Mutation).
Phép đột biến xảy ra với xác suất p
m
nhỏ hơn rất nhiều so với xác suất lai p
c.
Phép
đột biến có thể được mô phỏng:
 Chọn ngẫu nhiên một cá thể bất kỳ cha mẹ trong quần thể.
 Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m với 1≤ k ≤ m.
 Thay đổi gen thứ k và trả cá thể này về quần thể để tham gia vào quá