intTypePromotion=3

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ị

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

0
19
lượt xem
1
download

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ị

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

Luận án trình bày những khái niệm lý thuyết cơ bản của tối ưu hóa, làm quen với các dạng bài toán tối ưu đơn cực trị (uni-modal optimization problems) và đa cực trị (multi-modal optimization problems), luận án mô tả một cách chi tiết nội dung các thuật toán tìm kiếm tiêu biểu dựa trên thông tin định hướng,... Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: 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 />

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản