BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
TRƢƠNG VĂN HIỀN ỨNG DỤNG GIẢI THUẬT
DI TRUYỀN GIẢI QUYẾT BÀI TOÁN TỐI
ƢU HÓA XẾP DỠ HÀNG HÓA Chuyên nghành : Khoa học máy tính
Mã số : 60.48.01

TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng - Năm 2013

Công trình đƣợc hoàn thành tại
ĐẠI HỌC ĐÀ NẴNG
doanh buôn bán, cung cấp dịch vụ phụ thuộc rất nhiều yếu tố.
.
Trong
đó, có một yếu tố quan trọng đầu tiên, đóng góp một phần rất lớn đó
là xác định đƣợc dự án xếp dỡ hàng hóa từ trong kho chuyển đến các
phƣơng tiện vận chuyển. Có rất nhiều tiêu chí đặt ra khi chọn các
phƣơng án: thuận tiện về giao thông, ít tốn thời gian, để làm sao
chi phí bốc xếp là thấp nhất từ đó thu đƣợc lợi nhuận cao nhất.
Sau khi tìm hiểu kiến thức tổng quan và thực tế tồn tại nhiều
bài toán chƣa có phƣơng pháp giải chấp nhận đƣợc hay lời giải tối
ƣu, các nhà nghiên cứu đã đề xuất một phƣơng pháp tính toán dựa
trên quan sát về quá tình tiến hoá trong tự nhiên.Phƣơng pháp tính
toán đó đƣợc gọi là tính toán tiến hóa (Evolutionary Computation).
Tính toán tiến hóa có nhiều nhánh nhỏ khác nhau, trong đó có thể kể
tới giải thuật di truyền (Genetic Algorithms).
Giải thuật di truyền đã thu hút đƣợc nhiều chú ý trong những
năm gần đây. Lớp giải thuật này đã đƣợc chứng minh là có nhiều ƣu
điểm nỗi trội so với các loại thuật toán khác đặc biệt khi áp dụng
chúng vào lớp bài toán tối ƣu - một lớp bài toán khó và có nhiều ứng
dụng trong đời sống thực tiễn.
Chính những ƣu điểm nổi bật của Giải thuật di truyền và nhu
cầu thực tế kinh doanh buôn bán lập dự án xếp dỡ hàng hóa, em
nghiên cứu về giải thuật này và thực hiện đề tài: “Ứng dụng giải
thuật di truyền giải quyết bài toán tối ưu xếp dỡ hàng hóa”. 2
2. Mục tiêu và nhiệm vụ nghiên cứu
Mục tiêu của đề tài là tìm hiểu giải thuật di truyền, xây dựng
thuật toán di truyền giải quyết bài toán tối ƣu xếp dỡ hàng hóa.

trình cài đặt thuật toán giải bài toán tối ƣu xếp dỡ hàng hóa. Thể hiện
kết quả thực nghiệm.

4
CHƢƠNG 1
CƠ SỞ LÝ THUYẾT

1.1 TỔNG QUAN VỀ GIẢI THUẬT DI TRUYỀN
1.1.1 Lịch sử phát triển
1.1.2 Ƣu và nhƣợc điểm giải thuật di truyền
1.1.3 Sơ đồ tổng thể của giải thuật di truyền
Quá trình hoạt động của giải thuật di truyền có thể đƣợc biểu
diễn bởi lƣu đồ dƣới đây:
+ Xác suất lai ghép
+ Xác suất đột biến
1.1.7. Lập trình song song và thuật toán song song
1.1.8. Thuật toán di truyền tuần tự cho bài toán tối ƣu hóa
hàm nhiều biến
1.1.9. Song song hóa giải thuật di truyền trong bài toán tối
ƣu hóa hàm nhiều biến
1.1.10. Đánh giá chƣơng trình song song với chƣơng trình
tuần tự
1.2 TỔNG QUAN VỀ BÀI TOÁN TỐI ƢU
1.2.1 Bài toán tố
i
ƣu tổng quát và phân loạ
i
a) Bài toán tối ưu tổng quát
Tối ƣu hóa là một trong những lĩnh vực kinh điển của toán học

6
có ảnh hƣởng đến hầu hết các lĩnh vực khoa học – công nghệ và kinh
tế – xã hội. Trong thực tế, việc tìm giải pháp tối ƣu cho một vấn đề
nào đó chiếm một vai trò hết sức quan trọng. Phƣơng án tối ƣu là
phƣơng án hợp lý nhất, tốt nhất, tiết kiệm chi phí, tài nguyên, nguồn
lực mà lại cho hiệu quả cao.
b) Phân loại các bài toán tối ưu
Các bài toán tối ƣu, cũng còn đƣợc gọi là các bài toán quy
hoạch toán học, đƣợc chia ra thành các lớp sau:
– Bài toán quy hoạch tuyến tính.
– Bài toán tối ƣu phi tuyến hay còn gọi là bài toán quy hoạch
phi tuyến, bao gồm cả bài toán quy hoạch lồi và bài toán quy hoạch
toàn phƣơng.

