ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
NGUYỄN THỊ NGỌC NGÂN

NGUYỄN THỊ NGỌC NGÂN

*

Ư C Ư NG N
C PHÁT TRI N PH N
SỬ DỤNG THUẬT TOÁN TỐI ƯU
D A TRÊN HÀNH VI SĂN ỒI CỦA B Y SÓI

KHOA HỌC
ÁY TÍNH

UẬN VĂN THẠC SĨ KHOA HỌC
CHUYÊN NGÀNH KHOA HỌC

*
KHÓA K32

Đà Nẵng - Năm 2018

ÁY TÍNH


ĐẠI HỌC ĐÀ NẴNG
TRƢỜNG ĐẠI HỌC BÁCH KHOA
----------------------

NGUYỄN THỊ NGỌC NGÂN

Ƣ C Ƣ NG NỖ

C PHÁT TRIỂN PH N MỀM

SỬ DỤNG THUẬT TOÁN TỐI ƢU
D A TRÊN HÀNH VI SĂN MỒI CỦA B Y SÓI
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ

Ngƣời hƣớng dẫn khoa học: TS Lê Thị Mỹ Hạnh

ĐÀ NẴNG - Năm 2018


i

LỜI CAM ĐOAN

Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu
trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào
khác.

Tác giả

Nguyễn Thị Ngọc Ngân



ii

MỤC ỤC
MỞ ĐẦU ......................................................................................................................... 1
CHƢƠNG 1 TỔNG QUAN VỀ Ƣ C LƢ NG NỖ L C PHÁT TRIỂN PHẦN
MỀM THEO M H NH SHETA....................................................................................4
1.1. Tổng quan về ƣớc lƣợng nỗ lực phát triển phần mềm..........................................4
1.1.1. Khái niệm ......................................................................................................4
1.1.2. Bốn bƣớc cơ bản trong ƣớc lƣợng dự án phần mềm .....................................5
1.3. Mô hình ƣớc lƣợng nỗ lực phát triển phần mềm ................................................10
1.3.1. Mô hình COCOMO .....................................................................................11
1.3.2. Mô hình Sheta ..............................................................................................12
CHƢƠNG 2 THUẬT TOÁN TỐI ƢU D A TRÊN HÀNH VI SĂN MỒI CỦA BẦY
SÓI .................................................................................................................................13
2.1. Giới thiệu ............................................................................................................13
2.1.1. Bài toán tối ƣu tổng quát và phân loại .........................................................13
2.1.2. Trí tuệ bầy đàn .............................................................................................15
2.2. Mô tả hành vi săn mồi của bầy sói .....................................................................15
2.3. Chi tiết thuật toán ...............................................................................................16
2.3.1. Hệ thống phân cấp xã hội ............................................................................16
2.3.2. Bao vây con mồi ..........................................................................................17
2.3.3. Săn bắt con mồi ...........................................................................................18
2.3.4. Tấn công con mồi ........................................................................................19
2.3.5. Tìm kiếm con mồi (thăm dò) .......................................................................20
2.4. Cài đặt thuật toán ................................................................................................21
2.4.1. Biểu diễn bằng mã giả .................................................................................21
2.4.2. Lƣu đồ thuật toán.........................................................................................22
CHƢƠNG 3 ỨNG DỤNG THUẬT TOÁN VÀO Ƣ C LƢ NG NỖ L C PHÁT
TRIỂN PHẦN MỀM .....................................................................................................24

3.1. Giới thiệu ............................................................................................................24
3.1.1. iểu diễn c thể của thuật to n GWO và hàm th ch nghi cho bài to n dự
đo n .......................................................................................................................25
3.1.2. Đo lƣờng chất lƣợng dự đo n ......................................................................26
3.2. Kết quả và thực nghiệm ......................................................................................27
3.2.1. Tập dữ liệu thực nghiệm ..............................................................................27
3.2.2. Thiết lập thực nghiệm ..................................................................................28


iii
3.2.3. Đ nh gi kết quả ..........................................................................................28
3.3. Đ nh gi hiệu quả ƣớc lƣợng của mô hình Sheta sử dụng thuật toán tối ƣu dựa
trên hành vi săn mồi của bầy sói ...............................................................................33
KẾT LUẬN ................................................................................................................... 34
TÀI LIỆU THAM KHẢO ............................................................................................. 35


iv
Ƣ C Ƣ NG NỖ
C PHÁT TRIỂN PH N MỀM SỬ DỤNG THUẬT TOÁN
TỐI ƢU D A TRÊN HÀNH VI SĂN MỒI CỦA B Y SÓI
Học viên: Nguyễn Thị Ngọc Ngân. Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01. Khóa: 31. Trƣờng Đại học Bách khoa - ĐHĐN
Tóm tắt – Ƣớc lƣợng nỗ lực phát triển phần mềm là một vấn đề quan trọng đối với hầu hết
mọi ngƣời trong ngành công nghiệp phát triển phần mềm. Sự thành công hay thất bại của dự
án phụ thuộc rất lớn vào độ chính xác của kết quả ƣớc lƣợng nỗ lực và tiến độ thực hiện. Để
nâng cao tính chính xác của dự đo n, phƣơng ph p ƣớc lƣợng dựa trên các mô hình thuật toán
đã đƣợc sử dụng rộng rãi. Tuy nhiên, vấn đề đ nh gi ch nh x c nỗ lực là một vấn đề đầy
thách thức đối với các nhà nghiên cứu và việc khó khăn nhất là hiệu chuẩn các tham số.
Nghiên cứu này nhằm mục đ ch đề xuất thuật toán tối ƣu dựa trên hành vi săn mồi của bầy sói

(GWO – Grey Wolf Optimizer) để tối ƣu hóa c c thông số của công thức đã đƣợc đề xuất
trƣớc đó dựa trên nỗ lực thực tế trong quá khứ. Các kết quả chỉ ra rằng phƣơng ph p tiếp cận
của tôi đã vƣợt trội hơn c c phƣơng ph p trong c c nghiên cứu khác về tính chính xác của các
kết quả ƣớc lƣợng.
Từ khóa - Ƣớc lƣợng nỗ lực phát triển phần mềm; tối ƣu ho bầy đàn; thuật to n hành vi săn
mồi của bầy sói; thuật toán tối ƣu hóa; mô hình ƣớc lƣợng.

OPTIMIZING PARAMETERS OF SOFTWARE EFFORT ESTIMATION
USING GREY WOLF OPTIMIZER
Abstract – Software effort estimation has been an important issue for almost everyone in
software industry. The success or failure of projects depends greatly on the accuracy of effort
estimation and schedule results. To enhance the accuracy of predictions, estimation
approaches based on algorithmic models have been widely used. However, the question of
accurate estimation of effort has been a challenging issue with regards to researchers, and the
most difficult is to calibrate the parameters. This study aims to use a Grey Wolf Optimizer
(GWO) to optimize the parameters of the previously proposed estimation formula based on
past actual effort. The results indicated that our proposal outperformed methods in other
studies in terms of the accuracy of estimated results.
Key words - Software effort estimation; particle swarm optimization; Grey Wolf Optimizer
algorithm; swarm optimization algorithm; estimation models.


