THUẬT TOÁN DI TRUYỀN VÀ CÁC TOÁN TỬ DI TRUYỀN

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.

Häc viªn: Lª Thñy Th¹ch-Líp cao häc Tin häc khãa 2004-2006 1