Luận Văn Tốt Nghiệp Cao Học

MỤC LỤC
MỤC LỤC .......................................................................................................................................1
PHẦN 1: GIỚI THIỆU ....................................................................................................................3
I- GIỚI THIỆU CHUNG ......................................................................................................... 3
I.1.
Các vấn đề điều hành mực nước hồ thủy điện ............................................................ 3
I.2.
Mục tiêu của đề tài ...................................................................................................... 4
IIPHƯƠNG HƯỚNG GIẢI QUYẾT VẦN ĐỀ ................................................................... 6
Xây dựng hệ cơ sở dữ liệu ....................................................................................................... 6
II.1. Xây dựng phần mềm dự báo lượng nước nhập vào hồ ................................................ 6
II.2. Xây dựng chương trình tìm phương án tối ưu điều hành mực nước hồ ........................ 6
IIICÁC CÔNG TRÌNH LIÊN QUAN ĐẾN ĐỀ TÀI ........................................................... 7
III.1.
An attempt to apply Artificial Neural Networks to Meterology............................... 7
III.2.
Ứng dụng ANN trong việc tính toán các dữ liệu khí tượng...................................... 7
III.3.
Ứng dụng ANN trong việc dự báo nhu cầu điện năng giúp điều hành các tổ máy
của nhà máy điện .................................................................................................................... 7
III.4.
Các ngôn ngữ CLP hỗ trợ lập trình tối ưu ................................................................ 7
III.5.
Xu hướng lai ghép giữa lập trình ràng buộc và tìm kiếm cục bộ............................. 7
IVCƠ SỞ LÝ THUYẾT ....................................................................................................... 9
IV.1.
Mạng Neural nhân tạo (ANN) ................................................................................. 9
IV.1.1. Giới thiệu.............................................................................................................. 9
IV.1.2. Cấu trúc của ANN .............................................................................................. 10

IV.1.3. Mạng nhiều tầng và giải thuật lan truyền ngược ............................................... 10
IV.1.4. Hàm truyền......................................................................................................... 12
IV.1.5. Phương trình kết xuất mạng ANN ...................................................................... 13
IV.1.6. Máy học.............................................................................................................. 14
IV.2.
Lập trình tối ưu hóa ................................................................................................ 18
IV.2.1. Lập trình ràng buộc ............................................................................................ 18
I.1.1.1. Giải thuật Backtracking căn bản .................................................................... 19
I.1.1.2. Giải thuật Backtracking có kiểm tra hướng tới (forward checking) ............... 20
IV.2.2. Kỹ thuật Simulated Annealing và Local Search ................................................ 21
PHẦN 2: GIẢI QUYẾT VẤN ĐỀ THỰC TẾ ...............................................................................24
VXÂY DỰNG HỆ THỐNG THÔNG TIN ĐỊA LÝ PHỤC VỤ QUẢN LÝ DỮ LIỆU.... 24
V.1. Bản đồ số khu vực hồ Trị An ..................................................................................... 24
V.2. Mô hình toàn khu vực trong ArcGIS 9.0 .................................................................... 25
VIXÂY DỰNG PHẦN MỀM DỰ BÁO LƯNG NƯỚC NHẬP HỒ ............................... 27
VI.1.
Ứng dụng ANN vào việc hỗ trợ dự báo lượng nước nhập hồ................................. 27
VI.2.
Mô hình dự báo lượng nước nhập hồ...................................................................... 27
VI.3.
Hiện thực chương trình hỗ trợ dự báo lượng nước nhập hồ.................................... 28
VI.3.1. Giới thiệu về RunOffPredict .............................................................................. 28
VI.3.2. Giao diện RunOffPredict.................................................................................... 29
VI.3.3. Mô tả mô hình mạng ANN được sử dụng trong chương trình ............................ 31
VII- XÂY DỰNG PHẦN MỀM ĐIỀU HÀNH HỆ THỐNG HỒ THỦY ÑIEÄN................... 35
Trang 1/76


Luận Văn Tốt Nghiệp Cao Học
VII.1.

SƠ ĐỒ KHU VỰC HẠ LƯU SÔNG ĐỒNG NAI.................................................. 35
VII.2.
PHÂN TÍCH MÔ HÌNH:........................................................................................ 35
VII.2.1.
Vấn đề điều hành hồ nước và nhà máy thủy điện ......................................... 36
VII.2.2.
Vấn đề sử dụng nước tại các vùng nông nghiệp: ........................................... 38
VII.2.3.
Vấn đề sử dụng nước tại các nhà máy xử lý cấp nước công cộng ................. 38
VII.2.4.
Vấn đề sử dụng kênh thủy lợi để đưa nước đến các vùng thiếu nước ........... 39
VII.2.5.
Vấn đề ngăn mặn tại các điểm kiểm soát mặn .............................................. 40
VII.3.
Tuyến tính hóa hàm mục tiêu tổng quát ................................................................ 40
VII.4.
Mô hình tối ưu điều tiết hồ..................................................................................... 41
VII.5.
Hiện thực chương trình tối ưu điều hành................................................................ 42
VII.5.1.
Giới thiệu chương trình ReservoirManager.................................................... 42
VII.5.2.
Dữ liệu đầu vào .............................................................................................. 42
VII.5.3.
Dữ liệu đầu ra................................................................................................. 44
VII.5.4.
Mã chương trình hiện thực bằng ngôn ngữ LINGO phiên bản 8.0 ................. 44
VII.6.
Kết quả đạt được .................................................................................................... 50
VIIITÍCH HP CÁC MODULE THÀNH MỘT DSS ...................................................... 57

VIII.1. Giới thiệu ............................................................................................................... 57
VIII.2. Giao diện chương trình ........................................................................................... 57
IXKẾT LUẬN – HƯỚNG PHÁT TRIỂN.......................................................................... 59
IX.1.
Kết luận .................................................................................................................. 59
IX.2.
Hướng phát triển .................................................................................................... 60
TÀI LIỆU THAM KHẢO .............................................................................................................61
PHỤ LỤC A ..................................................................................................................................62
THƯ XIN SỐ LIỆU ................................................................................................................... 62
PHỤ LỤC B ..................................................................................................................................64
BẢNG SỐ LIỆU MƯA VÀ LƯNG NƯỚC NHẬP HỒ.......................................................... 64
TẠI CÁC ĐIỂM KHÍ TƯNG, THỦY VĂN ........................................................................... 64
PHỤ LỤC C ..................................................................................................................................75
BẢNG SỐ LIỆU CỦA MÔ HÌNH ĐIỀU HÀNH TỐI ƯU ....................................................... 75

Trang 2/76


Luận Văn Tốt Nghiệp Cao Học

PHẦN 1: GIỚI THIỆU

I- GIỚI THIỆU CHUNG

Thuỷ điện nói chung là sử dụng thế năng của nguồn nước để chạy các máy phát điện. Để thực
hiện điều này người ta phải tích luỹ dự trữ nguồn nước trong các hồ chứa nước gọi là hồ thuỷ
điện. Mục đích chính của các hồ thuỷ điện là cung cấp thế năng dự trữ để phục vụ nhà máy thuỷ
điện, tuy nhiên, ngoài nhiệm vụ chính, các hồ thuỷ điện còn đảm nhận nhiều mục tiêu khác nhau
thuộc các lãnh vực kinh tế, xã hội... Trong đó, các mục tiêu thường được quan tâm là:

