<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

<b>BỘ GIÁO DỤC VÀ ĐÀO TẠO</b>

<b>TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP.HCM</b>

<b>BÁO CÁO GIỮA KỲ</b>

<b>ĐỀ TÀI: THUẬT TOÁN LOCAL BEAM SEARCH</b>

<b> GVHD: Lê Minh Tân</b>

1. Đặng Thanh Bình 21110380 2. Đào Tấn Kiệt

3. Lê bá Điền

4. Hồng Đình Minh Thơng 5. Nguyễn Thiện Luân 6. Nguyễn Đức Nhân 7. Hồ Phương Đơng

<b>Tp. Hồ Chí Minh, tháng 3 năm 2023</b>

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

2.2 Mô tả các phương pháp để tạo ra các bộ khởi tạo (initial state sets) cho

3.2 Các ví dụ về các bài tốn có thể giải quyết bằng thuật toán 10 3.3 Kết quả đạt được khi áp dụng thuật toán trên các bài toán thực tế 10

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

MỞ ĐẦU

1. Lí do chọn đề tài

Thuật toán Local beam search là một trong những thuật tốn quan trọng trong lĩnh vực trí tuệ nhân tạo. Nó được sử dụng để giải quyết các bài toán tối ưu trong nhiều lĩnh vực khác nhau như kế hoạch hóa sản xuất, quản lý vận tải, lập lịch, tối ưu hóa mạng và nhiều bài tốn khác.

Ngồi ra, Local beam search cũng được sử dụng trong các bài tốn tìm kiếm lời giải của các bài tốn NP (nondeterministic polynomial time) -khó như bài tốn TSP (Traveling Salesman Problem), bài toán cây Steiner, bài toán phân bổ tài ngun và nhiều bài tốn khác.

Bên cạnh đó, Local beam search cũng là một trong những phương pháp được sử dụng trong lĩnh vực học máy để tìm kiếm các bộ tham số tối ưu cho các mơ hình học máy. Nó được sử dụng để tìm kiếm các bộ tham số tối ưu cho các mơ hình học sâu như mạng neural, mơ hình học tăng cường và nhiều mơ hình khác.

Thuật tốn Local beam search là một thuật tốn tìm kiếm rất hữu ích trong việc giải quyết các bài tốn tối ưu. Nó cho phép tìm kiếm các giải pháp tốt nhất trong một tập hợp các giải pháp có thể. Vì vậy, việc tìm hiểu và nghiên cứu thuật toán này là rất quan trọng và có ý nghĩa trong việc nghiên cứu và giải quyết các bài tốn tối ưu. Ngồi ra, Local beam search cũng là một trong những thuật toán được sử dụng phổ biến trong lĩnh vực trí tuệ nhân tạo và học máy. Vì vậy, việc nắm vững kiến thức về thuật toán này cũng là một bước quan trọng để có thể phát triển các ứng dụng trí tuệ nhân tạo và học máy trong tương lai.

2. Giới thiệu về thuật toán Local beam search

Thuật toán Local beam search là một thuật tốn tìm kiếm cục bộ được sử dụng để giải quyết các bài tốn tối ưu hóa. Nó thuộc nhóm các thuật tốn tìm kiếm địa phương và thường được sử dụng khi không thể áp dụng các phương pháp tìm kiếm tồn cục, như thuật tốn tìm kiếm theo chiều sâu hay tìm kiếm theo chiều rộng.

Thuật toán Local beam search thường được sử dụng trong các bài tốn tối ưu hóa đa dạng như tối ưu hóa màu sắc đồ thị, tối ưu hóa lịch trình đi lại hay tối ưu hóa các hàm số phi tuyến. Tuy nhiên, cũng có những hạn chế của thuật tốn này, ví dụ như khó khăn trong việc tránh các điểm cực đại địa phương.

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

NỘI DUNG

Chương 1: Cơ sở lí thuyết 1.1 Lịch sử ra đời

Thuật toán Local beam search được giới thiệu đầu tiên vào năm 1972 bởi nhà khoa học thuộc trường Đại học Stanford, Nils Nilsson. Thuật toán này được sử dụng để giải quyết bài tốn tối ưu hóa trên mạng lưới điện.

Sau đó, trong những năm 1980, Local beam search trở thành một trong những thuật tốn tìm kiếm địa phương phổ biến nhất, được áp dụng trong nhiều lĩnh vực như kỹ thuật, kinh tế và khoa học máy tính.

