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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
2MỤC LỤC LỜI MỞ ĐẦU……………………………………………………………………2

Với khả năng hiện nay, máy tính đã giúp giải được rất nhiều bài toán khó mà
trước đây thường bó tay. Mặc dù vậy vẫn có một số lớn các bài toán thú vị mà
chưa có giải thuật hợp lý để giải chúng. Trong đó các bài toán tối ưu là nững bài
toán thường gặp trong thực tiễn.
Trong thực tiễn, có nhiều bài toán tối ưu quan trọng đòi hỏi những thuật toán
có chất lượng cao. Ví dụ ta có thể dùng phương pháp mô phỏng luyện thép để
giải quyết bài toán tìm đường đi ngắn nhất cho xe cứu hỏa hay bài toán người du
lịch… Cũng có nhiều bài toán tối ưu tổ hợp (trong đó có nhiều bài toán được
chúng minh là NP - đủ) có thể giải gần đúng trên máy tính hiện đại bằng kỹ thuật
Monte - Carlo.
Nói chung bài toán tối ưu có thể xem như bài toán tìm kiếm giải pháp tốt
nhất trong không gian vô cùng lớn các giải pháp. Khi không gian tìm kiếm nhỏ,
những phương pháp cổ điển như trên cũng đủ thích hợp, nhưng khi không gian
tìm kiếm lớn phải dùng kỹ thuật trí tuệ nhân tạo đặc biệt. Thuật giải di truyền
(GA) là một trong những kỹ thuật đó.

Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
4
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
sát không gian tìm kiếm. Leo đồi là một ví dụ về chiến lược cho phép khai thác
và cải thiện lời giải tốt nhất hiện hành nhưng leo đồi lại bỏ qua việc khảo sát
không gian tìm kiếm. Ngược lại, tìm kiếm ngẫu nhiên là một ví dụ điển hình của
chiến lược khảo sát không gian tìm kiếm mà không chú ý đến việc khai thác
những vùng đầy hứa hẹn của không gian. Thuật toán di truyền (GA) là phương
pháp tìm kiếm (độc lập miền) tạo được sự cân đối đáng kể giữa việc khai thác và
khảo sát không gian tìm kiếm.
Thực ra, GA thuộc lớp các thuật giải xuất sắc, nhưng lại rất khác những thuật
giải ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên.
Khác biệt quan trọng giữa tìm kiếm của GA và các phương pháp tìm kiếm khác
là GA duy trì và xử lý một tập các lời giải (ta gọi là một quần thể)
Theo đề xuất 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 với chiều dài bit 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 hoặc hệ số của
một biểu thức toán học. Người ta gọi các chuỗi bít này là mã genome ứng với
mỗi cá thể, các genome đề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 bít, cũ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ó
Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
6

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 đó,

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.
1.2 Cấu trúc của giải thuật di truyền như sau:

1. t = 0
2. initialize P(t)
Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
8

3. evaluate structures in P(t)
4. while not end do
5. t = t + 1
6. select C(t) from P(t - 1)
7. recombine structures in C(t) forming C'(t)
8. mutate structures in C' (t) forming C'' (t)
9. evaluate structures in C''(t)
10. replace P(t) from C''(t) and/or P (t - 1)

Khởi tạo quần thể (initialize): Quần thể đầu tiên được khởi tạo một cách ngẫu
nhiên từ tập hợp những cá thể riêng lẻ. Kích cỡ của quần thể đầu tiên phụ thuộc
vào yếu tố tự nhiên của bài toán, nhưng nhìn chung thì một bài toán có đến hàng

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).
o Lai ghép thứ tự tuyến tính (LOX Linear order Crossover).
Phép lai tạo xảy ra với xác suất p
c
, được mô phỏng như sau:
 Chọn ngẫu nhiên một hay nhiều cá thể bất kỳ trong quần thể. Giả
sử các nhiễm sắc thể của cha mẹ đều có m gen.
 Tạo một số ngẫu nhiên trong khoảng từ 1 đến m - 1 (được gọi là
điểm lai). Điểm lai chia các chuỗi cha mẹ có độ dài m thành hai
nhóm chuỗi con với độ dài m
1
, m
2
hai chuỗi nhiễm sắc thể mới là
m
11

