ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG NGUYỄN THỊ HỒNG NHUNG MỘT SỐ THUẬT TOÁN
GIẢI BÀI TOÁN PHÂN CÔNG NHIỆM VỤ
TRONG HỆ THỐNG TÍNH TOÁN
KHÔNG ĐỒNG NHẤT
LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH MỤC LỤC

TRANG PHỤ BÌA
LỜI CAM ĐOAN
MỤC LỤC i
DANH MỤC CÁC BẢNG iii
DANH MỤC CÁC HÌNH iv
LỜI NÓI ĐẦU 1
CHƢƠNG I: GIỚI THIỆU SƠ LƢỢC VỀ HỆ THỐNG TÍNH TOÁN
KHÔNG ĐỒNG NHẤT MỘT SỐ BÀI TOÁN PHÂN CÔNG NHIỆM VỤ 3
1.1. GIỚI THIỆU SƠ LƢỢC VỀ HỆ THỐNG TÍNH TOÁN KHÔNG ĐỒNG
NHẤT. 3
1.1.1. Giới thiệu 3
1.1.2. Mô hình khái niệm HC 6
1.2. GIỚI THIỆU MỘT SỐ BÀI TOÁN PHÂN CÔNG NHIỆM VỤ 9
1.2.1. Bài toán phân công nhiệm vụ trong hệ thông tính toán không đồng
nhất…………………………………………………………………………… 9
1.2.2. Bài toán lập lịch thực hành 13
1.2.3. Bài toán lập lịch gia công 14
1.3. KẾT LUẬN 15
CHƢƠNG II: MẠNG NƠ RON VÀ GIẢI THUẬT DI TRUYỀN GIẢI BÀI
TOÁN KHÔNG ĐỒNG NHẤT 16
2.1. GIỚI THIỆU VỀ MẠNG NƠ -RON 16
2.1.1. Lịch sử phát triển 16
2.1.2. Mô hình mạng nơ-ron nhân tạo 17
2.2. PHẠM VI ỨNG DỤNG CỦA MẠNG NƠ -RON 21
2.2.1. Những bài toán thích hợp 21
2.2.2. Các lĩnh vực ứng dụng mạng nơ-ron 22

3.3. KẾT LUẬN 53
KẾT LUẬN 55
TÀI LIỆU THAM KHẢO 57

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
iii
DANH MỤC CÁC BẢNG

Bảng 3.1: Trƣờng hợp thử nghiệm với 15 công việc và 5 bộ xử lý
50
Bảng 3.2: So sánh các kết quả thu đƣợc của HNNGA và HNNSA
53

35
Hình 2.8: Lƣu đồ thuật toán của quá trình đột biến .
36 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-1- LỜI NÓI ĐẦU
Hiện nay, các máy tính có tốc độ xử lý rất cao, đôi khi thực hiện một số
công việc thì chỉ dùng đến một phần nhỏ khả năng của tốc độ đó.
Điều này là bởi vì các công việc khác nhau cần đến các yêu cầu tính toán rất
khác nhau vì vậy phải có các máy tính có khả năng khác nhau để đáp ứng
yêu cầu. Một máy tính có cấu trúc đơn lẻ, có thể không đáp ứng đƣợc tất cả
các yêu cầu tính toán công việc mà có kết quả tốt nhƣ nhau. Vì vậy, việc sử
dụng một môi trƣờng tính toán không đồng nhất là rất thích hợp.
Trong hệ thống không đồng nhất, gồm có xử lý song song, phân phối,

của giải pháp đƣợc tìm thấy, đó là: Thuật toán lai ghép mạng Nơron Hopfield
- giải thuật di truyền và thuật toán lại mạng Nơron Hopfield- mô phỏng luyện
kim.
Qua luận văn này em xin chân thành cảm ơn: PGS .TS Đặng Quang Á -
Viện Công nghệ thông tin đã tận tình giúp đỡ, động viên, định hƣớng, hƣớng
dẫn em nghiên cứu và hoàn thành luận văn. Em xin cảm ơn các thầy cô giáo
trong viện Công nghệ thông tin, các thầy cô giáo Trƣờng Đại học Công nghệ
thông tin và truyền thông ĐH Thái nguyên, đã giảng dạy và giúp đỡ em
trong hai năm học vừa qua, cảm ơn sự giúp đỡ nhiệt tình của các bạn đồng
nghiệp.
Xin chân thành cảm ơn!

Thái Nguyên, tháng 06 năm 2012
Ngƣời viết luận văn

Nguyễn Thị Hồng Nhung
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-3- CHƢƠNG I
GIỚI THIỆU SƠ LƢỢC
VỀ HỆ THỐNG TÍNH TOÁN KHÔNG ĐỒNG NHẤT
MỘT SỐ BÀI TOÁN PHÂN CÔNG NHIỆM VỤ

1.1. GIỚI THIỆU SƠ LƢỢC VỀ HỆ THỐNG TÍNH TOÁN KHÔNG
ĐỒNG NHẤT.
Hệ thống tính toán không đồng nhất hiệu suất cao (sau đây gọi là HC),
trong môi trƣờng này bao gồm các máy với khả năng tính toán khác nhau kết
nối với nhau bằng các liên kết tốc độ cao. Môi trƣờng này rất thích hợp để


Hình 1.1: Mô hình trên trạm làm việc cơ bản
Xét hình 1.1: Trong đó cho thấy một ví dụ giả thuyết của một chƣơng
trình ứng dụng với các thành phần khác nhau là tốt nhất phù hợp để thực
hiện một kiến trúc máy tính khác nhau. Các ứng dụng trong ví dụ bao
gồm một nhiệm vụ đƣợc phân tách thành bốn công việc phụ liên tiếp. Ứng
dụng này thực hiện cho 100 đơn vị thời gian trên một máy trạm cơ bản, nơi
mà mỗi công việc phụ là phù hợp nhất với kiến trúc máy tính và có số lƣợng
thời gian chỉ ra bên dƣới trong hình [5].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-5- Bằng cách thực hiện toàn bộ ứng dụng trên một nhóm các máy trạm, thời
gian thực hiện của một cụm lớn các công việc phụ theo định hƣớng có thể
giảm từ 35 đến 0,3 đơn vị thời gian.Thực hiện việc cải thiện thời gian tổng thể
cho toàn bộ ứng dụng chỉ khoảng gần 2 lần bởi vì các công việc phụ khác có
thể không đƣợc thích hợp cho một kiến trúc nhóm.
Ngoài ra, việc sử dụng của 4 kiến trúc máy tính khác nhau, để phù hợp
với các yêu cầu tính toán mà các công việc phụ đƣợc giao, có thể dẫn đến
một thực hiện 50 lần nhanh nhƣ máy trạm cơ bản. Điều này là bởi vì mỗi
công việc phụ đƣợc thực hiện trên kiến trúc hiệu suất cao mà nó thích hợp
nhất. Thời gian thực hiện đƣợc hiển thị bên dƣới cho các bộ HC trong
hình.1.1 bao gồm chi phí thông tin liên lạc giữa các máy tính cho mỗi công
việc phụ để truyền dữ liệu đến công việc phụ tiếp theo. Giữa các máy đơn thì
chi phí thông tin liên lạc là không cần thiết trong việc triển khai các nhiệm vụ.
Việc xây dựng một bộ HC với tất cả bốn loại máy, tất nhiên là tốn kém
hơn so với chỉ duy nhất một máy trạm hoặc một nhóm các máy trạm đơn lẻ.
Nhƣ vậy, trạng thái công việc ổn định của các ứng dụng phải có đủ để biện
minh cho chi phí của hệ thống. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-7-
Hình 1.2: Mô hình khái niệm hệ thống HC
Hình1.2: Mô hình hỗ trợ cần thiết để tự động hoá việc sử dụng các hệ
thống HC [10]. Hình Elip đại diện cho các thông tin và hình chữ nhật đại diện
cho các hành động. Các đƣờng nét đứt đại diện cho các thành phần cần thiết
để thực hiện lập ánh xạ động.
4

3
Các ứng dụng
Các máy
trong bộ
Tạo ra các thông số liên quan
đến ứng dụng và máy
Danh mục các nhu cầu
cần tính toán
Danh mục khả năng của
máy

Mô tả nhiệm vụ của
các ứng dụng


trên các máy trong bộ Màm hình hiệu suất
của hệ thống

1
2
stage
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-8- Một mô hình khái niệm cho môi trƣờng HC bằng cách sử dụng một bộ
các máy chuyên dụng đƣợc mô tả trong hình1.2. Mô hình khái niệm bao
gồm bốn giai đoạn:
Giai đoạn 1: Đƣa ra các loại dự kiến về việc sử dụng thông tin trong các
nhiệm vụ ứng dụng và các máy trong bộ HC, một tập hợp các tham số đƣợc
tạo ra có liên quan đến các yêu cầu tính toán của các ứng dụng và khả
năng máy của hệ thống HC. Ví dụ, nếu không có các ứng dụng, dự kiến sẽ
bao gồm các hoạt động điểm nổi, không cần thiết để mô tả việc thực hiện
điểm nổi của mỗi máy trong bộ phần mềm. Đối với mỗi thông số liên
quan đến các ứng dụng dự kiến và phù hợp với yêu cầu của máy, danh mục
cho các đặc điểm tính toán và danh mục cho các tính năng kiến trúc của máy
đƣợc rút ra.
Giai đoạn 2: Bao gồm hai phần, mô tả nhiệm vụ và phân tích mẫu. Công
tác mô tả nhiệm vụ là phân tách các ứng dụng thành các nhiệm vụ (và nhiệm
vụ phụ), mỗi nhiệm vụ đó là tính toán đồng nhất. Các nhiệm vụ khác nhau
có thể có những nhu cầu tính toán khác nhau. Các yêu cầu tính toán cho từng
nhiệm vụ là xác định số lƣợng mã định hình và dữ liệu. Phân tích mẫu đƣợc

đồng nhất.
a. Giới thiệu
Phân công nhiệm vụ (sau đây gọi là TSAP) là một vấn đề quan trọng
trong hệ thống máy tính phân tán, có khả năng cung cấp, khai thác và cải
thiện hiệu quả tốt hơn các hệ thống xử lý song song [7,9]. Vấn đề phân
công nhiệm vụ nhƣ vậy hay còn gọi là sự tối ƣu hóa kết hợp, trong đó bao
gồm việc phân công một chƣơng trình máy tính với một số nhiệm vụ cho các
bộ vi xử lý thực hiện, với một tập các ràng buộc sao cho tối thiểu hóa một
hàm chi phí. Các ràng buộc của TSAP thƣờng liên quan đến các tài nguyên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-10- sẵn có, ứng dụng cho từng bộ vi xử lý trong hệ thống (số lƣợng nhiệm vụ mà
một bộ xử lý đƣợc cho là có thể xử lý, đƣợc giới hạn bởi chính các đặc tính
của nó, ví dụ nhƣ hạn chế về bộ nhớ để tránh quá tải hệ thống). Các hàm chi
phí cho TSAP có thể khác nhau tùy thuộc vào nhu cầu thiết kế, nhƣng nó
thƣờng liên quan đến việc tối thiểu hóa thời gian hoàn thành toàn bộ chƣơng
trình, giảm thiểu thời gian liên kết giữa các nhiệm vụ hoặc giảm tải cho bộ vi
xử lý.
TSAP có thể đƣợc định nghĩa nhƣ là 2 đồ thị liên kết một vấn đề và đã
đƣợc chứng minh là bài toán NP-đầy đủ. Có một số phƣơng pháp tiếp cận
vấn đề phân công nhiệm vụ trong các hệ thống máy tính phân tán nhƣng đặc
biệt quan trọng là các phƣơng pháp thử nghiệm và đánh giá dựa trên phân
tích toán học và lý thuyết đồ thị. Phần lớn các phƣơng pháp tiếp cận này đều
xem xét hai đồ thị trong định nghĩa TSAP. Đầu tiên là một đồ thị đơn mà mỗi
nút đại diện cho một nhiệm vụ, và mỗi cạnh giữa hai nút đại diện cho số
lƣợng thông tin kết nối của hai nhiệm vụ. Thứ hai là một đồ thị mạng trong đó
mỗi nút đại diện cho một máy tính và mỗi cạnh kết nối hai nút đại diện cho
chi phí liên kết giữa hai máy tính. Sử dụng hai đồ thị này, TSAP có thể đƣợc

,…w
N
}: Là số lƣợng tài nguyên
yêu cầu của nhiệm vụ T
i
. R = {r
1
,…r
M
}: Là nguồn tài nguyên tối đa có sẵn
cho một bộ xử lý P
i
nhất định. Sau đó nhiệm vụ T
i
có thể đƣợc giao cho vi xử
lý P
j
nếu và chỉ nếu tổng chi phí của tất cả các nhiệm vụ trƣớc đây đƣợc
giao cho P
j
xử lý cộng với W
i
mà ít hơn hoặc bằng so với khả năng tối đa
nguồn tài nguyên tƣơng ứng của các bộ vi xử lý P
j
, R
J
. Các tài nguyên cần cho
mỗi nhiệm vụ, cũng nhƣ các nguồn tài nguyên tối đa có sẵn cho một bộ xử
lý nhất định, phải đƣợc dự tính trƣớc để hạn chế sự quá tải của bộ vi xử lý.

 =1,2,,

