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
Chương I: Tổng quan về phương pháp CHC.............................................3
I.Tìm hiểu chung về thuật toán di truyền..............................................3
II.
Tổng quan về phương pháp CHC................................................4
1. Khái niệm.........................................................................................4
2. Tư tưởng của thuật toán CHC.......................................................4
3. Sự Chọn lọc Elitist.........................................................................6
4. Tránh sự giao phối gần...................................................................7
Chương II: Xây dựng khung thuật toán CHC...........................................8
I.
Thiết kế khung thuật toán CHC.....................................9
1. Các lớp đòi hỏi (Requires)............................................................10
Lớp bài toán (Problem)..............................................................10
Lớp lời giải (Solution)................................................................10
Lớp toán tử người sử dụng (Uer_Operator)............................10
Lớp kiểm tra điều kiện dừng (StopCondition)..........................10
2. Các lớp cung cấp (Provided)........................................................11
Lớp thiết lập tham số đầu vào (SetUpParams)..........................11
Lớp quần thể (Population).........................................................11
Lớp lựa chọn (Selection)............................................................12
Lớp chỉ định toán tử sử dụng (Intra_Operator):......................13
Lớp định nghĩa giao diện toán tử (Inter_Operator).................13
2
Lớp lai ghép (Crossover)............................................................13
Lớp thực thi giải thuật (Solver)...............................................14
II.
Khung thuật toán tuần tự...........................................................14
1. Hàm void Solver_Seq::DoStep().................................................14
III.
Khung thuật toán song song.......................................................16
Chương III. Sử dụng khung thuật toán giải quyết bài toán MAXSAT..17
I. Đọc file cấu hình.................................................................................17
II. Sử dụng khung thuật toán giải quyết bai toán MAXSAT.............18
III.
Kết quả thực nghiệm...................................................................24
1. Kết quả tuần tự............................................................................24
2. Kết quả song song........................................................................24
3
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
Giải thuật di truyền 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 hoá và đấu tranh sinhh tồn của sinh vật trong tự nhiên
theo thuyết tiến hoá muôn loài của Darwin.
Mục tiêu của giải thuật di truyền: giải thuật di truyền không đưa ra lời
giải tối ưu mà là đưa ra lời giải gần đúng (tương đối tối ưu).
Bản chất của thuật toán di truyền là bài toán tìm kiếm dựa theo qui luật
của quá trình tiến hoá tự nhiên. Thuật toán di truyền kết hợp sự sống sót của
cấu trúc khoẻ nhất trong số các cấu trúc biểu diễn các nhiễm sắc thể (NST)
với 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 sử dụng các biểu diễn nhị phân kết hợp với sơ đồ
để mô hình hoá sự chọn lọc, lai ghép và đột biến.
Ứng dụng của thuật toán di truyền:
+ Trong tin học: xây dựng chương trình tin học đặc biệt như trí tuệ
nhân tạo để hướng dẫn người sử dụng trong lĩnh vực giáo dục, quản trị.
+ Trong các công việc khác: Ứng dụng giải bài toán sắp xếp thời khoá
biểu, điều khiển robot, bài toán vận tải, bài toán đồ thị…
II. Tổng quan về phương pháp CHC
1. Khái niệm
4
CHC là giải thuật di truyền phi truyền thống kết hợp chiến lược chọn
lọc (dựa trên những cá thể đơn lẻ tốt nhất) để đưa ra con lai tốt nhất khác
với cả cha và mẹ.
2. Tư tưởng của thuật toán CHC
CHC là từ viết tắt của cross – generational selection, Heterogeneous
recombination, and Cat – aclysmic mutation. Giải thuật CHC được phát triển
bởi Eshelman (1991) được trình bày như hình vẽ:
5
CHC lựa chọn một trang của quần thể có kích cỡ µ (µ =50) nhưng thay
vì chọn những cha mẹ tốt để tái kết hợp giống cách làm của giải thuật gi
truyền, cha mẹ được chọn một cách ngẫu nhiên một cặp duy nhất và điều
kiện để sinh ra con chung. Giải thuật sau đó sẽ chọn tập cá thể tốt nhất từ
cha mẹ được kết hợp và quầ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
6
đượ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(t1) 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,
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 là sự chọn lọc elitist bởi vì nó đảm bảo rằng các cá thể M tốt
nhất sẽ luôn sống sót.
Một vài sự chọn lọc sinh tồn thiên về tính thích hợp sử dụng của giải
thuật di truyền khác - Whitley’s GENITOR (1989), Syswerda’s Steady State
GA (SSSGA(1989), và Ackley’s Iterated Generic Search(IGS) (1987). CHC
khác với tất cả ba loại giải thuật này trong đó việc cạnh tranh sinh tồn là thế
hệ lai-thế hệ con chỉ thay thế một thành viên của quần thể cha mẹ nếu nó tốt
hơn. Hơn nữa, không giống như ba giải thuât này, CHC vận hành trong các
chu kỳ thế hệ với rất nhiều bạn đời chứ không phải chỉ một bạn đời cho mỗi
chu kỳ. Sự tin cậy duy nhất đối với sự chọn lọc sinh tồn cho sự thiên lệch
của nó vì lợi ích của những cá nhân thực thi tốt hơn hơn và cũng phân biệt
nó với GENITOR và SSSGA nhưng không phải là IGS. Cuối cùng, phương
pháp được dựa trên sự xếp hạng tất yếu của việc thực hiện sự chọn lọc phân
biệt nó với SSGA Và IGS nhưng không phải là GENITOR.
4. Tránh sự giao phối gần
Sự tăng trưởng theo số mũ của các trường hợp lược đồ tốt thì có giá trị ít
hơn nếu nó dẫn đến sự quy tụ còn non. Một trong những hậu quả của phép
lai một nửa bit khác nhau giữa các thế hệ cha mẹ đó là sự nguy có của sự hội
tụ còn non sẽ giảm đi. Thậm chí ở mỗi thế hệ thì thế hệ con cháu gần đây
7
nhất giao phối với một trong những tổ tiên đầu tiên (con giống nhau trong
mỗi lần). Nó sẽ mang các thế hệ log 2h để quy tụ (trong vòng 1 bit) đến tổ
tiên đầu tiên ở đó h là khoảng cách tín hiệu giữa các thế hệ cha mẹ đầu tiên.
Mặc khác, trong trường hợp của phép lai hai điểm hai thế hệ con sẽ khác so
với thế hệ cha mẹ gần nhất của nó (được đo bởi khoảng cách tín hiệu) bằng
số lượng dao động từ 1 bit cho đến không quá một nửa chiều dài của chuỗi
L. Chính vì vậy, thời gian dài nhất mà nó có thể tạo ra sự quy tụ trong vòng
1 bit của tổ tiên của nó là các thế hệ log 2h và thời gian ngắn nhất là một thế
hệ. Tất nhiên, thế hệ con không được giao phối lại với một trong những tổ
tiên xa của 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 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
8
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.
Chương II: Xây dựng khung thuật toán CHC
Việc xây dựng khung thuật toán có ý nghĩa rất quan trọng trong quá
trình lập trinh. Nó cho phép nhiều người dùng khai thác hiệu quả nhất những
giải thuật cũng như cơ sở dữ liệu nhờ những khung thuật toán có sẵn. Một số
tiểu ứng dụng của khung thuật toán:
Hỗ trợ thiết kế tối đa và khả năng tái sử dụng code:
Khung phải cung cấp cho người dùng toàn bộ kiến trúc của phương
pháp giải quyết bài toán của họ. Hơn nữa các lập trình viên có thể tái sự
dụng các đoạn code đã có. Do đó người dùng chỉ cần phát triển một đoạn
code nhất định cho vấn đề đó.
Tiện ích và khả năng mở rộng:
9
Khung phải cho phép người dùng đi qua một số lượng lớn các giải thuật
đã được giả quyết, các vấn đề, các mô hình song song đã được đưa ra. Nó có
khả năng cho phép người dùng dễ dàng thêm hoặc thay đổi các đặc tính/ giải
thuật mà ko cần liên quan đến các thành phần khác. Giúp cho người sau thử
nghiệm bai toán trên môi trường song song.
Tính linh động:
Khung hỗ trợ nhiều kiến trúc phần cứng và phần mềm khác nhau nên
đáp ứng được một số lượng lớn người dùng.
I.
Thiết kế khung thuật toán CHC
Cấu trúc chung của thuật toán CHC:
1 t = 0
2 initialize P(t)
3 evaluate structures in P(t)
4 while not end do
5
t = t + 1
6
select: C(t) = P(t-1)
7
recombine: C'(t) = 'incest
prevention' + HUX(C'(t))
8
evaluate structures in C'(t)
9
replace P(t) from C''(t) and P(t-1)
10
if convergence(P(t))
11
diverge P(t)
10
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)
11
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.
- operator>> nhận vào các thông số của một lời giải theo luồng is.
- char *to_String(): Chuyển nhiễm sắc thể biểu diễn lời giải thành một
xâu ký tự
- to_Solution(char *_cadena_): Hàm tạo ra một đối tượng lời giải từ
một xâu ký tự.
- 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
- fitness (): Hàm tính độ thích nghi làm cơ sở đánh giá lời giải.
Lớp toán tử người sử dụng (Uer_Operator)
Thừa kế từ lớp Intra_Operator.
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...
2.
Các lớp cung cấp (Provided)
Bao gồm các thủ tục chung cho các bài toán giải bằng giải thuật CHC.
Ta có thể hình dung các lớp loại provide giống như một thư viện, và khi giải
các bài toán chỉ việc gọi nó ra.
Lớp thiết lập tham số đầu vào (SetUpParams)
12
Lớp này chứa các thủ tục để thiết đặt các tham số cho bài toán như đã
nêu trên và cho các toán tử của giải thuật từ 1 file đầu vào:
oindependent_runs: số lần thực hiện quá trình tiến hóa trong một lần
thực hiện chương trình
opopulation_size: kích thước quần thể
onb_evolution_steps: số bước tiến hóa
oselect_parents: phương thức lựa chọn cha
oselect_offsprings: phương thức lựa chọn con
ocombine: có kết hợp quần thể cũ hay chỉ lựa chọn từ quần thể mới.
oHàm istream& operator>> (istream& is, SetUpParams& setup) có
nhiệm vụ thiết đặt các tham số cho bài toán. Cụ thể, nó nhận vào các thông
số cấu hình từ một 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ể.
Trong đó:
oEvaluate(Solution *sol, struct individual &_f): tạo ra cá thể _f (độ
thích nghi, vị trí ) tương ứng với nhiễm sắc thể sol.
oinitialize(): Sinh ra một tập các cá thể mới trong quần thể
oevolution(): Tiến hóa quần thể bằng các phương pháp: lụa chọn, lai
ghép, đột biến.
13
oevaluate_parents(): Tạo ra một mảng chứa đựng độ thích nghi của tất
cả các cá thể và vị trí của nó trong quần thể. Cùng với việc đánh giá độ thích
nghi của cha tốt nhất, cha tồi nhất và giá trị trung bình
oevaluate_offsprings(): Tạo ra một mảng chứa đựng độ thích nghi của
tất cả các cá thể và các con cùng vị trí của nó trong quần thể.
oselect_parents(): Lựa chọn cha để tiến hành lai ghép, sử dụng một
trong 5 phương pháp để tiến hành lựa chọn.
oselect_offsprings(): Lựa chọn các cá thể cho quần thể mới. Có hai
phương pháp hoặc là chỉ lựa chọn từ quần thể mới (combine = 0) hoặc là lựa
chọn từ quần thể mới và quần thể cũ (combine = 1)
Hàm quan trọng nhất trong lớp này là hàm evolution(), nó để thực hiện
công việc tiến hoá quần thể hay sinh quần thể mới qua các phép chọn lọc, lai
ghep, đột biến như trên đã tìm hiểu.
Lớp lựa chọn (Selection)
Để thực hiện việc chọn lọc các cá thể có độ thích nghi cao để cho vào
bể lai ghép để thực hiện các phép biến đổi cho ra một quần thể mới có độ
thích nghi cao hơn.
Dưới đây là các thủ tục chính trong lớp lựa chọn.
Trong đó:
oprepare: thực hiện việc chuẩn bị các điều kiện cho việc tiến hành
chuẩn bị, ở mỗi phương pháp chọn lựa thì yêu cầu chuẩn bị này sẽ khác
nhau.
oselect_onechọn một cá thể trong quần thể để cho vào bể ghép đôi, việc
chọn lựa này là ngẫu nhiên theo xác xuất chọn lựa được tính từ độ thích
nghi, cách tính này tuỳ thuộc theo từng phương pháp chọn lựa.
14
Có 5 lớp kế thừa từ lớp Selection tương ứng với 5 phương pháp lựa
chọn phổ biến…
Trong đó:
oSelection_Tournament: lựa chọn cạnh tranh, như đã giới thiệu trong
phần lý thuyết ở chương I.
oSelection_Roulette_Wheel: Lựa chọn bánh xe số.
oSelection_Rank: Lựa chọn theo danh sách xếp loại.
oSelection_Best: Lựa chọn tốt nhất.
oSelection_Worst: Lựa chọn tồi nhất .
Lớp chỉ định toán tử sử dụng
(Intra_Operator):
Để xác định phép biến đổi quần thể là lai ghép hay đột biến theo xác
xác xuất lai ghép và đột biến đã cho.
Hàm này gồm có cách thuộc tính và phương thức chính:
- int _number_operator: số hiệu của toán tử áp dụng, được quy ước là
bằng 0 nếu toán tử là Crossover, bằng 1 nếu toán tử là Mutation.
- probability: xác xuất (lai ghép hay đột biến)
- Intra_Operator *create(unsigned int _number_op): để tạo ra một đối
tượng thuộc lớp Crossover hoặc Mutation tuỳ theo tham số truyền vào
(unsigned int _number_op) là 0 hay 1..
- operator<< (ostream& os, const Intra_Operator& intra): Hàm đưa ra
các thông số về đối tượng được tạo ra ở hàm creat
Lớp định nghĩa giao diện toán tử (Inter_Operator)
Cung cấp những lớp định nghĩa giao diện chung cho nhiều toán tử mà
được tạo nên từ hai phương thức chính: Setup, đọc cấu hình của toán tử và
execute, ứng dụng toán tử.
15
Lớp lai ghép (Crossover)
Để thực hiện việc lai ghép các lời giải với nhau tạo ra các lời giải mới.
Dưới đây là các thủ tục chính trong lớp lai ghép.
Trong đó:
- cross(Solution &sol1,Solution &sol2): hàm lai hai lời giải với nhau
tạo ra các lời giải mới.
- execute(Rarray& sols): lai ghép 2 cá thể liên tiếp nhau
trong quần thể sols[] (một mảng các cá thể Solution).
Trong hai hàm này thì hàm Excute là chung cho mọi bài toán, và ta chỉ
cần khai triển lại hàm Cross khi làm việc với các bài toán cụ thể.
Ngoài ra còn các hàm
- setup(char line[MAX_BUFFER]): nhận vào xác xuất lai ghép
Probability.
- RefreshState(const StateCenter& _sc): thiết lập lại các tham số phục
vụ cho việc lai ghép.
- UpdateFromState(const StateCenter& _sc): cập nhật các tham số
chung của bài toán sau một quá trình lai ghép: quần thể lời giải, các thông
tin trong quần thể, ...
Lớp Statistics
Lớp này thống kê những vết ở trạng thái hiện thời. Đưa ra thứ tự vết,
quá trình tiến hoá, chi phí tốt nhất, chi phí tổng cộng tốt nhất, giá trị trung
bình,…
Lớp OperatorPool cung cấp một giao diện chung để sử dụng bất
cứ toán tử.Toán tử này quan tâm đến những thay đổi của các giải pháp trong
quần thể
Lớp thực thi giải thuật (Solver)
16
Đưa ra và duy trì các thông tin có liên quan tới trạng thái tìm kiếm
trong suốt quá trình thực hiện. có thể nói đây là lớp tổng hợp, được gọi trực
tiếp từ chương trình chính, nó sử dụng thành quả xây dựng được của các lớp
trình bày phía trên và là lớp trung gian giữa các lớp, thủ tục ta xây dựng
phục vụ cho quá trình tiến hoá với chương trình thực thi với các bài toán cụ
thể. Dưới đây là các hàm chính trong lớp thực thi giải thuật
Trong đó:
oStartUp(): Khởi tạo quần thể, khởi tạo giá trị cho các biến trạng thái
tiến hoá, các tham số cho quần thể trước khi bắt đầu một quá trình tiến hoá
mới. Cập nhật các biến kiểm soát quá trình chạy của cả bài toán.
oDoStep(): Thực hiện các công việc trong một bước tiến hoá của quần
thể, cập nhật lại các tham số của quần thể sau một bước tiến hoá
oRun (): là thủ tục thực hiện toàn bộ quá trình tìm kiếm của bài toán
dựa vào các thông tin về bài toán, về các tham số, các điều kiện đầu vào
được đọc vào từ 2 file là file cấu hình và file bài toán.
II. Khung thuật toán tuần tự
Sử dụng lớp bài toán tuần tự của phương pháp CHC.
1. Hàm void Solver_Seq::DoStep()
void Solver_Seq::DoStep()
{
// tăng bước lặp hiện thời lên 1.
current_iteration(current_iteration()+1);
// gọi đến hàm tiến hoá của quần thể hiện thời
17
current_population.evolution();
current_evaluations(current_population.evaluations());
// Lấy những giá trị quan trọng trong quần thể hiện
thời
best_cost=current_population.best_cost(); // chi phí
tốt nhất
best_solution=current_population.best_solution(); //
giải pháp tốt nhất
worst_cost=current_population.worst_cost(); // chi
phí tồi nhất
average_cost=current_population.average_cost(); //chi
phí trung bình
standard_deviation=current_population.standard_deviation();
//
time_spent_in_trial = _used_time(start_trial);
total_time_spent
= start_global +
time_spent_in_trial; // tổng số thời gian sử dụng
// refresh state with these values
18
RefreshState();
RefreshCfgState();
if( (current_iteration() %
params.refresh_global_state()) == 0)
UpdateFromCfgState();
_stat.update(*this);
_userstat.update(*this);
if (display_state())
show_state();
}
Chương trình:
Solver_Seq solver();
Solver.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;
}
III. Khung thuật toán song song
19
- 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:
Ư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.
- 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.
+ 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
20
- Xem thêm -