Tài liệu Nghiên cứu giải thuật seamo, ứng dụng xây dựng modul hỗ trợ người dùng cấu hình máy tính

LỜI CẢM ƠN Sau một thời gian học tập và nghiên cứu, em đã hoàn thành đồ án tốt nghiệp với đề tài: “Nghiên cứu giải thuật SEAMO, ứng dụng xây dựng modul hỗ trợ người dùng cấu hình máy tính”. Trước tiên em xin bày tỏ lòng kính trọng và biết ơn chân thành đến cô giáo ThS. Dương Thị Mai Thương là người trực tiếp hướng dẫn đã tận tình chỉ bảo cũng như tạo điều kiện giúp đỡ em để hoàn thành đồ án tốt nghiệp. Qua thời gian được thầy hướng dẫn, em đã học hỏi được nhiều kiến thức bổ ích và kinh nghiệm quý báu làm nền tảng cho quá trình học tập, làm việc và nghiên cứu sau này. Em cũng xin chân thành cảm ơn các thầy cô giáo giảng dạy tại bộ môn Khoa học máy tính và các thầy cô giáo giảng dạy tại Khoa công nghệ thông tin – Trường ĐH Công nghệ thông tin và truyền thông – ĐH Thái Nguyên trong suốt thời gian 5 năm học tập tại trường đã trang bị cho em những kiến thức cơ bản cần thiết và bổ ích giúp em hoàn thành đồ án tốt nghiệp. Với vốn kiến thức được tiếp thu trong quá trình học không chỉ là nền tảng cho quá trình nghiên cứu thực tâp mà còn là hành trang quí báu để em phát triển các công việc thực tiễn trong tương lai. Cuối cùng em kính chúc quý Thầy, Cô dồi dào sức khỏe và thành công trong sự nghiệp cao quý. Đồ án tuy hoàn thành nhưng không tránh khỏi nhiều thiếu sót và những vấn đề chưa xử lý được. Em rất mong nhận được sự thông cảm và chỉ bảo tận tình của quý Thầy cô và các bạn. Thái nguyên, ngày... tháng 06 năm 2016 Sinh viên Nguyễn Thế Toàn 1 LỜI CAM ĐOAN Để hoàn thành đồ án tốt nghiệp đúng quy định và đáp ứng được nhu cầu đề ra, bản thân em đã cố gắng nghiên cứu, học tập và làm việc trong thời gian dài cùng với sự hướng dẫn nhiệt tình của cô giáo Th.s Dương Thị Mai Thương và các thầy cô giáo khoa công nghệ thông tin. Em đã tham khảo một số tài liệu nêu trong phần “Tài liệu tham khảo” và không sao chép nội dung từ bất kỳ đồ án nào khác. Em xin cam đoan những lời nói trên là hoàn toàn đúng sự thật, mọi thông tin sai lệch em xin hoàn toàn chịu trách nhiện trước hội đồng. Thái nguyên, ngày… tháng 06 năm 2016 Sinh viên Nguyễn Thế Toàn 2 MỤC LỤC LỜI CẢM ƠN .....................................................................................................1 LỜI CAM ĐOAN................................................................................................2 MỤC LỤC ..........................................................................................................3 DANH MỤC HÌNH ẢNH ...................................................................................5 MỞ ĐẦU ............................................................................................................6 CHƯƠNG 1: TỔNG QUAN VỀ TỐI ƯU ĐA MỤC TIÊU .................................8 1.1. Giới thiệu bài toán tối ưu đa mục tiêu .......................................................8 1.1.1. Mô hình bài toán tối ưu đa mục tiêu có ràng buộc .............................9 1.1.2. Khái niệm tối ưu Pareto.....................................................................9 1.1.3. Khái niệm trội Pareto ........................................................................9 1.1.4. Tập các lời giải tối ưu Pareto...........................................................10 1.2. Bài toán cái túi (Knapsack).....................................................................11 1.2.1. Bài cái túi dạng 0-1 .........................................................................11 1.2.2. Bài toán cái túi bị chặn ....................................................................11 1.2.3. Bài toán cái túi không bị chặn .........................................................12 1.3. Bài toán cái túi đa mục tiêu ....................................................................12 1.4. Mô hình bài toán cái túi đa mục tiêu .......................................................15 1.4.1. Mô hình mã nhị phân.......................................................................15 1.4.2. Mô hình mã hóa hoán vị ..................................................................16 1.4.3. Một số ví dụ mã hóa đối với bài toán cái túi đa mục tiêu .................17 CHƯƠNG 2: GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU .................................................................................................................19 2.1. Giới thiệu về giải thuật di truyền ............................................................19 2.1.1. Các nguyên tắc căn bản của giải thuật di truyền ..............................19 2.1.2. Các vấn đề chính trong tìm kiếm đa mục tiêu ..................................21 2.1.3. Mô hình tổng quát giải thuật di truyền.............................................22 2.2. Một số thuật toán thường được áp dụng giải bài toán tối ưu đa mục tiêu.23 2.2.1. Thuật toán MOGA ..........................................................................23 2.2.2. Thuật toán VEGA............................................................................25 3 2.2.3. Thuật toán SEAMO, SEAMO2 .......................................................26 2.2.4. Thuật toán NSGA, NSGA II............................................................30 2.2.5. Thuật toán SPEA, SPEA 2 ..............................................................36 CHƯƠNG 3: XÂY DỰNG GIẢI PHÁP HỖ TRỢ NGƯỜI DÙNG CẤU HÌNH MÁY TÍNH.......................................................................................................40 3.1 Máy tính số..............................................................................................40 3.2 Phân loại theo nhu cầu.............................................................................44 3.2.1 Phân loại theo cấu hình.....................................................................44 3.2.2 Phân loại người sử dụng theo thương hiệu:.......................................44 3.2.3 Phân loại người sử dụng theo hình thức:...........................................45 3.3 Cài đặt thuật toán SEAMO2 ....................................................................47 3.3.1 Thuật toán SEAMO2........................................................................47 3.3.2. Dữ liệu của bài toán.........................................................................47 3.3.3. Mô hình và các toán tử cho bài toán máy tính 0-1 đa mục tiêu.........49 KẾT LUẬN.......................................................................................................52 HƯỚNG PHÁT TRIỂN ....................................................................................53 TÀI LIỆU THAM KHẢO .................................................................................54 4 DANH MỤC HÌNH ẢNH Hình 2.1 Mối liên hệ giữa không gian cá thể, vectơ quyết định và mục tiêu.......21 Hình 2.2: Mô hình tổng quát giải thuật di truyền ...............................................23 Hình 2.3: Minh họa thuật toán MOGA ..............................................................25 Hình 2.4:Minh họa biên chứa các nghiệm không trội và thứ hạng tương ứng.....30 Hình 2.5: Minh họa khoảng cách quy tụ quanh nghiệm i ...................................34 Hình 2.6: Minh họa các biên và thứ hạng...........................................................34 Hình 2.7: Minh họa sự quy tụ của các nghiệm quanh một nghiệm .....................35 Hình 2.8: Minh họa tính toán độ thích nghi của các cá thể.................................38 Hình 2.9: Minh họa cách xóa bỏ các nghiệm nào có δk nhỏ nhất.....................39 Hình 3.1: kết quả thu được với bộ dữ liệu 750 thiết bị với kích thước 250 .........50 Hình 3.2: kết quả thu được với bộ dữ liệu 500 thiết bị với kích thước 250 .........50 Hình 3.3: kết quả thu được với bộ dữ liệu 100 thiết bị với kích thước 100 .........51 5 MỞ ĐẦU 1. Lý do chọn đề tài: Trên thực tế, tồn tại rất nhiều bài toán yêu cầu tối ưu hóa đồng thời nhiều mục tiêu (thường là cạnh tranh lẫn nhau) ví dụ như: định tuyến các phương tiện giao thông để xác định các tuyến đường tối ưu nhằm cung cấp dịch vụ cho một tập hợp các khách hàng có thể liên quan đến một số mục tiêu khác nhau: tổng quãng đường đi (hoặc thời gian thực hiện), lượng xe sử dụng, độ hài lòng của khách hàng (giao hàng trong khoảng thời gian đã thỏa thuận trước), … hay việc đi mua máy tính đảm bảo sao cho đáp ứng được yêu cầu cấu hình, thẩm mỹ, thương hiệu với số tiền chi tiêu không vượt quá giới hạn, … Giải thuật di truyền (GA) là một trong những mô hình tính toán phổ biến và thành công nhất trong lĩnh vực tính toán thông minh. Cùng với các kỹ thuật tính toán thông minh khác như tính toán mờ (fuzzy computing), mạng Nơ-ron (neural networks), hệ đa tác tử (multi- agent systems), trí tuệ bầy đàn (swarm intelligence), giải thuật di truyền ngày càng phát triển, được áp dụng rộng rãi trong các lĩnh vực của cuộc sống. Đối với bài toán đa mục tiêu, đã có nhiều phương pháp nghiên cứu đề xuất ra các thuật toán để giải quyết bài toán như: MOGA, NSGA2, SPEA2, SEAMO2, … trong đó giải thuật SEAMO2 là hiệu quả hơn cả . Với giải thuật SEAMO2, việc thay thế cá thể vào quần thể (thực hiện chiến lược chọn lọc tự nhiên) thì độ hội tụ về tập nghiệm tối ưu (với lần chạy ngắn) là chưa cao và khi quần thể nghiệm đã đạt ngưỡng tối ưu (với lần chạy dài) thì sẽ mất nhiều thời gian để loại cá thể không phù hợp. Chính vì vậy, tác giả mạnh dạn nghiên cứu phương pháp cải tiến chiến lược chọn lọc tự nhiên trong giải thuật SEAMO2 để giải các bài toán tối ưu đa mục tiêu trong luận văn: “Nghiên cứu giải thuật SEAMO, ứng dụng xây dựng modul hỗ trợ người dùng cấu hình máy tính”. 2. Mục đích nghiên cứu Mục tiêu của đồ án là nghiên cứu các toán tử trong giải thuật di truyền (hay giải thuật tiến hóa nói chung) đặc biệt là toán tử chọn lọc tự nhiên để chọn lọc và thay thế các lời giải nhằm tối ưu tập lời giải thu được giúp cho giải thuật di truyền giải quyết hiệu quả các bài toán tối ưu đa mục tiêu. Mục đích cụ thể của 6 đồ án là sử dụng các toán tử di truyền khác nhau đối với thuật toán SEAMO2, ứng dụng cho bài toán máy tính đa mục tiêu, thay đổi chiến lược chọn lọc tự nhiên của thuật toán nhằm cải tiến thuật toán. Phương pháp này sẽ được so sánh với kết quả của các thuật toán tối ưu đa mục tiêu khác như: SPEA2, NSGA2. Do đó mục tiêu của đồ án là: Nghiên cứu giải thuật di truyền cho bài toán đa mục tiêu. 3. Nhiệm vụ nghiên cứu Nghiên cứu các mô hình của giải thuật di truyền có áp dụng các nguyên lý tiến hóa và trên cơ sở đó tiếp cận các ý tưởng từ thuật toán di truyền để giải bài toán máy tính đa mục tiêu như: NSGA2, SPEA2, SEAMO2, cách thức tìm nghiệm của các thuật toán này để cải thiện cải tiến thuật toán di truyền có áp dụng nguyên lý tiến hóa SEAMO2. 4. Đối tượng và phạm vi nghiên cứu Tìm hiểu về bài toán tối ưu đa mục tiêu, bài toán máy tính 0-1 đa mục tiêu. Tìm hiểu về giải thuật tiến hóa, các mô hình giải thuật tiến hóa có thể áp dụng cho bài toán máy tính 0 - 1 đa mục tiêu. Xây dựng ứng dụng giải bài toán máy tính 0 - 1 đa mục tiêu với giải thuật SEAMO2 và đề xuất phương pháp cải tiến giải thuật. So sánh kết quả thực nghiệm của phương pháp đề xuất với các kết quả của các thuật toán khác. 5. Phương pháp nghiên cứu Dựa trên tài liệu thu thập từ nhiều nguồn (tài liệu, bài báo do giảng viên hướng dẫn cung cấp, sách, báo, tạp chí, internet…) tổng hợp, phân tích và trình bày lại theo sự hiểu biết của bản thân. Mở rộng các cách tiếp cận trước đây trên cơ sở phân tích đặc thù giải thuật, bài toán cần giải quyết để đưa ra những ý kiến, đề xuất cải tiến hợp lý. Ứng dụng những kết quả dựa trên nghiên cứu để xây dựng chương trình thực nghiệm, từ đó so sánh với kết quả của các thuật toán tối ưu đa mục tiêu khác. 7 CHƯƠNG 1: TỔNG QUAN VỀ TỐI ƯU ĐA MỤC TIÊU 1.1. Giới thiệu bài toán tối ưu đa mục tiêu Tối ưu đa mục tiêu (multiobjective optimization) hay cũng còn gọi là tối ưu đa tiêu chuẩn (multicriteria optimization), tối ưu đa nhiệm (multiperformance optimization) hay tối ưu vectơ (vector optimization) có thể được định nghĩa như là một bài toán tìm kiếm vectơ của các biến quyết định mà nó thỏa mãn các ràng buộc và tối ưu hóa một hàm vectơ mà các thành phần của nó biểu diễn các hàm mục tiêu thông thường đối nghịch lẫn nhau. Vì vậy thuật ngữ tối ưu có nghĩa là tìm kiếm một lời giải mà nó cho các giá trị của các hàm mục tiêu có thể chấp nhận được đối với người thiết kế. Chúng ta gọi các đại lượng số mà các giá trị của nó được chọn cho bài toán tối ưu hóa là các biến quyết định, ký hiệu là xi (i=1,…,n). Vectơ x của n biến lấy quyết định được biểu diễn như sau: =(x1,…,xn) Trong mỗi bài toán tối ưu đa mục tiêu luôn luôn có các hạn chế được đặt ra bởi các đặc trưng đặc biệt của môi trường hay các tài nguyên có sẵn. Các hạn chế này phải được thỏa mãn trong việc xem xét lời giải nào đó có thể chấp nhận được. Tổng quát, chúng ta gọi các hạn chế này là các ràng buộc, chúng mô tả sự phụ thuộc giữa các biến lấy quyết định và các hằng số (hay các tham số) trong bài toán. Các ràng buộc thường được biểu diễn dưới dạng bất đẳng thức toán học như sau: hk≤0 k=1,…,r Để biết một lời giải nào đó tốt như thế nào chúng ta cần phải có một số tiêu chuẩn để đánh giá nó. Các tiêu chuẩn này được biểu diễn như là các hàm toán học theo các biến quyết định, chúng được gọi là các hàm mục tiêu. Trong các hàm mục tiêu đó, một số hàm này đối nghịch với một số hàm khác, và một số mục tiêu thì được cực tiểu hóa trong khi các mục tiêu khác thì được cực đại hóa. Các hàm mục tiêu này có thể so sánh được với nhau, nghĩa là chúng được đo lường trong các đơn vị giống nhau, hay không so sánh được với nhau, nghĩa là chúng được đo lường trong các đơn vị khác nhau. 8 1.1.1. Mô hình bài toán tối ưu đa mục tiêu có ràng buộc Chúng ta xét một mô hình tối ưu đa mục tiêu có ràng buộc gồm có p hàm mục tiêu fi(x) (i=1, …, p) và r hàm (có thể phi tuyến) ràng buộc hk(x) (k=1, …, r) với x=(x1, …, xn) là biến quyết định n chiều được định nghĩa theo mô hình sau Max[fi(x1, …, xn)] (i=1, …, p) sao cho hk(x1, …, xn) ≤ ak (k=1, …, r) Chúng ta có một vectơ x* sao cho fi(x*) ≥ fi(x) (i=1, …, p) với tất cả x lời giải khả thi. Nếu trường hợp này xảy ra, x* được gọi là lời giải mong ước (desirable solution) hay lời giải lý tưởng (ideal solution), điều này có nghĩa là tất cả các fi(x) đều có cực đại trong Yf tại một điểm chung x*. Nhưng chúng ta thường không có được lời giải lý tưởng này, nên chúng ta phải thiết lập một tiêu chuẩn để xác định cái gì sẽ được xem là lời giải tối ưu. Trong đồ án này, chúng ta chỉ xem xét tiêu chuẩn tối ưu theo khái niệm tối ưu Pareto. 1.1.2. Khái niệm tối ưu Pareto Khái niệm tối ưu Pareto được giới thiệu bởi Vilfredo Pareto vào năm 1896, và nó tạo thành cơ sở cho việc nghiên cứu trong lĩnh vực này. Ta có định nghĩa như sau : Gọi O(x) = ( f1(x), …, fp(x),g1(x), …, gq(x)) là hàm vectơ p+q chiều. Gọi Xf là tập lời giải khả thi của mô hình trên, nghĩa là tập các vectơ x thỏa mãn các điều kiện ràng buộc. 1.1.3. Khái niệm trội Pareto Gọi x, y Xf là hai lời giải khả thi. Ta nói x trội hơn y nếu và chỉ nếu O(x) tốt hơn O(y), nghĩa là : fi(x) ≥ fi(y) (i=1, …, p) và gj(x)≤gj(y) (j=1, …, q) 9 và i {1, …, p}: fi(x) ≥ fi(y) hay ∃j ∈{1, …, q}: gj(x)≤gj(y) 1.1.4. Tập các lời giải tối ưu Pareto Khái niệm: Gọi Xd={x ∈ Xf / ∃ y ∈ Xf sao cho O(y) tốt hơn O(x)} là tập các lời giải khả thi bị trội của Xf . Khi đó Xp=Xf\Xd là tập các lời giải khả thi không bị trội của Xf hay còn gọi là tập các lời giải tối ưu Pareto của Xf. Tuy nhiên, điểm tối ưu Pareto hầu như luôn luôn không duy nhất, mà có đến một tập các điểm tối ưu Pareto thường được gọi là tập các lời giải không bị trội (nondominated). Thông thường một lớp bài toán tối ưu đa mục tiêu trong thiết kế kỹ thuật có một tập tối ưu Pareto, và các bài toán đó lại có một số lượng lớn các lời giải có khả năng để chọn lựa, và điều này gây khó khăn ở 2 điểm: một là việc phát sinh ra tập lời giải, hai là việc xử lý các kết quả. Toàn bộ các lời giải tối ưu Pareto được gọi là tập tối ưu Pareto, các vectơ mục tiêu tương ứng thành lập một biên (front) Pareto hay mặt (surface) Pareto. Trong hầu hết các trường hợp, sẽ có nhiều lời giải tối ưu khác nhau theo nghĩa Pareto khi đó ta sẽ phải tìm kiếm các giá trị của các hàm mục tiêu để quyết định giá trị nào của chúng là thích hợp nhất gọi là quá trình lấy quyết định. Nếu ta biết trước được tầm quan trọng tương đối của mỗi hàm mục tiêu thì quá trình lấy quyết định sẽ đơn giản. Tuy nhiên, trong nhiều trường hợp ta không biết tầm quan trọng tương đối của mỗi hàm mục tiêu vì nó không đầy đủ hay không thể biểu diễn một cách hình thức hóa đầy đủ, nên các phương pháp này thường không được áp dụng trong thực tế. Một cách tổng quát, ta không dễ dàng tìm được một biểu diễn giải tích cho các đường hay các mặt chứa các điểm tối ưu Pareto và các thủ tục chuẩn để tính toán các điểm trong Xf cho các điểm tương ứng của nó trong Yf. Tuy nhiên, khi ta có một số lượng tương đối đầy đủ các điểm này thì ta có thể tiến hành lấy quyết định cuối cùng. 10 1.2. Bài toán cái túi (Knapsack) Bài toán cái túi là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Martello và Toth xây dựng bài toán cái túi đơn mục tiêu là một tập hợp n đồ vật và một cái túi. Mỗi mục tiêu có một trọng lượng wi và một giá trị pi với mục tiêu là tìm một tập con của n đồ vật sao cho tối đa giá trị các đồ vật mà không vượt quá giới hạn khối lượng của cái túi. Nội dung bài toán : Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Vậy kẻ trộm nên bỏ vào túi những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được. Các bài toán tương tự thường xuất hiện trong kinh doanh, toán tổ hợp, lý thuyết độ phức tạp tính toán, mật mã học và toán ứng dụng. 1.2.1. Bài cái túi dạng 0-1 Hạn chế số đồ vật thuộc mỗi loại là 0 (không được chọn) và 1 (được chọn). Bài toán cái túi 0-1 có thể được phát biểu bằng toán học như sau: Cực đại hóa: sao cho 1.2.2. Bài toán cái túi bị chặn Hạn chế số đồ vật thuộc mỗi loại không được vượt quá một lượng nào đó. Bài toán cái túi bị chặn có thể được phát biểu bằng toán học như sau: Cực đại hóa 11 sao cho 1.2.3. Bài toán cái túi không bị chặn Không có một hạn chế nào về số lượng đồ vật mỗi loại. Một trường hợp đặc biệt của bài toán này nhận được nhiều quan tâm, đó là bài toán với các tính chất:  là một bài toán quyết định  là một bài toán 0-1  với mỗi đồ vật, chi phí bằng giá trị: C = V Bài toán cái túi thường được giải bằng quy hoạch động, tuy chưa có một thuật toán thời gian đa thức cho bài toán tổng quát. Cả bài toán cái túi tổng quát và bài toán tổng con đều là các bài NP-khó, và điều này dẫn đến các cố gắng sử dụng tổng con làm cơ sở cho các hệ thống mật mã hóa khóa công khai, chẳng hạn Merkle-Hellman. Các cố gắng này thường dùng nhóm thay vì các số nguyên. Merkle-Hellman và một số thuật toán tương tự khác đã bị phá, do các bài toán tổng con cụ thể mà họ tạo ra thực ra lại giải được bằng các thuật toán thời gian đa thức. 1.3. Bài toán cái túi đa mục tiêu Martello và Toth cũng định nghĩa bài toán bái túi đa mục tiêu trong đó bao gồm n đồ vật và m cái túi, mỗi cái túi có một giới hạn trọng lượng cj. Bài toán cái túi đa mục tiêu (MKP) là bài toán tổng quát hóa của bài toán cái túi dạng đơn giản. Ở dạng này, một tập hợp các đồ vật được lựa chọn sao cho thỏa mãn tối đa một tập các ràng buộc của ba lô. Bài toán có thể phát biểu bằng toán học như sau: Cực đại hóa 12 sao cho Trong đó : n là số đồ vật với giá trị pj>0 và m ba lô với sức chứa ci>0, mỗi đồ vật j sẽ có trọng lượng wi,j ≥ 0 từ mỗi ba lô i, {0,1} để chỉ ra đồ vật xj được chọn hay không được chọn. Mục tiêu của bài toán là để chọn một tập con các đồ vật sao cho có giá trị đối đa. Các đồ vật được lựa chọn phải không vượt quá khả năng của ba lô tương ứng. Tuy nhiên, đề xuất trên đã không được sử dụng rộng rãi cho đến khi Zitzler and Thiel đề xuất mô hình mới cho bài toán cái túi đa mục tiêu, mô hình được mô tả bởi Zitzler and Thielelà mô hình đa mục tiêu được mở rộng từ mô hình đơn mục tiêu của Martello và Toth. Từ đó, bài toán này đã được sử dụng rộng rãi như là một bài toán chuẩn để đánh giá hiệu suất không chỉ cho các thuật toán tiến hóa đa mục tiêu mà còn cho các thuật toán tìm kiếm khác. Mô hình dạng 0-1 được xác định như sau: Cho một tập hợp n đồ vật và m cái túi, trọng lượng và giá trị của mỗi đồ vật tương ứng với mỗi túi là khác nhau và bị ràng buộc bởi khả năng có thể chứa của mỗi cái túi. Mục tiêu của bài toán là tìm một tập hợp các đồ vật sao cho giá trị ở mỗi túi là tối đa và có trọng lượng không vượt quá khả năng của mỗi túi. pi,j – giá trị của đồ vật j trong túi i wi,j – trọng lượng của đồ vật j trong túi i ci – thể tích của túi i tìm vector sao cho: Và tối đa hàm khi: 13 và nếu và chỉ nếu đồ vật j được chọn, ngược lại . Ở bài toán cái túi đa mục tiêu, ta phải giải quyết các vấn đề sau :  Chọn các đồ vật vào tất cả cái túi có thể.  Mỗi cái túi có thể tích khác nhau.  Mỗi đồ vật có thể có trọng lượng và giá trị khác nhau đối với mỗi cái túi 14 1.4. Mô hình bài toán cái túi đa mục tiêu 1.4.1. Mô hình mã nhị phân Mô hình mã nhị phân là mô hình phổ biến nhất, các công trình đầu tiên về giải thuật di truyền thường sử dụng mô hình này. Trong mô hình mã nhị phân, mỗi cá thể là một chuỗi các bits có giá trị là 0 hoặc 1. Mô hình mã nhị phân cho nhiều cá thể tốt ngay cả với quần thể số lượng nhỏ. Nhưng mặt khác mô hình này thường là không tự nhiên đối với một số bài toán và đôi khi chúng ta phải sửa chữa các cá thể thu được sau khi lai ghép hoặc đột biến. Cá thể A 101100101100101011100101 Cá thể B 111111100000110000011111 Đối với mô hình này ta có thể sử dụng các phép lai ghép: Single point crossover: Ta chọn một điểm ngẫu nhiên làm điểm lai phép, chuỗi nhị phân từ đầu đến điểm lai ghép sẽ được sao chép từ cá thể cha mẹ đầu tiên, phần còn lại được sao chép từ cá thể cha mẹ còn lại. 11001011+11011111 = 11001111 Two point crossover: Ta chọn hai điểm lai ghép, chuỗi nhị phân từ đầu đến điểm lai ghép đầu tiên được sao chép từ cá thể cha mẹ đầu tiên, phần từ điểm lai ghép đầu tiên đến điểm lai ghép thứ hai được sao chép từ cá thể cha mẹ còn lại, phần còn lại được sao chép từ cá thể cha mẹ đầu tiên. 11001011 + 11011111 = 11011111 Uniform crossover: mỗi bit sẽ được sao chép ngẫu nhiên từ cá thể cha hoặc mẹ 11001011 + 11011101 = 11011111 Arithmetic crossover: Một số phép toán số học trên bit sẽ được áp dụng để tạo ra cá thể con mới. 11001011 + 11011111 = 11001001 (AND) Mô hình này áp dụng phép đột biến là Bit inversion, các bit được chọn sẽ được ngẫu nhiên đảo ngược. 11001001 => 10001001 15 1.4.2. Mô hình mã hóa hoán vị Trong mô hình mã hóa hoán vị mỗi cá thể là một chuỗi các con số, đại diện cho số trong một chuỗi nào đó. Cá thể A 1 5 3 2 6 4 7 9 8 Cá thể B 8 5 6 7 2 3 1 4 9 Các phép lai ghép có thể áp dụng: Single point crossover: một điểm lai ghép sẽ được chọn, từ đầu đến điểm lai ghép này ta sao chép từ cá thể cha mẹđầu tiên sau đó cá thể cha mẹ còn lại sẽ được kiểm tra, nếu số được kiểm tra chưa có trong cá thể con thì thêm số đó vào cá thể con (1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7) Cycle crossover: Ở phép lai ghép này, mỗi vị trí của cá thể con sẽ là kết quả của việc lấy giá trị từ vị trí tương tự của cá thể cha mẹ. (8 7 6 4 1 2 5 3 9 10) + (2 5 1 7 3 8 4 6 10 9) =(2 5 6 7 1 8 4 3 10 9) Các phép đột biến có thể áp dụng: Displacement Mutation: Chọn hai điểm ngẫu nhiên, lấy các gen giữa chúng, sau đó đưa các gen đó vào một vị trí ngẫu nhiên (0 1 2 3 4 5 6 7) =(0 3 4 5 1 2 6 7) Insertion Mutation: Đây là phương pháp đột biến rất hiệu quả, nó tương tự như Displacement Mutation, điểm khác biệt là chỉ có một gen được chọn. Trong các thử nghiệm thì phương pháp đột biến này luôn có kết quả tốt hơn các phương pháp đột biến còn lại. (0 1 2 3 4 5 6 7) = (0 1 3 4 5 2 6 7) Inversion Mutation: Chọn hai điểm ngẫu nhiên và đảo ngược các gen giữa chúng (0 1 2 3 4 5 6 7) = (0 4 3 2 1 5 6 7) Displaced Inversion Mutation: Chọn hai điểm ngẫu nhiên, đảo ngược các gen giữa hai điểm này, sau đó đưa vào vị trí bất kỳ trong cá thể gốc (0 1 2 3 4 5 6 7) = (0 6 5 4 1 2 3 7) 16 1.4.3. Một số ví dụ mã hóa đối với bài toán cái túi đa mục tiêu 1.4.3.1 Mô hình mã hóa nhị phân Trong bài toán cái túi 0-1 đa mục tiêu với mô hình mã hóa nhị phân, mỗi bit sẽ cho biết đồ vật đó có được chọn vào túi hay không. Cá thể 101100101100101011100101 Với mô hình này mỗi với vector cá thể (phương án) sẽ là một nếu đồ vật thứ i được chọn vào túi, và nếu đồ vật thứ i không được chọn. Việc tạo ra các bits của vector có thể khởi tạo ngẫu nhiên. Giả sử có 10 đồ vật muốn cho vào hai cái túi mô tả như sau: Thứ tự đồ vật Túi 1,Dung tích = 38 Túi 2,Dung tích = 35 Trọng lượng Giá trị Trọng lượng Giá trị 1 9 2 3 3 2 8 7 4 9 3 2 4 2 1 4 7 5 4 5 5 3 6 9 3 6 6 2 5 8 7 1 7 4 2 8 3 3 8 6 9 9 7 3 1 10 3 1 7 3 Theo mô hình mã hóa nhị phân, giả sử ta có vector x=1011001011, theo vector x thì các đồ vật có thứ tự {1,3,4,7,9,10} sẽ được chọn để đưa vào các túi, như vậy ta có trọng lượng tương ứng của hai túi là {31,23} và giá trị trong các túi tương ứng là {26, 15}. 1.4.3.2. Mô hình mã hóa hoán vị Đối với bài toán cái túi 0-1 đa mục tiêu để áp dụng được mô hình mã hóa hoán vị phải dựa trên một bộ giải mã. Đối với các bộ giải mã các giải pháp của 17 bài toán được biểu diễn như là một hoán vị đơn giản của các đối tượng được chọn. Bộ giải mã sẽ chọn lần lượt các cá thể bắt đầu từ đầu danh sách hoán vị, với mỗi đối tượng được chọn bộ giải mã sẽ kiểm tra để đảm bảo rằng bất kỳ cái túi nào cũng không bị vượt quá tải trọng tối đa. Việc giải mã sẽ ngừng ngay lập tức khi vượt quá tải trọng của một cái túi, và khi điều này xảy ra, đồ vật đó sẽ bị lấy ra khỏi mọi túi. Như vậy, mỗi một túi chứa chính xác cùng một đồ vật theo yêu cầu và mỗi giải pháp được tạo thành là một giải pháp khả thi. Giả sử có 10 đồ vật muốn cho vào hai cái túi mô tả như sau: Thứ tự đồ vật Túi 1, Dung tích = 38 Túi 2, Dung tích = 35 Trọng lượng Giá trị Trọng lượng Giá trị 1 9 2 3 3 2 8 7 4 9 3 2 4 2 1 4 7 5 4 5 5 3 6 9 3 6 6 2 5 8 7 1 7 4 2 8 3 3 8 6 9 9 7 3 1 10 3 1 7 3 Ta có thể lấy một hoán vị của các đồ vật như {2,5,1,7,9,8,10,3,4,6}, bộ giải mã đầu tiên chọn đồ vật 2 với trọng lượng là 8 đối với túi 1 và 4 đối với túi 2, tiếp theo là đồ vật thứ 5 với trọng lượng là 3 đối với túi 1 và 9 đối với túi 2, cho ta tổng trọng lượng là 11 đối với túi 1 và 12 đối với túi 2. Bộ giải mã sẽ thực hiện chọn các đồ vật từ danh sách hoán vị cho đến khi nó chọn đến đồ vật 10 và cho tổng trọng lượng là 36 đối với túi 1, 39 đối với túi 2. Trọng lượng 39 trong túi 2 vượt quá tải trọng của túi do đó đồ vật cuối cùng được chọn (đồ vật 10) sẽ bị xóa bỏ khỏi cả hai túi. Vector giá trị cho việc chọn các đồ vật 2, 5, 1, 7, 9, 8 là {32, 24}. 18 CHƯƠNG 2: GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU 2.1. Giới thiệu về giải thuật di truyền Các bài toán tối ưu đa mục tiêu thường hướng đến một đặc trưng bởi một tập các lựa chọn được xem xét tương đương với nhau trong tình trạng thiếu thông tin về mối tương quan của mỗi mục tiêu với các mục tiêu khác. Khi số lượng các mục tiêu cạnh tranh với nhau gia tăng và ít các mục tiêu có hành vi tốt thì độ phức tạp của bài toán sẽ tăng nhanh chóng. Trong sự phát triển của các giải thuật di truyền, người ta đã nhận thấy rằng các giải thuật di truyềncó khả năng thích hợp tốt nhất cho tối ưu hóa đa mục tiêu. Nhiều cá thể có thể được tìm kiếm cho nhiều lời giải song song với nhau. Khả năng để xử lý các bài toán phức tạp có các đặc trưng như : tính không liên tục, đa phương thức, không gian tìm kiếm tách rời và các hàm định giá bị nhiễu, đã củng cố tính hiệu quả tiềm năng của các giải thuật di truyền trong tìm kiếm và tối ưu đa mục tiêu. 2.1.1. Các nguyên tắc căn bản của giải thuật di truyền Tổng quát, một giải thuật di truyền được đặc trưng bởi ba yếu tố sau :  Một tập các lời giải ứng viên P  Tập P được thay đổi trong quá trình chọn lọc  Được xử lý bởi các toán tử di truyền, thường là lai ghép và đột biến Tương tự như tiến hóa trong tự nhiên, các lời giải ứng viên được gọi là các cá thể và tập các lời giải ứng viên được gọi là quần thể. Mỗi cá thể biểu diễn một lời giải có khả năng, nghĩa là một vectơ của các biến quyết định hay gọi tắt là vectơ quyết định, đối với bài toán đang xử lý, tuy nhiên một cá thể không phải là một vectơ quyết định, đúng hơn là nó đã được mã hóa dựa trên một cấu trúc thích hợp. Quá trình chọn lọc có thể là ngẫu nhiên hay được xác định hoàn toàn. Trong quá trình chọn lọc, các cá thể có chất lượng thấp bị loại bỏ ra khỏi quần thể trong khi đó các cá thể chất lượng cao thì được sinh sản. Mục đích là tập trung việc tìm kiếm trên phần đặc biệt của không gian tìm kiếm nhằm gia tăng 19 chất lượng trung bình của cá thể trong quần thể. Mục đích của tái tổ hợp và đột biến là phát sinh ra các lời giải mới bên trong không gian tìm kiếm bằng cách biến dạng các cá thể hiện đang có. Toán tử lai ghép lấy ra một số các cha và tạo ra một số các con bằng cách tái tổ hợp các cha lại với nhau. Để mô phỏng tính tự nhiên ngẫu nhiên của quá trình tiến hóa, một xác xuất lai ghép được kết hợp với toán tử này. Ngược lại, toán tử đột biến hiệu chỉnh các cá thể bằng cách thay đổi những phần nhỏ bên trong vectơ liên kết tương ứng với một tỉ lệ đột biến đã cho. Cả hai toán tử lai ghép và đột biến đều làm việc trên các cá thể. Nghĩa là trong không gian cá thể, không phải trên vectơ quyết định đã được giải mã. Dựa vào các khái niệm trên, tiến hóa tự nhiên được mô phỏng bằng một quá trình tính toán lặp đi lặp lại. Đầu tiên một quần thể ban đầu được khởi tạo một cách ngẫu nhiên (hay tương ứng với một lược đồ đã được định nghĩa trước), nó chính là điểm khởi đầu của một quá trình tiến hóa. Kế đến là một vòng lặp bao gồm các bước như định giá (gán giá trị fitness), chọn lọc, tái tổ hợp và đột biến được thực thi trong một số lần lặp hữu hạn nào đó. Mỗi lần lặp của vòng lặp được gọi là một thế hệ, và thường là có một số khá lớn, gọi là ngưỡng, được xác định trước làm điều kiện kết thúc của vòng lặp khi số lần lặp vượt qua ngưỡng đó. Nhưng cũng có một số điều kiện khác, như tình trạng đình trệ trong quần thể hay đã có một cá thể có chất lượng đủ, có thể được dùng để dừng vòng lặp. Sau cùng các cá thể tốt nhất trong quần thể cuối cùng hay tìm được trong toàn bộ quá trình tiến hóa sẽ là kết quả của giải thuật tiến hóa. Ta có một số ký hiệu như sau : I : không gian các cá thể X: không gian vectơ quyết định Y: không gian vectơ mục tiêu P: quần thể, chứa một số cá thể thuộc I (có thể gồm nhiều cá thể giống nhau) m: ánh xạ, một hình thức thu gọn của giải thuật giải mã, biến đổi một cá thể I thành một vectơ quyết định x=m(i) 20