ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

TIỂU LUẬN MÔN
TÍNH TOÁN LƯỚI
Tên đề tài:
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ
DỤNG GENETIC ALGORITHM
Giáo viên HD : PGS. TS. Nguyễn Phi Khứ
Họ tên học viên : Nguyễn Trọng Ngân
Mã số học viên : CH1101107
Cao học : Khóa 6
Chuyên ngành : Khoa học máy tính - Mã số: 60.48.01
Tháng 07/2013
LỜI CÁM ƠN
LỜI CÁM ƠN
Trong quá trình thực hiện bài tiểu luận, với sự hướng dẫn nhiệt tình của thầy
Nguyễn Phi Khứ và những ý kiến đóng góp của bạn bè đã cho em nguồn động viên lớn
để hoàn thành nhiệm vụ của bài tiểu luận. Qua đó, bản thân đã đạt được nhiều tiến bộ về
kiến thức và hoạch định được hướng nghiên cứu, tìm hiểu để phát triển các kỹ năng, kiến
thức trong tương lai.
Em chân thành cám ơn quý Thầy Cô trong khoa Khoa học máy tính, phòng đào tạo
sau đại học, trường đại học Công nghệ thông tin – đại học Quốc gia TP. Hồ Chí Minh đã
tận tình giảng dạy, hướng dẫn, giúp đỡ và tạo điều kiện cho em thực hiện tiểu luận này.
Mặc dù rất cố gắng, song tiểu luận vẫn còn nhiều thiếu sót. Em mong nhận được
nhiều sự thông cảm và góp ý của thầy.
Xin chân thành gửi lời cám ơn sâu sắc đến quý thầy.
Tp.Hồ Chí Minh, ngày /03 / 2013
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
NHẬN XÉT CỦA GIẢNG VIÊN
NHẬN XÉT CỦA GIẢNG VIÊN

LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
MỤC LỤC 4
MỤC LỤC
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
DANH MỤC CÁC HÌNH 5
DANH MỤC CÁC HÌNH
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 1- GIỚI THIỆU CHUNG 6
1. CHƯƠNG 1 – GIỚI THIỆU CHUNG
1.1. Thông tin chung về môn học
Môn học Tính toán lưới với thời lượng 45 tiết. Đây là một môn học thuộc dạng tự
chọn trong nội dung chương trình khung đào tạo cao học tại trường đại học Công nghệ
thông tin. Môn học cung cấp cho học viên các kiến thức về các phương pháp tính toán
trên hệ thống điện toán lưới và hệ thống điện toán đám mây. Ngoài ra, môn học còn giới
thiệu các công nghệ, ứng dụng đang được sử dụng rộng rãi trên thế giới trong các lĩnh vực

này.
1.2. Giới thiệu về đề tài tiểu luận và lý do chọn đề tài
Trong ngành khoa học máy tính nói chung và lĩnh vực trí tuệ nhân tạo nói riêng, tìm
kiếm lời giải tối ưu cho các bài toán là vấn đề được các nhà khoa học máy tính đặc biệt rất
quan tâm. Mục đích chính của các thuật toán tìm kiếm lời giải là tìm ra lời giải tối ưu nhất
cho bài toán trong thời gian nhỏ nhất. Các thuật toán như tìm kiếm không có thông tin /
vét cạn ( tìm kiếm trên danh sách, trên cây hoặc đồ thị ) sử dụng phương pháp đơn giản
nhất và trực quan nhất hoặc các thuật toán tìm kiếm có thông tin sử dụng heurictics để áp
dụng các tri thức về cấu trúc của không gian tìm kiếm nhằm giảm thời gian cần thiết cho
việc tìm kiếm được sử dụng nhiều nhưng chỉ với không gian tìm kiếm nhỏ và không hiệu
quả khi tìm kiếm trong không gian tìm kiếm lớn.
Tuy nhiên, trong thực tiễn có rất nhiều bài toán với không gian giả thuyết rất lớn và
việc tìm kiếm lời giải theo phương pháp vét cạn không thể thực hiện được trên không
gian tìm kiếm rất lớn cần phải giải quyết, đặc biệt trong lĩnh vực tính toán lưới. Việc tìm
giải pháp để giúp cân bằng, chia sẽ tải giữa các node trong tính toán lưới là một vấn đề
khó và Giải thuật di truyền là phương án để giúp cân bằng tải giữa các node khi tính toán.
Vì vậy, trong bài tiểu luận này, em sẽ tìm hiểu các đặc điểm của tính toán lưới và việc áp
dụng giải thuật di truyền để giải quyết bài toán cân bằng tải trong tính toán lưới.
1.3. Mục tiêu nghiên cứu
Bài tiểu luận này sẽ tập trung vào các vấn đề như sau:
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 1- GIỚI THIỆU CHUNG 7
- Tìm hiểu cơ chế hoạt động của giải thuật di truyền.
- Tìm hiểu cơ sở lý thuyết về tính toán lưới;
- Tìm hiểu về cơ sở toán học di truyền và ứng dụng trong việc xử lý các bài toàn tối
ưu;
- Tìm hiểu về ứng dụng giải thuật load balancing trên tính toán lưới.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 8
2. CHƯƠNG 2 - CƠ SỞ LÝ THUYẾT

2.1. Tổng quan về tính toán lưới
2.1.1. Giới thiệu về tính toán lưới
Thuật ngữ grid computing ban đầu do tác giả Ian Foster thuộc Phòng thí nghiệm
quốc gia Argonne (Mỹ) nêu ra vào cuối thập kỷ trước. Ian Foster đưa ra 3 tiêu chuẩn của
một lưới tính toán:
1. Không điều khiển tập chung mà phân tán theo địa lý
2. Sử dụng các giao thức tổng quát, mở và chuẩn hóa
3. Nhiều máy tính kết hợp tạo nên những dịch vụ tích hợp chất lượng cao (High
Qos)
Tuy nhiên, 3 tiêu trên được đưa ra trong thời điểm mới khai sinh ra Grid và từ đó
đến nay đã có nhiều thay đổi. Định nghĩa thế nào là một Grid vẫn là vấn đề gây tranh cãi.
Ian Foster đã định nghĩa Grid như sau:
“Grid là một loại hệ thống song song, phân tán cho phép chia sẻ, lựa chọn, kết hợp
các tài nguyên phân tán theo địa lý, thuộc nhiều tổ chức khác nhau dựa trên tính sẵn sàng,
khả năng, chi phí của chúng và yêu cầu về chất lượng dịch vụ (QoS) của người dùng để
giải quyết các bài toán, ứng dụng có quy mô lớn trong khoa học, kỹ thuật và thương mại.
Từ đó hình thành nên các “tổ chức ảo” (Virtual Organization (VO)), các liên minh tạm
thời giữa các tổ chức và tập đoàn, liên kết với nhau để chia sẻ tài nguyên và/hoặc kỹ năng
nhằm đáp ứng tốt hơn các cơ hội kinh doanh hoặc các dự án có nhu cầu lớn về tính toán
và dữ liệu, toàn bộ việc liên minh này dựa trên các mạng máy tính”
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 9
Hình 2-1 Mô hình Grid Computing
2.1.2. Các đặc trưng của Grid
1. Có sự kết hợp, chia sẻ các tài nguyên không được quản lý tập trung
Grid kết hợp và phân phối tài nguyên, người dùng thuộc nhiều vùng quản lý khác
nhau, nhiều đơn vị khác nhau trong một hay nhiều tổ chức khác nhau. Công nghệ Grid
tập trung giải quyết các vấn đề về bảo mật, chính sách quản trị, chi phí, thành viên,… nảy
sinh trong quá trình chia sẻ và sử dụng tài nguyên.
2. Sử dụng các giao diện và giao thức chuẩn, mang tính mở, đa dụng.

Grid được xây dựng trên các giao thức và giao diện tổng quát, đa dạng để giải quyết
các vấn đề cơ bản như chứng thực người dùng, phân quyền, tìm kiếm và truy xuất tài
nguyên.
3. Đáp ứng yêu cầu cao về chất lượng dịch vụ.
Grid cho phép sử dụng phối hợp các tài nguyên để cung cấp nhiều loại dịch vụ với
các mức chất lượng khác nhau như thời gian đáp ứng, hiệu suất, tính sẵn sàng, bảo mật,
cho phép kết hợp nhiều kiểu tài nguyên để đáp ứng nhu cầu phức tạp của người dùng.
Mục tiêu phối hợp để khả năng của hệ thống sau khi kết hợp lớn hơn tổng khả năng của
từng đơn vị cấu thành nên Grid.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 10
2.1.3. Các tài nguyên của Grid
2.1.3.1 Tài nguyên tính toán
Đây là tài nguyên phổ biến nhất gồm các chu kỳ tính toán (computing cycles) được
cung cấp bởi bộ vi xử lý của các thiết bị trong Grid. Các bộ vi xử lý có thể có tốc độ, kiến
trúc, chạy phần mềm khác nhau.
Có 3 cách để khai thác tài nguyên tính toán của Grid:
1. Chạy các ứng dụng hiện có trên một node của Grid thay vì chạy trên máy tính cục
bộ.
2. Thiết kế ứng dụng, tách các công việc thành các phần riêng lẽ để có thể thực thi
song song trên nhiều bộ xử lý khác nhau.
3. Chạy ứng dụng thực thi nhiều lần trên nhiều node khác nhau trong Grid.
2.1.3.2 Tài nguyên lưu trữ
Tài nguyên phổ biến khác trong Grid là tài nguyên lưu trữ. Mỗi thiết bị trong Grid
thường cung cấp một số dung lượng lưu trữ phục vụ cho việc thực thi ứng dụng trên Grid.
Tài nguyên lưu trữ có thể là bộ nhớ trong, ổ đĩa cứng hoặc các thiết bị lưu trữ khác. Bộ
nhớ trong thường dùng để lưu trữ dữ liệu tạm thời cho ứng dụng, trong khi các thiết bị lưu
trữ ngoài có thể được sử dụng để tăng không gian lưu trữ, tăng hiệu suất, khả năng chia sẻ
và đảm bảo tính tin cậy của dữ liệu.
2.1.3.3 Phương tiện liên lạc

Ở đây bao gồm việc liên lạc, trao đổi dữ liệu giữa các thành phần trong Grid và giao
tiếp giữa Grid với bên ngoài. Một số công việc đòi hỏi một lượng dữ liệu lớn nhưng các
dữ liệu này thường không nằm trên máy đang thực thi công việc. Khả năng về băng thông
trong những trường hợp như vậy là một tài nguyên then chốt, ảnh hưởng đến khả năng
của Grid. Việc giao tiếp với bên ngoài được thực hiện thông qua mạng Internet. Grid có
thể sử dụng các kết nối Internet để liên lạc giữa các node. Vì các kết nối này không chia
sẻ một đường truyền nên làm tăng băng thông truy cập Internet. Các đường truyền dự
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 11
phòng đôi khi cần thiết để giải quyết tốt hơn các vấn đề về hư hỏng mạng và truyền dữ
liệu lớn.
2.1.3.4 Phần mềm, ứng dụng
Grid các phần mềm mà có thể không yêu cầu phải cài đặt trên tất cả mọi máy tính
trong Grid. Các phần mềm này chỉ cần được cài trên một số node. Thông qua Grid, khi
một công việc cần đến chúng, nó sẽ gửi dữ liệu đến node đã được cài đặt phần mềm và
cho thực thi. Đây có thể là một giải pháp tốt để tiết kiệm chi phí về bản quyền phần mềm.
2.1.4. Phân loại Grid
2.1.4.1 Grid tính toán (computational grid)
Loại Grid này tập trung chủ yếu vào việc sử dụng năng lực tính toán. Ở dạng này,
phần lớn các node là các máy tính hay các nhóm máy tính(cluster) có năng lực xử lý, tính
toán rất lớn thông qua việc chia tác vụ tính toán lớn thành nhiều công việc nhỏ thực thi
song song trên các node của Grid. Việc phân tán các tác vụ tính toán trong Grid sẽ làm
giảm rất đáng kể toàn bộ thời gian xử lý và tăng khả năng tận dụng hệ thống.
Thông thường một hệ thống chính sẽ chia khối dữ liệu cần xử lý thành các phần
nhỏ, sau đó phân phối đến các node trên Grid. Mỗi node sẽ thực hiện xử lý dữ liệu và trả
kết quả về hệ thống chính để hệ này tổng hợp và trình diễn kết quả toàn cục cho người
dùng.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 12
Hình 2-2 Mô hình Grid tính toán