=1
(1.2)
Lƣu ý rằng, ràng buộc đầu tiên từ công thức (1.1) cần đảm bảo rằng
mỗi công việc phải đƣợc kết hợp với một và chỉ một bộ xử lý, và ràng buộc
thứ hai từ công thức (1.2) cho thấy rằng các ràng buộc nguồn tài nguyên trên
mỗi bộ vi xử lý không thể bị vi phạm.
* Hàm chi phí
Hàm chi phí của TSAP dùng để tính việc giảm thiểu tối đa tổng thời gian
thực hiện và giảm thiểu thời gian kết nối giữa các nhiệm vụ khác nhau trong
bộ vi xử lý và gồm các nội dung sau:
(1) Tất cả các nhiệm vụ có thể đƣợc thực hiện trong tất cả các bộ vi xử
lý. Hai nhiệm vụ đang đƣợc thực hiện trong các bộ vi xử lý khác nhau sẽ phát
sinh một chi phí kết nối. Công việc này không tính đến chi phí kết nối giữa
các nhiệm vụ đang thực hiện trong cùng một bộ xử lý (xử lý giao tiếp nội bộ).
(2) Xác định một ma trận các chi phí kết nối K, với mỗi phần tử k
ijpq
đại
diện cho chi phí kết nối giữa một nhiệm vụ i đang thực hiện trong bộ vi xử
lý j và một nhiệm vụ p thực hiện trong một bộ xử lý q khác.
(3) Gọi v
j
gọi là tốc độ trung bình của bộ vi xử lý j tới bộ vi xử lý chậm
nhất trong hệ thống, gọi là tốc độ của bộ xử lý chậm nhất 1. Gọi t
i
là thời gian
thực hiện một nhiệm vụ i trên bộ xử lý chạy chậm nhất trong hệ thống.
Xác định 


=1
   
k
ijpq
x
ij
M
q=1
qj
N
p=1
M
j=1
N
i=1
x
pq
(1.3)
Trong đó 
1
, 
2
là hai tham số điều khiển tầm quan trọng cho từng
thành phần của hàm tính toán chi phí và 
1
+ 
2
= 1
1.2.2. Bài toán lập lịch thực hành
Phân lịch lý thuyế t và thƣ̣ c hà nh tại các trƣờng đại học là vấn đề mà các




= 100

=1
có nghĩa
là mỗi sinh viên phải đạt độ thích thú tối đa P vào một nhóm hoặc vài nhóm
mà họ đƣợc phân công, giá trị nhỏ cho các nhóm mà họ không thích.
Với các định nghĩa nhƣ trên , việ c phân công sinh viên và o nhóm đƣợc
phát biểu nhƣ sau (P1):
Tìm X sao cho:
max(


.


)
với ràng buộc





,
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-14-



=1






,
.
Chú ý rằng P1 chỉ dành cho sở thích của sinh viên, nên mộ t nhó m có thể
nhiề u sinh viên trong khi nhó m khá c chỉ có 1 sinh viên. P1 không có sự can
thiệ p củ a giá o viên, do vậ y trong P2 vấn đề này đƣợ c điề u chỉnh theo hàm s ố
thích nghi là m cân bằ ng số sinh viên trong mỗ i nhó m.
1.2.3. Bài toán lập lịch gia công
Mỗi một chi tiết trong số n chi tiết D
1,
D
2
,…,D
n
cần phải đƣợc lần lƣợt
gia công trên m máy M
1
, M
2
,…,M
m
. Thời gian gia công chi tiết D
i

,(+1)
1
=1
+


,()

=1

