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)