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

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….
Nội dung trích xuất từ tài liệu:
Kết hợp hệ mờ và giải thuật di truyền giải bài toán tối ưuNguyễn Thu Huyền và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆ113(13): 3 - 6KẾT HỢP HỆ MỜ VÀ GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN TỐI ƯUNguyễn Thu Huyền*, Nguyễn Thị TuyểnTrường ĐH Công nghệ thông tin và Truyền thông – ĐH Thái NguyênTÓM TẮTGiả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ởitạ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ếnhà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ếnhà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ầnthể ban đầu, chúng ta không thể biết được cáccá thể ấy có độ thích nghi tốt hay xấu với môitrường. Nếu các cá thể ấy thích nghi tốt vớimô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ạoquầ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 ngaytừ đầ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ợphệ mờ và GAs để tạo ra quần thể ban đầu gồmnhững cá thể có độ thích nghi cao, sau đó ápdụng các toán tử di truyền để tìm ra lời giảitối ưu. Để kiểm tra tính hiệu quả của sự kếthợp này, chúng tôi tiến hành giải một số hàmtố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ếthợp GAs với hệ mờ. Phần kế tiếp trình bàycác kết quả thử nghiệm trên một số bài toáncụ thể. Cuối cùng là kết luận và thảo luận.*Tel: 0904012478; Email: h2m174@gmail.comKẾ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ớibộ 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ặcmột giá trị rõ. Bộ xử lý thực chất là một ánhxạ 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ờ đượcmô 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ànhphần chủ đạo[4]:Hình 1. Kiến trúc của hệ mờ- Giao diện mờ hoá (Fuzzification): Có chứcnăng thực hiện việc chuyển đổi các đầu vàorõ 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 hayquy 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.3Nguyễn Thu Huyền và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆ- Cơ chế suy diễn (inference mechanism): Cóchức năng thực hiện thủ tục suy diễn mờ dựatrên cơ sở tri thức và các giá trị đầu vào đểđưa ra một giá trị dự báo ở đầu ra.- Giao diện giải mờ (Defuzzification): Cóchức năng thực hiện chuyển đổi kết quả suydiễn mờ thành giá trị đầu ra rõ. Hệ mờ thựchiện việc suy luận để tạo ra các quyết định từcác thông tin mơ hồ, không đầy đủ, thiếuchính xác.Có hai dạng mô hình mờ cơ bản:Mô hình mờ Mamdani: ( mô hình ngôn ngữ(linguistic model(1975))) được đề xuất vớimục đích ban đầu là điều khiển tổ hợp độngcơ hơi nước và nồi hơi thông qua một tập luậtdạng ngôn ngữ thu được từ những thao tácviên, người có kinh nghiệm. Đây là mô hìnhmờ điển hình nhất, với bộ luật bao gồm cácluật mà phần giả thiết và phần kết luận đều làcác tập mờ.Mô hình mờ Takagi- Sugeno (TSK): được đềxuất bởi Takagi, Sugeno và Kang vào nhữngnăm 1985. Mô hình mờ này ra đời với mụcđích sinh luật mờ từ những tập dữ liệu vào racho trước. Nó được cấu thành từ một tập cácluật mờ, trong đó phần kết luận của mỗi luậtlà một hàm (không mờ) ánh xạ các tham sốđầu vào của hệ mờ tới tham số đầu ra môhình. Tham số của các ánh xạ này có thể đượcđánh giá thông qua các giải thuật nhận dạngnhư phương pháp bình phương tối thiểu haybộ lọc Kalman. Một luật mờ điển hình trongmô hình Takagi-Sugeno có dạng sau[5]:“If x is A & y is B then z = f(x, y)”Trong đó x, y là các biến đầu vào, Ai và Bi làcác tập mờ trong phần giả thiết của mỗi luật,trong khi z = f(x, y) là một hàm rõ trong phầnkết luận. Thông thường hàm f (x, y) có dạngđa thức của hai biến đầu vào x, y.Kết hợp GAs và hệ mờĐể khởi tạo được quần thể ban đầu gồmnhững cá thể có độ thích nghi cao, chúng tôicho những giá trị đầu vào của bài toán cần tìmlời giải tối ưu vào hệ mờ, các yếu tố đầu vàocủa hệ nhận giá trị số rõ. Sau đó hệ mờ sẽ sử4113(13): 3 - 6dụng các hàm thuộc và các luật ...