zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Ứng dụng giải thuật di truyền để tìm kiếm tài liệu trong kho dữ liệu

Chia sẻ: Minh Minh | Ngày: | Loại File: PDF | Số trang:10

Báo xấu

50
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Kho dữ liệu đóng một vai trò quan trọng trong việc lưu trữ, phân tích và cung cấp thông tin. Các kho dữ liệu đều chứa nhiều thông tin hữu ích cung cấp cho các hệ trợ giúp quyết định. Việc tìm và đưa ra những tài liệu cần thiết từ kế hoạch xử lý đa dạng của hệ thống đã tạo ra những thách thức khi nghiên cứu về kho dữ liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Ứng dụng giải thuật di truyền để tìm kiếm tài liệu trong kho dữ liệu

JOURNAL OF SCIENCE OF HNUE FIT., 2011, Vol. 56, pp. 102-111 ỨNG DỤNG GIẢI THUẬT DI TRUYỀN ĐỂ TÌM KIẾM TÀI LIỆU TRONG KHO DỮ LIỆU Nghiêm Thị Lịch(∗) Khoa Tin học thương mại, Trường Đại học Thương mại Nguyễn Tân Ân Khoa CNTT - ĐHSP Hà Nội (∗) Email :lichnt72@gmail.com Tóm tắt. Kho dữ liệu đóng một vai trò quan trọng trong việc lưu trữ, phân tích và cung cấp thông tin. Các kho dữ liệu đều chứa nhiều thông tin hữu ích cung cấp cho các hệ trợ giúp quyết định. Việc tìm và đưa ra những tài liệu cần thiết từ kế hoạch xử lý đa dạng của hệ thống đã tạo ra những thách thức khi nghiên cứu về kho dữ liệu. Vấn đề này là bài toán lớp NP khó [4]. Một số tác giả đã dùng các giải thuật heuristic để giải. Dưới đây, chúng tôi trình bày cách ứng dụng giải thuật di truyền để giải quyết bài toán đặt ra. Những vấn đề như mã hóa cá thể, các toán tử trong giải thuật trong trường hợp cụ thể này cũng được đề cập đến. Từ khóa: Kho dữ liệu, Giải thuật di truyền, Khai phá dữ liệu. 1. Giới thiệu Hiện nay, do sự phát triển nhanh chóng của khoa học kỹ thuật và sản xuất, mỗi ngày đều có rất nhiều thông tin mới. Cũng nhờ các thành tựu của khoa học kỹ thuật, các thiết bị lưu trữ thông tin cũng ngày càng có thể lưu trữ lượng thông tin lớn và đa dạng. Cùng với việc tăng không ngừng khối lượng dữ liệu, các hệ thống thông tin cũng được chuyên môn hóa, phân chia theo các lĩnh vực ứng dụng như sản xuất, tài chính, thị trường.... Như vậy, với chức năng khai thác dữ liệu có tính chất tác nghiệp, sự thành công của các hệ thống thông tin không còn là khả năng lưu trữ nữa mà là tính linh hoạt và sẵn sàng đáp lại những yêu cầu trong thực tế. Cơ sở dữ liệu (CSDL) cần đem lại những “tri thức” hơn là chính những dữ liệu đó. Các mô hình CSDL truyền thống và ngôn ngữ SQL đã tỏ ra có nhiều hạn chế khi thực hiện công việc này với các nguồn thông tin lớn. Để lấy được những thông tin có tính “tri thức” trong khối dữ liệu khổng lồ, người ta đã đi tìm những kỹ thuật có khả năng hợp nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển đổi 102
Ứng dụng giải thuật di truyền để tìm kiếm tài liệu trong kho dữ liệu thành một tập hợp các cơ sở dữ liệu ổn định, có chất lượng, chỉ được sử dụng riêng cho một vài mục đích nào đó. Các kỹ thuật đó được gọi chung là kỹ thuật tạo kho dữ liệu (data warehousing) và nơi chứa các dữ liệu có được gọi là các kho dữ liệu (data warehouse). Vấn đề đặt ra là với kho dữ liệu nhất định, hệ thống đã cung cấp các kế hoạch xử lý đa dạng, làm thế nào để chọn, đưa ra tập tài liệu liệu thích hợp với mục đích đặt ra (View Selection Problem: VSP) từ kho dữ liệu đó với chi phí thấp nhất. Điều này cũng đồng nghĩa với việc làm thế nào để chọn ra một kế hoạch truy vấn, tìm kiếm ít chi phí nhất trong số các kế hoạch xử lý đa dạng (Multiple View Processing Plan: MVPP) để đưa ra được tài liệu cần tìm. Do kho dữ liệu là lớn và dữ liệu chứa trong đó là đa dạng, kế hoạch xử lý của hệ thống phức tạp nên việc chọn ra một kế hoạch tìm kiếm nhằm đưa ra được những tài liệu cho trước với chi phí thấp nhất là bài toán khó. Theo [4] đây là bài toán NP-khó (NP-hard). Một số tác giả đã giải quyết vấn đề này nhờ các giải thuật heuristic. Bài báo này sẽ giới thiệu cách giải quyết vấn đề đặt ra bằng giải thuật di truyền (GA). 2. Nội dung nghiên cứu 2.1. Vấn đề tìm kiếm tài liệu 2.1.1. Mô hình toán học của vấn đề tìm kiếm tài liệu [6] Một MVPP để tìm kiếm, đưa ra tài liệu được cung cấp bởi hệ thống kho dữ liệu, trong đó các kế hoạch tiếp cận cục bộ cho các truy vấn riêng lẻ được hợp nhất dựa trên các toán tử được chia sẻ trên các tập dữ liệu chung. MVPP được biểu diễn như sau: M = (V, A, Caq , Cm r , fq , fu ) Trong đó V là tập các đỉnh, A là tập các cung trên V , sao cho: Với mỗi toán tử đại số quan hệ trong một cây truy vấn, với mỗi quan hệ cơ sở, và với mỗi câu truy vấn riêng biệt, ta có một đỉnh. Với v ∈ V , T (v) là quan hệ được tạo ra tương ứng với đỉnh v. T (v) có thể là quan hệ cơ sở, là kết quả trung gian hoặc kết quả cuối cùng của một truy vấn. Với một đỉnh lá bất kỳ, (tức là không có cạnh nào xuất phát từ đỉnh này), T (v) tương ứng với một quan hệ cơ sở, và được mô tả bằng cách sử dụng kí hiệu. Ký hiệu L là tập các nút lá. Với bất kỳ đỉnh v ∈ V , fu (v) là tần số cập nhật v. Với đỉnh gốc v bất kỳ, (nghĩa là không có cạnh nào đi ra ngoài đỉnh này), T (v) tương ứng với câu truy vấn toàn cục, và được mô tả bằng cách sử dụng kí hiệu. Ký hiệu R là tập các nút gốc, với mọi đỉnh thuộc V , fq (v) là tần số truy cập câu truy vấn v. Nếu T (u) tương ứng với đỉnh u cần phải được xử lý tiếp tại nút v, ta có cung 103
Nghiêm Thị Lịch, Nguyễn Tân Ân từ u tới v. Với mỗi đỉnh v, S(v) biểu diễn các nút nguồn (nút gốc) có cung trỏ tới v ; với bất kỳ v ∈ L, S(v) = 0: S ∗ {v} = S(v) ∪ { ∪ S ∗ {v ′ }} là tập các con cháu v′ ∈S(v) của v ; Với mỗi đỉnh v, D(v) biểu thị nút đích mà v được trỏ tới; với bất kỳ v ∈ R, D(v) = 0: D ∗ {v} = D(v) ∪ { ∪ D ∗ (v ′ )}} là tập các tổ tiên của v. v′ ∈D(v) Với v ∈ V , Caq (v)là chi phí của câu truy vấn q với sự truy cập T (v); Cm r (v) là chi phí duy trì T (v) dựa trên những thay đổi của quan hệ cơ sở S (v) ∩ R, nếu ∗ T (v) được lựa chọn để đưa ra. Giới thiệu lại tất cả các ký hiệu được sử dụng trong tài liệu này: - Có k truy vấn được cung cấp bởi hệ thống quản trị kho dữ liệu. - Với truy vấn q bất kỳ, có một tập các kế hoạch có thể thực hiện truy vấn. - Có n nút (biểu thức/truy vấn phụ) tham gia vào trong tất cả các kế hoạch. - Một MVPP được xây dựng bởi k kế hoạch (mỗi truy vấn biểu diễn một kế hoạch). Bây giờ, vấn đề lựa chọn tài liệu có thể được mô tả như sau: - Làm thế nào để chọn, đưa ra được một tập các tài liệu được thích hợp từ một MVPP đã cho sao cho tổng chi phí xử lý các truy vấn và tổng chi phí duy trì các tài liệu được đưa ra là nhỏ nhất. - Cụ thể, cho trước một MVPP, cho M là tập các tài liệu trong MVPP được đưa ra. fq , fu tương ứng là tần số thực hiện các truy vấn và tần số cập nhật các quan hệ cơ sở. Hơn nữa cho mỗi v ∈ M, cho Caq (v) và Cm r (v) biểu thị chi phí truy cập cho truy vấn q sử dụng v và chi phí duy trì tài liệu v căn cứ vào sự thay đổi cho quan hệ cơ sở r (trong đó v ∈ R là tập các truy vấn và r ∈ L là tập các quan hệ cơ sở). Khi đó, chi phí xử lý truy vấn sẽ là: P Cqueryprocessing (v) = fq Caq (v) q∈R Và chi phí duy trì tài liệu được đưa ra sẽ là: P r Cmaintenance (v) = fu Cm (v) r∈L Ví dụ: Cho các quan hệ cơ sở và tập các truy vấn: DEPARTMENT (DNAME, DNUMBER, MGRSSN, GGRSTARTDATE) EM- PLOYEE (FNAME, LNAME, SSN, BDATE, ADDRESS, SEX, SALARY, SUPER- SSN, DNO) PROJECT (PNAME, PNUMBER, PLOCATION, DNUM) Q0: SELECT * 104
Ứng dụng giải thuật di truyền để tìm kiếm tài liệu trong kho dữ liệu FROM EMPLOYEE, DEPARTMEENT WTHUSHERE SALARY > 50000 AND DUNMBER = DNO Q1: SELECT * FROM EMPLOYEE, DEPARTMEENT, PROJECT WHERE DNO = DNUMBER AND DNUM = DNUMBER AND PNAME = ‘Intec’; Như vậy, tổng chi phí để chọn lựa tài liệu v là: P P Ctotal (v) = fq Caq (v) + r fu Cm (v) q∈R r∈L Vì vậy, tổng chi phí để lựa chọn tập các tài liệu M là Ctotal : P Ctotal (v) = Ctoal (v) v∈M Đây là mô hình toán học khả quan mô tả vấn đề lựa chọn tài liệu. VSP được giải quyết bằng các bước sau đây: Bước 1: Tạo ra MVPP tốt nhất bằng cách kết hợp các siêu biểu thức chung. Bước 2: Lựa chọn tài liệu từ tập MVPP tốt nhất. Tuy nhiên như mô tả ở trên, một số các tập tài liệu tiềm năng được đưa ra có thể sẽ bị bỏ lỡ khi lựa chọn nếu nó không nằm trong MVPP tốt nhất. Trong tài liệu này, chúng tôi đưa ra một cách tiếp cận khác để giải quyết VSP. Chúng tôi cố gắng duyệt qua tất cả MVPP như là một khả năng có thể tìm kiếm giải pháp tốt nhất cho VSP. 2.1.2. Một số ví dụ điển hình Hình 1 minh họa bốn ví dụ đơn giản của MVPP. Đây là ví dụ được lấy ra từ hệ thống kho dữ liệu mà chúng tôi mô phỏng. Các quan hệ và các thuộc tính của lược đồ cho các ứng dụng này và hai truy vấn được đưa ra ở bên dưới. Lược đồ và các truy vấn xuất phát từ 0. Trong hình 1, mỗi đồ thị là một MVPP được xây dựng bằng cách kết hợp các kế hoạch thực hiện truy vấn tiềm năng được gán nhãn ở đầu của mỗi nút truy vấn và tần số cập nhật quan hệ cơ sở được gán nhãn bên dưới mỗi nút quan hệ cơ sở. Đối với mỗi nút, không kể nút gốc (nút truy vấn) và nút lá (nút quan hệ cơ sở), đều có hai thông tin dữ liệu liên kết với nó. Dữ liệu bên trái đại diện cho toán tử truy vấn, bên phải đại diện cho chi phí tạo ra các nút trừ các quan hệ cơ sở. Con số bên trong nút (trừ nút gốc) chỉ ra số lượng các nút trung gian cần được lựa chọn. Con số giống nhau trong các MVPP khác nhau đại diện cho các toán tử tương tự. Để tính toán được chi phí, chúng tôi đưa ra các giả định như sau: - Có 10 bộ trong quan hệ DEPARTMENT. 105
Nghiêm Thị Lịch, Nguyễn Tân Ân - Có 30 bộ k trong quan hệ EMPLOYEE, và thuộc tính DNO không rỗng. - Có 20 bộ trong quan hệ PROJECT. Chi phí của sự trả lời câu truy vấn Q là số các dòng hiện tại trong bảng được sử dụng để xây dựng Q. Việc tính toán chi phí trả lời cho câu truy vấn tương tự như ở 0. Phương thức để tiến hành lựa chọn cách cài đặt và kết hợp (liên kết) toán tử là tìm kiếm tuyến tính và vòng lặp lồng nhau. Hình 1: Ví dụ về MVPP Dựa trên cơ sở các giả định ở trên, chi phí của mỗi nút toán tử ở trong hình 1 được gán nhãn ở phía bên phải của nút. Giả sử rằng một số nút trung gian được lựa chọn. Đối với mỗi truy vấn, chi phí xử lý truy vấn là tần số truy vấn nhân với chi phí truy cập truy vấn từ các nút được lựa chọn. Chi phí duy trì cho việc lựa chọn dữ liệu là chi phí sử dụng để xây dựng đưa ra tài liệu. Ví dụ, trong hình 1a, nếu nút 0 được lựa chọn để đưa ra, thì chi phí xử lý truy vấn cho Q0 và Q1 là 3*30k và 2*30.02k. Chi phí duy trì tài liệu là (8+0.5)*(300k). Tổng chi phí cho một MVPP là tổng chi phí xử lý truy vấn và duy trì tài liệu. Mục tiêu của việc giải quyết VSP là đi tìm kiếm tập các nút được lựa chọn sao cho tổng chi phí là nhỏ nhất. 106
Ứng dụng giải thuật di truyền để tìm kiếm tài liệu trong kho dữ liệu 2.2. Ứng dụng giải thuật di truyền để tìm kiếm tài liệu Giải thuật di truyền cổ điển là các kỹ thuật phỏng theo quá trình thích nghi tiến hoá của các quần thể sinh học dựa trên học thuyết Darwin [1, 3]. Tư tưởng của giải thuật di truyền là mô phỏng các hiện tượng tự nhiên: Kế thừa và đấu tranh sinh tồn để cải tiến lời giải và khảo sát không gian lời giải. Giải thuật di truyền sử dụng các thuật ngữ vay mượn của di truyền học. Ta có thể nói về các cá thể (hay kiểu gen, cấu trúc) trong một quần thể; những cá thể này cũng còn được gọi là các chuỗi hay các nhiễm sắc thể. Mỗi kiểu (nhóm) gen (ta gọi là một nhiễm sắc thể) sẽ biểu diễn một lời giải của bài toán đang giải (ý tưởng của một nhiễm sắc thể cụ thể được người sử dụng xác định trước); một tiến trình tiến hoá được thực hiện trên một quần thể các nhiễm sắc thể tương ứng với một quá trình tìm kiếm lời giải trong không gian lời giải. Tìm kiếm đó cần cân đối hai mục tiêu: Khai thác những lời giải tốt nhất và khảo sát không gian tìm kiếm. Giải thuật di truyền (GA) là phương pháp tìm kiếm (độc lập miền) tạo được sự cân đối đáng kể giữa việc khai thác và khảo sát không gian tìm kiếm. Thực ra, GA thuộc lớp các thuật giải xác suất, nhưng lại rất khác những thuật giải ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên. Khác biệt quan trọng giữa tìm kiếm của GA và các phương pháp tìm kiếm khác là GA duy trì và xử lý một tập các lời giải (ta gọi là một quần thể) tất cả những phương pháp khác chỉ xử lý một điểm trong không gian tìm kiếm. Chính vì vậy mà GA mạnh hơn các phương pháp tìm kiếm hiện có rất nhiều. Sau đây ta sẽ ứng dụng GA để giải quyết vấn đề tìm kiếm tài liệu trong kho dữ liệu. 2.2.1. Biểu diễn nhiễm sắc thể Để ứng dụng GA, đầu tiên là việc mã hóa các giải pháp của vấn đề lựa chọn tài liệu trong việc biểu diễn nhiễm sắc thể. Nhưng chúng ta cần nhìn nhận lại các vấn đề trong các bước sau: - Làm thế nào để mã hóa số kế hoạch của truy vấn và các tài liệu của mỗi MVPP trong cùng một nhiễm sắc thể? - Mỗi nhiễm sắc thể có thể có độ dài khác nhau vì tập các kế hoạch truy vấn khác nhau sẽ tạo ra các MVPP khác nhau và có thể có số các nút khác nhau. Nếu muốn ứng dụng GA, chúng ta phải khắc phục hai vấn đề trên trong biểu diễn nhiễm sắc thể. Xem xét hai vấn đề đó, đầu tiên chúng ta tạo ra các kế hoạch thực hiện truy vấn cho mọi truy vấn, có thể được hỗ trợ trong kho dữ liệu và sau đó liệt kê tất cả các tài liệu xuất hiện trong mỗi kế hoạch. Mỗi nhiễm sắc thể được biểu diễn bởi hai phần. Phần thứ nhất, gọi là chuỗi kế hoạch truy vấn, ghi lại kế hoạch truy vấn được lựa chọn để trả lời cho một truy vấn. Trong cơ sở dữ liệu xử 107
Nghiêm Thị Lịch, Nguyễn Tân Ân lý truy vấn, một truy vấn có thể có nhiều kế hoạch thực hiện. Mỗi kế hoạch thực hiện sẽ sử dụng các toán tử trung gian. Truy vấn tối ưu cuối cùng sẽ chọn lựa một kế hoạch thực hiện để trả lời câu truy vấn theo mô hình chi phí. Vì vậy, mỗi truy vấn có một số đại diện cho kế hoạch truy vấn được lựa chọn. Phần thứ hai, gọi là chuỗi tài liệu, ghi lại các tài liệu nào sẽ được đưa ra trong kho dữ liệu. Phần này bao gồm chuỗi các bit nhị phân. Bít 1 tương ứng với tài liệu thích hợp sẽ được đưa ra. Ngược lại, tài liệu tương ứng sẽ không được đưa ra. Độ dài của phần này là số các tài liệu thích hợp xuất hiện trong tất cả các MVPP. Ví dụ, cho trước bốn truy vấn và giả định mỗi truy vấn có ba kế hoạch thực hiện và tổng số tài liệu xuất hiện trong 12 kế hoạch là 20. Nhiễm sắc thể được biểu diễn như sau: [0,2,1,2][1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]. Mảng đầu tiên trong biểu diễn chỉ ra một MVPP được xây dựng từ kế hoạch thực hiện đầu tiên cho truy vấn 1 và kế hoạch thứ 3 cho truy vấn 2, kế hoạch thứ 2 cho truy vấn 3, kế hoạch thứ 3 cho truy vấn 4. Mảng sau chỉ ra tài liệu thích hợp đầu tiên được lựa chọn để đưa ra. Chú ý rằng mỗi nhiễm sắc thể có thể hoặc không thể trở thành giải pháp khả thi bởi vì không phải tất cả tài liệu đều xuất hiện trong một MVPP. Ví dụ, nếu tài liệu thích hợp 1 không nằm trong MVPP được xây dựng bởi các kế hoạch thứ 1, 2, 3 cho truy vấn 1, 2, 3, 4. Khi đó, nhiễm sắc thể [0,2,1,2][1,0,0,0,0,0,0,0,0,0,0,0,0,0,. . . .] không trở thành giải pháp khả thi. Một MVPP nào đó có thể chỉ bao gồm các tài liệu thích hợp nào đó. Chúng ta hãy trở lại MVPP trong hình 1. Có 8 tài liệu thích hợp trong tất cả các MVPP gộp lại. Tuy nhiên, tài liệu 1, 2, 3 và 4 là tài liệu thích hợp chỉ khi chúng ra sử dụng MVPP trong hình 1a. Trong trường hợp này, các vị trí tại 0, 1, 2, 3 (tài liệu đầu tiên là vị trí 0 trong quá trình mô tả) có thể xuất hiện giá trị 1 hoặc 0. Các vị trí khác nên đặt là 0. Chúng ta chỉ cần quan tâm đến các vị trí của một MVPP được giải quyết. Bởi vì không gian tìm kiếm có thể được giảm xuống đến một giới hạn thấp hơn trong cách tiếp cận xấp xỉ. Với mỗi giải pháp (nhiễm sắc thể), chúng ta có tập các tài liệu được đưa ra tương ứng với nút đầu tiên trong việc giải quyết MVPP. Và đối với mỗi giải pháp, hàm chi phí trả về tổng chi phí của chi phí truy vấn và chi phí duy trì. Giá trị của hàm chi phí nhận được càng nhỏ thì giải pháp đó càng tốt. 2.2.2. Giải thuật GLS (Genetic Local Search) Giải thuật GLS là một phương pháp giải quyết vấn đề bằng cách sử dụng các quy tắc có được từ kinh nghiệm kết hợp các ưu điểm của giải thuật mẫu dựa vào tìm kiếm như giải thuật di truyền và sự tối ưu cục bộ. Tìm kiếm cục bộ di chuyển lặp lại từ một trong những giải pháp tới một giải pháp trong lân cận của nó cho đến khi đạt được một cực tiểu cục bộ 00. Trong khi nó nhanh chóng tìm ra các giải pháp tốt trong các miền nhỏ của không gian tìm kiếm, các toán tử di truyền là phù 108
Ứng dụng giải thuật di truyền để tìm kiếm tài liệu trong kho dữ liệu hợp cho quá tình khám phá trong không gian tìm kiếm để nhận dạng được các tài liệu quan tâm. Trên đây là khuôn mẫu của giải thuật GLS cho VSP. Như mô tả ở trên, không phải tất cả các giải pháp đều là các giải pháp khả thi. Trong giải thuật, chúng tôi thiết kế một hàm kiểm tra tính khả thi để loại bỏ các gen không phù hợp. Để loại ra các gen không thích hợp, hàm kiểm tra có thể làm giảm bớt không giam tìm kiếm. Khi quần thể ban đầu được tạo ra. Hàm Check_feasible() đầu tiên liệt kê các tài liệu liên quan theo chuỗi kế hoạch truy vấn và ghi lại chúng. Hàm tìm kiếm cục bộ Local_search() được sử dụng để điều chỉnh giá trị của chuỗi tài liệu theo giá trị của chuỗi kế hoạch truy vấn. Tìm kiếm cục bộ được thực hiện cho mỗi cá thể nhằm thu được quần thể cực tiểu cục bộ. Trong vòng lặp chính, các toán tử trao đổi chéo và đột biến được áp dụng để lựa chọn ngẫu nhiên các cá thể riêng lẻ cho một số lần được định trước. 2.2.3. Các toán tử di truyền Trong phần này, chúng tôi giới thiệu các toán tử di truyền bao gồm: Chọn lọc, trao đổi chéo và đột biến. Toán tử chọn lọc. 109
Nghiêm Thị Lịch, Nguyễn Tân Ân Mục đích của chọn lọc trong giải thuật di truyền là một quá trình trong đó cá thể được chọn để tham gia vào các pha tiếp theo của quá trình tiến hóa. Việc chọn lựa này tùy thuộc vào hàm thích nghi của cá thể đó, có nghĩa là những cá thể nào có giá trị hàm thích nghi cao hơn sẽ có khả năng có nhiều con cháu trong thế hệ tiếp theo. Có nhiều kiểu chọn lọc được biết đến như chọn lọc ngẫu nhiên, chọn lọc bánh xe quay, chọn lọc xếp hạng,. . . Điểm chính của việc chọn lọc là giữ lại thế hệ cha mẹ tốt nhất để có thể có các cơ hội tốt nhất khi chọn lọc. Chúng tôi chọn lựa cách tiếp cận bằng phương pháp chọn lọc xếp hạng. Chọn lọc xếp hạng là phương pháp sẽ sắp xếp các cá thể dựa trên độ thích nghi của chúng. Các cá thể được lựa √ chọn một cách ngẫu nhiên từ 1 đến n, trong đó n là kích thước quần thể. Toán tử trao đổi chéo. Trong các giải thuật di truyền, trao đổi chéo tổ hợp lại các gen trong 2 nhiễm sắc thể cha mẹ để tạo ra con cái. Toán tử trao đổi chéo cho phép chúng ta xác định một điểm bắt đầu mới cho tìm kiếm cục bộ dựa trên thông tin chứa trong quần thể hiện tại. Mục đích của trao đổi chéo là xác định các vùng của không gian tìm kiếm mà ở đó các giải pháp tốt hơn có khả năng được tìm thấy bằng thủ tục tìm kiếm cục bộ. Trong cách tiếp cận này, chúng tôi áp dụng một điểm trao đổi chéo cho nhiễm sắc thể được lựa chọn. Nhiễm sắc thể được bao gồm hai phần, mỗi phần được trao đổi chéo như sau: Chuỗi kế hoạch truy vấn: hai chuỗi kế hoạch truy vấn từ hai nhiễm sắc thể được lựa chọn để trao đổi chéo và sinh ra hai con. Ví dụ, cho bốn truy vấn và số kế hoạch thực hiện truy vấn là 2, 2, 4, 4. Áp dụng một điểm trao đổi chéo tới hai chuỗi kế hoạch truy vấn [1100] và [3311] và sinh ra 2 con: [1111] và [3300] nếu điểm cắt tại vị trí thứ 2. Hàm check-feasible được áp dụng để kiểm tra tính khả thi của thế hệ con. Chúng ta sử dụng hàm “mod” để điều chỉnh nếu đó là giải pháp không khả thi. Trong ví dụ, chuỗi kế hoạch truy vấn [3300] là một giải pháp không khả thi. Vì vậy, ta sử dụng hàm “mod” để điều chỉnh nó tới [1100]. Chuỗi tài liệu: thường là trao đổi hai chuỗi tài liệu từ hai cha mẹ và sử dụng hàm check-feasible() để tạo ra nhiễm sắc thể mới sinh ra phù hợp. Toán tử đột biến. Trong giải thuật di truyền, đột biến không xảy ra thường xuyên (với khả năng rất nhỏ) là sự thay đổi ngẫu nhiên giá trị của vị trí các bit. Đột biến rất cần thiết, bởi vì cho dù sao chép lại và trao đổi chéo tìm kiếm hiệu quả, và sự tổ hợp lại các khái niệm hiện có, đôi khi chúng có thể trở nên tích cực (có hiệu quả) và mất đi một số gen cần thiết có ích (các vị trí đặc biệt như 0 hoặc 1). Trong tài liệu này, đột biến trong chuỗi tài liệu đơn giản thay đổi 1 thành 0 và ngược lại trong nhiễm sắc thể. Đột biến trong chuỗi kế hoạch truy vấn tăng 1 thành truy vấn lựa chọn và chắc chắn rằng nó có khả năng trở thành số kế hoạch. 110
Ứng dụng giải thuật di truyền để tìm kiếm tài liệu trong kho dữ liệu 3. Kết luận Quá trình tìm kiếm trong kho dữ liệu lớn là một vấn đề luôn được các nhà tin học quan tâm. Đã có rất nhiều các phương pháp tìm kiếm, lựa chọn tài liệu được đưa ra. Ứng dụng GA là một giải pháp không những khả thi mà còn tỏ ra có nhiều ưu điểm. Việc cải tiến hàm thích nghi và các toán tử trong giải thuật còn phải được nghiên cứu thử nghiệm thêm nữa. Những vấn đề đó sẽ được trình bày trong các báo cáo tiếp sau. REFERENCES [1] Nguyễn Đình Thúc, (2001). Trí tuệ nhân tạo: Lập trình tiến hoá. Nxb giáo dục thành phố Hồ chí Minh. [2] Võ Huỳnh Trâm, Trần Ngân Bình, (2002). Giáo trình trí tuệ nhân tạo. Nxb giáo dục. [3] J.R.Goldberg - D.E. Fogel, (1996). Genetic programming, proceeding of the first annual conference. Cambrige, MA Mit press. [4] H. Gupta and I. S. Mumick, (1999). Selection of views to materialize under a maintenance cost constraint. Proc. Int. Conf. Database Theory (ICDT), pp. 453–470. [5] Gupta A, Mumick, (1995). Maintenance of materialized views: problems, tech- niques, and applications. IEEE Data Eng. Bulletin, (Special Issue on Materialized Views and Data Warehousing), pp. 3–18. [6] Gupta H, (1997). Selection of views to materialize in a data warehouse. Proceed- ings of the 23rd VLDB conference, Athens, Greece, pp.156–165. [7] Horng JT, Chang YJ, Liu BJ, (1999). Materialized View Selection Using Genetic algorithms in Data Warehouse System. Late Breaking Papers at the Genetic and Evolutionary Computation Conference, pp. 107–115. [8] http://www.felk.com. [9] http://www.codeproject.com. ABSTRACT Apply Genetic algorithm in searching information in data warehouse A data warehouse plays an important role for storage and analysis and supply information. Data warehouses store lots of materialized views to provide an efficient decision-support system. Selection of a fitness set of materialized views from a variety of Multiple View Processing Plan (MVPP) forms a challenge in data warehouse research. This is an NP complete [4]. Some authores used heuristic algorithms to solve this problem. In this paper, we present genetic algorithm to choose materialized views. How to code chromosomes and operators of this algorithm in this case are presented. 111

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.