Chương 1 CƠ SỞ LÝ THUYẾT Chương này sẽ trình bày các kiến thức cơ bản về bài toán tối ưu và một số cách tiếp cận giải quyết bài toán tối ưu, trong đó đi sâu vào hai hướng tiếp cận bao gồm hướng tiếp cận heuristic/meta-heuristic và hướng tiếp cận học tăng cường. Ngoài ra, chương này cũng trình bày về mạng cảm biến không dây, mạng cảm biến sạc không dây, vấn đề tối ưu chiến lược sạc trong các mạng cảm biến sạc không dây. Bài toán tối ưu Trong rất nhiều tình huống thực tế, con người luôn phải tìm ra những giải pháp tốt nhất, hiệu quả nhất, tốn chi phí hoặc tiêu hao tài nguyên ít nhất. Việc lựa chọn trong một loạt các giải pháp khả thi để tìm giải pháp tốt nhất cho một mục đích nào đó được gọi là tối ưu.
Để máy tính có thể giải quyết các vấn đề thực tế đó thì trước tiên phải mô hình các bài toán về dạng toán học [46]. Trong khoa học máy tính, các bài toán tìm giá trị của các biến để tìm giá trị lớn nhất (cực đại) hoặc nhỏ nhất (cực tiểu) cho mục tiêu cụ thể nào đó của bài toán được gọi là “bài toán tối ưu”. Bài toán tối ưu thường được phân loại thành hai lớp dựa vào miền giá trị của các biến là liên tục hay rời rạc: • Tối ưu hóa liên tục, trong đó miền giá trị của các biến là liên tục. • Tối ưu hóa rời rạc (tối ưu hóa tổ hợp), trong đó miền giá trị của các biến là rời rạc (số nguyên, hoán vị, đồ thị).
Tối ưu hóa liên tục Nghiên cứu [46] đưa ra dạng tổng quan của một bài toán tối ưu hóa liên tục như sau: 8 Maximize/Minimize :f (x) (1.1) Các ràng buộc :gi (x) ≤ 0 i = 1, ., xn ) với xi là một biến nhận giá trị liên tục. • f (x) : R → R là hàm mục tiêu của bài toán. • gi (x) ≤ 0 thể hiện các ràng buộc bất đẳng thức. • hj (x) = 0 thể hiện các ràng buộc đẳng thức.
Tối ưu hóa rời rạc Bài toán tối ưu rời rạc tổng quát có thể phát biểu như sau: Maximize/Minimize : f (x) với x ∈ D ⊂ Rn , (1.4) D là tập các vectơ x = (x1 , x2 , ., xn ) mà một số (hoặc tất cả) các thành phần của x chỉ nhận các giá trị rời rạc. Tập D thường được xác định bởi một hệ thống các phương trình và bất phương trình với điều kiện bổ sung về tính nguyên của các biến số sau đây: gi (x) = 0, i = 1, 2, .7) được gọi là bài toán quy hoạch nguyên. Nếu n1 = n ta có bài toán quy hoạch nguyên hoàn toàn, nếu n1 < n ta có bài toán quy hoạch nguyên bộ phận. Một trong lớp các bài toán quy hoạch nguyên quan trọng là quy hoạch nguyên tuyến tính thu được từ bài toán quy hoạch nguyên tổng quát khi các hàm f (x) và gi (x) là tuyến tính.
Một số cách tiếp cận giải bài toán tối ưu Có hai phương pháp giải các bài toán tối ưu là phương pháp giải chính xác (exact method) và phương pháp giải gần đúng (approximate method). Với 9 phương pháp thứ nhất, thuật toán luôn luôn đảm bảo trả về phương án tối ưu toàn cục tuy nhiên hầu hết các bài toán tối ưu trong thực tế đều không thể áp dụng được do chi phí và thời gian tính toán là quá lớn. Vì vậy, giải chính xác chỉ được áp dụng cho các bài toán tối ưu kích thước nhỏ. Ngược lại, các thuật toán gần đúng mặc dù không đảm bảo phương án tối ưu toàn cục nhưng có thể đưa ra những lời giải “đủ tốt” trong thời gian chấp nhận được.
Đây được xem là giải pháp hiệu quả thay thế cho các phương pháp giải chính xác. Trong nghiên cứu này, luận án tập trung vào các phương pháp giải gần đúng với hai cách tiếp cận dựa vào các thuật toán heuristic/meta-heuristic và các thuật toán học tăng cường. Hai cách tiếp cận này sẽ được trình bày chi tiết trong các phần tiếp theo của chương này. Các thuật toán tối ưu theo cách tiếp cận Meta-heuristic 1.
Thuật toán di truyền Thuật toán di truyền được Holland đề xuất và được Michalevicz phát triển [47]. Thuật toán này thường được áp dụng để giải các bài toán tối ưu hóa. Thuật toán di truyền được xây dựng dựa trên quy luật tiến hóa sinh học hay phát triển tự nhiên của một quần thể sống. Các cá thể phải trải qua một quá trình phát triển và sinh sản để tạo ra những cá thể mới cho thế hệ tiếp theo.
Trong quá trình tăng trưởng và phát triển những cá thể xấu (theo một tiêu chuẩn nào đó ví dụ như độ thích nghi với môi trường và mỗi cá thể sẽ có độ thích nghi với môi trường khác nhau) sẽ bị đào thải, đồng thời, những cá thể tốt sẽ được giữ lại (quá trình chọn lọc) và được lai ghép (quá trình lai ghép) để tạo ra những cá thể mới cho thế hệ sau. Quá trình lai ghép được thực hiện ngẫu nhiên giữa các cá thể trong quần thể. Những cá thể mới được sinh ra mang những tính trạng của cá thể cha mẹ (di truyền). Các cá thể trong quá trình lai ghép có thể sẽ xảy ra hiện tượng đột biến và tạo ra các cá thể khác với cá thể cha mẹ.
Các cá thể này có thể tốt hơn hoặc xấu hơn cá thể cha mẹ chúng. Tuy nhiên xác suất xảy ra hiện tượng đột biến là nhỏ hơn rất nhiều so với hiện tượng di truyền. Như vậy lai ghép và chọn lọc là hai quá trình cơ bản xuyên suốt quá trình tiến hóa tự nhiên. Vì vậy thuật toán di truyền là một trong những thuật toán tiến hóa, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa tự nhiên là quá trình hoàn hảo, hợp lý nhất, tự mang tính tối ưu.
Điều này tuy chưa được chứng minh nhưng thuật toán phù hợp với thực tế khách quan. Tính tối ưu được thể 10 hiện ở chỗ, thế hệ sau bao giờ cũng tốt hơn, hoàn thiện hơn thế hệ trước. Tuy nhiên, không phải tất cả các trường hợp đều như vậy, vẫn có một hoặc một số cá thể của thế hệ trước tốt hơn thế hệ sau vì vậy, trong khi sử dụng thuật toán di truyền, chúng ta phải lưu lại những cá thể tốt nhất ở mỗi thế hệ, trải qua số thế hệ nhất định (đây là tham số thiết kế) chúng ta đem so sánh những cá thể tốt nhất của thế hệ với nhau và chọn ra những cá thể tốt nhất giữa chúng. Đó có thể chính là lời giải tối ưu của bài toán hoặc hội tụ tới lời giải tối ưu của bài toán.
Thuật toán di truyền sử dụng nhiều thuật ngữ của ngành sinh học như chọn lọc (selection), lai ghép (crossover ), đột biến (mutation), nhiễm sắc thể (chromosome). Thông thường một cá thể mang nhiều nhiễm sắc thể nhưng để đơn giản ta chỉ coi mỗi cá thể mang một nhiễm sắc thể và bộ mã gen của chúng mang đặc tính của cá thể, mỗi nhiễm sắc thể là một lời giải của bài toán [48]. Các vấn đề cơ bản về thuật toán di truyền Biểu diễn cá thể: để áp dụng được thuật toán di truyền, việc đầu tiên là phải tìm được cách biểu diễn của các cá thể sao cho mỗi cá thể biểu diễn một giải pháp của bài toán đang được quan tâm. Dựa vào đặc trưng của mỗi bài toán mà người thiết kế giải thuật cần lựa chọn các cách biểu diễn phù hợp nhất như: biểu diễn nhị phân, biểu diễn nguyên, biểu diễn thực, biểu diễn theo hoán vị, .[49] Đánh giá độ thích nghi: là một hàm lượng giá đóng vai trò môi trường.
Độ thích nghi là khả năng thích nghi của mỗi cá thể (giải pháp) đối với môi trường (bài toán). Việc xây dựng hàm đo độ thích nghi (fitness function) là một bước quan trọng trong thuật toán di truyền vì cho ta thấy cá thể thích nghi thế nào với môi trường (tốt hay là không tốt). Các toán tử di truyền: bao gồm lai ghép, đột biến, chọn lọc và thay thế. • Lai ghép: là quá trình tạo ra cá thể mới dựa trên nhiều cá thể đã có.
Các cá thể con được tạo ra bằng cách hoán đổi các gen từ một số cá thể ban đầu (gọi là cha mẹ của chúng). Hai phép lai ghép phổ biến nhất là lai ghép đơn điểm và lai ghép đa điểm. • Đột biến: là quá trình tạo ra cá thể mới từ một cá thể ban đầu bằng cách thay đổi một số gen trong cá thể. Nếu sử dụng biểu diễn nhị phân thì phép đột biến thường sử dụng là bit flipping, nghĩa là nếu gen là 1 thì được đổi thành 0 và ngược lại.
• Chọn lọc và thay thế (reproduction): là quá trình chọn những cá thể 11 từ quần thể hiện tại để tạo ra thế hệ sau. Quá trình này đào thải những cá thể xấu (có độ thích nghi thấp) và giữ lại những cá thể tốt (có độ thích nghi cao). Nếu như phép lai ghép tạo ra những cá thể mới có thể kế thừa được những gen tốt của cha mẹ thì phép đột biến sẽ giúp duy trì tính đa dạng của quần thể bằng cách thêm vào các gen mới một cách ngẫu nhiên. Điều này khiến cho quần thể tránh mắc kẹt tại một cá thể tối ưu cục bộ.
Phép đột biến chỉ xảy ra với xác suất nhỏ vì nếu xác suất đột biến lớn thì thuật toán di truyền sẽ trở thành một quá trình tìm kiếm ngẫu nhiên. Điều kiện dừng: thuật toán di truyền là một quá trình ngẫu nhiên, nên không thể đảm bảo chắc chắn thuật toán di truyền sẽ dừng sau hữu hạn bước. Vì vậy, để đảm bảo thuật toán di truyền sẽ kết thúc, người dùng thường phải định nghĩa điều kiện dừng cho thuật toán. Thuật toán tối ưu bầy đàn Tương tự như thuật toán di truyền, thuật toán tối ưu bầy đàn (Particle Swarm Optimization - PSO) là một dạng của các thuật toán tiến hóa quần thể.
Tuy nhiên, PSO khác với di truyền ở chỗ, phương pháp này thiên về việc sử dụng sự tương tác giữa các cá thể trong một quần thể để khám phá không gian tìm kiếm. Thuật toán tối ưu bầy đàn được giới thiệu đầu tiên vào năm 1995 bởi James Kennedy và C. Thuật toán có nhiều ứng dụng quan trọng trong tất cả các lĩnh vực mà ở đó đòi hỏi giải quyết vấn đề tối ưu hóa. Thuật toán PSO được xây dựng dựa vào quá trình mô phỏng sinh học của đàn chim.
Để hiểu rõ về thuật toán PSO, hãy xem một ví dụ đơn giản về quá trình tìm kiếm thức ăn của một đàn chim.