Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI TIỂU LUẬN
MÔN THUẬT TOÁN VÀ PHƯƠNG PHÁP
GIẢI QUYẾT VẤN ĐỀ
ĐỀ TÀI:
THUẬT TOÁN VÀ ỨNG DỤNG
THUẬT GIẢI DI TRUYỀN CHO BÀI TOÁN
NGƯỜI DU LỊCH
GVHD: PGS.TS ĐỖ VĂN NHƠN
HVTH: TRẦN KHÁNH AN
MSHV: CH1301076
LỚP: CH08-02
HVTH: CH1301076 - Trần Khánh An 1
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
TP.HCM, tháng 10 năm 2014
MỤC LỤC
HVTH: CH1301076 - Trần Khánh An 2
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
MỞ ĐẦU
Thuật toán và cách thiết kế, đánh giá thuật toán đóng vai trò quan trọng đối với mỗi
kỹ sư công nghệ thông tin. Nó cung cấp những kiến thức giúp phân tích và thiết kế thuật
toán, những kỹ năng cần thiết để giải quyết các bài toán, các vấn đề hay gặp trong lĩnh
vực công nghệ thông tin.
Để giải một bài toán, điều trước tiên là chúng ta phải có thuật toán. Một câu hỏi đặt
ra là làm thế nào để tìm ra được thuật toán cho một bài toán? Lớp các bài toán được đặt
ra từ các ngành khoa học kỹ thuật, từ các lĩnh vực hoạt động thực tiễn của con người là
hết sức phong phú và đa dạng. Các thuật toán giải các lớp bài toán khác nhau cũng rất
khác nhau. Để giải quyết được chúng ta cần có các kỹ thuật để thiết kế thuật toán. Mỗi kỹ
thuật có các tính chất riêng và chỉ thích hợp cho một số dạng bài toán nào đó. Vì chúng ta
việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một tập hữu hạn các
hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như vậy,
thuật toán là một phương pháp thể hiện lời giải của vấn đề - bài toán.
Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì
máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. Nếu
hướng dẫn giải sai hoặc không rõ ràng thì máy tính không thể giải đúng được bài toán.
Trong khoa học máy tính, thuật toán được định nghĩa là một dãy hữu hạn các bước không
mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho
được kết quả như mong muốn. .
2.2. Các đặc trưng cơ bản của thuật toán.
a. Tính hữu hạn: thuật toán bao giờ cũng phải kết thúc sau hữu hạn bước mặc dù số bước
này có thể rất lớn.
b. Tính xác định: các bước phải rõ ràng, thực hiện được ra một kết quả nào đó.
HVTH: CH1301076 - Trần Khánh An 4
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
c. Tính chính xác: đảm bảo kết quả tính toán hay các thao tác thực hiện được là chính xác.
d. Ðầu vào và đầu ra: mọi thuật toán, dù có đơn giản đến mấy cũng phải nhận dữ liệu đầu
vào, xử lý nó và cho ra kết quả cuối cùng.
e. Tính hiệu quả: tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn
như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành. Tính hiệu
quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề-
bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán.
Tiêu chuẩn được dùng rộng rãi để đánh giá là độ phức tạp của thuật toán.
f. Tính tổng quát: thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi
trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ
nào đó. Chẳng hạn giải phương trình bậc hai sau đây bằng Delta đảm bảo được tính chất
này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy nhiên, không phải thuật
toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng
thuật toán cho một dạng đặc trưng của bài toán mà thôi.
2.3. Phân tích thuật toán.
Hằng số: Hầu hết các chỉ thị của các chương trình đều được thực hiện một lần hay
nhiều nhất chỉ một vài lần. Nếu tất cả các chỉ thị của cùng một chương trình có tính chất
nầy thì chúng ta sẽ nói rằng thời gian chạy của nó là hằng số. Điều nầy hiển nhiên là hoàn
cảnh phấn đấu để đạt được trong việc thiết kế thuật toán.
logN: Khi thời gian chạy của chương trình là logarit tức là thời gian chạy chương
trình tiến chậm khi N lớn dần. Thời gian chạy thuộc loại nầy xuất hiện trong các chương
trình mà giải một bài toán lớn bằng cách chuyển nó thành một bài toán nhỏ hơn, bằng
cách cắt bỏ kích thước bớt một hằng số nào đó. Với mục đích của chúng ta, thời gian
chạy có được xem như nhỏ hơn một hằng số "lớn". Cơ số của logarit làm thay đổi hằng
số đó nhưng không nhiều: khi N là một ngàn thì logN là 3 nếu cơ số là 10, là 10 nếu cơ
số là 2; khi N là một triệu, logN được nhân gấp đôi. Bất cứ khi nào N được nhân đôi,
logN tăng lên thêm một hằng số, nhưng logN không bị nhân gấp đôi khi N tăng tới N
2
.
N: Khi thời gian chạy của một chương trình là tuyến tính, nói chung đây trường hợp
mà một số lượng nhỏ các xử lý được làm cho mỗi phần tử dữ liệu nhập. Khi N là một
triệu thì thời gian chạy cũng cỡ như vậy. Khi N được nhân gấp đôi thì thời gian chạy
cũng được nhân gấp đôi. Đây là tình huống tối ưu cho một thuật toán mà phải xử lý N dữ
liệu nhập (hay sản sinh ra N dữ liệu xuất).
NlogN: Đây là thời gian chạy tăng dần lên cho các thuật toán mà giải một bài toán
bằng cách tách nó thành các bài toán con nhỏ hơn, kế đến giải quyết chúng một cách độc
lập và sau đó tổ hợp các lời giải. Bởi vì thiếu một tính từ tốt hơn (có lẻ là "tuyến tính
logarit"?), chúng ta nói rằng thời gian chạy của thuật toán như thế là "NlogN". Khi N là
một triệu, NlogN có lẽ khoảng hai mươi triệu. Khi N được nhân gấp đôi, thời gian chạy
bị nhân lên nhiều hơn gấp đôi (nhưng không nhiều lắm).
N
2
: Khi thời gian chạy của một thuật toán là bậc hai, trường hợp nầy chỉ có ý nghĩa
thực tế cho các bài toán tương đối nhỏ. Thời gian bình phương thường tăng dần lên trong
các thuật toán mà xử lý tất cả các cặp phần tử dữ liệu (có thể là hai vòng lặp lồng nhau).
3.3 Diễn giải thuật toán
Sau khi thiết kế thuật toán ta tiến hành diễn giải thuật toán đó. Thông thường ta
không nên cụ thể hóa ngay toàn bộ chương trình mà nên tiến hành theo phương pháp tinh
chế từng bước từ tổng thế đến chi tiết hơn.
Thuật toán có thể diễn đạt dưới nhiều hình thức, chẳng hạn dưới dạng lưu đồ, dạng
ngôn ngữ tự nhiên, dạng mã giả hoặc một ngôn ngữ lập trình nào đó.
3.4 Chứng minh tính đúng đắn của thuật toán.
Khi một thuật toán được làm ra, ta cần phải chứng minh rằng, thuật toán khi được
thực hiện sẽ cho ta kết quả đúng với mọi dữ liệu vào hợp lệ. Điều này gọi là chứng minh
tính đúng đắn của thuật toán. Việc chứng minh tính đúng đắn của thuật toán là một công
việc không dễ dàng. Trong nhiều trường hợp, nó đòi hỏi ta phải có trình độ và khả năng
tư duy toán học tốt.
HVTH: CH1301076 - Trần Khánh An 7
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
3.5 Tính hiệu quả về phương diện lý thuyết và thực hành
Khi giải một vấn đề, chúng ta cần chọn trong số các thuật toán, một thuật toán mà
chúng ta cho là “tốt” nhất .Vậy ta cần lựa chọn thuật toán dựa trên cơ sở nào? Thông
thường ta dựa trên hai tiêu chuẩn sau đây:
• Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình
• Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy tính, và đặc biệt chạy
nhanh nhất có thể được.
Khi ta viết một chương trình chỉ để sử dụng một số ít lần, và cái giá của thời gian
viết chương trình vượt xa cái giá của chạy chương trình thì tiêu chuẩn thứ nhất là quan
trọng nhất. Nhưng có trường hợp ta cần viết các chương trình (hoặc thủ tục, hàm) để sử
dụng nhiều lần, cho nhiều người sử dụng, khi đó giá của thời gian chạy chương trình sẽ
vượt xa giá viết nó. Chẳng hạn, các thủ tục sắp xếp, tìm kiếm được sử dụng rất nhiều lần,
bởi rất nhiều người trong các bài toán khác nhau. Trong trường hợp này ta cần dựa trên
tiêu chuẩn thứ hai. Ta sẽ cài đặt thuật toán có thể sẽ rất phức tạp, miễn là chương trình
nhận được chạy nhanh hơn so với các chương trình khác.
Tiêu chuẩn hai được xem là tính hiệu quả của thuật toán. Tính hiệu quả của thuật
không phải lúc nào cũng có
Mỗi phương pháp có các tính chất riêng và chỉ thích hợp cho một số dạng vấn đề
nào đó. Cần nhấn mạnh rằng, ta không thể áp dụng máy móc một chiến lược cho một vấn
đề, mà ta phải phân tích kỹ vấn đề. Cấu trúc của vấn đề, các đặc điểm của vấn đề sẽ quyết
định chiến lược có khả năng áp dụng.
Đối với lớp các vấn đề giải được bằng thuật toán, dựa vào các đặc trưng của quá
trình thiết kế của thuật toán cho vấn đề, ta có thể chỉ ra một số các phương pháp thiết kế
thuật toán cơ bản sau đây:
• Phương pháp chia để trị (Divide-and-Conquer method): Ý tưởng là chia dữ liệu thành
từng miền đủ nhỏ, giải bài toán trên các miền đã chia rồi tổng hợp kết quả lại. Chẳng hạn
như thuật toán Quicksort.
• Phương pháp tham lam (Greedy Method): Ý tưởng là xác định trật tự xử lý để có lợi
nhất, Sắp xếp dữ liệu theo trật tự đó, rồi xử lý dữ liệu theo trật tự đã nêu. Công sức bỏ ra
là tìm ra trật tự đó. Chẳng hạn thuật toán tìm cây bao trùm nhỏ nhất (Shortest
spanning Trees).
• Phương pháp Quy hoạch động (Dynamic Programming method): Phương pháp quy
hoạch động dựa vào một nguyên lý, gọi là nguyên lý tối ưu của Bellman: “ Nếu lời giải
của bài toán là tối ưu thì lời giải của các bài toán con cũng tối ưu ”. Phương pháp này tổ
chức tìm kiếm lời giải theo kiểu từ dưới lên. Xuất phát từ các bài toán con nhỏ và đơn
giản nhất, tổ hợp các lời giải của chúng để có lời giải của bài toán con lớn hơn và cứ
như thế cuối cùng được lời giải của bài toán ban đầu. Chẳng hạn thuật toán “chiếc túi
xách” (Knapsack).
• Phương pháp nhánh cận (branch-and-bound method): Ý tưởng là trong quá trình tìm
kiếm lời giải, ta phân hoạch tập các phương án của bài toán ra thành hai hay nhiều tập
HVTH: CH1301076 - Trần Khánh An 9
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
con được biểu diễn như là các nút của cây tìm kiếm và cố găng bằng phép đánh giá cận
cho các nút, tìm cách loại bỏ các nhánh của cây mà ta biết chắc không chưa phương án
tối ưu. Chẳng hạn thuật toán giải bài toán người du lịch.
• Phương pháp vét cạn (Brute force): Đây là phương pháp đơn giản nhất, nhưng cũng
HVTH: CH1301076 - Trần Khánh An 10
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
2.3.2. Mô hình
Lời giải của bài toán thường biểu diễn bằng một vectơ gồm n thành phần x = (x
1
, ,
x
n
) phải thỏa mãn các điều kiện nào đó. Để chỉ ra lời giải x, ta phải xây dựng dần các
thành phần lời giải x
i
.
Tại mỗi bước i :
+ Đã xây dựng xong các thành phần x
1
, , x
i-1.
+ Xây dựng thành phần xi bằng cách lần lượt thử tất cả các khả năng mà xi có
thể chọn :
• Nếu một khả năng j nào đó phù hợp cho x
i
thì xác định x
i
theo khả
năng j. Thường phải có thêm thao tác ghi nhận trạng thái mới của bài toán để hổ trợ cho
bước quay lui. Nếu i = n thì ta có được một lời giải, nguợc lại thì tiến hành bước i+1 để
xác định x
i+1
.
• Nếu không có một khả năng nào chấp nhận được cho x
Ghi chú:
Tìm nghiệm bằng phương pháp quay lui có thể chuyển về tìm kiếm trên cây
không gian các trạng thái, với cây được xây dựng từng mức như sau:
- Các nút con của gốc (thuộc mức 1) là các khả năng có thể chọn cho x
1
.
HVTH: CH1301076 - Trần Khánh An 11
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
- Giả sử x
i-1
làmột nút ở mức thứ i-1, khi đó các nút con của x
i-1
là các khả
năng mà x
i
có thể chọn, một khi đã tìm được các thành phần x
1
, , x
i-1
.
Như vậy, mỗi nút x
i
của cây biểu diễn một lời giải bộ phận, đó là các nút nằm
trên đường đi từ gốc đến nút đó.
Ta có thể nói việc tìm kiếm nghiệm bằng phương pháp quay lui chính là tìm
kiếm theo chiều sâu trên cây không gian các trạng thái.
2.4. Phương pháp nhánh cận (Branch And Bound)
2.4.1. Ý tưởng:
Phương pháp quay lui, vét cạn có thể giải các bài toán tối ưu, bằng cách lựa chọn
phương án tối ưu trong tất cả các lời giải tìm được. Nhưng nhiều bài toán không gian các
i
sao cho :
Bất đẳng thức này có nghĩa là giá trị g(x
1
, , x
i
) không lớn hơn giá trị của các
phương án mở rộng từ lời giải bộ phận (x
1
,…, x
i
) .
HVTH: CH1301076 - Trần Khánh An 12
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
Sau khi tìm được hàm đánh giá cận g, ta dùng g để giảm bớt chi phí duyệt các
phương án theo phương pháp quay lui.
Giả sử x* là lời giải tốt nhất hiện có (phương án mẫu), còn f* là giá trị tốt nhất
tương ứng f* = f(x*).
Nếu g(x
1
, , x
i
) > f* thì :
Nên chắc rằng các lời giải mở rộng từ (x
1
,…, x
i
) sẽ không tốt hơn phương án
mẫu, do đó có thể bỏ đi không cần phát triển lời giải bộ phận (x
1
}
Thực chất của phương pháp nhánh cận là tìm kiếm theo chiều sâu trên cây liệt kê lời
giải như phương pháp quay lui, chỉ khác có một điều là khi tìm được x
i
mà đánh giá cận
g(x
1
,…,x
i
)>f* thì ta cắt bỏ các nhánh con từ x
i
đi xuống, mà quay lên ngay cha của nó là
x
i
-1.
Vấn đề là xác định hàm đánh giá cận như thế nào ?
HVTH: CH1301076 - Trần Khánh An 13
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
3. Phương pháp Heuristic
Trong nhiều bài toán dùng phương pháp thử - sai sẽ dẫn đến số lượng thử quá lớn
không chấp sẽ dẫn đến số lượng thử quá lớn không chấp nhận được.
Heuristic chính là ước lượng về khả năng dẫn đến lời giải của một trạng thái:
phương pháp vét cạn nhưng có thêm tri thức đi kèm, tối ưu cục bộ, nguyên lý hướng
đích, nguyên lý sắp thứ tự,
Mở rộng khái niệm thuật toán : thuật giải
Trong quá trình nghiên cứu giải quyết các vấn đề - bài toán, người ta đã đưa ra những
nhận xét như sau :
Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán
và cũng không biết là có tồn tại thuật toán hay không.
Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời
dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.
• Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài
toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng
giai đoạn) trong quá trình tìm kiếm lời giải.
• Nguyên lý thứ tự : Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không
gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt.
• Hàm Heuristic: Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các
hàm Heuristic. Ðó là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái hiện
tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách hành động
tương đối hợp lý trong từng bước của thuật giải.
• Meta heuristic: là loại heuristic tổng quát có thể áp dụng cho nhiều lớp bài toán. Meta
heuristic là một lãnh vực nghiên cứu phát triển mạnh mẽ, với sự ra đời của nhiều meta
heuristic như: giải thuật di truyền (genetic algorithm), giải thuật mô phỏng luyện kim
(simulated annealing), giải thuật đàn kiến ACO, tìm kiếm tabu (Tabu search)
CHƯƠNG 3: GIẢI THUẬT DI TRUYỀN (GA)
1. Giới thiệu về giải thuật di truyền
Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp
thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật di
truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến hóa như
di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo.
Giải thuật di truyền thường được ứng dụng nhằm sử dụng ngôn ngữ máy tính để mô
phỏng quá trình tiến hoá của một tập hợp những đại diện trừu tượng (gọi là những nhiễm
sắc thể) của các giải pháp có thể (gọi là những cá thể) cho bài toán tối ưu hóa vấn đề. Tập
hợp này sẽ tiến triển theo hướng chọn lọc những giải pháp tốt hơn.
Thông thường, những giải pháp được thể hiện dưới dạng nhị phân với những chuỗi 0 và
1, nhưng lại mang nhiều thông tin mã hóa khác nhau. Quá trình tiến hóa xảy ra từ một tập
hợp những cá thể hoàn toàn ngẫu nhiên ở tất cả các thế hệ. Trong từng thế hệ, tính thích
nghi của tập hợp này được ước lượng, nhiều cá thể được chọn lọc định hướng từ tập hợp
hiện thời (dựa vào thể trạng), được sửa đổi (bằng đột biến hoặc tổ hợp lại) để hình thành
HVTH: CH1301076 - Trần Khánh An 15
1975 : Giải thuật gen do John Holland phát minh và được phát triển bởi ông cùng
với các đồng nghiệp và những sinh viên. Cuốn sách "Adaption in Natural and
Artificial Systems" (Sự thích nghi trong các hệ tự nhiên và nhân tạo) xuất bản năm
1975 đã tổng hợp các kết quả của quá trình nghiên cứu và phát triển đó.
1992 : John Koza đã dùng GA để xây dựng các chương trình giải quyết một số
bài toán và gọi phương pháp này là " lập trình gen".
Ngày nay giải thuật di truyền càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu
hoá, một lĩnh vực có nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng
thường khó và chưa có giải thuật hiệu quả để giải .
HVTH: CH1301076 - Trần Khánh An 16
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
2. Các khái niệm cơ bản
Giải thuật di truyền dựa vào quá trình tiến hoá trong tự nhiên nên các khái niệm và
thuật ngữ của nó đều có liên quan đến các thuật ngữ của di truyền học.
Cá thể, nhiễm sắc thể
Trong giải thuật di truyền, một cá thể biểu diễn một giải pháp của bài toán. Không
giống với trong tự nhiên, một cá thể có nhiều nhiễm sắc thể (NST), ở đây ta quan niệm
một cá thể có một nhiễm sắc thể. Do đó khái niệm cá thể và nhiễm sắc thể trong giải
thuật di truyền coi như là tương đương.
Một NST được tạo thành từ nhiều gen, mỗi gen có thể có các giá trị khác nhau để
quy định một tính trạng nào đó. Trong GA, một gen được coi như một phần tử trong
chuỗi NST.
Quần thể
Quần thể là một tập hợp các cá thể có cùng một số đặc điểm nào đấy. Trong giải
thuật di truyền ta quan niệm quần thể là một tập các lời giải của một bài toán.
Chọn lựa
Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay đổi các cá thể
trong quần thể. Những cá thể tốt, thích nghi được với điều kiện sống thì có khả năng đấu
tranh lớn hơn, do đó có thể tồn tại và sinh sản. Các cá thể không thích nghi được với điều
kiện sống thì dần mất đi. Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh sinh
chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn)
d.[Lai ghép] Với một xác suất lai ghép được chọn, lai ghép hai cá thể bố mẹ
để tạo ra một cá thể mới.
e.[Đột biến] Với một xác suất đột biến được chọn, biến đổi cá thể mới
5. [Chọn kết quả] Nếu điều kiện dừng được thỏa mãn thì thuật toán kết thúc và trả
về lời giải tốt nhất trong quần thể hiện tại
4. Các tham số của GA
Kích thước quần thể:
Kích thước quần thể cho biết có bao nhiêu cá thể trong một quần thể (trong một thế
hệ). Qua các nghiên cứu cũng như các thử nghiệm đã cho thấy kích thước quần thể không
nên quá bé cũng như không quá lớn. Nếu có quá ít cá thể thì ít có khả năng thực hiện lai
giống và chỉ một phần nhỏ không gian tìm kiếm được dùng. Như vậy sẽ dễ xảy ra trường
hợp bỏ qua các lời giải tốt. Nhưng quá nhiều cá thể cũng không tốt vì GA sẽ chạy chậm
đi, ảnh hưởng đến hiệu quả của giải thuật. Các nghiên cứu cũng đã chỉ ra không có lợi
khi tăng kích thước quần thể lên quá một giới hạn cho phép.
Xác suất lai ghép
Xác suất lai ghép cho biết việc lai ghép tạo ra thế hệ mới được thực hiện thường
xuyên như thế nào. Xác suất lai ghép là p
c
, khi đó khả năng để một cá thể được lai ghép
là p
c
. Nếu không thực hiện lai ghép, con sinh ra sẽ giống hoàn toàn bố mẹ. Nếu được lai
ghép, con sinh ra sẽ có một phần giống bố và một phần giống mẹ.
Xác suất đột biến
Xác suất đột biến cho biết các gen của NST thay đổi thường xuyên như thế nào.
Xác suất đột biến là p
m
, khi đó khả năng để mỗi gen của một NST bất kỳ bị đột biến là
p
xảy ra trường hợp các toán tử lai ghép và đột biến tạo ra các cá thể không nằm trong
không gian tìm kiếm và đòi hỏi phải có những phương pháp sửa chữa để làm cá thể tạo ra
nằm trong không gian tìm kiếm. Do đó, với nhiều bài toán thì biểu diễn nhị phân là
không hữu hiệu, điển hình là bài toán TSP.
Mã hoá hoán vị
Mã hoá hoán vị có thể được sử dụng trong các bài toán liên quan đến thứ tự như
bài toán du lịch hay bài toán lập lịch.
Trong mã hoá hoán vị, mỗi nhiễm sắc thể là một chuỗi các số biểu diễn một trình tự.
Ví dụ :
Nhiễm sắc thể 1: 1 5 4 3 2 6 7 9 8
Nhiễm sắc thể 2: 9 1 7 3 8 5 6 4 2
Mã hoá hoán vị phù hợp cho các bài toán liên quan đến thứ tự. Đối với các bài
toán này, việc thao tác trên các nhiễm sắc thể chính là hoán vị các số trong chuỗi đó làm
thay đổi trình tự của nó.
Ví dụ: Trong bài toán người du lịch, để biểu diễn một cách đi của người du lịch
thì dùng một nhiễm sắc thể mà trình tự các số trong chuỗi cho biết thứ tự các thành phố
mà người du lịch đi qua.
Mã hoá theo giá trị
Mã hoá trực tiếp theo giá trị có thể được dùng trong các bài toán sử dụng giá trị
phức tạp như trong số thực. Trong đó, mỗi nhiễm sắc thể là một chuỗi các giá trị. Các giá
HVTH: CH1301076 - Trần Khánh An 20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
trị có thể là bất cứ cái gì liên quan đến bài toán, từ số nguyên, số thực, kí tự cho đến các
đối tượng phức tạp hơn.
Ví dụ:
Nhiễm sắc thể 1: 1.23 5.32 0.34 2.98 3.54
Nhiễm sắc thể 2: (back), (back), (right), (forward), (left)
Mã hoá theo giá trị thường dùng cho các bài toán đặc biệt. Trong cách mã hoá này
ta thường phải phát triển các toán tử đột biến và lai ghép cho phù hợp với từng bài toán.
6. Khởi tạo quần thể ban đầu
_
1
)(
Tính xác suất chọn p
i
cho mỗi nhiễm sắc thể v
i
: p
i
= f(v
i
)/F
Tính vị trí xác suất q
i
của mỗi nhiễm sắc thể :
∑
=
=
i
j
ji
Pq
1
Cơ chế lựa chọn theo bánh xe Roulet được thực hiện bằng cách quay bánh xe
Roulet N lần. Mỗi lần chọn một nhiễm sắc thể từ quần thể hiện hành vào quần thể mới
bằng cách sau :
Phát sinh ngẫu nhiên một số r trong khoảng [0,1].
HVTH: CH1301076 - Trần Khánh An 21
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
Lựa chọn tranh đấu
Cơ chế lựa chọn :
Lấy một số NST trong quần thể, NST nào có độ thích nghi cao nhất được chọn.
Lặp lại thao tác trên N lần.
7. Các toán tử di truyền
Các toán tử di truyền là các hàm biến đổi NST từ thế hệ P(t) để tạo ra các NST của
thế hệ P(t+1). Các toán tử di truyền của GA là toán tử lai ghép và đột biến. Việc xây
dựng hai toán tử này đóng vai trò rất quan trọng trong hiệu quả của giải thuật. Nó phải
được đảm bảo rằng kết quả sinh ra của 2 toán tử là hợp lệ theo nghĩa phải nằm trong
không gian tìm kiếm của giải thuật, lấy ví dụ với bài toán TSP thì việc mã hóa nhị phân
và toán tử đột biến và lai ghép sẽ tạo ra các cá thể không phù hợp vì không tạo thành 1
đường đi hợp lệ, do đó mã hóa nhị phân ít được dùng cho bài toán TSP.
Toán tử lai ghép
HVTH: CH1301076 - Trần Khánh An 22
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
Lai ghép đơn điểm cắt :
Một điểm cắt được chọn tại một vị trí thứ k trên NST.
Từ đầu NST đến vị trí k, NST con sao chép từ cha, phần còn lại sao chép từ
mẹ.
Lai ghép hai điểm cắt :
Hai điểm cắt được chọn .
Từ đầu cho đến điểm cắt thứ nhất được sao chép từ cha, từ điểm cắt thứ
nhất đến điểm cắt thứ hai sao chép từ mẹ và phần còn lại sao chép từ cha.
Lai ghép đồng nhất :
Có một mặt nạ sao chép là một chuỗi nhị phân có chiếu dài bằng chiều dài
NST.
Xây dựng NST mới: Duyệt qua mặt nạ, bit có giá trị một thì sao chép gen
tại vị trí đó từ NST cha sang con, bit có giá trị 0 thì sao chép từ mẹ.
Mặt nạ được phát sinh ngẫu nhiên đối với từng cặp cha mẹ.
Lai ghép số học: NST con được tạo thành bằng cách thực hiện một phép toán
Bài toán người du lịch (Travelling Salesman problem (TSP)) là một bài toán nổi
tiếng trong lĩnh vực tối ưu tổ hợp được nghiên cứu trong lý thuyết khoa học máy tính.
Nội dung của nó khá đơn giản , nó được phát biểu như sau : Cho một danh sách các thành
phố và khoảng cách giữa chúng , nhiệm vụ là phải tìm đường đi ngắn nhất có thể mà chỉ
thăm mỗi thành phố đúng 1 lần.
Bài toán được lần đầu tiên đưa ra như một vấn đề toán học vào năm 1930 và là
một trong số những bài toán được nghiên cứu chuyên sâu trong lĩnh vực tổ hợp thời đó.
Nó được sử dụng như một sự đánh giá cho nhiều phương thức tối ưu khác nhau. Thậm
chí bài toán là thuộc lớp NP khó , một lượng rất lớn các heuristic và phương thức tìm
kiếm cụ thể đã được biết đến vì vậy một vài trường hợp của bài toán với khoảng chục
nghìn thành phố đã được giải quyết.
TSP có một vài ứng dụng thậm chí trong dạng thức nguyên thuỷ của nó như lập kế hoạch
, logistic , và sản xuất các microchip. Thay đổi đi chút ít nó xuất hiện như một bài toán
con trong rất nhiều lĩnh vực như việc phân tích gen trong sinh học. Trong những ứng
dụng này, khái niệm thành phố có thể thay đổi thành khách hàng, các điểm hàn trên bảng
mạch, các mảnh DNA trong gen, và khái niệm khoảng cách có thể biểu diễn bởi thời gian
du lịch hay giá thành , hay giống như sự so sánh giữa các mảnh DNA với nhau. Trong
nhiều ứng dụng, các hạn chế truyền thống như giới hạn tài nguyên hay giới hạn thời gian
thậm chí còn làm cho bài toán trở nên khó hơn
1.2. Phát biểu bài toán
Một du khách muốn thăm mọi thành phố anh quan tâm, mỗi thành phố thăm qua
đúng một lần; rồi trở về điểm khởi hành. Biết trước chi phí di chuyển giữa hai thành phố
bất kỳ. Hãy xây dựng một lộ trình thỏa các điều kiện trên với tổng chi phí là nhỏ nhất.
HVTH: CH1301076 - Trần Khánh An 24
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
1.3. Mô hình hóa vấn đề
• Xác định DIK:
Vấn đề được mô hình hóa bằng đồ thị có trọng số dương G={V,E}. Trong đó:
V: là tập đỉnh
E: là tập cạnh
phương án của thuật toán quay lui.
Thiết kế
Input: C = (C
ij
)
Output: - x* = (x
1
, ,x
n
) // Hành trình tối ưu
HVTH: CH1301076 - Trần Khánh An 25
Copyright: Tài liệu đại học ©