v

DANH MỤC CÁC TỪ VIẾT TẮT
Ký hiệu

Diễn giải

LOC


Line Of Code: Ứớc lƣợng kích cỡ của phần mềm đƣợc phát
triển theo số dòng lệnh

EP

Function Point: Ƣớc lƣợng kích cỡ của phần mềm đƣợc phát
triển theo chức năng, độ phức tạp

COCOMO Constructive Cost Model: Mô hình giá cấu thành
ME

Methodology: Phƣơng ph p luận để nâng cao chất lƣợng của
mô hình COCOMO

GWO

Grey Wolf Optimizer: thuật to n hành vi săn mồi của bầy sói

MMRE

Độ đo Mean Magnitude of Relative Error

MdMRE

Độ đo Median Magnitude of Relative Error

PRED (N)

Độ đo Prediction at level N



vi

DANH MỤC CÁC BẢNG BIỂU
Số hiệu
Tên bảng

Trang

bảng
3.1

Dữ liệu dự n phần mềm của NASA

27

3.2

Phạm vi các tham số của mô hình đề xuất

28

3.3

Gi trị nỗ lực ƣớc lƣợng và gi trị MRE của mô hình Sheta
1 và mô hình GWO 1

29


3.4

Gi trị nỗ lực ƣớc lƣợng và gi trị MRE của mô hình Sheta
2 và mô hình GWO 2

31

3.5

Kết quả của các mô hình dựa trên các tiêu chí

33


vii

DANH MỤC CÁC HÌNH VẼ
Số hiệu
hình vẽ

Tên hình vẽ

Trang

1.1

Đồ thị hội tụ ƣớc lƣợng

5


1.2

Tiến trình cơ sở ƣớc lƣợng dự án

9

2.1

Hệ thống phân cấp của sói xám

15

2.2

Hành vi săn bắt của sói

17

2.3

Các vị tr vectơ trong 2D, 3D và vị trí tiếp theo có thể có
của sói

18

2.4

Vị tr đƣợc cập nhật trong GWO

19


2.5

Tấn công con mồi và tìm kiếm con mồi

20

2.6

Lƣu đồ thuật toán

22

3.1

Sự hội tụ của GWO khi sử dụng hàm kiểm tra ngẫu nhiên
(F1) và (F10)

25

3.2

So sánh nỗ lực thực tế với nỗ lực ƣớc lƣợng mô hình
Sheta 1 và mô hình GWO 1

30

3.3

So sánh MRE của mô hình Sheta 1 và mô hình GWO 1


30

3.4

So sánh nỗ lực thực tế với nỗ lực ƣớc lƣợng mô hình
Sheta 2 và mô hình GWO 2

32

3.5

So sánh MRE của mô hình Sheta 2 và mô hình GWO 2

32


1

MỞ Đ U
1. Lý do chọn đề tài
Ƣớc lƣợng nỗ lực phát triển phần mềm hiệu quả là một trong những hoạt động
quan trọng của ƣớc lƣợng dự án phần mềm, đồng thời cũng là th ch thức trong công
nghệ phần mềm. Ƣớc lƣợng nỗ lực có thể đƣợc sử dụng nhƣ là dữ liệu đầu vào cho các
kế hoạch dự án, phân t ch đầu tƣ, nguồn ngân sách, quy trình định giá dự án nên nó trở
nên rất quan trọng để có đƣợc ƣớc lƣợng chính xác. Nhiều tổ chức phải chịu các tác
động tài chính lên công việc của họ, bị mất lợi thế cạnh tranh, và chậm trễ trong việc
hƣởng lợi từ kế hoạch và các sáng kiến do c c ƣớc lƣợng xấu. Ở giai đoạn phát triển
ban đầu, những hạn chế trong c c mô hình ƣớc lƣợng nỗ lực của các dự án phát triển
phần mềm là độ ch nh x c và độ chắc chắn chƣa cao.

Một số kỹ thuật ƣớc lƣợng sử dụng dữ liệu thu thập từ các dự n đã hoàn thành
từ nhiều tổ chức khác nhau cùng với công thức toán học để ƣớc lƣợng chi phí dự án
đƣợc giới thiệu nhƣ COCOMO của Barry Boehm, SLIM của Putnam, mô hình điểm
chức năng của Albrecht…
Trong những năm gần đây, c c mô hình thuật toán và xử lý những khó khăn
trong việc điều chỉnh các tham số nhằm cải tiến độ chính xác của ƣớc lƣợng nỗ lực
phát triển phần mềm đƣợc phát triển rộng rãi. Các mô hình Sheta hay Uysal sử dụng
thuật toán tối ƣu của bầy đàn đã đ p ứng đƣợc tiến độ của c c phƣơng ph p công nghệ
phần mềm mới. Áp dụng một phƣơng ph p ƣớc lƣợng trong qu trình ph t triển phần
mềm là một nhiệm vụ khó khăn mà chúng ta cần phải lƣờng trƣớc k ch thƣớc và độ
phức tạp của các sản phẩm sẽ đƣợc xây dựng để x c định những việc cần làm tiếp
theo. Phát triển phần mềm theo mô hình Sheta sử dụng thuật to n đã trở nên phổ biến
trong ngành công nghiệp và thay thế c c phƣơng ph p tiếp cận thông thƣờng của phát
triển phần mềm.
Trí thông minh của bầy đàn là quy luật đƣợc tích góp từ c c hành vi tƣơng t c
độc lập của c c c nhân và môi trƣờng sống của chúng. Gần đây, c c nhà ph t triển
phần mềm đã nghiên cứu về trí tuệ của bầy đàn để tối ƣu hóa c c bài toán về ƣớc
lƣợng nỗ lực phát triển phần mềm. Đa số c c phƣơng ph p đƣợc lấy cảm hứng từ hiện
tƣợng sinh học hoặc các hành vi xã hội và chủ yếu là động vật, côn trùng. Trong đó,
hành vi săn mồi của bầy sói cho thấy đƣợc kỹ năng và chiến lƣợc tuyệt vời của chúng.
Ngoài sự phát triển của các thuật toán tối ƣu về bầy đàn nhƣ: đàn c , đàn ong nhân tạo,
thuật to n đom đóm… thuật toán về bầy sói cũng đƣợc đề xuất để nâng cao hiệu quả
cho ƣớc lƣợng nỗ lực của phát triển phần mềm.
Chính vì vậy, tôi quyết định chọn đề tài:


2

“ Ước lượng nỗ lực phát triển phần mềm sử dụng thuật toán tối ưu dựa trên
hành vi săn mồi của bầy sói”.

