CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114
NHẬN XÉT CỦA GIẢNG VIÊN


3. Hàm đánh giá và hàm thích nghi: 25
4. Các toán tử di truyền: 26
5. Các tham số của thuật giải: 27
III. Các toán tử và kỹ thuật di truyền nâng cao 28
1. Thể lưỡng bội (Diploidy), thể trội (Dominicance) và thể khuyết (Abeyance): 28
2. Thể đa bội (Multiploid): 30
3. Một số toán tử vi mô tái thiết lập thứ tự: 31
4. Vùng thích nghi (Niche) và sự hình thành loài (Speciation): 35
CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114
5. Tối ưu hóa đa mục tiêu: 42
6. Tối ưu tổ hợp: 43
CHƢƠNG 3: BÀI TOÁN PHÁT THƢ TPHCM 44
I. Giới thiệu Bưu Điện Thành Phố: 44
II. Bài toán lấy thư hằng ngày: 46
KẾT LUẬN 56
TÀI LIỆU THAM KHẢO 57


Cuộc sống của chúng ta luôn có rất nhiều vấn đề được đặt ra đòi hỏi ta cần phải giải
quyết. Máy tính giúp chúng ta giải quyết các vấn đề một cách chính xác và thông minh.
Sau khi hoàn thành môn học Công nghệ tri thức và ứng dụng do thầy Hoàng Kiếm
phụ trách em đã nắm bắt được một số kiến thức quan trọng về nghiên cứu phân tích tri thức
và ứng dụng vào các bài toán trong thực tế.
Trong bài báo cáo này em xin được nếu một vài điểm tìm hiểm về mạng neural nhân tạo
và thuật giải di truyền. Từ thuật giải di truyền em đã xây dựng một chương trình demo giải
bài toán phát thư cho khu vực TPHCM. CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114 Trang 3
CHƢƠNG 1: MẠNG NEURAL NHÂN TẠO
I. Tổng quan về mạng Neural nhân tạo
1. Giới thiệu

khách hàng sau khi nhận được quảng cáo.

CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114 Trang 4
2. Lịch sử phát triển của mạng neural:
Các quá trình phát triển của mạng Neural được chia làm 4 giai đoạn :
 Giai đoạn 1: Mạng Neural bắt đầu từ nghiên cứu của William(1980) về tâm lý học và
sự liên kết các Neural thần kinh . Đến năm 1940, Mc Culloch và Pitts đã chứng minh
các Neural có thể mô hình hóa như những thiết bị giới hạn ( hay thiết bị ngưỡng) để
giải quyết các phép tính logic và mô hình mạng Neural của Mc Culloch – Pitts cùng
với giải thuật huấn luyên của Hebb ra đời 1943.
 Giai đoạn 2: Vào khoảng 1960 một số mô hình Neural hoàn thiện hơn ra đời như mô
hình Perceptron do Rosenblatt (1958), Adalile của Widrow(1962),…. Cả hai mô hình
này cho đến hiện nay vẫn được dùng rộng rãi nhưng nó có một số nhược điểm . Ví dụ
như mô hình Perceptron, theo Marvin Minsky và Seymour Papert của MIT chứng
minh nó không dùng được cho các hàm logic phức(1969).Còn Adalie là mô hình
tuyến tính, tự điều chỉnhđược dùng rộng rãi trong điều khiển thích nghi, tách nhiễu
và phát triển cho đến nay.
 Giai đoạn 3: Giai đoạn này có thể tính là bắt đầu từ thập niên 80. Chúng ta có thể kể
đến những đóng góp của Grossberg, Kohonen, Rumelhart, Hopfield…Đặc biệt là
đóng góp của Hopfield gồm 2 mạng phản hồi: Mạng rời rạc 1982 và mạng liên tục
1984
 Giai đoạn 4: Từ năm 1987 đến nay, hàng năm thế giới đều mở ra các hội nghị toàn