Trong đó: c
ij
= S
j
- S
i
; S
j
là thời điểm bắt đầu thực hiện việc gia công chi
tiết j (i,j = 1,2,…,n). Ý nghĩa của hệ số c
ij
có thể giải thích nhƣ sau: nó là tổng
thời gian gián đoạn(đƣợc tính từ khi bắt đầu gia công chi tiết i) gây ra bởi chi
tiết j khi nó đƣợc gia công sau chi tiết i trong lịch gia công. Vì vậy c
ij
có thể
đƣợc tính theo công thức:
c
ij
= max [

MẠNG NƠ RON VÀ GIẢI THUẬT DI TRUYỀN GIẢI
BÀI TOÁN TRONG HỆ THỐNG TÍNH TOÁN
KHÔNG ĐỒNG NHẤT

2.1. GIỚI THIỆU VỀ MẠNG NƠ -RON
2.1.1. Lịch sử phát triển
Quá trình nghiên cứu và phát triển mạng nơ-ron nhân tạo có thể chia
thành bốn giai đoạn nhƣ sau:
+ Giai đoạn một: Có thể tính từ nghiên cứu của William (1890) về tâm lý
học với sự liên kết các nơ-ron thần kinh. Năm 1940, MeCulloch và Pitts đã
cho biết: nơ-ron có thể đƣợc mô hình hoá nhƣ thiết bị ngƣỡng (giới hạn) để
thực hiện các phép tính logic và mô hình mạng nơ-ron của Mc Culloch-Pitts
cùng với giải thuật huấn luyện mạng của Hebb ra đời năm 1943.
+ Giai đoạn hai: Vào khoảng gần những năm 1960, một số mô hình nơ-
ron hoàn thiện hơn đã đƣợc đƣa ra nhƣ: mô hình Perceptron của Rosenblatt
(1958), Adaline của Widrow (1962).
+ Giai đoạn ba: Có thể tính vào khoảng đầu thập niên 80. Những đóng
góp lớn cho mạng nơ-ron trong giai đoạn này phải kể đến Grossberg,
Kohonen, Rumelhart và Hopfield. Trong đó đóng góp lớn của Hopfield gồm
hai mạng phản hồi: mạng rời rạc năm 1982 và mạng liên tục năm 1984. Đặc
biệt, ông đã dự kiến nhiều khả năng tính toán lớn của mạng mà một nơ-ron
không có khả năng đó.
+ Giai đoạn bốn: Tính từ năm 1987 đến nay, hàng năm thế giới đều mở
hội nghị toàn cầu chuyên ngành nơ-ron IJCNN (International Joint
Conference on Neural Networks). Rất nhiều công trình đƣợc nghiên cứu để ứng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-17- dụng mạng nơ-ron vào các lĩnh vực, ví dụ nhƣ: kỹ thuật tính, tối ƣu, sinh học, y

kinh ( Đầu Vào)
Nhân
Tế bào
Trục
Đầu ra
Hình 2.1. Mô hình nơ ron sinh học
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-18- Mỗi nơ-ron nhận tín hiệu vào từ các tế bào thần kinh khác. Chúng tích
hợp các tín hiệu vào, khi tổng tín hiệu vƣợt quá một ngƣỡng nào đó chúng tạo
tín hiệu ra và gửi tín hiệu này tới các nơ-ron khác thông qua dây thần kinh.
Các nơ-ron liên kết với nhau thành mạng. Mức độ bền vững của các liên kết
này xác định một hệ số gọi là trọng số liên kết.
2.1.2.2. Nơ-ron nhân tạo
+ Trọng số và tổng tín hiệu đầu vào:
Mô phỏng nơ-ron sinh học, ta có nơ-ron nhân tạo. Mỗi nơ-ron có rất
nhiều dây thần kinh vào, nghĩa là mỗi nơ-ron có thể tiếp nhận đồng thời nhiều
tín hiệu. Giả sử tại nơ-ron i có N tín hiệu vào, mỗi tín hiệu vào

đƣợc gán
một trọng số tƣơng ứng. Ta có thể ƣớc lƣợng tổng tín hiệu đi vào nơ-ron
i
net
theo một số dạng sau:
(i) Dạng tuyến tính:
, (2.1)
(ii) Dạng toàn phƣơng:
, (2.2)

1
2




N
j
ijji
wsnet

 
Njw
ij
,1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
-19- + Hàm kích hoạt
Hàm biến đổi tín hiệu đầu vào net cho tín hiệu đầu ra out đƣợc gọi là
hàm kích hoạt. Hàm này có đặc điểm là không âm và bị chặn. Có nhiều dạng
hàm kích hoạt, ngƣời ta thƣờng sử dụng một hàm kích hoạt chung cho toàn
mạng.
Một số hàm kích hoạt thƣờng đƣợc sử dụng:
(i) Hàm McCuloch-Pitts:
 




netf
LTPnet
UTPnet
netfout 0
1
(2.5)
ở đây UTP>LTP. Trong đó:
UTP là ngƣỡng trên (Upper Trip Point).
LTP là ngƣỡng dƣới (Lower Trip Point).
(iii) Hàm Sigmoid:
 
 




net
e
netfout
1
1
, (2.6)
trong đó > 0 là hằng số xác định độ nghiêng của hàm.
 Nút bias:
Là một nút thêm vào nhằm tăng khả năng thích nghi của mạng nơ-ron
trong quá trình học. Trong các mạng nơ-ron có sử dụng bias, mỗi nơ-ron có
thể có một trọng số tƣơng ứng với bias. Trong số này luôn có giá trị là 1.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn