phần mở đầu, phần kết luận và tài liệu tham khảo, nội dung luận văn được chia thành 3 chương: Chƣơng I: Tối ƣu đa mục tiêu và giải thuật di truyền- Trình bày các khái niệm cơ bản về tối ưu đa mục tiêu, thuật giải di truyền. Chƣơng II: Tối ƣu đa mục tiêu trong mua hàng trực tuyến. Trình bày các khó khăn khi xây dựng một module hỗ trợ khách hàng lựa chọn sản phẩm, cách Tối ưu đa mục tiêu sử dụng giải thuật di truyền với bài toán hỗ trợ người mua hàng trực tuyến lựa chọn sản phẩm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 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, 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 III.
Xây dựng website bán hàng trực tuyến – Chương này làm rõ hơn các vấn đề của các chương trước bằng một bài toán cụ thể - bài toán bán hàng trực tuyến máy tính xách tay có hỗ trợ người dùng lựa chọn sản phẩm, sử dụng giải thuật di truyền và tối ưu đa mục tiêu. Tối ưu đa mục tiêu sử dụng giải thuật di truyền với bài toán hỗ trợ người mua hàng trực tuyến lựa chọn sản phẩm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 PHẦN II: NỘI DUNG CHƢƠNG I BÀI TOÁN TỐI ƢU ĐA MỤC TIÊU VÀ GIẢI THUẬT DI TRUYỀN 1. Bài toán tối ƣu đa mục tiêu. Sự ra đời bài toán tối ƣu Tất cả các lĩnh vực như kỹ thuật, khoa học, kinh doanh đề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.
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. 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 Tối ưu đa mục tiêu sử dụng giải thuật di truyền với bài toán hỗ trợ người mua hàng trực tuyến lựa chọn sản phẩm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 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. Một số định nghĩa 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. Y được gọi là không gian mục tiêu. 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 Tối ưu đa mục tiêu sử dụng giải thuật di truyền với bài toán hỗ trợ người mua hàng trực tuyến lựa chọn sản phẩm LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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)) 1. 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 đẳng thức h(x) và bất đẳng thức g(x). Miền tối ƣu Pareto 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). [3] Tối ưu đa mục tiêu sử dụng giải thuật di truyền với bài toán hỗ trợ người mua hàng trực tuyến lựa chọn sản phẩm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Tối ƣu pareto Miền khả thi Hình 1.
Miền tối ưu Pareto.1 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 1.1 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 toán tối ưu hóa đa mục tiêu là chọn ra từ Tối ưu đa mục tiêu sử dụng giải thuật di truyền với bài toán hỗ trợ người mua hàng trực tuyến lựa chọn sản phẩm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 miền Pareto của bài 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.
Cách tiếp cận bài toán đa mục tiêu dựa trên thuật giải di truyền 1.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 đơ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 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.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ề Tối ưu đa mục tiêu sử dụng giải thuật di truyền với bài toán hỗ trợ người mua hàng trực tuyến lựa chọn sản phẩm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 16 độ quan trọng 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.