Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Cơ sở dữ liệu quan hệ thô và vấn đề tối ưu hóa câu hỏi.Nếu sự tăng một số lượng giá trị sản sinh một giảm sút kết quả dẫn tới giảm số lượng giá trị, thì quan hệ là một phản hồi âm. Điều này sản sinh giá trị ổn định về số lượng, chống trả lại các hỗn loạn môi trường. Điều này là cơ chế bên dưới quan hệ điều khiển nhắm hướng mục đích giới thiệu ở trên. | Tạp chí Tin học và Đĩêu khiền học T. 19 s. 4 2003 366-372 CÁC TOÁN TỬ LAI GHÉP CHO THUẬT TOÁN DI TRUYÊN GIẢI BÀI TOÁN TÔ MÀU Đồ THỊ ĐƠN NGUYỄN XUÂN HUY vũ THIỆN CẨN Viện Công nghệ thông tin Abstract. This paper describes and compares some crossover operators of the genetic algorithm for the problem of single chromatic graph. Using a fixed number of evolutions and a specified number of colors we count the number of pairs of adjacent vertices having the same color for each certain graph. This number is calculated in real-time and the best operator is one that produces better solution. Genetic algorithms mentioned in this paper mainly use proportionally selected operators and classic mutation operators. Tóm tắt. Bài báo mô tả và so sánh một số toán tử lai ghép khác nhau của thuật toán di truyền giải bài toán tô màu đồ thị đơn. Nội dung so sánh là đếm bang thực nghiệm với số lần tiến hóa cố định cho trước và số màu cho trước đối với mỗi loại đồ thị. số đếm này được xác định trong thời gian thực. Toán tử được chọn sẽ là toán tử cho kết quả trội. Các thuật toán di truyền dề cập đến là toán tử chọn mà chủ yếu là toán tử chọn tỉ lệ và toán tử đột biến cổ điển. 1. BÀI TOÁN TÔ MÀU ĐỒ THỊ ĐƠN 1.1. Bài toán Cho G V E là một đồ thị đơn vô hướng trong đó V là tập các đỉnh và E là tập các cạnh. Ta giải bài toán sau. Dùng một số cho trước các màu xác định màu tô cho mỗi đỉnh i V sao cho số cạnh có đỉnh cùng màu là nhỏ nhất. Đồ thị G được gọi là đơn nếu mỗi cặp đỉnh có thể xác định không quá một cung nối chúng 1 . 1.2. Mô hình toán học cúa bài toán Với mỗi i e V và với mỗi j 1 2. đặt í 1 với đỉnh i e V có màu j Xịj 1 0 ngược lại Bài toán có thể phát biểu như sau 1 3 5 e min E E j l út G-E với ràng buộc í X ị j 1 i E V j i CÁC TOÁN TỦ LAI GHÉP CHO THUẬT TOÁN DI TRUYỀ. 367 Xij 0 hay 1 7 e ư j 1 2.Ệ 2. KỸ THUẬT DựA TRÊN QUAN THE Trong các kỹ thuật này một cơ chế tiến hóa được sử dụng để biến đổi một quần thể tập hợp các lời giải từ thế hệ này đến thế hệ kế tiếp sao cho từ quần thể kế