Đại học Quốc Gia Thành Phố Hồ Chí Minh
Đại học Công Nghệ Thông Tin
Khoa Khoa học máy nh
Môn:HỆ HỖ TRỢ QUYẾT ĐỊNH
Đề tài thu hoạch:
Ứng dụng Neuron &thuật giải di truyền trong hệ
thống ra quyết định điều khiển xe tự hành


 !"#
Mục lục
$%&'()*  %+!,2
Lời nói đầu
Ứng dụng Công nghệ thông tin trong điều khiển ra quyết định một cách tự động
ngày càng được nghiên cứu và áp dụng ngày càng mạnh mẽ; các thuật toán, hệ thống trí
tuệ nhân tạo ngày được ứng dụng nhiều hơn trong việc hỗ trợ quyết định.
Xu hướng xây dựng áp dụng các hệ thống trí tuệ nhân tạo nói chung mạng neuron
cũng như thuật toán di truyền nói riêng đang phát triển ngày một lớn mạnh trên toàn thế
giới.
Các hệ thống nhân tạo này giúp con người xử lí được các vấn đề thường gặp cũng
như gia tang được năng suất lao động của con người, hỗ trợ con người đưa ra các quyết
định trong quá trình thực hiện công việc cũng như duy trì sự sống.
Mục tiêu của bài thu hoạch đó là việc tìm hiểu cách thức hoạt động cũng như mô
hình vận hành của hệ thống mạng neuron nhân tạo và thuật giải di truyền, để từ đó có thể
áp dụng thuật giải di truyền huấn luyện mạng neuron trong môi trường không có trước
các dữ liệu mẫu.
Mục tiêu chính đó chính là xây dựng hệ thống điều khiển đưa quyết định để giúp
xe có thể tự hành hoàn thành lộ trình đường đi.
$%&'()*  %+!,3
Mục đích nghiên cứu
- Tìm hiểu về mạng neuron và ứng dụng.

B. Mạng Neuron nhân tạo
Mạng Neuron nhân tạo là một hệ thống xử lý thông tin có những đặc điểm gần giống
với mạng Neuron sinh học. Mạng Neuron nhân tạo được xây dựng dựa trên các mô hình
toán học mô phỏng hoạt động của những yếu tố chính trong mạng Neuron sinh học
(dendrite, soma, axon). Hoạt động của mạng Neuron nhân tạo có những tính chất sau:
− Quá trình xử lý thông tin xảy ra tại mỗi đơn vị của mạng, gọi là neuron.
− Các neuron được liên kết với nhau.
− Mỗi liên kết của các neuron đều có một trọng số. Trọng số này đặc trưng cho bài
toán được biểu diễn bởi mạng. Khi nhận được thông tin đầu vào, các đầu vào sẽ
được nhân với các trọng số tương ứng, sau đó được cộng lại để cho một giá trị gọi
là net.
− Mỗi neuron đều có một hàm kích hoạt (activation function), hàm này có chức
năng tính toán đầu ra cho neuron dựa vào giá trị net đã nêu ở trên.
Đặc trưng của một mạng Neuron nhân tạo bao gồm:
− Mô hình kết nối giữa các neuron trong mạng với nhau hay còn gọi là kiến trúc của
mạng.
− Cách thức xác định trọng số của các liên kết trong mạng.
− Hàm kích hoạt của các neuron.
Mạng Neuron nhân tạo được ứng dụng để giải quyết nhiều lớp bài toán : lưu trữ và
phục hồi trạng thái của mẫu, phân lớp mẫu, tìm ánh xạ giữa đầu vào và đầu ra, gom nhóm
các mẫu giống nhau hoặc dùng để giải quyết các bài toán về tối ưu có ràng buộc.
Mỗi neuron trong mạng có một đặc trưng là hàm kích hoạt. Hàm này tính toán đầu ra
từ các thông tin đầu vào một cách gián tiếp thông qua giá trị net. Tại mỗi thời điểm nhất
định, mỗi neuron chỉ có thể có một đầu ra, tuy nhiên, đầu ra này có thể được gửi đến
nhiều neuron khác.
Cách thức hoạt động của một neuron như sau:
$%&'()*  %+!,6
− Tính toán giá trị net là tổng các tích giữa các đầu vào và trọng số tương ứng.
− Áp dụng hàm kích hoạt để tìm giá trị đầu ra.
Để cho thuận tiện, ta sẽ sử dụng mạng Neuron thay cho mạng Neuron nhân tạo,

Nhận dạng mẫu là một trong những lĩnh vực thu hút được nhiều sự quan tâm của
giới khoa học nhất bởi có nhiều bài toán khó chưa được giải quyết trọn vẹn. Một nhánh
độc lập của lĩnh vực này có liên quan mật thiết đến mạng Neuron chính là nhận dạng chữ
viết tay (kí tự chữ hoặc số). Đây là một bài toán khó bởi vì các mẫu chữ viết khác nhau ở
kích cỡ, vị trí cũng như cách viết của từng người và những phương pháp truyền thống
không có khả năng giải quyết được. Để có thể tìm ra được giải pháp cho bài toán trên,
người ta sử dụng mạng lan truyền ngược và sau này là mạng neocognitron.
4. Y học
Mạng Neuron đã được sử dụng trong việc xác định toa thuốc cho bệnh nhân.
Trong giải pháp này, mạng được dùng như một phương pháp lưu trữ các mẫu toa thuốc
có sẵn với triệu chứng, chẩn đoán, các loại thuốc, các chỉ định, … Với một triệu chứng và
chẩn đoán được đưa vào, mạng sẽ trả về toa thuốc tương ứng và thông dụng nhất đối với
$%&'()*  %+!,8
các triệu chứng và chẩn đoán đó. Dù cấu trúc mạng rất đơn giản nhưng đã tỏ ra rất hiệu
quả khi giải quyết bài toán kê toa thuốc.
5. Mô phỏng và nhận dạng giọng nói
Để làm cho máy tính nói được tiếng Anh là một việc rất khó, bởi vì cách nhấn âm,
lên - xuống giọng phụ thuộc rất nhiều vào ngữ cảnh của câu. Phương thức truyền thống
để giải quyết vấn đề trên là sử dụng cấu trúc lưu trữ lại tất cả từ vựng và các quy tắc trong
việc nói tiếng Anh kèm theo các bảng tra những trường hợp bất quy tắc. Phương pháp
này có hiệu suất không cao và thường rất chậm.
Mô hình phát âm tiếng Anh đầu tiên sử dụng mạng Neuron được công bố là
NETtalk của Sejnowski và Rosenberg. Thay vì sử dụng cấu trúc lưu trữ từ vựng, những
quy tắc và bảng tra bất quy tắc thì NETtalk chỉ yêu cầu một tập dữ liệu mẫu bao gồm các
trường hợp phát âm. Sau khi được huấn luyện trêntập các trường hợp mẫu này, máy có
khả năng phát âm những từ mới với tỉ lệ sai rất thấp.
6. Thương mại
Mạng Neuron đã được ứng dụng trong thương mại để trợ giúp các quyết định. Một
trong những hệ thống loại này là hệ thống quản lý thế chấp tài sản của tập đoàn Nestor.
Hệ thống này lấy những trường hợp đã lưu lại trong hồ sơ thế chấp để làm tập mẫu dữ