2. Mục đích nghiên cứu
- Nghiên cứu thuật to n tối ƣu hành vi săn mồi của bầy sói.
- Nghiên cứu lý thuyết về ƣớc lƣợng nỗ lực ph t triển phần mềm theo mô hình
Sheta.
- Áp dụng vào ƣớc lƣợng nỗ lực phần mềm theo mô hình Sheta nhằm tối ƣu c c gi
trị trong ƣớc lƣợng phần mềm.
3. Đối tƣợng và phạm vi nghiên cứu
3.1. Đối tượng nghiên cứu
- Nghiên cứu thuật toán tối ƣu bầy đàn.
- Cơ sở lý thuyết về ƣớc lƣợng nỗ lực phát triển phần mềm.
3.2. Phạm vi nghiên cứu
- Nghiên cứu thuật toán tối ƣu hành vi săn mồi của bầy sói.
- Nghiên cứu ƣớc lƣợng nỗ lực phát triển phần mềm theo mô hình Sheta.
4. Phƣơng pháp nghiên cứu
4.1. Phương pháp nghiên cứu lý thuyết
Tìm hiểu, tra cứu, phân tích và tổng hợp từ sách, các bài báo, tạp chí khoa học, các
trang web, các bài luận văn thạc sĩ trong nƣớc và nƣớc ngoài.
4.2. Phương pháp thực nghiệm, mô phỏng
- Đề xuất áp dụng thuật toán tối ƣu dựa trên hành vi săn mồi của bầy sói.
- Cài đặt thực nghiệm và đ nh gi kết quả.
5. Dự kiến kết quả đạt đƣợc
5.1. Về mặt lý luận
- Hiểu đƣợc đặc điểm, tính chất của thuật toán tối ƣu bầy đàn.
- Hiểu đƣợc mô hình Sheta trong ƣớc lƣợng nỗ lực phát triển phần mềm.
- Áp dụng thuật toán tối ƣu dựa trên hành vi săn mồi vào bài to n ƣớc lƣợng nỗ lực
sử dụng tập dữ liệu trên NASA để đƣợc các tham số cần ƣớc lƣợng.
5.2. Về mặt thực tiễn
- Đề xuất giải ph p ƣớc lƣợng nỗ lực phát triển phần mềm theo mô hình Sheta sử
dụng thuật toán tối ƣu dựa trên hành vi săn mồi của bầy sói.
- Đ nh gi hiệu quả của giải ph p đề xuất so với các thuật toán tối ƣu kh c.



3

6. Nội dung nghiên cứu và dự kiến cấu trúc luận văn
6.1. Nội dung nghiên cứu
- Thu thập và tổng hợp các tài liệu liên quan đến thuật toán tối ƣu về hành vi săn mồi
của bầy sói.
- Thu thập, tổng hợp và phân t ch kỹ thuật ƣớc lƣợng nỗ lực phát triển phần mềm
theo mô hình Sheta.
- Áp dụng thuật to n tối ƣu dựa trên hành vi săn mồi của bầy sói để ƣớc lƣợng nỗ
lực ph t triển phần mềm theo mô hình Sheta.
- Thử nghiệm, phân tích các kết quả; từ đó đ nh gi hiệu quả của giải ph p đề xuất.
6.2. Bố cục luận văn
Mở đầu
- Tính cấp thiết của đề tài.
- Mục tiêu của luận văn.
- Ý nghĩa thực tiễn.
Chƣơng 1: Tổng quan về ƣ c ƣợng nỗ ực phát triển ph n mềm theo m h nh
Sheta
-

Tổng quan về ƣớc lƣợng nỗ lực phát triển phần mềm.
C c phƣơng ph p ƣớc lƣợng nỗ lực.
Ƣớc lƣợng nỗ lực cho dự án phát triển phần mềm theo mô hình Sheta.
Mô hình ƣớc lƣợng nỗ lực phát triển phần mềm.

Tiểu kết chƣơng 1
Chƣơng 2: Thuật toán tối ƣu dựa trên hành vi săn mồi của b y sói
-


Giới thiệu.
Mô tả hành vi săn mồi của bầy sói.
Chi tiết thuật toán.
Cài đặt thuật toán.

Tiếu kết chƣơng 2
Chƣơng 3: Ứng dụng thuật toán vào dự đoán nỗ lực phát triển ph n mềm
- Giới thiệu.
- Thu thập dữ liệu, phân tích mô hình.
- Đ nh gi hiệu quả ƣớc lƣợng của mô hình Sheta sử dụng thuật toán tối ƣu dựa trên
hành vi săn mồi của bầy sói.
Tiểu kết chƣơng 3
Kết luận và hƣ ng phát triển


4

CHƢƠNG 1 - TỔNG QUAN VỀ Ƣ C Ƣ NG NỖ
C PHÁT TRIỂN
PH N MỀM THEO M H NH SHETA
Khi nói đến vấn đề ph t triển phần mềm thì không thể không đề cập đến qu trình
quản lý phần mềm, đƣợc bắt đầu và tiếp diễn bằng một chuỗi c c hoạt động ƣớc lƣợng
phần mềm. Trong thực tế, để lấy đƣợc dự n phần mềm, c c công ty tham gia đấu thầu
phải nộp hồ sơ dự thầu bao gồm cả chi ph , nhân lực và thời gian ph t triển phần mềm.
C c công ty tham gia dự thầu rất cần phải đƣa ra một ƣớc lƣợng hợp lý phản nh đúng
gi trị thật của đề n.
1.1. Tổng quan về ƣ c ƣợng nỗ lực phát triển ph n mềm
1.1.1. Khái niệm
Ƣớc lƣợng là công việc t nh to n gần đúng một đại lƣợng nào đó dựa trên tập dữ

liệu liên quan đến đại lƣợng đó. Tập dữ liệu này thƣờng đƣợc thu thập trong điều kiện
thiếu, nhiễu hoặc chỉ có gi trị gần đúng. Khi tập dữ liệu ở trong điều kiện hoàn hảo
hay đầy đủ thông tin thì ƣớc lƣợng trở thành t nh to n ch nh x c.
Hình 1.1 (đƣợc tr ch từ tài liệu tham khảo [4]) thể hiện độ hội tụ của ƣớc lƣợng
trong vòng đời ph t triển của c c dự n thực tế, ƣớc lƣợng chỉ đƣợc ch nh x c hóa dần
trong qu trình làm mịn dần dự n. Từ hình 1.1 có thế nhận thấy rằng để đƣa ra đƣợc
c c ƣớc lƣợng đ ng tin cậy và sớm trong vòng đời ph t triển của dự n là rất khó do đó
chúng ta cần tập trung nhiều nỗ lực để giải quyết vấn đề này.
Ƣớc lƣợng thiếu nỗ lực cho một dự n dẫn đến việc bố tr thiếu nhân sự cho dự n
(điều mà thƣờng dẫn đến việc vƣợt qu khả năng làm việc), quản lý thiếu c c nỗ lực
đảm bảo chất lƣợng (bỏ sót c c nguy cơ rủi ro của sản phẩm kém chất lƣợng) và tạo ra
một lịch trình làm việc qu ngắn (dẫn đến sự mất uy t n do thời hạn thỏa thuận với
kh ch hàng không đƣợc tôn trọng).
Còn thêm nhiều yếu tố thừa vào ƣớc lƣợng thì ƣớc lƣợng thừa một dự n có thể chỉ
làm tồi tệ thêm cho tổ chức. Nếu nhƣ đƣa cho một dự n với nhiều tài nguyên hơn mức
nó thực sự cần mà không có những sự quản lý thì tài nguyên đó sẽ bị dùng hết.
Dự n khi đó có khả năng phải chi ph nhiều hơn mức cần thiết (một t c động tiêu
cực đến tài ch nh và có thể làm giảm lợi thế cạnh tranh), mất nhiều thời gian hơn để
hoàn thành (dẫn đến đ nh mất c c cơ hội) và trì hoãn việc sử dụng tài nguyên ở c c dự
n tiếp theo.