2.1.4.2 Grid dữ liệu (data grid)
Một Grid Dữ liệu chịu trách nhiệm lưu trữ và cung cấp khả năng truy cập dữ liệu
cho nhiều tổ chức khác nhau. Người dùng không cần biết chính xác vị trí dữ liệu khi thao
tác với dữ liệu. Các cơ sở dữ liệu, đặc biệt các cơ sở dữ liệu liên hợp đóng vai trò quan
trọng trong các Grid Dữ liệu, nhất là khi có nhiều nguồn dữ liệu và xuất hiện nhu cầu kết
hợp các thông tin từ các nguồn dữ liệu này.
Các Grid Dữ liệu có thể được sử dụng trong lĩnh vực khai mỏ dữ liệu(data mining)
hoặc các hệ thống thương mại thông minh.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 13
Hình 2-3 Mô hình Data Grid
2.1.4.3 Scavenging Grid
Một Scavenging Grid thường được dùng với một lượng lớn các máy tính để bàn.
Các máy tính thường được kiểm tra định kỳ để xem khi nào bộ xử lý và các tài nguyên
khác rảnh rỗi để thực hiện các tác vụ Grid. Chủ nhân của máy để bàn thường có quyền
xác định khi nào thì chia sẻ chiếc máy của mình.
2.1.5. Một số lợi ích của Grid
2.1.5.1 Khai thác, tận dụng các tài nguyên nhàn rỗi
Hầu hết các tổ chức đều có một lượng lớn các tài nguyên tính toán nhàn rỗi, các máy
tính cá nhân thường chỉ sử dụng hết 5% thời gian xử lý CPU, ngay cả các server cũng
thường “rảnh rỗi”. Grid có thể tối ưu sử dụng các tài nguyên nhàn rỗi này theo nhiều cách
khác nhau và cân bằng sử dụng tài nguyên. Một tổ chức thường gặp các vấn đề khó khăn
khi các hoạt động đòi hỏi thêm nhiều tài nguyên hơn. Với Grid, có thể chuyển hoạt động
đến các tài nguyên nhàn rỗi khác, hoặc có thể thêm các tài nguyên mới một cách dễ dàng,
từ đó làm tăng khả năng chịu đựng của hệ thống.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 14
2.1.5.2 Sử dụng CPU song song
Khả năng sử dụng các CPU song song là một đặc tính tuyệt vời của Grid, ngoài việc
hỗ trợ các nhu cầu tính toán của các nhà khoa học, sức mạnh tính toán do Grid cung cấp

