Tiểu Luận Tiểu luận môn xử lý song song: Thuật toán di truyền thích nghi song song

A. GIỚI THIỆU



Thuật toán di truyền là một sự thể hiện của một lớp các phương pháp dựa trên kỹ thuật tìm kiếm ngẫu nhiên Heuristic. Thuật toán di truyền khi thực hiện đòi hỏi một lượng lớn thời gian tính toán. Song song hóa thuật toán di truyền là một thử nghiệm đầu tiên để tăng tốc thuật toán mà không ảnh hưởng đến các tính chất của nó. Trong tiểu luận này, kỹ thuật đa luồng được sử dụng để chuyển đổi thuật toán di truyền thành dạng song song. Vấn đề mấu chốt để nâng cao hiệu suất trong tính toán song song là phải giảm truyền thông giữa các tiến trình.
Sức mạnh của thuật toán di truyền chủ yếu là ở khả năng xác định vị trí tối ưu toàn cục trong một môi trườngđa phương thức. Tuy nhiên, cho dù hiệu quả của thuật toán di truyền là thế nào đi chăng nữa thì lời giải của phương pháp này cũng không chính xác một cách tuyệt đối. Nhiều công trình đang nghiên cứu để tìm cách tăng thêm độ chính xác đó. Để đạt được mục tiêu này, hai hướng tiếp cận chính có thể được chấp nhận: hướng thứ nhất là thiết kế một thuật toán di truyền cho một lớp các bài toán mà ta đang giải quyết. Khuynh hướng này bao gồm việc tạo ra cấu trúc dữ liệu và đặc tả các phép toán di truyền cho một bài toán, tạo ra một chương trình tiến hóa. Hướng tiếp cận thứ hai hoạt động trực tiếp trên thuật toán và cố gắng để tăng hiệu quả bằng cách thay đổi cấu trúc nội tại của nó. Phương pháp thích nghi được giới thiệu ở đây là một ví dụ của tiếp cận này.
Tiểu luận được viết trong cấu trúc bốn phần.
Phần 1: Trình bày tổng quan về thuật toán di truyền và hoạt động của các toán tử di truyền.
Phần 2: Trình bày thuật toán di truyền song song. Trong đó nhấn mạnh trên thuật toán di truyền song song song song với các luồng bằng nhau.
Phần 3: Trình bày các toán tử di truyền thích nghi.
Phần 4: Giới thiệu một sự thực hiện của thuật toán di truyền song song thích nghi, trong đó mô tả sự thực hiện của một thuật toán di truyền song song kết hợp với kỹ thuật thích nghi.
​ ​