Phân tích và thiết kế website bán điện thoại di động có hỗ trợ người mua chọn sản phẩm

ự nhiên sẽ dễ dàng và hiệu quả hơn. Trong khi đó người mua chỉ có thể trao đổi với trang web qua một số cách nhất định (thường được số hóa). 25 Các khó khăn về kỹ thuật: • Không gian tìm kiếm sản phẩm rất lớn, không thể tìm tuyến tính vì sẽ bắt khách hàng đợi lâu. • Cần tạo một kich bản để thu thập thông tin khách hàng sao cho hợp lý, tránh gây nhàm chán và làm mất nhiều thời gian. • Vấn đề “đa mục tiêu” (xem phụ lục A), các sở thích của người dùng đôi khi xung đột hoặc không hợp lý dẫn đên kết quả tìm kiếm thường là “Không tìm thấy mặt hàng nào phù hợp”. Đây là một trong những điều cấm kỵ nhất của người bán hàng, để người khách hàng ra về tay không, không những không bán được hàng mà còn để lại ấn tượng không tốt nơi khách hàng. 4.3 Vấn đề “đa mục tiêu” khi chọn sản phẩm Có thể thấy khó khăn lớn nhất của module hỗ trợ chọn sản phẩm đó là giải quyết, thỏa mãn cùng lúc nhiều tiêu chí của người mua về mặt hàng mà khách hàng đó quan tâm. Các mục tiêu,sở thích này có thể đối chọi nhau.Đây thực chất chính là đi giải quyết bài toán tối ưu đa mục tiêu (xem phụ lục A), trong đó mỗi mục tiêu chính là các sở thích của người dùng mà mặt hàng đó phải thỏa. Module này có nhiệm vụ tìm ra sản phẩm phù hợp (hoặc gần giống) với các sở thích của người mua. 4.4 Cách tiếp cận để giải bài toán “Tối ưu đa mục tiêu” khi chọn sản phẩm Nội dung của luận văn này là tìm hiểu bài toán tối ưu hóa đa mục tiêu và cách tiếp cận dùng giải thuật di truyền (Genetic Algorithm - GA). Và áp dụng cách tiếp cận trên để giải bài toán tối ưu hóa đa mục tiêu khi hỗ trợ khách hàng chọn sản phẩm. Luận văn này chọn cách tiếp cận trên với các lý do sau: • Đây là một cách tiếp cận mới mẻ và đang được nhiều người quan tâm,phát triển và ứng dụng vào nhiều lĩnh vực khác nhau. • Giải thuật di truyền (GA) giựa trên ý tưởng quần thể tự nhiên, chọn lọc ngẫu nhiên sẽ làm cho giải thuật có khả năng mạnh mẽ trong việc tìm kiếm một cách song song. Trong đó tất cả các cá thể trong quẩn thể sẽ được cố gắng tìm kiếm ở tất cả các hướng trong không gian tìm kiếm qua đó cho phép GA tránh được tối ưu hóa cục bộ. • Một thế mạnh của GA trong nhiệm vụ tìm kiếm đó là không lo sợ khả năng bùng nổ của tổ hợp tìm kiếm.GA đặc biệt tỏ ra hữu hiệu với các không gian tìm kiếm lớn. Với các không gian tìm kiếm lớn GA không những bảo đảm được tối 26 ưu hóa toàn cục mà còn bảo đảm được thời gian tìm kiếm, một trong những yêu cầu quan trọng của bài toán. • Và do đặc trưng của bài toán, chúng ta cần trả về cho người mua một danh sách các mặt hàng mà theo hệ thống là phù hợp nhất (thông thường từ 3 đến 5 giải pháp) nên việc sử dụng GA lại càng hợp lý. GA khác các phương pháp tìm kiếm tuyến tính khác là trong một lần chạy có thể cho ta một tập các giải pháp thuộc miền Pareto (xem phụ lục A) trong quần thể của nó. 4.5 Chuyển bài toán chọn sản phẩm thành bài toán tối ưu đa mục tiêu Chúng ta sẽ mô tả bài toán mua hàng thành các khái niệm trong bài toán tối ưu hóa đa mục tiêu. 4.5.1 Lời giải cho bài toán Trong bài toán tìm kiếm sản phẩm, người dùng mong muốn chọn ra một mặt hàng thích hợp do đó sản phẩm tối ưu đối với sở thích người mua chính là lời giải của bài toán. Nhưng chọn ra chỉ một sản phẩm cho người dùng có vẻ không phù hợp cho lắm, đôi khi tạo cho người dùng cảm giác bị ép buộc. Do đó giải pháp phù hợp đó là một tập các lời giải tối ưu, tập hợp này tương tự như những sản phẩm mà một người bán hàng sẽ gợi ý cho chúng ta khi đã nắm bắt được nhu cầu của khách hàng. 4.5.2 Các biến quyết định Ở đây các biến quyết định (xem phụ lục A) chính là các thuộc tính cấu thành nên sản phẩm. Ví dụ (sản phẩm là điện thoại di động) =X (Giá, trọng lượng, kiểu dáng, thời gian sử dụng pin) X là một điểm trong vùng khả thi (xem phụ lục A). Trong ví dụ trên có 4 biến quyết định. 4.5.3 Các ràng buộc Trong bài toán “tối ưu đa mục tiêu “ các ràng buộc (xem phụ lục A) chính là các điều kiện giữa các biến quyết định. Nhưng trong bài toán này không gian tìm kiếm là rời rạc, các điểm trong không gian tìm kiếm chính là ràng buộc của các biến quyết định. Hay nói cách khác nếu các giá trị của các biến quyết định cùng tồn tại trong một lời giải thì đó là một ràng buộc đúng đắn. Các ràng buộc được mô tả bằng 1 vector: 27 ))(),...,(),(( 21 xhxhxhH n= với n là số biến quyết định. Trong đó )()( kkk Nxxh == Khi đó ràng buộc H thỏa khi ),...,,(, 21 nii NNNXFX =∈∃ Với F là vùng khả thi, không gian lời giải và trong bài toán này là không gian các sản phẩm. 4.5.4 Các mục tiêu Có thể dễ dàng nhận thấy 2 mục tiêu (objective) (xem phụ lục A) mà người mua luôn nhắm tới là giá cả (cost) và chất lượng của sản phẩm (performance). Người mua luôn muốn mua được sản phẩm đáp ứng đầy đủ các yêu cầu với một giá rẻ nhất .Và điều khó khăn ở đây đó là 2 mục tiêu này luôn xung đột với nhau. Một sản phẩm với các tính năng nổi trội luôn có một cái giá cao hơn một sản phẩm khác và ngược lại do đó thường đi ngược lại với mong muốn của người mua. Do đó nhiệm vụ của bài toán đa mục tiêu đó là phải dung hòa cả 2 mục tiêu đó. Mô tả tổng quát: ))(),((maxmin/ xfxfF cp= . Từ đây ta thống nhất là sẽ dùng min, tức là mục tiêu của ta là làm tối thiểu hóa vector mục tiêu. Trong đó F là một vector mô tả 2 mục tiêu chính là cost và performance )(xfc là hàm mục tiêu cho mục tiêu về giá cả (cost). )(xf p là hàm mục tiêu cho mục tiêu về chất lượng (performance) Một ví dụ đơn giản về vector mục tiêu trên một sản phẩm gồm 2 thuộc tính. Sản phẩm X =(weight, cost) với tính chất giá (cost) càng cao trọng lượng (weight) càng thấp và người mua muốn một sản phẩm với giá (cost) thấp và trọng lượng (weight) cũng thấp. Vector mục tiêu được định nghĩa như sau: ))(),(( XfXfF cp= với )(Xf p = weight và )(Xfc = cost 28 Hình 4.1 - Vector mục tiêu của sản phẩm có 2 thuộc tính. Trên đây chỉ là trường hợp đơn giản performance của ta chỉ có một thuộc tính. Đối với trường hợp tổng quát thì sao? Bây giờ hàm mục tiêu về chất lượng (performance) sản phẩm sẽ trở thành: ))(...)()(()( )1(21 xfxfxfxf npppp −+++= với n là số thuộc tính của sản phẩm (n-1 vì đã bỏ qua thuộc tính giá cả) Nhưng khó khăn đặt ra là các thuộc tính lại không có đơn vị tính giống nhau do đó ta cần có một số tinh chỉnh để hàm )(xf p có thể thực hiện được. Một cách đơn giản mà ta có thể áp dụng đó là tinh chỉnh (normalize) các thuộc tính để các thuộc tính đều có giá trị là một số thực từ 0 đến 1. Bây giờ hàm mục tiêu về performance sẽ có dạng: )/)(.../)(/)(()( 0 1)1( 0 22 0 11 −−+++= nnpppp XxfXxfXxfxf trong đó 0kX là giá trị lớn nhất mà thuộc tính 1X có thể có được. 4.5.5 Hướng đến một lời giải “tối ưu” Để có được một lời giải tối ưu (hoặc gần tối ưu) chúng ta cần qua 2 giai đoạn: • Hướng các lời giải của chúng ta về miền tối ưu Pareto (xem phụ lục A) • Chọn trên miền Pareto một lời giải phù hợp nhất. 4.5.5.a Điều hướng lời giải về miền tối ưu Pareto Cũng như với cách mua hàng truyền thống ,để người bán hàng có thể chọn ra các sản phẩm phù hợp thì người mua phải cung cấp các tiêu chí (sở thích) về sản phẩm mà mình định mua. Cũng tương tự như vậy để giải quyết bài toán này chúng ta cũng phải thu thập một số thông tin về sản phẩm mà người dùng mong đợi, đây chính là mục tiêu của người dùng. )(Xfc )(Xf p Xu hướng người mua Vùng khả thi hay không gian tìm kiếm Vùng yêu thích 29 Chúng ta có thể mô tả một mục tiêu của người dùng bằng một vector như sau: ),...,,(Pr 21 kPPPef = (Pref - Preference ) Trong đó iP là một hằng số, mô tả giá trị mà người mua mong muốn có được ở thuộc tính ix . Và k là số thuộc tính mà người dùng mô tả về sản phẩm.Trong đó nk ≤≤1 (n là số thuộc tính của sản phẩm) vì không nhất thiết người dùng phải mô tả tất cả các thuộc tính. Và mục tiêu của chúng ta là đưa giá trị của các thuộc tính được mô tả về càng gần với giá trị iP càng tốt. Đây chính là nơi ta áp dụng hướng tiếp cận hướng mục đích (xem phụ lục A), mỗi iP là một mục đích của chúng ta. Một mục đích trên thuộc tính ix có thể được mô tả một cách đơn giản là: ipi xxf −)(min Và hàm mục tiêu về chất lượng sản phẩm sẽ có dạng: ))(minmin()( 1 ∑ = −= k i ipip xxfxf Khi tối ưu từng mục đích (goal) chúng ta hi vọng rằng các sản phẩm trong không gian tìm kiếm của thuật toán di truyền sẽ điều hướng về miền tối ưu Pareto. Hình 4.2 - Điều hướng về miền tối ưu Pareto. )(xfc )(xf p Miền tối ưu Pareto iP 1P 2P 30 4.5.5.b Chọn trên miền tối ưu Pareto lời giải tối ưu nhất Theo định nghĩa của miền tối ưu Pareto thì những lời giải trên miền này không thể so sánh với nhau được nữa vì trên miền này không có lời giải nào hoàn toàn thống trị lời giải khác (xem phụ lục A). Khi chúng ta đã chọn lọc được các lời giải trên miền Pareto (ở bước trên) thì việc tiếp theo đó là chọn ra trên miền đó 1 hoặc nhiều lời giải mà ta cho là tốt hơn những lời giải khác (cũng thuộc miền Pareto). Chúng ta phải làm việc này vì trên miền Pareto không đảm bảo chỉ tồn tại 1 lời giải. Để chọn ra lời giải tốt hơn trên miền này chúng ta sẽ áp dụng cách tiếp cận Weighting Objective(xem phụ lục A). Khi đó ta cần thêm các thông tin về mức độ quan trọng của các mục tiêu (đây là các đánh giá khách quan của người ra quyết định-người mua hàng).Đây chính là mối tương quan về độ trội của các mục tiêu. Lúc này vector mô tả sở thích của người mua có dạng: )),(),...,,(),,((Pr 2211 kpkpp PwPwPwef = trong đó iw chính là độ quan trọng của mục tiêu thứ i trong mục tiêu về chất lượng của sản phẩm )(xf pi Khi đó trọng số quan trọng của mục tiêu về chất lượng sản phẩm (performance) sẽ là : ∑ = = k i pip ww 1 Và độ quan trọng của mục tiêu về giá cả cw Với các ràng buộc: 1 1 =+=+ ∑ = c k i picp wwww Khi người dùng thay đổi các trọng số độ quan trọng của các mục tiêu thì các lời giải “tối ưu” sẽ di chuyển trên miền Pareto. Người ra quyết định có thể thay đổi trọng số này để có thể chọn ra các lời giải “tối ưu”. 31 Hình 4.3 Di chuyển trên miền Pareto bằng cách thay đổi trọng số 4.5.6 Các cải tiến để phù hợp với bài toán. 4.5.6.a Mô tả cấu trúc gene của thuật giải di truyền Do nhu cầu của bài toán (cần trả về một tập lớn hơn 1 lời giải tối ưu) nên mỗi gen sẽ được biễu diễn bằng một mảng các định danh của các lời giải trong không gian tím kiếm (trong trường hợp cụ thể đó là các id của các sản phẩm trong cơ sở dữ liệu). Số lời giải trả về có thể phụ thuộc vào mong muốn của người dùng (nhưng phải lớn hơn 1, không ai lại muốn không tìm thấy sản phẩm nào). Mô tả một gen: Trong đó n là số kết quả mà người dùng mong đợi được trả về. Kết quả tốt nhất mà ta mong đợi để chọn đó là gen mà tất cả các ID trong gen đều nằm trên miền tối ưu Pareto hoặc tồi hơn có thể có một số ID thuộc Pareto và một số ít hơn nằm gần miền Pareto. Trường hợp không thành công là không có ID nào thuộc miền Pareto lúc này thuật giải chưa được hội tụ, hoặc hội tụ quá sớm gây ra tối ưu cục bộ. )(xfc )(xf p cw pw Miền tối ưu Pareto ID1 ID2 … IDn 32 Hình 4.4 - Các trạng thái gen trong quần thể. 4.5.6.b Vai trò của các thao tác chọn lọc, lai ghép, đột biến trên quần thể Chọn lọc: Quá trình này nhằm mục đích loại bỏ khỏi quần thể những gen chứa các lời giải xấu (những lời giải nằm xa miền tối ưu Pareto) (xem hình trên). Tuy nhiên vấn đề cần quan tâm ở đây đó là bảo toán tính tốt và tính đa dạng của quần thể. Khi loại bỏ các gen xấu chúng ta có thể loại bỏ luôn cả các lời giải tốt (hoặc tương đối tốt) tồn tại trong gen. Lai ghép: Đây là một quá trình tự nhiên trong đó các nhiễm sắc thể giữa 2 gen sẽ được hoán đổi cho nhau. Nhiệm vụ chính của nó là làm tăng tính đa dạng của quần thể, với hi vọng các gen tốt hơn sẽ được tạo ra. Chúng ta cần một số cải tiến để bảo đảm rằng các gen đời sau sẽ tốt hơn đời trước. Bởi vì độ tốt của một gen được xác định bằng tổng độ tốt của mỗi nhiễm sắc thể (gen nào có nhiều nhiễm sắc thể (NST) trên miền Pareto, hoặc gần miền Pareto hơn thì gen đó tốt hơn). Nên khi lai ghép ta sẽ chuyển các NST tốt của một gen (bố hoặc mẹ) vào gen của người còn lại. Như vậy sau khi lai ghép sẽ tạo ra một gen hoàn toàn trội hơn 2 gen bố mẹ, và một gen sẽ chứa toàn những tính xấu. Khi đó trong quá trình chọn lọc ta chỉ giữ lại một gen con tốt vừa được tạo ra và một gen (bố hoặc mẹ) tốt hơn. Khi đó ta sẽ vừa bảo đảm các nhiễm sắc thể tốt sẽ không bị “vô tình” loại bỏ và tính đa dạng của quần thể cũng vẫn được bảo tồn qua các đời. )(xfc )(xf p Loại gene tốt nhất Gene tương đối tốt Gene xấu 33 Hình 4.5 - Lai ghép. Đột biến: Vai trò của thao tác đột biến là để tránh tối ưu hóa cục bộ (các gen chưa tiến đến được miền Pareto). Qua thao tác đột biến chúng ta sẽ đưa các lời giải tốt hơn vào không gian quần thể của thuật giải di truyền. Hình 4.6 - Đột biến. 4.5.6.c Hàm thích nghi Hàm thích nghi của mỗi sản phẩm sẽ có dạng như sau: ∑ = += k i cpi xfxfF 1 )()( trong đó )(xf pi là hàm mục tiêu của thuộc tính về chất lượng thứ i (người mua quan tâm đến k thuộc tính-ngoài giá). )(xfc )(xf p Đột biến )(xfc )(xf p Gene bố Gene mẹ Gene con tốt Gene con xấu 34 )(xf c hàm mục tiêu về giá. Một sản phẩm tốt khi có giá trị hàm thích nghi lớn hơn.Khi thuật giải cố gắng tối đại hóa hàm thích nghi, thực chất là đang điều hướng các sản phẩm về miền tối ưu Pareto. Để kết hợp cả 2 giai đoạn điều hướng chúng ta có thể kết hợp cả 2 cách dùng hướng mục đích và trọng số quan trọng vào cùng một hàm mục tiêu như sau: )/1()( *iiiipi xxpwxf −−= và )/||1()( *ccpwxf ccc −−= trong đó iw là độ quan trọng của thuộc tính i. ip là giá trị mà người dùng mong đợi ở thuộc tính i. ix là giá trị của thuộc tính i * ix là giá trị tối đa mà thuộc tính i có thể có được. *c là giá tiền tối đa mà một sản phẩm có thể có. 35 Chương 5 Phân tích và thiết kế website bán điện thoại di động có hỗ trợ người mua chọn sản phẩm 5.1 Phân tích 5.1.1 Mô hình Usecase Hình 5.1 - Lược đồ Usecase. 5.1.2 Mô tả các Actor Actor khách hàng: Người dùng duy nhất của hệ thống là khách hàng. Hệ thống không yêu cầu mỗi khách hàng phải có tài khoản riêng. Một người dùng bất kỳ có thể vào hệ thống tìm và mua điện thoại bất cứ lúc nào. 5.1.3 Mô tả các Usecase 5.1.3.a Usecase Tìm kiếm Usecase này thực hiện khi khách hàng muốn tìm kiếm sản phẩm điện thoại di động theo một mức giá và theo một số hãng sản xuất. Người dùng chọn một mức giá trong năm mức giá sau: và chọn các hãng điện thoại cần tìm. Hệ thống sẽ trả về cho khách hàng danh sách các máy điện thoại di động của các hãng đã chọn có mức giá đó. Danh sách thể hiện thông tin sơ bộ về mỗi sản phẩm gồm: tên máy, nhà sản xuất, giá bán, kích cỡ, thời gian chờ, thời gian đàm thoại. Và đối với mỗi sản phẩm đều cho phép người dùng xem thông tin chi tiết sản phẩm hoặc đặt mua sản phẩm. Lược đồ trình tự - luồng cơ bản cho usecase Tìm kiếm 36 Hình 5.2 - Lược đồ trình tự cho usecase Tìm kiếm. 5.1.3.b Usecase Xem danh sách sản phẩm bán chạy nhất Usecase này nhằm đưa ra cho khách hàng một danh sách các sản phẩm bán chạy nhất của hệ thống. Hệ thống thể hiển danh sách thông tin sơ bộ về mỗi sản phẩm gồm: tên máy, nhà sản xuất, giá bán, kích cỡ, thời gian chờ, thời gian đàm thoại. Và đối với mỗi sản phẩm đều cho phép người dùng xem thông tin chi tiết sản phẩm hoặc đặt mua sản phẩm. Lược đồ trình tự-luồng cơ bản cho usecase Xem danh sách sản phẩm bán chạy nhất như sau: Hình 5.3 - Lược đồ trình tự cho usecase Xem danh sách sản phẩm được mua nhiều nhất. 5.1.3.c Usecase Xem danh sách sản phẩm mới ra mắt Usecase này nhằm đưa ra cho khách hàng một danh sách các sản phẩm mới ra mắt trong tháng. Hệ thống thể hiển danh sách thông tin sơ bộ về mỗi sản phẩm gồm: tên máy, nhà sản xuất, giá bán, kích cỡ, thời gian chờ, thời gian đàm thoại. Và đối với mỗi sản phẩm đều cho phép người dùng xem thông tin chi tiết sản phẩm hoặc đặt mua sản phẩm. Lược đồ trình tự-luồng cơ bản cho usecase Xem danh sách sản phẩm mới ra mắt như sau: 37 Hình 5.4 - Xem danh sách sản phẩm mới ra mắt. 5.1.3.d Usecase Xem danh sách sản phẩm được nhiều người quan tâm Usecase này nhằm đưa ra cho khách hàng danh sách các sản phẩm được nhiều người xem chi tiết nhất. Hệ thống thể hiển danh sách thông tin sơ bộ về mỗi sản phẩm gồm: tên máy, nhà sản xuất, giá bán, kích cỡ, thời gian chờ, thời gian đàm thoại. Và đối với mỗi sản phẩm đều cho phép người dùng xem thông tin chi tiết sản phẩm hoặc đặt mua sản phẩm. Lược đồ trình tự-luồng cơ bản cho usecase Xem danh sách sản phẩm được nhiều người quan tâm như sau: Hình 5.5 - Lược đồ tuần tự Usecase Sản phẩm được quan tâm nhiều nhất. 5.1.3.e Usecase Trợ giúp chọn sản phẩm Usecase này thực hiện khi khách hàng muốn tìm kiếm những chiếc điện thoại di động có các đặc tính mà mình thích. Hệ thống yêu cầu khách hàng đánh giá mức độ quan tâm đối với các tiêu chuẩn của máy điện thoại di động và giá trị mong muốn của thuộc tính đó. Hệ thống sẽ trả về danh sách gồm 3 máy điện thoại phù hợp nhất với tiêu chuẩn đã đánh giá của khách hàng. Năm tiêu chuẩn cho khách hàng sau đánh giá gồm có: Trọng lượng của máy, thời gian sử dụng máy, kiểu dáng của máy, các tính năng giải trí có trong máy (bao gồm các tính năng 38 “có camera”,”xem video”,”nghe nhạc MP3”, “nghe radio FM” và “tải nhạc chuông Midi”), và giá bán của máy. Ta chọn 5 tiêu chuẩn trên tiêu biểu cho sự phong phú thuộc tính của một máy điện thoại di động. Hai tiêu chuẩn đầu (trọng lượng, thời gian sử dụng máy) và tiêu chuẩn cuối (giá bán) là những thuộc tính có miền giá trị gần như liên tục, có thể chia ra các khoảng cho người dùng chọn. Ví dụ thời gian chờ có thể chia ra các khoảng “ngắn”, ”rất ngắn”, ”trung bình”, “dài”, ”rất dài”. Tiêu chuẩn thứ ba(kiểu dáng của máy) là thuộc tính có miền giá trị rời rạc, người dùng chọn một kiểu dáng cụ thể của máy mà họ ưa thích. Tiêu chuẩn thứ tư là sự kết hợp nhiều tính năng của máy điện thoại di động, người dùng sẽ chọn các tính năng mà họ thích. Đây sẽ là nơi thuật toán di truyền được áp dụng. Các đánh giá của khách hàng được dùng tìm kiếm sản phẩm thích hợp nhất trong quần thể sản phẩm của thuật toán di truyền. Lược đồ trình tự-luồng cơ bản cho usecase Trợ giúp chọn sản phẩm như sau: Hình 5.6 - Lược đồ trình tự cho usecase Trợ giúp lựa chọn sản phẩm. 5.1.3.f Usecase Duyệt danh mục sản phẩm theo hãng sản xuất Usecase này thực hiện khi khách hàng muốn xem tất cả các sản phẩm điện thoại di động của một nhà sản xuất cụ thể. Hệ thống đưa ra các danh sách thông tin sơ bộ về các điện thoại của nhà sản xuất đã chọn. Lược đồ trình tự-luồng cơ bản cho usecase Duyệt danh mục sản phẩm theo hãng sản xuất như sau: 39 Hình 5.7 - Lược đồ trình tự cho usecase Duyệt sản phẩm theo hãng sản xuất. 5.1.3.g Usecase Xem chi tiết Usecase này thực hiện khi khách hàng muốn xem thông tin chi tiết về một máy điện thoại di động nào đó từ danh sách các điên thoại. Các thông tin đưa ra cho khách hàng gồm : Tên nhà sản xuất, model máy, kích thước, trọng lượng, kiểu dáng, băng tần hỗ trợ, độ phân giải và màu sắc màn hình hiển thị, thời gian đàm thoại và thời gian chờ, giá bán, bộ nhớ, dạng tin nhắn hỗ trợ, các tính năng giải trí (bao gồm tích hợp máy ảnh, quay video, nghe nhạc MP3, nghe radio FM) và các tính năng kết nối dữ liệu (bao gồm Java, GPRS, WAP, Bluetooth). Tại đây, khách hàng có thể đặt mua ngay máy điện thoại này. Lược đồ trình tự-luồng cơ bản cho usecase Xem chi tiết như sau: Hình 5.8 - Lược đồ trình tự cho usecase Xem thông tin chi tiết. 5.1.3.h Usecase Thêm hàng vào giỏ Usecase này thực hiện khi khách hàng muốn chọn một sản phẩm và thêm vào giỏ hàng. Hệ thống sẽ báo cho khách hàng khi đã thêm sản phẩm vào giỏ thành công. Lược đồ trình tự-luồng cơ bản cho usecase Thêm hàng vào giỏ như sau: 40 Hình 5.9 - Lược đồ trình tự cho usecase Thêm hàng vào giỏ. 5.1.3.i Usecase Xem giỏ hàng Usecase này thực hiện khi khách hàng muốn xem danh sách sản phẩm đã đặt mua trong giỏ hàng. Hệ thống hiển thị danh sách từng sản phẩm đã đặt mua của khách hàng và số lượng của chúng. Người dùng có thể nhập lại số lượng đặt mua hoặc hủy việc đặt mua một sản phẩm. Lược đồ trình tự-luồng cơ bản cho usecase Xem giỏ hàng như sau: Hình 5.10 - Lược đồ trình tự cho usecase Xem giỏ hàng. 5.1.3.j Usecase Thanh toán Usecase này thực hiện khi khách hàng muốn thanh toán cho những sản phẩm đã chọn trong giỏ hàng. Hệ thống sẽ xem khách hàng đã đăng ký thông tin cá nhân chưa. Nếu chưa hệ thống sẽ buộc khách hàng điền vào thông tin cá nhân bao gồm: Họ tên khách hàng, địa chỉ, email. 41 Hệ thống sẽ tạo tạo hóa đơn liệt kê các sản phẩm trong giỏ hàng, yêu cầu khách hàng chọn phương thức giao hàng, phương thức thanh toán. Khách hàng chọn phương thức giao hàng và phương thức thanh toán thích hợp với mình rồi chấp nhận đặt mua hoặc hủy không mua. Lược đồ trình tự-luồng cơ bản cho usecase Thanh toán như sau: Hình 5.11 – Lược đồ trình tự cho usecase Thanh toán. 5.2 Thiết kế 5.2.1 Thiết kế hệ thống Hệ thống gồm 2 module chính: Module ứng dụng cửa hàng web bán điện thoại di động và module áp dụng thuật toán GA tìm kiếm điện thoại theo sở thích người dùng. Mobile ứng dụng thuật toán GA có thể phân gồm 2 gói riêng biệt. Gói MobilePhoneShop chứa thông tin các thuộc tính của máy điện thoại di động, có chức năng kết nối và đưa thông tin của cơ sở dữ liệu lên một nhớ chính. Gói GenecticAlgorithm chứa thuật toán di truyền. Sơ đồ kiến trúc các thành phần hệ thống: 42 Hình 5.12 - Mô hình kiến trúc hệ thống. 5.2.2 Thiết kế cơ sở dữ liệu 5.2.2.a Lược đồ cơ sở dữ liệu quan hệ Hình 5.13 - Sơ đồ dữ liệu quan hệ. 43 5.2.2.b Danh sách các bảng Bảng 5-1-Danh sách các bảng cơ sở dữ liệu STT Tên bảng Ghi chú 1. tblItems Sản phẩm điện thoại di động 2. tblProducers Hãng sản xuất 3. tblCaseType Danh sách kiểu dáng của điện thoại di động 4. tblOders Đơn đặt hàng 5. tblOderDetails Chi tiết đơn đặt hàng 5.2.2.c Chi tiết các bảng dữ liệu Bảng 5.2 - Bảng dữ liệu tblItems STT Tên thuộc tính Ý nghĩa Kiểu dữ liệu Miền giá trị Ghi chú 1 ItemID Mã sản phẩm int Khóa chính 2 ItemModel Tên sản phẩm nvarchar(50) 3 ProducerID Mã hãng sản xuất int 4 Image Đường dẫn chứa file hình của sản phẩm 5 SmallImage 6 Comingdate Ngày ra mắt datetime 7 Height Chiều cao real Đơn vị: mm 8 Length Chiều rộng real Đơn vị: mm 9 Width Độ dày real Đơn vị: mm 10 Weight Trọng lượng smallint Đơnvị: gam 11 Standby Time Thời gian chờ smallint Đơn vị: giờ 12 Talk Time Thời gian đàm thoại smallint 13 Screen Color Màn hình char(10) 14 Screen Resolution Độ phân giải của màn hình char(10) 15 GPRS GPRS Bit 16 FM Nghe radio FM bit 17 Message Loại tin nhắn hỗ trợ nvarchar(50) 18 Camera Chụp hình nvarchar(50) 19 MP3 Nghe nhạc MP3 bit 20 Memory Dung lượng bộ nhớ int 21 WAP Char(10) 44 22 Bluetooth bit 23 Java Bit 24 Battery nvarchar(50) 25 Networks Mô tả các băng tần hỗ trợ nvarchar(50) 26 Price float 27 CaseType Mã kiểu dáng int 1-4 28 Midi bit 29 Video Quay video bit 30 Games Mô tả các trò chơi có trong máy nvarchar(50) Bảng 5.3 - Bảng dữ liệu tblCaseType STT Tên thuộc tính Ý nghĩa Kiểu dữ liệu Miền giá trị Ghi chú 1 CasetypeID Mã kiểu dáng int Khóa chính 2 Description Mô tả nvarchar(20) Bảng 5.4 - Bảng dữ liệu tblProducers STT Tên thuộc tính Ý nghĩa Kiểu dữ liệu Miền giá trị Ghi chú 1 ProducerID Mã hãng sản xuất Int Khóa chính 2 ProducerName Tên hãng sản xuất nvarchar(50) 3 Website Đường dẫn trang web hãng sản xuất nvarchar(50) 4 Logo Đường dẫn chứa hình của hãng sản xuất nvarchar(50) Bảng 5.5 - Bảng dữ liệu tblOrders STT Tên thuộc tính Ý nghĩa Kiểu dữ liệu Miền giá trị Ghi chú 1 OderID Mã đơn đặt hàng Int Khóa chính 2 OderDate Ngày đặt datetime 3 CusName Tên khách hàng nvarchar(50) 4 CusAdd Địa chỉ khách hàng nvarchar(50) 5 CusEmail Email của khách hàng nvarchar(50) 6 CusTel Điện thoại của khách hàng char(10) 7 DeliveryAdd Địa chỉ giao hàng nvarchar(50) 8 Amount Tổng tiền khách float 45 hàng 9 DiscountAmount Phần trăm giảm giá float 10 ShipCost Phí giao hàng float 11 TotalAmount Tổng tiền thanh toán hóa đơn. float Bảng dữ liệu tblOrderDetails Bảng 5.6 - Bảng dữ liệu tblOrderDetails STT Tên thuộc tính Ý nghĩa Kiểu dữ liệu Miền giá trị Ghi chú 1 OrderNumber Số thứ tự của chi tiết trong hóa đơn Int Khóa chính 2 OrderID Mã hóa đơn Int Khóa chính 3 ItemID Mã sản phẩm Int Khóa chính 4 Quatity Số lượng Int 5 Price Giá Float 5.2.3 Thiết kế các lớp đối tượng Phần này bao gồm thiết kế các xử lý của đối tượng ở cả ba tầng hoạt động của hệ thống và sự phối hợp hoạt động giữa chúng ở các mức độ tổng thể và chi tiết đến từng nghiệp vụ. 5.2.3.a Hiện thực hóa các usecase ở mức thiết kế Usecase Tìm kiếm Hình 5.14 - Lược đồ trình tự (mức thiết kế) cho usecase Tìm kiếm. Usecase Xem danh sách sản phẩm mới ra mắt: 46 Hình 5.15 - Lược đồ trình tự (mức thiết kế) cho usecase Xem sản phẩm mới ra mắt. Usecase Trợ giúp chọn sản phẩm Hình 5.16 - Lược đồ trình tự (mức thiết kế) cho usecase Trợ giúp chọn sản phẩm 47 Usecase Xem chi tiết Hình 5.17 - Lược đồ trình tự (mức thiết kế) cho usecase Xem thông tin chi tiết Usecase Thêm hàng vào giỏ Hình 5.18 - Lược đồ trình tự (mức thiết kế) cho usecase Thêm hàng vào giỏ Usecase Xem giỏ hàng Hình 5.19 Lược đồ trình tự (mức thiết kế) cho usecase Xem giỏ hàng 48 Usecase Thanh toán Hình 5.20 - Lược đồ trình tự (mức thiết kế) cho usecase Thanh toán 5.2.3.b Sơ đồ phối hợp giữa các trang web Hình 5.21 Sơ đồ phối hợp giữa các trang web 52 5.2.3.c Sơ đồ lớp của ứng dụng web Hình 5.22 - Sơ đồ lớp ứng dụng WebMobileShop. 53 Các thành phần của sơ đồ: Bảng 5.7 - Các đối tượng lớp của hệ thống WebMobileShop STT Lớp Mô tả 1 pageDefault Trang chủ của ứng dụng web 2 pageSearch Trang tìm kiếm sản phẩm theo giá và hãng sản xuất 3 pageCriterionChoose Trang trợ giúp khách hàng lựa chọn sản phẩm thông qua đánh giá các tiêu chuẩn của sản phẩm 4 pageResult Trang kết quả sản phẩm đề nghị cho khách hàng. 5 pageViewcart Trang xem giỏ hàng. 6 Checkout Trang đặt hàng và kết xuất hóa đơn. 7 BLItems Lớp đối tượng xử lý liên quan đến sản phẩm gồm các phương thức lấy sản phẩm theo hãng sản xuất, tìm kiếm sản phẩm theo giá và hãng sản xuất. 8 BLProducer Lớp đối tượng xử lý liên quan đến hãng sản xuất gồm các phương thức lấy danh sách các hãng sản xuất. 9 OrderItem Lớp đối tượng xử lý các sản phẩm đã đặt hàng. 10 OrderList Lớp đối tượng xử lý liên quan đến danh sách đặt hàng. 11 CustomerPreference Lớp đối tượng chứa các đánh giá khách hàng về mỗi tiêu chuẩn sản phẩm. 12 Weight Lớp đối tượng chứa thuộc tính trọng lượng của sản phẩm. 13 Price Lớp đối tượng chứa thuộc tính giá bán của sản phẩm. 14 CaseType Lớp đối tượng chứa thuộc tính kiểu dáng của sản phẩm. 15 Entertainment Lớp đối tượng chứa các thuộc tính giải trí của sản phẩm. 16 StandbyTime Lớp đối tượng chứa thuộc tính thời gian sử dụng của sản phẩm. 17 Population Lớp đối tượng chứa các xử lý danh sách sản phẩm của module thuật toán GA. 18 MobileContainer Lớp đối tượng xử lý dữ liệu danh sách sản phẩm của module thuật toán GA. 19 DAItems Lớp đối tượng xử lý dữ liệu danh sách sản phẩm. 20 DAProducer Lớp đối tượng xử lý dữ liệu danh sách hãng sản xuất. 54 5.2.3.d Sơ đồ lớp của module thuật toán GA Hình 5.23 - Sơ đồ lớp của module thuật toán GA. Các lớp đối tượng trong module này được mô tả trong bảng dưới đây: Bảng 5.8 - Các đối tượng thuộc module thuật toán GA STT Lớp Mô tả 1 Genome Lớp đối tượng biểu diễn một gen của thuật toán di truỳen. 2 Individual Lớp đối tượng biểu diễn một cá thể 3 CustomerPreference Lớp đối tượng chứa các đánh giá khách hàng về mỗi tiêu chuẩn sản phẩm. 4 Weight Lớp đối tượng chứa thuộc tính trọng lượng của sản phẩm. 5 Price Lớp đối tượng chứa thuộc tính giá bán của sản phẩm. 6 CaseType Lớp đối tượng chứa thuộc tính kiểu dáng của sản phẩm. 7 Entertainment Lớp đối tượng chứa các thuộc tính giải trí của sản phẩm. 8 StandbyTime Lớp đối tượng chứa thuộc tính thời gian sử dụng của sản phẩm. 9 Population Lớp đối tượng chứa các xử lý danh sách sản phẩm, biểu diễn quần thể của thuật giải di truyền. 10 MobileContainer Lớp đối tượng xử lý dữ liệu danh sách sản phẩm. 11 MobileCriterion Lớp đối tượng cha được xử lý dữ liệu danh sách sản phẩm từ cơ sở dữ liệu.. 55 Chương 6 Cài đặt 6.1 Môi trường phát triển ứng dụng Hệ thống website được cài đặt dựa trên các môi trường phát triển sau: • Môi trường cài đặt ứng dung: Visual Studio.NET • Ngôn ngữ sử dụng: ASP.NET và C#.NET • Hệ quản trị cơ sở dữ liệu: SQL Server • Phần mềm mô hình hóa ứng dụng: Rational XDE 6.2 Cài đặt chương trình Tập tin cơ sở dữ liệu SQL Server được cài đặt tại máy Server. Hệ chương trình được viết bằng ngôn ngữ C#.NET gồm 2 phần: • Phần cài đặt thuật toán GA gồm 2 project : project MobilePhoneShop chứa kết nối và xử lý đến cơ sở dữ liệu và project GeneticAlgorithm chứa cài đặt thuật toán di truyền theo trọng số. Cả hai project là những Class Library project kết xuất ra tập tin DLL. • Phần trang web Mua bán điện thoại di động gồm 1 project WebMobileShop được cài đặt theo mô hình ứng dụng web 3 tầng: - Tầng dữ liệu bao gồm các phương thức đọc, ghi cơ sở dữ liệu sử dụng kỹ thuật ADO.NET để kết nối và truy cập dữ liệu. Các hàm này chứa trong các lớp đối tượng DABasic, DAItems, DAProducers. Khi khởi động chương trình, hệ thống đọc vào bộ nhớ chính danh sách thuộc tính của các máy điện thoại di động. Trong quá trình hoạt động, khi có nhu cầu đọc, ghi dữ liệu, hệ thống kết nối với Server để đọc các thông tin dữ liệu vào bộ nhớ chính của hệ thống hoặc ghi dữ liệu từ bộ nhớ chính vào tập tin cơ sở dữ liệu trên Server. - Tầng xử lý bao gồm các hàm xử lý nghiệp vụ. Các hàm xử lý khi xử lý trên dữ liệu sẽ thực hiện trực tiếp trên dữ liệu đã được đọc vào bộ nhớ chính. Nếu chưa có dữ liệu trong bộ nhớ, các hàm xử lý sẽ triệu gọi đến các hàm đọc ghi dữ liệu ở tầng dữ liệu. Trong chương trình, các hàm xử lý được thiết kế độc lập với giao diện người dùng. 56 - Tầng giao tiếp bao gồm các hàm hiển thị thông tin và các xử lý dữ liệu có thể hiện trên màn hình được thiết kế. Các hàm này được cài đặt trực tiếp tại các trang web. Khi các trang web được triệu gọi, thông tin dữ liệu được lấy từ bộ nhớ của máy chủ để hiển thị đến trình duyệt của người dùng. Khi có các xử lý nghiệp vụ xảy ra, các hàm tại tầng giao tiếp sẽ triệu gọi đến các hàm xử lý nghiệp vụ ở tầng xử lý. Riêng trang trợ giúp lựa chọn sản phẩm sẽ áp dụng mô hình thuật toán GA bằng cách gọi các hàm trong 2 DLL đã trình bày ở trên. Với mô hình xử lý như mô tả trên, hệ thống phần nào đã thể hiện được sự hoạt động của mô hình ba lớp trên môi trường .NET, sự phối hợp cũng như tính độc lập của các lớp đối tượng được cài đặt tại mỗi tầng và trong toàn ứng dụng. 6.3 Một số màn hình tiêu biểu Khi gọi ứng dụng web, trang đầu tiên sẽ hiển thị như sau: Trang web: Default.aspx Tiêu đề: WebMobileShop Homepage Ý nghĩa: Trang chủ của ứng dụng 57 Trang web: CriterionChoose.aspx Ý nghĩa: Trợ giúp người dùng chọn lựa sản phẩm theo các tiêu chuẩn cần có của một máy điện thoại di động Trang web: Result.aspx Ý nghĩa: Danh sách các máy điện thoại đề nghị cho khách hàng sau khi họ đã đánh giá các tiêu chuẩn ở trang CriterionChoose.aspx 58 Trang web: Viewcart.aspx Ý nghĩa: Trang chủ của ứng dụng 59 60 Chương 7 Kết luận và hướng phát triển 7.1 Kết luận Hệ hỗ trợ ra quyết định tuy không phải là một đề tài mới mẻ, với rất nhiều đề tài nghiên cứu và các nổ lực áp dụng thực tế nó đã dần dà trở thành một bộ phận quan trọng của các hệ thống thông tin hiện đại. Tuy nhiên các áp dụng của nó vẫn ở mức rất sơ khai và vẫn chưa có một chuẩn thống nhất.Trong khuôn khổ luận văn chúng em đã tìm hiểu một cách tổng quan Hệ hỗ trợ ra quyết định. Bài toán tối ưu hóa đa mục tiêu thực chất là một pha trong Hệ hỗ trợ ra quyết định, giai đoạn lựa chọn. Đã có rất nhiều cách tiếp cận được đặt ra để giải quyết bài toán này, xong các cách tiếp cận đó vẫn giựa trên một ứng dụng, một tình huống cụ thể thực tế nào đó. Và thực tế là chưa có một phương pháp nào có thể thỏa mãn tất cả các tình huống và cũng chưa có phương pháp nào để so sánh hiệu quả của các phương pháp đó với nhau.Trong luận văn này chúng em đã cố gắng đưa ra một cái nhìn tổng quát về bài toán tối ưu hóa đa mục tiêu và một số cách tiếp cận.Trong đó chúng em tập trung vào phương pháp dùng thuật giải di truyền, một phương pháp còn tương đối mới mẻ. Và giựa trên phương pháp áp dụng thuật giải di truyền trong bài toán tối ưu hóa đa mục tiêu ,chúng em cũng đã có những cải tiến để có thể áp dụng vào bài toán cụ thể đó là “Trợ giúp khách hàng chọn sản phẩm khi mua hàng qua mạng”. Với cách tiếp cận trên chúng em đã tìm cách áp dụng và xây dựng một trang web bán điện thoại qua mạng.Trong đó có cài đặt phần trợ giúp để khách hàng có thể chọn một chiếc vừa ý và nhanh chóng nhất.Do trong khuôn khổ giới hạn của luận văn ,tuy trang web có thể đáp ứng được các thành phần cơ bản cho một trang web bán hàng nhưng vẫn còn rất nhiều thiếu sót và hạn chế. Sau khi cài đặt chúng em nhận thấy rằng với cách tiếp cận này trang web sẽ đảm bảo được về mặt thời gian.Thế nhưng kết quả trả về có thể khác nhau qua các lần chạy (vì đôi khi miền tối ưu Pareto có nhiều lời giải). Tuy nhiên một điểm mạnh của phương pháp này so với các phương pháp tìm kiếm thông thường đó là luôn cho ra kết quả (tối ưu hoặc gần tối ưu) chứ không phải đưa ra một câu thông báo đáng buồn cho người mua lẫn kẻ bán “Không thể tìm thấy sản phẩm thích hợp”. 61 7.2 Hướng phát triển Hoàn thiện trang web để nó có thể áp dụng một cách thực tế: giao diện thân thiện và gần gủi hơn, hoàn thiện chức năng thanh toán. Cải tiến phương pháp đánh giá trên miền Pareto để có thể cho ra kết quả xâu xát hơn và để tránh tình trạng cho ra các kết quả khác nhau qua các lần chạy. Hổ trợ thêm để người dùng có thể chọn ra sản phẩm cuối cùng trong số các sản phẩm mà ta đã đề nghị. Vì chỉ cần có 2 sự chọn lựa là ta đã phải đưa ra quyết định. Chúng ta có thể áp dụng các phương pháp giải quyết tối ưu cũ (tiêu tốn nhiều thời gian hơn) như AHP, Tweak Utility... 62 Phụ lục A Bài toán tối ưu đa mục tiêu A.1 Sự ra đời Tất cả các lĩnh vực như kỹ thuật, khoa học, kinh doanh, và khoa học xã hội và tự nhiên đều liên quan đến việc quyết định phân bổ,hoạch định các tài nguyên hạn hẹp cho các hoạt động,ví dụ quyết định đầu tư kinh doanh,phân công công việc, phân bổ tài nguyên v.v... Những hoạt động này đều liên quan đến việc đo lường và tối ưu các hiệu xuất, mục tiêu. Trong một trường hợp cụ thể nào đó, các mục tiêu có thể được tối ưu hóa một cách độc lập để đạt được kết quả tốt nhất ứng với mục tiêu đó. Tuy nhiên một kết quả chấp nhận được cho toàn bộ các mục tiêu khó có thể tìm ra theo cách đó. Bởi vì việc tối ưu hóa một mục tiêu có thể dẫn đến kết quả của một hoặc nhiều mục tiêu khác trở nên tồi tệ. Ví dụ trong việc chế tạo xe đua làm sao tìm ra được trọng lượng hợp lý của thùng xăng để xe có thể đi một khoảng đường dài mà không phải tiếp nhiên liệu (cần một lượng xăng lớn) nhưng không làm tăng nhiều khối lượng của xe (làm giảm tốc độ xe). Tuy nhiên thực tế là chưa có một định nghĩa thống nhất thế nào là tối ưu như trong bài toán một mục tiêu do đó thậm chí rất khó để ta có thể so sánh kết quả giữa các phương pháp với nhau bởi vì việc quyết định cái gì là tốt nhất rốt cuộc vẫn thuộc về người ra quyết định. A.2 Phát biểu bài toán Khi một vấn đề được đặt ra trong đó có nhiều tiêu chí, mục tiêu kèm theo.Nếu các mục tiêu xung đột với nhau và các biến quyết định có những ràng buộc với nhau thì việc đi tìm giải pháp tối ưu của vấn đề trở thành bài toán “Tối ưu hóa đa mục tiêu” Việc giải quyết bài toán tối ưu hóa đa mục tiêu được giải quyết với ý tưởng tương tự bài toán tối ưu một mục tiêu. Trong bài toán một mục tiêu để giải quyết bài toán ta phải đi tìm một tập các các biến quyết định thỏa các ràng buộc và đưa ra một kết quả tối ưu đối với hàm mục tiêu. Bài toán đa mục tiêu chỉ khác là nó phải giải quyết nhiều mục tiêu khác nhau (có thể xung đột với nhau) và thường cho ra một tập các giải pháp tối ưu hoặc không so sánh được với nhau. 63 A.3 Một số định nghĩa A.3.1 Các biến quyết định Bước đầu tiên trong quá trình tối ưu hóa là việc công thức hóa vấn đề. Một mô hình toán học cần được đưa ra để mô tả chính xác các hành vi hay giá trị của các tình huống. Nhìn chung các bài toán đa mục tiêu đều có thể biểu diễn bằng một vector các hàm trong đó ánh xạ m tham số (các biến quyết định) thành một tập n mục tiêu. Min/Max y = f(x) = (f1(x),f2(x)…fn(x)) Trong đó x=(x1, x2,… ,xm) ∈ X y=( y1, y2,… ,yn) ∈ Y x được gọi là vector quyết định bao gồm m biến quyết định . X được gọi là không gian tham số(hay không gian tìm kiếm) . y được gọi là vector mục tiêu bao gồm n mục tiêu và Y được gọi là không gian mục tiêu. A.3.2 Các ràng buộc Bước tiếp theo của việc công thức hóa vẫn đề đó là xác định các ràng buộc. Ràng buộc là những điều kiện giữa các biến quyết định mà các giải pháp cần phải thỏa. Các ràng buộc được mô tả bằng các đẳng thức hoặc bất đẳng thức. gj(x) ≤ 0 , j = 1,2,…,J hk(x) = 0 , k = 1,2,…,K A.3.3 Hàm mục tiêu Bước cuối cùng của việc công thức hóa vấn đề đó là định nghĩa các hàm mục tiêu. Đây chính là con số mà người thiết kế cần tối ưu hóa. Các hàm này được biểu diễn dưới dạng: f(x)=(f1(x),f2(x),…,fn(x)) A.3.4 Dạng chuẩn của vấn đề Một vấn đề được công thức hóa có dạng chuẩn như sau min/max {f(x):h(x)=0,g(x) ≤0} => x ∈ Rn Công thức trên có thể được diến đạt như sau: tìm một tập các giá trị R của vector quyết định sao cho hàm mục tiêu đạt giá trị nhỏ nhất (lớn nhất) và thỏa các ràng buộc là các dẳng thức h(x) và bất đẳng thức g(x). 64 A.4 Miền tối ưu Pareto A.4.1 Giới thiệu Trong bài toán tối ưu đa mục tiêu, ta mong muốn tìm được một tập giá trị các biến quyết định nhằm tối ưu các hàm mục tiêu. Tập các biến quyết định cho ta một kết quả tối ưu được gọi là một tập tối ưu và được ký hiệu là x*. Miền tối ưu Pareto là một tập hợp chứa các tập tối ưu mà từ đó ta có thể chọn ra các giá trị mong muốn (tối ưu). A.4.2 Tối ưu pareto Mieàn khaû thi C A B C1 f1 f2 Hình 7.1 - Miền tối ưu Pareto. Như hình trên miền tối ưu Pareto (đường tô đậm) là một tập hợp các điểm nếu di chuyển từ điểm này (ví dụ điểm A) đến điểm kia (ví dụ điểm B) trong tập hợp làm cho một mục tiêu bị giảm thì phải có ít nhất một mục tiêu khác tăng lên và ngược lại. Nói cách khác một vector xv = f(xv)=(v1,v2,…,vn) thuộc một tập P được gọi là thuộc miền tối ưu Pareto khi và chỉ khi không tồn tại một vector quyết định xu = f(xu) = (u1,u2,…un) nào thống trị xv ,nghĩa là ∀ i ∈{1,…,n}, ui ≤ xi và ∃ i ∈ {1,…,n}, ui<xi Như ở hình trên thì A,B,C1 thuộc miền tối ưu Pareto nhưng C thì không, vì C bị thống trị bởi C1. Một phương án x* không bị thống trị bởi một phương án nào cả sẽ thuộc về miền tối ưu Pareto. Do vậy việc giải bài tóan tối ưu hóa đa mục tiêu là chọn ra từ miền Pareto của bài 65 toán một hay một số các phương án tốt nhất theo một nghĩa nào đó dựa trên cơ cấu ưu tiên của người ra quyết định. A.5 Cách tiếp cận bài toán đa mục tiêu giựa trên thuật giải di truyền A.5.1 Giới thiệu Khái niệm về áp dụng thuật toán di truyền vào bài toán đa mục tiêu đã xuất hiện vào những năm 60 trong một nổ lực nghiên cứu của Rosenberg (1967). Ông đã đề xuất sử dụng nhiều thuộc tính trong việc mô phỏng các gene và quần thể các sinh vật dơn bào. Thật ra trong cài đặt của mình ông chỉ sử dụng một thuộc tính và cách tiếp cận đa mục tiêu không thể thấy được trong cài đặt của ông nhưng nó đã trở thành điểm xuất phát cho việc áp dụng giải thuật di truyền vào bài toán tối ưu đa mục tiêu. Chúng ta biết rằng thuật toán di truyền (xem phụ lục B) cần thông tin về độ thích nghi để làm việc. Có lẽ ý nghĩ đơn giản và tự nhiên nhất đó là kết hợp các mục tiêu lại làm một bằng cách sử dụng các phép toán đại số. Cách tiếp cận này đòi hỏi chúng ta phải cung cấp các thông tin về tầm mức của các mục tiêu. Điều này đòi hỏi chúng ta phải biết về hành vi, hoạt động của các hàm mục tiêu, đây không phải là một tiến trình đơn giản. Với cách kết hợp các mục tiêu lại với nhau, rõ ràng đây không phải là cách đơn giản nhất nhưng có lẽ là một trong những cách hiệu quả nhất bởi vì nó không đòi hỏi phải giao tiếp với người ra quyết định thêm lần nào nữa trong khi thuật toán đang được thực hiện. Và nếu GA kết thúc bằng một kết quả thích nghi tối ưu thì kết quả này ít nhất sẽ thuộc về một tập các giải pháp tối ưu trong đa số trường hợp. Cách tiếp cận kết hợp các mục tiêu lại đưa về bài toán một mục tiêu là một trong các cách được biết đến nhiều nhất trong việc giải bái toán tối ưu đa mục tiêu vì tính hiệu quả của nó. Một số cách tiếp cận theo cách trên đã được đề ra như tổng trọng số, hướng mục đích và tối ưu Min-Max. A.5.2 Cách tiếp cận tổng trọng số (Weighting objective) Phương pháp này chúng ta sẽ cộng các hàm mục tiêu lại với nhau và sử dụng các trọng số đối với từng mục tiêu, trọng số này thể hiện sự tương quan về độ quan trong của các mục tiêu. Với cách này các giải pháp trên miền Pareto (vốn không so sánh được với nhau) sẽ có thể đánh giá và so sánh được. Khi đó vấn đề của chúng ta sẽ được chuyển thành dạng: 66 ∑ = k i ii xfw 1 )(min hoặc ∑ *)(min iii cxfw Trong đó wi ≥ 0 là các trọng số mô tả mối tương quan độ quan trọng giữa các mục tiêu.Và thường được tạo với cách: ∑ = = k i iw 1 1 Và *ic là một hằng số với ** 1 ii fc = và *if là giá trị tối ưu của hàm mục tiêu if . Rõ ràng kết quả của bài toán sẽ thay đổi khi các hệ số trọng số thay đổi, và thông thường các trọng số này khó được xác định do đó cần một cách tiếp cận khác khi chúng ta phải sử đụng nhiều giá trị trọng số khác nhau. Nhưng trong trường hợp các trọng số được xác định bởi người ra quyết định giựa trên trực giác của mình thì cách này vẫn tỏ ra có hiệu quả. A.5.3 Cách tiếp cận hướng mục đích (Goal programming) Cách tiếp cận này được đưa ra và đã đóng một vai trò then chốt trong các ứng dụng trong lĩnh vực công nghiệp.Trong phương pháp này người ra quyết định phải xác định mục đích mà mỗi mục tiêu cần đạt được. Các hàm mục tiêu sẽ cố gắng tìm cách làm tối thiểu hóa khoảng cách giữa giá trị hiện đạt được của mục tiêu với giá trị đích mà người ra quyết định mong muốn đạt được. Hình thức đơn giản nhất của phương pháp này là: FxTxf k i ii ∈−∑ = ,|)(|min 1 Trong đó iT là giá trị đích mà người ra quyết định mong muốn đạt được ở hàm mục tiêu thứ i, F là vùng khả thi.Trong đó mục tiêu của ta bây giờ là làm tối thiểu hóa khoảng cách giữa giá trị đích và giá trị thực sự mà mục tiêu đạt được. Phương pháp này sẽ cho ra một giải pháp đôi khi bị thống trị bởi một giải pháp khác nếu đích cần đạt được nằm trong vùng khả thi. Đây có thể là một cách tiếp cận rất hiệu quả nếu chúng ta biết được giá trị đích mà chúng ta mong đợi và giá trị đó nằm trong vùng 67 khả thi. Tuy nhiên người ra quyết định vẫn phải cung cấp các trọng số ưu tiên của các mục tiêu để cho các giải pháp có thể so sánh được, và trong nhiều trường hợp điều này rất khó thực hiện nếu không biết trước được hình dáng của không gian tìm kiếm. A.5.4 Các cách tiếp cận khác Một số cách tiếp cận khác để giải bài toán tối ưu đa mục tiêu khác cũng giựa trên thuật giải di truyền như Min-Max, ràng buộc ε, VEGA… A.5.5 Cách tiếp cận ràng buộc ε A.6 Tổng kết Mặc dù rất nhiều nổ lực được đưa ra để giải quyết bài toán tối ưu đa mục tiêu, tuy nhiên hầu hết đều nhằm để giải quyết các vấn đề cụ thể nào đó và chưa có một phương thức nào tỏ ra có hiệu quả trong tất cả các vấn đề. Và cũng chưa có phương cách nào để so sánh tính hiệu quả của các phương pháp.Do đó để muôn áp dụng thuật toán di truyền để giải quyết một bài toán tối ưu đa mục tiêu thì có rất nhiều chuyện để làm như kích thứoc một quần thể, biểu diễn các biến quyết định, các thao tác của thuật toán như lai ghép, đột biến. Mặc dù độ phức tạp khi cài đặt thuật toán khá cao nhưng do kết quả mà nó đem lại rỏ ràng rất ấn tượng. Do đó việc áp dụng thuật toán di truyền để giải quyết bài toán tối ưu đa mục tiêu đang được ngày càng quan tâm và phát triển. 68 Phụ lục B Thuật giải di truyền B.1 Tổng quát về thuật giải di truyền Các khái niệm cơ bản của Thuật giải di truyền (Genetic Algorithm-GA) lần đầu tiên được đưa ra bởi Holland [29] vào những năm 70. GA hoạt động dựa trên cơ chế chọn lọc tự nhiên được đề xuất bởi nhà bác học Darwin. Theo cơ chế này, những cá thể thích nghi hơn sẽ tồn tại, và được gọi là “quy luật tồn tại của sự thích nghi”.Tương tự như vậy, thuật giả GA cũng sử dụng cơ chế chọn lọc tự nhiên, theo cách đó những giải pháp tối ưu sẽ được tồn tại qua các tiến trình của thuật giải .Nhìn chung thuật giải GA bao gồm các yếu tố :biểu diễn số,tính toán độ thích nghi,chọn lọc và các thao tác di truyền .Một thuật giải GA tổng quát có dạng như sau: Tạo nhẫu nhiên quần thể ban đầu P(0), đặt i=0 Lặp Định giá độ thích nghi của từng cá thể trong P(i) Chọn các cặp bố mẹ dựa trên độ thích nghi của các cá thể P(i) Thực hiện các hàm lai ghép và đột biến trên các các cập bố mẹ đã chọn để tạo ra thế hệ tiếp theo Cho đến khi “tiêu chuẩn dừng” thỏa mãn. B.2 Biểu diễn một giải pháp dưới dạng gen Theo GA mỗi giải pháp cho một vấn đề đều có thể biểu diễn dưới dạng một tấp hợp các tham số. Các tham số này đóng vai trò như các gene trong một nhiễm sắc thể, và có thể biểu diễn dưới dạng một dạng chuỗi các bit số học. Mỗi nhiễm sắc thể được mã hóa từ một giải pháp được gọi là “kiểu di truyền” và giải pháp được mã hóa đó được gọi là một “kiểu hình”. Biểu diễn một vấn đề được dưới dạng gene luôn là phần quan trọng nhất của thuật giải di truyền. B.3 Tính độ thích nghi Một số thực dùng để phản ánh độ tốt của nhiễm sắc thể được gọi là “độ thích nghi”.Nó dùng để diễn tả giá trị mục tiêu của nhiễm sắc thể. Việc tính toán độ thích nghi dùng để xác định chất lượng của một nhiễm sắc thể đối với một mục tiêu của kiểu hình. 69 B.4 Chọn lọc tự nhiên Sau khi tính toán độ thích nghi những nhiễm sắc thể (NST) tốt hơn sẽ có nhiều cơ hội sống sót và di truyền sang thế hệ sau hơn. Trong các ứng dụng GA quần thể ban đầu phải được khởi tạo, các nhiễm sắc thể sẽ được khởi tạo ngẫu nhiên. Kích thước của quần thể thay đổi theo từng bài toán cụ thể. Trong mỗi chu trình tiến hóa, một số cặp NST sẽ được chọn lọc để nhân giống, tạo ra thế hệ kế tiếp. B.5 Những hoạt động di truyền Trong quần thể các cặp gene bố mẹ được chọn sẽ được trộn lẫn và kết hợp lại để tạo ra các cặp gene thế hệ con. Thao tác như vậy gọi là “lai ghép” . Hình B.1 - Lai ghép trong thuật toán di truyền. Thao tác ”đột biến” được thực hiện với tần số thấp để tạo ra các gene mới cho quần thể. Đột biến được thực hiện bằng cách thay đổi ngẫu nhiên một gene trong NST Hình B.2 - Thao tác đột biến trong thuật toán di truyền. B.6 Điều kiện dừng Các vòng lặp của thuật giải sẽ kết thúc khi gặp điều kiện dừng. Các điều kiện dừng có thể như: 70 • Đạt số vòng lặp tối đa. • Đạt độ thích nghi tối đa. • Quá thời gian thực hiện. • Đạt ngưỡng tài nguyên. 71 Tài liệu tham khảo [1] Nguyễn Tấn Trần Minh Khang, Giải thuật di truyền trong một lớp bài tóan lập lịch, Luận Văn Thạc sĩ Khoa Học CNTT, 2002. [2] Nguyễn Hòang Tú Anh, Nghiên cứu và phát triển thuật tóan tìm luật kết hợp tối ưu trên thuộc tính số, Luận Văn Thạc sĩ Khoa Học CNTT, 2002. [3] Ngô Quang Tuấn Huy, Xây dựng hệ thống giải lớp bài tóan tôi ưu số trên cơ sở thuật giải di truyền, Luận Văn Cử Nhân CNTT, 2002. [4] DSS Glossary, [5] Gorry,G.A, Scott Morton, A framework for Management Information Systems , Sloan Management Review, Vol 13, No 1, (1971). [6] Efraim Turban và Jay E Aronson, Decision Support Systems and Intelligent Systems [7] Management Information Systems for the Information Age [8] Susan Sproule và Norm Archer, Knowledgeable Agents For Search And Choice Support In E-Commerce: A Decision Support Systems Approach, [9] Bing Xu, Zhi-geng Pan và Hong-wei Yang, Agent-based Model for Intelligent Shopping Assistant and its Application ccd13cce.pdf [10] Filippo Menczer và các cộng sự, IntelliShopper: A Proactive, Personal, Private Shopping Assistant. [11] Nguyễn Đình Thúc, Trí tuệ nhân tạo : Lập trình tiến hóa, Nhà xuất bản giáo dục, Tp HCM, 2001. [12] Hoàng Kiếm và Nguyễn Đình Thúc, Về sự hội tụ của hồi quy di truyền, Hội nghị khoa học trường ĐHKHTN lần 2 , 2000. [13] Bùi Thế Tâm và Trần Vũ Thiên, Các phương pháp tối ưu hóa , NXB Giao thông Vận tải, 1998. 72 [14] Carlos A Coello, A comprehensive survey of evolutionary-based multiobjective optimization techniques, [15] Carlos M Fonseca và Peter J Fleming, Genetic Algorithms for multiobjective optimization: Formulation, Discussion and Generalizations [16] Barry G. Silverman, Mintu Bachann, Khaled Al-Akharas (Dept. of Systems Engineering, University of Pennsylvania),Implications of Buyer Decision Theory for Design of eCommerce Websites,2001,pp.24. [17] J. Ben Schafer, Joseph A. Konstan, John Riedl(Department of Computer Science and Engineering University of Minnesota),E-Commerce Recommendation Applications,2004. [18] Jochen Hansen, How new and different are consumer in the digital marketplace?, The Impact of Networking,Vienna Austria,tháng 9 năm 2000.