có thể giúp giải quyết các bài toán đòi hỏi năng lực xử lý lớn trong các ngành khác như y
dược, tính toán tài chính, kinh tế, khai thác dầu hỏa, dự báo thời tiết, công nghiệp vũ trụ,
thiết kế sản phẩm, … và rất nhiều lĩnh vực khác.
2.1.5.3 Cho phép hợp tác trên toàn thế giới
Một trong những đóng góp quan trọng của công nghệ Grid Computing là cho phép
và đơn giản hoá hợp tác chia sẻ, làm việc giữa một cộng đồng rộng lớn trên toàn thế giới.
Grid cho phép mở rộng trên phạm vi toàn cầu khi đưa ra những chuẩn quan trọng cho
phép các hệ thống không đồng dạng làm việc chung với nhau để tạo nên một hệ thống
tính toán ảo cung cấp rất nhiều dạng tài nguyên khác nhau.
2.1.5.4 Cho phép chia sẻ, sử dụng tất cả các loại tài nguyên
Grid có thể cho phép chia sẻ tất cả các loại tài nguyên mà trước đây chưa được chia
sẻ như băng thông mạng, các thiết bị đặc biệt, phần mềm, bản quyền, các dịch vụ,…
2.1.5.5 Tăng tính tin cậy cho các hệ thống máy tính.
Hiện nay, các hệ thống tính toán sử dụng các phần cứng chuyên dụng, với chi phí
cao để tăng độ tin cậy. Các giải pháp này làm tăng độ tin cậy của hệ thống, tuy nhiên với
chi quá đắt khi phụ kiện đi kèm cũng phải nhân lên. Các hướng tiếp cận mới để giải quyết
vấn đề độ tin cậy dựa nhiều hơn vào các công nghệ phần mềm hơn là các phần cứng đắt
tiền. Grid là sự khởi đầu cho các công nghệ đó. Các hệ thống trong Grid thường có chi
phí thấp và phân tán theo địa lý. Do đó, nếu có sự cố về nguồn điện hay các lỗi hệ thống
khác tại một vị trí, toàn bộ phần còn lại không bị ảnh hưởng. Các phần mềm quản trị Grid
có khả năng thực thi lại công việc trên một node khác khi phát hiện có lỗi hệ thống. Nếu
quan trọng hơn nữa, trong các hệ thống theo thời gian thực, nhiều bản dự phòng của các
các công việc quan trọng có thể được chạy trên nhiều máy tính khác nhau trong Grid để
đảm bảo độ tin cậy tối đa.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 15
2.1.5.6 Tăng khả năng quản trị các hệ thống
Mục tiêu ảo hoá tất cả các tài nguyên và cung cấp giao diện quản lý đơn nhất các hệ
thống hỗn tạp đem lại những cơ hội mới để quản trị tốt hơn trong các cơ sở hạ tầng công
nghệ thông tin lớn, phân tán.

2.2. Giải thuật di truyền
Giải thuật di truyền (Genetic Algorithm) là kỹ thuật chung giúp giải quyết vấn đề-
bài toán bằng cách mô phỏng sự tiến hóa của con người hay của sinh vật nói chung (dựa
trên thuyết tiến hóa muôn loài của Darwin) trong điều kiện qui định sẵn của môi trường.
Giải thuật di truyền là một thuật giải và mục tiêu của Giải thuật di truyền không nhằm đưa
ra lời giải chính xác tối ưu mà là đưa ra lời giải tương đối tối ưu.
Sự phổ biến của Giải thuật di truyền được thúc đẩy bởi các yếu tố sau:
- Tiến hóa là một phương pháp mạnh, thành công cho sự thích nghi bên trong các hệ
thống sinh học.
- Giải thuật di truyền có thể tìm kiếm trên các không gian giả thuyết có các phần
tương tác phức tạp, ở đó ảnh hưởng của mỗi phần lên toàn thể độ thích nghi giả thuyết
khó có thể mô hình.
- Giải thuật di truyền có thể được thực hiện song song và có thể tận dụng thành tựu
của phần cứng máy tính mạnh.
Do các thế mạnh này, trong bài tiểu luận em đề cập tới việc giải thuật di truyền để
tính toán việc cân bằng tải giữa các node trong grid tính toán (Computational Grid).
2.2.1. Xác định tính thích nghi của cá thể
2.2.1.1 Hàm mục tiêu
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à 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ể đó. Trong bài toán tìm cực đại thì giá trị trả ra càng
lớn thì cá thể càng tốt. Ngược lại, đố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.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 16
2.2.1.2 Độ thích nghi tiêu chuẩn
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ể tính theo độ thích nghi tiêu chuẩn:
2.2.1.3 Độ thích nghi xếp hạng
Cách tính độ thích nghi tiêu chuẩn như trên chỉ thực sự hiệu quả đối với những quần

