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.

theo kiểu leo đồi. Vì phát sinh ngẫu nhiên nên độ "tốt" của lời giải hay tính thích
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
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
vấn đề này. Đó 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.

,…, x
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).

Ví dụ : Hai nhiễm sắc thể cha mẹ :
Parent 1:
1 0 1 0 1 1 1 0 0 1
Parent 2:
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:

ngược lại.
2. Một số ví dụ minh họa.
2.1 Bài toán Max-sat.
Vấn đề bài toán SAT (SATisfiability) là vấn đề có tính ứng dụng rộng rãi cả
trong lý thuyết độ phức tạp, trong Trí tuệ nhân tạo hay những lĩnh vực thực tế
khác… Mà cần đưa ra những giải pháp tốt để giải quyết.
Bài toán SAT: Cho tập m mệnh đề C= {C
1,
C
2
, C
3
, …,C
m
} bao gồm n giá trị
biến x
1
x
2
, …, x
n
. Bài toán SAT giải quyết vấn đề có tồn tại hay không? Sự phân
bố trên các biến sao cho các mệnh đề thỏa mãn đồng thời. Bài toán Max-Sat
(Maximum Satisfiability) là bài toán tìm sự phân bố trên các biến sao cho các
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
12
Đề 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ệnh đề thỏa mãn là lớn nhất. Vấn đề giải quyết cả hai bài toán SAT và Maxsat
là thuộc bài toán NP- khó.
Có rất nhiều giải thuật thuật được đề xuất và đã đạt được những tiến bộ quan