Trong thập niên 1990, các nhà nghiên cứu đã phát triển và cải tiến thuật toán Local beam search, bao gồm việc kết hợp với các thuật tốn tìm kiếm khác để tăng hiệu quả tìm kiếm.

Hiện nay, thuật toán Local beam search vẫn được sử dụng rộng rãi trong các bài tốn tối ưu hóa và là một trong những thuật toán quan trọng trong lớp các thuật tốn tìm kiếm địa phương.

1.2 Tổng quan về thuật tốn Local beam search

Thuật toán Local beam search là một thuật tốn tìm kiếm cục bộ được sử dụng để giải quyết các bài tốn tối ưu hóa. Nó được áp dụng để tìm kiếm các giá trị tối ưu của một hàm mục tiêu trong khơng gian nhiều chiều.

Thuật tốn bắt đầu với một tập hợp các trạng thái khởi tạo, được gọi là beam, và thực hiện tìm kiếm địa phương trên các trạng thái này. Trong quá trình tìm kiếm, thuật tốn sẽ tạo ra các trạng thái mới từ các trạng thái hiện tại bằng cách áp dụng các phép biến đổi. Các trạng thái mới này sẽ được lựa chọn dựa trên hàm mục tiêu, và chỉ những trạng thái tốt nhất sẽ được giữ lại để sử dụng cho vịng lặp tiếp theo.

Q trình này được lặp lại cho đến khi thuật tốn tìm thấy giải pháp tối ưu hoặc đạt tới một số tiêu chí dừng khác. Trong trường hợp của thuật tốn Local beam search, các tiêu chí dừng thường là số lượng vòng lặp hoặc giá trị của hàm mục tiêu đã đạt tới một ngưỡng nhất định.

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

Thuật tốn Local beam search có thể được mở rộng để xử lý các bài toán với nhiều hơn một beam. Với mỗi beam, thuật tốn sẽ thực hiện tìm kiếm địa phương và lựa chọn ra các trạng thái tốt nhất để sử dụng cho vòng lặp tiếp theo. Sau đó, các trạng thái tốt nhất từ tất cả các beam sẽ được lựa chọn để tiếp tục tìm kiếm.

Thuật toán Local beam search là một trong những thuật tốn tìm kiếm địa phương phổ biến nhất và được sử dụng trong nhiều lĩnh vực như kỹ thuật, kinh tế và khoa học máy tính.

1.3 Cấu trúc của thuật tốn Local beam search

Cấu trúc của thuật toán Local beam search gồm các thành phần sau: Khởi tạo: Tạo ra tập hợp các trạng thái khởi đầu (initial states).

Tìm kiếm: Lặp lại việc tạo ra các trạng thái con từ các trạng thái hiện tại, tính tốn hàm giá trị cho các trạng thái con, lựa chọn tập hợp con tốt nhất và lặp lại cho đến khi tìm được giải pháp tối ưu hoặc đáp ứng được điều kiện dừng.

Cập nhật: Cập nhật các trạng thái hiện tại để tiếp tục quá trình tìm kiếm, lựa chọn tập hợp con tốt nhất và lặp lại cho đến khi tìm được giải pháp tối ưu hoặc đáp ứng được điều kiện dừng.

Kết thúc: Kết thúc thuật tốn sau khi tìm được giải pháp tối ưu hoặc đáp ứng được điều kiện dừng.

Điều kiện dừng: Điều kiện để dừng thuật tốn có thể là đạt đến giới hạn số lần lặp lại, đạt đến giới hạn thời gian, hoặc khi tìm được giải pháp tối ưu.

Cấu trúc của thuật toán Local beam search là một vịng lặp chính trong đó tìm kiếm được thực hiện bằng cách tạo ra các trạng thái con, tính toán hàm giá trị, lựa chọn tập hợp con tốt nhất và cập nhật các trạng thái hiện tại. Quá trình này lặp lại cho đến khi tìm được giải pháp tối ưu hoặc đáp ứng được điều kiện dừng.

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

Chương 2: Thuật toán

2.1 Các bước thực hiện của thuật toán

Thuật toán Local beam search là một thuật tốn tìm kiếm trong khơng gian trạng thái để tìm kiếm một lời giải tối ưu cho bài tốn tối ưu hóa. Các bước thực hiện thuật tốn Local beam search như sau:

Bước 1: Khởi tạo tập các trạng thái bắt đầu (có thể được chọn ngẫu nhiên hoặc dựa trên thơng tin khác, ví dụ như một giải pháp khởi đầu)