• Cung cấp nguồn nước phục vụ thuỷ lợi, sản xuất nông nghiệp
• Cung cấp nguồn nước phục vụ sản xuất công nghiệp
• Cung cấp nguồn nước phục vụ sinh hoạt (ngành cấp nước)
• Chống ngập mặn ở các khu vực ven biển bằng cách duy trì mực nước và dòng nước ngọt
phù hợp ở các khu vực này
• Dữ trữ nước chống hạn hán và lũ lụt
Việc điều hành mực nước hồ thuỷ điện nói chung, thuỷ điện Trị An nói riêng là vấn đề đa mục
tiêu. Trong đó, với một lượng tài nguyên nước cho trước, điều hành viên phải xác định được cách
phân phối tài nguyên tốt nhất nhằm đảm bảo đạt hiệu quả tối đa cho tất cả các mục tiêu đã đề
cập như trên. Đây là bài toán tối ưu hóa thuộc loại khó. Đã có nhiều phương pháp khác nhau trên
thế giới được nghiên cứu để giải quyết bài toán này. Mỗi phương pháp đều có những ưu khuyết
điểm riêng.
Việc điều hành mực nước phụ thuộc rất nhiều vào nguồn tài nguyên nước chứa trong lòng hồ,
mà thông thường người ta lấy giá trị mực nước hồ để định lượng. Mực nước hồ thay đổi liên tục
theo thời gian, sự thay đổi này phụ thuộc vào rất nhiều yếu tố khác nhau, bao gồm: nhiệt độ, độ
ẩm không khí, cường độ mưa, thể tích và hình thể hình học lòng hồ và lượng mưa tại các điểm
quan trắc mưa trong lưu vực lòng hồ (nước trên các điểm mưa này sẽ chảy về lòng hồ sau một
khoảng thời gian, tuỳ vào khoảng cách so với hồ). Ngoài ra, tốc độ thay đổi mực nước hồ cũng
diễn biến khác nhau tuỳ theo mùa, thời tiết nói chung và chế độ điều tiết hồ… Do tất cả các lý do
trên, vấn đề tính toán mực nước lòng hồ trở nên rất khó khăn và phức tạp, nhưng nếu giải quyết
tốt được vấn đề này, việc điều hành mực nước hồ sẽ trở nên hiệu quả hơn với những số liệu nhập
lưu tiên đoán trước. Đây là bài toán tính toán không đầy đủ: mực nước hồ phụ thuộc vào quá
nhiều các yếu tố độc lập, nhưng thông tin về các yếu tố này có thể không đầy đủ với nhiều lý do
khác nhau (giới hạn về thời gian, giới hạn về kỹ thuật, không gian…), nói một cách khác, đây
chính là bài toán dự báo thông tin, thuộc loại bài toán khó. Trên thế giới cũng đã có nhiều
phương pháp giải quyết bài toán tính toán không đầy đủ này và cũng đạt được một số thành công
nhất định.
Hiện nay, chủ yếu người ta dựa vào các số liệu mực nước hiện tại để điều hành hồ. Việc sử
dụng các thông tin dự báo về mực nước hồ để điều hành còn rất hạn chế vì các thông tin dự báo
này chủ yếu dựa vào kinh nghiệm của điều hành viên.

I.1. Các vấn đề điều hành mực nước hồ thuỷ ñieän

Trang 3/76


Luận Văn Tốt Nghiệp Cao Học
Như đã giới thiệu, việc điều hành mực nước hồ thuỷ điện là vấn đề đa mục tiêu. Trong đó,
điều hành viên phải sử dụng nguồn tài nguyên nước để tối ưu tất cả mục tiêu đặt ra. Hai vấn
đề chính của điều hành viên là:
•

•

Dự báo chính xác lượng nước nhập vào hồ trong tương lai để định lượng tài nguyên nước
hiện có. Trong thời gian xả nước khỏi hồ thì lượng nước trong hồ có thể được bổ sung bởi
nguồn nước từ thượng lưu chảy về. Kết quả dự báo chính xác sẽ là cơ sở để thực hiện vấn
đề thứ hai. Trong giới hạn của đề tài, thông tin sử dụng cho việc dự báo là chuỗi lượng
mưa, nhiệt độ, độ ẩm tại các điểm mưa trong lưu vực theo thời gian.
Phân tích và đưa ra phương án điều hành mực nước hồ sao cho tối ưu các mục tiêu. Mỗi
hồ thuỷ điện luôn có hai mực nước giới hạn. Mực nước tối đa được qui định bởi sức chứa
của lòng hồ và khả năng chịu đựng của đập thuỷ điện. Ngược lại, một mức nước tối thiểu
phải được duy trì để đảm bảo các máy phát điện không bị hư hỏng. Mực nước trong lòng
hồ luôn phải ở giữa hai ngưỡng này. Nước trong hồ được xả về hạ lưu theo hai cách sau:
o Cách 1: Xả qua tua bin phát điện để chạy máy phát tạo năng lượng. Đây là mục tiêu
chính của hồ thuỷ điện. Nước được xả theo cách này không bị biến chất, nói một cách
khác, nó vừa đảm bảo mục tiêu tạo ra năng lượng vừa đảm bảo các mục tiêu khác
(nếu có)
o Cách 2: Xả tràn không qua tua bin phát điện, cách này không tạo ra năng lượng, chỉ
được sử dụng để đảm bảo các mục tiêu khác như: chống mặn, xả lũ, chống quá tải đập
thuỷ điện…

Mỗi mục tiêu được hình thức hoá bằng một hàm mục tiêu thể hiện sự tác động của lưu
lượng nước đối với mục tiêu đó.
Phương án điều hành cần được xác định là chuỗi lưu lượng xả về hạ lưu qua các cổng
xả theo thời gian.

Tóm lại, vấn đề chính của điều hành hồ thuỷ điện là xác định chuỗi lưu lượng nước xả về hạ
lưu qua các cổng xả từ hai yếu tố đầu vào:
1. Chuỗi cường độ mưa, nhiệt độ, độ ẩm tại các điểm quan trắc mưa theo thời gian
2. Các yêu cầu định mức của các mục tiêu
I.2. Mục tiêu của đề tài
Chính vì những lý do trên, nên việc xây dựng một hệ hỗ trợ quyết định (Decision Support
System-DSS) phục vụ cho công tác lưu trữ, truy xuất thông tin về thời tiết nói chung tại khu
vực thượng lưu lòng hồ thuỷ điện, dự báo về sự thay đổi mực nước lòng hồ và tính toán các
giải pháp điều hành mực nước lòng hồ để đạt hiệu quả cao nhất là một công việc rất có ý
nghóa. DSS sẽ giúp giải quyết những vấn đề sau:
• Thay đổi toàn bộ quy trình lưu trữ dữ liệu thủ công bằng qui trình tự động. Tất cả các
thông tin thời tiết ảnh hưởng đến mực nước lòng hồ thuỷ điện, kể cả bản đồ lưu vực lòng
hồ đều được xử lý, lưu trữ phù hợp cho việc truy xuất tức thời và phục vụ cho công tác
điều hành, nghiên cứu
• Giúp cho điều hành viên tại các nhà máy thuỷ điện có thể dễ dàng truy xuất các thông tin
cần thiết phục vụ công tác phân tích, điều hành hồ, từ cơ sở dữ liệu của hệ thống.

Trang 4/76


Luận Văn Tốt Nghiệp Cao Học
•
•

•


•
•

Giúp điều hành viên dễ dàng quyết định dựa vào các bảng phân tích tự động, các phương
án tối ưu do hệ thống dự báo, tính toán từ các thông tin trong cơ sở dữ liệu.
Ứng dụng ANN vào giải quyết bài toán thuộc loại phức tạp nhất trong lónh vực tính toán,
đó là bài toán dự báo lượng nước nhập vào hồ dựa vào các thông tin thực đã có, đặc biệt
là dự báo chính xác các hiện tượng tăng giảm đột ngột lượng nước vào trong lòng hồ trong
trường hợp nguy hiểm để có thể triển khai phương án điều hành khẩn cấp tránh các rủi ro
đáng tiếc xảy ra.
Ứng dụng kỹ thuật lập trình tối ưu hoá để giải quyết bài toán đa mục tiêu, dựa vào các
thông tin dự báo mực nước hồ, phân tích và tính toán các phương án điều hành hồ sao cho
tối ưu về tất cả các mục tiêu đề ra.
Xây dựng hệ thống giao diện phục vụ người dùng đảm bảo sự dễ dàng, thuận tiện, linh
hoạt trong sử dụng.
Toàn bộ hệ thống có thể dễ dàng cài đặt cho các nhà máy thuỷ điện khác.

Để thực hiện mục tiêu của đề tài, các công việc cần phải thực hiện như sau:
• Xây dựng một hệ thống thông tin thực thi đảm bảo hai yêu cầu:
o Cơ sở dữ liệu lưu trữ tất cả các thông tin liên quan đến sự thay đổi mực nước hồ
o Bản đồ số về lưu vực lòng hồ phục vụ việc truy cập thông tin một cách thân thiện. Sử
dụng công nghệ GIS.
• Xây dựng một phần mềm dựa vào mô hình ANN (Artificial Neural Network) để dự báo
lượng nước nhập vào hồ thuỷ điện
• Xây dựng một phần mềm dựa vào kỹ thuật lập trình tối ưu để phân tích, xác định phương
án điều hành tốt nhất đảm bảo vấn đề đa mục tiêu của công tác điều hành lòng hồ, hỗ trợ
điều hành viên nhà máy thuỷ điện.
• p dụng thử nghiệm thực tế cho công tác điều hành hồ thuỷ điện Trị An và một số hồ
điều tiết nước khác trong khu hạ lưu Đồng Nai.


Trang 5/76


Luận Văn Tốt Nghiệp Cao Học

II- PHƯƠNG HƯỚNG GIẢI QUYẾT VẦN ĐỀ

