Tối ưu tiến trình công nghệ bằng giải thuật di truyền

ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 5(126).2018, Quyển 1 125 TỐI ƯU TIẾN TRÌNH CÔNG NGHỆ BẰNG GIẢI THUẬT DI TRUYỀN OPTIMIZATION OF OPERATION SEQUENCING BASED ON GENETIC ALGORITHM Phạm Trường Tùng1, Phạm Đăng Phước2, Lưu Đức Bình3 1, 2Trường Đại học Phạm Văn Đồng; pttung@pdu.edu.vn, pphamdang@yahoo.com 3Trường Đại học Bách khoa – Đại học Đà Nẵng; ldbinh@dut.edu.vn Tóm tắt - Lập tiến trình công nghệ được xem là yếu tố quan trọng, phức tạp trong công nghệ CAPP (Computer Aided Process Planning). Bài báo trình bày việc ứng dụng giải thuật di truyền (GA) trong việc xác định tiến trình công nghệ với hàm mục tiêu là chi phí thấp nhất. Một giải thuật di truyền gồm các toán tử lai ghép, đột biến, chiến lược lựa chọn cá thể trên cơ sở “mô hình ưu tú” được đề nghị. Một ma trận ràng buộc được tạo ra trên cơ sở quan hệ hình học của chi tiết, các yêu cầu công nghệ và các tài nguyên gia công. Tiến trình công nghệ tối ưu được xác định bằng thuật toán tối ưu trên cơ sở tuân thủ các luật ràng buộc của ma trận ràng buộc. Cuối cùng, một ví dụ thực tế được đưa ra để chứng tỏ rằng tính hội tụ đến lời giải tối ưu của GA tốt hơn so với giải thuật đàn kiến (ACO). Abstract - Process sequencing is considered as the key technology for computer aided process planning (CAPP) and is very complex. This paper deals with optimization of operation sequencing based on Genetic Algorithm (GA) with the lowest cost function. A GA is proposed, including the crossover, mutation operators and selection strategy based on “elitist model”. A matrix of constrants is created based on geometrical shape of part, technology requirements and available machining resources. An optimization of operation sequencing is found through GA in compliance with rules of matrix of constrants. Finally, an experiment is presented to verify that the convergence to optimal solution is better than that to Ant colony optimization Algorithm (ACO). Từ khóa - giải thuật di truyền; CAPP; tối ưu; tiến trình công nghệ; ma trận ràng buộc. Key words - genetic algorithm; CAPP; optimization; operation sequencing; constraint matrix. 1. Đặt vấn đề Thiết kế quy trình công nghệ là quá trình đưa ra giải pháp công nghệ dựa trên các thông số đầu vào như kích thước, hình dáng vật liệu phôi; các yêu cầu kỹ thuật của chi tiết gia công; dạng sản xuất; chủng loại và thông số kỹ thuật của máy; chủng loại, kích thước và vật liệu dao; kích thước, hình dáng vật liệu phôi; các yêu cầu kỹ thuật của chi tiết gia công; các yêu cầu kinh tế xã hội; điều kiện sản xuất, bí quyết và truyền thống công nghệ, Phương pháp chuẩn bị công nghệ truyền thống mang nặng tính chủ quan và tính hợp lý phụ thuộc vào kỹ năng, kiến thức, kinh nghiệm của người thiết kế và thực tế là rất khó có thể là phương án tối ưu. Việc chuẩn bị công nghệ có sự trợ giúp của máy tính (CAPP) khắc phục được các nhược điểm của phương pháp truyền thống, nâng cao chất lượng quy trình công nghệ, rút ngắn thời gian lập quy trình công nghệ. Theo Paiva Gustavo Silva và Carvalho Marco Antonio M. [1], giải quyết bài toán lập tiến trình công nghệ là một trong những vấn đề quan trọng, khó khăn, phức tạp khi nghiên cứu CAPP, bởi đây là dạng bài toán NP (nondeterministic polymonial) khó, phi tuyến, hàm mục tiêu và các điều kiện ràng buộc là yếu tố không được định lượng rõ ràng. Do đó, việc giải bài toán bằng các giải thuật truyền thống là khó khăn và thường không cho được kết quả tối ưu. Tối ưu tiến trình công nghệ bằng cách sử dụng các giải thuật thông minh đã được quan tâm nghiên cứu trong những năm gần đây. Wang Jinfeng và Fan Xiaoliang cùng các cộng sự [2] đã sử dụng thuật toán đàn dơi lai (Hybird Bat Algorithm) dựa trên nguyên lý mô phỏng việc định vị bằng siêu âm của đàn dơi và kết hợp hai chiến lược tìm kiếm nhằm tránh vấn đề hội tụ cục bộ để lập tiến trình công nghệ tối ưu. Petrović Milica và Vuković Najdan cùng các cộng sự [3] đã sử dụng thuật toán tối ưu bầy đàn hỗn loạn CPSO (Chaotic Particle Swarm Optimization) để xác định tiến trình công nghệ và kế hoạch sản xuất tối ưu trên hệ thống sản xuất. Tran Anh Van và Nguyen Ngoc Binh [4] sử dụng thuật toán tối ưu đàn kiến (ACO) để xác định tiến trình công nghệ tối ưu. Paiva Gustavo Silva và Carvalho Marco Antonio M. [1] lại sử dụng thuật toán heuristic cải tiến để xác định chuỗi công việc và bài toán chọn dao tối ưu trong hệ thống sản xuất linh hoạt (FMS). Giải thuật di truyền (Genetic Algorithm - GA) cũng đã được quan tâm, nghiên cứu ứng dụng cho việc tối ưu hóa các hoạt động công nghệ trong sản xuất. Khan Z. và Prasad B. cùng các cộng sự [5] đã sử dụng cả hai thuật toán GA và giải thuật mô phỏng luyện kim (Simulated Annealing - SA) để xác định các chế độ cắt cho nguyên công tiện nhiều lớp với các vật liệu và dao khác nhau. Li L. và Fuh J. Y. H. cùng các cộng sự [6] ứng dụng GA trong việc xác định tiến trình tối ưu hoặc gần tối ưu trên cơ sở một số các tiêu chuẩn cho hệ thống sản xuất phân tán. Chiu Nan-Chieh và Fang Shu-Cherng cùng các cộng sự [7] sử dụng GA để xác định chuỗi hoạt động của trung tâm gia công phay/tiện với các máy song song. Bài báo trình bày việc ứng dụng giải thuật di truyền để lập tiến trình công nghệ gia công chi tiết trong sản xuất loạt nhỏ với hàm mục tiêu là giá thành thấp nhất. Thông tin chi tiết sẽ được biểu diễn theo quan điểm hướng đối tượng, các ràng buộc hình học giữa các đối tượng, các chi phí gia công cũng sẽ được tính đến. 2. Kết quả nghiên cứu 2.1. Một số các định nghĩa 2.1.1. Biểu diễn đối tượng gia công Một đối tượng gia công có thể định nghĩa bởi bốn thuộc tính như sau: ( ) , , , , i e a iF ID F A M f= (1) Trong đó: - Fi biểu diễn đối tượng gia công thứ i của chi tiết. - ID biểu diễn mã của đối tượng gia công. - Fe biểu diễn đối tượng gia công thuộc loại nào. 126 Phạm Trường Tùng, Phạm Đăng Phước, Lưu Đức Bình - A biểu diễn độ chính xác gia công. - Ma biểu diễn vật liệu. - fi biểu diễn nguyên công, hay bước nguyên công thứ i trong bảng tiến trình công nghệ. 2.1.2. Phần tử gia công Mỗi đối tượng gia công Fi có thể được tạo bởi chuỗi các nguyên công hay bước nguyên công khác nhau. Mỗi bước này gọi là phần tử gia công. Để thuận tiện, ta gọi F là tập các phần tử gia công và fi là phần tử gia công thứ i thì F = {f1, f2, fn}, với n là số các phần tử gia công. Với mỗi phần tử gia công, ta quy ước: - Một phần tử gia công chỉ thuộc về một đối tượng gia công, có thể là một nguyên công hoặc một bước nguyên công. - Một phần tử gia công chỉ sử dụng một loại dao cụ duy nhất khi gia công. - Một phần tử gia công chỉ gia công trong một lần gá đặt. - Một phần tử gia công chỉ dùng duy nhất một phương pháp gia công. Ta mô tả mối quan hệ giữa các phần tử gia công i và j bằng một ma trận gọi là ma trận ràng buộc: 12 1 21 2 1 2 0 ... 0 ... ... ... 0 ... ... 0 n n n n r r r r R r r      =       (2) Trong đó: - rij = 1 nếu phần tử gia công i được thực hiện trước phần tử gia công j; - rij = 0 nếu phần tử gia công i được thực hiện sau j. Các phần tử gia công trước khi được sắp xếp theo một tiến trình hợp lý thì trước hết phải thỏa mãn ma trận ràng buộc này. 2.1.3. Mục tiêu tối ưu hóa Khi lập tiến trình công nghệ, các nhà công nghệ luôn mong muốn lập một tiến trình gia công mà thời gian gia công là ngắn nhất, chi phí gia công là nhỏ nhất và chất lượng là cao nhất. Bài báo này chỉ xét đến mục tiêu là tối ưu hóa chi phí gia công. Chi phí gia công của chi tiết bao gồm tổng chi phí thực hiện các phần tử gia công cộng với chi phí khi vận chuyển từ phần tử này sang phần tử khác. Số lượng các phần tử gia công trên chi tiết là không đổi, do đó chi phí trên mỗi chi tiết gia công là cố định, do vậy muốn giảm chi phí gia công ta phải giảm chi phí chuyển đổi từ phần tử này sang phần tử khác. Để biểu diễn chi phí khi chuyển các phần tử gia công ta sử dụng một ma trận chi phí. Quá trình chuyển đổi giữa các phần tử chủ yếu phát sinh từ những vấn đề sau: chi phí thay đổi máy móc, chi phí thay đổi đồ gá, chi phí thay dao. Giả sử chi phí tổng là C, chi phí khi chuyển từ phần tử gia công thứ i sang thứ j là Cij. Ma trận chi phí có thể biểu diễn như sau: 11 12 1 21 22 2 1 2 ... ... ... ... ... ... ... n n n n nn C C C C C C C C C C      =       (3) Gọi ma trận khoảng cách F theo quy luật như sau: nếu rij = 0 thể hiện đối tượng gia công thứ i đứng trước đối tượng gia công thứ j, khi đó không tồn tại chi phí gia công, Cij = 0 thì fij = 0. Nếu rij = 1, chi phí gia công fij = Cij. Ma trận khoảng cách cuối cùng sẽ là: 11 12 1 21 22 2 1 2 ... ... ... ... ... ... ... n n n n nn f f f f f f F f f f      =       (4) Hàm mục tiêu là quãng đường ngắn nhất có thể được biểu diễn như sau: 1 1 j n ij i f f = − = =  (5) Ở đây, fij biểu diễn chi phí khi chuyển giữa phần tử gia công thứ i sang phần tử gia công thứ j. 2.2. Giải thuật di truyền xác định tiến trình công nghệ tối ưu 2.2.1. Giải thuật di truyền Giải thuật di truyền cũng như các thuật toán tiến hoá khác hình thành dựa trên quan niệm cho rằng quá trình tiến hoá tự nhiên là quá trình hợp lý, hoàn hảo, tự nó đã mang tính tối ưu. Quan điểm trên như một tiên đề, không chứng minh, nhưng phù hợp với thực tế khách quan. Giải thuật di truyền sử dụng một số thuật ngữ của ngành di truyền học như: nhiễm sắc thể, quần thể (population), gen.... Nhiễm sắc thể được tạo thành từ các gen. Mỗi gen mang một số đặc trưng và có vị trí nhất định trong nhiễm sắc thể. Mỗi nhiễm sắc thể sẽ biểu diễn một lời giải của bài toán. Một giải thuật di truyền cơ bản bao gồm các bước sau: Bước 1: Khởi tạo một quần thể ban đầu gồm các chuỗi nhiễm sắc thể. Bước 2: Xác định giá trị mục tiêu cho từng nhiễm sắc thể tương ứng. Bước 3: Tạo các nhiễm sắc thể mới dựa trên các toán tử di truyền. Bước 5: Xác định hàm mục tiêu cho các nhiễm sắc thể mới và đưa vào quần thể. Bước 4: Loại bớt các nhiễm sắc thể có độ thích nghi thấp. Bước 6: Kiểm tra thỏa mãn điều kiện dừng. Nếu điều kiện đúng, lấy ra nhiễm sắc thể tốt nhất, giải thuật dừng lại. Ngược lại, quay về Bước 3. 2.2.2. Thuật toán giải thuật di truyền xác định tiến trình công nghệ tối ưu Để sử dụng giải thuật di truyền tối ưu tiến trình công nghệ, nhóm tác giả đề xuất các phương pháp định nghĩa các toán tử di truyền như sau: Cá thể: Trong giải thuật này, mỗi cá thể được đại diện bởi một nhiễm sắc thể đặc trưng cho độ thích nghi của cá thể trong quần thể. Một chi tiết gia công có N phần tử gia công, được đánh số thứ tự từ 1 đến N. Ta gọi p là tập các phần tử gia công p = {1, 2, N}. Khi đó, nhiễm sắc thể E là một véc-tơ N phần tử với các phần tử véc-tơ là một phần tử gia công. ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 5(126).2018, Quyển 1 127 1 2 ... N e e E e      =       (6) Trong đó: ei p và ei  ej ij. Tập hợp các cá thể E, gọi là quần thể, ký hiệu P. Độ thích nghi của mỗi cá thể: là tổng chi phí của mỗi lời giải. Độ thích nghi chính là hàm mục tiêu của bài toán toán tối ưu cần hướng tới. 1 1 1 i i N e e i f f + − = =  (7) Trong đó: 1i ie e f + là phần tử thuộc ma trận F được định nghĩa trong (4). Sinh sản: Quá trình sinh sản là quá trình lai ghép một phần nhiễm sắc thể của cá thể cha và một phần nhiễm sắc thể của cá thể mẹ. Việc chọn các cá thể cha/mẹ để lai ghép được dựa trên độ thích nghi của các cá thể cha/mẹ trong quần thể theo nguyên tắc độ thích nghi của cá thể nào cao hơn thì xác suất được lựa chọn cũng cao hơn. Xác suất để lựa chọn cá thể cha, mẹ theo công thức (8). Chiến lược lựa chọn cá thể cha/mẹ dựa trên nguyên lý bánh xe Roullet [8]. / / f m f m f p f =  (8) Trong đó: f là tổng độ thích nghi của quần thể. Gọi k là vị trí lai ghép giữa hai nhiễm sắc thể cha Ef và nhiễm sắc thể mẹ Em. Khi đó, nhiễm sắc thể của con được lai ghép từ cặp cha mẹ trên là:  f c f mE E I E  = + Trong đó: ( )   1 k f f fi N E e I E    = =   (9)     ( )   ( )   ( ) ( ) k k N kk N k k N k N k I Zero I Zero Zero  − −  −  − =        (10) - kI là ma trận đơn vị cấp k. -  ( )N k kZero −  là ma trận 0 có (N-k) hàng và k cột. - mE  là véc-tơ có N phần tử với: ( ) 1 k mi mi mi pj j e e e e = = − (11)  f ij N N I a   =   với: 11 1 1 0 ji ij f i lj ip m j l p if i k a e a a e if i k −−   = =    =   + +           (12) ( ) 0 0 1 if u u else  = =   (13) ( ) 1 0 0 if u u else  = =   (14) Hình 1. Mô tả quá trình lai ghép Đột biến: là quá trình tạo ra một nhiễm sắc thể không mang bất kỳ kiểu nhiễm sắc thể nào từ cha và mẹ với một xác suất rất nhỏ. Trong giải thuật di truyền cho bài toán tối ưu hóa tiến trình công nghệ bằng giải thuật di truyền, ta thực hiện phép đột biến như sau: Chọn ngẫu nhiên 1 cá thể E trong quần thể; Chọn ngẫu nhiên 2 vị trí k1 và k2 trên nhiễm sắc thể của cá thể được chọn, tráo đổi 2 vị trí đó để trở thành nhiễm sắc thể cá thể E* sau đột biến. Ta mô tả bằng công thức sau:  m E I E  = (15) Trong đó:  m ij N N I b   =   (16)   1 2 1 2 1 0 0 ... 0 ... 0 0 1 0 ... ... ... 0 0 0 ... ... 0 ... 0 0 0 ... 0 0 0 0 ... 0 0 ... 0 0 0 0 1 0 0 0 1 1 0 0 0 0 ... 0 1 m N N k k I k k    = → →                       (17) Ví dụ: Hình 2. Mô tả quá trình đột biến Chọn lọc: Sau các quá trình sinh sản và đột biến, kích thước quần thể sẽ tăng lên, do đó toán tử chọn lọc là một phần rất quan trọng của giải thuật GA. Nó quyết định sự hội tụ của giải thuật đến kết quả tối ưu. Có rất nhiều các chiến lược lựa chọn đã được đề xuất. Như chiến lược “mô hình thủ lĩnh”, hay chiến lược “cạnh tranh” ... dựa trên cơ sở giới hạn quần thể của thuật toán và độ thích nghi của từng cá thể theo công thức . Trong bài báo này, nhóm tác giả sử dụng chiến lược “mô hình ưu tú” để tiến hành loại 128 Phạm Trường Tùng, Phạm Đăng Phước, Lưu Đức Bình bỏ các cá thể có độ thích nghi thấp, chỉ giữ lại các cá thể có độ thích nghi cao (tức giữ lại các kết quả tốt nhất của bài toán tối ưu). Cuối cùng, sau quá trình sinh sản, đột biến sẽ sinh ra các cá thể của một đời mới và được bổ sung vào quần thể. Thông qua quá trình chọn lọc, chỉ các cá thể tốt mới được giữ lại trong quần thể và qua một số đời, giải thuật sẽ dừng và cá thể có độ thích nghi cao nhất trong quần thể chính là đáp án cho bài toán tối ưu. 2.3. Kết quả ứng dụng giải thuật di truyền tối ưu tiến trình công nghệ. 2.3.1. Mô tả chi tiết gia công Để đánh giá các giải thuật, ta sử dụng một chi tiết gia công có 6 đối tượng công nghệ đã được trình bày và nghiên cứu trong [4]. Căn cứ vào bản vẽ và yêu cầu công nghệ, 6 đối tượng gia công này sẽ có 8 phần tử gia công. Hình 3. Mô tả chi tiết gia công Bảng 1. Bảng thông tin các đối tượng gia công Mã đối tượng Loại Kích thước Độ sâu Cấp chính xác Độ nhám Vật liệu F1 Mặt phẳng 7 3,2 CT45 F2 Trụ tròn ngoài 50 7 CT45 F3 Lỗ 12 10 7 6,3 CT45 F4 Lỗ 12 10 7 6,3 CT45 F5 Mặt phẳng 7 3,2 CT45 F6 Lỗ 30 35 7 1,2 CT45 Bảng 2. Bảng thông tin các phần tử gia công Đối tượng gia công Phần tử gia công Máy Mã đối Loại Mã Phương pháp gia tượng công F1 Mặt phẳng f1 Phay thô F1 Phay f2 Phay tinh F1 Phay F2 Trụ tròn ngoài f3 Tiện F2 Tiện F3 Lỗ f4 Khoan lỗ F3 Phay F4 Lỗ f5 Khoan lỗ F4 Phay F5 Mặt phẳng f6 Phay thô F5 Phay f7 Phay tinh F5 Phay F6 Lỗ f8 Phay lỗ F6 Phay Gọi C1 là chi phí thay đổi máy móc, C2 là chi phí thay đổi đồ gá, C3 là chi phí thay dao. Giả sử ta có C1 = 50, C2 = 10, C3 = 5. Ta lập các ma trận quan hệ và ma trận chi phí như sau: 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 R            =              (18) 0 10 65 15 15 10 15 15 10 0 65 15 15 15 15 15 65 65 0 65 65 65 65 65 15 15 65 0 0 5 5 5 15 15 65 0 0 5 5 5 10 15 65 5 5 0 5 5 15 15 65 5 5 5 0 5 15 15 65 5 5 5 5 0 C            =              (19) 0 10 65 15 15 10 15 15 0 0 65 15 15 15 15 15 0 0 0 65 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 15 65 5 5 0 5 5 0 0 65 0 0 0 0 5 0 0 0 0 0 0 0 0 F            =              (20) Tất cả các thuật toán sử dụng dưới đây để tìm tiến trình công nghệ tối ưu là tìm giá trị nhỏ nhất. Ma trận F trong (4) xuất hiện những khoảng cách giữa 2 đỉnh (i, j) = 0 (nếu không thỏa mãn ma trận R). Để đảm bảo sự hội tụ của bài toán và cũng để đơn giản hóa thuật toán, nhóm tác giả đề xuất một phương pháp: đó là nếu như không thể đi từ đỉnh i đến đỉnh j thì ta cho F(i, j) =  (một giá trị rất lớn). Khi đó kết quả có chứa cặp đỉnh (i, j) này sẽ là kết quả rất lớn, và quá trình tìm kiếm lời giải sẽ bỏ qua kết quả này. Nếu như có thể đi được từ đỉnh i → j mà chi phí bằng 0 thì ta gán cho nó một giá trị tượng trưng (trong các thuật toán sử dụng bằng 1), khi đó kết quả cuối cùng của thuật toán ta trừ đi giá trị tượng trưng này. Như vậy, ta có ma trận F sử dụng trong thuật toán được trình bày trong (22). 1000000 10 65 15 15 10 15 15 1000000 1000000 65 15 15 15 15 15 1000000 1000000 1000000 65 65 1000000 1000000 10000000 1000000 1000000 1000000 1000000 1 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 5 1000 F = (22) 000 15 65 5 5 1000000 5 5 1000000 1000000 65 1000000 1000000 1000000 1000000 5 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000                          ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 5(126).2018, Quyển 1 129 Tiến trình công nghệ tìm được được mô tả bằng một dãy chứa các mã đối tượng fi mô tả thứ tự thực hiện các nguyên công. 2.3.2. Kết quả ứng dụng thuật toán di truyền tối ưu tiến trình công nghệ Áp dụng giải thuật GA để lập tiến trình công nghệ gia công cho chi tiết trên, với kích thước quần thể là 500 cá thể, xác suất đột biến là 0,1, số đời 20. Kết quả chạy mô phỏng trên Matlab R2010b với cấu hình máy Intel Core i5- Ram 4GB, ta được tiến trình tối ưu là f1 → f2 → f6 → f7 → f3 → f4 → f5 → f8 với tổng chi phí là 166. Giải thuật có thời gian tính toán là 12s. Hình 4. Kết quả mô phỏng của thuật toán GA Kết quả nghiên cứu của [4] khi sử dụng giải thuật đàn kiến (ACO) cho cùng một chi tiết được mô tả ở trên, cho ra tiến trình công nghệ là f1 → f6 → f2 → f7 → f3 → f4 → f5 → f8 với tổng chi phí là 174. So sánh với giải thuật GA được trình bày trong bài báo này, ta thấy giải thuật GA tốt hơn nhiều, kết quả cũng cho ra tiến trình công nghệ với chi phí thấp hơn rất nhiều. 3. Kết luận Lập tiến trình công nghệ tối ưu là một vấn đề hết sức quan trọng trong công nghệ CAPP. Bài báo đã trình bày cách tiếp cận giải thuật GA với các toán tử chọn lọc, lai ghép, đột biến được mô tả bằng ngôn ngữ toán học để lập tiến trình công nghệ tối ưu. Một chi tiết điển hình với nhiều đối tượng gia công được mô tả bằng các ma trận ràng buộc, ma trận chi phí. Giải thuật GA được trình bày ở trên cũng đã được ứng dụng để tìm tiến trình công nghệ với chi phí thấp nhất và rõ ràng hiệu quả của giải thuật GA tốt hơn so với giải thuật ACO. Mức độ hội tụ đến kết quả tối ưu khi sử dụng thuật toán GA phụ thuộc rất nhiều vào kích thước quần thể, số đời, xác suất đột biến. Việc tăng kích thước quần thể và số đời sẽ làm giải thuật có khả năng tìm được lời giải tối ưu, tuy nhiên sẽ làm thời gian tính toán tăng lên rất nhiều. Giảm kích thước quần thể và số đời sẽ làm giảm thời gian tính toán, tuy nhiên kết quả đạt được chưa chắc là tối ưu. Xác suất đột biến nhỏ sẽ làm cho bài toán lâu hội tụ, tuy nhiên khi tăng xác suất đột biến sẽ dễ làm xuất hiện các cá thể có độ thích nghi thấp và duy trì trong nhiều đời liên tiếp, đôi khi sẽ làm mất khả năng đạt được điểm tối ưu cục bộ sắp đạt được trước đó. Do đó, việc lựa chọn kích thước quần thể, số đời và xác suất đột biến phải tính tới mục tiêu đạt được tiến trình công nghệ tốt ở mức chấp nhận được. Khi lập tiến trình công nghệ, các nhà công nghệ luôn mong muốn lập một tiến trình gia công mà thời gian gia công là ngắn nhất, chi phí gia công là nhỏ nhất và chất lượng cao nhất. Rõ ràng để đáp ứng được yêu cầu này, chúng ta phải giải bài toán tối ưu đa mục tiêu. Giải thuật GA trong bài báo chỉ mới giải bài toán tối ưu hóa một mục tiêu chi phí. Việc tối ưu hóa đa mục tiêu áp dụng cho lập tiến trình công nghệ sẽ được nghiên cứu tiếp theo bằng cách ứng dụng lý thuyết của Vũ Ngọc Phàn [8]. Hiện nay, các giải thuật tối ưu rất phát triển. Trong phạm vi nghiên cứu của bài báo, nhóm tác giả chưa thể trình bày được việc ứng dụng các giải thuật PSO (Particle Swarm Optimization), giải thuật luyện kim, giải thuật di truyền vi sai, các thuật toán trí tuệ nhân tạo, các giải thuật lai Việc tiếp tục nghiên cứu các giải thuật này cũng sẽ mở ra hướng nghiên cứu tiếp theo trong nghiên cứu công nghệ CAPP. TÀI LIỆU THAM KHẢO [1] Paiva Gustavo Silva and Carvalho Marco Antonio M., “Improved Heuristic Algorithms for the Job Sequencing and Tool Switching Problem”, Computers & Operations Research, 88(Supplement C), 2007, pp. 208-219. [2] Wang Jinfeng, et al., “A Hybrid Bat Algorithm for Process Planning Problem”, IFAC-PapersOnLine, 48(3), 2015, pp. 1708-1713. [3] Petrović Milica, et al., “Integration of Process Planning and Scheduling Using Chaotic Particle Swarm Optimization Algorithm”, Expert Systems with Applications, 64(Supplement C), 2016, pp. 569-588. [4] Tran Anh Van and Nguyen Ngoc Binh, “Optimization of Operation Sequencing in CAPP Based on Ant Colony Algorithm”, Proceedings of The 4th National Conference on Mechanical Science & Technology, 2, 2015, pp. 87-95. [5] Khan Z., Prasad B., and Singh T., “Machining Condition Optimization by Genetic Algorithms and Simulated Annealing”, Computers & Operations Research, 24(7), 1997, pp. 647-657. [6] Li L., et al.,2005 “Application of Genetic Algorithm to Computer- Aided Process Planning in Distributed Manufacturing Environments”, Robotics and Computer-Integrated Manufacturing, 21(6), 2005, pp. 568-578. [7] Chiu Nan-Chieh, Fang Shu-Cherng, and Lee Yuan-Shin, “Sequencing Parallel Machining Operations by Genetic Algorithms”, Computers & Industrial Engineering, 36(2), 1999, pp. 259-280. [8] Vũ Ngọc Phàn, “Ứng dụng thuật toán tiến hóa giải bài toán tối ưu đa mục tiêu có ràng buộc”, Tạp chí Tin học và Điều khiển, 16, 2000, pp. 16-22. [9] KA De Jong, An Analysis of The Behavior of A Class of Genetic Adaptive Systems, Doctoral dissertation, University of Michigan. [10] DE Gold Berg, K Deb, and B Korb, “Do Not Worry, Be Messy”, Proceedings of The Fourth International Conference on Genetic Algorithms, 1991, pp. 24-30. (BBT nhận bài: 19/3/2018, hoàn tất thủ tục phản biện: 26/4/2018)