xác suất là tỷ lệ đột biến.
Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
11

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 :
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á
trình tiến hóa tiếp theo.
NST1
0 1 1 1 1 0 1 1 1 0
NST1
0 1 1 1 0 0 1 1 1 0

Một thuật giải di truyền, giải một bài toán được cho phải có năm thành phần:
 Một cấu trúc dữ liệu biểu diễn không gian lời giải của bài toán.

Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
13

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
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
trọng. Những giải thuật này được chia thành hai lớp: Giải thuật đầy đủ (chính
xác) và giải thuật chưa đầy đủ.
 Thuật giải đầy đủ:Giải thuật được coi là tốt dựa trên thủ tục DPLP. SAT2
là ví dụ khá nổi tiếng về giải thuật đủ. Giải thuật Nhánh cận và kết nối
dựa vào thủ tụ DPLP là một trong những giải thuật chính xác và mạnh
nhất để giải quyết bài toán Max-Sat. Giải thuật BnB có thể được vận dụng

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
Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
15

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.
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

int _numvar;
int _numclause;
int _lenclause;
int ** _clauses;
} Khai báo hàm trong Problem.
- istream& operator>> (istream& is, Problem& pbm){}: Nhập vào
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
Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
17

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 đề.
- 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:

nhật lời giải khả thi vào trong danh sách lời giải khả thi
o Lớp kiểm tra điều kiện dừng (StopCondition).
Để xác định điều kiện dừng của bài toán, trong từng bài toán thì điều kiện
dừng sẽ khác nhau, thường căn cứ vào một hoặc một vài tham số như số thế hệ,
thời gian chạy, các điều kiện đặc thù của bài toán.

o Lớp chéo hóa Crossover.

requires class Crossover: public Intra_Operator
{
public:
Crossover();
virtual ~Crossover();

friend ostream& operator << (ostream& os, const Crossover& cross);
Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
19 void cross(Solution &sol1,Solution &sol2) const;
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);
};

o Lớp đột biến (Mutation)
requires class Mutation: public Intra_Operator

current_evaluations(current_population.evaluations());
// Lấy giá trị phù hợp để thực hiện trong quần thể đang thực thi.

best_cost=current_population.best_cost();
best_solution=current_population.best_solution();
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;

// lấy lại trạng thái với nhứng giá trị này
RefreshState();
Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
21

RefreshCfgState();

if( (current_iteration() % params.refresh_global_state()) == 0)
UpdateFromCfgState(); _stat.update(*this);
_userstat.update(*this);

if (display_state())
show_state();


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
khả năng của xử lý song song.
Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
23

- Mô hình đảo (Island model): Trong mô hình này mọi bộ vi xử lý chạy giải
thuật tiến hóa một cách độc lập, sử dụng các quần thể phụ riêng biệt các bộ vi xử
lý hợp tác với nhau bằng việc thay đổi vị trí một cách đều đặn. Mô hình đảo đặc
biệt thích hợp cho các nhóm máy tính khi giao tiếp bị hạn chế.
- Mô hình khuếch tán (Diffusion model): mỗi cá nhân là một không gian
được sắp xếp và kết hợp với cá nhân khác từ một mạng nội bộ bên cạnh. Khi xử
lý song song có rất nhiều bộ vi xử lý giao tiếp với nhau (như là những cá nhân
giao tiếp với hàng xóm trong mọi tương tác), nhưng giao tiếp chỉ trong nội bộ.
Vì vậy mô hình này chỉ phù hợp với hệ thống máy tính song song lớn với mạng
nội bộ tốc độ cao.
Do đó ta sẽ lựa chọn mô hình phần mềm là mô hình đảo (Island model).
Hàm void Solver_lan:: DoStep()

global state
if ((int)current_iteration() % params.refresh_global_state()
==0)
{
send_local_state_to(mypid);
UpdateFromCfgState();
}

_stat.update(*this);
Đề 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
Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B
25

_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;
Mở file f2 để đọc “Problem.dat”
Đọc file f2>>pbm
Thực hiện hàm SetUpParams
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());