cung đƣờng (i, j).
*Các phương pháp tạo phương án xuất phát:
+Phương pháp "góc tây bắc"

+Phương pháp cước phí tối thiểu
b) Các tính chất của bài toán vận tải
Tính chất 1: Bài toán vận tải cân bằng thu phát luôn có
phƣơng án tối ƣu.
Để nghiên cứu tính chất 2 của bài toán vận tải, trƣớc hết chúng
ta xem xét các định nghĩa sau đây.
Định nghĩa 1. Một tập hợp các ô trong bảng vận tải đƣợc nói
là tạo nên một chu trình khép kín nếu có thể tìm đƣợc một đƣờng đi
khép kín xuất phát từ một ô nào đó thuộc tập hợp trên lại trở về ô
xuất phát sau khi lần lƣợt đi qua các ô khác trong tập hợp (mỗi ô đi
qua đúng một lần) dọc theo các hàng hay các cột của bảng vận tải,
bƣớc này theo hàng thì bƣớc sau phải theo cột hoặc ngƣợc lại. Nhƣ
vậy, số ô tối thiểu trong một chu trình khép kín là 4.
Định nghĩa 2. Một tập hợp một số ô của bảng vận tải đƣợc nói
là không tạo nên đƣợc một chu trình khép kín nào là một tập hợp các
ô có tính chất: không một tập con nào của nó có thể tạo nên một chu
trình khép kín.

8
Tính chất 2: Với một phƣơng án bất kỳ, số ô chọn của phƣơng
án không vƣợt quá tổng số điểm cung và cầu.
Tính chất 3: Một phƣơng án cực biên của bài toán vận tải (m
hàng và n cột) là một phƣơng án ứng với m + n– 1 ô sử dụng không
tạo nên một chu trình khép kín nào.
Tính chất 4: Nếu lƣợng cung và lƣợng cầu là số nguyên thì
bài toán có lời giải nguyên.


(1) Kho chứa bốc hết hàng:
n
j
ij
x
1
= a
i
, i= 
(2) Xe chở bốc đủ hàng:
m
i
ij
x
1
= b
j
, j= 
(3) Điều kiện cân bằng thu - phát:
n
j
j
m
i
i
ba
11
u
i
= v
j
– c
ij
,trong đó ô (i, j) là ô chọn
Chọn u
i
= 0 tại dòng bất kỳ
(2) Đặt 
ij
= v
j
– u
i
– c
ij

Nếu 
ij
≤ 0 : ta có phƣơng án tối ƣu
Nếu 
ij
> 0 : chuyển sang bƣớc 3
Bƣớc 3 : Xác định vòng điều chỉnh
(1) chọn ô vào : Max
ij
(
ij

ij
) ( 1 ≤ i ≤ m, 1≤ j ≤ n).
V=



 

  


 



Với cách biểu diễn này ta sẽ đi tìm cách diễn tả ràng buộc,
hàm lƣợng giá, cùng các toán tử di truyền tƣng ứng.
2.3.2 Hệ thống ràng buộc
Rõ ràng với mỗi lời giải khi biểu diễn bằng ma trận (mảng 2
chiều) lời giải V= (v
ij
) có thể thỏa mãn ràng buộc của bài toán
n
j
ij
v
1
= sour (i) i= 1, 2, …, m
m
i

Để mô tả cách tạo một lời giải thỏa tất cả ràng buộc, ta xây
dựng một giải thuật có tên là khoi_tao . Có thể lời giải thu đƣợc sẽ là
tối ƣu nhƣng vấn đề đó ta chƣa đề cập ở đây.
Procedurekhoi_tao ( )
Input: mảng sour(m), dest(n)
Output : mảng (v
ij
) sao cho v
ij
≥ 0 với i,j thỏa mãn ràng buộc
toàn cục
Begin
L ←{1,2,…,mx n} là danh sách các điểm chưa được xét
Repeat
Chọn ngẫu nhiên 1 số q trong L chưa được xét
Đánh dấu q đã xét
(hàng) i ← (q-1) div n +1
(cột) j ← (q-1)mod n +1
val ←min {sour(i),dest(j)}
v
ij
← val

12
sour(i) ← sour(i) – val
dest( j) ← dest(j) – val
Until ( tất cả các điểm trong L đều được thăm )
End;
2.3.5 Các toán tử di truyền
a) Đột biến

1
,
j
2
,…,j
q
}. Điều này có nghĩa là nếu i = i
r
, j = j
s
thì phần tử v
ij
đƣợc đặt
trong hàng r và cột s của ma trận W.
Bây giờ ta mới có thể gán các giá trị mới sour W(i) và dest
W(j) cho ma trận W (1 ≤ i ≤ p , 1 ≤ j ≤ q) :
sour W(i) =



1 ≤ i ≤ p
dest W(j) =



