Lời nói đầu
Những năm gần đây, cùng với sự phát triển của khoa học kỹ thuật, người ta
đã giải quyết được nhiều bài toán hóc búa bằng máy tính. Nhưng bên cạnh đó, vẫn
còn khá nhiều các bài toán vẫn chưa tìm được giải thuật phù hợp để giải nó, đó là
các bài toán tối ưu, trí tuệ nhân tạo và các bài toán xuất phát từ thực tế cuộc sống
như bài toán lập lịch, bài toán điều khiển Robot, bài toán người du lịch,... Đây là các
bài toán có khá nhiều ràng buộc phức tạp, không rõ ràng, ko gian tìm kiếm lớn. Do
đó các phương pháp truyền thống như quay lui vét cạn, leo đồi, mô phỏng luyện
thép, … tỏ ra ít hiệu quả, và người ta đã sử dụng một phương pháp khá tối ưu đó là
phương pháp CHC và sử dụng trong mô hình song song.
Trong bài nghiên cứu này nhóm tác giả nghiên cứu về phương pháp CHC sử
dụng mô hình song song để giải quyết bài toán MAXSAT. Chúng ta sẽ thấy được sự
độ tối ưu khi sử dụng mô hình song song so với mô hình tuần tự về thời gian, độ
thích nghi …
Trong tương lai nhóm sẽ tiếp tục phát triển đề tài nghiên cứu bằng cách sử
dụng thuật toán để giải quyết một số bài toán khác.
Nhóm tác giả xin chân thành cảm ơn sự giúp đỡ tận tình của thầy giáo Đỗ
Trung Kiên đã giúp cho nhóm trong quá trình thực hiện.
Cuối cùng xin chúc hội nghị nghiên cứu khoa học của chúng ta thành công
rực rỡ.
Hà Nội, tháng 04 năm 2008.
Nhóm tác giả.
1
MỤC LỤC
[2]. Sushil J. Louis, A Genetic Algorithm.............................................................................23
[3]. Helmut Pekari and Robert Clariso, MALLBA: instantiating SAT and MAXCUT.......23
[4]. M.B Menai Département d’informatique, ‘Extremal Optimization’ for Max - SAT....23
BÁO CÁO KHOA HỌC
Đề tài:: PHƯƠNG PHÁP CHC SONG SONG
Chương I: Tổng quan về phương pháp CHC
I. Tìm hiểu chung về thuật toán di truyền

thể con được sinh ra ở thế hệ tiếp theo. Vì vậy giải thuật CHC sẽ duy trì được quần
thể tốt nhất mà được bắt gặp qua quá trình tìm kiếm.
Cha mẹ không được phép giao phối nếu như chúng không có sự khác biệt
thích đáng như được xác định bởi ngưỡng giao phối liên tục giảm. Toán tử chéo
(crossover) được sử dụng bởi CHC là toán tử HUX, với HUX là đại diện cho
crossover một nửa không đổi. Toán tử HUX đảm bảo chính xác một nửa của số bit
khác nhau giữa cha mẹ được trao đổi để sản sinh ra con cái.
CHC không được sử dụng các toán tử đột biến trong trường hợp thông thường,
và thực tế cùng với những quần thể nhỏ trong CHC và sự lựa chọn thế hệ giao làm
cho quần thể được hội tụ nhanh chóng. Khi quần thể được hội tụ, CHC sẽ được
khởi động lại từng phần bởi việc sao chép bởi thành viên tốt nhất của quần thể hiện
tại sang một quần thể mới và sinh ra phần còn lại của quần thể mới với những phiên
bản được biến đổi ồ ạt (35% của các bit) của thành viên tốt nhất của quần thể hiện
tại.
3. Sự Chọn lọc Elitist
Trong suốt sự chọn lọc cho việc sinh sản thay vì sự thiên về chọn lọc C(t) cho
việc sinh sản hơn vì lợi ích của những thành viên thực hiện tốt hơn trong quần thể
cha mẹ P(t-1). Mỗi thành viên của P(t-1) được sao chép thành C(t) và được ghép đôi
một cách ngẫu nhiên. (Nói cách khác, C(t) đồng nhất với P(t-1) ngoại trừ khi trật tự
của các cấu trúc đã bị thay đổi). Mặt khác, trong suốt giai đoạn chọn lọc sinh tồn
thay vì thay thế quần thể cha mẹ cũ P(t-1) bằng quần thể con C’(t) để hình thành
P(t), thế hệ con mới được tạo ra phải được cạnh tranh với các thành viên của quần
thể cha mẹ P(t-1) cho sự sinh tồn - ví dụ cạnh tranh chính là thế hệ lai. Cụ thể hơn,
các thành viên của P(t-1) và C’(t) được hoà trộn và được xếp hạng theo sự thích
hợp, và P(t) được tạo ra bằng việc chọn lọc M tốt nhất (trong đó M là kích thước
quần thể), các thành viên của quần thể được hoà trộn. (Trong các trường hợp mà
một thành viên của P(t-1) và một thành việc của C’(t) có sự thích hợp giống nhau,
4
thành viên của P(t-1) được xếp hạng cao hơn). Ta sẽ gọi thủ tục giữ lại các thành
viên được xếp hạng tốt nhất của các quần thể con và quần thể cha mẹ được xáo trộn