5

Hình 1.1 Đồ thị hội tụ ƣớc lƣợng. Nguồn tài liệu tham khảo[4]
Ƣớc lƣợng dự n hiện là một vấn đề khó khăn trong thực tế sản xuất phần mềm.
Không ƣớc lƣợng đƣợc thì dự n rất dễ vỡ kế hoạch về thời gian và tài ch nh. Mức ƣớc
lƣợng có thể có nhiều sai sót trong c c giai đoạn kh c nhau do đó thực tế không dự n
nào có thể ƣớc lƣợng ch nh x c. Ƣớc lƣợng chỉ có thể ch nh x c nếu phân rã đƣợc vấn
đề lớn thành c c vấn đề nhỏ hơn, đó là kỹ thuật chia để trị.


1.1.2. Bốn bước cơ bản trong ước lượng dự án phần mềm
Bốn bƣớc ch nh trong ƣớc lƣợng dự án phần mềm là:
1) Ƣớc lƣợng phạm vi của sản phẩm cần ph t triển. Thông thƣờng, điều này luôn
yêu cầu một ƣớc lƣợng k ch cỡ của phần mềm đƣợc ph t triển theo số dòng lệnh (LOC
– line of code) hoặc điểm chức năng (FP – Function Point). Trong khi k ch cỡ theo
LOC là đơn vị k ch cỡ cơ sở đƣợc dùng bởi nhiều mô hình t nh to n ƣớc lƣợng hàng
đầu, nhiều đội ph t triển lại không th ch những phép đo này và dùng những đơn vị t
ch nh quy hơn (số đặc t nh, số yêu cầu thay đổi, số ca sử dụng/số kịch bản, số tƣờng
thuật ngƣời dùng, số ph t biểu yêu cầu, …).


6

2) Ƣớc lƣợng nỗ lực theo đơn vị [ngƣời – th ng] hoặc [ngƣời – giờ] dùng một mô
hình t nh to n liên hệ nỗ lực với k ch cỡ của phần mềm và năng suất của nhóm ph t
triển.
3) Ƣớc lƣợng lịch trình theo lịch thời gian (th ng/tuần). Điều này có thể đƣợc t nh
to n từ nỗ lực đƣợc ƣớc lƣợng và là một hàm số của k ch cỡ nhóm ph t triển. Điều
quan trọng là phải nhận thức rõ rằng đây không phải là một quan hệ tuyến t nh và ở
một số điểm trong lịch trình dự n không thể rút ngắn lịch trình bằng c ch thêm tài
nguyên cho việc ph t triển.
4) Ƣớc lƣợng chi ph dự n theo đơn vị tiền tệ. Điều này là một kết hợp của gi
nhân công (có thể đƣợc t nh to n từ ƣớc lƣợng nỗ lực) và gi phi nhân công (v dụ, gi
khấu hao của c c phần cứng và phần mềm cần thiết đƣợc cung cấp cho dự n).
1.1.2.1. Ước lượng kích cỡ, phạm vi
Một ƣớc lƣợng ch nh x c k ch cỡ của phần mềm đƣợc xây dựng là bƣớc đầu tiên
cho một ƣớc lƣợng có hiệu quả. C c tài nguyên thông tin về phạm vi của dự n nên
đƣợc thu thập bất cứ nơi nào có thể, bắt đầu với những mô tả ch nh x c của c c yêu
cầu. V dụ, một đặc tả c c yêu cầu của kh ch hàng hoặc một đặc tả về hệ thống. Không

nên để cho sự thiếu sót về đặc tả phạm vi làm cản trở việc thực hiện ƣớc lƣợng. Tài
liệu ƣớc lƣợng cũng không nên chốt cứng. Trong mọi trƣờng hợp, chúng ta phải xem
xét c c mức độ rủi ro và không chắc chắn trong một ƣớc lƣợng cho mọi kh a cạnh và
phải thực hiện lại ƣớc lƣợng cho dự n ngay khi có thêm thông tin phạm vi đƣợc x c
định. Nếu chúng ta thực hiện ƣớc lƣợng lại một dự n ở những pha sau của vòng đời
dự n, c c tài liệu thiết kế có thể đƣợc sử dụng để cung cấp thêm thông tin chi tiết.
Hai c ch để có thể ƣớc lƣợng k ch cỡ sản phẩm là:
1) Cách thứ nhất: ằng phép tƣơng tự.
Nếu chúng ta đã hoàn thành một dự n tƣơng tự trong qu khứ và biết thông tin
k ch cỡ sản phẩm đã đƣợc ph t triển, chúng ta có thể ƣớc lƣợng mỗi phần ch nh của dự
n mới nhƣ là một phép t nh phần trăm về k ch cỡ phần tƣơng tự với dự n trƣớc. Ƣớc
lƣợng k ch cỡ tổng thể dự n mới bằng c ch cộng lại c c k ch cỡ đƣợc ƣớc lƣợng của
mỗi phần hoặc chia sản phẩm thành những phần cấu thành (c c đặc t nh, c c ca sử
dụng/kịch bản, c c yêu cầu ngƣời dùng) và đếm chúng. Một số ngƣời dùng những
phép đếm thô nhƣ là một ƣớc lƣợng trực tiếp của k ch cỡ phần mềm hoặc chúng ta có
thể chuyển chúng thành một đơn vị đo k ch cỡ ch nh thức mà ta biết, theo một phép
t nh trung bình, bao nhiêu LOC hoặc FP mà mỗi phần này yêu cầu trong những dự n
trƣớc.
Một ngƣời có kinh nghiệm có thể đƣa ra những ƣớc lƣợng k ch cỡ tốt, hợp lý bằng
phép tƣơng tự nếu sẵn có c c gi trị k ch cỡ chuẩn x c cho dự n trƣớc và dự n mới là


7

gần giống với dự n trƣớc.
2) C ch thứ hai: ằng phép phân t ch.
ằng c ch đếm c c đặc t nh của sản phẩm và dùng một phƣơng ph p nhƣ là điểm
chức năng (FP) chúng ta có thể chuyển phép đếm thành một ƣớc lƣợng của k ch cỡ.
C c đặc t nh sản phẩm ở cấp độ vĩ mô có thể chứa c c hệ thống con, c c lớp/mô
đun, c c phƣơng thức/hàm. C c đặc t nh sản phẩm ở mức chi tiết hơn có thể gồm có số

lƣợng c c màn hình, c c hộp thoại, c c tập tin, c c bảng cơ sở dữ liệu, các báo cáo và
c c thông điệp,…
1.1.2.2. Ước lượng nỗ lực
Một khi chúng ta có một ƣớc lƣợng k ch cỡ của sản phẩm, chúng ta có thể t nh to n
ƣớc lƣợng nỗ lực từ nó. Việc chuyển đổi từ k ch cỡ phần mềm sang tổng nỗ lực dự n
chỉ có thể làm đƣợc nếu chúng ta có một vòng đời ph t triển phần mềm x c định và
tiến trình ph t triển mà ta sử dụng ổn định trên dự n để phân t ch, thiết kế, ph t triển
và kiểm thử phần mềm.
Một dự n ph t triển phần mềm đòi hỏi nhiều yêu cầu hơn công việc viết mã nguồn
đơn thuần. Trên thực tế, việc mã hóa chỉ chiếm chƣa đến ¼ tổng thể nỗ lực dự n. Việc
viết và thẩm định tài liệu, thi hành c c bản mẫu, thiết kế c c phiên bản có thể phân
phối và thẩm định, kiểm thử mã chiếm phần lớn thời gian của nỗ lực dự n tổng thể.
Ƣớc lƣợng nỗ lực dự n yêu cầu ta x c định và ƣớc lƣợng về thời gian, về nhân lực,…
Sau đó tổng hợp lại tất cả c c hoạt động ta phải thực hiện để xây dựng sản phẩm từ
k ch cỡ đƣợc ƣớc lƣợng.
1.1.2.3. Ước lượng lịch trình
ƣớc thứ ba trong ƣớc lƣợng một dự n ph t triển phần mềm là ƣớc lƣợng lịch
trình dự n. Điều này thƣờng đòi hỏi ƣớc lƣợng số lƣợng ngƣời sẽ làm việc trên dự n,
c i gì họ sẽ làm (cấu trúc phân cấp chia nhỏ công việc), khi nào họ sẽ bắt đầu làm việc
trên dự n và khi nào họ sẽ kết thúc. Một khi chúng ta có những thông tin này, chúng
ta cần t nh to n để đƣa nó vào một lịch trình theo lịch thời gian. Ngoài ra, dữ liệu lịch
sử từ c c dự n trong qu khứ của tổ chức hoặc c c mô hình dữ liệu công nghiệp có
thể đƣợc sử dụng để dự đo n số lƣợng ngƣời mà chúng ta cần cho một dự n với k ch
cỡ cho trƣớc và làm thế nào công việc có thể chia nhỏ vào lịch trình.
Nếu chúng ta không có gì, một quy tắc ƣớc lƣợng lịch trình có thể đƣợc dùng để
lấy c c ý tƣởng thô của lịch thời gian tổng cổng cần thiết:
Lịch trình theo tháng = 3.0 * (nỗ lực [người – tháng])*1/3
V dụ, nếu chúng ta đã ƣớc lƣợng một dự n cần nỗ lực là 65 [ngƣời – tháng], biểu
thức trên cho thấy rằng cần lịch trình 12 th ng, từ đó suy ra nhóm dự n có 5 hoặc 6
thành viên (65/12).



8

Trong [4], t c giả có nêu vấn đề nhiều đề xuất dùng 2.0, 2.5 hay ngay cả 4.0 để
thay thế cho gi trị 3.0 – chỉ bằng thực nghiệm thì chúng ta mới có thể chọn đƣợc gi
trị phù hợp.
Ƣớc lƣợng lịch trình dự n là một chủ đề rắc rối bởi vì hầu hết c c dự n thƣờng
bị chậm trễ và sự chậm trễ do nhiều nguyên nhân. C c yêu cầu đƣợc ph t hiện dần dần
không đƣợc quản lý chủ động. Việc điều khiển chất lƣợng sản phẩm từ sớm thƣờng
không đƣợc chú trọng, dẫn đến dự n sẽ bị chậm trễ khi pha kiểm thử bắt đầu. Ở
những tổ chức chƣa có quy trình làm việc chuẩn thì những dự thảo lịch trình thƣờng bị
bỏ qua ngay cả với những ngƣời điều hành cấp cao.
Xem xét công việc quản trị dự n và công việc ƣớc lƣợng lịch trình, chúng ta thấy
rằng công việc ƣớc lƣợng lịch trình sẽ quan tâm đến việc lên lịch trình ở mức độ cao
của toàn dự n, còn những t nh to n chi tiết hơn đòi hỏi c c yếu tố phụ thuộc, đội ngũ
nhân viên sẵn có, mức độ tài nguyên, phân công cho từng ngƣời sẽ đƣợc thực hiện bởi
công việc quản trị dự n.
Nếu ƣớc lƣợng theo biểu thức t nh lịch trình ở trên, ta ƣớc lƣợng thời gian lịch
trình trƣớc sau đó mới chỉ định số nhân viên. Nhƣng nếu đƣợc chỉ định một đội/nhóm
ph t triển trƣớc, một biểu thức cơ bản cho việc ƣớc lƣợng lịch trình của bất kỳ hoạt
động quản lý là:
Nỗ lực / Số nhân viên = Lượng thời gian
Dùng biểu thức tổng qu t này, một hoạt động mà yêu cầu 8 [ngƣời – th ng] của nỗ
lực và có 4 ngƣời đƣợc chỉ định tham gia có thể đƣợc hoàn thành trong thời gian 2
tháng.
8 [người – tháng] / 4 [người] = 2 [tháng]
Thực tế thì việc ƣớc lƣợng lịch trình sẽ khó hơn rất nhiều. Nó liên quan đến nhiều
yếu tố nhƣ:
 C c phụ thuộc của một hoạt động với c c hoạt động trƣớc

 C c hoạt động đan xen hay đồng thời
 Đƣờng găng xuyên suốt chuỗi công việc
 Số ca làm việc mỗi ngày, số giờ làm việc hiệu quả trong mỗi ca
 Những gi n đoạn nhƣ là du lịch, hội nghị, đào tạo hay nghỉ ốm, …
 Số lƣợng vùng thời gian cho c c dự n đối với c c công ty đa quốc gia
Nhƣ vậy công việc quản trị dự n, công việc ƣớc lƣợng lịch trình có nhiều mối
liên hệ và đƣợc thực hiện theo sự tinh tế của từng ngƣời quản lý.


9

1.1.2.4. Ước lượng chi phí
Có nhiều yếu tố cần quan tâm khi ƣớc lƣợng chi ph tổng cộng của một dự n.
Những yếu tố đó bao gồm gi nhân công, gi mua hay gi thuê phần cứng, phần mềm,
chi ph đi lại cho mục đ ch gặp gỡ hay kiểm thử, c c giao tiếp (v dụ, c c cuộc gọi điện
thoại đƣờng dài, hội thảo video từ xa, …), c c khóa đào tạo, không gian văn phòng, …
Gi nhân công thì có thể đƣợc x c định một c ch đơn giản nhất bằng phép nhân
giữa nỗ lực ƣớc lƣợng của dự n (t nh theo giờ) với lƣơng nhân công t nh trung bình
tổng qu t. Một chi ph nhân công chuẩn x c hơn lấy kết quả từ việc sử dụng lƣơng
nhân công rõ ràng cho mỗi vị tr (v dụ: vị tr kĩ thuật, quản lý chất lƣợng, quản lý dự
n, ngƣời lập tài liệu, cộng t c viên, …). Chúng ra sẽ phải x c định xem bao nhiêu
phần trăm của nỗ lực dự n tổng cộng cần đƣợc cấp ph t cho mỗi vị tr . Khi đó dữ liệu
lịch sử hoặc c c mô hình dữ liệu công nghiệp lại có thể trợ giúp.
Qua việc nghiên cứu 4 bƣớc trong phép ƣớc lƣợng nhƣ trên, đề xuất một tiến trình
cơ sở cho việc ƣớc lƣợng nhƣ đƣợc mô tả trong sơ đồ ở hình 1.2.

Hình 1.2. Tiến trình cơ sở ƣớc lƣợng dự án


10


- Ƣớc lƣợng dựa vào mô hình to n học: còn đƣợc gọi là c c mô hình tham số nhằm
cố gắng thể hiện mối quan hệ giữa nỗ lực và đặc điểm của dự n. Chƣơng trình điều
khiển chi ph ch nh của c c mô hình này là k ch thƣớc phần mềm, thƣờng đƣợc đo
bằng c c dòng lệnh (Kilo Line of Code - KLOC) hoặc điểm chức năng. Đây vẫn là kỹ
thuật phổ biến nhất trong lƣợc khảo tài liệu [5]. C c mô hình này bao gồm COCOMO
I [6], COCOMO II [7], mô hình SLIM [8], và điểm chức năng [9].
Tuy nhiên, không có phƣơng ph p nào đƣợc đề cập ở trên là hoàn chỉnh và có thể
phù hợp trong mọi tình huống. Nghiên cứu này tập trung vào c c mô hình thuật to n
và giải quyết những khó khăn của chúng trong việc định chuẩn và điều chỉnh c c
thông số để nâng cao t nh ch nh x c của ƣớc lƣợng nỗ lực phần mềm.
1.3. M h nh ƣ c ƣợng nỗ lực phát triển ph n mềm
Phƣơng ph p ƣớc lƣợng dựa trên mô hình to n học là phổ biến. C c nhà nghiên
cứu đã cố gắng tìm ra c c mô hình và công thức to n học để trình bày mối quan hệ
giữa k ch thƣớc, chƣơng trình điều khiển chi ph , phƣơng ph p luận đƣợc sử dụng
trong dự n và nỗ lực. Kết quả là một mô hình thuật to n có thể đƣợc biểu diễn nhƣ
sau:
Effort = f(x1, x2,…, xn)

(1.1)

Trong đó{x1, x2,…, xn} biểu thị c c yếu tố chi ph . Ngoài k ch thƣớc phần mềm, có
rất nhiều yếu tố chi ph kh c đƣợc đề xuất và đƣợc sử dụng bởi oehm và cộng sự
trong Mô hình Chi ph Xây dựng COCOMO II (Constructive Cost Model) [7]. Những
yếu tố chi ph này có thể đƣợc chia thành bốn loại:
- C c yếu tố sản phẩm: yêu cầu độ tin cậy phần mềm, k ch thƣớc cơ sở dữ liệu, độ
phức tạp của sản phẩm.
- C c yếu tố m y t nh: ràng buộc thời gian thực thi, bộ nhớ lƣu trữ, độ không ổn
định của m y ảo và c c ràng buộc vòng quay m y t nh.
- C c yếu tố nhân sự: khả năng phân t ch, kinh nghiệm ứng dụng, khả năng lập

trình, kinh nghiệm về m y ảo và kinh nghiệm về ngôn ngữ.
- C c yếu tố dự n: ph t triển đa trang web, công cụ phần mềm đƣợc sử dụng và
tiến độ ph t triển cần thiết.
C c mô hình thuật to n hiện nay kh c nhau giữa c c yếu tố chi ph đƣợc lựa chọn
và hàm f đƣợc sử dụng.
Công thức đơn giản nhất của mối quan hệ giữa nỗ lực và c c yếu tố đầu vào là một
hàm tuyến t nh, có nghĩa là nếu k ch thƣớc tăng lên thì nỗ lực cũng tăng với tốc độ ổn
định. C c mô hình tuyến t nh có dạng:


11

∑

(1.2)

Trong đó, c c hệ số a0, a1, ..., an đƣợc chọn để phù hợp nhất với dữ liệu toàn bộ dự
án.
Tuy nhiên, mô hình tuyến t nh không phù hợp với ƣớc lƣợng c c dự n có gi trị
trong c c môi trƣờng lớn. Do đó, c c mô hình phức tạp hơn đã đƣợc ph t triển. Những
điều này phản nh thực tế là chi ph thƣờng không tăng tuyến t nh với quy mô dự n.
Một c ch tổng qu t nhất, ƣớc lƣợng thuật to n cho chi ph phần mềm có thể đƣợc biểu
diễn nhƣ sau:
Effort = A * SizeB * M

(1.3)

Trong đó:
+ A là một yếu tố không đổi phụ thuộc vào cơ chế hoạt động nội bộ và loại
phần mềm đƣợc ph t triển.

+ Size là k ch thƣớc của phần mềm.
+ Gi trị của số mũ

thƣờng từ 1 đến 1,5.

+ M là một cấp số nhân đƣợc xây dựng bằng c ch kết hợp c c quy trình, sản
phẩm và c c thuộc t nh ph t triển.
1.3.1. Mô hình COCOMO
COCOMO đƣợc oehm giới thiệu là một trong những mô hình ƣớc t nh nỗ
lực ph t triển phần mềm rất nổi tiếng đƣợc sử dụng theo công thức chung đƣợc trình
bày trong phƣơng trình 1.3. Mô hình COCOMO là một mô hình thực nghiệm thu
đƣợc bằng c ch thu thập, phân t ch dữ liệu từ 63 dự n phần mềm. Những dữ liệu này
đƣợc phân t ch để xây dựng một công thức phù hợp nhất với c c thông tin đã đƣợc
ghi nhận. Công thức của COCOMO cơ bản đƣợc biểu diễn trong phƣơng trình 1.4:
E = A * (KLOC)B

(1.4)

Trong đó:
+ E là nỗ lực ph t triển phần mềm t nh theo đơn vị ngƣời - tháng.
+ KLOC là số dòng lệnh (đơn vị = 1000) ƣớc t nh của sản phẩm dự n phần
mềm.
+ C c gi trị của c c tham số A và
mềm.

phụ thuộc chủ yếu vào loại dự n phần

Dựa trên sự phức tạp của dự n có thể phân ra làm ba lớp:
- Lớp đơn (Organic): dành cho một đội nhỏ c c nhà ph t triển có kinh nghiệm và
môi trƣờng quen thuộc. Đối với c c ứng dụng đơn giản này: A = 2.4, B = 1.05.



12

- Nửa gắn kết (Semi – detached): trung gian giữa lớp đơn và lớp nhúng. Đối với hệ
thống phức tạp hơn: A = 3.0, = 1.15.
- Nhúng (Embedded): dành cho dự n có nhiều ràng buộc chặt chẽ, thƣờng là dự n
mới và duy nhất, khó tìm ngƣời thực hiện. Đối với hệ thống nhúng: A = 3.6, = 1.15.
Mô hình COCOMO bỏ qua c c yêu cầu về kinh nghiệm, khả năng chuyên nghiệp
của con ngƣời, c c vấn đề về phần cứng. Do đó, đối với c c dự n phức tạp, c c kết
quả ƣớc t nh sử dụng mô hình COCOMO không ch nh x c.
1.3.2. Mô hình Sheta
Một phƣơng ph p kh c để nâng cao chất lƣợng của mô hình COCOMO là bổ sung
phƣơng ph p luận (Methodology: ME) đƣợc sử dụng vào phƣơng trình để ƣớc t nh nỗ
lực trong dự n phần mềm. Việc bổ sung yếu tố ME tƣơng tự nhƣ c c mô hình hồi qui
giúp ổn định mô hình và giảm nhiễu trong c c phép đo. Mô hình nỗ lực ph t triển phần
mềm đƣợc thay đổi thành:
E = f(KLOC, ME)

(1.5)

Trong đó, f là một hàm không tuyến t nh theo KLOC và ME.
Sheta [3] đã đƣa ra hai phiên bản kh c nhau cho hàm f nhƣ sau:
Mô hình Sheta 1:
E = A * (KLOC)B + C * ME
Cấu trúc mô hình đề xuất có c c tham số A,
ƣớc lƣợng nhƣ sau:
Với A = 3.1938,

(1.6)

và C. C c tham số mô hình đƣợc

= 0.8209, C = - 0.1918

Mô hình Sheta 2:
E = A * (KLOC)B + C * ME + D
Với A = 3.3602,

(1.7)

= 0.8116, C = - 0.4524, D = 17.8025.

Để tối ƣu hóa c c thông số của mô hình Sheta nhằm nâng cao t nh ch nh x c của
c c ƣớc t nh ta sẽ sử dụng thuật to n Grey Wolf Optimizer.


13

CHƢƠNG 2 - THUẬT TOÁN TỐI ƢU D A TRÊN HÀNH VI SĂN MỒI
CỦA B Y SÓI
Tối ƣu hóa là một trong những lĩnh vực quan trọng của toán học có ảnh hƣởng đến
hầu hết c c lĩnh vực khoa học, công nghệ, kinh tế và xã hội. Việc tìm giải pháp tối ƣu
cho một bài toán thực tế nào đó chiếm một vai trò hết sức quan trọng nhƣ việc tiến
hành lập kế hoạch sản xuất hay thiết kế hệ thống điều khiển c c qu trình… Nếu sử
dụng các kiến thức trên nền tảng của toán học để giải quyết các bài toán cực trị thì
chúng ta sẽ đạt đƣợc hiệu quả kinh tế cao. Điều này phù hợp với mục đ ch của các vấn
đề đặt ra trong thực tế hiện nay. Một phƣơng n tối ƣu là một phƣơng n khả thi và tốt
nhất, tức là phƣơng n làm cho hàm mục tiêu đạt kết quả cực tiểu hoặc cực đại và phải
thỏa mãn c c điều kiện yêu cầu của bài toán (thỏa mãn c c điều kiện ràng buộc). Tối
ƣu hóa có thể trở nên khó khăn hơn khi không gian tìm kiếm ngày càng rộng lớn. Đối

với các bài toán cỡ nhỏ có thể tìm lời giải bằng cách tìm kiếm vét cạn. Đối với các bài
toán cỡ lớn không có phƣơng ph p giải đúng, đến nay ngƣời ta vẫn dùng các cách tiếp
cận sau:
1) Tìm kiếm heuristic để tìm lời giải đủ tốt;
2) Tìm kiếm cục bộ để tìm lời giải tối ƣu địa phƣơng;
3) Tìm lời giải gần đúng nhờ các thuật toán mô phỏng tự nhiên nhƣ: mô phỏng luyện
kim, giải thuật di truyền, tối ƣu bầy đàn,…Phƣơng pháp này còn gọi là
“metaheuristics” là nền tảng của các thuật toán có thể đƣợc sửa đổi và mở rộng cho
phù hợp với các vấn đề tối ƣu hóa
Hai cách tiếp cận đầu thƣờng cho lời giải nhanh nhƣng không thể cải thiện thêm lời
giải tìm đƣợc, nên cách tiếp cận thứ ba đang đƣợc sử dụng rộng rãi cho các bài toán cỡ
lớn.
2.1. Gi i thiệu
2.1.1. Bài toán tối ưu tổng quát và phân loại
2.1.1.1. Giới thiệu bài toán tối ưu tổng quát
Trong mô hình to n học, mục tiêu của bài to n đƣợc biểu diễn bởi hàm:
f (x)  min/max; với x là một biến hoặc vector biến x = (x1 ,x2 ,...,xn )
iến x hoặc vector biến x = (x1, x2,..., xn ) thƣờng có yêu cầu phải thỏa mãn một số
điều kiện nào đó. Tập hợp c c điều kiện của c c biến đƣợc gọi là điều kiện ràng buộc
và đƣợc biểu diễn bởi miền D (miền ràng buộc).
Dạng tổng qu t của bài to n tối ƣu:
Tìm cực tiểu/cực đại một hàm mục tiêu:


14

f (x)  min/max

(2.1)


Thỏa mãn c c điều kiện ràng buộc:
x

D

(2.2)

Yêu cầu: Tìm x để thỏa mãn (2.2) và làm cực tiểu/cực đại hàm mục tiêu (2.1), x*
(một bộ c c gi trị cụ thể của (x1 ,x2 ,...,xn ), thỏa mãn điều kiện (2.1) & (2.2) gọi là
phƣơng n tối ƣu. Nếu x chỉ thỏa mãn điều kiện (2.2) gọi x là phƣơng n hay phƣơng
n chấp nhận đƣợc.
2.1.1.2. Phân loại các bài toán tối ưu
C c bài to n tối ƣu ch nh là c c bài to n qui hoạch to n học (Mathematics –
Programming)


ài to n tối ƣu tuyến t nh: Hàm mục tiêu và tất cả c c ràng buộc đều có dạng
tuyến t nh.



ài to n tối ƣu phi tuyến: Trong đó hàm mục tiêu hoặc t nhất một điều kiện
ràng buộc là phi tuyến (có chứa t nhất một yếu tố phi tuyến t nh – bậc lơn hơn
1, logic, hàm mũ…).



ài to n tối ƣu rời rạc: Khi biến hoặc gi trị hàm mục tiêu là rời rạc. Có thể chia
nhƣ sau:
 Tối ƣu nguyên (quy hoạch nguyên): C c biến hoặc c c hàm mục tiêu nhận

c c gi trị nguyên.
 Tối ƣu đồ thị: Là một dạng đặc biệt của bài to n tối ƣu rời rạc. Có c c đỉnh là c c
điểm rời rạc. K hiệu: X = {A, , C, D}. Tập cạnh E = {e1, e2,…} hoặc E = {(A,
D); (A, ); … }. Tìm đƣờng đi ngắn nhất của đồ thị thỏa mãn điều kiện nào đó.



ài to n quy hoạch động (những kết quả của bài to n ở bƣớc sau thì phụ thuộc
vào kết quả của bƣớc trƣớc). Quy hoạch động là một phƣơng ph p rất hiệu quả
để giải c c bài to n tối ƣu tổ hợp. Ý tƣởng cơ bản của phƣơng ph p này là: để có
lời giải của bài to n tối ƣu k ch thƣớc n, ta giải c c bài to n tƣơng tự có k ch
thƣớc nhỏ hơn và phối hợp lời giải của chúng để đƣợc lời giải của bài to n ban
đầu. Đó ch nh là ý tƣởng chia để trị một c ch rất nghiêm ngặt.



ài to n tối ƣu đa mục tiêu: Là bài to n trong đó có nhiều hàm mục tiêu cần
phải tối ƣu trên cùng một miền ràng buộc.
fi (x) → min (max); i = 1, 2, …, n

x

D

Trong đó có nhiều hàm mục tiêu có thể đối lập nhau. Khi giải bài toán này phải kết
hợp hài hòa các lợi ích (giá trị) đạt đƣợc của hàm mục tiêu.


15


2.1.2. Trí tuệ bầy đàn
Thế giới tự nhiên thúc đẩy giới sinh vật tiến hóa theo hai c ch để thực hiện những
hành động thông minh:
 Một là ph t triển những bộ não lớn và tinh vi nhƣ bộ não con ngƣời.
 Hai là hàng triệu những bộ não nhỏ có khả năng liên lạc với nhau trong những
bầy đàn khổng lồ.
Có thể nói, tuy một con kiến hoặc một con ong không có tr thông minh nhƣng cả
đàn thì có.
Tr tuệ bầy đàn hay tr thông minh bầy đàn là c ch thức liên lạc giữa một c thể và
tập thể trong một tổ chức khổng lồ. Tr tuệ bầy đàn thể hiện qua những hành vi tập thể
trong một hệ thống (tự nhiên hoặc nhân tạo) đƣợc tổ chức và phân cấp. Nhờ tr tuệ bầy
đàn, mỗi c thể hành động tuân theo quy tắc chung của cả đàn mà không cần ra lệnh.
Nhƣ vậy, mỗi đàn không cần sự lãnh đạo những hành động phức tạp sẽ hình thành
bằng c ch phối hợp nhiều tƣơng t c đơn giản.
Việc sử dụng tr tuệ bầy đàn vào trong c c lĩnh vực từ công nghiệp, khoa học lẫn
thƣơng mại đã có nhiều ứng dụng đặc sắc và đa dạng. Nghiên cứu tr tuệ bầy đàn có
thể giúp con ngƣời quản lý những hệ thống phức tạp, từ việc vận hành c c chuyến xe
cho đến robot quân sự.
Tr tuệ bầy đàn đƣợc ứng dụng rộng rãi trong việc lập kế hoạch, tìm đƣờng đi tối
ƣu, tìm kiếm và bảo mật thông tin, hỗ trợ ra quyết định, giải tr công nghệ cao, …
Nhiều nhà nghiên cứu đã lấy cảm hứng từ sự chuyển động của động vật và côn
trùng (v dụ: đom đóm, dơi, đàn kiến và đàn ong…) với những ƣu điểm của việc t nh
to n hiệu quả và dễ thực hiện. Trong đó Grey Wolf Optimizer (GWO) mô phỏng theo
c ch mà sói tìm kiếm thức ăn và sống sót bằng c ch tr nh kẻ thù của chúng.
2.2. Mô tả hành vi săn mồi của b y sói
Chó sói xám hay Sói xám là thành viên lớn nhất trong họ Chó và cũng là loài
chó sói nổi tiếng nhất. Sói x m săn mồi theo bầy đàn nên hiệu quả săn mồi của chúng
rất cao. Nhóm của chúng có thể từ 5 đến 12 con. Đặc biệt, chúng có hệ thống phân cấp
xã hội chặt chẽ nhƣ hình 2.1.


Hình 2.1. Hệ thống phân cấp của sói xám


16

Con đầu đàn có thể là con đực hoặc con c i đƣợc gọi là alpha. Alpha nghĩa là con
dẫn đầu có nhiệm vụ quyết định về việc săn bắt, nơi ở, thời gian để đ nh thức… Các
quyết định của alpha là quyết định của cả bầy. Tuy nhiên, cũng có lúc alpha theo quyết
định của các con khác trong bầy. Khi tụ họp với nhau, toàn bộ sói thừa nhận alpha
bằng cách giữ đuôi của chúng xuống. Sói alpha cũng đƣợc gọi là con sói có sức ảnh
hƣởng lớn vì những con trong bầy luôn làm theo lệnh của nó.
Alpha không nhất thiết là con mạnh nhất của bầy nhƣng có c ch quản lý tốt nhất.
Điều này cho thấy tổ chức và kỷ luật của một bầy quan trọng hơn sức mạnh của nó.
Cấp thứ hai trong phân cấp của những con sói xám là beta. Các betas là những con
sói thƣờng trong đàn dƣới quyền alpha nhƣng cũng chỉ huy các con sói cấp thấp khác.
Sói beta có thể là ứng cử viên tốt nhất để trở thành alpha trong trƣờng hợp một trong
những con sói alpha biến mất hoặc trở nên già. Nó đóng vai trò của một cố vấn cho
alpha và thiết lập nguyên tắc cho bầy. Beta củng cố các lệnh của alpha trong bầy và
đƣa ra phản hồi về alpha.
Bậc thấp nhất trong bầy sói x m là Omega. Đó là những con sói yếu ớt và phải
dựa dẫm vào các con sói khác trong đàn. Chúng là những con sói cuối cùng đƣợc phép
ăn.
Nếu một con sói không phải là alpha, beta, hoặc omega, Sói đó đƣợc gọi là delta.
Các con sói Delta phụ thuộc vào alphas và betas, nhƣng chúng trội hơn omega. Chúng
làm nhiệm vụ theo dõi ranh giới lãnh thổ và cảnh b o trong trƣờng hợp có nguy hiểm,
bảo vệ và đảm bảo an toàn cho bầy, chăm sóc những con sói yếu, bị thƣơng trong đàn.
Ngoài hệ thống cấp bậc xã hội của sói, săn mồi theo bầy còn là một hành vi xã
hội đ ng chú ý của sói. Theo Muro và cộng sự [10] c c giai đoạn chính của việc săn
bắt nhƣ sau: rƣợt đuổi, bao vây và tấn công con mồi cho đến khi nó ngừng di chuyển
(hình 2.2).

2.3. Chi tiết thuật toán

2.3.1. Hệ thống phân cấp xã hội
Để mô phỏng toán học theo thứ bậc xã hội của sói khi thiết kế GWO, nghiên
cứu này xem xét giải pháp thích hợp là alpha (α). Do đó, c c giải pháp tốt thứ hai và
thứ ba đƣợc đặt tên là beta (β) và delta (). Phần còn lại của các giải ph p đƣợc chọn
(candidate solutions) giả định là omega (). Trong thuật toán GWO việc săn bắt (tối
ƣu hóa) đƣợc điều khiển bởi α, β, và  và sau cùng là .