Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải Giải thuật di truyền và ứng dụng đối với bài toán vận tải
Bài toán vận tải
Bài toán quy hoạch tuyến tính
1.1.1 Mô hình một số bài toán thực tế
Chương này sẽ giới thiệu những kiến thức cơ bản về quy hoạch tuyến tính, một mô hình toán học được G B Dantzig phát triển vào năm 1947 sau khi nghiên cứu các bài toán lập kế hoạch cho lực lượng không quân Mỹ Ban đầu, ông gọi mô hình này là "Quy hoạch trong cấu trúc tuyến tính", nhưng vào mùa hè năm 1948, sau khi nhận được ý kiến từ Tijalling Koopmans, ông đã đồng ý đổi tên thành "Quy hoạch tuyến tính" Nhiều năm sau, Albert Tuckey đã sử dụng thuật ngữ ngắn gọn hơn là "Linear Program" Ngay sau khi ra mắt, mô hình quy hoạch tuyến tính đã được áp dụng để giải quyết nhiều bài toán thực tế trong các lĩnh vực khác nhau.
Công ty Reddy Mikks chuyên sản xuất hai loại sơn: sơn nội thất và sơn ngoài trời Nguyên liệu chính để sản xuất bao gồm hai loại, A và B, với nguồn dự trữ lần lượt là 60 tấn và 80 tấn Để sản xuất một tấn sơn nội thất, công ty cần sử dụng một lượng nguyên liệu nhất định từ nguồn dự trữ này.
Để sản xuất một tấn sơn ngoài trời, cần sử dụng 1 tấn nguyên liệu A và 2 tấn nguyên liệu B Trong khi đó, nguồn cung hiện có là 2 tấn nguyên liệu A và 1 tấn nguyên liệu B Nhu cầu thị trường cho hai loại sản phẩm này trong một ngày đang được theo dõi.
- Nhu cầu sơn nội thất không hơn nhu cầu sơn ngoài trời quá 1 tấn;
- Nhu cầu cực đại của sơn nội thất là 2 tấn.
Giá bán buôn 1 tấn sơn nội thất hiện tại là 2000 USD, trong khi giá sơn ngoài trời không có dấu hiệu giảm Việc đầu tư thiếu đồng bộ, quy hoạch và kế hoạch chi tiết đã dẫn đến nhiều công trình hoàn thành nhưng không đưa vào sử dụng, hoặc dở dang, gây lãng phí vốn đầu tư Công tác quản lý và giám sát đầu tư còn yếu kém, dẫn đến thất thoát vốn và không đảm bảo chất lượng công trình Để khắc phục tình trạng này, nhà nước và quốc hội đang hoàn thiện các văn bản luật như Luật Đầu tư, Luật Xây dựng và Luật Đấu thầu (sửa đổi) Đối với doanh nghiệp, đặc biệt là VNPT Hải Dương, việc cải tiến mô hình tổ chức quản lý và quy trình đầu tư là rất cần thiết để phù hợp với thực tiễn và đáp ứng xu thế phát triển xã hội Hiện nay, đã có một số công trình nghiên cứu và luận văn thạc sĩ liên quan đến công tác quản lý dự án đầu tư.
Doãn Thị Hải Anh, quản lý dự án đầu tư tại Học viện Công nghệ Bưu chính Viễn thông, đã thực hiện nghiên cứu về lý thuyết quản lý dự án đầu tư trong luận văn của mình Cô phân tích thực trạng công tác quản lý dự án tại Học viện, chỉ ra những ưu điểm và tồn tại, đồng thời đề xuất một số biện pháp nhằm hoàn thiện quản lý dự án đầu tư tại đây.
Võ Thị Minh Nguyệt (2013) đã nghiên cứu và hệ thống hoá các vấn đề liên quan đến hiệu quả sử dụng vốn đầu tư tại VNPT Thừa Thiên Huế Bài viết đánh giá thực trạng hiện tại của hiệu quả sử dụng vốn đầu tư trong tổ chức này và đề xuất những biện pháp nhằm nâng cao hiệu quả sử dụng vốn đầu tư, góp phần cải thiện hoạt động kinh doanh và phát triển bền vững tại VNPT Thừa Thiên Huế.
Vấn đề đặt ra là cần sản xuất mỗi ngày như thế nào để doanh thu là lớn nhất.
Gọi x 1 là số lượng sơn nội thất cần sản xuất trong một ngày;
Gọi x2 là số lượng sơn ngoài trời cần sản xuất trong một ngày, trong khi x1 và x2 được xem là các biến hoặc phương án của bài toán Do sản lượng sản phẩm phải là số thực không âm, ta có điều kiện x1 ≥ 0 và x2 ≥ 0, với đơn vị tính là tấn Doanh thu thu được trong một ngày sẽ được xác định dựa trên các biến này.
F(x) = 2000x 1 + 3000x 2 và F được gọi là hàm mục tiêu (objective funtion).
Số lượng sản phẩm x1 và x2 không được vượt quá lượng nguyên liệu dự trữ có hạn Những giới hạn này đối với các biến x1 và x2 được gọi là ràng buộc (constraint).
Hơn nữa, việc sản xuất lại phải đảm bảo không nhiều hơn nhu cầu của thị trường, do đó:
Cặp sắp thứ tự (x1, x2) được xem là phương án chấp nhận được (feasible) nếu nó đáp ứng tất cả các ràng buộc Khi đó, (x1, x2) được gọi là nghiệm chấp nhận được (feasible solution).
Ta có mô hình toán học của bài toán lập kế hoạch sản xuất như sau:
Tìm phương án chấp nhận được làm hàm mục tiêu F(x) đạt cực đại max và được biểu diễn dưới dạng toán học dưới đây:
Ví dụ 1.2 Bài toán phân công lao động Ta xét một bài toán cụ thể sau đây:
Một đội sản xuất gồm 12 lao động loại A, 26 lao động loại B và 16 lao động loại C cần phân công công việc giữa việc gặt và đập lúa Năng suất làm việc của lao động loại A là 2 sào/ngày khi gặt và 5 sào/ngày khi đập, trong khi lao động loại B có năng suất tương ứng là 1,8 sào/ngày khi gặt và 4 sào/ngày khi đập.
3,6; lao động loại C là 1,5 và 2,4 Hãy phân công lao động sao cho gặt được nhiều nhất và số lúa được gặt về cũng được đập hết trong ngày.
Gọi x, y, z lần lượt là số lao động các loại A, B, C được phân công để đi gặt lúa, x ≥ 0, y ≥ 0, z ≥ 0 Khi đó số lao động ở nhà đập lúa tương ứng là: 12−x,26−y và 16−z.
Mặt khác, hai công việc phải đảm bảo cân đối, nên:
7x+ 5,4y + 3,9z = 192 Khi đó mô hình toán học của bài toán này là:
Ví dụ 1.3 Bài toán vận tải (Transportation Problem) Ta xét một dạng bài toán tổng quát.
Trong quá trình sản xuất, hàng hoá được vận chuyển từ 02 kho A,
Kho A và kho B mỗi nơi có 15 tấn hàng Nhu cầu tiêu thụ tại cửa hàng I là 10 tấn, trong khi cửa hàng II cần 20 tấn Cước phí vận chuyển một tấn hàng từ kho A đến hai cửa hàng I và II cần được xác định.
1 triệu VNĐ, 3 triệu VNĐ và kho B đến hai cửa hàng I, II tương ứng là
Kế hoạch vận chuyển hàng hóa từ kho A và B đến các cửa hàng I và II cần được lập nhằm giảm thiểu tổng chi phí Điều kiện cần thiết là phải đảm bảo tất cả hàng hóa từ các kho được phát ra và các cửa hàng nhận đủ số lượng hàng theo nhu cầu.
Lượng hàng vận chuyển từ kho i đến cửa hàng j được ký hiệu là xij (với i = 1,2 và j = 1,2, xij ≥ 0) Kế hoạch vận chuyển, hay phương án vận chuyển hàng hoá, được biểu diễn dưới dạng một ma trận thực cấp 2×2, X = (xij) Cước phí vận chuyển hàng hoá sẽ được tính dựa trên ma trận này.
F(x) = x^11 + 3x^12 + 2x^21 + 5x^22 Hiện trạng đầu tư đang gặp nhiều khó khăn do thiếu đồng bộ, quy hoạch và kế hoạch chi tiết, dẫn đến nhiều công trình hoàn thành nhưng không được đưa vào sử dụng hoặc dang dở, gây lãng phí vốn Công tác quản lý và giám sát đầu tư yếu kém làm thất thoát vốn và không đảm bảo chất lượng công trình Để khắc phục, nhà nước và quốc hội đang hoàn thiện các dự thảo luật như Luật Đầu tư, Luật Xây dựng và Luật Đấu thầu sửa đổi Đối với doanh nghiệp, đặc biệt là VNPT Hải Dương, việc cải tiến mô hình tổ chức quản lý và quy trình đầu tư là cần thiết để phù hợp với thực tiễn và xu thế phát triển xã hội Hiện đã có một số nghiên cứu và luận văn thạc sĩ về quản lý dự án đầu tư.
Doãn Thị Hải Anh, Quản lý dự án đầu tư tại Học viện Công nghệ Bưu chính Viễn thông, đã thực hiện nghiên cứu về quản lý dự án đầu tư trong luận văn của mình Năm 2011, tác giả phân tích thực trạng công tác quản lý dự án tại Học viện, chỉ ra những ưu điểm và tồn tại, đồng thời đề xuất các biện pháp nhằm hoàn thiện công tác này.
Bài toán vận tải
Giả sử có m kho hàng (trạm phát) và n điểm tiêu thụ (trạm thu), với khả năng cung cấp hàng ở kho thứ i là a i đơn vị (i = 1,2, , m) và nhu cầu tiêu thụ ở điểm thứ j là b j đơn vị (j = 1,2, , n), trong đó a i ≥ 0 và b j ≥ 0 Cước phí vận chuyển một đơn vị hàng hóa từ kho i đến điểm tiêu thụ j là cij VNĐ Điều kiện đặt ra là khả năng cung cấp phải bằng nhu cầu tiêu thụ.
Cần lập kế hoạch vận chuyển hàng hóa từ kho thứ nhất đến điểm tiêu thụ thứ j với mục tiêu giảm thiểu tổng chi phí, đồng thời đảm bảo rằng các kho phải cung cấp đủ hàng hóa và các điểm tiêu thụ nhận được số lượng hàng hóa theo nhu cầu.
Ký hiệu xij đại diện cho số lượng hàng cần vận chuyển từ điểm i đến điểm j, với i từ 1 đến m và j từ 1 đến n, trong đó xij không âm Phương án vận chuyển hàng hóa được biểu diễn dưới dạng ma trận m × n, ký hiệu là X = (xij) Cước phí vận chuyển hàng hóa sẽ được tính toán dựa trên ma trận này.
Cần chú ý đến khả năng cung cấp hàng hóa của kho i và khả năng tiêu thụ hàng hóa của cửa hàng j, từ đó xác định các ràng buộc ẩn liên quan.
Hành trình đầu tư hiện nay đang gặp nhiều khó khăn do thiếu đồng bộ, quy hoạch và kế hoạch chi tiết, dẫn đến nhiều công trình hoàn thành nhưng không đưa vào sử dụng hoặc dở dang, gây lãng phí vốn Công tác quản lý và giám sát đầu tư còn yếu kém, làm thất thoát vốn và không đảm bảo chất lượng công trình Để khắc phục tình trạng này, Nhà nước và Quốc hội đang hoàn thiện các văn bản luật như Luật Đầu tư (Sửa đổi), Luật Xây dựng (Sửa đổi) và Luật Đấu thầu (Sửa đổi) Đối với doanh nghiệp, đặc biệt là VNPT Hải Dương, việc cải tiến mô hình tổ chức quản lý và quy trình thực hiện công tác đầu tư là rất cần thiết để phù hợp với thực tiễn và xu thế phát triển xã hội Hiện nay, đã có một số công trình nghiên cứu và luận văn thạc sĩ liên quan đến quản lý dự án đầu tư.
Doãn Thị Hải Anh, Quản lý dự án đầu tư tại Học viện Công nghệ Bưu chính Viễn thông, đã thực hiện nghiên cứu trong luận văn năm 2011 về lý luận quản lý dự án đầu tư Bài viết phân tích thực trạng công tác quản lý dự án tại Học viện, chỉ ra những ưu điểm và tồn tại, đồng thời đề xuất một số biện pháp nhằm hoàn thiện công tác này.
Võ Thị Minh Nguyệt (2013) đã nghiên cứu về hiệu quả sử dụng vốn đầu tư tại VNPT Thừa Thiên Huế, hệ thống hoá các vấn đề chung liên quan đến chủ đề này Tác giả đánh giá thực trạng hiệu quả sử dụng vốn đầu tư tại VNPT Thừa Thiên Huế và đề xuất các biện pháp nhằm nâng cao hiệu quả sử dụng vốn đầu tư, góp phần phát triển bền vững cho tổ chức.
Ta có mô hình toán học của bài toán vận tải là:
Mô hình này đại diện cho một bài toán quy hoạch tuyến tính có cấu trúc đặc biệt, với các biến xuất hiện trong hai phương trình của hệ ràng buộc Đặc biệt, tất cả các hệ số của các biến trong hệ ràng buộc đều bằng 1.
X j=1 b j ("tổng phát" không bằng "tổng thu") ta gọi là bài toán không cân bằng.
3 Ta luôn giả thiết bài toán vận tải cân bằng thu - phát.
X j=1 bj thì ta bổ sung thêm một trạm phát giả thứ m + 1 và a m+1 n
X i=1 a i với cước phí vận chuyển c m+1,j = 0; j = 1,2, , n.
X j=1 bj thì ta bổ sung thêm một trạm thu giả thứn+ 1 và b n+1 m
Thuật toán phân phối giải bài toán vận tải
Xét bài toán vận tải:
Ma trận X = (xij) (i = 1,2, , m, j = 1,2, , n) được xem là một phương án của bài toán vận tải khi các giá trị của nó đáp ứng đồng thời các điều kiện ràng buộc (1.13), (1.14), (1.15) Một phương án được gọi là phương án tối ưu (hay nghiệm) và được ký hiệu là X opt nếu nó giúp hàm mục tiêu (1.12) đạt giá trị cực tiểu Các ô (i, j) với xij > 0 được gọi là ô chọn của phương án X.
Một phương án mà các ô chọn không lập thành một chu trình gọi là một phương án cơ sở (hay phương án cực biên).
Ký hiệu H đại diện cho tập hợp các ô chọn trong phương án cơ sở X, với điều kiện số ô chọn không vượt quá m + n - 1 Nếu số ô chọn bằng m + n - 1, phương án cơ sở được xem là không suy biến; ngược lại, nếu số ô chọn nhỏ hơn m + n - 1, phương án này được gọi là suy biến.
Nếu phương án cơ sở là suy biến, ta có thể thêm một số ô suy biến với giá trị x ij = 0 vào tập H, đảm bảo rằng tập H có đúng m+n−1 ô và không chứa chu trình Những ô được chọn theo cách này được gọi là ô chọn 0.
Do vậy ta luôn có thể giả thiết phương án cơ sở X ứng với tập H luôn có đúng m+ n−1 ô chọn và không chứa chu trình.
1.3.2 Cơ sở lý luận của thuật toán Định lý 1.2 Gọi C = (c ij ) là ma trận cước phí của bài toán vận tải (i = 1,2, , m;j = 1,2, , n) Nếu ta cộng vào mỗi phần tử của hàng i một số ri và cộng vào mỗi phần tử của cột j một số sj tùy ý, ta sẽ được một bài toán vận tải mới, tương đương với bài toán vận tải ban đầu có cùng phương án tối ưu
Thay thế ma trận C = (cij) bằng ma trận C 0 = (cij + ri + sj) sẽ dẫn đến một bài toán vận tải mới, chỉ khác biệt ở hàm mục tiêu, trong khi tất cả các ràng buộc vẫn giữ nguyên.
Hàm mục tiêu của hai bài toán chỉ khác nhau một hằng số, vì vậy nếu X là nghiệm của bài toán ban đầu, thì X cũng sẽ là nghiệm của bài toán mới và ngược lại.
Dựa vào Định lý 1.2, chúng ta có thể xác định phương án tối ưu bằng cách quy 0 cho các ô chọn, tức là điều chỉnh cước phí của các ô chọn trong một phương án cơ sở thành 0, từ đó tạo ra một bài toán tương đương.
Giả sử X là một phương án cơ sở và H là tập hợp các ô chọn không chứa chu trình, với m + n - 1 ô chọn Để giải bài toán, ta cần chọn cặp số r_i và s_j cho mỗi ô (i, j) ∈ H sao cho thỏa mãn phương trình c_0ij = c_ij + r_i + s_j = 0 Điều này dẫn đến việc giải hệ phương trình với m + n ẩn r_i và s_j, cụ thể là c_ij + r_i + s_j = 0 cho các chỉ số i và j trong khoảng từ 1 đến m và 1 đến n.
Hệ phương trình (1.16) có m+n ẩn nhưng chỉ có m+n−1 phương trình độc lập, dẫn đến việc hệ nghiệm phụ thuộc vào một tham số duy nhất và luôn có vô số nghiệm Để tính nhanh các ẩn còn lại, chúng ta chọn tham số đó bằng 0 Quy trình giải hệ phương trình này được gọi là quy 0 ô chọn Theo định lý 1.3, nếu X = (xij) là một phương án cơ sở với tập hợp các ô chọn H và c ij = 0 với (i, j) ∈ H.
1 Nếu cij > 0 với mọi ô (i, j) ∈/ H thì X là phương án tối ưu;
2 Nếu có ít nhất một số c ij < 0 với ô (i, j) ∈/ H thì X không là phương án tối ưu Khi đó ta có thể xây dựng được một phương án cơ sở mới X 0 tốt hơn phương án X.
Chứng minh 1 Đặt z = F(c) Vì các c ij = 0 với (i, j) ∈ H, nên: z m
Suy ra, mọi phương án X 0 6= X, ta đều có z 0 ≥ 0 = z vì c ij > 0 với mọi ô (i, j) ∈/ H.
2 Giả sử tồn tại c i o j o < 0 với ô (i o , j o ) ∈/ H Khi đó tập hợp H ∪ {(i o , j o )} sẽ chứa đúng một chu trình duy nhất V và số ô của chu trình là chẵn.
Bắt đầu từ ô (i o , j o ) ta đánh số thứ tự từ số 1 cho chu trình V Khi đó số các ô trên V chia thành hai lớp Ký hiệu V c là tập hợp các ô chẵn,
V l là tập hợp các ô lẻ.
Tiếp theo, đặt θ o = min{x ij ,(i, j) ∈ V c } là lượng hàng nhỏ nhất trong những ô chẵn của V.
Ta xây dựng phương án mới X 0 như sau: x 0 ij
xij −θo nếu (i, j) ∈ V c x ij +θ o nếu (i, j) ∈ V l xij nếu (i, j) ∈/ V
Trong chu trìnhV sẽ có một ô chọn tương ứng với giá trịθo = min{x ij , (i, j) ∈ V c } bị loại ra và thêm vào một ô (i o , j o ) ∈/ H ứng với c i o j o < 0.
Ta sẽ được một phương án mới X 0 có đúng m+n−1 ô chọn và không chứa chu trình Vậy nên, X’ là một phương án cơ sở.
Vì c i o j o < 0, nên z 0 = c i o j o θ o < 0 = z, nên phương án X 0 tốt hơn X.Điều phải chứng minh
Nếu phương án cơ sở X không suy biến, thì θo > 0, cho thấy X0 thực sự tốt hơn X Ngược lại, nếu X suy biến, θo có thể bằng 0, trong trường hợp này X0 chỉ tốt bằng X Cả hai trường hợp đều cho thấy X0 là phương án chấp nhận được Định lý 1.3 cung cấp dấu hiệu tối ưu cho các phương án cơ sở và đề xuất một phương pháp, thuật toán để điều chỉnh các phương án này nhằm tiến gần hơn đến phương án tối ưu.
Thuật toán phân phối tìm phương án tối ưu của bài toán vận tải gồm các bước sau:
Bước 1 Xây dựng phương án cơ sở ban đầu X với tập hợp H có m+n−1 ô chọn;
Bước 2 Quy 0 các ô chọn, xác định được các giá trị r i , s j ; tính giá trị của cước phí giả c 0 ij = c ij +r i +s j ở các ô loại, kiểm tra dấu cước phí giả ở các ô loại.
Nếu c 0 ij ≥ 0,(i, j) ∈/ H, thì X là phương án tối ưu;
Nếu có ít nhất một số c 0 ij < 0 với (i, j) ∉ H, chúng ta cần thực hiện điều chỉnh để tìm ra một phương án cơ sở mới X 0 không kém hơn X, trong đó ô (i o , j o ) được chọn trong phương án cơ sở mới X 0.
Bước 3: Xác định ô (i∗, j∗) có cước phí giả âm nhỏ nhất trong số các ô loại Tiếp theo, tìm ô đưa ra từ các ô chọn thuộc H Xác định chu trình V bao gồm các ô chọn thuộc H và đi qua ô (i∗, j∗), trong đó ô (i∗, j∗) chia V thành tập đỉnh chẵn Vc và tập đỉnh lẻ Vl, với (i∗, j∗) ∈ Vl Ô đưa ra là ô (io, jo) có θo = min{xij, (i, j) ∈ Vc} Bước 4: Xây dựng phương án mới X0 = (x0ij) theo quy tắc đã xác định.
Quay lại bước 2 để xác minh xem phương án X0 có phải là phương án tối ưu hay không Quá trình sẽ kết thúc khi tìm ra phương án tối ưu Xopt.
1.3.4 Vấn đề chọn phương án ban đầu
Có nhiều cách để xác định phương án cơ sở ban đầu, nhưng trong phần này, chúng ta sẽ tập trung vào phương án ưu tiên theo tiêu chí có lợi nhất hoặc phương án có cước phí thấp nhất Nội dung chi tiết sẽ được trình bày dưới đây.
Các dạng khác của bài toán vận tải
1.4.1 Bài toán vận tải không cân bằng thu phát
Nếu a không bằng b, bài toán sẽ không có phương án Tuy nhiên, thực tế cho thấy không nhất thiết phải vận chuyển toàn bộ hàng từ các trạm phát để đáp ứng yêu cầu của các trạm thu Có thể xảy ra trường hợp lượng hàng ở các trạm phát không đủ để đáp ứng yêu cầu của các trạm thu Trong tình huống này, ta có thể thêm một trạm thu giả a m+1 hoặc một trạm phát giả b n+1, với giá trị được tính bằng chênh lệch giữa tổng lượng hàng thu và tổng lượng hàng phát: a m+1 = b−a nếu a nhỏ hơn b, hoặc b n+1 = a−b nếu a lớn hơn b.
Lượng hàng vận chuyển từ trạm phát ai đến trạm thu giả bn+1 được giữ lại tại ai, trong khi lượng hàng chuyển từ trạm phát giả am+1 đến trạm thu bj cho thấy tại bj, lượng hàng này không được đáp ứng.
Tất nhiên cước phí các ô trên trạm giả bằng không.
Cước phí tại các trạm giả thường bằng không và là mức thấp nhất, nhưng vẫn được ưu tiên phân phối cho các ô có cước phí dương nhỏ nhất ở các ô không phải của trạm giả Cuối cùng, phần còn lại sẽ được phân phối vào các ô của trạm giả.
Ví dụ 1.6 a = 120, b = 100 Thêm trạm thu giả với b4 = 20
Giá trị tối ưu của hàm f(x) = 410 chưa đạt được khi xem xét ô (3,4), nơi có cước phí giả âm nhỏ nhất Do đó, ô này sẽ được chọn để xây dựng phương án mới trong bảng, với các giá trị a i \b j là 30, 40, 30, và 20.
1.4.2 Bài toán vận tải dạng cực đại
Xét bài toán vận tải dạng cực đại max f(x) m
(1.17) Đưa về bài toán tìm min dạng tương đương bằng cách đặt c ij −q ij (i = 1, , m;j = 1, , n) và chú ý rằng f max = −g min g(x) m
Một công ty vận tải biển cần tuyển 110 lao động, bao gồm 10 máy trưởng, 25 thợ 1, 30 thợ 2 và 45 thợ 3 Tuy nhiên, phòng Nhân sự chỉ tìm được 90 ứng viên, trong đó có 25 kỹ sư.
20 trung cấp (TC) và 45 công nhân (CN) Khả năng cán bộ được đánh giá theo công việc qua bảng sau:
Cần tối ưu hóa việc bố trí để khai thác tối đa năng lực của mọi người Đây là một bài toán vận tải không cân bằng, với mục tiêu tối đa hóa thu nhập Để giải quyết, cần đưa vào trạm phát giả với thông số a4 = 110−90 = 20, và các chỉ số ai, bj là 10, 25, 30, 45, cùng với ri.
Giá trị f(x) = 380 chưa đạt tối ưu với cước phí giả âm lớn nhất tại ô (23) Do đó, ô (23) sẽ được chọn để xây dựng phương án mới trong bảng.
0 0 0 0 s j 5 4 3 2 c 0 ij ≥ 0 với mọi 1 ≤ i, j ≤ 4 Do đó, ta suy ra, đây là phương án tối ưu và f max = 400 Vậy có phương án phân phối lao động tối ưu như sau:
10 kỹ sư làm Máy trưởng;
Bài toán bổ nhiệm yêu cầu phân công n người cho n công việc nhằm tối đa hóa tổng năng suất Mỗi người i thực hiện công việc j với năng suất c ij (i, j = 1, , n) Để giải quyết bài toán này, ta sử dụng biến x ij, trong đó x ij = 1 nếu người i được giao việc j và x ij = 0 nếu không Đây là bài toán quy hoạch nguyên 0−1, với bảng năng suất được cung cấp để hỗ trợ việc phân công.
Ta giải bài toán như sau: a i \b j 1 1 1 1 r i
-8 -6 -7 -3 s j 3 1 2 0 c 0 ij ≤ 0với mọi 1 ≤i, j ≤ 5, nên ta có phương án tối ưu và f max = 24.
Bài toán xe rỗng ứng dụng thường xuyên trong thực tế, nên được xem là một dạng đặc biệt của bài toán vận tải.
Công ty vận tải cần hoàn thành hợp đồng chở hàng theo bảng 1.1, vì vậy cần lập kế hoạch vận chuyển tối ưu để giảm thiểu tổng số tấn xe rỗng Các cự ly giữa các địa điểm được liệt kê trong bảng 1.2 sẽ là cơ sở để xây dựng kế hoạch này.
TT Hàng Cung Cầu Khối lượng
Bảng 1.1: Hợp đồng chở hàng
A 5 26 2 15 15 20 Bảng 1.2: Cự ly vận chuyển
Cước phí là cự ly; nơi có hàng là trạm thu xe rỗng, nơi cần hàng là trạm phát xe rỗng.
Trạm thu xe rỗng Trạm phát xe rỗng
Bảng 1.3 trình bày khả năng thu - phát trong bài toán vận tải cân bằng, với mục tiêu tối thiểu hóa chi phí Giả định rằng A1 và A2 là các trạm có nguồn xe vận tải đáp ứng đầy đủ nhu cầu hàng hóa.
21 22 4 28 20 s j -10 -11 -7 -25 -15 c 0 ij ≥ 0 với mọi i, j, nên F min = 1404.
Bảng phân phối xe rỗng với tổng tấn×km xe rỗng ít nhất là:
Tuyến đường Số tấn xe rỗng
Bảng 1.4: Tổng số tấn × km xe rỗng ít nhất
Kết hợp các trạm có nguồn xe như A1 và A2 cho phép phân phối lộ trình tối ưu trong các bài toán thực tế Dựa trên lộ trình vận tải thực tế, chúng ta có thể xác định một lộ trình giả định để cải thiện hiệu quả vận chuyển.
Chương 1 của bài viết trình bày những kiến thức cơ bản về Bài toán vận tải, một dạng đặc biệt của Bài toán Quy hoạch tuyến tính Phương pháp giải quyết Bài toán vận tải sử dụng Thuật toán phân phối, với chiến lược quy 0 ô chọn, là phương pháp đơn giản và dễ áp dụng Bài toán cũng đề cập đến trường hợp không cân bằng, và để giải quyết, ta chuyển đổi sang bài toán vận tải cân bằng bằng cách thêm các trạm thu giả hoặc trạm phát giả Việc tìm giá trị tối đa trong bài toán vận tải cũng được thực hiện nhanh chóng nhờ vào đẳng thức maxf = −min(−f).
Giải thuật di truyền và ứng dụng đối với bài toán vận tải
Giới thiệu về Giải thuật di truyền
Trong lĩnh vực công nghệ thông tin, Giải thuật di truyền (GA) là một phần quan trọng của Tính toán tiến hóa (EC), một lĩnh vực đang phát triển nhanh chóng trong trí tuệ nhân tạo Tính toán tiến hóa có thể được chia thành năm hướng nghiên cứu chính.
Thuật toán di truyền (GA) là một phương pháp tối ưu hóa dựa trên quá trình di truyền tự nhiên, nhằm cải thiện các lời giải qua nhiều thế hệ, bắt đầu từ một tập hợp các lời giải ban đầu.
Quy hoạch tiến hoá (Evolutionary Programming - EP) là một phương pháp tối ưu hóa dựa trên các quy luật tiến hóa Nó tìm kiếm các giải pháp kết hợp có khả năng giải quyết toàn diện một bài toán từ một nhóm các phương pháp có thể chỉ giải quyết được một phần của bài toán đó.
Các chiến lược tiến hoá (Evolutionary Strategies - ES) là phương pháp dựa trên những chiến lược ban đầu, nhằm phát triển và điều chỉnh các chiến lược mới phù hợp hơn với môi trường thực tế.
Lập trình di truyền (Genetic Programming - GP) là một phương pháp mở rộng của thuật toán di truyền (GA) áp dụng trong lĩnh vực phát triển các chương trình máy tính Mục tiêu chính của GP là tự động sinh ra các chương trình máy tính nhằm tối ưu hóa giải quyết các vấn đề cụ thể.
Các hệ thống phân loại (Classifier Systems - CS) là những thuật toán di truyền đặc biệt, được áp dụng trong lĩnh vực học máy để phát hiện và xây dựng các quy tắc trong các hệ thống dựa trên quy tắc.
GA và các thuật toán tiến hóa được xây dựng trên quan niệm rằng "quá trình tiến hóa tự nhiên là hoàn hảo và tối ưu" Điều này thể hiện rõ ràng qua việc thế hệ sau luôn vượt trội hơn thế hệ trước, cho thấy tính tối ưu của tiến trình này trong việc cải thiện và phát triển.
Sự hình thành và phát triển của GA trên thế giới có thể được điểm qua các mốc thời gian quan trọng như sau:
Vào năm 1960, Rechenberg đã giới thiệu khái niệm Tính toán tiến hoá trong tác phẩm "Các chiến lược tiến hoá" Ý tưởng này đã thu hút sự quan tâm và được nhiều nhà nghiên cứu tiếp tục phát triển sau đó.
Vào năm 1975, John Holland đã phát minh ra thuật toán gen, và ông cùng với các đồng nghiệp và sinh viên đã phát triển nó Cuốn sách "Sự thích nghi trong các hệ tự nhiên và nhân tạo" đã tổng hợp những kết quả từ quá trình nghiên cứu và phát triển này.
Vào năm 1992, John Koza đã phát triển phương pháp "Lập trình gen" bằng cách sử dụng Thuật toán di truyền (GA) để giải quyết nhiều bài toán khác nhau Hiện nay, GA ngày càng trở nên quan trọng trong lĩnh vực tối ưu hóa, nơi có nhiều bài toán thú vị và ứng dụng thực tiễn, nhưng thường gặp khó khăn và thiếu giải thuật hiệu quả để giải quyết.
Các khái niệm cơ bản
2.2.1 Cá thể, nhiễm sắc thể
Trong thuật toán di truyền (GA), cá thể đại diện cho một giải pháp của bài toán, và trong ngữ cảnh này, cá thể được hiểu là một nhiễm sắc thể (NST) Mỗi NST bao gồm nhiều gen, với mỗi gen có thể mang các giá trị khác nhau để xác định một tính trạng cụ thể Do đó, trong GA, khái niệm cá thể và nhiễm sắc thể có thể coi là tương đương, với mỗi gen được xem như một phần tử trong chuỗi nhiễm sắc thể.
Quần thể là tập hợp các cá thể có chung những đặc điểm nhất định Trong lĩnh vực GA (Thuật toán di truyền), quần thể được hiểu là tập hợp các giải pháp cho một bài toán cụ thể.
Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã tạo ra sự thay đổi ở các cá thể trong quần thể, với những cá thể thích nghi tốt có khả năng tồn tại và sinh sản cao hơn Ngược lại, các cá thể không thích nghi sẽ dần bị loại bỏ Dựa trên nguyên lý này, trong quá trình chọn lọc gen, việc lựa chọn các cá thể có độ thích nghi tốt là rất quan trọng để tạo ra thế hệ mới vượt trội hơn Mặc dù có nhiều phương pháp lựa chọn, mục tiêu cuối cùng vẫn là tăng cường khả năng chọn lọc cho các cá thể tốt.
Lai ghép trong tự nhiên là quá trình kết hợp các tính trạng của bố mẹ để tạo ra thế hệ con Trong thuật toán di truyền (GA), lai ghép được hiểu là sự tổ hợp các thành phần từ hai lời giải cha mẹ nhằm sinh ra một lời giải mới với các đặc tính mong muốn, tốt hơn thế hệ trước Quá trình này đóng vai trò quan trọng trong GA, giúp tối ưu hóa các giải pháp.
2.2.5 Đột biến (Mutation) Đột biến là sự biến đổi tại một (hay một số) gen của NST ban đầu để tạo ra một NST mới Đột biến có xác suất xảy ra thấp hơn lai ghép.Đột biến có thể tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban đầu Tuy nhiên trong GA thì ta luôn muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua từng thế hệ.
Mô hình GA
Với các khái niệm được giới thiệu ở trên, GA được mô tả bởi sơ đồ theo hình 2.1 sau đây:
Hình 2.1: Sơ đồ mô tả GA
1 Xác lập các tham số ban đầu của bài toán.
2 Khởi tạo: Sinh ngẫu nhiên một quần thể gồm n cá thể (là n lời giải ban đầu của bài toán).
3 Xác lập quần thể mới: tạo quần thể mới bằng cách lặp lại các bước sau cho đến khi quần thể mới hoàn thành, bao gồm:
3.1 Tính độ thích nghi của mỗi cá thể.
3.2 Kiểm tra điều kiện kết thúc giải thuật.
3.3 Chọn lọc các cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn).
3.4 Tiến hành lai ghép các cặp bố-mẹ với một xác suất lai ghép được chọn để tạo ra một cá thể mới.
3.5 Tiến hành đột biến với xác suất đột biến được chọn xác định cá thể đột biến.
4 Kiểm tra điều kiện dừng: Nếu điều kiện đượ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 chính là quần thể hiện tại.
Các tham số của GA
Kích thước quần thể là yếu tố quan trọng xác định số lượng cá thể trong một thế hệ Nghiên cứu cho thấy, kích thước quần thể cần được duy trì ở mức hợp lý; quá ít cá thể sẽ giảm khả năng lai giống và sử dụng không gian tìm kiếm, dẫn đến việc bỏ lỡ các giải pháp tối ưu Ngược lại, quần thể quá đông sẽ làm chậm quá trình chạy của thuật toán di truyền (GA), ảnh hưởng đến hiệu quả giải thuật Do đó, việc tăng kích thước quần thể cần tuân theo một giới hạn nhất định để đạt được hiệu quả tốt nhất.
Xác suất lai ghép thể hiện tần suất tạo ra thế hệ mới thông qua quá trình lai ghép Nếu xác suất lai ghép là p c, thì khả năng một cá thể được lai ghép sẽ là pc Trong trường hợp không thực hiện lai ghép, thế hệ con sẽ giống hoàn toàn bố mẹ, trong khi nếu được lai ghép, con sinh ra sẽ mang đặc điểm của cả bố và mẹ.
Xác suất đột biến phản ánh tần suất thay đổi gen trên nhiễm sắc thể (NST) Nếu xác suất đột biến là p m, thì mỗi gen trên NST có khả năng bị đột biến là p m Toán tử đột biến giúp ngăn chặn thuật toán di truyền (GA) rơi vào cực trị địa phương, nhưng nếu xác suất đột biến quá cao, GA sẽ trở thành một thuật toán tìm kiếm ngẫu nhiên.
Nhận xét 2.1 Xuất phát từ sơ đồ thực hiện GA, chúng ta có thể có một số nhận xét như sau:
GA sử dụng lập luận ngẫu nhiên để tìm kiếm giải pháp tối ưu cho các vấn đề phức tạp, khác với phương pháp xác định trong toán học giải tích Hình thức ngẫu nhiên này được hướng dẫn bởi giá trị thích nghi, cho phép GA xác định giải pháp tối ưu trong một tập hợp rộng lớn các khả năng.
GA tập trung vào việc tìm kiếm giải pháp cho các vấn đề, thay vì chú trọng vào những chi tiết cụ thể Họ tìm kiếm các điều kiện tối ưu để cải thiện quy trình điều hành và phân nhóm.
33 những giải pháp có được.
GA là công cụ lý tưởng cho các bài toán tối ưu toàn cục, đặc biệt trong những không gian tìm kiếm lớn và phức tạp Nhờ khả năng duyệt qua không gian tìm kiếm một cách đại diện, GA cho phép tìm kiếm hiệu quả mà không cần kiểm tra từng điểm trong toàn bộ không gian.
Cơ chế thực hiện GA
2.5.1 Mã hóa Để có thể thực hiện GA, vấn đề đầu tiên là xuất phát từ bài toán thực tế, ta cần phải mô tả các phương án của bài toán dưới một dạng nào đó (mô hình toán học, tin học, ) Vấn đề mô tả đó được gọi là các phương pháp mã hóa Thông thường người ta sử dụng một trong các phương pháp như sau: a Mã hoá nhị phân
Mã hoá nhị phân là phương pháp phổ biến nhất để mã hoá NST, trong đó mỗi NST được biểu diễn dưới dạng chuỗi nhị phân Mỗi bit trong chuỗi này có khả năng thể hiện một đặc tính của nghiệm.
Mã hoá nhị phân là phương pháp phổ biến trong việc tối ưu hóa các hàm một biến hoặc nhiều biến, trong đó mỗi chuỗi nhị phân đại diện cho hàm tại một tập giá trị của các biến Ngoài ra, mã hoá nhị phân còn được ứng dụng trong nhiều loại bài toán khác nhau.
Mã hoá nhị phân, mặc dù rất phổ biến, nhưng có nhược điểm là có thể tạo ra không gian mã hoá lớn hơn so với không gian giá trị của NST.
Do đó, với nhiều bài toán thì biểu diễn nhị phân là không hữu hiệu. b Mã hoá hoán vị
Mã hoá hoán vị là phương pháp sử dụng chuỗi số để biểu diễn thứ tự sắp xếp của các nhiễm sắc thể (NST) Phương pháp này rất hữu ích cho các bài toán liên quan đến thứ tự, trong đó việc hoán vị các số trong chuỗi giúp thay đổi thứ tự của chúng Mã hoá hoán vị có ứng dụng rộng rãi trong các bài toán như bài toán du lịch và bài toán lập lịch.
Mã hoá trực tiếp theo giá trị là phương pháp hữu ích trong các bài toán liên quan đến giá trị phức tạp, tương tự như với số thực Mỗi NST được cấu thành từ một chuỗi các giá trị, có thể bao gồm số nguyên, số thực, kí tự, hoặc các đối tượng phức tạp hơn, tùy thuộc vào yêu cầu của bài toán.
Mã hóa số thực thường được áp dụng cho các bài toán đặc biệt, yêu cầu phát triển các toán tử đột biến và lai ghép phù hợp Mỗi nhiễm sắc thể (NST) được mã hóa dưới dạng một véc tơ trong không gian, thường sử dụng cho các bài toán tối ưu số Phương pháp mã hóa này đang được phát triển mạnh mẽ trong giai đoạn hiện nay.
Phương pháp này được sử dụng trong các biểu thức toán học Mỗi NST là một cây của một nhóm đối tượng nào đó.
2.5.2 Khởi tạo quần thể ban đầu
Khởi tạo quần thể ban đầu là bước quan trọng trong thuật toán di truyền (GA), thường được thực hiện bằng cách tạo ra ngẫu nhiên các giải pháp khả thi Những giải pháp này thường phải đáp ứng các ràng buộc của bài toán, mặc dù chưa chắc chắn rằng chúng đã tối ưu Tùy thuộc vào từng bài toán cụ thể, có nhiều phương pháp khởi tạo khác nhau Chất lượng của quần thể ban đầu ảnh hưởng trực tiếp đến chất lượng của giải pháp mà GA tìm ra, do đó, việc khởi tạo tốt sẽ dẫn đến kết quả tối ưu hơn.
2.5.3 Xác định hàm thích nghi
Theo các nghiên cứu và các thử nghiệm của nhiều nhà nghiên cứu về
Hàm tính độ thích nghi trong GA là yếu tố then chốt quyết định thành công hay thất bại của thuật toán Để đạt hiệu quả cao, hàm thích nghi cần phản ánh chính xác giá trị thực của NST trong việc giải quyết bài toán, đồng thời nó cũng chính là hàm mục tiêu của bài toán.
Cơ chế lựa chọn là quá trình quan trọng khi chọn các cá thể từ quần thể P(t) để lai ghép và đột biến, nhằm tạo ra quần thể mới P(t+1) Có nhiều phương pháp khác nhau để thực hiện việc chọn lọc này, và dưới đây sẽ là một số cơ chế phổ biến thường được áp dụng trong thực tiễn.
Ta sử dụng các kí hiệu như sau:
- Kí hiệu NST thứ i là v i
- Hàm tính độ thích nghi của NST v i là f(v i ).
- Kích thước quần thể là pop_size().
- Số NST cần chọn là N.
Cơ chế lựa chọn theo bánh xe Roulette:
Bước 1: Tính tổng độ thích nghi của cả quần thể: F pop_size
Bước 2: Tính xác suất chọn p i cho mỗi NST v i : p i = f(vi)
F Bước 3: Tính vị trí xác suất qi của mỗi NST: qi i
Bước 4: Cơ chế lựa chọn theo bánh xe Roulette được thực hiện bằng cách quay bánh xe N lần Mỗi lần, một NST sẽ được chọn từ quần thể hiện hành để đưa vào quần thể mới theo nguyên tắc đã định.
- Phát sinh ngẫu nhiên một số r trong khoảng [0,1].
- Nếu r < q 1 thì chọn NST v 1 ; ngược lại thì chọn NST thứ i(2≤ i ≤ pop_size) sao cho q i−1 ≤ r ≤ q i
Cơ chế lựa chọn xếp hạng cho phép một số nhiễm sắc thể (NST) được chọn nhiều lần, phù hợp với lý thuyết lược đồ Theo đó, các NST tốt nhất sẽ có nhiều bản sao, trong khi NST trung bình giữ nguyên và NST kém sẽ bị loại bỏ.
Cơ chế lựa chọn xếp hạng được mô tả như sau:
Bước 1: Sắp xếp các NST trong quần thể theo độ thích nghi từ thấp đến cao.
Bước 2: Đặt lại độ thích nghi cho quần thể đã được sắp xếp, trong đó NST thứ nhất có độ thích nghi là 1, NST thứ hai có độ thích nghi là 2, và tiếp tục như vậy cho đến NST thứ pop_size, có độ thích nghi là pop_size.
Phương pháp lựa chọn theo kiểu bánh xe Roulette đã giảm thiểu việc một NST được chọn nhiều lần, tuy nhiên, điều này có thể gây ra sự hội tụ chậm và làm cho NST có độ thích nghi cao không khác biệt nhiều so với các NST khác Cơ chế lựa chọn này dựa trên việc lấy mẫu ngẫu nhiên.
Cơ chế lựa chọn theo mẫu được thực hiện như sau:
Bước 1: Biểu diễn xác suất chọn các NST lên trên một đường thẳng. Bước 2: Đặt N điểm chọn lên đường thẳng Các điểm chọn này cách nhau 1
N, điểm đầu tiên đặt ngẫu nhiên trong khoảng
.Bước 3: Với một điểm chọn, NST gần với nó nhất về bên phải sẽ được chọn.
Phương pháp này có đặc điểm là các điểm chọn được phân bố đều trên trục số, do đó sẽ gần với điểm xứng đáng được chọn.
Thuật toán di truyền kinh điển
GA kinh điển sử dụng mã hóa nhị phân, mỗi cá thể được mã hóa là một chuỗi nhị phân có chiều dài cố định.
Sử dụng véc tơ nhị phân độ dài L làm nhiễm sắc thể để biểu diễn giá trị của biến x trong khoảng [lx, ux] Độ dài L của nhiễm sắc thể phụ thuộc vào yêu cầu cụ thể của bài toán, trong đó mỗi bit mã hóa x tương ứng với một giá trị trong khoảng này.
[0,2 L ] sẽ được ánh xạ lên giá trị thực thuộc miền [l x , u x ].
Tỷ lệ co giãn của ánh xạ: g = ux−lx
Giá trị x tương ứng với chuỗi NST nhị phân được tính bằng công thức x = l x + decimal(NST) * g, trong đó decimal(NST) là giá trị thập phân của chuỗi NST Để khởi tạo quần thể, cần tạo ra pop_size NST ngẫu nhiên theo từng bit Sau đó, tiến hành đánh giá từng NST bằng cách tính giá trị hàm f trên các chuỗi nhị phân đã được giải mã, từ đó chọn quần thể mới dựa trên phân bố xác suất theo độ thích nghi Các phép đột biến và lai tạo sẽ được thực hiện để tạo ra các cá thể thế hệ mới Sau một số thế hệ, nếu không có sự cải thiện nào, NST tốt nhất sẽ được coi là giải pháp tối ưu, thường là toàn cục Thuật toán di truyền thường dừng lại sau một số bước lặp cố định, tùy thuộc vào điều kiện về tốc độ hoặc tài nguyên máy tính.
2.6.2 Toán tử chọn lọc a Sử dụng bánh xe Roulette
Có nhiều phương pháp để thực hiện toán tử chọn lọc, trong đó nguyên tắc chính là những cá thể có độ thích nghi cao hơn sẽ có khả năng được chọn nhiều hơn Phương pháp đơn giản và hiệu quả nhất để thực hiện việc này là sử dụng bánh xe Roulette.
Mỗi cá thể trong quần thể chiếm một khe có độ rộng tương ứng với giá trị phù hợp của nó Độ rộng này được xác định dựa trên tỷ lệ phần trăm của giá trị phù hợp của cá thể so với tổng giá trị phù hợp của toàn quần thể.
Giả sử f i là độ phù hợp của cá thể thứ i trong quần thể gồm N cá thể Khi đó, cá thể i sẽ được chọn với xác suất: p i = f i
X i=1 f i b Thủ tục xếp hạng các cá thể
Trong quy trình này, các cá thể được tổ chức dựa trên giá trị của hàm mục tiêu, với cá thể đầu tiên là tốt nhất và cá thể cuối cùng là kém nhất.
Cá thể thứ (N −j) trong dãy có xác suất chọn lựa: p N−j = j
Các bước tiến hành thủ tục là:
Sắp xếp các chuỗi theo thứ tự giảm dần của hàm mục tiêu trong bài toán cực đại, hoặc theo thứ tự tăng dần của hàm mục tiêu trong bài toán cực tiểu.
- Tính độ phù hợp của chuỗi. c Thủ tục chọn lọc cạnh tranh
Trong thủ tục này cách tiến hành như sau:
Chọn ngẫu nhiên t cá thể từ quần thể hiện tại và sau đó xác định cá thể tốt nhất trong số đó để sao chép sang quần thể tạm thời.
- Lặp lại bước trên N lần sẽ được quần thể tạm thời.
Giá trị t khi đó gọi là kích cỡ của chọn lọc cạnh tranh Khi t = 2 ta có chọn lọc cạnh tranh nhị phân.
2.6.3 Toán tử lai ghép a Lai ghép một điểm
Giả sử với hai cá thể cha và mẹ đã được chọn P 1 , P 2 :
Toán tử này thực hiện việc sinh ngẫu nhiên một vị trí k trong khoảng (1 < k < L), sau đó tạo ra hai cá thể con bằng cách tráo đổi các gen của cặp cha mẹ từ điểm cắt đã xác định.
Giả sử điểm cắt đã chọn k = 7, hai con được sinh ra như sau:
Thủ tục lai ghép một điểm:
End; b Lai ghép nhiều điểm
Lai ghép nhiều điểm thực hiện tương tự như lai ghép một điểm, nhưng với hai cá thể cha mẹ P1 và P2 đã chọn, toán tử này cần sinh ngẫu nhiên k vị trí cắt i1, i2, , ik (với giả thiết i1 < i2 < < ik) Các điểm cắt này sẽ chia các cá thể thành các đoạn chẵn và lẻ, từ đó tạo ra hai cá thể con bằng cách tráo đổi các gen của cha mẹ dựa trên vị trí đoạn cắt chẵn hoặc lẻ.
P 1 = (1001110101), P 2 = (0100111110) là hai chuỗi nhị phân độ dài 10, giả sử các điểm cắt đã chọn là 2, 4, 6,
9 khi đó hai con được sinh ra là :
Thủ tục lai ghép được viết tương tự như trên. c Lai ghép mặt nạ
Từ hai cá thể cha mẹ đã chọn P1, P2 và phát sinh một chuỗi nhị phân ngẫu nhiên cũng có độ dài L gọi là chuỗi mặt nạ P 1 = (1010111001),
Các con được tạo ra dựa trên chuỗi mặt nạ này để quyết định lấy thành phần của cá thể cha hay cá thể mẹ dựa trên nguyên tắc:
Gen thứ i của cá thể con C 1 được chọn từ gen thứ i của P 1 khi bit mặt nạ là 1, và từ gen thứ i của P 2 khi bit mặt nạ là 0 Ngược lại, cá thể con C 2 sẽ lấy gen thứ i từ P 2 khi bit mặt nạ là 1 và từ P 1 khi bit mặt nạ là 0.
C 1 = (1010110001), C 2 = (1111011010)Thủ tục lai ghép mặt nạ:
Toán tử đột biến có khả năng thay đổi thông tin trong quần thể ở mức bit (gen) Mỗi bit có xác suất pm để bị đột biến, và tất cả các bit đều có cơ hội đột biến như nhau.
Toán tử đột biến bao gồm: toán tử đột biến chuẩn, đột biến đều và không đều.
If random[0,1] < p m then invert(parent[i]);
Với invert(u) là hàm đảo ngược bít u
Thuật toán GA cổ điển được mô tả một cách tường minh như sau:
{Khởi tạo quần thể gồm m quần thể} t := 0;
While (stopping condition not fulfilled) do
For i := 1 to m do Begin r := random [0,1]; k := 1;
For i := 1 to m−1 step 2 do Begin
If random [0,1] < p c then Begin pos:=random {1, , n−1}; for k :=pos+1 to n do Begin aux := b it+1 [k]; b it+1 [k] := b i+1t+1 [k]; b i+1t+1 [k] := aux;
For i := 1 to m do For k := 1 to n do
If random [0,1] < pm then Invert(b it+1 [k]); t:= t+ 1;
Thuật toán di truyền mã hóa số thực (RCGA)
Bài toán RCGA được định nghĩa là một cặp (S, f), trong đó S là tập con của R n và f là hàm n biến từ S đến R Mục tiêu của bài toán là tìm véc tơ x = (x 1 , x 2 , , x n ) thuộc S sao cho giá trị của hàm f(x) đạt cực tiểu trên S, tức là f(x) phải nhỏ hơn hoặc bằng f(y) với mọi y trong S Hàm f trong bài toán này không liên tục nhưng phải được giới hạn trên tập S.
Trong RCGA, mỗi cá thể được biểu diễn bởi một véc tơ thực n chiều: b = (x1, x2, , xn), xi ∈ R
Như vậy một quần thể kích cỡ m là một tập véc tơ có m véc tơ trong
R n hay có thể xem như một ma trận thực cấp m×n Cách mã hóa này tự nhiên và thuận tiện trong việc thực hiện các toán tử tiến hóa.
2.7.2 Các toán tử của RCGA a Toán tử chọn lọc
Trong RCGA, các phương pháp chọn lọc như chọn lọc tỷ lệ, chọn lọc xếp hạng và chọn lọc cạnh tranh vẫn được áp dụng tương tự như trong GA kinh điển Bên cạnh đó, toán tử lai ghép cũng đóng vai trò quan trọng trong quá trình tối ưu hóa.
RCGA áp dụng các toán tử lai ghép tương tự như GA kinh điển, bao gồm lai ghép một điểm, lai ghép nhiều điểm và lai ghép mặt nạ Bên cạnh đó, với cách mã hóa quần thể, nhiều dạng toán tử lai ghép khác cũng được nghiên cứu và đề xuất Phần này sẽ giới thiệu một số dạng toán tử lai ghép phổ biến, giả thiết rằng cặp cá thể cha mẹ được chọn để thực hiện lai ghép.
Với cặp cha mẹ X và Y là các véc tơ m chiều, toán tử lai ghép sẽ chọn ngẫu nhiên một vị trí k (1 ≤ k ≤ m) và từ đó sinh ra cá thể con theo công thức đã định.
Chọn ngẫu nhiên k điểm j1, , jk (1≤ j1 < j2 < < jk < m)
Lai ghép đa điểm tạo ra cặp (X 0 , Y 0 ) bằng cách đánh số các đoạn [jt, jt+1] từ 0 Cụ thể, x 0 i được xác định là x i tại những đoạn có số hiệu chẵn và y i tại những đoạn có số hiệu lẻ, trong khi y 0 i được tính là x i tại những đoạn có số hiệu lẻ và y i tại những đoạn có số hiệu chẵn.
+ Lai ghép mặt nạ hoặc lai ghép đều
Chọn ngẫu nhiên k vị trí 1 < i 1 < i 2 < < i k < m
Các các thể con X 0 , Y 0 được sinh ra như sau:
+ Lai số học (Arithmetic Crossover)
Các cá thể X 0 và Y 0 được tính bởi: x 0 i = a∗x i + (1−a)∗y i ; y i 0 = a∗y i + (1−a)∗x i ; + Lai ghép Heuristic
Trong quá trình lai ghép giữa cặp cha mẹ (X, Y), nếu cá thể X có độ thích nghi cao hơn cá thể Y, toán tử lai ghép sẽ tạo ra một cá thể con duy nhất X₀ Cụ thể, cá thể con này được xác định theo công thức: x₀ᵢ = r∗(xᵢ − yᵢ) + xᵢ với 0 < r < 1, áp dụng phương pháp lai ghép BLX-α (Blend Crossover).
Với cặp cha mẹ được chọn lai ghép:
Khi đó thành phần thứ i của cá thể con tạo ra là một số ngẫu nhiên chọn trong khoảng [min(x i , y i )−I ∗α,max(x i , y i ) +I ∗α].
Toán tử BLX-α thông qua kết quả thực nghiệm đã khẳng định tính hiệu quả tốt nhất khi giá trị α là 0,5.
+ Lai ghép UNDX (Unimodal Normal Distributed Crossover)
Trong UNDX-m, (m+ 2) cha mẹ được chọn ngẫu nhiên từ quần thể, trong đó (m + 1) cá thể đầu được dùng để tính một véc tơ trung bình.
Cá thể cuối cùng được sử dụng để định hướng cá thể con sẽ sinh ra. Thuật toán được mô tả như sau:
1 Chọn (m+ 1) cá thể cha mẹ x 1 , x 2 , , x m+1 một cách ngẫu nhiên từ quần thể ban đầu.
2 Tính véc tơ trung bình của các cá thể đã chọn : u = 1 m+ 1 m+1
3 Chọn ngẫu nhiên cá thể cha x m+2 từ quần thể.
4 Tính độ dài d của d m+2 = (x m+2 −u) trực giao với d 1 , , d m+1
5 Lấy một cơ sở trực giao e m+2 , , e n của không gian con trực giao với không gian sinh bởi d 1 , , d m+1
6 Sinh ra các con theo công thức: x c1 = u+ m+1
X j=m+2 v j de j trong đó wi và vj là các biến ngẫu nhiên tương ứng với các phân phối chuẩn N(0, σ η 2 ) và N(0, σ ξ 2 ).
Các nhà toán học Kita và Yamamura đã sử dụng thành công với các giá trị σ ξ = 1
√n−m + Lai ghép CMX (Center of Mass Crossover)
Giả sử quần thể đang xét là {X 1 , , X N } Mỗi cá thể là một véc tơ trong R n
Thuật toán được mô tả như sau:
1 Chọn ngẫu nhiên m cá thể từ quần thể (1< m < N)
3 Với mỗi i = 1, , m tính các véc tơ "cha mẹ ảo" X vi đối xứng với
4 Với mỗi cặp X vi và X pi tạo ra một cá thể con X ci bằng cách sử dụng BLX-α.
Như vậy với m cá thể cha mẹ sẽ sinh ra được m cá thể con.
Mô phỏng lai ghép CMX được biểu diễn bởi hình 2.2.
Hình 2.2: Mô phỏng lai ghép CMX
Với cách lai ghép này, các cá thể con sinh ra sẽ phân bố gần với tâm của “đám đông” các cá thể cha mẹ.
+ Lai ghép MFX (Multi-parent Feature-wise Crossover)
Thuật toán này chọn từ mỗi cá thể cha mẹ một tính chất đặc trưng nào đó rồi thực hiện tiến hoá sử dụng thông tin đặc trưng này.
Thuật toán được mô tả như sau:
1 Chọn ngẫu nhiên m cá thể từ quần thể (1< m < N)
2 Cá thể con X ci = x ci 1 , , x ci n được sinh ra như sau:
Đối với mỗi j từ 1 đến n, chọn ngẫu nhiên một số tự nhiên k trong khoảng (1, m) với điều kiện k khác i Tiếp theo, x ci j được tạo ra từ x pi j và x pk j, là số ngẫu nhiên nằm trong khoảng (x pi j −αl, x pk j +αl), trong đó l là khoảng cách giữa x pi j và x pk j.
Hình 2.3: Phân bố của x ci j
Bằng cách cố định một cá thể cha X pi, chúng ta có thể sinh ra một cá thể con X ci tương ứng, trong đó mỗi thành phần của véc tơ được kế thừa thông tin đặc trưng từ cả cá thể cha X pi và cá thể mẹ.
+ Lai ghép SX (Seed Crossover)
Thuật toán này thực hiện quá trình lai ghép đôi giữa một cá thể và cá thể con được sinh ra, sau đó cá thể con này sẽ tiếp tục lai ghép với cá thể cha mẹ, nhằm gia tăng độ thích nghi theo thời gian.
Thuật toán được trình bày như sau:
1 Chọn ngẫu nhiên m cá thể từ quần thể (1< m < N)
2 Xếp hạng các cá thể cha mẹ giảm dần theo độ thích nghi.
4 Cho j chạy từ (m−2) đến 1 thực hiện X c = Blx(X c , X pj ).
Trong đó Blx(X, Y) là toán tử lai ghép hai cha mẹ dạng BLX-α.
Với phương pháp này, mỗi bước lặp, cá thể con được tạo ra có khả năng kế thừa các đặc điểm từ cá thể cha mẹ, đồng thời nâng cao độ thích nghi Toán tử này chỉ tạo ra một cá thể con từ m cá thể cha mẹ đã được chọn.
Hình 2.4: Toán tử lai ghép SX c Toán tử đột biến
Khi một gen i được chọn ngẫu nhiên từ cá thể b (x1, x2, , xN) để thực hiện đột biến, thành phần xi sẽ được thay thế bằng một số ngẫu nhiên nằm trong khoảng xác định [li, ui] của xi.
Từ cá thể cha mẹ đã chọn với đột biến x và vị trí đột biến k, thành phần thứ k (xk) của x sẽ được thay thế bằng l k hoặc u k, trong đó [l k , u k ] là khoảng xác định cho xk.
Trong các bài toán biên của các biến không lớn và giải pháp cần tìm nằm gần biên thì phép đột biến biên tỏ ra rất hữu ích.
Giả sử t max là một số cực đại đã được định nghĩa, ta có thể thay thế thành phần x i bằng một trong hai giá trị theo công thức: x 0 i = x i + ∆(t, b i −x i ) và x 00 i = x i −∆(t, x i −a i ) Việc lựa chọn giá trị nào sẽ được thực hiện dựa trên một giá trị ngẫu nhiên khởi tạo với xác suất 1/2 Biến ngẫu nhiên ∆(t, x) sẽ xác định một bước đột biến trong khoảng [0, x] theo công thức đã cho.
Hàm ∆(t, x) = x∗(1−λ) (1− t max t )τ λ mô tả sự phân bố đột biến, trong đó λ là một số ngẫu nhiên được phân bố đều trong khoảng đơn vị Tham số τ xác định ảnh hưởng của lần sinh thứ t đến phân bố của đột biến trong miền [0, x.].
Thuật toán di truyền với bài toán vận tải cân bằng
2.8.1 Biểu diễn lời giải bài toán vận tải bằng véc tơ
Một lời giải (một NST) được biểu diễn dưới dạng véc tơ bit < v1, v2, , vp > với p = n × k Mỗi thành phần v i (với i = 1, 2, , p) là một véc tơ bit < w 0 i , , w i s >, thể hiện một số nguyên liên quan đến hàng j và cột m trong ma trận phân phối, trong đó j = [(i−1) k + 1] và m = (i−1) mod k + 1.
Chiều dài véc tơ w (tham số f) xác định số nguyên lớn nhất (2 s+1 −1) cần thiết để biểu diễn một lời giải Mỗi véc tơ lời giải cần phải đáp ứng các ràng buộc cụ thể, bao gồm ck+k.
Chú ý 2.1 Ràng buộc cuối cùng luôn được thỏa mãn (1 chuỗi các số
Hàm lượng giá là tổng chi phí vận tải từ các nguồn đến các đích, với hai ràng buộc đầu tiên thể hiện tổng cung bằng tổng cầu tại mỗi nguồn và đích, mặc dù các công thức này không đối xứng.
Đột biến trong các toán tử di truyền được hiểu là sự thay đổi của một bit trong véc tơ lời giải, tương ứng với sự thay đổi của giá trị nguyên v i trong bài toán vận tải Sự đột biến này có thể dẫn đến chuỗi thay đổi ở các điểm khác nhau nhằm duy trì các ràng buộc Do đó, cần ghi nhớ những thay đổi đã xảy ra ở cột và hàng tương ứng (các nguồn và các đích), điều này làm cho công thức trở nên phức tạp và mất tính đối xứng trong việc diễn tả các ràng buộc.
Giả sử 2 điểm ngẫu nhiên v i và v m (với i < m) được chọn sao cho chúng thuộc cùng một hàng hay cột.
Giả sử v i , v j , v k , v m (với i < j < k < m) là những thành phần của véc tơ lời giải (được chọn để đột biến) sao cho v i và v j cũng như v k , v m thuộc cùng 1 hàng.
Tức là trong biểu diễn ma trận ta có:
Với cách phân tích này thì gặp phải khó khăn khi xác định sự thay đổi cần thiết trong véc tơ lời giải, ta nên tăng hay giảm v i ?
Chúng ta có thể điều chỉnh giá trị của một hoặc nhiều phần tử trong khoảng (0, 1, , vi) Khi tăng giá trị vi lên một hằng số C, ta cần giảm các giá trị vj và vk tương ứng với cùng một hằng số Nếu vj hoặc vk nhỏ hơn C, ta có thể chọn C = min(vi, vj, vk) Phương pháp này sẽ giúp phần lớn các đột biến không thay đổi kết quả, vì xác suất để chọn ba phần tử cùng lúc gần như bằng 0 (nhỏ hơn 1/n đối với các véc tơ có kích thước n^2).
Phương pháp thay đổi 1 bít làm giảm hiệu quả của các toán tử đột biến do yêu cầu biểu thức phức tạp để kiểm soát hàng hoặc cột của phần tử được chọn Do đó, việc biểu diễn véc tơ nhị phân không phải là phương pháp tối ưu để định nghĩa các toán tử di truyền trong những bài toán ràng buộc khác Cần tìm kiếm cách biểu diễn lời giải mà vẫn giữ nguyên cấu trúc cơ bản của véc tơ, đồng thời kết hợp tri thức của bài toán vào trong biểu diễn này.
Thủ tục Khởi tạo là thành phần quan trọng trong toán tử đột biến của các toán tử di truyền trong cấu trúc 2 chiều, có nhiệm vụ tạo ra một ma trận với tối đa (k+n−1) phần tử khác 0, đảm bảo tất cả các ràng buộc được thỏa mãn.
+ Output: Mảng (v)ij sao cho vij ≥ 0 với ∀i, j
L ← {1,2, , k×n}: là danh sách các điểm chưa được xét đến; Lặp:
1 Chọn 1 số ngẫu nhiên q trong L;
2 q được gọi là điểm đã xét;
Hết lặp nếu (tất cả các điểm trong L đều đã được thăm);
Ví dụ 2.1 Xét bài toán vận tải có 3 nguồn và 4 đích với các tham số:
Có tất cả 3×4 = 12 số đều được thăm từ đầu Chọn số ngẫu nhiên đầu tiên chẳng hạn là 10 với số này tính được.
Ta lặp lại cách tính này với 3 số (chưa thăm) ngẫu nhiên, ví như 8,
(D[3] = D[3]−15 = 15−15 = 0); D = (0,10,0,0) Khi đó ta có bảng kết quả sau đây:
Sau 4 lần lặp, các giá trị S[i] và D[i] được xác định Khi thêm các số ngẫu nhiên như 1, 11, 4, 12, 7, 6, 9, 2, ta có thể tính toán được ma trận cuối cùng dựa trên chuỗi số ngẫu nhiên được chấp nhận là (10, 8, 5, 3, 1).
Sau 12 lần lặp, S[i] và D[j] sẽ bằng 0 Cần lưu ý rằng có nhiều chuỗi số mà quy trình khởi tạo có thể tạo ra giải pháp tối ưu Ví dụ, giải pháp tối ưu trong trường hợp này có thể đạt được với bất kỳ chuỗi nào như < 7,9,4,2,6,∗,∗,∗,∗,∗,∗,∗ >, trong đó dấu sao (*) đại diện cho các số chưa được khám phá.
Kỹ thuật này có khả năng tạo ra một lời giải khả thi với tối đa (k+n−1) phần tử nguyên khác 0 Tuy nhiên, nó sẽ không phát sinh các lời giải khả thi khác mà không sử dụng đặc trưng này, do đó cần điều chỉnh thủ tục khởi tạo khi giải bài toán vận tải phi tuyến.
Dựa trên kiến thức và lời giải của bài toán, chúng ta có thể biểu diễn lời giải của bài toán vận tải thông qua một véc tơ Véc tơ này gồm một chuỗi các số nguyên phân biệt k × n trong khoảng (1, k × n), và theo quy trình khởi tạo, nó sẽ tạo ra một lời giải khả thi Nói cách khác, véc tơ lời giải được coi là một hoán vị của các số, cho phép chúng ta tìm ra các hoán vị cụ thể tương ứng với lời giải tối ưu.
Tiếp theo, chúng ta sẽ xem xét cách cài đặt biểu diễn này để đảm bảo thỏa mãn các ràng buộc, hàm lượng giá và các toán tử di truyền Việc thỏa mãn các ràng buộc là một yếu tố quan trọng trong quá trình tối ưu hóa, giúp đảm bảo rằng các giải pháp tìm được không chỉ hợp lệ mà còn hiệu quả trong việc đáp ứng các yêu cầu đề ra.
Mỗi hoán vị của k × n số phân biệt sẽ tạo ra một lời giải duy nhất đáp ứng tất cả các ràng buộc, điều này được đảm bảo nhờ vào quy trình khởi tạo.
Hoán vị nào cũng tương ứng với một ma trận duy nhất như (v ij ), hàm lượng giá là: n
V ij ∗C[i, j] c Các toán tử di truyền:
+ Đảo: Nếu (x 1 , x 2 , , x q ) với q = k×n là một lời giải thì véc tơ đảo
51 của nó (x q , x q−1 , , x 1 ) cũng là 1 lời giải.
Đột biến là quá trình hoán vị bất kỳ hai phần tử trong véc tơ lời giải (x₁, x₂, , xq), chẳng hạn như xᵢ và xⱼ, để tạo ra một véc tơ kết quả cũng được coi là một lời giải hợp lệ.
Khi sử dụng toán tử lai ngẫu nhiên, chúng ta cần lưu ý rằng nó có thể tạo ra các lời giải không hợp lệ, chẳng hạn như khi áp dụng vào các chuỗi.
8> sẽ sinh ra (điểm lai tạo là ở sau vị trí thứ 6) các lời giải
< 1,2,3,4,5,6,5,2,10,9,6,8 > và < 7,3,1,11,4,12,7,8,9,10, 11,12 > cả 2 chuỗi này đều là các lời giải không hợp lệ.
Nhận xét 2.2 Như vậy, phải dùng tới một toán tử lai Heuristie mà khi cho 1 cặp cha mẹ, sẽ tạo một con hợp lệ theo thủ tục sau:
1 Tạo bản sao của phần tử thứ hai trong cặp cha – mẹ đã cho.
2 Chọn một phần ngẫu nhiên từ phần tử thứ nhất trong cặp cha – mẹ đó.
3 Tạo những thay đổi tối thiểu cần thiết ở con để có được lời giải hợp lệ.
3 Tạo những thay đổi tối thiểu cần thiết ở con để có được lời giải hợp lệ.
Ví dụ 2.2 Với cặp cha – mẹ (∗) đã xét ở ví dụ trên, phần được chọn là (4,5,6,7) thì con có được là < 3,1,11,4,5,6,7,12,2,10,9,8 >.