Kết hợp hệ mờ và giải thuật di truyền giải bài toán tối ưu

Nguyễn Thu Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 113(13): 3 - 6

3

KẾT HỢP HỆ MỜ VÀ GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN TỐI ƯU

Nguyễn Thu Huyền

*

, Nguyễn Thị Tuyển

Trường ĐH Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên

TÓM TẮT

Giải thuật di truyền (GAs) là một công cụ hữu ích giải quyết các bài toán tối ưu dựa trên cơ chế

chọn lọc tự nhiên. Tuy nhiên, kết quả tối ưu của GAs còn phụ thuộc nhiều vào các yếu tố như khởi

tạo quần thể ban đầu, kích cỡ quần thể, xác xuất lai, xác suất đột biến…. Vì vậy, chúng tôi đã tiến

hành kết hợp hệ mờ với GAs nhằm tạo ra một quần thể ban đầu gồm những cá thể được sinh ra từ

kết quả của hệ mờ, sau đó tiếp tục áp dụng GAs cho ra kết quả cuối cùng. Chúng tôi cũng tiến

hành giải một số hàm tối ưu bằng GAs thuần túy và bằng sự kết hợp giữa hệ mờ với GAs, sau đó

so sánh kết quả của cả hai phương pháp và rút ra kết luận hiệu quả của việc kết hợp này.

Từ khóa: Giải thuật di truyền, hệ mờ, hàm Sphere, Schwefel.

ĐẶT VẤN ĐỀ*

Trong GAs, các cá thể trong quần thể ban đầu

được sinh ra hoàn toàn ngẫu nhiên. Chính vì

vậy trước khi hoàn thành việc khởi tạo quần

thể ban đầu, chúng ta không thể biết được các

cá thể ấy có độ thích nghi tốt hay xấu với môi

trường. Nếu các cá thể ấy thích nghi tốt với

môi trường thì khả năng sau này giải thuật tìm

được ra lời giải tối ưu là rất cao. Chính vì vậy,

chúng tôi nghĩ đến tác động vào việc khởi tạo

quần thể ban đầu sao cho có thể sinh ra các cá

thể có độ thích nghi cao với môi trường ngay

từ đầu. Để làm được điều đó, việc kết hợp hệ

mờ với GAs là một ý tưởng hay.

Bài báo này muốn đưa ra một ý tưởng kết hợp

hệ mờ và GAs để tạo ra quần thể ban đầu gồm

những cá thể có độ thích nghi cao, sau đó áp

dụng các toán tử di truyền để tìm ra lời giải

tối ưu. Để kiểm tra tính hiệu quả của sự kết

hợp này, chúng tôi tiến hành giải một số hàm

tối ưu bằng GAs thuần túy và giải thuật đề

xuất để so sánh kết quả, sau đó rút ra kết luận.

Bài báo có cấu trúc như sau: Sau phần mở

đầu, bài báo trình bày thuật toán đề xuất kết

hợp GAs với hệ mờ. Phần kế tiếp trình bày

các kết quả thử nghiệm trên một số bài toán

cụ thể. Cuối cùng là kết luận và thảo luận.

*

Tel: 0904012478; Email: h2m174@gmail.com

KẾT HỢP GAs VÀ HỆ MỜ

Giới thiệu chung về hệ mờ

Hệ mờ bao gồm các đầu vào, đầu ra cùng với

bộ xử lý. Các yếu tố đầu vào của hệ nhận giá

trị số rõ, còn đầu ra có thể là một tập mờ hoặc

một giá trị rõ. Bộ xử lý thực chất là một ánh

xạ phản ánh sự phụ thuộc của biến đầu ra hệ

thống với biến đầu vào. Quan hệ ánh xạ của

đầu ra đối với các đầu vào của hệ mờ được

mô tả bằng một tập luật mờ.

Cấu trúc cơ bản của hệ mờ gồm bốn thành

phần chủ đạo[4]:

Hình 1. Kiến trúc của hệ mờ

- Giao diện mờ hoá (Fuzzification): Có chức

năng thực hiện việc chuyển đổi các đầu vào

rõ thành các mức mờ.

- Cơ sở luật (rule base): Chứa các luật mờ if -

then, thực chất là một tập các phát biểu hay

quy tắc mà con người có thể hiểu được. Cơ sở

luật là thành phần quan trọng nhất của bất kỳ

mô hình mờ nào.