Xây dựng hệ cơ sở dữ liệu
Yêu cầu về cơ sở dữ liệu của DSS là phải có giao diện trực quan về toàn bộ bản đồ khu vực
thượng lưu hồ thuỷ điện. Với lượng dữ liệu tương đối lớn, không thể phẳng hoá các quan hệ
giữa các đối tượng cần thể hiện, hệ cơ sở dữ liệu được thiết kế dựa trên công nghệ GIS. Bằng
cách sử dụng các công cụ hỗ trợ GIS như ARCVIEW, ARCGIS, AVENUE… chúng ta có thể
thiết lập một bản đồ số lưu trữ các thông tin cần thiết cho vùng lưu vực hồ thuỷ điện.

II.1.Xây dựng phần mềm dự báo lượng nước nhập vào hồ
Mực nước hồ luôn thay đổi liên tục và phụ thuộc vào quá nhiều các yếu tố. Do đó, việc tính
toán lượng nước nhập hồ theo các yếu tố đầu vào là một công việc rất khó khăn. Ở đây, về
mặt toán học, chúng ta không thể tìm được một hàm tường minh mô tả mối quan hệ giữa
lượng nước nhập hồ và các yếu tố tự nhiên khác. Thực tế, việc xác định nhập lưu cũng chỉ
được con người ước lượng một cách gần đúng theo kinh nghiệm. Hướng tiếp cận để giải
quyết vấn đề này là cố gắng đưa ra một xấp xỉ hàm mô tả gần đúng mối quan hệ giữa lượng
nước và các yếu tố tự nhiên khác. Nói một cách khác, từ các số liệu mô tả các quan hệ giữa
lượng nước nhập hồ và các yếu tố tự nhiên, chúng ta tổng quát hoá chúng lên thành các qui
luật gần đúng. Về sau, với một tập dữ liệu đầu vào, ta có thể dễ dàng tìm ra kết quả nhập lưu
đầu ra nhờ vào qui luật đó. Về mặt khoa học, đây là tiếp cận theo hướng tính toán sinh học,
điển hình nhất là mạng neural nhân tạo (ANN). Mạng Neural nhân tạo mô phỏng quá trình
tính toán sinh học của bộ não con người. ANN là kỹ thuật tính toán sinh học, kỹ thuật này
tránh lối lập trình cấu trúc tường minh mà sử dụng phương pháp máy học. Nói chung, ANN là
kỹ thuật mô phỏng phương pháp suy luận kinh nghiệm của con người, quá trình tính toán của

ANN chủ yếu có hai giai đoạn chính:
1. Giai đoạn học: ở giai đoạn này, chúng ta đưa vào mạng các số liệu chi tiết thực về mối
quan hệ giữa lượng nước nhập hồ và các yếu tố tự nhiên khác có liên quan. Bản thân
mạng lần lượt “học” từng mẫu số liệu, tạo ra và ghi nhận một qui luật tổng quát phù hợp
với tất cả các mẫu đã học. Giai đoạn này dùng để ghi nhận các tri thức kinh nghiệm về
nhập lưu.
2. Giai đoạn tính toán: ở giai đoạn này, chúng ta chỉ cần đưa các thông số về yếu tố tự
nhiên, mạng sẽ cho ra kết quả lượng nước nhập hồ. Giai đoạn này được ứng dụng để dự
báo nhập lưu.
II.2.Xây dựng chương trình tìm phương án tối ưu điều hành mực nước hồ
Với việc phải tìm được phương án tốt nhất thoả mãn tất cả các mục tiêu đề ra thì đây là bài
toán tối ưu hoá. Đây là một bài toán khó, có độ phức tạp hàm mũ.
Phương hướng giải quyết vấn đề này là phối hợp lập trình ràng buộc với kỹ thuật simulated
annealing (thuộc local search). Sự phối hợp là nhằm phát huy thế mạnh của mỗi phương
pháp:
• Dùng lập trình ràng buộc để tạo ra một lời giải đúng.
• Dùng Simulated annealing để cải thiện chất lượng của lời giải đạt đến một phương án
điều hành xấp xỉ tối ưu

Trang 6/76


Luận Văn Tốt Nghiệp Cao Học
Phương án này nhằm tránh việc tìm kiếm vét cạn vốn yêu cầu rất nhiều chi phí để tìm ra lời
giải tối ưu.

Trang 7/76


Luận Văn Tốt Nghiệp Cao Học


III-

CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN ĐỀ TÀI

Phần này điểm qua một số đề tài nghiên cứu liên quan đến vấn đề dự báo và các phương pháp
giải thuật quan trọng sử dụng để giải bài toán tối ưu.
Các đề tài liên quan đến dự báo: phần lớn các đề tài dự báo đều nghiên cứu giải quyết bài toán
khó nhất về khí tượng, đó là dự báo thời tiết. Trong đó các nhà nghiên cứu sử dụng nhiều phương
án khác nhau để giải quyết bài toán dự báo, điển hình có các đề tài sau:
III.1. An attempt to apply Artificial Neural Networks to Meterology.
Marco Verdecchia, Anna Rita Pantaleo and Guido Visconti, Dipartimento di Fisica
dell’Universita’ dell’Aquita, Italy, 1997
Trong báo cáo này, nhóm tác giả đã đưa ra những lý do có thể và cần thiết ứng dụng ANN
vào lónh vực dự báo khí tượng như sau:
• Phần lớn những giá trị của lónh vực khí tượng là không xác định và đầy đủ
• Việc tăng cường khả năng tính toán của máy tính không cho phép tăng hiệu suất lên
nhiều trong các mô hình dự báo sử dụng cách tiếp cận theo kinh nghiệm, bởi vậy cần phải
cải tiến phương pháp tiếp cận và giải quyết vấn đề.
III.2. Ứng dụng ANN trong việc tính toán các dữ liệu khí tượng
Đã có nhiều công trình nghiên cứu ứng dụng ANN vào lónh vực tính toán không đầy đủ,
nhưng chủ yếu là tính toán các dữ liệu khí tượng. Các công trình này cũng đã chứng minh
những công dụng và ưu điểm của ANN trong việc tính toán các dữ liệu không đầy đủ. Kết
quả đạt được cũng rất khả quan.
III.3. Ứng dụng ANN trong việc dự báo nhu cầu điện năng giúp điều hành các tổ máy
của nhà máy điện
Công trình này nghiên cứu ứng dụng ANN vào việc dự báo nhu cầu điện năng nhằm giúp
điều hành các tổ máy phát điện một cách hợp lý nhất. Bài báo cáo của tác giả cũng đánh giá
cao khả năng dự báo dựa vào các thông tin không đầy đủ của kỹ thuật ANN. Công trình cũng
đạt kết quả rất khả quan, tuy nhiên, chỉ dừng lại ở mức độ là đáp ứng một mục tiêu duy nhất

là nhu cầu điện năng của người dùng.
Các nghiên cứu liên quan đến kỹ thuật lập trình tối ưu:
III.4. Các ngôn ngữ CLP hỗ trợ lập trình tối ưu
Cho đến ngày nay, đã có rất nhiều nghiên cứu phát triển các ngôn ngữ CLP có hỗ trợ tối ưu
hoá và đã đạt được khá nhiều thành công. Trong đó, có các ngôn ngữ đã trở nên phổ biến
như: CHIP, B-Prolog, Lingo… Điều này giúp cho việc lập trình tối ưu ngày càng trở nên dễ
dàng hơn. Đề tài nghiên cứu của đề cương cũng dự định sử dụng một trong các ngôn ngữ CLP
để tìm phương án điều hành hồ thuỷ điện tối ưu.
III.5. Xu hướng lai ghép giữa lập trình ràng buộc và tìm kiếm cục bộ
Điển hình cho xu hướng này là công trình của Merlot. Merlot và các cộng sự đã dùng một
phần mềm thương mại ILOG chuyên dụng cho lập trình ràng buộc để tạo ra lời giải khả thi
ban đầu, và sau đó sử dụng kỹ thuật Simulated Annealing để hoàn thiện lời giải này thành lời
Trang 8/76


Luận Văn Tốt Nghiệp Cao Học
giải xấp xỉ tối ưu. Xu hướng này kết hợp được thế mạnh của hai phương pháp để đối phó với
cả hai loại ràng buộc cứng và mềm. Thực nghiệm cho thấy có thể đem lại lời giải xấp xỉ tối
ưu với một độ hữu hiệu tính toán khá tốt.

Trang 9/76


Luận Văn Tốt Nghiệp Cao Học

IV-

CƠ SỞ LÝ THUYẾT

IV.1. Mạng Neural nhân tạo (ANN)

