Chương 1 đã trình bày bài toán tổng quan thu gom chất thải rắn. Có thể nhận thấy bài toán tối ưu thu gom chất thải rắn là một mối quan tâm mang tính cấp thiết tại bất kỳ đô thị nào trên thế giới. Nó mang nhiều ý nghĩa về mặt môi trường, phát triển cảnh quan và tiết kiệm kinh tế. Để giải quyết khó khăn này, luận văn xây dựng phương pháp tối ưu thời gian thu gom chất thải.
Đó là thiết kế thuật toán di truyền cho bài toán tối ưu thu gom chất thải rắn ở chương sau. 8 CHƯƠNG 2: THIẾT KẾ THUẬT TOÁN DI TRUYỀN CHO BÀI TOÁN TỐI ƯU THU GOM CHẤT THẢI RẮN ĐÔ THỊ 2. Tổng quan về thuật toán di truyền Hiện nay và trong tương lai, trí tuệ nhân tạo đã, đang và sẽ được nghiên cứu, phát triển rất mạnh mẽ và được ứng dụng rộng rãi. Đây là một mảng chuyên môn rất lớn trong khoa học máy tính, bao gồm nhiều lĩnh vực khác nhau.
Một trong những lĩnh vực đó là kỹ thuật tính toán thông minh trong đó có Thuật toán di truyền đã đem lại những phương mới để giải bài toán mà nếu áp dụng những phương pháp truyền thống sẽ gặp nhiều khó khăn [1]. Thuật toán di truyền – chỉ cần nghe tên cũng có thể hiểu được rằng nó dựa trên việc quan sát quá trình tiến hóa trong tự nhiên. Các nguyên lý cơ bản của giải thuật di truyền được Holland công bố lần đầu tiên vào năm 1962. Sau đó các nền tảng toán học đầu tiên được công bố vào năm 1975 trong cuốn sách “Adaptation in Natural and Artificial System” cũng của Holland.
Cũng có thể nói Holland là người đi tiên phong nghiên cứu trong lĩnh vực giải thuật di truyền cùng với Beglay [1]. 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ể 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 đó hay còn gọi là độ thích nghi của nó trong môi trường) sẽ bị đào thải, ngược lại, những cá thể tốt sẽ được giữ lại (đây chính là 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.
Những cá thể mới được sinh ra mang những tính trạng của cá thể cha-mẹ (còn gọi là hiện tượng di truyền). Những cá thể được giữ lại có độ thích nghi khác nhau và quá trình lai ghép được thực hiện hoàn toàn ngẫu nhiên giữa các cá thể trong quần thể. Các cá thể được tạo ra trong quá trình lai ghép có thể sẽ xảy ra hiện tượng đột biến và tạo ra những cá thể khác với cá thể cha-mẹ. Cá thể này có thể tốt hơn hoặc xấu hơn cá thể cha-mẹ.
Di truyền và đột biến là hai cơ chế có vai trò như nhau trongquá trình tiến hóa, mặc dù hiện 9 tượng đột biến xảy ra với xác suất nhỏ hơn nhiều so với xác suấtcủa hiện tượng di truyền. Và quá trình 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 [2]. Sau đây là sơ đồ thực hiện thuật giải di truyền [26]: Bắt đầu 1. Khởi tạo quần thể ban đầu, trong đó mỗi nhiễm sắc thể được thể hiện thông qua định nghĩa biểu diễn nhiễm sắc thể; 2.
Xác định fitness cho mỗi nhiễm sắc thể của quần thể; 3. Chọn lọc một tập hợp các nhiễm sắc thể (được gọi là cha mẹ) sẽ được sử dụng tái tổ hợp để tạo ra con cái; 4. Sử dụng lại ghép chéo cho cha mẹ để tạo ra con mới; 5. Sử dụng đột biến theo một xác suất xác định; 6.
Các nhiễm sắc thể có giá trị fitness tồi sẽ bị loại bỏ khỏi quần thể ; 7. Nếu tiêu chí ngừng thoải mãn thì dừng lại giải thuật trả về nhiễm sắc thể tốt nhất cùng giá trị hàm mục tiêu, nêu chưa thoải mãn, quay lại Bước 3. Kết thúc Hình 2.1: Sơ đồ thực hiện thuật giải di truyền 10 Biểu diễn nhiễm sắc thể: Công việc đầu tiên khi thực hiện việc giải bài toán bằng thuật toán di truyền là chọn cách biểu diễn các cá thể còn gọi là nhiễm sắc thể. Đó là việc ánh xạ các tham số của bài toán lên một chuỗi có chiều dài xác định.
Tùy theo từng bài toán cụ thể mà có nhưng cách biểu diễn khác nhau sao cho thích nghi. Trong đó có một số cách biểu diễn thông dụng là: biểu diễu theo dạng chuỗi ký tự, biểu diễn nhị phân, biểu diễn sử dụng hoán vị [26]. Quần thể và khởi tạo: Trong khởi tạo, một tập nhiễm sắc thể ban đầu được tạo ra, cũng gọi là quần thể ban đầu. Kích thước của quần thể hay số lượng nhiễm sắc thể rất quan trọng đối với thuật toán di truyền tổng quát, cần phải cân nhắc.
Nếu chọn kích thước quá nhỏ có thể chỉ dẫn đến một kết quả tối ưu địa phương, không phát huy được hiệu quả của thuật toán, trong khi chọn kích thước lớn đưa ra một xác suất cao hơn tối ưu toàn cục sẽ được tìm thấy, tuy nhiên, thời gian tính toán tăng lên, chương trình chạy chậm lại. Kích thước quần thể tốt nên ở trong khoảng 20-30, tuy nhiên đôi khi kích thước 50 -100 vẫn được xem là tốt [26]. Đánh giá và chọn lọc tiến hóa: Toán tử chọn lọc được sử dụng để xác định nhiễm sắc thể sẽ được sử dụng cho thế hệ kế tiếp. Nhiều kỹ thuật khác nhau có thể được sử dụng trong toán tử chọn lọc, tuy nhiên, thường là một quá trình chọn lọc được mô phỏng, trong đó các nhiễm sắc thể "mạnh nhất" được sử dụng trong di truyền.
Một trong những phương pháp chọn lọc được gọi là bánh xe Roulette, một bánh xe được chia thành các phần theo giá trị Fitness của các nhiễm sắc thể trong quần thể, ở đây những nhiễm sắc thể tốt hơn có phần bánh xe lớn hơn và nhữngnhiễm sắc thể yếu sẽ nhận được một phần nhỏ của bánh xe. Vì vậy, xác suất được lựa chọn là tỷ lệ thuận với giá trị Fitness. Khi bánh xe quay, nhiễm sắc thể có độ thích nghi cao hơn sẽ có cơ hội được lựa chọn nhiều hơn, và ngược lại [26]. Phương pháp thứ hai để chọn lọc là phương pháp Ranking.
Trong phương pháp Ranking, tất cả các nhiễm sắc thể trong quần thể được sắp xếp theo giá trị Fitness f (x) để phân cấp, các nhiễm sắc thể với giá trị Fitness tốt hơn được xếp 11 hạng cao hơn. Trong TSP, thường là f (x) xác định độ dài của toàn bộ đường đi, tuy nhiên, hàm này có thể bao gồm bổ sung các đặc điểm và các độ đo để giữ cho các nhiễm sắc thể trong quần thể. Nếu trong phương pháp bánh xe Roulette, giá trị Fitness được sử dụng khi gán một xác suất để được chọn, trong phương pháp Ranking các nhiễm sắc thể được chọn lọc theo hạng [26]. Một phương pháp khác để lựa chọn được gọi là chọn lọc Tournament.
Phương pháp này sử dụng đặc điểm từ phương pháp Ranking nhưng có sự điều chỉnh, Lựa chọn Tournament đánh hạng chỉ một nhóm con các nhiễm sắc thể. Lúc đầu, chọn hai nhóm con từ quần thể. Mỗi nhóm con phải chứa ít nhất hai nhiễm sắc thể. Các nhiễm sắc thể được xếp hạng trong một nhóm như trong phương pháp chọn lọc Ranking.
Các nhiễm sắc thể tốt nhất từ mỗi nhóm được lựa chọn để sinh sản, và các nhiễm sắc thể tồi nhất được chọn để loại bỏ khỏi quần thể. Để tạo ra một lứa con mới gồm l phần tử, trong mỗi lần lặp người ta chọn l nhóm con sau đó thực hiện chọn l cặp cha mẹ để sản sinh ra l phần tử con [5]. Tái tổ hợp hay lai ghép: Một phần quan trọng của thuật toán di truyền là toán tử lai ghép.Toán tử chéo mô phỏng sự sinh sản giữa hai nhiễm sắc thể, ở đây con cái được tạo ra thừa hưởng một số đặc điểm từ các nhiễm sắc thể cha mẹ. Nhiều toán tử chéo và đột biến với các nhiễm sắc thể được mã hoá dưới dạng một chuỗi ký hiệu hoặc số.
Một số toán tử chéo được sử dụng nhiều trông bài toán VRP và TSP như sau [16], [24] : Lai ghép một điểm cắt Lai ghép vòng Lai ghép sắp xếp Lai ghép đồng bộ Lai ghép kết hợp cạnh Lai ghép trộn 12 Đột biến là một giải pháp xử lý vấn đề tối ưu hóa địa phương và tăng khả năng tìm ra sự tối ưu toàn cục [14]. Trong toán tử đột biến, một nhiễm sắc thể mới được tạo ra từ giải pháp đơn lẻ được chọn bởi thay đổi một số đặc điểm trong nó. Trong thuật toán di truyền, các toán tử chéo và đột biến được áp dụng bởi xác suất xác định trước. Chúng ta có thể tìm thấy các giá trị cho những xác suất này được trong đề xuất của Srinivas và Patnaik (1994) [23], Hong và các cộng sự [14].
Duy trì sự đa dạng và áp lực chọn lọc: Hai yếu tố quan trọng của di truyền thuật toán là đa dạng quần thể và áp lực chọn lọc. Hai yếu tố này có liên quan: nếu áp lực chọn lọc đang gia tăng thì sự đa dạng dân số sẽ giảm và ngược lại. Áp lực chọn lọc là một công việc của toán tử lựa chọn. Áp lực chọn quá yếu có thể dẫn đến việc tìm kiếm không hiệu quả.
Toán tử lựa chọn cũng như các toán tử khác ảnh hưởng đến tính đa dạng của quần thể. Làm sao để đạt được hiệu suất tốt trong khi duy trì tính đa dạng của quần thể càng lâu càng tốt. Đột biến rất quan trọng trong sự biến đổi của các nhiễm sắc thể, khi quần thể trở nên đồng nhất [23]. Sự đa dạng quần thể cũng có thể được duy trì bằng cách tăng kích thước quần thể hoặc do tỷ lệ đột biến lớn hơn, tuy nhiên, yếu tố hiệu suất nên được tính đến.
Các kỹ thuật khác cũng được sử dụng. Cách tiếp cận phổ biến là tránh trùng lặp nhiễm sắc thể trong quần thể. Tiêu chí dừng: Thuật toán di truyền là một quá trình ngẫu nhiêncó thể chạy mãi mãi, nếu một tiêu chí dừng không được áp dụng. 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 tiêu chí dừng cho thuật toán.
Một tiêu chí dừng đơn giản có thể là thời gian tính toán tối đa hoặc số lặp lặp lại tối đa, hoặc giá trị trung bình của độ thích nghi trên tất cả các nhiễm sắc thể của quần thể không thay đổi [26].