Bước 2:Tính tốn hàm giá trị (điểm số) cho các trạng thái trong tập ban đầu. Bước 3: Với mỗi trạng thái, tạo ra các trạng thái con bằng cách thực hiện một số hành động có thể từ trạng thái đó.

Bước 4: Tính tốn hàm giá trị cho tất cả các trạng thái con mới được tạo ra. Bước 5: Lựa chọn một tập hợp con của các trạng thái con tốt nhất (có điểm số cao nhất).

Bước 6: Nếu tập hợp con này chứa một giải pháp tối ưu, kết thúc thuật toán và trả về giải pháp tối ưu đó.

Bước 7: Nếu khơng, lặp lại các bước 3-6 cho các trạng thái con được chọn để tạo ra các trạng thái con tiếp theo.

Bước 8: Nếu tập hợp trạng thái ban đầu bị loại bỏ hoàn toàn, chọn một tập hợp trạng thái mới và lặp lại các bước 2-7.

Bước 9: Thuật toán sẽ kết thúc sau khi đạt đến số lần lặp tối đa hoặc giới hạn thời gian đã định trước.

Thuật toán Local beam search thực hiện việc tìm kiếm trong khơng gian trạng thái bằng cách lặp lại việc tạo ra các trạng thái con từ các trạng thái ban đầu, tính tốn hàm giá trị cho các trạng thái con đó, lựa chọn các trạng thái con tốt nhất và tiếp tục lặp lại quá trình cho đến khi tìm ra giải pháp tối ưu hoặc đạt đến giới hạn lặp lại hoặc thời gian.

2.2 Mô tả các phương pháp để tạo ra các bộ khởi tạo (initial state sets) cho thuật tốn

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

Có nhiều phương pháp để tạo ra các bộ khởi tạo cho thuật toán Local beam search, tùy thuộc vào loại bài toán và mục đích sử dụng của thuật tốn. Dưới đây là một số phương pháp phổ biến:

Khởi tạo ngẫu nhiên: Phương pháp này đơn giản và hiệu quả nhất, chỉ cần khởi tạo một tập hợp các trạng thái ban đầu ngẫu nhiên và sử dụng chúng để bắt đầu thuật tốn. Tuy nhiên, phương pháp này khơng đảm bảo rằng tập hợp khởi tạo chứa các giải pháp tốt cho bài toán.

Tạo bộ khởi tạo từ giải pháp đã biết: Nếu đã biết một giải pháp tốt cho bài toán, có thể sử dụng nó để tạo ra một tập hợp các trạng thái ban đầu. Phương pháp này đảm bảo rằng tập hợp khởi tạo chứa các giải pháp tốt, nhưng đơi khi khó khăn để tìm ra một giải pháp tốt ban đầu.

Tạo bộ khởi tạo từ phân tích dữ liệu: Đối với các bài tốn liên quan đến dữ liệu, có thể phân tích dữ liệu để tạo ra các trạng thái khởi tạo. Ví dụ, trong bài tốn phân loại ảnh, có thể sử dụng phương pháp rút trích đặc trưng để tạo ra các trạng thái ban đầu từ ảnh.

Tạo bộ khởi tạo từ các kỹ thuật khác: Ngồi các phương pháp trên, cịn có thể sử dụng các kỹ thuật khác để tạo ra các trạng thái khởi tạo. Ví dụ, trong bài tốn tối ưu hóa điều khiển, có thể sử dụng các kỹ thuật mơ hình hóa hệ thống để tạo ra các trạng thái ban đầu.

2.3 Các tham số quan trọng trong thuật toán

Các tham số quan trọng trong thuật toán Local beam search bao gồm:

<b>Số lượng các trạng thái con: Đây là số lượng các trạng thái con được tạo ra</b>

trong mỗi lần lặp của thuật toán. Nếu số lượng trạng thái con lớn hơn, thuật tốn sẽ có khả năng khám phá nhiều hơn, nhưng đồng thời cũng tăng độ phức tạp tính tốn. Nếu số lượng trạng thái con q nhỏ, thuật tốn có thể dễ dàng bị mắc kẹt ở một giá trị cục bộ.

<b>Số lần lặp lại: Đây là số lần lặp lại của thuật tốn. Nếu số lần lặp lại nhiều,</b>

