ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP
HOÀNG THỊ QUYÊN
ĐỀ TÀI:
SỬ DỤNG THUẬT TOÁN PARTICLE SWARM OPTIMIZATION
ĐÁNH GIÁ ĐỘ TRỤ TỪ DỮ LIỆU ĐO TRÊN MÁY CMM C544
TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT
KHOA ĐT SAU ĐẠI HỌC NGƯỜI HD KHOA HỌC HỌC VIÊN
PGS.TS Nguyễn Đăng Hòe Hoàng Thị Quyên
THÁI NGUYÊN - 2011
I. Tính cấp thiết của đề tài.
Cơ sở khoa học:
Trong nền sản xuất hiện đại, các hệ thống sản xuất có tích hợp máy tính đòi hỏi độ chính xác cao của các
phương pháp kiểm tra kích thước. Các phương pháp kiểm tra kích thước truyền thống khó đáp ứng được nhu cầu
ngay càng cao này và do đó sức cạnh tranh của sản phẩm trên thị trường bị hạn chế. Trước thực tế đó, hệ thống
kiểm tra kích thước có tích hợp máy tính được sử dụng, trong đó máy đo tọa độ ba chiều (CMM) là lựa chọn
hàng đầu của các nhà sản xuất.
Hiện nay, với sự suất hiện ngày càng nhiều của máy đo tọa đọ CMM, kỹ thuật đo bằng máy CMM đã
nhận được nhiều sự quan tâm. Các máy CMM tích hợp máy tính và phần mềm phù hợp để phân tích và xử lý kết
quả đo. Điều làm nhiều người dùng băn khoăn là cùng một bộ dữ liệu về tọa độ nhưng các máy CMM khác nhau
lại cho các kết quả khác nhau. Điều này được giải thích là do thuật toán xử lý dữ liệu khác nhau.
Xác định các thông số chuẩn cho hình trụ là một trong những tính năng quan trọng nhất trong thiết kế,
sản xuất và lắp ráp cơ khí. Nó là điều kiện cần thiết để xây dựng một thuật toán để đánh giá sai số hình trụ. Độ
trụ là sai lệch lớn nhất giữa bề mặt thực đến bề mặt trụ áp (là mặt trụ lý thuyết bao lấy mặt trụ thực). Đã có nhiều
nghiên cứu để đánh giá sai số độ trụ [1-3]. Murthy [1] đã nâng cao một phương pháp với các đa thức trực giao,
có nghĩa là chiếu dữ liệu của hình trụ lên một số mặt phẳng và sau đó nhận được sai số của hình trụ bằng
phương pháp bằng phẳng. X Qian [2] đã sử dụng hàm mục tiêu để đánh giá sai số hình trụ. Các sai số được tối
ưu hóa bằng thuật toán genetic algorithm (GA), phương pháp này cho phép giảm không gian tìm kiếm mà vẫn
hội tụ đến các giải pháp tối ưu toàn cục. Mặc dù vậy tốc độ hội tụ của phương pháp này là quá chậm bởi các quá
trình lai ghép và đột biến trong quá trình tiến hóa. J Mao [3] phát triển một phương pháp để đánh giá sự không
chắc chắn của các sai số hình trụ. Phương pháp này dựa trên thuật toán tối ưu hóa bầy đàn particle swarm

theo Dhanish.
Chương 1
CÁC KIẾN THỨC CƠ BẢN VỀ ĐO ĐỘ TRỤ
I. Các khái niệm cơ bản trong kỹ thuật đo.
1.1. Đo lường.
1.2. Đơn vị đo - Hệ thống đơn vị đo.
1.3. Phương pháp đo.
1.4. Kiểm tra - phương pháp kiểm tra.
1.5. Phương tiện đo - Phân loại phương tiện đo.
1.6. Các chỉ tiêu đo lường cơ bản.
1.7. Các nguyên tắc cơ bản trong đo lường.
1.7.1. Nguyên tắc Abbe.
1.7.2. Nguyên tắc chuỗi kính thước ngắn nhất.
1.7.3. Nguyên tắc chuẩn thống nhất.
1.7.4. Nguyên tắc kinh tế.
1.8. Các thông số chất lượng của hệ thống đo.
1.8.1. Độ nhạy.
1.8.2. Độ phân giải.
1.8.3. Độ chính xác đo.
1.8.4. Độ chính xác lặp lại.
3
1.8.5. Khoảng chết.
1.8.6. Khả năng lặp.
1.8.7. Khả năng tuyến tính hóa.
1.8.8. Sai số gắn với mô hình hóa hệ thống đo.
1.8.9. Phương pháp tính sai số tổng.
II. Phương pháp đo các thông số hình học.
2.1. Phương pháp đo kích thước.
2.1.1. Phương pháp đo hai tiếp điểm.
2.1.2. Phương pháp đo ba tiếp điểm.

3.1.2. Các phép biến đổi tọa độ
3.2 . Thuật toán xác định tâm và bán kính đường tròn.
3.2.1. Xác định đường tròn qua tọa độ 3 điểm đo
3.2.2. Xác định đường tròn qua tọa độ nhiều điểm đo.
Chương 2
GIỚI THIỆU VỀ THOẬT TOÁN TỐI ƯU BẦY ĐÀN
PARTICLE SWARM OPTIMIZATION (TỐI ƯU HÓA BẦY ĐÀN)
2.1 Tổng quan về thuật toán Particle Swarm Optimization (PSO).
Phương pháp tối ưu bầy đàn là một trong những thuật toán xây dựng dựa trên khái niệm trí tuệ bầy đàn
để tìm kiếm lời giải cho các bài toán tối ưu hóa trên một không gian tìm kiếm nào đó.
2.1.1 Giới thiệu
Phương pháp tối ưu bầy đàn là một dạng của các thuật toán tiến hóa quần thể, với sự tương tác giữa các
cá thể trong một quần thể để khám phá một không gian tìm kiếm. PSO là kết quả của sự mô hình hóa việc đàn
chim bay đi tìm kiếm thức ăn cho nên nó thường được xếp vào các loại thuật toán có sử dụng trí tuệ bầy đàn.
Được giới thiệu vào năm 1995 tại một hội nghị của IEEE bởi James Kennedy và Russell C.Eberhart.
Để hiểu rõ thuật toán PSO ta cùng xem một ví dụ đơn giản về quá trình tìm kiếm thức ăn của một đàn
chim. Không gian tìm kiếm thức ăn lúc này là toàn bộ không gian ba chiều mà chúng ta đang sinh sống. Tại thời
điểm bắt đầu tìm kiếm tìm kiếm cả đàn bay theo một hướng nào đó, có thể là rất ngẫu nhiên. Nhưng sau một thời
gian tìm kiếm một số cá thể trong đàn bắt đầu tìm ra được nơi có chứa thức ăn. Tùy theo số lượng thức ăn vừa
tìm kiếm mà các cá thể gửi tín hiệu đến các cá thể khác đang tìm kiếm ở vùng lân cận. Tín hiệu này lan truyền
trên toàn quần thể. Dựa vào thông tin nhận được mỗi cá thể điều chỉnh hướng bay và vận tốc theo hướng về nơi
có nhiều thức ăn nhất. Cơ chế truyền tin như vậy thường được xem như là một kiểu hình của trí tuệ bầy đàn. Cơ
chế này giúp cả đàn chim tìm ra nơi có nhiều thức ăn nhất trên không gian tìm kiếm vô cùng rộng lớn.
Như vậy đàn chim đã dùng trí tuệ, kiến thức và kinh nghiệm của cả đàn để nhanh chóng tìm ra nơi chứa
thức ăn. Bây giờ chúng ta tìm hiểu làm cách nào mà một mô hình trong sinh học như vậy có thể áp dụng trong
tính toán và sinh ra thuật toán PSO mà ta nhắc đến. Việc mô hình hóa này thường được gọi là quá trình phỏng
sinh học mà chúng ta thường thấy trong các ngành khoa học khác. Một thuật toán được xây dựng dựa trên việc
mô hình hóa các quá trình trong sinh học được gọi là thuật toán phỏng sinh học.
5
2.1.2 Thuật toán PSO