2. Mạng một lớp
Mạng Neuron một lớp là mạng bao gồm một lớp neuron có liên kết trọng số.
Thông thường, các đơn vị của mạng được phân biệt thành các đơn vị input và các đơn vị
output. Các đơn vị input đóng vai trò nhận các giá trị đầu vào của môi trường. Còn các
đơn vị output chính là các neuron đảm nhận việc tính toán giá trị xuất cho mạng. Mỗi đơn
vị input sẽ có các kết nối đến tất cả các đơn vị output và ngược lại. Bên cạnh đó, giữa hai
đơn vị input không có liên kết nào, tương tự với các đơn vị output.
Hình 4. Mạng Neuron một lớp
$%&'()*  %+!,11
Đối với bài toán phân lớp, mỗi đơn vị đầu ra của mạng Neuron đại diện cho các
lớp chứa các đối tượng đại diện bởi vector đặc trưng đầu vào.
3. Mạng nhiều lớp
Mạng nhiều lớp là mạng bao gồm một hay nhiều lớp nằm giữa lớp input và output,
các lớp này được gọi là các lớp ẩn (hidden layers). Trong kiến trúc này, mỗi hai lớp kề
nhau sẽ có một bộ các trọng số liên hệ tương ứng liên kết tất cả các neuron của lớp này
với lớp nọ. Mạng nhiều lớp có khả năng giải quyết được nhiều bài toán phức tạp mà
mạng một lớp không thể làm được. Tuy nhiên, việc huấn luyện mạng không hề đơn giản
chút nào.
Hình 5. Mạng Neuron nhiều lớp
4. Thiết lập trọng số mạng
Bên cạnh kiến trúc mạng, cách thức thiết lập trọng số mạng (hay còn gọi là huấn
luyện, học - training) cũng là một đặc trưng để phân biệt các mô hình mạng Neuron với
nhau. Trong quá trình huấn luyện này, các trọng số mạng sẽ được điều chỉnh cho đến khi
đáp ứng một tiêu chí đặt ra. Hai hình thức huấn luyện được sử dụng cho mạng Neuron là
huấn luyện giám sát và không có giám sát. Bên cạnh đó, một số mô hình mạng Neuron
không có sự thay đổi trọng số trong quá trình huấn luyện mạng.
Mạng Neuron được huấn luyện để giải quyết những lớp bài toán như: tìm ánh xạ,
phân nhóm hoặc tối ưu hóa có ràng buộc. Phân loại mẫu và đối chiếu mẫu là hai dạng bài
$%&'()*  %+!,12
toán đặc biệt của lớp bài toán ánh xạ, cụ thể là ánh xạ một vector hoặc một mẫu từ đầu

neuron. Bên cạnh đó, vì một số lý do, ta có thể áp dụng các hàm kích hoạt khác nhau cho
các lớp khác nhau.
Hình 6. Đồ thị hàm số
( )f x x
=
Mạng Neuron một lớp thường sử dụng hàm ngưỡng để chuyển đổi một giá trị thực
liên tục sang một giá trị nhị phân (0 hoặc 1) hoặc lưỡng cực (-1 hay 1), hàm ngưỡng còn
được gọi là hàm Heaviside. Khi giá trị đầu vào của hàm lớn hơn hoặc bằng một giá trị
ngưỡng θ thì hàm sẽ trả về giá trị 1. Ngược lại, nếu giá trị đầu vào của hàm nhỏ hơn
ngưỡng θ thì hàm sẽ trả về giá trị 0 (hoặc -1)
1
( )
0
khi x
f x
khi x
θ
θ
≥

=

<

(hàm ngưỡng nhị phân)
1
( )
1
khi x
f x

+
'( ) ( )[1 ( )]f x f x f x
σ
= −
Hình 7. Đồ thị của hàm sigmoid nhị phân
Hàm sigmoid lưỡng cực thực chất là một biến thể của hàm sigmoid nhị phân, trả
về giá trị nằm từ -1 đến 1.
2
( ) 2 ( ) 1 1
1
x
g x f x
e
σ
−
= − = −
+
'( ) [1 ( )][1 ( )]
2
g x g x g x
σ
= + −
$%&'()*  %+!,15
Hình 8. Đồ thị của hàm sigmoid lưỡng cực
Hàm tanh cũng nhận giá trị từ -1 đến 1 tuy nhiên sự biến thiên xảy ra nhanh hơn so
với hàm sigmoid lưỡng cực.
( )
x x
x x
e e