i
nhận giá trị 0 (False) hoặc 1 (True).
o Lai ghép: là phép toán mục đích xây dựng một quần thể mới (quần thể
con) từ quần thể ban đầu.
o Đột biến: là phép toán dùng phát sinh cá thể mới .
CHƯƠNG II : XÂY DỰNG KHUNG THUẬT TOÁN DI TRUYỀN
Để giải quyết các bài toán với độ phức tạp rất lớn hoặc những bài toán có
NP-khó thì một giải pháp là sử dụng các thuật toán chẳng hạn như thuật toán di
truyền. Xây dựng khung chương trình (Skeletons) cần thiết cho những người
muốn áp dụng các thuật toán nổi tiếng để giải bài toán khó, khi giải quyết những
bài toán tương đối giống nhau cùng sử dụng một tư tưởng của của thuật giải, sử
dụng các hàm và thư viện giống nhau, việc viết đi viết lại những hàm và thư viện
này khiến mất thời gian và công sức. Xây dựng khung chương trình nhằm giảm
thiểu quá trình code cho người sau, cho những người sau thử nghiệm bài toán lập
trình song song để hiểu bài toán mà chưa cần hiểu sâu về code và quá trình phát
triển
1. Thiết kế khung thuật toán di truyền.
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
14
Đề 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
Khung thuật toán di truyền bao gồm hai lớp chính là: lớp Provides và
Requies
1.1 Lớp Provides (lớp cung cấpi) làm nhiệm vụ thi hành bên trong bộ khung của
bài toán, nó tạo ra nhiều phương án cho bài toán.
o Hàm Solver: Hiển thị trạng thái, xác suất, xác suất đột biến và chọn ra
cha mẹ và con cái. Solver gồm một số hàm:
Class Solver {
Run() // Thực thi thuật toán
StartUp() // Thiết lập các thông số.
DoStep() // Thực hiện theo khung thuật toán newGA,

kích thước, số mệnh đề và chiều dài mệnh đề.
- Problem& Problem::operator= (const Problem& pbm{}: Tạo ra
mảng một chiều _clauses gồm số mệnh đề, số phần từ  tạo ra mảng 2
chiều kích thước số mệnh đề, độ dài mệnh đề. Lưu các phần tử mệnh đề
vào mảng. Tạo ra biến _dimension. Truyền giá trị số mệnh đề trong
pbm.numlause() của lớp Pro vào _numclause trong mảng clause.
- Direction Problem::direction() const{}: Trả ra kích thước mệnh đề
lớn nhất.
- int Problem::dimension() const{}: Trả ra kích thước mệnh đề.
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
16
Đề 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
- int Problem::numclause() const : trả ra số mệnh đề.
- int Problem::lenclause() const : trả ra độ dài mệnh đề
- int *Problem::clause(const int i) const:trả ra giá trị của mệnh đề thứ i
o Lớp Solution :định nghĩa một giải pháp có khả thi hay không
Khai báo lớp Sulutioncho bài toán Maxsat:
Class Solution {
friend ostream& operator<< (ostream& os, const Solution& sol); // đưa ra
các thông số của một lời giải
friend istream& operator>> (istream& is, Solution& sol); // nhận vào các
thông số của một lời giải
….
void initialize(); // Hàm khởi tạo bộ giá trị ngẫu nhiên cho các phần tử trong
lời giải
double fitness (); // Hàm tính độ thích nghi làm cơ sở đánh giá lời giải.
Một số hàm trong lớp Solution:
- Solution& Solution::operator= (const Solution &sol): Gán các giá trị
trong các phương thức của lớp solution cho các biến.
- bool Solution::operator== (const Solution& sol) const: Lời giải bài

virtual void UpdateFromState(const StateCenter& _sc);
};
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
18
Đề 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 Lớp đột biến (Mutation)
requires class Mutation: public Intra_Operator
{
public:
Mutation();
virtual ~Mutation();
friend ostream& operator<< (ostream& os, const Mutation&
mutation);
void mutate(Solution& sol) const;
//Hiển thị đột biến qua tất cả các giải pháp trong mảng Sols
virtual void execute(Rarray<Solution*>& sols) const;
virtual void setup(char line[MAX_BUFFER]);
virtual void RefreshState(const StateCenter& _sc) const;
virtual void UpdateFromState(const StateCenter& _sc);
};
2. Khung thuật toán tuần tự.
Sử dụng khung thuật toán di truyền cho bài toán (newGA) đầu vào đưa vào
gồm hai file cấu hình.
Gọi tới hàm Problem: Hiển thị màn hình thông số đưa vào.
Hàm void Solver_sqe :: DoStep()
Class Solver_sqe:: DoStep(){
current_iteration(current_iteration()+1);
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
19
Đề 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

Solver.run(); // thực hiện hàm run
Nếu là máy chủ (pid()= =0) thì
{
Gọi đến hàm hiện trạng thái (show_state());
Đưa ra giải pháp tốt nhất;
Đưa ta Độ thích nghi tốt nhất;
}
3. Khung thuật toán song song.
3.1 Lựa chọn mô hình phần cứng:
Có hai mô hình đó là: mô hình phần cứng phân tán và mô hình phần cứng dùng
chung.
+ Mô hình phần cứng dung chung:
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
21
Đề 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
Ưu điểm: tốc độ nhanh
Nhược điểm: giá thành cao.
+ Mô hình phần cứng phân tán:
Ưu điểm: dễ cài đặt.
Nhược điểm: tốc độ chậm.
Vì những lý do trên ta sử dụng mô hình phần cứng phân tán để việc nói chuyện
giữa các máy tính được dễ dàng.
Trong mô hình này ta sử dụng các thư viện MPI và thư viện NetStream nhằm tạo
ra sự thân thiện với người sử dụng.
3.2 Lựa chọn mô hình phần mềm:
Có ba mô hình phần mềm:
- Mô hình chủ - khách (Master_slave):ở đây một bộ vi xử lý đơn duy trì việc
điều khiển qua các vùng chọn và sử dụng bộ vi xử lý khác cho việc xử lý chéo,
biến đổi và giá trị đơn lẻ. tuy nhiên giải thuật chỉ hữu ích cho một số lượng nhỏ
bộ vi xử lý và một số lượng lớn thời gian, mặt khác một giao tiếp tốt làm tăng

worst_cost=current_population.worst_cost();
average_cost=current_population.average_cost();
standard_deviation=current_population.standard_deviation();
time_spent_in_trial = _used_time(start_trial);
total_time_spent = start_global + time_spent_in_trial;
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
23
Đề 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
// refresh state with these values
RefreshState();
RefreshCfgState();
// in this iteration i have to send data about my local state to the
global state
if ((int)current_iteration() % params.refresh_global_state()
==0)
{
send_local_state_to(mypid);
UpdateFromCfgState();
}
_stat.update(*this);
_userstat.update(*this);
// if (display_state()) show_state();
}
Hàm void main_lan();
Sử dụng khung newGA;
Mở file f1 là “newGA.cfg” để đọc vào cấu hình
Đọc file f1>>cfg;
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
24
Đề 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