best
: Vị trí tốt nhất của cá thể thứ i
G
best
: Vị trí tốt nhất trong quần thể
Vận tốc và vị trí của cá thể trong quần thể được tính như sau:
( ) ( )
k
ibest
k
ibest
k
i
k
i
XGrcXPrcVV −+−+=
+

2211
1
ω
(2.1)
11 ++
+=
k
i
k
i
k
i

k
X
i
k
V
i
Pbest
Pbest
i
Lưu đồ giải thuật:
7
Khởi tạo các cá thể với vị trí và vận tốc ngẫu nhiên
Bắt đầu
Khởi tạo
- Kích thước quần thể N
- Trọng số quán tính w
- Hệ số gia tốc c
1
, c
2
Tính hàm thích nghi
Tính P
best
và G
best
Cập nhập vị trí, vận tốc, P
best
và G
best
của các cá thể

Để áp dụng được thuật toán PSO cho bài toán thì việc đầu tiên chúng ta phải tìm được cách biểu diễn
của các phần tử sao cho mỗi phần tử là một giải pháp của bài toán. Thông thường, có ba phương pháp mã hóa:
mã hóa số thực, mã hóa số nguyên, mã hóa bít nhi phân. Trong luận văn này, phương pháp được sử dụng là
phương pháp mã hóa số thực. Mỗi phần tử là một vectơ d chiều (d là số biến được tối ưu).
Cụ thể, ký hiệu tập dữ liệu đo là N gồm L điểm trên bề mặt trụ: N
j
= {(x
1
, y
1
, z
1
), , (x
j
, y
j
, z
j
), , (x
L
, y
L
,
z
L
)}; j = 1, , L, trong đó x
j
, y
j
, z

, , v
id
). Vị trí tốt nhất
của phần tử thứ i mà nó đã từng đạt được là P
i
= (p
i1
, p
i2
, p
i3
, , p
id
) (còn gọi là P
best
). Vị trí tốt nhất trong tất cả
quá trình tìm kiếm từ trước đến bây giờ cho mọi phần tử là P
g
= (p
g1
, p
g2
, p
g3
, , p
gd
) (còn gọi là G
best
). Khi đó vị
8

,,,
iiiii
vvvvV
=

( )
4321
,,,
iiiii
ppppP
=

( )
4321
,,,
ggggi
ppppP
=
Đầu vào thuật toán:
• X
i
nhận giá trị ngẫu nhiên, với i = 1, , s.
• N
j
đo bằng thực nghiệm, với j = 1, , L.
• V
i
nhận giá trị ngẫu nhiên, với i = 1, , s.
Khi đó quá trình xác định sai số hình trụ từ một phần tử (hay một cá thể) thứ i sẽ được thực hiện như
sau:

i
Đặt k = 1
Bước 2:
• Với mỗi cá thể
k
i
X
ta đi tính:
( )
k
ij
kj
i
XNdd →=
,
, với i = 1, , s
j = 1, , L
→
( ) ( )
kj
i
kj
i
k
i
ddf
,,
minmax −=
Nếu
1−

thì thiết lập
i
best
f
bằng giá trị hiện hành. Xác định vị trí phần tử trong vùng lân cận
đạt được là tốt nhất cho tới thời điểm hiện tại
g
best
f
.)
9
• Tìm
( ) ( ){ }
kj
i
kj
i
k
i
ddf
,,
minmaxminmin
−=
; với i = 1, , s
j = 1, , L
• Vì PSO là một quá trình ngẫu nhiên, nên chúng ta phải định nghĩa điều kiện dừng cho bài toán. Thuật
toán chỉ dừng khi giá trị của P
best
và G
best

vxx
Trong đó
k
id
v
và
k
id
x
lần lượt là tốc độ và vị trí cá thể thứ i trong quần thể thuộc thế hệ đang xét k. Trong
ngữ cảnh của bài toán đang xét,
k
id
v
và
k
id
x
đều là các vectơ d chiều. Nhắc lại d chính là số biến tối ưu.
• Tăng k =k + 1
Bước 3: Quay lại bước 2.
3.3. Lưu đồ thuật toán.
10
11
Đo bề mặt ngoài của mẫu hình trụ có đường kính
φ
26 dài 28mm được đo bởi máy đo CMM, nhóm các
dữ liệu đo được trong bảng 3.1:
Bảng 3.1: Bộ dữ liệu đo bất kỳ trên bề mặt trụ.
x y z x y z

, r
2
, v
max
, s, …
- Thuật toán
Chương trình
SỐ LIỆU ĐẦU RA
- Các giá trị a, b, l, m.
- Sai lệch độ trụ nhỏ nhất
- Biểu đồ biểu diễn sai số
của các điểm
Số liệu đầu vào là số liệu tọa độ các điểm trên biên dạng lỗ/ trục được lấy từ máy đo CMM. Chương
trình với thuật toán sẽ tự động xử lý dữ liệu sẽ cho ra các thông số a, b, l, m và sai số độ trụ, biểu đồ biểu diễn sai
số của các điểm đến trục của hình trụ lý tưởng.
4.1. Lập cơ sở dữ liệu
4.1.1. Máy đo tọa độ 3 chiều CMM
4.1.2. Tạo bộ dữ liệu cho chương trình.
Tiến hành đo mẫu thử là một con lăn cán thép trên máy đo CMM 544 Mitutoyo của trung tâm thí
nghiệm trường ĐH Kỹ thuật công nghiệp Thái Nguyên. Mẫu thử được gá đặt chắc chắn trên bàn máy. Khởi động
máy CMM, máy nén khí cùng phàn mềm MCOSMOS và tiến hành thiết lập đầu đo, xây dựng hệ tọa độ cho mẫu
thử.
Hình 4.6. Mẫu thử đo trên máy CMM
4.2. Giới thiệu về phần mềm matlab.
4.3. Ứng dụng phần mềm matlab chạy chương trình PSO ứng dụng.
- Nhấp chuột vào biểu tượng chương trình matlab, xuất hiện hộp thoại:
Hình 4.18. Giao diện chương trình.
- Vào File, chọn: Set path. Xuất hiện hộp thoại:
13
Hình 4.19. Hộp thoại Set path.

Cylindricity 0.0068
Hình 4.25. Các lần lặp của PSO
4.4. So sánh thuật toán PSO với thuật toán Dhanish.
4.4.1. Thuật toán Dhanish xác định độ không tròn.
4.4.2. Kết quả của việc ứng dụng thuật toán Dhanish.
4.4.3. Chuyển dữ liệu trên mặt trụ về một mặt phẳng.
Chiếu bộ dữ liệu các điểm đo trong bảng 3.1 xuống một mặt phẳng như trong hình 4.24 ta được bộ tọa
độ gồm 32 điểm nằm trên đường tròn có số liệu như bảng 4.3: Khi đó ta có bài toán xác định độ không tròn là
trường hợp đặc biệt của bài toán xác định độ không trụ.
17
Bảng 4.3: Bộ dữ liệu chiếu xuống mặt phẳng oxy.
x y x y x y
1 -0.004 13.038 12 9.686 -8.726 23 -12.836 -2.289
2 8.900 9.545 13 1.522 -12.946 24 -11.144 6.784
3 13.027 0.796 14 -7.724 -10.499 25 0.005 13.032
4 10.045 -8.313 15 -12.844 -2.230 26 8.872 9.547
5 1.563 -12.942 16 -11.136 6.795 27 13.015 0.752
6 -7.699 -10.515 17 -0.003 13.040 28 10.024 -8.345
7 -12.840 -2.249 18 8.862 9.573 29 1.491 -12.958
8 -11.139 6.784 19 13.020 0.778 30 -7.739 -10.498
9 -0.009 13.037 20 10.025 -8.339 31 -12.858 -2.210
10 8.890 9.552 20 1.517 -12.949 32 -11.149 6.775
11 13.026 0.760 22 -7.688 -10.524
Xuất bộ dữ liệu này vào file định dạng text, xem hình 4.28:
Hình 4.28. Dữ liệu dạng text trong mặt phẳng.
Giao diện làm việc của chương trình xác định độ tròn bằng thuật toán Dhanish:
18
Hình 4.29. Giao diện chương trình thuật toán Dhanish
- Click chuột vào nút Browse và chọn đường dẫn đến bộ dữ liệu dạng Notebad cần kiểm tra, xem hình
vẽ:

thẳng là trục hình trụ lý tưởng phù hợp nhất với các tọa độ vừa đo được (cụ thể phải xác định a, b, l, m) và sai số
nhỏ nhất độ trụ bằng máy tính. Các kết quả chính của nghiên cứu này bao gồm:
- Khảo sát, đánh giá một cách toàn diện các phương pháp đo trong kỹ thuật.
- Trình bầy chi tiết về thuật toán PSO: Nguồn gốc phát triển, ưu nhược điểm, đặc điểm, tính chất và ứng
dụng của thuật toán. Và đã phân loại cụ thể hai loại PSO nối tiếp và PSO song song cùng với ưu nhược điểm của
từng loại. Đặc biệt đưa ra cụ thể các bước quan trọng trong việc áp dụng thuật toán PSO.
- Luận văn đã bước đầu đề xuất phương pháp ứng dụng thuật toán PSO vào bài toán xác định độ trụ.
- Chỉ ra được cách giao tiếp về dữ liệu giữa chương trình đo trên máy CMM và chương trình xử lý dữ
liệu tự động trên máy tính.
- Xây dựng được các hàm tính toán cho bài toán và phát biểu bài toán xác định độ trụ để có thể áp dụng
thuật toán PSO. Cài đặt hoàn thiện demos cho giải pháp.
- Thử nghiệm chương trình với bộ dữ liệu đo từ máy CMM C544. Mu đun phần mềm trên nền matlab có
giao diện thân thiện, dễ sử dụng. Mu đun này không những cho phép xử lý dữ liệu đo nhanh chóng, tiện lợi mà
còn hiển thị các kết quả đo một cách trực quan.
- Tìm hiểu và cài đặt thuật toán Dhanish đã xác định độ không tròn, qua đó làm cơ sở để so sánh với kết
quả nghiên cứu của đề tài.
- Các chương trình và kết quả thử nghiệm đã chứng minh hướng tiếp cận thuật toán PSO để giải quyết bài toán
xác định độ trụ là đúng đắn và có hiệu quả. Đặc biệt chương trình cài đặt đã xác định được hình trụ phù hợp nhất
với bộ dữ liệu đo từ máy CMM và sai số độ trụ nhỏ nhất.
21
TÀI LIỆU THAM KHẢO
Để hoàn thiện đề tài này tôi đã tham khảo các tài liệu sau:
[1] Nguyễn Tiến Thọ, Nguyến Thị Xuân Bẩy, Nguyễn Thị Cẩm Tú (2001), Kỹ thuật đo lường và kiểm tra
trong cơ khí, NXB Khoa học & kỹ thuật, Hà Nội.
[2] Bùi Quý Lục, Phương pháp xây dựng bề mặt cho CAD/CAM, NXB Khoa học & kỹ thuật.
[3] Nguyễn Ngọc Tân - Kỹ thuật đo - NXB Khoa học & kỹ thuật.
[4] Ninh Đức Tốn (2000), Dung sai lắp ghép, NXB Giáo dục Hà nội.
[5] Catalog máy CMM 544 của hãng Mitutoyo Nhật bản.
[6] Vũ Thị Tâm (2010), Thuật toán mới và chương trình Matlab xác định sai lệch độ tròn từ dữ liệu đo trên
máy CMM 544, Luận văn thạc sỹ khoa học Chế tạo máy, Đại học Thái Nguyên trường Đại học Kỹ thuật