thích nghi) từ tập hiện thời. Sau đó, các cá thể này được biến đổi bằng cách lai ghép hay
đột biến để tạo ra các cá thể mới. Việc này được thực hiện lặp đi lặp lại qua các thế hệ
tiếp theo và cuối cùng, giải thuật cho ra lời giải tối ưu hoặc gần tối ưu.
B. Các toán tử di truyền
1. Toán tử sinh sản
Toán tử sinh sản gồm hai quá trình: quá trình sinh sản (phép tái sinh), quá trình
chọn lọc (phép chọn).
2. Phép tái sinh
Phép tái sinh là quá trình các nhiễm sắc thể được sao chép trên cơ sở độ thích
nghi. Độ thích nghi là một hàm được gán giá trị thực, tương ứng với mỗi nhiễm sắc thể
trong quần thể. Quá trình này, được mô tả như sau:
Xác định độ thích nghi của từng nhiễm sắc thể trong quần thể ở thế hệ thứ t, lập
bảng cộng dồn các giá trị thích nghi (theo thứ tự gán cho từng nhiễm sắc thể). Giả sử,
quần thể có n cá thể. Gọi độ thích nghi của nhiễm sắc thể i tương ứng là fi tổng cộng dồn
thứ i là fti được xác định bởi:
$%&'()*  %+!,17
Gọi Fn là tổng độ thích nghi của toàn quần thể. Chọn một số ngẫu nhiên f trong
khoảng từ 0 tới Fn. Chọn cá thể thứ k đầu tiên thoả mãn f ≥ ftk đưa vào quần thể mới.
3. Phép chọn
Phép chọn là quá trình loại bỏ các nhiễm sắc thể kém thích nghi trong quần thể.
Quá trình này được mô tả như sau:
- Sắp xếp quần thể theo thứ tự mức độ thích nghi giảm dần.
- Loại bỏ các nhiễm sắc thể ở cuối dãy. Giữ lại n cá thể tốt nhất.
4. Toán tử ghép chéo
Ghép chéo là quá trình tạo nhiễm sắc thể mới trên cơ sở các nhiễm sắc thể cha-mẹ
bằng cách ghép một đoạn trên nhiễm sắc thể cha-mẹ với nhau. Toán tử ghép chéo được
gán với một xác suất p c . Quá trình được mô tả như sau:
Chọn ngẫu nhiên một cặp nhiễm sắc thể (cha-mẹ) trong quần thể. Giả sử, nhiễm
sắc thể cha-mẹ có cùng độ dài m.
Tạo một số ngẫu nhiên trong khoảng từ 1 tới m-1 (gọi là điểm ghép chéo). Điểm

Cứ sau mỗi thế hệ được hình thành, chúng ta cần tính lại độ thích nghi cho từng cá
thể để chuẩn bị cho một thế hệ mới. Do số lượng các cá thể tăng lên, độ thích nghi giữa
các cá thể không có sự chêch lệch đáng kể. Do đó, các cá thể có độ thích nghi cao chưa
hẳn chiếm ưu thế trong thế hệ tiếp theo. Vì vậy, cần ấn định tỷ lệ đối với hàm thích nghi
nhằm tăng khả năng cho các nhiễm sắc thể đạt độ thích nghi cao. Có 3 cơ chế định tỷ lệ
như sau.
1. Định tỷ lệ tuyến tính
Độ thích nghi được xác định theo công thức:
Cần chọn các tham số a, b sao cho độ thích nghi trung bình được ánh xạ vào chính
nó. Tăng độ thích nghi tốt nhất bằng cách nhân nó với độ thích nghi trung bình. Cơ chế
này có thể tạo ra các giá trị âm cần xử lý riêng. Ngoài ra, các tham số a, b thường gắn với
đời sống quần thể và không phụ thuộc vào bài toán.
2. Phép cắt Sigma
Phương pháp này được thiết kế vừa để cải tiến phương pháp định tỷ lệ tuyến tính
vừa để xử lý các giá trị âm, vừa kết hợp thông tin mà bài toán phụ thuộc. Ở đây, độ thích
nghi mới được tính theo công thức:
Trong đó:
C: số nguyên nhỏ (thường lấy giá trị từ 1 tới 5);
σ : độ lệch chuẩn của quần thể.
Với giá trị âm thì f' được thiết lập bằng 0.
E. Độ thích nghi:
1. Độ thích nghi tiêu chuẩn:
Hàm mục tiêu là hàm dùng để đánh giá độ tốt của một lời giải hoặc cá thể. Hàm
mục tiêu nhận vào một tham số là gen của một cá thể và trả ra một số thực. Tùy theo giá
trị của số thực này mà ta biết độ tốt của cá thể đó (chẳng hạn với bài toán tìm cực đại thì
$%&'()*  %+!,20
giá trị trả ra càng lớn thì cá thể càng tốt, và ngược lại, với bài toán tìm cực tiểu thì giá trị
trả ra càng nhỏ thì cá thể càng tốt).Giả sử trong một thế hệ có N cá thể, cá thể thứ i được
ký hiệu là ai. Hàm mục tiêu là hàm G. Vậy độ thích nghi của một cá thể ai tính theo độ
thích nghi tiêu chuẩn là