IV.1.1. Giới thiệu
Khái niệm tính toán có thể hiểu theo nhiều cách, phần lớn là tính toán theo chương trình,
trong đó các giải thuật tính toán được thiết kế và cài đặt bằng cách sử dụng các cấu trúc
điều khiển hiện hành. Một khái niệm khác của tính toán là hoạt động tính toán của các hệ
sinh học. Qua quá trình nghiên cứu, người ta nhận ra rằng sự tính toán trong bộ não con
người khác rất nhiều so với hoạt động tính theo chương trình ở các điểm sau:
• Sự tính toán được phân tán cực đại và song song
• Việc học thay thế cho sự phát triển chương trình có rất nhiều ưu thế
Theo cách hoạt động này của bộ não, một mô hình tính toán mới có nguồn gốc từ sinh học
đã ra đời, đó là mạng neural nhân tạo (Artificial Neural Network-ANN)
Mạng neural nhân tạo là một cấu trúc gồm các đơn vị kết nối với nhau. Mỗi đơn vị có
những đặc tính nhập/xuất và được cài đặt một tính toán hay chức năng cục bộ. Đầu ra của
mỗi đơn vị được xác định bởi các đặc tính nhập/xuất của chính nó, những mối liên hệ của
nó với những đơn vị khác và đầu vào bên ngoài. Một mạng thường phát triển một chức
năng tổng thể thông qua một hay nhiều dạng đào tạo.
Kỹ thuật ANN có tiềm năng trở thành cấu trúc tính toán chiếm ưu thế. Công nghệ ANN
đang hình thành là một lượng lớn kiến thức và kỹ thuật thường liên quan với nhau, nó
thay thế cho các giải pháp tính toán truyền thống và đưa ra một khả năng để tiếp cận
nhiều vấn đề hiện tại chưa giải quyết quyết được. ANN là lónh vực vừa khoa học vừa kỹ
thuật, trong đó khoa học được định nghóa một cách lỏng lẻo như là kiến thức có cấu trúc
và kỹ thuật là khoa học ứng dụng. Quá trình tính toán của ANN có một số nét chính như
sau:
• Mô hình tính toán tổng thể là sự kết nối những phần tử đơn giản và có thể thay đổi
cấu hình
• Những đơn vị riêng lẻ cài đặt một chức năng cục bộ và mạng tổng thể của những đơn
vị kết nối thể hiện một chức năng tương ứng. Việc phân tích chức năng này là rất khó,
thường chỉ được phân tích thông qua đào tạo và thử nghiệm. Các ứng dụng thực tế
thường xác định chức năng, yêu cầu thông qua những thông số đặc tả, vai trò của
người thiết kế ANN là xác định những tham số mạng để thoả mãn những đặc tả này.
• Cải biến các mẫu kết nối như là một chức năng của dữ liệu đào tạo chủ yếu là tiếp

cận học tập. Kiến thức hệ thống kinh nghiệm, đào tạo được lưu trữ dưới dạng kết nối
mạng
• ANN phải có khả năng lưu trữ thông tin, tức là phải đào tạo được. Mục đích của quá
trình đào tạo là làm cho mạng phát triển một cấu trúc bên trong cho phép nó định
danh hay phân loại đúng những mẫu mới và gần giống.
• ANN là một hệ động, trạng thái của nó thay đổi theo thời gian trong quá trình đào tạo.

Một số ưu điểm của ANN:
• Tránh được lập trình cấu trúc dựa vào các điều khiển cấu trúc IF-THEN cụ thể
Trang 10/76


Luận Văn Tốt Nghiệp Cao Học
•
•
•
•
•
•
•

Giảm được công sức và yêu cầu kinh nghiệm trong công việc chuyên môn cần giải
quyết
ANN sẵn sàng thích nghi và không cần cập nhật lại khi đầu vào thay đổi
Không cần định nghóa lại cơ sở tri thức
ANN là một hệ thống động và tiếp tục tự cải tiến trong quá trình hoạt động
Có khả năng xử lý lỗi, mâu thuẫn và thậm chí dữ liệu không đầy đủ
Cho phép tổng quát hoá từ những thông tin chi tiết
Cho phép bao gồm cả yếu tố thông minh, kinh nghiệm vào lónh vực giải quyết vấn đề


IV.1.2. Cấu trúc của ANN
Mạng ANN bao gồm ba phần: tầng nhập, các tầng ẩn và tầng xuất.

Các tầng ẩn
Tầng nhập

Tầng xuất
MÔ HÌNH MẠNG ANN

Mỗi nút trong tầng nhập nhận giá trị của một biến độc lập và chuyển vào mạng. Dữ liệu
từ tất cả các nút của tầng nhập được chuyển cho tất cả các nút ở tầng ẩn đầu tiên.
Các nút trong tầng ẩn chỉ có thể liên hệ với các nút trong tầng nhập hay tầng xuất hoặc
giữa chúng với nhau, người sử dụng không thể giao tiếp được với các nút thuộc tầng ẩn
này.
Các nút trong tầng xuất nhận tín hiệu từ các nút thuộc những tầng trước đó, mỗi nút trong
tầng xuất tương ứng với một biến phụ thuộc.
ANN chỉ có một tầng nhập và một tầng xuất, các tầng ẩn có thể không có hoặc có nhiều
là tuỳ vào từng ứng dụng cụ thể và do người thiết kế ANN quy định. Tương tự, số lượng
các nút trong mỗi tầng cũng phụ thuộc vào các ứng dụng khác nhau, do người thiết kế qui
định.

Trang 11/76