thể có độ tốt tương đối đồng đều giữa các cá thể. Vì một lý do nào đó – có thể do chọn
hàm mục tiêu không tốt - có một cá thể có độ tốt quá cao và tách biệt hẳn các cá thể còn
lại thì các cá thể của thế hệ sau sẽ bị “hút” về phía cá thể đặc biệt đó. Do đó, sẽ làm giảm
khả năng di truyền đến thế sau của các cá thể xấu, tạo nên hiện tượng di truyền cục bộ, từ
đó có thể làm giảm khả năng dẫn đến lời giải tốt nhất.
Phương pháp xác định độ thích nghi xếp hạng không làm việc trên giá trị độ lớn của
hàm mục tiêu G mà chỉ làm việc dựa trên thứ tự của các cá thể trên quần thể sau khi đã
sắp xếp các thể theo giá trị hàm mục tiêu G. Phương pháp xác định độ thích nghi xếp
hạng sẽ linh động đặt một trọng số để xác định sự tập trung của độ thích nghi lên các cá
thể có độ tốt cao, mà vẫn luôn đảm bảo được quy luật: cá thể có độ thích nghi càng cao
thì xác suất được tồn tại và di truyền càng cao.
Độ thích nghi (hay xác suất được chọn) của cá thể thứ i được tính theo công thức
sau:
Trong đó: p là một hằng số trong khoảng [0,1] và có thể cân chỉnh để xác định độ
hút của cá thể phục vụ công tác lựa chọn cá thể để di truyền sang thế hệ sau. Hình sau sẽ
minh họa việc thay đổi độ hút của cá thể khi tiến hành điều chỉnh hệ số p.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 17
Hình 2-4 Mô tả độ thích nghi xếp hạng
2.2.2. Chọn lọc cá thể
Trong giải thuật di truyền có rất nhiều phương án chọn lọc cá thể như chọn lọc theo
kiểu xén, chọn lọc theo kiểu rải, chọn lọc theo bàn xoay Roulete.
Đối với việc lựa chọn các cá thể trong bài tiểu luận, có thể áp dụng phương pháp
lựa chọn theo bàn xoay Roulete.
Hình 2-5 Mô hình vòng xoay Roulete
Theo mô hình trên, cá thể có độ thích nghi cao nhất sẽ chiếm 1 đoạn là 0,5. Cá thể
tiếp theo sẽ chiếm 1 đoạn là 0,25…. Ta sẽ phát sinh một số ngẫu nhiên trong khoảng
[0,1]. Nếu rơi vào đoạn nào trong hình, cá thể tương ứng sẽ được chọn.
2.2.3. Lai ghép 2 cá thể
2.2.3.1 Lai ghép đơn điểm

Lai ghép đơn điểm là dạng lai ghép đơn giản nhất, có thể áp dụng đối với nhiều kiểu
dữ liệu Gen khác nhau.
Phương pháp lai ghép đơn điểm sẽ được trong bài tiểu luận để tạo ra các con. Để
thực hiện được phương pháp lai ghép này, ta tiến hành lựa chọn ra 2 cá thể bố, mẹ bằng
phương pháp chọn lọc Roulete trong quần thể.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 18

Hình 2-6 Ví dụ về lai ghép đơn điểm hai nhiễm sắc thể dạng tế bào FAT trong
phân bố mảnh CSDL phân tán
2.2.3.2 Các phương pháp lai ghép khác
Ngoài phương pháp lai ghép đơn điểm, còn có phương pháp lai ghép đa điểm, lai
ghép mặt nạ…
Lai ghép đa điểm là dạng tổng quát hơn so với lai ghép đơn điểm. Ta sẽ tiến hành
chọn nhiều điểm trên Gen bố mẹ tiến hành trao đổi dữ liệu cho nhau để tạo ra các con.
Lai ghép mặt nạ là hình thức tổng quát nhất của lai ghép. Trong lai ghép mặt nạ, liên
kết với bố mẹ là hai mặt nạ có chiều dài Gen tương đương và được phát sinh ngẫu nhiên.
Giá trị bit của mặt nạ sẽ quyết dịnh thành phần Gen của con được trích ra từ bố mẹ.
2.2.4. Đột biến cá thể
Đối với kiểu cấu trúc dữ liệu Gen đang đề cập trong bài tiểu luận, việc đột biến cá
thể chỉ đơn giản là đổi giá trị bít nhị phân ngẫu nhiên (01 và 10) trong Gen.
Thông thường thì đột biến diễn ra với xác suất thấp(xác suất đột biến). Vì vậy đột
biến chỉ diễn ra tối đa ở trên một thành phần Gen là tối đa.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 2- CƠ SỞ LÝ THUYẾT 19
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 3 – LOAD BALANCING TRONG CG SỬ DỤNG GA 20
3. CHƯƠNG 3 – LOAD BALANCING TRONG TÍNH TOÁN
LƯỚI SỬ DỤNG GENETIC ALGORITHM
3.1. Giới thiệu sơ lược

Grid tính toán (CG) là một tập hợp của phần cứng và các nguồn tài nguyên phần
mềm được cung cấp tin cậy, nhất quán và phổ biến với chi phí thấp để phục vụ các yêu
cầu tính toán cao cấp. Người dùng khi sử dụng Grid tính toán sẽ gửi các yêu cầu tính toán
và các yêu cầu này sẽ được đăng ký để tìm kiếm các tài nguyên thích hợp tiến hành xử lý.
Tùy thuộc vào các chính sách thực hiện, các yêu cầu được sắp xếp vào một trong những
nguồn tài nguyên thích hợp. Thông thường, vấn đề này được xử lý theo hai dạng song
song hạt mịn nếu các công việc phụ của nó giao tiếp nhiều lần mỗi giây; song song hạt
thô nếu chúng kết nối nhiều lần mỗi giây. Trong khi thực hiện công việc trong khoảng
thời gian, các node của Grid trở nên rất mất cân bằng có thể dẫn đến việc mỗi
suy thoái quả hoạt động của toàn hệ thống Grid. Để giữ cho hệ thống hoạt động ổn định,
vấn đề cân bằng giữa các node trở nên quan trọng. Giải thuật di truyền (Genetic
Algorithm) sẽ được sử dụng để giải quyết vấn đề cân bằng tải trên Grid tính toán.
3.2. Áp dụng giải thuật di truyền giải quyết vấn đề cân bằng tải
3.2.1. Hàm mục tiêu
Hàm mục tiêu có nguồn gốc dựa trên sự thay đổi tải trong mỗi nút trên môi trường
tính toán lưới. Trong môi trường lý tưởng như khi tải được phân bố đều giữa các node,
biến động về tải giữa các node gần như bằng không. Tuy nhiên, thông số này thường biến
động rất nhiều trong thực tế. Do đó, thông số này phải được giảm thiểu đến mức tối đa.
Để tính toán tải sự thay đổi tải giữa các nút lưới, phải tính được tải trung bình giữa các
node. Đây là thông số cần thiết để tính toán tổng tải trên lưới. Tải trên các node được tính
toán dựa trên kích thước của các mô-đun tác vụ. Tải trọng trung bình trên lưới (ký hiệu là
W
avg)
, có thể được tính thông qua tổng tải (ký hiệu là W
total
) và số lượng node trên lưới
( ký hiệu là m).
Tại node thứ i, tải sẽ được tính thông qua công thức: . Với r là số lượng các module
được phân bố trên node thứ I, là kích module.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM

CHƯƠNG 3 – LOAD BALANCING TRONG CG SỬ DỤNG GA 21
Với m node, tổng tải được tính
Tải trung bình trên toàn lưới sẽ được tính:
Hàm mục tiêu sẽ được tính là: với là tải tại node thứ j.
3.2.2. Mô hình
Mô hình đề xuất sử dụng thuật giải di truyền(GA) để giảm thiểu thông số biến động
về tải để đạt được trạng thái cân bằng tải tốt hơn. Giải thuật di truyền cho mô hình cân
bằng tải thì sẽ có một số điểm khác biệt tương ứng với những module cụ thể.
Cấu trúc nhiễm sắc thể đề xuất:
Struct chromosome {task[]; machine ;};
Cấu trúc của task và machine như sau:
Struct task {int task_ no; double task size ;} task;
Struct machine {int machine no; double machine ;} ma-chine;
Khởi tạo quần thể ban đầu: Khởi tạo một số lượng các chromosome để hình thành
nên quần thể ban đầu. Các chromosome được tạo ra một cách ngẫu nhiên dựa trên phép
hoán vị ngẫu nhiên.
Lai ghép và đột biến: Hai con được tạo ra từ việc lai ghép hai nhiễm sắc thể bố và
mẹ. Việc lai ghép này được sử dụng dựa trên cơ chế lai ghép mặt nạ đã trình bày ở phần
trên. Xác xuất lai ghép được sử dụng ở đây là 0,95. Cơ chế đột biến được sử dụng theo
cách thay đổi ngẫu nhiên 1 vị trí nào đó trong nhiễm sắc thể với xác xuất đột biến là 0,05.
Lựa chọn cho thế hệ tiếp: Việc lựa chọn các nhiễm sắc thể tốt cho các thế hệ sau
được thực hiện dựa trên sự sắp xếp trong quần thể ban đầu với các giá trị hàm mục tiêu
tương ứng nhằm đảm bảo các nhiễm sắc thể xấu bị loại bỏ.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 3 – LOAD BALANCING TRONG CG SỬ DỤNG GA 22
3.2.3. Thuật toán
Hình 3-7 Lược đồ tổng quát của thuật toán
Thuật toán cài đặt như sau:
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 3 – LOAD BALANCING TRONG CG SỬ DỤNG GA 23

Load Balancing Algorithm ( )
{
Tạo ngẫu nhiên quần thể ban đầu (old population)
Đánh giá độ thích nghi và sắp xếp quần thể theo giá trị độ thích nghi
tăng dần.
Lựa chọn một nữa các nhiễm sắc thể tốt nhất trong quần thể đầu
Tạo các nhiễm sắc thể quần thể mới từ quần thể đầu
For (i=1; i<=no_of_generations; i++)
{
Lựa chọn 2 bố mẹ;
Thực hiện lai ghép;
Thực hiện đột biến;
Lưu các con và quần thể mới
Đánh giá độ thích nghi
Sắp xếp quần thể theo giá trị độ thích nghi
Lưu trữ giá trị biến đổi thông số tải trên grid vào mảng
kết quả
Lựa chọn 1 nữa các nhiễm sắc thể trong quần thể mới, lưu
vào quần thể cũ.
} }
3.2.4. Kết quả thử nghiệm, đánh giá
Trong thí nghiệm này, tác giả của bài viết [2] đã xem xét vùng cố định các kích
thước của module là 100-200 MFLOPS. Số lượng các node lần lượt 20, 40, 50, 60, 80.100
với tổng tải trên lưới là 15.074 MFLOPS. Sự thay đổi tải (trong MFLOPS) được mô tả
trên trục Y tương ứng cho nhiều thế hệ (X-axis)
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM
CHƯƠNG 3 – LOAD BALANCING TRONG CG SỬ DỤNG GA 24
Hình 3-8 Thông số thay đổi tải di truyền qua các thế hệ với số node 20-50
Hình 3-9 Thông số thay đổi tải di truyền qua các thế hệ với số node 60-100
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM

CHƯƠNG 4- TỔNG KẾT 25
4. CHƯƠNG 4 -TỔNG KẾT
4.1. Kết quả đối với bản thân
Trong bài thu hoạch này em thu được thu thập được nhiều kiến thức cũng như hoàn
thiện thêm nhiều kỹ năng làm việc.
- Về mặt công nghệ: Sau quá trình nghiên cứu giúp em tìm hiểu rõ hơn về các kỹ
thuật tìm kiếm lời khi có tập không gian giả thuyết lớn.
- Về mặt giải pháp: Tìm hiểu được giải pháp giúp cân bằng tải giữa các node trong
lưới tính toán, qua đó tiếp cận được giải pháp tối ưu hóa thông qua thuật toán di truyền.
4.2. Hạn chế và hướng phát triển
Hiện tại, bài báo liên quan đế vấn đề cân bằng tải đã công bố. Tuy nhiên khi tiến
hành tìm hiểu các kiến thức đã nêu trong bài báo em không được cài đặt để vận hành,
kiểm thử vì không tiếp cận được các hệ thống tính toán lưới. Do đó, hi vọng trong tương
lai về sau, nếu được tiếp cận em sẽ tiến hành kiểm thử các vấn đề đã trên.
LOAD BALANCING TRONG TÍNH TOÁN LƯỚI SỬ DỤNG GENETIC ALGORITHM