cầu chuyên ngành Neural IJCNN. Rất nhiều công trình được nghiên cứu để ứng dụng
mạng Neural vào các lĩnh vực như: kỹ thuật tính, điều khiển, bài toán tối ưu …
3. Biểu diễn một mạng Neural
Hình dưới đây là một ví dụ tiêu biểu cho mạng Neural được Pomerleu đề xuất trong hệ
thống ALVINN, hệ thống này là hệ thống lái xe tự động trên đường cao tốc. Dữ liệu đầu
vào của mạng Neural này là một ảnh gồm 30x32 ô, mỗi ô là 1 pixel thu từ camera được gắn
phía trước xe. Hệ thống này được huấn luyện để bắt chước cách lái xe của người lái xe trong

giá trị rời rạc hoặc liên tục
- Trong các dữ liệu học có thể chứa lỗi.
- Cho phép học trong thời gian dài.
- Ước lượng nhanh các hàm mục tiêu.
- Con người không cần phải hiểu hàm mục tiêu Mạng Neural trong hệ thống ALVINN

CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114 Trang 6
II. Cơ sở lý thuyết cho Mạng Neural
1. Dữ liệu huấn luyện:
Đặc điểm của mạng Neural đó là phải trải qua giai đoạn huấn luyện dựa trên một tập hợp
các dữ liệu huấn luyện.Dữ liệu huấn luyện là một cặp < > mà ở đó mỗi input cho ta một
output tương ứng. Đối với mạng Neural nhân tạo, là vector chứa các giá trị rời rạc hoặc
liên tục, còn là một giá trị liên tục hoặc rời rạc duy nhất.
Xét bảng giá trị sau:
Diện tích (feet
2
)
Số phòng ngủ
Giá tiền (1000$s)
2104
3
400
1600
3
330
2400

- U
i
là tích = x
1
.w
1
+ x
2
.w
2
+ … x
n
.w
n

- f(U
i
) là hàm kích hoạt của Neural. Hàm kích hoạt có nhiệm vụ chuyển tổng
các tích của dữ liệu đầu vào và trọng số thành một giá trị duy nhất. Hai hàm thông dụng
được dùng đó là hàm ngưỡng và hàm xích ma.
Bên cạnh các giá trị đầu vào có từ dữ liệu huấn luyện, các Neural nhân tạo này còn kèm
theo một giá trị đầu vào cố định gọi là giá trị bias x
0
= 1. Bởi vì như ta biết trong mạng
Neural nhân tạo thì có hai tham số có thể được điều chỉnh: các trọng số w
i
và giá trị ngưỡng
của hàm kích hoạt. Điều này là không thực tế và sẽ dễ dàng hơn nếu chỉ có một tham số cần
phải điều chỉnh. Để giải quyết điều này, người ta đưa giá trị bias thêm vào. Khi đó, tổng các
giá trị đầu vào sẽ được tính là:

i
là các thành phần của vector .


là độ lệch (Bias).
 w
i
là trọng số ứng với mỗi x
i

Perceptron có thể được dùng để biểu diễn cho nhiều hàm bool như AND hoặc OR.
Giả sử ta xem giá trị 1 là true, giá trị -1 là false thì một cách sử dụng perceptron có hai dữ
liệu đầu vào để cài đặt hàm AND là thiết lập giá trị w
0
= -0.8 và w
1
= w
2
= 0.5. Perceptron
này cũng có thể dùng để biểu diễn hàm OR bằng cách thiết lập giá trị w
0
= -0.3
2.2 Đơn vị xích ma (Sigmoid Unit):
Sự hạn chế của Perceptron là không thể biểu diễn các hàm phi tuyến tính vì hàm ngưỡng của
nó. Thế nên Hàm xích ma được đề xuất ra để
giải quyết vấn đề này. Đơn vị xích ma sử dụng
hàm  là hàm kích hoạt. Hàm xích ma có dạng:
(x) =
Vì vậy output của Đơn vị xứ lí Xích ma
sẽ là :

2.3 Một số đơn vị sử dụng một số hàm kích hoạt khác:
- Hàm McCuloch-Pitts: - Hàm McCuloch-Pitts trễ: - Hàm lưỡng cực: Bipolar Sigmoid (tansig)
Với g(x) =

Mô hình của Đơn vị xích ma
CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114 Trang 10
Hàm này cũng có những đặc tính khá thuận lợi giống như hàm Xích ma nhưng nó làm
việc tốt với đầu ra nằm trong khoảng [-1,1].
3. Mạng Neural Nhân tạo:
Mạng Neural nhân tạo (Artificial Neural Network - ANN) là là một cấu trúc mạng được
hình thành nên bởi nhiều Neural nhân tạo liên kết với nhau và xử lý các thông tin bằng cách
thay đổi trạng thái của nó theo dữ liệu đầu vào.
Với việc giả lập các hệ thống sinh học, các cấu trúc tính toán mạng Neural có thể giải
quyết được các lớp bài toán nhất định như: bài toán lập lịch, bài toán tìm kiếm, bài toán
nhận dạng mẫu, bài toán xếp loại,… Mạng Neural còn giải quyết được lớp bài toán sử dụng
dữ liệu không đầy đủ, xung đột mờ hoặc không chắc chắn. Những bài toán này được đặc
trưng bởi một số hoặc tất cả các tính chất sau: i) Sử dụng không gian nhiều chiều, các tương
tác phức tạp, chưa biết hoặc không thể theo dõi về mặt toán học giữa các biến; ii) Không
gian nghiệm có thể rỗng , có nghiệm duy nhất hoặc một có một số nghiệm bình đẳng như
nhau. Ngoài ra còn thích hợp để tìm nghiệm của những bài toán mà đầu vào là những cảm
nhận bởi con người như: Tiếng nói, nhìn,và nhận dạng,…Tuy nhiên việc ánh xạ từ một bài
toán bất kì sang mạng Neural nhân tạo lại là một việc không phải đơn giản.
Mạng Neural là một cấu trúc xử lí song song, thông tin phân tán và có các đặc trưng


Mô hình mạng hồi quy có nhiều lớp nối ngược
CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114 Trang 12
Các mô hình mạng hồi quy thường gây cho ta khó khăn khi phân tích và thiết kế các
thuật toán học cho nó so với các mạng truyền thẳng.
5. Đào tạo Huấn luyện Mạng Neural:
Ngày nay để giải quyết các bài toán, các vấn đề đặt ra trong các lĩnh vực trong đời sống
xã hội người ta vẫn sử dụng đến máy tính với những chương trình đặt thù. Có nhiều cách
tiếp cận để giải quyết các vấn đề, các bài toán. Cách thông dụng nhất là lập trình. Thế nhưng
lập trình đòi hỏi tư duy, kinh nghiệm của con người, giải quyết cho từng trường hợp và từng
vấn đề cụ thể. Một cách khác để giải quyết các vấn đề trong các hệ sinh học đó là đào tạo -
huấn luyện (training). Ta lấy một ví du : bản thân con người không được lập trình nhưng có
thể làm 1 bài toán đơn giản dựa vào các ví dụ đã cho sẵn ,…. Dĩ nhiên, để làm được điều
này thì máy tính phải có có khả năng học và chúng ta phải có những dữ liệu huấn luyện
(example training) phù hợp. Mộ trong những giải pháp để giúp máy tính đạt được những
khả năng đó là Mạng Neural với những tính chất sau:
- Các mạng Neural hoạt động như các hệ thông tin có thể đào tạo được, thích nghi và
thậm chí là tự tổ chức cho chính mình.
- Các mạng Neural phát triển các chức năng dựa trên dữ liệu đào tạo mẫu.
- Các mạng Neural có thể được cung cấp những kiến trúc tính toán dựa trên đào tạo
hơn là thiết kế.
Việc đào tạo và huấn luyện mạng Neural là quá trình làm cho mạng Neural có thêm
những chức năng dựa trên những dữ liệu mẫu có sẵn thông qua các thuật toán học hay các
luật học đã được cài đặt sẵn cho mạng Neural.
 Luật học:
Các luật học đóng vai trò quyết định trong việc đào tạo huấn luyện các mạng Neural
nhân tạo.Nó quyết định trực tiếp đến khả năng học, thích nghi cảu mạng Neural. Một khác
niệm đơn giản về việc học của mạng Neural là cập nhật các trọng số trên cơ sở các mẫu.
Luật học qui tắc chung để cập nhật các trọng số này. Hiểu theo nghĩa rộng hơn thì học có

Là quá trình học bằng cách đi tìm các tham số của cấu trúc của mạng để từ đó xây dựng
nên một cấu trúc hợp lí nhất cho mạng Neural giúp mạng hoạt động tốt nhất. Nhưng trong
thực tế việc này tốn rất nhiều thời gian ngay cả với mạng có kích thước nhỏ.Thường sử
dụng các giải thuật di truyền hay kĩ thuật gọt tỉa

CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114 Trang 14
III. Thuật toán lan truyền ngƣợc:
Thuật toán lan truyền ngược được đề xuất bởi Rumelhart, Hinton và Williams năm
1986 Nhằm tính toán các trọng số, là cơ sở cho việc huấn luyện các mạng Perceptron nhiều
lớp. Nó mở đường cho việc sử dụng các Mạng Neural nhân tạo bởi vì trước đó.
1. Thuật toán Backpropagation:
Đầu vào:
- Dữliệuhuấnluyện H
- Tốc độc học : .
- Số lượng đơn vị đầu vào n
in

- Số lượng đơn vị đầu ra n
out

- Số lượng lớp ẩn : n
layer

- Số lượng đơn vị trong trong lớp ẩn i : n
layer(i)

Mô tả:
- Dữ liệu huấn luyện là tập hợp các cặp vector < >. Trong đó là vector các giá
trị đầu vào, là vector các giá trị đầu ra.

Với f là hàm ngưỡng của Đơn vị xử lý
c) Với mỗi đơn vị ẩn tính 
k
theo công thức:

CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114 Trang 15
Với Downstream(j) là tập hợp các đơn vị liên kết trưc tiếp với đơn vị j và
nhận đầu ra của đơn vị j là đầu vào
d) Tính lại các trọng số theo công thức:

2. Chứng minh - Đạo hàm của thuật toán lan truyền ngƣợc:
Ta gọi tổng lỗi trên ví dụ d của 1 giả thuyết là ½ tổng bình phương độ chênh lệch giữa
các tín hiệu đầu ra của 1 đơn vị xử lí lớp output và mục tiêu của t của nó (E là thước đo độ
lỗi, E được tính 1 cách tương đối theo công thức dưới)

Theo đó thuật toán lan truyền ngược sẽ làm giảm đi E
d
nhằm giảm đi dần độ lỗi của
các lớp output này tức là giảm đi độ chênh lệch của các output o
k
so với mục tiêu t
k

Để làm giảm độ chênh lệch này thì thuật toán thực hiện thủ tục: Theo đó sẽ được tính theo công thức
(1)
Vì:

(với i là đơn vị output) có giá trị là thì
sẽ có giá trị là :

Trường hợp 2: Nếu như đơn vị xử lí là đơn vị ẩn (hidden unit):
Ta có:

Với Downstream(j) là tập hợp các đơn vị liên kết trưc tiếp với đơn vị j và nhận đầu ra
của đơn vị j là đầu vào.
CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114 Trang 17

Ta kí hiệu rằng 
i
(với i là đơn vị ẩn) có giá trị là thì sẽ có giá trị là :

Với: 3. Thuật toán lan truyền ngƣợc với đơn vị signmoid:
3.1 Tiếp cận:
Đơn vị signmoid sử dụng hàm signmoid là hàm kích hoạt vì nó dễ dàng cho việc tích
phân và dễ tính. Nó cũng là hàm phi tuyến thể nên với khả năng của mình kết hợp với mạng
Neural nhiều lớp nó gần như biểu diễn được mọi lớp hàm, không chỉ riêng hàm tuyến tính
như khi sử dụng perceptron.
Ta có hàm sigmoid :

Và đạo hàm của hàm signmoid :

Vì vậy Các giá trị  được viết lại như sau :
Với j là các đơn vị output ta có:

ji.

Khởi tạo:
- Tạo một mạng truyền thẳng với các khai báo  , n
in
,n
out
,n
layer
,n
layer(i)
i[1 n
layer
].
- Khởi tạo các giá trị w
ji
ban đầu ngẫu nhiên phù hợp (Các giá trị này cố gắng để gần
với độ tụ nhằm rút ngắn thời gian hội tụ).
Thuật toán: Cho đến khi gặp điều kiện dừng thì thực hiện các lệnh sau:
- Với mỗi cặp < > trong tập dữ luyện huấn luyên H, thực thi:
Lan truyền thẳng theo từng đơn vị dọc theo mạng .
a) Tính các o
u
của mỗi đơn vị khi input vào mạng đầu vào .
b) Với mỗi đầu ra của mạng ta tính các giá trị 
k
theo công thức