1 ≤ j ≤ q
Ta sẽ áp dụng thủ tục khoi_tao để gán các giá trị mới cho ma
trận W sao cho tất cả các ràng buộc sour W(i) và dest W(j) đƣợc thỏa
mãn. Sau đó, ta thay phần tử thích hợp của ma trận V bằng các phần
tử mới của ma trận W. Bằng cách này ta đã tạo ra đƣợc đột biến mà


/2)
+ R : theo dõi xem việc làm tròn nào ở trên là cần thiết, là ma
trận nhị phân :
R = (r
ij
) = ((v
ij
+ u
ij
) mod 2)
- Ta biến đổi ma trận R thành 2 ma trận R
1
=(t
ij
) và
R
2
=(s
ij
) sao cho R= R
1
+ R
2
và :
n
j
n
j
ij

2
:
V
3
= D + R
1

V
4
= D + R
2

2.3.6 Sơ đồ thuật toán
Bước 1: Khởi tạo
1. Đọc (sinh) dữ liệu
2. Khởi tạo quần thể
3. Sắp xếp quần thể theo thứ tự tăng dần của chi phí
4. Giữ lại cá thể tốt nhất
5. Ghi nhận cá thể tốt nhất Cbest
Bước 2: Vòng lặp chính
1. Sinh thêm cá thể qua các bƣớc lai ghép và đột biến. Nếu các
cá thể này tốt hơn cá thể tốt nhất trong quần thể cũ thì nó sẽ có mặt
trong quần thể mới.
2. Chuyển cá thể tốt nhất ở quần thể cũ sang quần thể mới
3. Sắp xếp quần thể theo thứ tự tăng dần của chi phí

14
4. Nếu cá thể tốt nhất ở quần thể mới tốt hơn CBest thì: đặt
CBest - cá thể tốt nhất này và Counter= 0; nếu không tăng biến
Counter lên l.

- PHƢƠNG ÁN XẾP DỠ (MaKho, MaXe, Soluong)
3.1.2 Mô tả cơ sở dữ liệu
Bảng kho:
STT
Khóa
Tên trƣờng
Kiểu dữ liệu
Null
Mô tả
1
PK
MaKho
vachar(5)
Not
null
Khóa chính
2

TenKho
nvarchar(50)

Tên Kho
3

SoLuong
int(4)

Số lƣợng gạo
chứa trong kho


gạo xếp
dỡ lên xe

Bảng chi phí:

STT
Khóa
Tên trƣờng
Kiểu dữ liệu
Null
Mô tả
1
PK
MaKho
vachar(5)
Not
null
Khóa
chính
2
PK
MaXe
varchar(5)

Khóa
chính, tên
xe
3

ChiPhi

MaKho
vachar(5)

Mã kho gạo
2

MaXe
varchar(5)

Mã xe vận
chuyển
3

SoLuong
int(4)

Số lƣợng
gạo từ kho
cần bốc xếp
lên xe

3.2 CẤU TRÚC DỮ LIỆU CỦA BÀI TOÁN
Bài toán đƣợc nêu ra để tìm phƣơng án xếp dỡ tối ƣu. Dữ liệu
của bài toán đƣợc biểu diễn dƣới dạng sau đây:
Dùng cấu trúc mảng một chiều biểu diễn số lƣợng gạo cung
cấp của các kho và số lƣợng gạo bốc lên các xe.
int sour[ ] ;
int dest [ ] ;
Sử dụng mảng hai chiều biểu diễn ma trận chi phí bốc xếp cho
một tấn gạo.

X1
X2
X3
X4

Xe
Kho
Kho
5
15
15
10
K1
15
10
0
20
11
K2
25
12
7
9
20
K3
5
0
14
16
18


20

Hình 3.3: Giao diện nhập chi phí bốc xếp

Cùng với các thông số của giải thuật di truyền của bài toán nhƣ
sau:

Hình 3.4: Thông số giải thuật di truyền 21
Kết quả chạy chƣơng trình:
Bảng phân phối số lƣợng xếp dỡ

Xe
Kho
X1
X2
X3
X4

K1
5

cá thể trong từng thế hệ. Rất đơn giản, ta chỉ cần chọn số thế hệvà
thế tự cá thể ở trong quần thể (đã sắp xếp theo chiều tăng dần của
tổng chi phí bốc xếp) , chọn xong nhấn vào nút Xem bên cạnh để
xem kết quả mong muốn nhƣ hình 6 bên dƣới.

Hình 3.6: Lời giải của từng thế hệ
Hơn nữa, chƣơng trình có thể thực hiện lại thuật toán trên với
bộ dữ liệu vào nhƣ cũ nhƣng với các tham số của quần thể nhƣ: số cá
thể, kích thƣớc quần thể, xác suất lai, xác suất đột biến có thể thay
đổi đƣợc bằng cách sau khi đã nhận đƣợc kết quả cuối cùng thì ta
nhấn vào nút nhập lại để thực hiện lại thuật toán.
23
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
1. Kết luận
Từ những kết quả nghiên cứu của luận văn cho phép rút ra một