Luận văn Tiếp cận thuật toán meta - Heuristic giải bài toán tối ưu hóa quá trình sản xuất

nghiệm. Để thực hiện các bước trên, thông thường các kỹ thuật giải sau được áp dụng: - Quy hoạch: tuyến tính, động, phi tuyến. - Quy hoạch luồng. - Quy hoạch động. - Cận – nhánh. 17 - Quy hoạch thỏa mãn ràng buộc. - Các thuật giải heuristic, approximation, tiến hóa (evolutionary), meta- heuristics. - Thuật giải ngẫu nhiên. Trong thực tế quản lý và vận hành, do các bài toán hiện nay sẽ xuất hiện với tốc độ nhanh và biến đổi liên tục nên nhiều bài toán, đặc biệt trong sản xuất, có yêu cầu tìm nghiệm tối ưu (nghiệm gần đúng). Về tổng quan, bài toán CFP là một bài toán có độ phức tạp không đa thức (NP). Về bản chất, đây là bài toán tổ hợp. Các thuật toán giải CFP bao gồm nhiều định hướng toán học. Cụ thể các nhóm phương pháp như: - Kỹ thuật phân tích gom cụm (clustering) nhằm nhận biết cấu trúc trong một tập dữ liệu. Như Chandrasekharan và Rajagopalan (1989) [11] đề xuất phương pháp “grouping efficiency”; Kumar và Chandrasekharan (1990) [31] đề xuất phương pháp “grouping efficacy”; Hsu (1990) [25] đề xuất giải pháp “group capability index”... - Phân hoạch đồ thị (graph) với graph hay một mạng đại diện được sử dụng để xây dựng CFP. Nhóm phương pháp này sử dụng các thuật toán phân tích đồ thị để tìm kiếm tối ưu. - Các phương pháp quy hoạch toán học đưa CFP về bài toán quy hoạch nguyên. Việc lựa chọn các nghiệm trong bài toán CFP là các nghiệm nguyên thỏa cực đại về số nhóm được tạo thành. - Các phương pháp Heuristics như tìm kiếm (SA), tìm kiếm Tabu (Tabu Search), thuật toán di truyền (GA), tối ưu cục bộ (PSO), mạng nơron (ANN). Chi tiết hơn về các phương pháp heuristic đối với bài toán CFP. Hiện tại, nhiều nhóm nghiên cứu đã thử nghiệm nhiều phương pháp heuristics khác nhau để giải bài toán CFP. Sơ lược bao gồm những thử nghiệm nghiên cứu: - Nhóm các phương pháp tìm kiếm cục bộ (local search algorithm). - Nhóm các phương dựa trên quần thể (population-based method). - Các phương pháp lai (hybrid). 18 Những phương pháp trên được áp dụng với các chiến lược tìm kiếm theo thống kê hoặc theo các chiến lược. Cụ thể hơn, cho đến nay, phần lớn các nghiên cứu đều xem xét đến dữ liệu phân tích dòng sản xuất (PFA) và cố gắng nhóm các bộ phận và máy để thỏa các tiêu chí được tối ưu như tính hiệu quả nhóm, tính hiệu nghiệm nhóm, hiệu quả về kỹ thuật nhóm,... Trong các phương pháp PFA, hầu hết ma trận 2 chiều bộ phận - máy, là ma trận A = [aij], được sử dụng. Với aij=1, nghĩa là bộ phận i cần xử lý trên máy j, ngược lại aij=0. Bài toán CFP nhằm đến nhóm tất cả các "1" trong dạng khối đường chéo. Trong một số nghiên cứu gần đây, đa số xem CFP như một ma trận incident bộ phận - máy nhị phân được đề cập. Ví dụ nghiên cứu của Chen và Cheng (1995) [41] xét mạng nơron dựa vào CFP trong CM. Cụ thể hơn, Chen và Cheng sử dụng lý thuyết cộng hưởng (ART – adaptive resonance theory) với nền tảng mạng nơron cho bài toán CF trong CM. Được biết, theo wikipedia, ART là lý thuyết do Stephen Grossberg và Gail Carpenter phát triển dựa trên khía cạnh “làm thế nào não xử lý thông tin” và ART sử dụng nhiều mô hình mạng neuron vừa có học giám sát vừa học không giám sát để nhận dạng mẫu và dự báo. Ưu điểm của mạng ART so với phương thức truyền thống là tính toán nhanh và khả năng vượt trội xử lý các vấn đề diện lớn trong công nghiệp vì, một cách khái quát, mô hình ART sẽ nhận diện đối tượng theo phương pháp quan sát kì vọng từ trên xuống (top-down) và “gặt hái/thu nhận” thông tin từ dưới lên (bottom-up). Mahdavi, Kaushal và Chandra (2001) [42] đề xuất phương án mạng đồ thị nơron giải quyết bài toán CF. Nhiều nỗ lực để phát triển một thuật toán đáng tin hơn các phương thức truyền thống được đưa ra. Những nghiên cứu có khả năng xử lý các vấn đề công nghiệp lớn mà không cần giả thiết tham số hoặc các thành phần thiếu trong các máy/bộ phận bị nghẽn cổ chai. Soleymanpour và cộng sự (2002) [43] áp dụng phương pháp mạng nơron hỗn độn (TCCN) cho thiết kế CM. Thuật toán TCCN nhằm vào mục đích nhóm các thành phần tương đồng và máy không tương đồng để cực tiểu tổng thành phần ngoại lệ. Theo [3], một mạng được xây dựng và thuật toán đề xuất để thử nghiệm nhóm 18 19 vấn đề. Các kết quả được so sánh với các phương pháp khác nhau như: ART1 (là mạng ART đơn giản với các giá trị nhập nhị phân), ART1 mở rộng, phương pháp OSHN (Ortho-Synapse Hopfield Neuron Network). Kết quả là phương pháp đề xuất có ba ưu điểm chính bao gồm: khả năng tránh các cực tiểu địa phương; khả năng giải quyết các vấn đề có kích thước khác nhau có cùng tập giá trị tham số; và thời gian tính toán giảm thiểu. Wang (2003) [44] trình bày một thuật toán phân công tuyến tính cho ô máy và hình thành họ bộ phận cho việc thiết kế các hệ thống CF. Đầu tiên, giải pháp trình bày bằng việc quyết định họ bộ phận hoặc ô-máy được thể hiện bằng việc so sánh các hệ số tương tự giữa các bộ phận và máy và tìm kiếm tập các bộ phận và máy ít tương đồng. Bằng việc sử dụng nhóm thể hiện và các hệ số tương tự liên hệ nhau, mô hình gán nhãn tuyến tính được hình thành để giải bài toán CFP cấp phát các bộ phận còn lại cho máy và tối ưu về chỉ số tương tự. Dựa trên mô hình gán tuyến tính được hình thành, thuật toán thành lập nhóm được phát triển. Mahdavi, Javadi, Alipour và Slomp (2007) [45] đề xuất mô hình toán học mới cho hình thành ô trong hệ thống CM (gọi là CMS – cellular manufacturing system), dựa trên khái niệm về sử dụng các ô. Mục tiêu của mô hình là tối thiểu số lượng void trong cell để đạt được tốc độ cao hơn về cell utilization. Kiểm chứng mô hình bằng phần mềm LINGO 8 sử dụng phương pháp rẽ nhánh và biên (B&B). Năm 2008, Wu, Chang và Chung đề xuất phương án đơn giản hiệu quả giả lập dựa trên kỹ thuật annealing để hình thành các nhóm máy – bộ phận khi hệ thống sản xuất được thể hiện bằng ma trận quan hệ giữa máy – bộ phận với trị 0 và 1. Năm 2009, Iraj Mahdavi và cộng sự [1] đã đề xuất mô hình hệ phi tuyến với các biến nguyên và mô hình được đề xuất giải cho bài toán có kích thước thật bằng thuật toán di truyền. Và phương pháp hiệu quả nhóm (group efficacy) có kết quả tốt hơn so với các phương pháp cell formation hiện tại. Như vậy, bài toán CF được phát biểu theo một mô hình toán học dưới dạng bài toán tối ưu. Đồng thời, bài toán CF được định hướng giải theo phương pháp heuristic với các nghiên cứu liên quan. Dưới đây là tổng quan một số phương pháp tìm kiếm gần 20 đúng (heuristic). 2.2. Tổng quan về heuristic và tìm kiếm cục bộ 2.2.1 Tìm kiếm heuristic Tìm kiếm heuristic là một kỹ thuật thông minh nhân tạo sử dụng tính chất gần đúng cho việc tìm kiếm. Heuristic là luật có xác suất cho việc giải quyết một vấn đề. Các phương pháp heuristic đóng vai trò lớn trong các chiến lược tìm kiếm cho nhiều bài toán phức tạp. Các đặc điểm của một thuật toán heuristic: - Không phải lúc nào cũng tìm được giải pháp tốt nhất. - Tuy nhiên, tìm được giải pháp tốt trong thời gian hợp lý. Từ đó, phương pháp heuristic thường được sử dụng để giải các bài toán nhằm đạt đến hai yếu tố chính: thỏa mãn yêu cầu đưa ra và định hướng tăng cường hiệu quả trong điều kiện: hoặc không tìm được thuật toán hay cách giải chính thức cho bài toán; hoặc giải pháp có thuật toán nhưng thời gian kéo dài vô tận hay việc tính toán cần khoảng thời gian rất lớn. Về quy trình, phương pháp tìm kiếm heuristic bao gồm các bước sau: - Bước 1: Sinh tập nghiệm có thể từ từ không gian bài toán hoặc từ các trạng thái ban đầu. - Bước 2: Kiểm tra để tìm ra các giải pháp thực so sánh với trạng thái đạt đến các trạng thái mục tiêu. - Bước 3: Nếu nhận được kết quả tốt thì dừng. Ngược lại lặp lại bước 1 để phát sinh tập nghiệm có thể khác. Với quan điểm trên, tư tưởng của heuristic được áp dụng trong nhiều lĩnh vực khác do có các ưu điểm về: tốc độ tìm kiếm và có thể kết hợp các phương pháp khác. Tuy nhiên, phương pháp cũng có một số nhược điểm là cần đến kiến thức, kinh nghiệm cũng như chuyên gia nhận định vấn đề để xây dựng các nghiệm vì những ước tính có thể nhận dạng được các vấn đề nhỏ mà không xử lý hoặc lường trước được các vấn đề lớn phát sinh trong khi tìm kiếm. Một số kỹ thuật về thuật toán heuristic được ứng dụng như sau: phương pháp thuần heuristic (pure heuristic search), tìm kiếm chiều sâu (depth-first search), tìm kiếm 21 chiều rộng (breadth-first search), thuật toán A* ứng dụng trong tìm kiếm đường đi ngắn nhất, Hiện nay, heuristic được phát triển theo nhiều hướng khác nhau với các dạng như: meta-heuristic và hyper-heuristic. Theo đó, hyper-heuristic được sử dụng trong việc tìm kiếm hình thức liên quan đến các kỹ thuật máy học, các quá trình lựa chọn, tổ hợp, phát sinh hoặc dựa theo một số loại heuristic cơ bản. Hyper-heuristic thường áp dụng cho các nghiên cứu về xây dựng các hệ thống để xử lý phân loại các lớp bài toán (hơn là chỉ xử lý một vấn đề). 2.2.2 Tìm kiếm meta-heuristic Trong khoa học máy tính và toán học, phương pháp metaheuristic là tiến trình heuristic mức cao để tìm, phát sinh và chọn phương án gần đúng với đầy đủ tiêu chí tìm nghiệm tốt hơn cho một bài toán tối ưu. Phương pháp metaheuristic đặc biệt phù hợp với các bài toán thiếu hoặc không đầy đủ thông tin hoặc các bài toán giới hạn về khả năng tính toán. Phương pháp metaheuristic tạo mẫu tập nghiệm và thường ứng dụng cho cả các bài toán tối ưu chưa được giải. Do đó, phương pháp metaheuristic được sử dụng trong nhiều bài toán. So sánh với các thuật toán tối ưu và các phương pháp lặp, metaheuristics không đảm bảo nghiệm được giải là tối ưu toàn cục với một số bài toán. Nhiều phương pháp metaheuristic được cài đặt dựa trên các kỹ thuật tối ưu ngẫu nhiên với các “nghiệm” tìm thấy phụ thuộc trên tập biến ngẫu nhiên sinh ra. Trong các bài toán tối ưu tổ hợp, bằng việc tìm kiếm trên tập nghiệm khả thi, metaheuristic có thể tìm thấy nghiệm tốt với việc tính toán ít hơn các giải thuật tối ưu, lặp hoặc các giải thuật heuristic đơn giản. Về phân loại, đến nay, metaheuristic được phân thành các loại sau: - Tìm kiếm cục bộ (local search) và tìm kiếm toàn cục (global search). - Tìm nghiệm đơn (single solution) và tìm nghiệm quần thể (population- based). - Thuật toán lai (hybridization) và thuật toán thuần (memetic). - Các thuật toán metaheristic song song (parallel metaheuristic). 22 - Các thuật toán metaheuristic theo cảm hứng của sinh vật theo tự nhiên (như: các thuật toán đàn kiến - ant, đàn ong - bee, chim cu - cookie,). Các giải thuật metaheuristics gồm các đặc tính sau: - Có các chiến lược đề ra phục vụ tiến trình tìm kiếm. - Mục tiêu là khám phá một cách tối ưu không gian tìm kiếm để tìm được các giải pháp gần tối ưu. - Các kỹ thuật sử dụng trong các thuật toán metaheuristic gồm cả các tiến trình tìm kiếm cục bộ đơn giản đến các tiến trình học phức tạp. - Các thuật toán metaheuristic đều là xấp xỉ (approximate) và thường là bất định (non-deterministic). - Lưu ý: metaheuristic không phải là việc xác định bài toán (problem- specific). 2.2.3 Tìm kiếm cục bộ Trong khoa học máy tính, tìm kiếm cục bộ, một nhánh nhỏ của meta-heuristic, là một phương pháp heuristic để giải quyết các bài toán tính toán và tối ưu hóa. Tìm kiếm cục bộ được sử dụng để tìm các giải pháp cực trị các tiêu chí giữa các giải pháp đề xuất. Chi tiết hơn, tìm kiếm cục bộ (local search) là thuật toán lặp để di chuyển từ một giải pháp S thành giải pháp S’ dựa trên cấu trúc lân cận được định nghĩa. Và việc thay đổi các giải pháp đến khi vượt quá thời gian tìm kiếm hoặc giải pháp có khả năng tối ưu nhất xuất hiện. Với ưu điểm sử dụng ít bộ nhớ và luôn tìm kiếm được các “nghiệm” hợp lý trong không gian trạng thái liên tục/lớn, các giải pháp tìm kiếm cục bộ điển hình được áp dụng trong nhiều ứng dụng như: bài toán người bán hàng (TSP – Traveling Salesman Problem),... và các bài toán khác trong khoa học máy tính (đặc biệt trong trí tuệ nhân tạo), trong toán học, điều khiển học, sinh tin học... Về quy trình, thông thường tìm kiếm cục bộ sẽ bao gồm bốn bước sau: - Bước 1: Bước khởi tạo (initialisation) bằng việc chọn một nghiệm S ban đầu và tính giá trị hàm mục tiêu F(S). 23 - Bước 2: Bước sinh các “lân cận” (neighbour generation) bằng việc chọn các nghiệm “lân cận” S’ và tính các giá trị F(S’). - Bước 3: Bước kiểm định chấp nhận (acceptance test) là kiểm định chấp nhận sự di chuyển từ S sang S’. Nếu chấp nhận di chuyển này thì giải pháp S’ sẽ thay thế S. Ngược lại, S vẫn giữ là giải pháp hiện hành. - Bước 4: Kiểm định để dừng tìm kiếm (termination test) là bước quyết định thuật toán có dừng hay không. Nếu dừng, đầu ra phải là một trong những giải pháp tối ưu. Ngược lại, thuật toán tiếp tục tìm kiếm những “lân cận” như bước 1. Hiện tại, bốn kỹ thuật tìm kiếm cục bộ bao gồm: iterative improvement (kỹ thuật hill climbing hoặc greedy local search), threshold accepting (kỹ thuật gradient method), Simulated Annealing và kỹ thuật tìm kiếm Tabu search (thuộc nhóm thuật toán di truyền). Các thuật toán đều tương đồng ở các bước 1, 2 và 4. Với bước 3, việc chấp nhận một giải pháp S’ không tối ưu hơn S là đặc điểm của từng giải pháp như bảng dưới đây: Bảng 2.4: Các dạng tìm kiếm cục bộ TT Kỹ thuật tìm kiếm cục bộ Điều kiện chấp nhận S’ Giải thích thêm 1 Iterative Improvement F(S’) < F(S) 2 Threshold Accepting F(S’) 0, là giá trị threshold. α ban đầu mang giá trị lớn, sau sẽ bé dần 3 Simulated Annealing Nếu : chọn Nếu : chọn với Sử dụng Kiểm định chấp nhận xác suất (Probabilistic Acceptance Test). T thay đổi trong suốt thuật toán. T ban đầu lớn. Sau đó T sẽ nhỏ dần 24 TT Kỹ thuật tìm kiếm cục bộ Điều kiện chấp nhận S’ Giải thích thêm xác suất với T là tham số theo thời gian. 4 Tabu Search Chấp nhận nghiệm S’ “tồi” hơn Mọi nghiệm được lưu vào trong danh sách tabu list để theo dõi các nghiệm mới phát sinh. Do đó, chúng ta phải biện luận thêm các nghiệm đã hoặc chưa thuộc về danh sách nghiệm (non-tabu). Theo đó, cả hai thuật toán Threshold Accepting và Simulated Annealing có thể quay lại nghiệm đã duyệt. Và giải pháp để việc tìm nghiệm không bị lặp là chúng ta tạo ra một danh sách (gọi là tabu list). Các giải pháp mới được chấp nhận sẽ được đưa vào trong danh sách. Với phương án tabu search, việc tìm kiếm sẽ loại bỏ được những cực trị trong khu vực nhỏ để tiến đến cực trị toàn cục. Mặt khác, về phân lớp, hai lớp tìm kiếm cục bộ bao gồm: tìm kiếm cục bộ trên một phần miền nghiệm (partial solutions) và tìm kiếm cục bộ dựa trên toàn bộ miền nghiệm (complete solution). 2.4. Các thuật toán giải gần đúng CFP Nhánh nhóm thuật toán metaheuristic phát triển rực rỡ trong những năm gần đây với nhiều ưu điểm như độc lập thông tin, uyển chuyển và hiệu quả, ẩn song song, đã góp phần thúc đẩy các nghiên cứu giải bài toán CF trong CM bằng kỹ thuật thuật toán di truyền. Là một trong những phương pháp metaheuristic, thuật toán di truyền (GA – genetic algorithm) là một trong những giải pháp tối ưu mới để bắt chước các tiến trình tự nhiên để tạo các tiến trình tối ưu (Goldberg, 1989). 25 Hình 2.3: Minh họa về một chuỗi “nhiễm sắc thể” Theo đó, dựa trên tính tương tự của các hiện tượng chọn lọc tự nhiên trong sinh học, đầu tiên, một cấu trúc nhiễm sắc thể (chromesome) để thể hiện các giải pháp cho vấn đề. Sau đó, các thành phần của quần thể được chọn, dựa trên hàm ước lượng, gọi là hàm phù hợp (fitness), liên quan đến giá trị mỗi thành phần dựa trên hàm mục tiêu. Giá trị phù hợp cao hơn của thành phần thì sẽ được ưu tiên chọn. Do đó, các cá nhân ít phù hợp sẽ được thay thế bằng cái phù hợp hơn. Các phép toán về di truyền được áp dụng để chọn các thành viên tạo ra thế hệ quần thể mới. Tiến trình này được lặp lại khi đến số lượng các bước lặp nhất định. Thuật toán di truyền do Holland phát triển (1975) được sử dụng rộng rãi như một phương pháp thay thế cho việc giải các bài toán tối ưu trong các ứng dụng khác nhau như kỹ thuật, kinh tế, nông nghiệp, kinh doanh, truyền thông và sản xuất (theo Gen và Cheng, 1997 [46]; Goldberg, 1989 [47]; Man, Tang và Kwong, 1999 [48]). Như một phương pháp tìm kiếm chung, ưu điểm một thuật toán di truyền là kết hợp các thành tố tìm kiếm có hướng và ngẫu nhiên để khám phá không gian tìm kiếm để đạt được kết quả tốt nhất. Các nghiên cứu về thuật toán di truyền áp dụng đối với bài toán CF trong CM gồm: - Venugopal và Narendran (1992) [50] mô hình CFP dựa trên cực tiểu sự biến đổi tổng tải trên cell sử dụng thuật toán di truyền. - Joines, Culbreth và King (1996) [27] sử dụng quy hoạch nguyên cho bài toán thiết kế cell và sử dụng thuật giải di truyền để giải mô hình sau đó. - Zhao và Wu (2000) [51] thể hiện thuật giải di truyền cho CF với nhiều đường đi (route) và đa mục tiêu. - Onwubolu và Mutingi (2001) [51] phát triển giải thuật di truyền để giải sự thay đổi của tải trong ô. - Brow và Sumichrast (2001) [53] đề cập đến bài toán nhóm tổng quát, nghĩa là mỗi bộ phận có hơn một tiến trình route. Bài toán được hình thành như bài 26 toán quy hoạch nguyên và đề xuất tiến trình giải quyết dựa trên một thuật toán di truyền. - Goncalves và Resende (2004) [54] trình bày một giải pháp mới để phân “họ” machine cell và sản phẩm. Phương pháp kết hợp heuristic tìm kiếm cục bộ với một thuật toán di truyền. - Ngoài ra còn có các nghiên cứu của Papaioannou và Wilson (2010). Về nguyên lý, thuật toán di truyền được cài đặt theo nhiều cách khác nhau với 06 bước như sau: Hình 2.4: Lược đồ công việc khung tổng quát cho thuật toán di truyền - Bước 1: Xây dựng lược đồ mã hóa (coding). Bước này để mã hóa các lựa chọn thành dãy. 27 - Bước 2: Khởi tạo quần thể (create initial population). - Bước 3: Tính toán, đánh giá và ước lượng mức độ phù hợp của mỗi thành phần trong quần thể. - Bước 4: Luật/Thủ tục chọn. Xác định nghiệm đã được chọn lựa theo các giá trị tham số điều khiển nhất định (như: kích thước quần thể, số lần lặp tối đa, các xác suất cho phép toán di truyền). - Bước 5: Nếu nghiệm được chọn thì tiến hành giải mã và kết xuất phương án (problem decoding) và kết thúc tiến trình. Ngược lại sang bước 6. - Bước 6: Phép toán di truyền để tạo dựng cho thế hệ mới bằng các phép toán như: lai chéo (crossover), đột biến (mutation), và lặp bước 3. Lưu ý: phép đột biến là thay đổi nhỏ (thường là đảo bit ngẫu nhiên) tại một vị trí trong chuỗi gen. Hình 2.5: Minh họa một phép “lai” crossover 2.4.1 Xây dựng lược đồ mã hóa Với bất kì một cài đặt của GA, bước đầu tiên là định các đặc tính của giải pháp trong định dạng chuỗi nhiễm sắc thể. Mỗi nhiễm sắc thể được tạo từ các gen tuần tự từ các chữ cái nhất định. Chữ cái có thể là số nhị phân, số thực, biểu tượng hoặc ma trận (theo Goldberg, 1989 [47]). Việc thể hiện lược đồ quyết định không chỉ là tính ảnh hưởng của bài toán được cấu trúc mà còn thể hiện hiệu quả của phép toán di truyền được sử dụng. Ví dụ: dưới đây là một loại mã được sử dụng trong một nghiên cứu như sau: mỗi 28 gen thể hiện số lượng ô mà máy hoặc bộ phận phụ thuộc (Chu và Tsai, 2001 [48]; Venugopal và Narendra, 1992 [49]). Sự thể hiện nhiễm sắc thể gồm hai phần: phần đầu thể hiện các bộ phận và phần hai thể hiện các máy. Nhiễm sắc thể sử dụng cho bài toán CF có thể được thể hiện như bên dưới với Pi là nhóm với bộ phận i được gán và Mj thể hiện nhóm mà máy j được gán: P1 P2 P3 P4 ... Pp M1 M2 M3... Mm Khi đó, xét một nhiễm sắc thể cho một vấn đề CF với 10 bộ phận và 10 máy: 2 2 2 3 3 1 1 1 2 2 2 2 1 1 2 3 3 1 1 1 Nhiễm sắc thể trên nghĩa là: 3 ô đầu trong phần 1 thuộc về cell 2, máy thứ 3 thuộc cell 1,... Và như thế, ô 1 chứa các bộ phận {6, 7, 8} và máy {3, 4, 8, 9, 10}, ô 2 chứa các bộ phận {1,2,3,9,10} và máy {1,2,5}, và ô 3 chứa các bộ phận {4,5} và máy {7,8}. Lưu ý rằng phần bộ phận và máy trong nhiễm sắc thể đã cố định theo kích thước của bài toán. 2.4.2 Khởi tạo quần thể Bước thứ hai trong việc cài đặt GA là phát sinh tập nghiệm ban đầu, gọi là quần thể. Số lượng nghiệm ban đầu gọi là kích thước quần thể. Quần thể khởi tạo được phát sinh một lần duy nhất tại thời điểm phát sinh của thuật toán. Kích thước của quần thể quyết định đến việc cài đặt thuật toán GA. Nếu kích thước quần thể nhỏ, chúng ta không thể nhận nghiệm tốt. Ngược lại, nếu kích thước quần thể lớn, việc tính toán sẽ chiếm nhiều thời gian (Back, Fogel và Michalawecz, 1997 [50]). Ví dụ: trong bài toán CFP, một tiến trình đặc biệt được phát triển để phát sinh quần thể khởi tạo ngẫu nhiên thỏa các ràng buộc các biến quyết định, nghĩa là mỗi máy và mỗi bộ phận chỉ được gán vào một ô. Nhắc lại ràng buộc các biến quyết định được phát biểu trong chương 1: 29 2.4.3 Mức độ tuân theo độ phù hợp của mỗi thành phần trong quần thể Trong cài đặt GA, hàm phù hợp được sử dụng để ước tính và tái tạo ra các nhiễm sắc thể mới gọi là các con cháu cho các thế hệ kế tiếp. Mục tiêu của hàm phù hợp là đo đạc độ "tốt" của ứng viên nghiệm trong quần thể so với hàm mục tiêu và các ràng buộc trong mô hình. Giá trị phù hợp của các nhiễm sắc thể trong thuật toán đề xuất là tổng số voids và EE trong tất cả các ô. 2.4.4 Luật chọn Goldberg (1989 [47]) đề xuất luật chọn Roulette Wheel theo tiêu chí cá nhân “phù hợp” nhất được xem xét thường xuyên để tạo ra “con cháu” và thế hệ tiếp theo. Mỗi cá nhân được gán một xác suất chọn dựa trên giá trị phù hợp. Tuy các cá nhân có xác suất chọn lớn hơn sẽ được chọn nhiều hơn nhưng tất cả các cá thể trong quần thể đều có cơ hội được chọn. Do đó, chúng ta có thể chọn các “bố mẹ” ngẫu nhiên sau khi xếp hạng các cá thể dựa trên sự phù hợp và đặt trọng số xác suất chọn cho mỗi cá thể trong quần thể. 2.4.5 Phép toán di truyền Mục đích các phép toán di truyền là tạo ra các thế hệ “con cháu” mới trên các “bố mẹ” được chọn lọc. Với bài toán CFP, phép toán di truyền có thể bao gồm:  Phép toán “lai” (crossover): là phép toán kết hợp thông tin của bố lẫn mẹ để “con cái” có tính chất “giống” cả bố lẫn mẹ. Theo nghiên cứu của Goldberg (1989) [47], thông thường, các kỹ thuật crossover là: 1-điểm, 2-điểm và đồng dạng. Tuy nhiên, nếu ứng dụng phép toán này có sự sai về nhiễm sắc thể nào đó, những sự thay đổi như các phương pháp PMX (crossover một phần), OX (order crossover), CX (cycle crossover) sẽ được sử dụng. Tóm lại, đây là phép toán để tạo ra “con” có tính chất giống với “bố mẹ”. Ví dụ với bài toán CFP, hai phép crossover có thể như sau: - Crossover đơn (simple crossover): với 2 cá thể “bố mẹ” được lựa chọn ngẫu nhiên từ quần thể. Khi đó, chọn ngẫu nhiên một số r có giá trị từ 1 đến M+P (với M là số lượng máy và P là số lượng bộ phận). Khi đó, gen từ r đến M+P của bố mẹ sẽ đổi nhau để tạo ra 2 nhiễm sắc thể con mới. 30 Hình 2.6: Minh họa về phép toán lai đơn giản (simple crossover) - Crossover đồng dạng (uniform crossover): với mỗi cặp “bố mẹ” được chọn ngẫu nhiên, một phần nhỏ gen được chọn ngẫu nhiên sẽ thay đổi cho nhau. Hình 2.7: Minh họa phép toán lai đồng dạng (uniform crossover)  Phép toán đột biến (mutation operator): phép toán sẽ biến đổi giá trị của gen ngẫu nhiên dựa trên những xác suất nhỏ của phép biến đổi. Phép biến đổi ngẫu nhiên và hoàn toàn không có định hướng tối ưu cho nghiệm. Ví dụ, với một cá thể từ quần thể và một giá trị r (1 ≤ r ≤ M+P), chúng ta có thể tạo quy luật biến đổi ngẫu nhiên với một ar là gen thứ r của nhiễm sắc thể được chọn: Nếu ar = 1 Gán ar = C 31 Ngược lại: Nếu ar = C Gán ar = 1 Ngược lại Phát sinh một giá trị ngẫu nhiên rx nào đó từ 0 đến 1; Nếu rx ≤ 0.5 ar = ar – 1 Ngược lại ar = ar + 1 2.4.6 Các giá trị tham số (để điều khiển nhất định) Thông thường bao gồm: kích thước quần thể, số lượng thế hệ, số lượng vào lặp, các xác suất thực hiện các phép toán crossover và mutation. Các giá trị trên sẽ tác động đến không gian nghiệm. Ví dụ: việc chọn kích thước quần thể sẽ thay đổi tùy theo ứng dụng và số lần lặp sẽ ảnh hưởng đến tiến trình hội tụ của thuật toán di truyền và thuật toán crossover sẽ tác động đến hiệu quả của việc lai tạo bên cạnh phép toán mutation sẽ là nền tảng cho sự đa dạng của quần thể. Lưu ý: thông thường xác suất cho phép toán mutation rất nhỏ. Ví dụ: Bộ tham số ứng dụng thuật toán di truyền của nghiên cứu của Araj Mahdavi và cộng sự (2009) [1]: Bảng 2.5. Bộ giá trị tham số ứng dụng thuật toán di truyền trong các thuật toán TT Tham số Giá trị tham số 1 Kích thước nhiễm sắc thể M + P 2 Kích thước quần thể 1000 3 Xác suất phép toán lai chéo (crossover) 0.70 – 0.80 4 Xác suất phép toán đột biến (mutation) 0.01 – 0.1 5 Số lượng thế hệ phát sinh Biến thay đổi Tóm lại, trong chương này các phương pháp về tìm kiếm heuristic và meta-heuristic 32 được nêu lên cùng với tổng quan các phương pháp, đặc biệt là thuật toán di truyền, để giải quyết bài toá