Luận Văn Tốt Nghiệp Cao Học
IV.1.3. Mạng nhiều tầng và giải thuật lan truyền ngược
Một mạng lan truyền tổng quát là một mạng có n>2 tầng: tầng thứ nhất là tầng nhập, tầng
thứ n là tầng xuất, còn lại (n-2) tầng ẩn. Trong mạng lan truyền, mỗi nút ở tầng thứ i
(0với nhau. Ngoài ra, còn một số cung liên kết trực tiếp từ các nút tầng nhập đến các nút

tầng xuất, ta gọi mạng này là mạng lan truyền có nối trực tiếp. Mỗi cung trong mạng
được gắn với một trọng số w∈R.
Mạng lan truyền có thể ở một trong hai trạng thái: ánh xạ hoặc học. Trong trạng thái ánh
xạ, thông tin lan truyền từ tầng nhập đến tầng xuất và mạng thực hiện ánh xạ để tính giá
trị các biến phụ thuộc dựa vào giá trị các biến độc lập được cho. Ở trạng thái này, mạng
xử lý mỗi lần một mẫu để tính kết quả xuất của mạng. Trước tiên, các giá trị của các biến
độc lập được truyền cho tầng nhập của mạng, các nút nhập không tính toán gì cả, mỗi nút
nhập chỉ truyền giá trị của nó cho tất cả các nút ẩn. Mỗi nút ẩn tính tổng trọng hoá của tất
cả các dữ liệu nhập bằng cách cộng dồn tất cả các tích giữa giá trị ẩn với trọng số của
cung liên kết giữa các nút nhập và nút ẩn. Hàm truyền chỉ đơn giản nén giá trị vào một
miền giới hạn nào đó. Sau khi nén tổng trọng hoá của nó, đến lượt mình, mỗi nút ẩn sẽ
gửi kết quả đến tất cả các nút xuất. Mỗi nút xuất thực hiện các thao tác tương tự như đã
thực hiện trong nút ẩn để cho ra giá trị kết xuất của nút xuất. Giá trị của các nút xuất
chính là giá trị thực, nghóa là giá trị của các biến phụ thuộc cần xác định.
Bản chất ánh xạ do mạng thực hiện tuỳ thuộc vào giá trị các trọng số trong mạng. Lan
truyền ngược là một phương pháp cho phép xác định tập trọng tốt nhất của mạng để giải
một bài toán được cho. Việc áp dụng phương pháp lan truyền ngược là một quá trình lặp
đi lặp lại nhiều lần hai tiến trình chính: ánh xạ và lan truyền ngược sai số. Hai tiến trình
này được áp dụng trên một tập mẫu xác định, ta gọi chung tiến trình này là huấn luyện
mạng (hay còn gọi là học).
Trong trạng thái học, thông tin được lan truyền theo hai chiều nhiều lần để chỉnh lý các
trọng số trong mạng.
Quá trình luyện mạng được bắt đầu với các giá trị trọng số tuỳ ý, có thể là các số ngẫu
nhiên và được tiến hành lặp đi lặp lại. Mỗi lần được gọi là một thế hệ. Trong mỗi thế hệ,
mạng hiệu chỉnh các trọng số sao cho sai số (độ sai lệch giữa các kết xuất thực và kết
xuất đích) giảm dần. Tiến trình điều chỉnh nhiều lần giúp cho trọng số dần dần đạt được
các giá trị tối ưu. Thông thường mạng cần được huấn luyện qua nhiều thế hệ mới đạt được
kết quả mong muốn.
Để cập nhật trọng số trong mỗi thế hệ, mạng phải xử lý tất cả các mẫu trong tập mẫu.
Đối với từng mẫu, mạng thực hiện các phép toán sau:

• Trước tiên, mạng thực hiện quá trình lan truyền tiến nghóa là mạng ánh xạ các biến
nhập của mẫu hiện hành thành các giá trị xuất, sử dụng các giá trị trọng số hiện hành.
Ở những thế hệ đầu, các kết xuất thường chưa chính xác, vì các trọng số ban đầu cũng
chưa đúng.

Trang 12/76


Luận Văn Tốt Nghiệp Cao Học
•

Sau đó sai số được tính toán dựa trên giá trị của kết quả xuất và giá trị đích, trên cơ sở
sai số tính được, mạng sẽ cập nhật lại các trọng số theo nguyên tắc lan truyền ngược
sai số, gọi là giai đoạn lan truyền ngược.

Như vậy, để học một mẫu, mạng thi hành hai bước: lan truyền tiến-thực hiện ánh xạ và
lan truyền ngược sai số-cập nhật trọng số mạng. Vì thế phương pháp này còn được gọi là
phương pháp lan truyền ngược. Kỹ thuật cơ bản trong lan truyền ngược là cập nhật trọng
số theo hướng giảm gradient dựa vào đạo hàm bậc nhất.
Giảm gradient cũng là kỹ thuật phổ biến trong thống kê học, và lan truyền ngược có thể
được xem như một phương pháp mô hình hoá thống kê. Trong giai đoạn thực hiện ánh xạ,
mạng tính giá trị của các biến phụ thuộc (giá trị của các nút xuất) dựa trên giá trị của các
biến độc lập là các nút nhập của mạng dựa vào các trọng số mạng. Các trọng số mạng
chính là các hệ số của mô hình. Phương pháp giảm gradient được dùng để cập nhật các hệ
số này sao cho giảm thiểu sai số của mô hình. Sai số được đo bằng phương pháp sai số
trung bình bình phương là cách thường được sử dụng để xây dựng các mô hình.
Mã giả mô tả quá trình học tập mẫu:
DO
FOR n=1 to examples
Forward

Back
NEXT n
ChangeWeights
LOOP

// duyệt toàn bộ tập mẫu
// lan truyền tiến
// tính sai số và lan truyền ngược
// cập nhật trọng số mạng

Chương trình là một vòng lặp vô tận, vì vậy ta phải thêm vào điều kiện dừng khi đã duyệt
hết các tập mẫu. Tại mỗi bước lặp, chương trình duyệt qua tất cả các mẫu, với mỗi mẫu
thủ tục Forward được gọi để thi hành giai đoạn lan truyền tiến, xác định các giá trị ánh xạ
dựa vào trọng số mạng hiện hành. Sau đó thủ tục Back được gọi để thi hành giai đoạn lan
truyền ngược, xác định lượng thay đổi trong mỗi trọng số dựa trên mẫu này và tích luỹ
toàn bộ thay đổi cần thiết của mạng. Sau khi duyệt hết tất cả các mẫu cần học trong tập
mẫu, thủ tục ChangeWeights được gọi để cập nhật tất cả các trọng số dựa trên các thay
đổi đã tích luỹ được. Sau đó tiếp tục học tập mẫu mới.
IV.1.4. Hàm truyền
Hàm truyền là hàm qui định phép ánh xạ từ tổng trọng hoá thành các giá trị của các nút.
Nói cách khác, giá trị các nút trong tầng ẩn và tầng xuất là giá trị của hàm truyền với
tham số là tổng trọng hoá. Về mặt hình học, đồ thị của hàm truyền có dạng chữ S, nên
hàm truyền được gọi là hàm dạng S
Một hàm S(u) là một hàm truyền dạng S nếu nó thoả:
• S(u) là hàm bị chặn, nghóa là các giá trị của S(u) không bao giờ vượt quá một chặn
trên cũng như không bao giờ thấp hơn chặn dưới với mọi giá trị u.
• S(u) là hàm đơn điệu tăng, giá trị của S(u) luôn tăng theo giá trị của u
• S(u) là hàm trơn liên tục, giá trị đạo hàm có thể xác định được với mọi u
Trang 13/76

Luận Văn Tốt Nghiệp Cao Học

Mọi hàm thoả tính chất trên đều có thể sử dụng làm hàm truyền trong mạng neural nhân
tạo. Tuy nhiên trong thực tế, người ta thường sử dụng các hàm sau:
• Hàm logistic: về mặt toán học, hàm logistic được định nghóa như sau
1
g (u ) =
1
1+

•

•

e
giá trị kết xuất của hàm này trong khoảng [0,1]
Hàm hyperbole:
−u
1− e
h(u ) =
−u
1+ e

u

giá trị kết xuất của hàm này trong khoảng [-1,1]
Hàm tang-hyperbole
u
−u

−e
e
tanh(u ) = u
−u
e +e

giá trị kết trong khoảng [-1,1] và tiến nhanh đến giới hạn so với h(u)
với e là cơ số logarit tự nhiên, hằng số e có giá trị khoảng 2.71828
Tất cả các hàm truyền này đều phục vụ khá tốt cho mục đích của mạng Neural và chúng
có thể thay thế cho nhau. Do khác nhau về các giới hạn của chúng, ta có thể chọn hàm
này hoặc hàm kia tuỳ theo khoảng cần thiết của giá trị kết xuất. Tuy nhiên, dữ liệu nhập
có thể nhận bất cứ giá trị nào với bất kỳ hàm truyền nào được chọn. Dữ liệu nhập cũng có
thể nhập trực tiếp vào mạng mà không cần phải qua quá trình tiền xử lý.
IV.1.5. Phương trình kết xuất mạng ANN
Phương trình kết xuất các nút ẩn của mạng có J nút ẩn là
y = g (u j ), j = 1..J
j

với g là hàm logistic,

u =a
j

I

0j

+ ∑ aij xi
i =1

trong đó, I là số nút nhập, xi là dữ liệu nhập của nút I, aij là các trọng số từ input i đến ẩn
j, a0j là trọng ngưỡng của nút ẩn j.
Trong không gian (I+1) chiều, kết xuất của nút ẩn j là siêu phẳng-S I-chiều. Mặt này biểu
diễn tập các điểm thoả phương trình của yj, khi biết trị đặc biệt các trọng số aij và a0j. các
trọng số aij điều khiển hướng và độ dốc của mặt phẳng nghiêng trong siêu phẳng-S theo
từng chiều tương ứng với các biến nhập. Trọng ngưỡng a0j điều khiển khoảng cách từ gốc
đến mặt phẳng nghiêng.
Một nút ẩn với các trọng số cụ thể chia không gian nhập I-chiều thành hai vùng: một
vùng có kết xuất cao và một vùng có kết xuất thấp. Biên chia các vùng này là một siêu
phẳng (I-1)-chiều trong không gian nhập I-chiều. Biên này là hình chiếu trên không gian
nhập của siêu phẳng-S của các kết xuất nút ẩn với siêu phẳng trực giao với trục y, và cắt
nó tại trung điểm của các biên.
Trang 14/76


Luận Văn Tốt Nghiệp Cao Học
Đối với mỗi trục i của không gian nhập, giao điểm của biên là:
−
xi = a0 , i = 1..I

a

i

Phương trình kết xuất của mạng với K nút xuất là
zk=g(vk),k=1..K
Trong đó g là hàm logistic,

J

vk = b0k + ∑ b jk
j =1

y

j

Có J nút ẩn với các kết xuất yj, bjk là các trọng số trên các cung liên kết từ nút ẩn j đến
nút xuất thứ k, b0k là trọng số ngưỡng của nút xuất thứ k.
Các phương trình này được giải thích theo thuật ngữ mạng như sau: mỗi nút trong J nút ẩn
chuyển giá trị kết xuất yj của nó đến từng nút xuất, mỗi nút xuất trong K nút xuất tính
tổng trọng hoá theo J và cộng với ngưỡng b0k. Kết xuất zk là giá trị hàm logistic của tổng
này.

IV.1.6. Máy học
Lan truyền tiến là quá trình tính giá trị các nút xuất từ các giá trị nhập vào mạng. Nó
lượng giá biểu thức tính các kết xuất của mạng như là hàm theo các mẫu nhập. Nói một
cách khác, biểu thức này thực hiện ánh xạ từ các dữ liệu nhập vào miền giá trị của các
kết xuất, có thể gọi là một hàm ánh xạ. Hàm ánh xạ có thể xấp xỉ bất kỳ một hàm đích
nào nếu các hệ số của nó (trong trường hợp này là các trọng số của mạng) được xác định
đúng. Với một hàm đích cho trước, thường dưới dạng bảng hoặc liệt kê, quá trình xác định
các trọng số của một mạng xấp xỉ hàm này được gọi là quá trình học.
Học là quá trình tìm các trọng số của mạng sao cho hàm ánh xạ khớp nhất với bộ dữ liệu
chứa các mẫu của hàm đích. Bộ dữ liệu này được gọi là tập mẫu. Sai số trung bình bình
phương được dùng để đánh giá sự trùng khớp giữa ánh xạ cần xây dựng với hàm đích cho
trước (qua tập mẫu).
Cho tập mẫu:
Ω={(Xk,Zk)=(xk1,…,xkM;zk1,…,zkN)xki,zkj∈R;i=1…M;j=1…N;k=1..K} gọi Tk=NN(Xk)=(tk1,…tkN)
thì sai số trung bình bình phương E là:
2

1 N K
(
−
)
∑∑
t
z
2 n =1 k =1 kn kn
E=
N .K
về mặt hình học ta có thể xem E như một mặt lỗi. Lưu ý là hình dạng của mặt lỗi phụ
thuộc vào một tập mẫu cụ thể đang xét. Nếu tập mẫu thay đổi, có khả năng mặt lỗi cũng
thay đổi. Mặt lỗi là siêu phẳng trong đó mỗi điểm của nó tương ứng với một điểm trong
không gian trọng. Chiều cao trên không gian trọng của mỗi điểm trong mặt lỗi biểu diễn
sai số của mô hình ứng với các trọng tương ứng đó. Điểm thấp nhất trên mặt lỗi cho ta mô
hình có sai số ít nhất.

Trang 15/76


Luận Văn Tốt Nghiệp Cao Học
Hồi qui tuyến tính là một phương pháp cho phép xác định tập các hệ số của một mô hình
tuyến tính của một tập mẫu cho trước sao cho sai số trung bình bình phương là nhỏ nhất.
Nghóa là xác định trong không gian trọng sao cho sai số E tương ứng điểm thấp nhất trong
mặt lỗi.Trong trường hợp mô hình là hàm không tuyến tính, như mạng neuron chẳng hạn,
việc xác định được tập trọng số để mô hình tạo sai số ít nhất là rất khó. Phương pháp
giảm gradient thường được sử dụng trong các trường hợp phức tạp này:
1. Chọn ngẫu nhiên một điểm x0 trong không gian trọng số
2. Tính độ dốc của mặt lỗi tại x0
3. Cập nhật các trọng số theo hướng dốc nhất của mặt lỗi

4. Tiếp tục xem điểm này như điểm x0 mới
Lặp đi lặp lại quá trình từ (2) đến (4) thì đến một lúc nào đó các giá trị của bộ trọng số sẽ
tiếp cận được điểm thấp nhất theo hướng giảm gradient. Tuy nhiên điểm thấp nhất tìm thấy
này chưa chắc là điểm thấp nhất trên mặt phẳng lỗi, mà đó có thể là điểm cực tiểu cục bộ.
Tìm cách tránh rơi vào điểm cực tiểu cục bộ là một vấn đề nan giải. Tuy nhiên, trong thực
hành mạng neuron, vấn đề không nghiêm trọng như vậy. Bằng các kỹ thuật bẫy khi tiến
trình rơi vào một cực tiểu cục bộ mà không thể tránh được thì có thể thêm một nút ẩn vào
mạng neuron. Việc thêm vào các nút ẩn rất có khả năng loại trừ cực tiểu cục bộ. Hornil
(1990) đã chứng minh được rằng một mạng neural với số nút ẩn thích hợp có thể xấp xỉ một
hàm đích bất kỳ với sai số bất kỳ.
Dù ta không thể tính toán được dạng của toàn mặt lỗi nhưng ta có thể tính được chiều cao và
độ dốc mặt lỗi tại bất kỳ điểm nào trong không gian trọng. Trong toán học, độ dốc mặt lỗi
được xác định qua đạo hàm riêng theo từng trọng số trong mạng neural.
Máy học trong ngữ cảnh mạng neural ta đang xét là quá trình cập nhật các trọng số của
mạng sao cho hàm lỗi E giảm dần. Bất cứ phương pháp nào giúp xác định biến thiên trọng,
khi cập nhật các trọng số sao cho E giảm, đều được gọi là qui tắc học.
Có nhiều qui tắc học đã được công bố, nhưng ở đây đề cập đến giải thuật lan truyền ngược.
Giải thuật này sử dụng qui tắc học giảm theo hướng dốc nhất. Ta gọi là giảm dốc nhất. Qui
tắc này sử dụng các thông tin đạo hàm để cập nhật trọng số của mạng. Hiện nay, những
người thiết kế mạng neural có kinh nghiệm thường sử dụng các biến thể của giải thuật
nguyên thuỷ này; lý do là vì tốc độ thuật giải nguyên thuỷ rất chậm.
Qui tắc học giảm dốc nhất
Qui tắc giảm dốc nhất còn được gọi là qui tắc delta, là một trong những qui tắc học nguyên
thuỷ nhất của lan truyền ngược. Phương pháp này được Rumelhart, Hinton và Williams giới
thiệu năm 1986.
Khi hoàn thành một bước lặp qua toàn bộ tập mẫu, tất cả trọng số của mạng sẽ được cập
nhật dựa trên thông tin đạo hàm riêng theo từng trọng số tích luỹ được. Đúng như tên được
đặt cho phương pháp, giảm dốc nhất, các trọng số sẽ được cập nhật theo hướng mà hàm lỗi E
tụt xuống dốc nhất.

Trang 16/76


Luận Văn Tốt Nghiệp Cao Học
Tại bất kỳ điểm nào trên không gian trọng số, giá trị hàm lỗi trung bình bình phương hoàn
toàn được xác định qua tập mẫu dùng luyện mạng. Như đã thảo luận, lỗi có thể coi như là
chiều cao của điểm đó trên mặt lỗi, trong không gian trọng. Ta không thể biết được chiều
cao của mặt lỗi của mỗi điểm trong không gian trọng mà chỉ có thể biết được tại điểm đang
xét tương ứng với bộ trọng số hiện hành.Tại một điểm cho trước trong không gian trọng số,
có hai vấn đề cần quan tâm: thứ nhất là xác định hướng nào để lỗi giảm nhanh nhất; vần đề
thứ hai là quyết định độ lớn của bước chuyển trọng số theo hướng đó.Trước hết, ta tìm độ
dốc trong mặt lỗi chỉ theo một trọng số trong không gian trọng. Với mỗi mẫu, đạo hàm hàm
lỗi được biểu diễn bằng một vectơ có hướng. Độ lớn mỗi vectơ tương ứng với sai số của mẫu
đó. Nếu đạo hàm hàm lỗi dương, hướng của vectơ sang phải; ngược lại nó hướng sang trái.

Đạo hàm hàm lỗi theo từng trọng
Như vậy, đạo hàm hàm lỗi trên toàn tập mẫu chính là tổng vectơ của từng vectơ đạo hàm
của từng mẫu trong tập mẫu.
Bây giờ, ta xét hai trọng số khác nhau. Độ lớn và hướng của mỗi vectơ sai số trung bình
tương ứng với từng trọng số đó được tính theo cách nêu trên. Kết quả ta sẽ có hai vectơ. Biểu
diễn chúng trong một hệ trục tạo từ các trọng số này, ta có hai mũi tên vuông góc nhau và
cùng độ lớn tại một vị trí như minh hoạ

Nếu mạng chỉ có hai trọng số thì tổng lỗi chính là tổng vectơ của hai đạo hàm riêng hàm lỗi
này. Độ lớn vectơ tổng chính là đường chéo hình chữ nhật tạo từ hai vectơ đạo hàm riêng và
hướng theo góc đối nghịch của hình chữ nhật. Theo qui tắc cộng vectơ, độ lớn vectơ tổng
tương ứng với độ dốc nhất của mặt lỗi tại điểm đó và vectơ theo hướng ngược lại vectơ tổng
biểu diễn hướng giảm dốc nhất. Tương tự, ta có thể tính vectơ tổng của nhiều vectơ đạo hàm
riêng hàm lỗi, từ đó, dễ dàng xác định được hướng mà hàm lỗi giảm dốc nhất.

Trang 17/76


Luận Văn Tốt Nghiệp Cao Học
Vấn đề thứ hai là xác định độ lớn bước theo hướng đã xác định ở trên. Bài toán này được
dành cho người thiết kế mạng quyết định thông qua tham số ε (gọi là tham số học), ε ∈ (0,1).
Tiến trình cập nhật trọng số được hình thức hoá bằng toán học như sau:
Gọi wt là giá trị trọng số w tại bước thứ t. Để đơn giản, ta dùng ký hiệu w biểu diễn trọng
số nói chung, thay vì phải dùng aij cho trọng số nút ẩn và bik cho nút xuất. Công thức cập
nhật trọng số là
wm=wm-1 + cm,
cm = -εdm
cm trong công thức trên được gọi là biến thiên của trọng số w ở bước thứ m. dấu trừ diễn tả
hướng ngược lại của vectơ tổng. dm chính là độ lớn của vectơ tổng này và được tính theo
dòng công thức:
N

d m = ∑(
n =1

∂E
)
∂ wm

n

Giá trị tham số học ε do người dùng quyết định, chưa có qui tắc tổng quát hướng dẫn cách
chọn giá trị cho ε. Thông thường người ta sử dụng phương pháp thử và sai để xác định ε bằng
thực nghiệm. Đây chính là hạn chế của qui tắc học giảm dốc nhất.
Nếu chọn được giá trị ε tốt, tiến trình giảm gradient sẽ nhanh chóng hội tụ; ngược lại quá

trình hội tụ phải rất lâu mới đạt được.
Qui tắc học thích nghi
Quy tắc này còn có tên là delta-bar-delta, là một phương pháp cải tiến được xem là hiệu quả
nhất của phương pháp delta, được Robert Jacobs và cộng sự đưa ra năm 1988. Nguyên tắc
của phương pháp này như sau: mỗi trọng số có một hệ số học e khác nhau, khi cập nhật trọng
số, nếu hướng giảm lỗi hiện hành cùng hướng với bước trước thì cho e lớn, còn ngược lại thì
cho e nhỏ.
Hướng lỗi giảm được xác định bởi dấu của dm, là đạo hàm riêng của hàm lỗi theo trọng số ở
bước thứ m. Nếu dm dương, lỗi giảm khi trọng số giảm, nếu dm âm, lỗi giảm khi trọng tăng.
Phương pháp này vận dụng khái niệm hướng lỗi “vừa mới giảm”. Ta có thể định nghóa
hướng này như một hàm theo d như sau:
fm+1=θ fm + (1 - θ)dm
trong đó 0 ≤ θ < 1 là tham số cho biết khoảng thời gian mới đây là bao lâu. Nếu θ = 0, thì
fm+1 = dm và khoảng thời gian mới đây là bây giờ. Nếu θ = 0.5, thì fm+1=0.5dm + 0.5fm. nhưng
vì fm được xác định từ những giá trị quá khứ của d nên thực sự có thể nói rằng:
fm+1 = 0.5 dm + 0.25dm-1 + 0.125 dm-2 + …
và cứ thế, trở về đến 1. Khi θ tiến về 1, giá trị dm hiện tại giảm và các giá trị quá khứ của d
được tính bởi fm lại tăng.

Trang 18/76


Luận Văn Tốt Nghiệp Cao Học
Nếu ta cho f là trung bình trọng số của các đạo hàm hiện tại và quá khứ, θ là trọng số cho
biết đạo hàm đã qua và (1 - θ) là trọng số cho biết đạo hàm hiện tại. Nếu f dương thì có thể
biết mới đây là “lỗi giảm khi trọng giảm” và ngược lại, cũng như đối với chính đạo hàm.
Dựa vào dấu của dm và fm ta có thể đo chính xác cả hướng mà lỗi hiện đang giảm và hướng
mà lỗi vừa mới giảm. Nếu chúng cùng dấu, việc giảm lỗi xảy ra theo cùng hướng cũ, nếu
khác dấu, hướng sẽ ngược với hướng cũ.
Chúng ta có thể kiểm chứng xem hướng mà lỗi giảm có thay đổi không bằng cách nhân dm

với fm. Nếu tích số này dương thì cùng dấu, nếu âm thì khác dấu.
Hệ số học thích nghi được tính theo công thức:
⎧⎪e + k , d f > 0
m −1
m
=
em ⎨ * Φ, f m ≤ 0
⎪⎩em −1
dm m
Trong đó k và φ là các tham số, nếu sắp đi theo cùng hướng, e sẽ tăng một lượng bằng hằng
số k. Nếu hướng đổi, e được nhân với một lượng bằng φ, 0 < φ <1.
Khi đã xác định e, biến thiên trọng số được xác định theo công thức:
cm= - em dm
Trong thực nghiệm, hệ thống không nhạy cảm lắm đối với việc chọn lựa các giá trị của k, φ
và θ. Thường các tham số này được gán giá trị như sau:
k= 0.1
φ = 0.5
θ = 0.7
Phương pháp sử dụng hệ số học thích nghi cho mỗi trọng số sẽ làm tăng tốc độ học. Để đạt
được cùng phương pháp delta, phương pháp này thường chỉ cần 1/10 số bước lặp so với
phương pháp delta.
Ngoài ra, còn có các qui tắc học khác như học từng mẫu, qui tắc moment…
IV.2. Lập trình tối ưu hoá
IV.2.1. Lập trình ràng buộc
Giống như lập trình logic, lập trình ràng buộc thuộc về phương thức lập trình mô tả
(declarative programming)
Lập trình ràng buộc là lãnh vực nghiên cứu các hệ thống tính toán dựa trên các ràng buộc
(constraint). Ý tưởng chính của nó là giải bài toán ứng dụng bằng cách phát biểu những
ràng buộc của bài toán, và sau đó, tìm kiếm lời giải thoả mãn một phần hoặc tất cả những
ràng buộc đó.

So với các phương pháp cổ điển hơn, lập trình ràng buộc có những ưu điểm:
• Thời gian phát triển phần mềm nhanh
• Mềm dẻo, linh hoạt, dễ thích ứng với thay đổi
• Dể đưa vào các tương tác với người sử dụng

Trang 19/76


Luận Văn Tốt Nghiệp Cao Học
Những ưu điểm trên được tạo ra mà không hề làm suy giảm tính hữu hiệu của chương
trình.
Lập trình ràng buộc có liên quan đến một lónh vực của AI (Artificial Intelligence) là giải
các hệ ràng buộc (constraint satisfaction problems)
Một bài toán giải hệ ràng buộc Contraint Satisfaction Problem (CSP) bao gồm một bộ ba
P=(V,D,C), trong đó:
V={V1,V2,…,Vn} là một tập các biến
D={Dv1,Dv2,..,Dvn} là tập hợp các miền trị của các biến
C={C1,C2,…,Cm} là tập hợp các ràng buộc trên các biến, nó giới hạn khả năng lựa chọn
giá trị cho biến.
Nếu các miền trị là những tập trị hữu hạn và rời rạc thì bài toán CSP được gọi là CSP trên
miền trị hữu hạn FCSP.
Các bài toán CSP chủ yếu được chia làm hai loại chính:
• Bài toán thoả mãn ràng buộc (Satisfiability problems): Mục tiêu là gán trị cho các
biến thoả mãn tất cả các ràng buộc
• Bài toán tối ưu (Optimization problems): Căn cứ vào độ ưu tiên của các ràng buộc,
mỗi giá trị được gán vào biến có mức chi phí (cost) hay giá trị mục tiêu (objective
cost). Mục tiêu của bài toán là tìm ra lời giải có tổng chi phí thấp nhất hoặc tổng giá
trị mục tiêu cao nhất.
Tất cả các bài toán CSP đều là bài toán NP-complete, có độ phức tạp tính toán hàm mũ.
I.1.1.1. Giải thuật Backtracking căn bản

Giải thuật căn bản để giải các bài toán FCSP là giải thuật backtracking, còn gọi là
treesearch. Điểm căn bản của giải thuật này là các biến được sắp xếp theo một thứ tự
nào đó, sau đó lần lượt gán được trị. Trong quá trình gán trị, mỗi biến được kiểm tra
xem có vi phạm ràng buộc với những biến khác đã gán hay không. Nếu có một ràng
buộc không thoả mãn, phải chọn giá trị khác cho biến hiện hành. nếu tất cả các giá trị
trong miền trị của biến hiện hành đều vi phạm ràng buộc thì phải thuật thực hiện cơ
chế quay lui về biến trước đó.
Mã giả của giải thuật
1
Procedure BACKTRACKING
2
i:=1
3
Di’:=Di
4
While 1<=i<=n
5
Instaniate vi:=SELECTVALUE
6
If vi is null then
7
i:=i -1
8
Else
9
i:=i+1
10
Di’:=Di

Trang 20/76

Luận Văn Tốt Nghiệp Cao Học
11
12
13
14
15
16

End While
If i=0
Return “inconsistent”
Else
Return instantiated values of {v1,v2,…,vn}
End procedure

1
2
3
4
5
6
7
8

Procedure SELECTVALUE
While Di’ is not empty
Select an arbitrary element a ∈ Di’ and remove a from Di’
If value a for vi is consistent with <a1,…,ai> then

Return a
End while
Return null
End procedure
I.1.1.2. Giải thuật Backtracking có kiểm tra hướng tới (forward checking)
Giải thuật backtracking có một nhược điểm chính là bị thrashing, tức là dò tìm trên
những nhánh khác nhau của không gian tìm kiếm thì có thể bị lặp lại cùng một số thất
bại cũ. Có nhiều kỹ thuật nhằm cải tiến giải thuật này được đề ra, nhìn chung, có hai
loại sau:
• Kỹ thuật nhìn hướng lui (look back): được dùng khi giải thuật gặp tình huống phải
quay lui lại biến trước đó.
• Kỹ thuật nhìn hướng tới (look ahead): được dùng khi giải thuật backtraking chuẩn
bị gán trị cho biến kế tiếp. Kỹ thuật này được ưu chuộng hơn vì dễ kết hợp với các
heuristic sắp thứ tự biến và sắp thứ tự trị, thường được sử dụng phối hợp với một
kỹ thuật tương thích (consistency technique) để tiền xử lý các miền trị dựa vào sự
lan truyền ràng buộc. Có nhiều cách phối hợp giữa backtracking với kỹ thuật tương
thích. Một giải thuật căn bản trong nhóm này được gọi là kỹ thuật backtracking có
kiểm tra hướng tới (backtracking with forward checking). Giải thuật này bổ sung
vào giải thuật backtracking căn bản các động tác loại ra khỏi miền trị của các biến
chưa được gán trị tất cả những trị nào không tương thích với sự gán trị hiện hành.

1
2
3
4
5
6
7
8
9

10

Mã giả giải thuật:
Procedure BACKTRACKING-WITH-LOOK-AHEAD
Di’:=Di for 1<=i<=n
i:=1
While 1<=i<=n
Instaniate vi:=SELECTVALUE-FORWARDCHECKING
If vi is null then
i:=i -1
Reset each Dk’,k>i, to its value before vi was last instantiated
Else
i:=i+1

Trang 21/76


Luận Văn Tốt Nghiệp Cao Học
11
12
13
14
15
16

End While
If i=0
Return “inconsistent”
Else
Return instantiated values of {v1,v2,…,vn}

End procedure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Procedure SELECTVALUE-FORWARD-CHECKING
While Di’ is not empty
Select an arbitrary element a ∈ Di’ and remove a from Di’
Empty_domain:=fasle
For all k,iFor all values b in Dk’
If value a for vi is consistent with <a1,…,ai> and vi=a then
Remove b from Dk’

End for
If Dk’ is empty then
Empty_domain:=true
End for
If Dk’ is empty then
Reset each Dk’, iElse
Return a
End while
Return null
End procedure
IV.2.2. Kỹ thuật Simulated Annealing và Local Search
Simulated Annealing (SA) là một kỹ thuật tối ưu hoá được đề xuất bởi S.Kirkpatrick và
các đồng sự năm 1983. Kỹ thuật này là một dạng của phương pháp tìm kiếm cục bộ (local
search), cho phép ta tạo ra những bước chuyển trạng thái tốt hơn theo một cách có kiểm
soát.
Kỹ thuật này mô phỏng việc luyện kim: nung nóng kim loại trong một lò nhiệt rồi làm
nguội đi. Quá trình này được gọi là annealing. Nếu ta nung nóng kim loại vượt qua điểm
hoá lỏng và rồi làm nguội nó. Các tính chất về cấu trúc của kim loại sẽ tuỳ thuộc vào tốc
độ làm nguội. Nếu quá trình làm nguội là hạ nhiệt độ dần dần cho đến khi kim loại hội tụ
về một trạng thái ổn định. p dụng vào bài toán tối ưu hoá, SA sẽ tìm kiếm những lời giải
khả thi và rồi hội tụ về lời giải tối ưu.
Nguyên tắc chọn bước chuyển trạng thái của SA:
SA luôn chọn các bước chuyển trạng thái có hàm chi phí tốt hơn so với trạng thái hiện
hành, tuy nhiên với các bước chuyển trạng thái tệ hơn thì SA vẫn có thể chấp nhận nó với

Trang 22/76


Luận Văn Tốt Nghiệp Cao Học

một xác suất nào đó. Với cách này, SA tránh được nguy cơ bị rơi vào trạng thái tối ưu cục
bộ và có cơ hội để tìm các lời giải khác tốt hơn trên không gian tìm kiếm.
Tiêu chuẩn để chấp nhận bước chuyển trạng thái:
Luật của nhiệt động học phát biểu rằng tại nhiệt độ t, xác suất cho một sự gia tăng về
mức năng lượng là:
[1]
P(δE)=exp(-δE/kt)
Với k là hằng số Boltzmann
SA mô phỏng giải thuật tính mức năng lượng mới của hệ thống. Nếu năng lượng đã giảm
thì hệ thống đi vào trạng thái năng lượng đó. Nếu năng lượng đã gia tăng thì trạng thái
mới được chấp nhận bằng cách dùng một xác suất cho ở công thức trên.
Một số bước lặp sẽ được thực hiện ở mỗi giá trị nhiệt độ và rồi thì nhiệt độ được giảm đi.
Điều này lặp lại nhiều lần cho đến khi hệ thống ngưng tụ vào một trạng thái ổn định.
Phương trình [1] được dùng trực tiếp trong giải thuật SA, mặc dù hằng số k thường được
bỏ đi. Do đó xác suất để chấp nhận một trạng thái dở hơn được cho bởi phương trình:
P=exp(-c/t) > r
Trong đó
c: mức thay đổi trong hàm chi phí
t: thông số điều khiển (nhiệt độ hiện thời)
r: một số ngẫu nhiên trong khoảng (0,1)
Mối liên hệ giữa Annealing thực sự và Simulated Annealing
Mô phỏng nhiệt động học
Tối ưu tổ hợp
Các trạng thái của hệ thống Các lời giải khả thi
Năng lượng
Chi phí
Chuyển trạng thái
Các lời giải lân cận
Nhiệt độ
Thông số điều khiển

Trạng thái ổn định
Lời giải
Với bảng liên hệ này, bất kỳ bài toán tối ưu tổ hợp nào cũng có giải được bằng kỹ thuật
SA.
Giải thuật Simulated Annealing
Để có thể áp dụng được kỹ thuật SA, ta phải diễn tả bài toán trong dạng thức của phương
pháp tìm kiếm cục bộ, bằng cách định nghóa:
• Không gian giải bài toán (solution space)
• Cơ cấu xác định vùng lân cận (neighbourhood structure)
• Hàm chi phí (cost function)
Mã giả giải thuật Simulated Annealing
1
2
3
4

Select an initial solution s0
Select an initial temperature t0>0
Select a temperature reduction function α

// s is a neighbour solution of s0

Repeat

// compute the change in cost function

Trang 23/76


Luận Văn Tốt Nghiệp Cao Học

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Select a nrep for current temperature t

Repeat
Randomly select s∈N(s0)
δ=f(s)-f(s0)
If δ<0 then
s0=s
Else
// x is random number in range 0 to 1
Generate random x ∈ [0,1]
If x < exp(-δ/t) then
s0=s
Endif

Endif
Until iterration_count = nrep
t=α(t)
Until stoppingcondition = true
/* s0 is the approximation to the optimal solution */

Chất lượng lời giải
Các bước di chuyển dự tuyển được chọn một cách ngẫu nhiên và tất những bước di
chuyển có cải thiện đều đươc chấp nhận một cách tự động . Còn các bước di chuyển khác
được chấp nhận với một xác suất exp (-δ/t) , với δ là mức thay đổi ở hàm chi phí và t là
một thông số điều khiển .
Chú ý rằng chất lượng của các lời giải thì nhạy cảm đối với cách thức thông số nhiệt độ t
được điều chỉnh-còn được gọi là lịch biểu làm nguội (cooling schedule). Lịch biểu làm
nguội được định nghóa bằng :
• một nhiệt độ khởi đầu t0,
• các điều kiện dừng,
• hàm giảm thiểu α và
• số lần lặp tại mỗi nhiệt độ, nrep
Tất cả những giá trị trên tuỳ thuộc vào từng bài toán áp dụng vì chúng phải được lựa chọn
theo dạng của không gian lời giải.

Trang 24/76


Luận Văn Tốt Nghiệp Cao Học

PHẦN 2: GIẢI QUYẾT VẤN ĐỀ THỰC TẾ
Phần này trình bày các công việc chính mà luận văn thực hiện:
1. Thu thập dữ liệu và xây dựng hệ thống thông tin địa lý hỗ trợ cho các yêu cầu tạo lập, lưu trữ
cập nhật, truy xuất thông tin của nhà điều hành nguồn nước

2. Xây dựng phần mềm “RunOffPredict”, hỗ trợ nhà điều hành trong việc dự báo nguồn tài
nguyên nước sẽ có được để có thể điều hành hiệu quả
3. Xây dựng phần mềm “ReservoirManager”, hỗ trợ nhà điều hành trong việc phân tích, tìm ra
phương án điều tiết tốt nhất, hợp lý nhất
4. Xây dựng chương trình điều phối hoạt động của ba chương trình trên như một hệ DSS thống
nhất.
V- XÂY DỰNG HỆ THỐNG THÔNG TIN ĐỊA LÝ PHỤC VỤ QUẢN LÝ DỮ

LIỆU
V.1. Bản đồ số khu vực hồ Trị An

Trang 25/76