thuật tốn sẽ có thời gian để khám phá và tìm kiếm giải pháp tốt nhất. Tuy nhiên, nếu số lần lặp lại quá nhiều, thuật tốn sẽ trở nên chậm và khơng hiệu quả.

<b>Hàm đánh giá: Đây là hàm được sử dụng để đánh giá chất lượng của mỗi</b>

trạng thái trong quá trình tìm kiếm. Hàm này thường được định nghĩa dựa trên u cầu của bài tốn cụ thể, và nó cần phải phù hợp với các giải pháp mong muốn.

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

<b>Chiến lược chọn lọc: Đây là cách mà thuật toán chọn ra các trạng thái con</b>

để tiếp tục tìm kiếm. Có thể sử dụng các chiến lược như chọn ngẫu nhiên, chọn theo độ ưu tiên hoặc chọn theo một hàm xác suất nhất định.

<b>Phương pháp tạo bộ khởi tạo: Đây là phương pháp tạo ra các trạng thái</b>

ban đầu. Phương pháp này cũng ảnh hưởng đến khả năng tìm kiếm của thuật tốn.

<b>Kích thước khơng gian tìm kiếm: Kích thước khơng gian tìm kiếm cũng</b>

ảnh hưởng đến khả năng tìm kiếm của thuật tốn. Nếu khơng gian tìm kiếm q lớn, thuật tốn sẽ tốn nhiều thời gian để tìm kiếm giải pháp. Nếu khơng gian tìm kiếm q nhỏ, thuật tốn có thể dễ dàng bị mắc kẹt ở một giá trị cục

2.4 Ưu điểm

Thuật toán Local beam search có nhiều ưu điểm như:

<b>Tốc độ nhanh: Vì chỉ lưu trữ một số lượng nhỏ các trạng thái con tốt nhất,</b>

Local beam search có thể tìm kiếm và giải quyết các bài toán lớn một cách nhanh chóng.

<b>Dễ dàng cài đặt: Thuật tốn Local beam search khá đơn giản và dễ dàng cài</b>

<b>Dễ dàng mở rộng: Thuật tốn Local beam search có thể được mở rộng để giải</b>

quyết các bài toán phức tạp hơn bằng cách sử dụng các phương pháp lựa chọn tập hợp con (subset selection) khác nhau.

<b>Khơng u cầu bộ nhớ lớn: Vì chỉ lưu trữ một số lượng nhỏ các trạng thái con</b>

tốt nhất, Local beam search không yêu cầu bộ nhớ lớn.

=> Local beam search là một thuật tốn tìm kiếm đơn giản và hiệu quả có thể được sử dụng để giải quyết các bài toán tối ưu trong nhiều lĩnh vực khác nhau. 2.5 Nhược điểm

Mặc dù có nhiều ưu điểm, thuật tốn Local beam search cũng có một số nhược điểm:

<b>Dễ bị rơi vào cực tiểu địa phương: Local beam search có thể bị rơi vào cực</b>

tiểu địa phương nếu khơng có các biện pháp để tránh điều này. Khi đó, thuật tốn sẽ khơng tìm được giải pháp tối ưu toàn cục.

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

<b>Yêu cầu lựa chọn thủ công của tham số: Để hoạt động hiệu quả, Local beam</b>

search yêu cầu lựa chọn thủ công của số lượng trạng thái con được lưu trữ và sử dụng trong q trình tìm kiếm.

<b>Khơng đảm bảo tìm được giải pháp tối ưu tồn cục: Do chỉ lưu trữ một số</b>

lượng nhỏ các trạng thái con tốt nhất, Local beam search khơng đảm bảo tìm được giải pháp tối ưu tồn cục của bài tốn.

=> thuật tốn Local beam search là một thuật tốn tìm kiếm đơn giản và hiệu quả, nhưng nó cũng có một số hạn chế và nhược điểm. Việc áp dụng thuật toán này vào giải quyết các bài toán tối ưu phải được thực hiện một cách cân nhắc và xem xét kỹ lưỡng các giải pháp khác để đảm bảo tìm được giải pháp tối ưu tồn cục của bài tốn.

2.6 So sánh thuật toán Local beam search với các thuật tốn tìm kiếm khác Thuật tốn Local beam search có những ưu điểm và nhược điểm so với các thuật tốn tìm kiếm khác. Dưới đây là một số so sánh:

So với thuật tốn tìm kiếm địa phương (local search): Local beam search có thể tìm được giải pháp tốt hơn bởi vì nó có thể khám phá nhiều hướng dẫn đến giải pháp tốt hơn. Tuy nhiên, nó có thể dẫn đến giải pháp tốt hơn chỉ khi có nhiều hướng khác nhau.

So với thuật tốn tìm kiếm theo chiều sâu (depth-first search): Local beam search không rơi vào trường hợp mắc kẹt trong một nhánh của cây tìm kiếm và khơng thể di chuyển đến các nhánh khác. Nó cũng có thể tìm giải pháp tốt hơn bởi vì nó có thể đánh giá được các giải pháp khác nhau.

So với thuật tốn tìm kiếm theo chiều rộng (breadth-first search): Local beam search khơng đảm bảo tìm ra giải pháp tối ưu vì nó chỉ duy trì một số giải pháp tốt nhất, trong khi breadth-first search sẽ duyệt tất cả các giải pháp có thể. Tuy nhiên, Local beam search có thể tìm ra giải pháp tốt hơn nếu khơng có q nhiều giải pháp cần duyệt.

So với thuật tốn tìm kiếm leo đồi (hill climbing search): Local beam search có khả năng tránh được bị kẹt tại điểm cực trị cục bộ bởi vì nó duy trì nhiều giải pháp tốt hơn. Tuy nhiên, nó có thể bỏ lỡ các giải pháp tốt hơn nếu chúng không được nằm trong số các giải pháp tốt nhất.

Tóm lại, Local beam search là một thuật tốn tìm kiếm tốt và có thể tìm ra giải pháp tốt hơn so với một số thuật tốn tìm kiếm khác, tuy nhiên, nó vẫn có nhược điểm và khơng đảm bảo tìm được giải pháp tối ưu.

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

Chương 3: Ứng dụng 3.1 Ứng dụng của thuật toán

Thuật toán Local beam search có nhiều ứng dụng trong các lĩnh vực khác nhau, bao gồm:

<b>Tối ưu hóa: Local beam search có thể được sử dụng để tìm kiếm giải pháp tối</b>

ưu cho các bài tốn tối ưu hóa trong các lĩnh vực như quản lý sản xuất, quản lý dự án, kế hoạch hóa năng lượng, kế hoạch hóa nguồn lực, quản lý chuỗi cung ứng, v.v.

<b>Trò chơi: Local beam search có thể được sử dụng để tìm kiếm giải pháp tối ưu</b>

cho các trò chơi như trò chơi cờ vua, trị chơi đi cờ, v.v.

<b>Tìm kiếm đường đi: Local beam search có thể được sử dụng để tìm kiếm</b>

đường đi tối ưu cho các bài tốn như tìm kiếm đường đi ngắn nhất trong các mạng lưới, tìm kiếm đường đi tối ưu cho robot di động, v.v.

<b>Học máy: Local beam search có thể được sử dụng để giải quyết các bài toán</b>

trong lĩnh vực học máy, chẳng hạn như tối ưu hóa các hàm mất mát, tìm kiếm các siêu tham số tối ưu cho các mơ hình học máy, v.v.

<b>Xử lý ngôn ngữ tự nhiên: Local beam search có thể được sử dụng để giải</b>

quyết các bài tốn trong lĩnh vực xử lý ngơn ngữ tự nhiên, chẳng hạn như tìm kiếm các câu trả lời phù hợp cho các câu hỏi, tìm kiếm các từ đồng nghĩa hoặc đối nghịch trong văn bản, v.v.

=> Local beam search là một thuật toán rất linh hoạt và có nhiều ứng dụng trong các lĩnh vực khác nhau. Các ứng dụng này đều có tính chất tối ưu hóa và tìm kiếm giải pháp tối ưu cho các bài tốn khác nhau.

3.2 Ví dụ về các bài tốn có thể giải quyết bằng thuật tốn

Bài tốn TSP (Travelling Salesman Problem): Tìm đường đi ngắn nhất để đi qua tất cả các thành phố một lần và trở về thành phố xuất phát.

Bài tốn tìm kiếm từ khóa: Tìm kiếm từ khóa trong một tập văn bản lớn.

Bài toán cắt túi (Knapsack Problem): Cho một tập hữu hạn các vật phẩm có giá trị và khối lượng, tìm cách đựng các vật phẩm vào một túi có giới hạn khối lượng sao cho tổng giá trị của các vật phẩm này là lớn nhất.

3.3 Kết quả đạt được khi áp dụng thuật toán vào các bài toán thực tế

</div>