• Ý nghĩa đặc biệt của một nhiễm sắc thể: đo tiến bộ của giải thuật trong một số thế
hệ cho trước. Nếu tiến bộ này nhỏ hơn một hằng số ε xác định, kết thúc tìm kiếm.
$%&'()*  %+!,22
III. Xây dựng hệ thống điều khiển xe tự hành:
A. Mô tả bài toán:
- Điều khiển xe hơi trên môi trường giả lập tự động.
- Động cơ điều khiển xe bao gồm hệ thống xoay trái phải, xe có gia tốc đều và
không thay đổi tốc độ khi điều khiển.
- Áp dụng mạng neuron để tiếp nhận dữ liệu và đưa ra quyết định cho xe hơi.
- Mục tiêu là điều khiển xe hoàn thành 1 vòng đua có hình dáng đường không đồng
đều mà không va chạm với lề đường.
B. Xây dựng mô hình:
1. Tiếp nhận dữ liệu:
$%&'()*  %+!,23
Hệ thống bao gồm các sensor để thu nhận tín hiệu đo khoảng cách từ thân xe đến
vật cản nằm trong phạm vi của sensor thu nhận được.
Hệ thống bao gồm 5 sensor theo các hướng: 0
o
, 45
o
, 90
o
, 135
o
, 180
o
Dữ liệu thu nhận được là khoảng cách đến vật thể nếu có.
2. Điều khiển:
Quá trình điều khiển học cần được ra quyết định để điều khiển lực (tốc độ) của 2
bánh xe điều hướng. Quá trình này cần thiết một hệ thống thông minh tiếp nhận các dữ

Neuron.
s[i]= signal/MAX signal
Quá trình thực hiện bao gồm:
- Các Neuron lớp đầu vào sẽ tiếp nhận tín hiệu từ các cảm biến về khoảng cách từ
xe đến các vật thể, chướng ngại vật trên đường di chuyển.
- Các lớp Neuron mờ sẽ tiếp tục xử lý tín hiệu.
- Các lớp Neuron đầu ra sau khi xử lý sẽ cung cấp tín hiệu quyết định cho các bánh
xe điều khiển
3. Huấn luyện mạng Neuron:
Để huấn luyện mạng Neuron có nhiều cách để huấn luyện mạng Neuron. Một số
phương pháp có thể kể đến như Propagation, Back Propagation, thuật giải di truyền, …
Trong bài thu hoạch này sẽ sử dụng thuật giải di truyền để huấn luyện mạng
Neuron. Một trong những ưu điểm theo tiếp cận hướng thuật giải di truyền đó là:
- Tự hệ thống có thể sinh ra lời giải và tối ưu hóa các lời giải để có thể tiếp cận
được mục tiêu
$%&'()*  %+!,25