phần mở đầu, kết luận và phụ lục, nội dung của luận án đƣợc bố cục thành 4 chƣơng nhƣ sau: CHƢƠNG 1. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀI TOÁN LẬP LỊCH JOB SHOP Chƣơng này trình bày vắn tắt về thuật toán di truyền cổ điển (mã hóa nhị phân), phân tích, đánh giá các giải pháp quan trọng nhất cho JSP đã đƣợc công bố trong những năm qua. Nhận diện những khó khăn khi giải quyết bài toán lập lịch job shop mà chúng ta cần phải vƣợt qua trong hiện tại và tƣơng lai. Sau khi phân tích, đánh giá, luận án đề xuất một số hƣớng nghiên cứu cho bài toán này.
CHƢƠNG 2: HAI BÀI TOÁN CON CỦA BÀI TOÁN LẬP LỊCH JOB SHOP Bài toán flow shop và flow shop hoán vị là hai trƣờng hợp riêng của bài toán job shop rất thƣờng gặp trong thực tiễn. Chƣơng này trình bày các khái niệm cơ bản liên quan đến hai bài toán con của JSP và thuật toán Johnson cho bài toán flow shop 2 máy và 3 máy có hạn chế điều kiện. Cuối cùng, một thuật toán di truyền mã hóa số tự nhiên đƣợc đề xuất cho hai bài toán này. 17 CHƢƠNG 3: MỘT THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP Bài toán lập lịch job shop là bài toán lập lịch tổng quát nhất và cũng khó giải quyết nhất.
Trong chƣơng này, luận án đề xuất một thuật toán di truyền lai mới cho JSP. Thuật toán này kết hợp thuật toán di truyền với một số kỹ thuật tìm kiếm khác nhƣ các luật ƣu tiên nhanh, kỹ thuật tìm kiếm lân cận,. Thuật toán đƣợc cài đặt và chạy thử nghiệm trên các bài toán test chuẩn, các kết quả tính toán đã khẳng định tính vƣợt trội của nó. Để khắc phục độ phức tạp tính toán của JSP, thuật toán đã đƣợc song song hóa, cài đặt và chạy thử nghiệm trên các bài toán test chuẩn.
Kết quả lời giải tối ƣu thu đƣợc tƣơng tự nhƣ thuật toán tuần tự nhƣng thời gian tính toán đƣợc cải thiện nhiều lần. CHƢƠNG 4: PHÂN TÍCH TÍNH HỘI TỤ CỦA THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP Trong chƣơng này, luận án phân tích thuộc tính hội tụ của thuật toán đã đề xuất bằng cách áp dụng các tính chất của xích Markov. Trên cơ sở phân tích xích Markov của thuật toán di truyền, luận án đã chứng minh thuật toán đƣợc đề nghị trong chƣơng 3 hội tụ tới tối ƣu toàn cục. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀI TOÁN LẬP LỊCH JOB SHOP Thuật toán di truyền (Genetic Algorithm - GA) là chiến lƣợc tìm kiếm đƣợc thiết kế phỏng theo các quá trình sinh học trong tự nhiên để tối ƣu hóa các hàm mục tiêu.
GA đƣợc đề xuất và nghiên cứu một cách có hệ thống lần đầu tiên bởi John Holland và các cộng sự tại trƣờng đại học Michigan vào năm 1975. Bài toán lập lịch job shop (JSP) xuất hiện từ những năm 1950. Đã có nhiều tiếp cận khác nhau đƣợc đề xuất cho bài toán này, từ các tiếp cận chính xác đến các tiếp cận gần đúng và gần đây là các tiếp cận lai kết hợp đồng thời nhiều kỹ thuật tìm kiếm với nhau. Trong chƣơng này, luận án thống kê, phân tích, đánh giá các giải pháp quan trọng nhất cho JSP đã đƣợc công bố trong những năm qua.
Cuối cùng, một số hƣớng nghiên cứu cho JSP và các khó khăn nổi bật khi giải quyết JSP mà chúng ta cần phải vƣợt qua trong hiện tại và tƣơng lai cũng đƣợc đề cập. Thuật toán di truyền cổ điển Khái niệm về thuật toán di truyền đã đƣợc biết tới từ những năm 1950. Tuy nhiên, trong thời kỳ này thuật toán di truyền chƣa đƣợc phát triển thành phƣơng pháp luận mà mới chỉ đƣợc sử dụng để giải quyết các bài toán riêng rẽ xuất phát từ sinh học. Vào năm 1975, tại trƣờng đại học Michigan ở Mỹ, John Holland và các cộng sự đã công bố một công trình mang tựa đề "Adaptation in Natural and Artificial Systems" [34].
Công trình này đƣợc xem nhƣ một nghiên cứu bài bản và toàn diện nhất về GA thời bấy giờ. Hiện nay, GA đã đƣợc nghiên cứu và ứng dụng ở hầu hết các quốc gia trên thế giới và đặc biệt phát triển mạnh ở Mỹ, Trung Quốc, Nhật Bản, Hàn 19 Quốc,. Lý thuyết GA đã đƣợc ứng dụng thành công trong rất nhiều lĩnh vực khác nhau nhƣ sinh học, khoa học máy tính, kỹ thuật lai ghép, xử lý ảnh,. Cấu trúc của thuật toán di truyền cổ điển a.
Mã hóa lời giải Trong GA cổ điển, mỗi lời giải hay cá thể đƣợc mã hóa bởi một chuỗi các số nhị phân. Mỗi vị trí trên chuỗi đƣợc gọi là một gien và nhận một trong hai giá trị 0 hoặc 1. Nhƣ vậy, một lời giải trong GA cổ điển có dạng sau: 1 0 0 1 1 0 0 1 1 1 Hình 1.1 - Một lời giải đƣợc mã hóa nhị phân Một trong những vấn đề cốt lõi của GA là mã hóa các lời giải sao cho phù hợp với đặc thù của bài toán. Trong GA cải tiến sau này, các nhà nghiên cứu thƣờng mã hóa lời giải của bài toán rất đa dạng theo đặc thù của bài toán cần giải quyết.
Cheng và những ngƣời khác [13] đã tổng kết và phân loại các chiến lƣợc biểu diễn lời giải đƣợc áp dụng cho GA thành 2 nhóm bao gồm 9 loại nhƣ sau: Nhóm 1: Mã hóa trực tiếp: 1. Dựa vào các thao tác. Dựa vào các công việc. Dựa vào sự liên quan giữa các cặp công việc.
Dựa vào thời gian hoàn thành. Dùng các khóa ngẫu nhiên. Nhóm 2: Mã hóa gián tiếp: 6. Dựa vào danh sách ƣu tiên.
Dựa vào luật ƣu tiên. Dựa vào đồ thị phân biệt 9. Các tiếp cận dựa trên GA áp dụng cho JSP thƣờng sử dụng phƣơng pháp mã hóa trực tiếp để mã hóa các lịch biểu nhƣ là các cá thể và các toán tử di truyền đƣợc sử dụng để tiến hóa các cá thể thành các lịch biểu tốt hơn. Toán tử trao đổi chéo Toán tử trao đổi chéo kết hợp các đặc tính trên hai cá thể cha để tạo ra một hoặc hai cá thể con mới bằng cách hoán đổi các đoạn gien tƣơng ứng của các cá thể cha.
Có một số cách hoán đổi các gien của hai cá thể cha sau đây: Trao đổi chéo một điểm Cha 1 1 1 0 1 0 0 1 1 0 1 Cha 2 1 0 1 1 1 0 0 1 1 0 Hình 1.2 - Hai cá thể cha cho phép trao đổi chéo Con 1 1 1 0 1 0 0 0 1 1 0 Con 2 1 0 1 1 1 0 1 1 0 1 Hình 1.3 - Hai cá thể con sau phép trao đổi chéo Theo cách này, chọn ngẫu nhiên một vị trí đƣợc gọi là điểm bắt chéo. Sau đó ghép đoạn trƣớc điểm bắt chéo của cha 1 với đoạn sau điểm bắt chéo của cha 2 và ngƣợc lại. Ví dụ: Cho hai cá thể cha nhƣ trong hình 1.2, phép trao đổi chéo một điểm sau gien thứ 5 cho kết quả hai cá thể con nhƣ trong hình 1. 21 Trao đổi chéo hai điểm Theo cách này, chọn ngẫu nhiên 2 vị trí trên chuỗi cá thể cha.
Sau đó tráo đổi đoạn gien nằm giữa 2 điểm đó của 2 cá thể cha cho nhau. Ví dụ: Cho hai cá thể cha nhƣ trong hình 1.2, phép trao đổi chéo 2 điểm sau gien thứ 2 và sau gien thứ 8 cho kết quả hai cá thể con nhƣ trong hình 1. Con 1 1 1 1 1 1 0 0 1 0 1 Con 2 1 0 0 1 0 0 1 1 1 0 Hình 1.4 - Hai cá thể con sau phép trao đổi chéo 2 điểm Trao đổi chéo đồng nhất Phép trao đổi chéo này gieo ngẫu nhiên một đồng xu, số lần gieo bằng số gien của cá thể cha. Nếu kết quả gieo là 1 (mặt sấp) thì lấy gien từ cha 2 còn nếu kết quả gieo là 0 (mặt ngửa) thì lấy gien từ cha 1.
Ví dụ: Cho hai cá thể cha nhƣ trong hình 1.2, phép trao đổi chéo đồng nhất với kết quả gieo ngẫu nhiên đồng xu là 1010101011 cho kết quả là cá thể con trong hình 1.5 - Cá thể con sau phép trao đổi chéo đồng nhất Trong GA cải tiến sau này, phép trao đổi chéo có thể đƣợc thay đổi cho phù hợp với bài toán thực tiễn, nhƣng vẫn phải đảm bảo nguyên tắc cá thể con đƣợc tái tổ hợp các gien từ hai (hoặc có thể nhiều hơn) cá thể cha. Toán tử đột biến 22 Toán tử đột biến sửa đổi một số gien trong một cá thể cha đƣợc chọn một cách ngẫu nhiên bằng cách thay đổi các gien có giá trị 0 thành 1 và ngƣợc lại. Ví dụ: Cho cá thể cha trong hình 1.6, giả sử các gien thứ 2, 5, 7, 9 đƣợc chọn để đột biến, chúng ta có cá thể con sau đột biến nhƣ trong hình 1. Cha 0 1 1 1 0 1 1 0 1 0 Con 0 0 1 1 1 1 0 0 0 0 Hình 1.6 - Cá thể cha và cá thể con sau phép đột biến Trong GA cải tiến, phép đột biến có thể rất đa dạng.
Tuy nhiên, vẫn phải đảm bảo nguyên tắc thực hiện sửa đổi một số gien trên một cá thể cha để có một cá thể con. Toán tử chọn lọc Toán tử chọn lọc sẽ chọn ra một quần thể cho thế hệ tiếp theo của quá trình tiến hóa. Khả năng đƣợc chọn của mỗi cá thể tùy thuộc và độ thích nghi (thƣờng là trên cơ sở giá trị của hàm mục tiêu) của nó. Những cá thể có giá trị hàm thích nghi cao hơn sẽ có nhiều khả năng đƣợc chọn hơn để trở thành thành viên trong quần thể của thế hệ tiếp theo.
Cơ chế chọn lọc này thực hiện theo nguyên lý bánh xe xổ số. Mỗi cá thể trong quần thể có một xác suất chọn lọc đƣợc tính theo công thức: pi = eval(vi) / F. Trong đó, eval(vi) là giá trị của hàm thích nghi của cá thể vi, F là tổng các giá trị thích nghi của quần thể. Tuy nhiên, trong GA cải tiến sau này thực hiện phép chọn lọc đa dạng hơn.
Phép chọn lọc có thể kết hợp cả việc ấn định với chọn lọc ngẫu nhiên theo nguyên tắc bánh xe xổ số. Một thủ tục đơn giản cho thuật toán di truyền cổ điển Một quá trình tiến hóa đƣợc thực hiện trên một quần thể gồm N cá thể (N tùy theo ngƣời dùng chọn). Mỗi cá thể đƣợc đánh giá độ tốt xấu theo hàm thích nghi. Tại thế hệ 0, một quần thể P(0) đƣợc khởi tạo một cách ngẫu nhiên.