Tóm tắt Luận án Tiến sỹ Toán học: Một lớp thuật toán phỏng tiến hoá sinh học dựa trên thông tin định hướng giải bài toán đa cực trị

BỘ QUỐC PHÒNG<br /> HỌC VIỆN KỸ THUẬT QUÂN SỰ<br /> —————————-<br /> <br /> Vũ Chí Cường<br /> <br /> MỘT LỚP THUẬT TOÁN PHỎNG TIẾN HÓA SINH HỌC<br /> DỰA TRÊN THÔNG TIN ĐỊNH HƯỚNG<br /> GIẢI BÀI TOÁN ĐA CỰC TRỊ<br /> <br /> TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC<br /> Chuyên ngành: Cơ sở toán học trong tin học<br /> <br /> Hà Nội - Năm 2016<br /> <br /> CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI<br /> HỌC VIỆN KỸ THUÂT QUÂN SỰ - BỘ QUỐC PHÒNG<br /> ——————————————————–<br /> <br /> Người hướng dẫn khoa học: PGS. TS. Bùi Thu Lâm<br /> <br /> Phản biện 1: PGS.TS Hoàng Xuân Huấn - ĐH Quốc gia Hà Nội<br /> Phản biện 2: PGS.TS. Huỳnh Thị Thanh Bình - ĐH Bách khoa Hà Nội<br /> Phản biện 3: TS. Nguyễn Đức Dũng - Viện Hàn lâm KH&CN Việt Nam<br /> <br /> Luận án được bảo vệ tại Hội đồng đánh giá luận án cấp Học viện theo<br /> quyết định số 2506/QĐ-HV, ngày 08 tháng 7 năm 2016 của Giám đốc<br /> Học viện Kỹ thuật Quân sự, họp tại Học viện Kỹ thuật Quân sự vào<br /> hồi .... giờ ...., ngày .... tháng .... năm ......<br /> <br /> Có thể tìm hiểu luận án tại:<br /> - Thư viện Học viện Kỹ thuật Quân sự<br /> - Thư viện Quốc gia<br /> <br /> Lời mở đầu<br /> <br /> Thuật toán phỏng tiến hóa sinh học hay gọi ngắn gọn là Thuật toán<br /> tiến hóa (Evolutionary Algorithms - EAs) là một lớp các thuật toán<br /> heuristic trong tối ưu hóa và học máy. EAs đã được áp dụng rộng rãi<br /> và thu được nhiều thành công trong việc giải quyết các bài toán tối ưu<br /> số và tối ưu tổ hợp. Về nguyên tắc, EA là một thuật toán lấy cảm hứng<br /> từ quá trình chọn lọc tự nhiên trong thuyết tiến hóa của Darwin. EAs<br /> hoạt động trên tập các phương án (còn gọi là quần thể - population)<br /> để tìm kiếm phương án tối ưu. Nguyên tắc tính toán dựa vào quần thể<br /> đã được khẳng định là một mô hình tiềm năng cho việc giải quyết các<br /> bài toán tối ưu toàn cục [4, 31, 32, 63, 65, 85].<br /> Trong quá trình nghiên cứu và phát triển, đã có 4 dạng EAs truyền<br /> thống được đề xuất, bao gồm Quy hoạch tiến hóa (Evolutionary Programming - EP), Chiến lược tiến hóa (Evolutionary Strategies - ES),<br /> Giải thuật di truyền (Genetic Algorithm - GA) và Lập trình di truyền<br /> (Genetic Programming - GP). Các đặc điểm quan trọng nhất đối với<br /> các EAs là:<br /> • EAs điều khiển quá trình tiến hóa của một quần thể gồm nhiều<br /> cá thể, mỗi cá thể đại diện (hay mã hóa) cho một phương án (hay<br /> một lời giải) chấp nhận được của bài toán tối ưu.<br /> • Các cá thể con (offsprings) được sinh ra một cách ngẫu nhiên<br /> thông qua các quá trình đột biến và lai ghép. Quá trình đột biến<br /> là một sự thay đổi (rất nhỏ) của một cá thể trong khi đó quá<br /> trình lai ghép là sự hoán đổi thông tin giữa 2 hay nhiều cá thể<br /> hiện tại.<br /> • Một hàm đánh giá được sử dụng để đo chất lượng hay tính toán<br /> mức độ phù hợp của các cá thể. Cá thể có giá trị đánh giá cao<br /> hơn được xem là tốt hơn cá thể khác. Quá trình lựa chọn thực<br /> hiện việc lựa chọn và ưu tiên cho các cá thể tốt hơn với mục đích<br /> là tạo ra một thế hệ mới với các cá thể tốt hơn.<br /> Bên cạnh các lớp EAs, trong khoảng thời gian 15 năm gần đây, đã<br /> có một số mô hình thuật toán phỏng tự nhiên mới được đề xuất, chẳng<br /> hạn như Tối ưu hóa bầy đàn (PSO) [43], Tối ưu hóa đàn kiến (ACO)<br /> [19], Ước lượng các thuật toán phân phối (EDA) [49], Hệ miễn nhiễm<br /> 3<br /> <br /> nhân tạo (AIS) [12],... Trong các mô hình này, các toán tử tính toán<br /> được lấy cảm hứng từ những hiện tượng khác nhau của thế giới tự<br /> nhiên như bầy chim, đàn cá hay đàn kiến,...<br /> Trong thiết kế các thuật toán heuristic, cả truyền thống cũng như<br /> hiện đại, vấn đề sử dụng thông tin định hướng luôn nhận được sự quan<br /> tâm của các nhà nghiên cứu. Nếu có thông tin định hướng tốt thì quá<br /> trình tìm kiếm phương án tối ưu sẽ diễn ra nhanh chóng và đạt kết<br /> quả tốt. Phương pháp tụt Gradient (Gradient Descent), thuật toán<br /> tìm kiếm đơn hình (Simplex Search) [66], thuật toán tìm kiếm phân<br /> tán (Scatter Search) [30, 47] là những ví dụ điển hình trong việc sử<br /> dụng thông tin định hướng để giải quyết các bài toán tối ưu. Trong các<br /> mô hình thuật toán tiến hóa mới, lớp các thuật toán tiến hóa vi phân<br /> (Differential Evolution) [75] là một ví dụ khác về những lợi ích đạt<br /> được khi sử dụng thông tin định hướng để chỉ dẫn quá trình tìm kiếm<br /> lời giải. Tuy nhiên, trong các thuật toán này, thông tin định hướng chỉ<br /> được xác định một cách cục bộ trong từng thế hệ của quá trình tiến<br /> hóa mà chưa có tính toàn cục, cách tổ chức quản lý thông tin hướng<br /> còn thiếu tính hệ thống. Bởi thế sẽ tồn tại những trường hợp mà thông<br /> tin định hướng có thể làm suy giảm chất lượng (giá trị đánh giá) của<br /> các phương án đã tìm được. Vấn đề xác định các thông tin định hướng<br /> tốt và cách thức quản lý, sử dụng thông tin đó một cách có hệ thống<br /> để hỗ trợ quá trình tiến hóa sẽ là chủ đề nghiên cứu chính của luận án.<br /> Ngoài ra, trong cách thức tổ chức quản lý các cá thể, có thể thấy<br /> rằng một quần thể các cá thể có thể bao hàm các thông tin định hướng,<br /> các thông tin định hướng này hoàn toàn có thể được xác định một cách<br /> có hệ thống và hỗ trợ quá trình tìm kiếm tiến hóa.<br /> Luận án được tổ chức thành 4 chương nội dung chính, bao gồm:<br /> Chương 1: Cơ sở lý thuyết,<br /> Chương 2: Những nội dung nghiên cứu liên quan,<br /> Chương 3: Thuật toán tiến hóa dựa trên thông tin định<br /> hướng,<br /> Chương 4: Thuật toán tiến hóa dựa trên thông tin định<br /> hướng với bài toán đa cực trị.<br /> <br /> 4<br /> <br /> Chương 1<br /> <br /> CƠ SỞ LÝ THUYẾT<br /> <br /> Mục đích của chương này là cung cấp các kiến thức cơ sở lý thuyết<br /> liên quan đến nội dung nghiên cứu của luận án. Cấu trúc của chương<br /> gồm 2 phần chính. Phần đầu trình bày những khái niệm lý thuyết tổng<br /> quan về tối ưu hóa, liên quan nhiều nhất đến thuật toán tiến hóa. Phần<br /> thứ hai mô tả các nội dung cơ bản của thuật toán tiến hóa như khái<br /> niệm, bản chất, các dạng phân loại truyền thống. Trong phần này, tác<br /> giả cũng dành thời gian để mô tả một cách cụ thể các thành phần chính<br /> của một thuật toán tiến hóa và cuối cùng là sơ đồ tổng quát của thuật<br /> toán.<br /> Sơ đồ tổng quát của một EA có thể được mô tả như Algorithm 1.1.<br /> Algorithm 1.1 Sơ đồ tổng quát của Thuật toán tiến hóa<br /> Input: µ, λ, κ, θι , θc , θm , θs<br /> Output: a∗ là cá thể tốt nhất hoặc P ∗ là quần thể tốt nhất tìm được.<br /> 1:<br /> 2:<br /> 3:<br /> 4:<br /> 5:<br /> 6:<br /> 7:<br /> 8:<br /> 9:<br /> 10:<br /> 11:<br /> 12:<br /> <br /> t ←− 0;<br /> P (t) ←− initialize(µ);<br /> Khởi tạo quần thể ban đầu<br /> f (t) ←− evaluate(P (t), µ);<br /> Đánh giá các cá thể của quần thể<br /> while (ι(P (t), θι ) = true) do<br /> P (t) ←− recombine(P (t), θc );<br /> Phép lai ghép<br /> P ” (t) ←− mutate(P (t), θm );<br /> Phép đột biến<br /> f (t) ←− evaluate(P ” (t), λ);<br /> P (t + 1) ←− select(P ” (t), f (t), µ, θs );<br /> Phép lựa chọn<br /> t ←− t + 1;<br /> end while<br /> return P ∗ = P (t);<br /> a∗ = best(P (t));<br /> <br /> 5<br /> <br />