Luận văn Phân tích thiết kế hệ thống trang web bán hàng và hỗ trợ khách hàng chọn sản phẩm

cũng dễ hiểu bởi không thể đề nghị khách hàng mua một quyển sách trong khi 15 họ đang tìm mua một máy điện thoại. Chúng ta sẽ tập trung vào hệ thống hỗ trợ trong mua bán sách của Amazon.com. Danh mục sách đề nghị mua (persionalized recommendation): Như nhiều website E- commerce khác, Amazon.com được cấu trúc với các trang thông tin cho mỗi quyển sách, đem lại các thông tin chi tiết về nội dung và mua bán. Danh sách các quyển sách đề nghị mua kèm được thấy ở trang thông tin của mỗi cuốn sách. Thật sự, nó gồm hai danh sách đề nghị riêng biệt. Phần thứ nhất gồm danh sách những quyển sách thường mua nhất. Phần thứ hai là danh sách các tác giả của những quyển sách thường xuyên được mua. Mọi hoạt động duyệt danh mục sách, thêm hàng vào giỏ của người dùng đều được website ghi nhận để làm cơ sở cho việc đưa ra các đề nghị này. Ý kiến của bạn (Your Recommendation): Amazon cũng khuyến khích khách hàng phản hồi trực tiếp các cuốn sách mà họ đã đọc. Khách hàng đánh giá các cuốn sách họ đã đọc trên thang điểm 5 từ “hated it” đến “loved it”. Những đánh giá này sẽ được dùng như là đầu vào cho một cơ chế đề nghị (recommendation engine). Do đó, khi đánh giá càng nhiều quyển sách, khách hàng sẽ nhận được lời đề nghị càng chính xác. Hình dưới cho phép ta xem việc đánh giá của khách hàng là lý do để Amazon đưa ra các đề nghị đối với các quyển sách khác. Ví dụ khi ta đánh giá quyển “A Road Ahead” của Bill Gates thì Amazon đề nghị ta một quyển sách khác cũng của Bill Gates là “Bussiness @ the Speed of Thought”. Hình 3.1 - Amazon đưa ra lý do vì sao các lời đề nghị được đưa ra. Email Notification: Đặc tính này cho phép customers được biết qua email các sản phẩm mới đã thêm vào catalog của Amazon.com. Nhận xét của khách hàng (Customer Comments): Nhận xét của khách hàng cho phép khách hàng nhận được các đề xuất dạng văn bản dựa trên ý kiến của các khách hàng khác. 16 Mỗi một trang thông tin cụ thể về một cuốn sách là đánh giá dựa trên thang điểm 5 biểu hiện bằng hình ngôi sao và các lời nhận xét của những người đã đọc quyển sách và đưa ra lời bình. Khách hàng cũng có sự chọn lựa các kết hợp giữa các đề xuất này trong quyết định mua của họ. Hơn nữa, khách hàng có thể đánh giá các nhận xét này. Với mỗi lời bình có một câu hỏi “Did this comment help you? ” và khách hàng có thể chọn là “có” hoặc “không” (yes hoặc no). Kết quả sẽ được liệt kê vào bảng và đưa ra 5 trong 7 người tìm được các lời nhận xét có ích. 3.4.1.b 3.2.2 MovieFinder.com MovieFinder.com là trang web phim ảnh được quản lý bởi E!Online. MovieFinder hỗ trợ người dùng qua các sắp xếp các phim theo đánh giá của chính họ và đánh giá của khách hàng theo các mức từ A đến F. Các đánh giá của người dùng về các phim họ đã xem thể hiện ở mục Users Grade. Còn mục Our Grade là đánh giá của những người biên tập trang web. Hình 3.2. dưới cho ta thấy bộ phim “Kingdom of Heaven” được đánh giá B+ ở cả hai mục Our Grade và Users Grade. Đối với người dùng đã đăng ký có thể được đánh giá trực tiếp tại đây. Hình 3.2 - Đánh giá phim ở movifinder.com 3.4.1.c Carsdirect.com Carsdirect là một cửa hàng bán xe hơi trên Web, được thành lập vào năm. Carsdirect đưa ra một danh mục sản phẩm theo hướng tiếp cận với nhu cầu của người dùng. Trang Research (xem hình 3.3) cho phép chọn xe theo mục đích sử dụng của người mua: xe chở khách, xe cao cấp, xe tải nhẹ, xe cũ v.v… 17 Hình 3.3 - Trang Research. Khi chọn một loại xe, trang web tiếp tục đưa người dùng chọn đến danh mục phân loại ở cấp dưới. Cứ thế người dùng sẽ nhận được danh sách các xe ở danh mục đã chọn. Vấn đề là danh sách này khá dài. Do đó, các công cụ hỗ trợ xem thông tin như car review (xem mô tả xe), compare car compare (so sánh xe) để tiếp tục tìm một chiếc xe phù hợp nhất. Các duyệt qua danh này khá rờm rà nhưng cũng đáng để khách hàng bỏ thời gian tìm kiếm cho mình chiếc xe ưng ý nhất. Hình 3.4 - Danh mục xe ở loại xe chở khách. 3.4.1.d ActiveDecisions.com Trong môi trường mua bán qua mạng, người dùng thường không thể đánh giá tất cả các tiêu chuẩn so sánh ở mức sâu. Việc này đòi hỏi nhiều thời gian và thao tác phức tạp. Do đó các trang web đưa ra kịch bản xử lý theo 2 bước để đạt được sự hỗ trợ khách hàng ở mức sâu. Bước đầu tiên, khách hàng thường được đưa ra một bộ gồm nhiều các sản phẩm và chỉ ra một bộ con các lựa chọn tốt. Sau đó, các lựa chọn này sẽ được đánh giá ở độ sâu 18 hơn, thực hiện các so sánh các sản phẩm trên các thuộc tính quan trọng và ra quyết định mua. Một chương trình đóng vai trò là người đề nghị (Recommender Agent-RA) sẽ trợ giúp cho khách hàng trong bước đầu tiên, đưa ra các sản phẩm lựa chọn. Dựa vào các thông tin cung cấp đã khảo sát trước hoặc chính từ người mua hàng đối với sở thích của họ mà RA sẽ đề xuất một bộ sản phẩm hấp dẫn nhất đối với cá nhân đó. Các hướng tiếp cận sở thích người dùng có thể chia ra thành hai nhóm: hướng đặc tính và hướng nhu cầu. Một hệ thống theo hướng đặc tính thường yêu cầu khách hàng chỉ ra các sở thích về đặc tính của sản phẩm như: môt máy chụp ảnh kỹ thuật số phải có độ phân giải ít nhất là 4 Mega Pixel. Các tiếp cận nhu cầu sẽ hỏi người dùng chỉ ra “Nhu cầu cá nhân của họ là gì?”. Ví dụ tôi cần chụp ảnh ngoại cảnh. Cách tiếp cập theo hướng nhu cầu nên là một phương pháp phù hợp để hỗ trợ cho người dùng chưa có kinh nghiệm chọn sản phẩm. Active Decisions Inc. là nhà cung cấp hàng đầu thế giới các giải pháp hướng dẫn mua hàng. Ứng dụng cung cấp bởi Active Decisions đem lại cho bộ phận mua hàng, các chi nhánh và các ứng dụng tự phục vụ mục tiêu là lôi kéo càng nhiều khách hàng. Kỹ thuật chính của Acitve Decisions được xem như là sự kết hợp của Recommender Agent (RA) và ma trận so sánh (Comparison Matrix-CM). Ma trận so sánh, sự trợ giúp tạo quyết định dạng thứ hai, là công cụ tương tác được đưa ra nhằm giúp người dùng trong các so sánh ở mức sâu hơn giữa các sản phẩm đã chọn ở bước một. Một dạng cơ bản của hướng trợ giúp ra quyết định này, thích hợp như một giỏ hàng hiển thị một ma trận các hàng là các sản phẩm và các cột là các thuộc tính quan trọng của sản phẩm. Thiết kế này cho phép người mua so sánh các giá trị của sản phẩm hiệu quả và chính xác hơn. Các bước tiếp cận của kỹ thuật này thì đầu tiên khách hàng sẽ được hỏi họ tìm cái gì và cái gì là quan trọng với họ thông qua các hướng tiếp cận theo nhu cầu hay theo đặc tính, dựa vào đó đưa ra các đề xuất thích hợp cho khách hàng. Khách hàng sẽ chọn một vài sản phẩm đưa ra để so sánh ở mức cao hơn trong ma trận so sánh. Những sản phẩm được đề nghị cũng hiển thị với lời giải thích tại sao nó tốt cho người dùng. Một vài giải pháp của Active Decision sẽ được thấy ở các website www.absound.ca, www.qvc.com , www.sonystyle.com, www.jr.com và www.hpshopping.com. Chúng ta sẽ khảo sát một ví dụ của Active Decision ở website Hpshopping.com. 19 3.4.1.e Hpshopping.com Hpshopping là một trang web giới thiệu các sản phẩm của hãng HP bao gồm máy tính, máy PDA, máy in. Trong phần này, chúng ta tập trung vào trang chọn mua máy in (printer). Các câu hỏi chuyên về tính năng sử dụng của máy in như số trang in, cỡ trang in thường dùng, cổng kết nối với máy tính, hệ điều hành của máy tính v.v… Kết quả là ba sản phẩm thích hợp nhất được hiển thị ở ma trận so sánh với cột là các sản phẩm và dòng là các thuộc tính của sản phẩm máy in. Trong một số trường hợp HPShopping còn đưa ra một kết quả mạnh hơn yêu cầu của người dùng. Kết quả này là một máy in không chỉ có đủ các đặc tính theo yêu cầu của người dùng mà còn có thêm một số tính năng khác. Hình 3.5 - Các câu hỏi về đặc tính máy in. 20 Hình 3.6 - Các sản phẩm đề nghị của HP sau khi chọn trả lời cho các câu hỏi. 3.4.1.f Samsungtelecom.com Đây là trang hỗ trợ khách hàng tìm kiếm sản phẩm theo nhu cầu của khách hàng qua các câu hỏi cho người dùng lựa chọn. Nếu như ở website hpshopping.com các câu hỏi tập trung vào “Sản phẩm cần tìm có đặc điểm gì?“ thì ở đây các câu hỏi tập trung vào “Người dùng cần mua sản phẩm để làm gì?”. Dựa vào các lựa chọn của khách hàng website đưa ra các điện thoại phù hợp với người dùng. Cuối cùng, sau quá trình đề xuất các sản phẩm thích hợp, trang web sẽ hỏi ý kiến người dùng có thỏa mãn với những sản phẩm được đề xuất hay chưa. 21 Hình 3.7 - Các câu hỏi của samsungtelecom.com. 3.4.1.g Shopping.Yahoo.com/Smartsort Shopping.yahoo.com là một trong những hệ thống mua sắm lớn nhất hiện nay. Ngoài các tính năng hỗ trợ tìm kiếm thông thường như duyệt theo catalog, cho khách hàng đánh giá trên sản phẩm đã mua, người dùng còn có thể tìm các sản phẩm theo sở thích, mục đích sử dụng qua tính năng Smartsort có trên trang web Yahoo!Shopping gồm nhiều loại mặt hàng trong đó phần Smartsort hỗ trợ các mặt hàng đồ điện tử như điện thoại di động, digital camera, PDA, máy tính v.v… Phần khảo sát này ta tập trung vào mặt hàng điện thoại di động. Tính năng Smartsort của Yahoo!Shoppping hỗ trợ người dùng chọn mức độ quan trọng của các thuộc tính sản phẩm qua thanh kéo (slider bar). Người dùng đánh giá độ quan trọng của các đặc tính trên máy điện thoại di động như thời gian dùng pin, kích cỡ, nhà sản xuất, các tính năng giải trí khác v.v… Yahoo đưa ra 5 mức đánh giá độ quan trọng đối với tính năng của điện thoại di động như sau: không quan trọng (not important), ít quan trọng (sightly important), quan trọng (important), rất quan trọng (very important), hết sức quan trọng(most important). Kết quả đưa ra là 10 máy điện thoại di động được sắp xếp theo độ quan trọng của các tính năng đã đánh giá trước đây. Trong danh sách các máy điện thoại đưa ra người dùng có thể tiếp tục chọn vào danh sách so sánh tiếp theo. Một ma trận so sánh sẽ đưa ra giúp khách hàng dễ dàng so sánh. 22 Hình 3.8 - Đánh giá độ quan trọng của các thuộc tính với SmartSort. 3.4.2 Bảng tóm tắt và so sánh Bảng 3.3 - Tổng kết so sánh website STT Website Đặc điểm Mức hỗ trợ đạt được 1 Amazon.com Các đặc tính hỗ trợ rất phong phú, hỗ trợ người dùng ở nhiều giai đoạn như tìm kiếm, hướng dẫn mua. 3 2 Moviefinder.com Chỉ có 2 đặc điểm đơn giản là danh sách “Top 10” và đánh giá điểm cho mỗi phim. 2 3 Carsdirect.com Catalogue danh mục các xe chứa theo nhu cầu người mua. 2 4 Samsungtelecom.com Danh sách các câu hỏi được đưa ra nhằm đánh giá nhu cầu người dung. Danh sách kết quả là ma trận so sánh khá hợp đã được sắp xếp. - 5 HpShopping.com Danh sách câu hỏi đưa ra cho khách hàng và ma trận so sánh của danh sách sản phẩm được đề nghị có nội dung và cách trình bày tốt. 3 6 Shopping.yahoo.com/ Smartsort Danh sách đánh giá độ quan trọng các tiêu chuẩn của sản phẩm đưa ra kết quả ngay lập tức. 3 3.5 Các tiện ích mà một trang web bán hàng cần cung cấp để có thể Hỗ trợ khách hàng tốt hơn Qua các phần thống kê bên trên chúng ta thấy rằng “hỗ trợ khách hàng” vẫn là một sự thiếu hụt nghiêm trọng của các trang web bán hàng hiện nay. 23 Theo một cuộc khảo sát các người thường xuyên mua hàng qua mạng thì các tiện ích hỗ trợ khách hàng đóng vai trò then chốt trong việc gia tăng số lượng mua hàng qua mạng. Các tiện ích mà các cửa hàng trên mạng cần cung cấp (tốt hơn) • Giá cả và hỗ trợ so sánh giá cả. • Tính bảo mật của các giao dịch. • Các dịch vụ hỗ trợ khách hàng trong việc mua và hoàn trả hàng hóa. • Hỗ trợ khách hàng tìm kiếm, chọn lựa sản phẩm. 24 Chương 4 Sử dụng giải thuật di truyền để giải quyết bài toán hỗ trợ chọn sản phẩm khi mua hàng qua mạng 4.1 Giới thiệu Để xây dựng được một trang web bán hàng thật sự hoàn hảo đó là sự kết hợp của rất nhiều yếu tố bao gồm sự quảng bá đến người dùng, giao diện người dùng, các tiện ích hỗ trợ khách hàng khi mua hàng, các dịch vụ giao hàng và hoàn trả hàng. Trong khuôn khổ luận văn, chúng em cố gắng đưa ra một cách tiếp cận để xây dựng một trong những yếu tố trên “hỗ trợ khách hàng chọn sản phẩm khi mua hàng qua mạng”. Chọn sản phẩm là một trong những phần quan trọng nhất khi mua hàng. Như chương trước đã phân tích một trong những nguyên nhân chính dẫn đến sự không thành công của phương thức mua hàng qua mạng đó là người mua không thể chọn ra được một sản phẩm ưng ý nhất trước vô vàn các mặt hàng được bày ra. Vậy trang web chúng ta xây dựng phải có nhiệm vụ như một người bán hàng chuyên nghiệp đó là nắm bắt các nhu cầu của người mua và khuyến cáo cho người mua một số sản phẩm mà mình cho là thích hợp. Mặc dù quyết định cuối cùng vẫn thuộc về người ra quyết định, ở đây là người mua hàng, tuy nhiên một lời khuyên cho người dùng vẫn rất quan trọng. 4.2 Các khó khăn khi xây dựng một module hỗ trợ khách hàng chọn sản phẩm Các khó khăn phi kỹ thuật: • Không giống như một người bán hàng thực, một người bán hàng có thể qua cách ứng xử, ăn mặc, thái độ v.v của người mua mà có thể chọn ra các mặt hàng cho phù hợp. Trang web bán hàng hoàn toàn không biết gì về các thông tin trên của khách hàng. • Người mua có thể tự do tương tác, trao đổi với người bán để nói lên nhu cầu, sở thích của mình. Trong khi mua hàng trên mạng thì yếu tố thời gian là rất quan trọng, cần phải dung hòa giữa lượng thông tin cần thu thập và thời gian tiêu tốn của người dùng. • Trao đổi bằng ngôn ngữ tự 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