nhưng bởi vì các cá thể tốt hơn sẽ có nhiều hậu duệ hơn. Vì vậy, sẽ rất hợp lý khi
một cá thế được giao phối với một trong những họ hàng gần nhất của nó. Cho đến
5
bây giờ, điều này dẫn đến việc lai các cá thể mà chia sẻ rất nhiều Alen, sự thông dò
đối với sự tái tổ hợp nhanh chóng thoái hoá. Mặc dù luôn luôn lai một nửa những sự
khác nhau( sử dụng HUX) sẽ làm chậm đi quá trình này nhưng đôi khi các cá thể
được ghép đôi lại có một vài sự khác biệt. Nếu một hay hai thế hệ con sống sót đối
với sự giao phối này thì nó chắc chắn sự việc như vậy cũng sẽ xảy ra ở thế hệ kế
tiếp.
CHC có một cơ chế bổ sung để làm chậm lại tốc độ của sự quy tụ- một cơ chế
để giúp tránh sự giao phối gần. Trong suốt thời kỳ sinh sản, mỗi thành viên của
quần thể cha mẹ được chọn một cách ngẫu nhiên mà không thay thế và được ghép
đôi cho việc giao phối. Tuy nhiên, trước khi giao phối thì khoảng cách tín hiệu giữa
các thế hệ cha mẹ tiềm năng được tính toán, và nếu một nửa khoảng cách đó
( khoảng cách tín hiệu của các thế hệ con được mong đợi từ các thế hệ cha mẹ) sẽ
không vượt quá ngưỡng khác nhau. Chúng không được giao phối và bị loại ra từ
quần thể con.(ngưỡng khác nhau được thiết lập ở phần bắt đầu cho đến L/4). Chính
vì vậy, chỉ một phần quần thể được giao phối để tạo ra thế hệ con mới trong bất kỳ
thế hệ nào. Không có thế hệ con nào được chấp nhận vào quần thể cha mẹ ( hoặc là
bởi vì không có bạn giao phối tiềm năng hay bởi vì không một thế hệ con nào tốt
hơn quần thể cha mẹ), thì ngưỡng khác nhau sẽ bị giảm đi. Hậu quả của cơ chế này
đó là chỉ có các quần thể cha mẹ tiềm năng và đa dạng hơn được giao phối nhưng
sự đa dạng được đòi hỏi bằng ngưỡng khác nhau tự động giảm khi quần thể quy tụ
một cách tự nhiên. Số lượng những con sống sót cho mỗi thế hệ sẽ được xem là
thích hợp nhất trong suốt quá trình tìm kiếm bởi vì khi CHC gặp khó khăn trong
việc tăng tiến trình thì ngưỡng khác nhau sẽ giảm xuống nhanh hơn khoảng cách tín
hiệu trung bình để có nhiều cá nhân hơn được đánh giá. Ngược lại, khi CHC được
xem là dễ dàng để tạo ra thế hệ con mà sống sót thì ngưỡng khác nhau sẽ giảm ở tỷ
lệ thấp hơn và số lượng các con giao phối cũng sẽ giảm.
6

11 diverge P(t)
7
Khung thuật toán gồm hai phần cơ bản là Provides và Requires.
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
Solver_Seq. Các mô hình song song được nhóm vào các lớp Solver_Lan và
Solver_Wan.
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 .
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 đó
- operator<< đưa ra các thông số của một lời giải theo os.

file dữ liệu (file này sẽ được gọi là file cấu hình), dựa vào các thông số nhận vào
này mà chương trình sẽ chọn phương pháp lựa chọn dùng trong bài toán (trong 5
phương pháp lựa chọn đã kể trên), tham số lựa chọn dấu hiệu dừng của thuật
toán, ... làm cơ sở cho cấu hình của giải thuật giải bài toán.
• Lớp quần thể (Population)
Lớp này lưu trữ các thông tin về quần thể các nhiễm sắc thể. Dưới đây là các
thủ tục chính trong lớp quần thể.
9