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ị

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.
Nội dung trích xuất từ tài liệu:
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ÒNGHỌC VIỆN KỸ THUẬT QUÂN SỰ—————————-Vũ Chí CườngMỘT LỚP THUẬT TOÁN PHỎNG TIẾN HÓA SINH HỌCDỰA TRÊN THÔNG TIN ĐỊNH HƯỚNGGIẢI BÀI TOÁN ĐA CỰC TRỊTÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌCChuyên ngành: Cơ sở toán học trong tin họcHà Nội - Năm 2016CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠIHỌC VIỆN KỸ THUÂT QUÂN SỰ - BỘ QUỐC PHÒNG——————————————————–Người hướng dẫn khoa học: PGS. TS. Bùi Thu LâmPhản biện 1: PGS.TS Hoàng Xuân Huấn - ĐH Quốc gia Hà NộiPhản biện 2: PGS.TS. Huỳnh Thị Thanh Bình - ĐH Bách khoa Hà NộiPhản biện 3: TS. Nguyễn Đức Dũng - Viện Hàn lâm KH&CN Việt NamLuận án được bảo vệ tại Hội đồng đánh giá luận án cấp Học viện theoquyết định số 2506/QĐ-HV, ngày 08 tháng 7 năm 2016 của Giám đốcHọc viện Kỹ thuật Quân sự, họp tại Học viện Kỹ thuật Quân sự vàohồi .... giờ ...., ngày .... tháng .... năm ......Có thể tìm hiểu luận án tại:- Thư viện Học viện Kỹ thuật Quân sự- Thư viện Quốc giaLời mở đầuThuật toán phỏng tiến hóa sinh học hay gọi ngắn gọn là Thuật toántiến hóa (Evolutionary Algorithms - EAs) là một lớp các thuật toánheuristic trong tối ưu hóa và học máy. EAs đã được áp dụng rộng rãivà thu được nhiều thành công trong việc giải quyết các bài toán tối ưusố 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ứngtừ quá trình chọn lọc tự nhiên trong thuyết tiến hóa của Darwin. EAshoạt động trên tập các phương án (còn gọi là quần thể - population)để 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ểđã được khẳng định là một mô hình tiềm năng cho việc giải quyết cácbài toán tối ưu toàn cục [4, 31, 32, 63, 65, 85].Trong quá trình nghiên cứu và phát triển, đã có 4 dạng EAs truyềnthố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),Giải thuật di truyền (Genetic Algorithm - GA) và Lập trình di truyền(Genetic Programming - GP). Các đặc điểm quan trọng nhất đối vớicác EAs là:• EAs điều khiển quá trình tiến hóa của một quần thể gồm nhiềucá thể, mỗi cá thể đại diện (hay mã hóa) cho một phương án (haymột lời giải) chấp nhận được của bài toán tối ưu.• Các cá thể con (offsprings) được sinh ra một cách ngẫu nhiênthông qua các quá trình đột biến và lai ghép. Quá trình đột biếnlà một sự thay đổi (rất nhỏ) của một cá thể trong khi đó quátrình lai ghép là sự hoán đổi thông tin giữa 2 hay nhiều cá thểhiện tại.• Một hàm đánh giá được sử dụng để đo chất lượng hay tính toánmức độ phù hợp của các cá thể. Cá thể có giá trị đánh giá caohơn được xem là tốt hơn cá thể khác. Quá trình lựa chọn thựchiện việc lựa chọn và ưu tiên cho các cá thể tốt hơn với mục đíchlà tạo ra một thế hệ mới với các cá thể tốt hơn.Bên cạnh các lớp EAs, trong khoảng thời gian 15 năm gần đây, đãcó một số mô hình thuật toán phỏng tự nhiên mới được đề xuất, chẳnghạn như Tối ưu hóa bầy đàn (PSO) [43], Tối ưu hóa đàn kiến (ACO)[19], Ước lượng các thuật toán phân phối (EDA) [49], Hệ miễn nhiễm3nhân tạo (AIS) [12],... Trong các mô hình này, các toán tử tính toánđược lấy cảm hứng từ những hiện tượng khác nhau của thế giới tựnhiên như bầy chim, đàn cá hay đàn kiến,...Trong thiết kế các thuật toán heuristic, cả truyền thống cũng nhưhiện đại, vấn đề sử dụng thông tin định hướng luôn nhận được sự quantâm của các nhà nghiên cứu. Nếu có thông tin định hướng tốt thì quátrình tìm kiếm phương án tối ưu sẽ diễn ra nhanh chóng và đạt kếtquả tốt. Phương pháp tụt Gradient (Gradient Descent), thuật toántìm kiếm đơn hình (Simplex Search) [66], thuật toán tìm kiếm phântán (Scatter Search) [30, 47] là những ví dụ điển hình trong việc sửdụng thông tin định hướng để giải quyết các bài toán tối ưu. Trong cácmô 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(Differential Evolution) [75] là một ví dụ khác về những lợi ích đạtđược khi sử dụng thông tin định hướng để chỉ dẫn quá trình tìm kiếmlời giải. Tuy nhiên, trong các thuật toán này, thông tin định hướng chỉđược xác định một cách cục bộ trong từng thế hệ của quá trình tiếnhóa mà chưa có tính toàn cục, cách tổ chức quản lý thông tin hướngcòn thiếu tính hệ thống. Bởi thế sẽ tồn tại những trường hợp mà thôngtin định hướng có thể làm suy giảm chất lượng (giá trị đánh giá) củacác phương án đã tìm được. Vấn đề xác định các thông tin định hướngtốt và cách thức quản lý, sử dụng thông tin đó một cách có hệ thốngđể hỗ trợ quá trình tiến hóa sẽ là chủ đề nghiên cứu chính của luận án.Ngoài ra, trong cách thức tổ chức quản lý các cá thể, có thể thấyrằng một quần thể các cá thể có thể bao hàm các thông tin định hướng,các thông tin định hướng này hoàn toàn có thể được xác định một cáchcó hệ thống và hỗ trợ quá trình tìm kiếm tiến hóa.Luận án được tổ chức thành 4 chương nội dung chính, bao gồm:Chương 1: Cơ sở lý thuyết,Chương 2: Những nội dung nghiên cứu liên quan,Chương ...