phần mở đầu, phần kết luận, phần mục lục, phần tài liệu tham khảo. Các nội dung cơ bản của luận văn đƣợc trình bày theo cấu trúc nhƣ sau: Chƣơng 1. Tổng quan tối ƣu tiến hóa và bài toán phân cụm mờ Trong chƣơng này, luận văn sẽ trình bày tổng quan về tối ƣu tiến hóa, thuật toán lập trình tiến hóa (EP), chiến lƣợc tiến hóa, thuật toán di truyền với thuật giải GA, lập trình di truyền, tiến hóa vi phân với thuật toán DE và thuật toán văn hóa. Từ các thuật toán tối ƣu tiến hóa, luận văn sẽ trình bày trình bày về khái niệm tập mờ, phân cụm mờ, thuật toán phân cụm mờ và thuật toán kinh điển FCM.
Từ cơ sở đó kế thừa, dẫn chứng, phân tích hai thuật toán Black Hole và Hamorny Search để thiết kế một thuật toán lai khác tối ƣu cho phân cụm mờ. Thiết kế thuật toán tối ƣu tiến hóa lai cho phân cụm mờ Trong chƣơng này, tác giả giới thiệu hai thuật toán tối ƣu tìm kiếm đó là thuật toán Back Hole (BH)của John Wheeler, để mô tả hiện tƣợng của một khối sụp đổvới ý tƣởng lực hút tƣơng tác trong vũ trụ của các vật thể và Hamorny Search(HS) với ý tƣởng tối ƣu thuật giải nhƣ ngƣời nhạc công chơi một bản nhạc tuyệt vời.Từ đó kết hợp 2 thuật toán lại thành thuật toán khác để tối ƣu tiến hóa trong không gian tìm kiếm đó là thuật toán lai ghép BHHS. Các nhận xét, đánh giá ƣu, nhƣợc điểm của 3 thuật toán trên cũng đƣợc nhắc đến trong chƣơng này. Xây dựng ứng dụng phân tích nhu cầu khách hàng Trong chƣơng này, tác giả cài đặt thuật toán lai ghép BHHS và xây dựng phần mềm phân tích nhu cầu của khách hàng để giúp công ty sản xuất kinh doanh có những quyết định sản xuất, lựa chọn sản phẩm tốt nhất phù hợp với các quyết sách của đơn vị mình.
10 TIEU LUAN MOI download : skknchat@gmail.com CHƢƠNG I. TỔNG QUAN TỐI ƢU TIẾN HÓA VÀ BÀI TOÁN PHÂN CỤM MỜ 1.1 Tối ƣu tiến hóa Tối ƣu hóa đƣợc khởi nguồn nhƣ một ngành của Toán học, có rất nhiều ứng dụng rộng rãi trong quy hoạch tài nguyên, thiết kế chế tạo máy, điều khiển tự động, quản trị kinh doanh, kiến trúc đô thị, công nghệ thông tin, trong việc tạo nên các hệ hỗ trợ ra quyết định trong quản lý và phát triển các hệ thống lớn. Chính vì vậy, các lĩnh vực của tối ƣu hóa ngày càng trở nên đa dạng. Trong thực tế, việc tìm giải pháp tối ƣu cho một vấn đề nào đó chiếm một vai trò hết sức quan trọng.
Phƣơng án tối ƣu là phƣơng án hợp lý nhất, tốt nhất, tiết kiệm chi phí, tài nguyên, nguồn lực mà lại đem lại hiệu quả. Có rất nhiều thuật toán đã và đang đƣợc sử dụng để tối ƣu hóa. Một trong những bƣớc phát triển trong lĩnh vực này đặc biệt phải kể đến là thuật toán tối ƣu tiến hóa [1] Từ khi trái đất đƣợc hình thành, mọi sự sống trên trái đấttrải qua hàng triệu triệu năm đều đã và đang tiếp tục tiến hóa và phát triển để thích nghi với điều kiện, môi trƣờng sống. Chúng phát triển, thay đổi liên tục để sinh tồn.
Những cá thể nào yếu và không thích nghi đƣợc thì sẽ bị chết hoặc không phát triển, những cá thể thích nghi với môi trƣờng sống sẽ phát triển mạnh mẽ để tiếp tục sinh tồn, duy trì và phát triển giống nòi [2]. Trong sinh học, tiến hóa là quá trình mà qua đó các sinh vật nhận đƣợc và truyền lại các đặc tính từ thế hệ này sang thế hệ khác (lai tạo). Việc diễn ra trong một thời gian rất dài của nó giải thích nguồn gốc của các loài mới và sự đa dạng của sinh vật. Các loài cùng nhau liên quan đến nhau bởi cùng gốc, sản phẩm của sự tiến hóa và sự hình thành loài qua hàng tỉ năm.
Và từ quy luật sự sống các loài ở trên, ngƣời ta có những ý tƣởng về tính toán tiến hóa (EC). Tính toán tiến hóa là mô phỏng của quá trình chọn lọc tự nhiên trong quá trình (thủ tục) tìm kiếm. Trong tự nhiên, các sinh vật có đặc trƣng 11 TIEU LUAN MOI download : skknchat@gmail.com nhất định tác động đến sự sống và sinh sản của chúng. Những đặc trƣng này đƣợc mã hóa thành những thông tin trên các nhiễm sắc thể.
Nhiễm sắc thể con mới, đƣợc tạo ra bằng cách ghép đôi và sinh sản. Kết quả cuối cùng có đƣợc nhiễm sắc thể con có chứa đặc tính tốt nhất từ nhiễm sắc thể của bố mẹ cho phép chúng sống sót trong môi trƣờng không thuận lợi. Với quá trình chọn lọc tự nhiên chắc chắn những cá thể tốt sẽ có cơ hội đƣợc kết hợp với nhau, cho ra những con tƣơng ứng hoặc có thể tốt hơn. Trong tự nhiên sự tiến hóa là một quá trình không điều khiển, các sinh vật tốt hơn sẽ thích nghi nhiều hơn với môi trƣờng, sinh vật sống sót sẽ sinh sản, phát triển… Đó là quá trình chọn lọc và tiến hóa tự nhiên.
Các phép sử dụng trong EC bao gồm: Phép lai ghép, phép đột biến và phép chọn lọc. Các phép này có thể kết hợp với nhau trong một mô hình tiến hóa Tính toán tiến hóa là kỹ thuật tính toán dựa trên nguyên lý tiến hóa của quá trình chọn lọc tự nhiên trong thuyết tiến hóa của Darwin. Các kỹ thuật tiến hóa bao gồm: Chiến lƣợc tiến hóa, lập trình tiến hóa, thuật giải di truyền và lập trình di truyền. Định nghĩa tính toán tiến hóa: Thuật toán mô phỏng [4] một hàm f : V R , trong đó V là không gian tìm kiếm, f đƣợc gọi là hàm thích nghi chứa đựng các thông tin đặc trƣng cho bài toán.
Mỗi vòng lặp của tính toán tiến hóa có thể định nghĩa bởi công thức: vi 1 vi , f vi (1.1) Trong đó: :V R V là một hàm tạo ra một vector mới, nghĩa là một quần thể mới vi 1 từ quần thể cũ vi , thƣờng đƣợc xác định bởi dạng tính toán đang sử dụng, cách chọn quần thể mới từ quần thể cũ và các con mới sinh ra cùng. Tính toán tiến hóa nhƣ là một khái niệm chung cho giải quyết bài toán, đặc biệt đối với bài toán tối ƣu hóa và áp dụng các thuật toán tiến hóa đã giải quyết đƣợc các bài toán tối ƣu khó. Ngày nay thuật toán trên thu hút rất nhiều nhà nghiên cứu tham gia nghiên cứu. 12 TIEU LUAN MOI download : skknchat@gmail.com Các khái niệm liên quan: - Biểu diễn cá thể: Mỗi cá thể biểu diễn trong thuật giải di truyền tƣơng ứng với một giải pháp của bài toán.
- Đánh giá độ thích nghi: Độ thích nghi là khả năng phù hợp của mỗi cá thể hay mỗi giải pháp đối với môi trƣờng, môi trƣờng tƣơng ứng với bai toán đang cần giải quyết. Xây dựng độ thích nghi cũng là một bƣớc quan trọng trong thuật toán di truyền. Để đánh giá đƣợc độ thích nghi của các cá thể giải thuật di truyền sử dụng một hàm đo dộ thích nghi. - Lai ghép: Là quá trình tạo ra các cá thể mới dựa trên nhiều cá thể đã có, gọi là cá thể cha - mẹ.
Hai cá thể con đƣợc - Đột biến: Là quá trình tạo ra cá thể mới từ một cá thể ban đầu bằng cách thay đổi một số gen của nó. - Chọn lọc và thay thế: Chọn lọc và thay thế là quá trình chọn những cá thể từ quần thể hiện tại để tạo ra thế hệ sau của nó. Trong quá trình này diễn ra sự đào thải những cá thể yếu, chỉ giữ lại những cá thể tốt. Những cá thể có độ thích nghi lớn hơn hoặc bằng với độ thích nghi tiêu chuẩn sẽ đƣợc giữ lại và độ thích nghi của cá cá thể trong quần thể sẽ tốt hơn sau nhiều thế hệ.
- Điều kiện dừng:Thuật toán di truyền là một quá trình ngẫu nhiên, nên không thể đảm bảo chắc chắn thuật toán sẽ dừng sau hữu hạn bƣớc. Vì vậy, để đảm bảo thuật toán di truyền kết thúc, ngƣời dùng thƣờng phải định nghĩa điều kiện dừng cho thuật toán di truyền. Thuật toán lập trình tiến hóa (EP) Thuật toán lập trình tiến hóa đƣợc đề xuất bởi Lawrence J. Fogel trong những năm 1960, là chiến lƣợc tối ƣu hóa ngẫu nhiên.
EP sau đó đƣợc phát triển thêm bởi David Fogel trong năm 1990 [5]. Thuật toán lập trình tiến hóa EP khác thuật toán tiến hóa khác là không có lai ghép mà chỉ thực hiện phép lựa chọn và phép đột biến để sinh ra thế hệ quần thể mới. 13 TIEU LUAN MOI download : skknchat@gmail.com EP tập trung vào sự phát triển của các hành vi và những mẫu không di truyền. EP có nguồn gốc từ mô phỏng các hành vi tiến hóa tƣơng ứng.
Do đó, EP nhƣ là một tiến hóa kiểu hình. Quá trình tiến hóa là quá trình tìm tập các hành vi tối ƣu từ tập các hành vi quan sát đƣợc. Với thuật toán này, độ đo thích nghi đo hành vi lỗi của cá thể trong quần thể trong môi trƣờng của cá thể đó. Mục tiêu của thuật toán có thể là tìm giải pháp tối ƣu hoặc tìm giải pháp nhanh nhất.
Thuật giải EP Gồm 4 bƣớc (EP đƣợc lặp cho đến khi một vƣợt qua một ngƣỡng cho trƣớc hoặc thu đƣợc một giáp pháp thích hợp): Bƣớc 1:Khởi tạo quần thể. Một quần thể đƣợc khởi tạo ngẫu nhiên, bao gồm không gian tìm kiếm của bài toán tối ƣu. Số lƣợng các cá thể trong quần thể phù hợp với tốc độ tối ƣu hóa, nhƣng không xác định đƣợc bao nhiêu cá thể là đủ và bao nhiêu cá thể là lãng phí. Bƣớc 2: Đột biến.
Các cá thể con đƣợc sinh ra bằng thực hiện phép đột biến ngẫu nhiên trên quần thể cha mẹ. Mức độ của đột biến đƣợc đánh giá dựa trên thay đổi chức năng so với cha mẹ. Bƣớc 3:Đánh giá. Mỗi cá thể đƣợc đánh giá bằng tính giá trị hàm mục tiêu.
Quá trình chọn lọc tự nhiên trong EP thƣờng dựa trên độ đo thích nghi. Cá thể đƣợc lựa chọn cho thế hệ tiếp theo dựa trên độ đo thích nghi tƣơng đối. Bƣớc 4: Lựa chọn. Mục tiêu lựa chọn cá thể từ cha mẹ và con cháu cho thế hệ sau.
Thông thƣờng, có sự đấu tranh ngẫu nhiên để xác định N cá thể đƣợc giữ lại cho thế hệ sau. EP thực hện phép lựa chọn và phép đột biến để sinh ra thế hệ quần thể mới. 14 TIEU LUAN MOI download : skknchat@gmail. Chiến lƣợc tiến hóa Chiến lƣợc tiến hóa (ES) [6] đƣợc đề xuất để giải quyết bài toán tối ƣu hóa các tham số do Rechenberg năm 1960 và tiếp tục phát triển bởi Schwefel.