c) Với mỗi đơn vị ẩn tính 
k

- Dùng trong việc quản lí các đối tượng đa biến là phân loại (phân lớp các đối tượng
trong vào các nhóm, nhóm con, hay chủng loại). Vi dụ : phân loại ảnh, nhận dạng
mẫu,…
- Khi phân loại một quyết định phức tạp, chúng ta phải bắt đầu với việc nghiên cứu
các mối liên quan giứa nhiều đối tượng đối tượng và các yếu tố tạo nên sự khác biệt
giữa các lớp. Có thể nói việc xây dựng 1 lớp và các quyết định phải được thực hiện
trươc skhi thủ tục học được tiến hành. Nếu kết quả cuối cùng không thỏa mãn chúng
ta cần phải xem xét lại cách biểu diễn các cây phân lớp hoặc thay đổi cả hai.
Mô hình hóa (modening):
- Các hệ thống phân định các câu trả lời rời rạc như có, không hoặc một số nguyên
định danh các đối tượng đầu vào thuộc lớp nào. Mô hình hóa yêu cầu hệ thống phải
sản sinh ra các câu trả lời mang tính liên tục. Trong quá trình mô hình hóa cần một
số lượng nhỏ các số liệu để xây dựng mô hình. Mô hình này có thể đưa ra các dự
báo cho tất cả các đối tượng đầu vào.Việc tìm ra 1 đường phù hợp với các số liệu
thực nghiệm là một tring những ứng dung thuộc dạng này. Trong bất kỳ loại mô
hình nào cũng phải tuân theo một giả định là : các thay đổi nhỏ của tín hiệu đầu vào
cũng chỉ gây rấtt hay đổi nhỏ trong tín hiệu đầu ra.
- Trong các phương pháp mô hình hóa cổ điển, các hệ số có thể có 1 ý nghĩa nào đó
nhưng mạng Neural thì các trọng số của nó không có ý nghĩa gì với vấn đề cần giải
quyết. Nhưng nhìn nhận ở một mặt nào đó ta có thể thấy ưu thế hơn hẳn của mạng
Neural so với những phương pháp cổ điển.
- Đối với việc chọn dữ liệu huấn luyện, chúng ta cần quan tâm tới sự phân bổ của các
đối tượng dùng để học. Nếu số lượng đối tượng dùng cho việc học là it và được
phân bố đều trong toán không gian, khi đó số liệu có thể được dùng để mô hình
ngay. Nếu không, nếu các đối tượng là nhiều và phân bố ngẫu nhiên trong không
gian biếnthì ta phải giảm thiểu sao cho chúng bao trùm cả không gian, sau đó mới
sử dụng được số liệu.
Biến đổi, thực hiện ánh xạ từ không gian đa biến này vào không gian đa biến khác
tương ứng (transformation add mapping):
CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG

-Thiết kế hệ thống tích nghi.
-Không đòi hỏi đặc trưng của bài toán, chỉ dựa trên dữ liệu học tập.
- Chấp nhận lỗi.
CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Huỳnh Thanh Việt – CH1301114 Trang 22
2.2 Nhƣợc điểm
- Không có các quy tắc hoặc hướng dẫn thiết kế cấu trúcmạng Neural cho từng ứng
dụ cụ thể. Việc lựa chọn số lượng lớp (layer) và số đơn vị trong mỗi lớp là chủ yếu dựa vào
thực nghiệm.
-Không có cách tổng quát để đánh giá hoạt động bên trong mạng.
-Việc học đối với mạng có thể khó (hoặc không thể) thực hiện.
-Khó mà đoán trước được hiệu quả của mạng trong tương lai. Có thể bộ dữ liệu huấn
luyện được cung cấp cho mạng chưa đầy đủ, như vậy có thể dẫn đến mạng hoạt động sai.
-Không gần gũi với tư duy của con người. Hầu như chúng ta không thể theo dõi và
hiểu được sự thay đổi của các tham số bên trong mạng. Chúng ta chỉ hy vọng sau khi được
huấn luyện, mạng Neural sẽ có thể giải quyết được vấn đề ta đang gặp phải.