Kết hợp giải thuật di truyền và tìm kiếm tabu giải bài toán tối Ưu

MỠĐẦU Giải thuật đi truyền GA là một giãi thuật tìm kiếm lời giãi của bài toán tối ưu dựa trên sự mô phông quá trình tiến hóa của tự nhiên.. Xuất phất từ một quần thể tập lời giải ban đầ

DATHOC THAINGUY - TRUONG DAIHOC CONG NGHE THONG TIN VA TRUYEN THONG

TRAN NGOC TRUONG

KET HỢP GIẢI THUAT DI TRUYEN

VA TIM KIEM TABU GIAI BAI TOAN TOI UU

LUAN VAN THAC Si KHOA HOC MAY TINH

THAI NGUYEN - 2016

TRUONG DAIHOC CONG NGHE THONG TIN VA TRUYEN THONG

TRAN NGOC TRUONG

KET HỢP GIẢI THUAT DI TRUYEN

VA TIM KIEM TABU GIAI BAI TOAN TOI UU

Chuyên ngành: Khoa học máy tính

Mã số: 60.48.01.01

LUAN VAN THAC Si KHOA HOC MAY TINH

Người hướng dẫn khoa học: TS Vũ Mạnh Xuân

THÁI NGUYÊN - 2016

này là kết quả tìm hiểu, nghiên cứu của bản thân đưới sự hướng đẫn của TS _Vũ Mạnh Xuân và tham khảo từ các nhà nghiên cứu đi trước Nội dung tham khảo, kế thừa, phát triển từ các công trình đã được công bố được trích dan, ghi rõ nguồn gốc

"Nếu có gì sai phạm tôi xin hoàn toàn chịu trách nhiệm

Người cam đoan

Trần Ngọc Trường

LỜI CẢM ƠN

“Trong quá trình thực hiện luận văn mặc đù gặp rất nhiều khó khăn nhưng tôi luôn nhận được sự quan tâm, giúp đỡ từ thầy cô, đồng nghiệp bạn b và người thân Đây là nguồn động lực giúp tôi hoàn thành luận văn này

"Tôi xin gửi lời chân thành cảm ơn tới TS Vũ Mạnh Xuân đã tận tình giúp

đỡ, hướng dẫn và chỉ bảo trong quá trình thực hiện luận văn

cô trường Đại học Công ngi

đạt những kiến thức qúy

"bầu giúp tôi hoàn thành nhiệm vụ học tập trong suốt thời gian theo học tại

Tôi xin chân thành cảm ơn tới quý thầ

thông tin và Truyền thông đã tận tỉnh chỉ bảo, truy

trường Quy thầy cô đã giúp tôi có được những kiến thức quan trọng trong Tĩnh vực Công nghệ thông tin, là nền tảng vững chắc cho những nghiên cứu của bản thân trong thời gian tới

"Tôi xin cảm ơn anh em, đông nghiệp đã giúp đỡ, ủng hộ tinh than trong thời gian tôi tham gia học tập

Cuối cùng, tôi xin cảm ơn tất cả những người đã luôn luôn quan tâm, sẻ chia va động viên tôi

Thái Nguyên, ngày —_ tháng _ năm 2016

Trần Ngọc Trường

LỠI CAM ĐOAN

LỠI CÁM ƠN

MỤC LỰC

DANH MỤC CÁC HÌNH

MỞ ĐẦU

CHƯƠNG 1: BÀI TOÁN TỐI ƯU

1.1 Giới thiệu bài toán tối ưu tổng quát

1.2 Phân loại các bài toán tối wu

1.3 Ứng đụng của lý thuyết tối ưu

1.4 Bài toán quy hoạch tuyến tính tổng quát

1.5 Bài toán vận tải tuyến tính

(CHUONG 2: GIAI THUAT DI TRUYEN VA TIM KIEM TABU

2.1 Giải thuật di truyền

2.1.3 Các bước đề áp đụng giải thuật di truyền cô điền

2.1.4 Các nguyên lý trong giải thuật di truyền

2.1.5 Ứng dụng giải thuật di truyền giải bài toán tối ưu

iv

(HUONG 3: KET HOP GIAI THUAT DI TRUYEN VA TIM KIEM

3.4 Giải bài toán vận tải sử đụng thuật giải di truyền kết hợp với tim

Hình 2.1 Sơ đồ của giải thuật đi tru)

Hình 2.2 Đồ thi ham f

Hình 3.1 Các tham số của giải thuật đi truyền

Hình 3.2 Tham số giải thuật tìm kiếm Tabu

'Hình 3.3 Giá trị lời giãi cho phần tử khởi tạo đầu tiên khi chạy lần 1

"Hình 3.4 Tham số cho lần chạy đầu tiên và kết quả

Hình 3.5 Kết quả với bài toán có đữ liệu đầu vào m = 7, n = 8

MỠĐẦU

Giải thuật đi truyền (GA) là một giãi thuật tìm kiếm lời giãi của bài toán tối ưu dựa trên sự mô phông quá trình tiến hóa của tự nhiên Xuất phất từ một quần thể (tập lời giải ban đầu), giải thuật tiến hành quá trình tiền hóa dựa trên 'ba toán tử di truyền là lai ghép (crossover), dét bién (mutation) và chọn lọc (selection) nhằm tạo ra thế hệ mới "tốt hơn” thể hệ trước đó

Tim kiém Tabu (T'S) là một kỹ thuật tìm kiếm dựa trên quy định về luật

"bài toán vận tải tuyến tính

“Nội dung luận văn được chia làm 3 chương ngoài phần Mỡ đầu và Kết luận Chương 1: Bài toán tối ưu

Chương này trình bày khái quát về các vấn đề liên quan tới các bài toán tối ưu đồng thời mô tả rõ bài toán vận tải

Chương 2: Giải thuật đi truyền và tìm kiếm Tabu

'Nội dung chương này là những nghiên cứu về giải thuật đi truyền và tim kiếm Tabu làm cơ sở cho chương 3

Chương 3: Kết hợp Giải thuật dĩ truyền va tim kiém Tabu giải bài toán vận tai

Chương này trình bây giải pháp kết hợp Giải thuật di truyễn và tìm kiếm Tabu gidi bai toin vận tải đồng thời lập trình thử nghiệm trên các bài toán cụ thể

Chương này sẽ giới thiệu tổng quan về bài toán tối tu, bài toamsquy hoạch tuyến tính tông quát, bài toán vận tãi tuyến tính Trình bày thuật toán thé vi giải bài toán vận tải bằng thuật và đưa ra kết quả Các khái niệm và kết quả trong chương này được tham khảo trong [3], [5]

1.1 Giới thiệu bài toán tối ưu tông quát

Lý thuyết tối ưu là một trong lĩnh vực kinh điển của toán học có nhiều ảnh hưởng đến nhiều lĩnh vực khoa học công nghệ, kinh tế xã hội

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 qui min (max) va 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)

Trong mô hình toán học, mục tiêu của bài toán được biểu di

A(x) + min(max)

với x là một biến hoặc vecto bién x = (Xi, Xa, Xe)

Biển x hoặc vectơ biến Xa) 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 thì được gọi là điều kiện rang bude va đượ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:

Lâm cực tiễu cực đại một hàm mục tiêu:

gọi là phwong an t6i uu Néu x chi théa man diéu kién (2) gọi x là phương án chấp nhận được hay phương án

Phuong pháp tìm GTLN (đã học trong giải tich 1) thực hiện như sau:

~ Tìm các cực trị của f(x) , tính các giá trị cực trị, tính các giá trị tại các đầu mút của miền D, sau đó so sánh để tìm ra giá trị lớn nhất (hay nhỏ nhất)

— Tim các điểm đừng Ấx) = 0 Tinh f(x) tại các điểm đừng

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

- Bà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ó đạng

- Bài toán tối ưu rời rac: khi bién hodc gia 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ị ng én,

Tối ưu đỗ thị: là một đạ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 rac

Kí hiệu: X = {A B, C, D} Tập canh E = {e1, e:, 63, es} hoặc D = {(A,D); (A,B); .) Tim đường đi ngắn nhất của đồ thị thỏa mãn điều kiện nào đô

- Bà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)

Đ®—@>—<Ð>—<4)

- Bà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

hải tối ưu trên cùng một miễn ràng buộc

(8) > min(max), i= 1,2,3, nvéix €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

1.3 Ứng dụng của lý thuyết tối ưu

Nhiều vấn đề thực tế, kinh tế, khoa học và xã hội đều có thể giải quyết

‘bing phương pháp tối ưu toán học Quan trọng là từ thực tẾ phải xây dựng.

một mô hình toán học thích hợp Tử đó sử dụng phương pháp tối ưu đễ giải cũng với công cụ thích hợp

Các bước cần thiết khi áp đụng phương pháp mô hình hóa:

Bước 1: Khão sát vấn đề thực tế, phát hiện vấn đề cần giải quyết bằng phương pháp tối ưu

"Bước 2: Phát biếu các điều kiện ràng buộc và hàm mmục tiêu đưới dạng định tính

"Bước 3: Lựa chọn các biến quy định và sau đó định lượng hóa các điều kiện rang buộc và hàm mục tiêu Từ đồ xây dựng mô hình định lượng và mô hình toán học (mô hình tối ưu)

"Bước 4: Thu thập số liệu và lựa chọn phương pháp toán học thích hợp để giải mô hình

"Bước 5: Xây đựng thuật toán và quy tình giải Lựa chọn công cụ (giấy bút, máy tính) có thể lập trình cho bài toán Ấy

Bước 6: Đánh giá kết quả thu được Nếu phù hợp thực tế nó cho kết quả tối ưu 'khi đó chứng tô mô hình chúng ta xây đựng đúng, hợp lý, vì vậy chấp nhận kết

ấu không phù hợp thực tế thì phải xem xét và điều chỉnh mô hình

‘Mot số thuật ngữ trong quá trình xây dựng mô hình:

- _ Toán ứng dụng (Applied Mathematic)

- _ Vận tri hoc (Operation Research ~OR)

- Khoa hoc quan ff (Management Science ~ MS)

- _ Quy hoạch Programming)

1.4 Bài toán quy hoạch tuyến tính tổng quát

Bài toán quy hoạch tuyến tính (QHTT) tổng quát có dạng,

~ Tìm cực đại (cực tiểu) của hàm:

Z ~ fỢX) gọi là hàm mục tiêu của bài toán, (6, 2 Xe) fa vecton thành phần (một bộ n giá trị hay còn gọi là một diém trong không gian n chiều)

"Ma trận của hệ rằng buộc có dang

D déu là một phương án, vì vậy miễn D còn gọi là tập phương án

Phương án tối tu (optimal solution) là một phương án, mà giá trị ham mục tiêu tại đồ đạt cực đại (hay cục

hiệu là X* hay X-opt

1.5 Bài toán vận tải tuyến tính

) Phương án tối ưu thường được ký:

‘Noi dung bài toán

Giả sử cần vận chuyên một loại hàng thuần nhất (vật tư, lương thực )

từ m địa điểm cung cấp (điểm phát) A¡, A; A„ đến n địa điểm tiêu thụ (điểm thu) Bị, Bà Bọ biết rằng:

b; (tổng số lượng hàng ở các điểm cung cấp bằng tông số hàng tại

Vấn đề đặt ra: Lập kế hoạch vận chuyển hàng từ các địa điểm cung cấp đến các địa điểm tiêu thụ sao cho tổng chi phí vận chuyển là nhỏ nhất và thỏa mãn nhu cầu thu phát Bài toán vận tải là tuyến tính nếu chỉ phí tỉ lệ với số lượng hàng vận tải

Ta có:

Š Š⁄,x; : tổng chỉ phí van chuyển

+, : số lượng hang cho di tA: i= 1m

3x, -s6 luong hing ché t6i tirB) j= 1.1

‘Vay mô hình toán học của bài toán là:

fx) =, Dex, — min (cực tiêu tổng chỉ phí) với các điều kiện:

>> (ạ>0,i=i.m, j= 1.n) _Với mô hình toán học của bài toán trên áp đụng phương pháp thể vị để tìm ra kết quả tối ưu

Phương pháp thể vị

Phuong án cực biên: x = {xạ} là phương án cực biên khi và chỉ khi tập hop các ô (1, ) tương ứng với các thành phần đương của phương án không tạo thành vòng Một phương án cực biên có tối đa m + n — 1 thành phần đương Tập hợp m + n — 1 6 không tạo thành vòng bao him tập ô tương ứng với các thành phần đương của phương án cực biên x (x5 > 0) gọi là tập ô cơ sở nó, ký hiệu là S Ô (¡.j) € S gọi là ô cơ sở, (ij) € S gọi là ô phí cơ sở Một ô phi cơ

sở kỷ bao giờ cũng tạo thành một vòng duy với các ô cơ sở Một phương án cực biên không suy biến chỉ có một tập ô cơ sỡ đuy nhất, đô chính

là tập ô tương ứng với các thành phần đương của phương án Một phương án

cực biên suy biến cô nhiều tập ô cơ sở khác nhau, phần chung của chúng là tập ô ứng với các thành phần đương

“Xây dựng phương án cực biên Khi xác định được x; = 0., ta nói là đã phân phối cho ô (, j) mét lượng hàng la a Nguyên tắc phân phối tối đa: Lấy ô (, j) bất kỳ của bảng và phân phối cho nó một lượng hàng tối đa có thể, nghĩa

14 dat xy = min bị

Ba tring hợp có thễ xây ra:

cầu của trạm phát thỏa mãn, loại hàng i ra khỏi bảng, đồng

axy = b , yêu cầu của trạm thu thỏa mãn, loại cột j ra khỏi bảng, đồng, thời sửa lại yêu cầu cia tram phat: a°:= ai

‘byxy = a = bị ,yêu cầu của cả trạm thu và phát đều thỏa mãn, loại đồng,

thời hàng ¡ và cộtj ra khôi bảng

Quá trình tiếp tục cho tới khi yêu cầu của mọi trạm thu và phát đều thoã

mãn Các 6 được phân phối có xy > 0, đất xạ = 0 với những ô không được

phân phối Khi đồ sẽ thu được một phương án cực biên của bài toán Nếu số ô được phân phối là m + n — 1 thì phương án cực biên thu được là không suy biển, tập ô được phân phối chính là tập 6 co sé Nếu số ô được phân phối nhỏ hon m+ n— 1 thi phương án cực biên tương ứng là suy biến Để có được một tập ô cơ sở cần phải bổ sung, ô bô sung có xụ = 0 và không tạo thành vòng với những ô cơ sở đã có, bỗ sung cho tới khi đũ m + n ~ 1 ô Với những ô bỗ sung

“khác nhau ta sẽ được các tập ô cơ sở

“Phương pháp thể vị giải bài toán vận ta:

Điều kiện cần và đủ để phương án x = {x;} của bài toán vận tải tối ưu

là tồn tại một hệ thống số {u, v;} thoả mãn:

3) vị— 0 <Gÿ (VJ)

) vị —0¿= cụ nếu xụ > 0

tủ; v; gọi là các thể vị hằng và cột

Co thé xem u; la giá trị của một đơn vị hàng hoá ở nơi sản xuất A:, còn

¡là giá trị của nô tại nơi tiêu thụ B_

Điều kiện b) cô nghĩa là trong mọi phương án vận chuyển tối ưu nếu

"hàng hoá được đưa từ trạm phát A; đến trạm thu B, thì giá trị của nó tại nơi tiêu thụ B, phải bằng giá trị tại nơi cấp A; c 1g thêm chỉ phí vận chuyén cy

Điễu kiên 2) có nghĩa là chênh lệch của gia tri hàng hod giữa nơi tiêu

t kỳ đều không vượt quá chỉ phí

thụ và nơi sẵn xuất

Thuật toán của phương pháp th

Giả sử đã biết một phương án cực biên x với tập ô cơ sở S

Bước 1: Xây dựng hệ thống thể vị {u;, v;}:

Lấy một hing i bat kỷ, cho nó một thể vị tí tùy ý Cac thé vi còn lại được xác định theo quy tắc

- Nếu hàng ¡ đã cô uụ và (1, JES thi thé vi của cột j được tính bối: vị = ti * c¡

- Nếu cột j đã có vụ và (, j)€S thi thé vi của hàng ¡ được tính bởi: 0; = vị ~ cy Quá trình tiếp tục cho tới khi xác định được toàn bộ hệ thống thể vị

Bước 2: Kiểm tra tiêu chuẩn tối ưu:

Tinh dai lượng Ag = v; — u — cạ đối với các 6 phi cơ sở ((i, j) € S)

- Néu Ag <0, v(, j)£S thì phương án tương ứng là tối ưu

~ Nếu tôn tai Ay > 0, (ta gọi là các 6 vi phạm) thì phải điều chỉnh phương án Bước 3: Điều chỉnh phương án:

Giả sit max Ay = Aw, 6 (¢, k) được lấy làm ô điều chỉnh A¿ > 0 Tim vòng V tạo bởi ô điều chỉnh với các ô cơ sỡ Trên vòng đánh đấu lẻ chẵn các

ô với 6 điều chỉnh (r, k) là ô lẽ Ký hiệu Vị, V: tương ứng là tập ô lẽ, chin trên vòng Xác dinh q= min {x5}, (.) € Ve

Kết quả của quá trình biến đôi ta được phương án cực biên mới x' tốt

"hơn x Sau điều chỉnh ô điều chỉnh trở thành ô cơ sỡ, ô ứng với q sẽ trỡ thành

ô phi cơ sỡ Đối với x` quay trở lại bước 1, quá trình lặp lại sau một số hữu

"hạn bước sẽ tìm được phương án cực biên tối tu

Vidy:

'Với bài toán vận tải đầu vào là số địa điểm cung cấp m = 3, số địa điểm tiêu thụ là n = 4, số lượng cung cấp của địa điểm 1 là 170, số lượng cung cấp của địa điểm 2 là 200, của địa điểm 3 là 180 Trong khi đó, số lượng tiêu thy của địa điểm 1 là 130, của địa điểm 2 là 160, của địa điểm 3 là 120 và địa

Do | 0 | 110} 70 |

Téng chi phi vận chuyên nhỗ nhất ở đây là: 12950

CHƯƠNG2

GIAI THUAT DI TRUYEN VA TIM KIEM TABU

Chương này sẽ giới thiệu tỗng quan về giải thuật di truyén, tim kiém Tabu: Các khái niệm, toán tử, mô hình tiễn hóa thuật toán Tabu cô điễn Các khái niệm trong chương này được tham khảo trong [1], [2] [4]

1.1 Giải thuật di truyền

211 Gi thiệu

Giải thuật đi truyền cổ điển là các kỹ thuật tìm kiếm và tối ưu hóa các

giải pháp cho vấn đề phông theo quá trình thích nghỉ tiến hóa của các quần thể sinh học dựa trên học thuyết Danvin GA là một g ¡ thuật, mục

tiêu 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

+ Các thành phần của GA

"Một thuật giãi di truyền, giải một bài toán được cho phải có năm thành phân sau:

~ _ Một cấu trúc đữ liệu ï biễu điễn không gian lời giải của bài toán

~ _ Phương pháp khởi tạo quần thê ban đầu P(0)

- _ Hàm định nghĩa độ thích nghỉ evalQ đồng vai trò môi trường,

~ _ Các phép toán di truyền: Lai ghép, đột biển, chọn lọc

~_ Các tham số thuật giải di truyền sử đụng ( kích thước quần thể, xác

suất lai, đột biến )

Điều kiện đừng của bài toán

«Cấu trúc củaGA.

13

Trong GA các cá thể (hay còn gọi là các NST) được mã hóa bởi các chuỗi nhị phân, mỗi vị trí trên chuỗi nhị phân chỉ nhận một trong hai giá trị "0" hoặc *1” Một NST trong GA có đạng như sau:

1011001001

GA cỗ điễn được 1 H Holland giới thiệu để giải bài toán tối tu:

max {f (*)% 6A), Trong đó A là một miễn trong không gian n-chiều, f(x) > 0 véi moi x

Tinh độ thích nghỉ cho các cá thể thuộc P(t)

‘While ( diéu kiện đừng chưa thöa ) do

tet Tái sinh P`() từ P(-1) ; Lãi Q(0 từ P(t) Đột biến R(t) từ P(-1) ; Chọn lọc P() từ P-1) 0 Q() U R() 0 P (0 ; End

- P°(t): Quan thé dugc tái sinh từ thể hệ trước

~ _ Q(Đ : Quần thể được lai ghép từ thế hệ trước

~ _ R(® : Quần thê được đột biến từ thể hệ trước

Quá trình tiết hóa được diễn ra trong vòng lặp while, tại thế hệ thứ t,

giải thuật duy trì một tập lời giải P (f) = {X,„ , x,} Mỗi lời giải x, được

đánh giá “4ô thích nghí” Một tập lời giải mới được xây đựng bằng cách

“chon lọc” các cá thể cô độ thích nghỉ cao hơn, ta được một tập ời giải trung

le phương pháp “iai ghóp và “đột biến” để tạo thành các lời giải mới cho thé

Điêu kiện kết thúc:

“Thoát ra quá trình tiến hóa quin thé, dựa vào bài toán mà có các cách kết thúc vấn đề khác nhau một khi đạt đến mức yêu cầu Điều kiện kết thúc vòng lặp có thể là một số thế hệ đũ lớn nào đó, hoặc độ thích nghỉ cũa các cá thé tét nhất trong các thế hệ kế tiếp nhau khác nhau không đáng kế Khi thuật toán đừng, cá thể tốt nhất trong thế hệ cuối cùng được chọn làm nghiệm cần tìm Một vải trường hợp thông thường như sau:

- Kết thúc theo kết quả: một khi đạt đến mức giá trị yêu cầu thì chấm đứt ngay quả trình thực hiện

- Kết thúc đựa vào số thế hệ: chọn số thế hệ, quá trình sẽ đừng đúng ngay số thế hệ đã qui định trước, khô

~ Tính theo thời gian: không cần biết đã bao nhiêu thế hệ hay kết quả nào, chỉ

\g cần biết kết quả như thế nào

đựa vào số giờ qui định mà kết thúc

- Tổ hợp: đùng nhiều phương án khác nhau cho vấn đề, chẳng hạn như: chạy theo số thế hệ xong sau đó đánh giá cho chạy theo kết quả, hoặc ngược lại

1.1.2 Các toán tử di truyền

Trong thuật giải đi truyền, các cá thể mới liên tục được sinh ra trong quá trình tiến hoá nhờ sự lai ghép ở thế hệ cha-me Một cá thể mới có thể mang những tính trạng của cha-rne (di truyền), cũng có thể mang những tính trạng hoàn toàn mới (đột biến) Di truyền và đột biến là hai cơ chế có vai trò quan trọng như nhau trong tiền trình tiền hoá, đù rằng đột biến xây ra với xác xuất nhỏ hơn rất nhiều so với hiện tượng đi truyền Các thuật toán tiến hoá, tuy có những diém khác biệt, nhưng đều mô phông ba toán tử cơ ban: Chon lọc, lai ghép, đột biến

2L Toán từ chọn lọc

Toán tử chọn lọc là một quá trình loại bỏ các NST kém thích nghỉ trong quản thễ Có các toán tử chọn lọc sau:

* Toán tử chọn lọc tÿ lệ: Được sit dung thường xuyên nhất trong GA

“Xác suất lựa chọn của mỗi cá thé lê thuận với giá trị độ thích hợp của nó, được tính theo công thức:

Pị =f()/Œ (= L.pop-size — kích cỡ của quần thé) goi là xác suất chọn cho mỗi nhiễm sắc thé vị

"Trong đồ: f () là hàm thích nghỉ của mỗi cá thể vị

F là tổng của các giá trị thích nghỉ của quần thê

'Việc chọn lọc cá thê nào phụ thuộc vào vị trí xác suất q; của mỗi nhiễm sắc thể vịđược tính nhu sau: = Sip;

Tế

pop- size lần;

trình chọn lọc được thực hiện bằng cách quay bánh xe Roulete

lần chọn một nhiễm sắc thể từ quần thể hiện hành vào quần thê mới theo cách sau:

~ Phát sinh ngầu nhiên một số r trong khoảng [0.1]

- Nếu r < q; thì chọn nhiễm sắc thể đầu tiên (v; ); ngược lại thì chọn nhiễm sắc thê thứ ¡, v¡ ( 2 < ï < pøp — size) sao cho q;_+ <7 < q¡

Hiển nhiên, có thể sẽ có một số nhiễm sắc thể được chọn nhiều lân

Điều này phù hợp với lý thuyết sơ đồ (Nguyễn Đình Thúc, [4]): các nhiễm sắc thể tốt nhất cô nhiêu bản sao hơn, các nhiễm sắc thê trung bình không thay đổi, các nhiễm sắc thê kém nhất thì chết đi

* Toán tữ chọn lọc cạnh tranh: Mỗi lần chọn lọc ta tiễn hành chọn ngẫu nhiên t cá thể từ quản thể hiện tại Bán sao của cá thể tốt nhất trong t cá

1

thể kể trên được sao chép vào quần thê bố mẹ Tiền hành N lần chọn như vậy

ta thu được quân thê bố mẹ Giá trị t được gọi là kích cỡ cạnh tranh

* Toản t chọn lọc xếp hang: Các cả th của quần thễ hiện tại được sắp xếp theo thứ tự giảm dần của giá trị độ thích nghi Cá thể tốt nhất được xếp thứ nhất và cá thể tôi nhất xếp cuối cùng

3.1.3.2 Toán từ lai ghép

Toán tử lai ghép là quá trnh tạo NST mới trên cơ sỡ các NST cha-

me bing cách ghép một đoạn trên NST cha mẹ với nhau Toán tử lai ghếp được gán với một xác suất pc Quá trình được mô tả như sau:

- Chọn ngẫu nhiên một cặp NST (để làm cha mẹ) trong quản thể Giả sử, 'NST cha mẹ có cùng độ đài m

- Tạo một số ngẫu nhiên trong khoảng từ 1 đến m - 1 (gọi là điểm lai ghép) Điểm lai ghép chia NST cha mẹ thành hai chuỗi con có độ đài m,, m,

Cé mét sé dang toán tử lai ghép như:

* Lai ghép mét diém (One-point Crossover)

Lai ghép một điểm là loại lai ghép đơn giản nhất, được sử đụng cả trong GA mã hoá nhị phân lẫn GA mã hoá số thực Với cặp cha mẹ X, Y

nhiền một vị trík (1

là các vectơ m chiều, toán tử lai ghép 1 diém chon ng:

k < mì tôi sinh ra 2 cá thể con theo công thức

(Xi Xe Yiet Ym )

(Yt Yk Xem Xem )

* Lai ghép đa điểm (Multi-point Crossover)

"Toán tử lai ghép đa điểm được mô tã như sau:

Chon ngẫu nhiên k điểm j¡ j (1 <= j¡ <j; < <j¿ < m), lai ghép đa điểm tạo ra cặp con (X', Y') bằng cách đánh số các đoạn [Ï,„ j:-] từ

0 trở đi, sau đó

bằng xị tại những đoạn cô số hiệu chẵn và bằng y; tại những

đoạn có số hiệu lẻ,

bằng x; tại những đoạn có số hiệu lẻ và bằng y: tại những,

đoạn cô số hiệu chân

* Lai ghép đều hay lai ghép mit na (Uniform Crossover)

'Trong lai ghép đều, ta chọn ngẫu nhiên K vị trí 1 <i <iy < <i <m

Các cá thể con X”, Y' được lập như sau:

trong tự nhiên, đột biến gen thường rất ít xảy ra Phép đột biến được mé ta như sau:

- Chọn ngẫu nhiên một NST trong quần thê

~ Tạo một số ngẫu nhiên k trong khoảng từ 1 tới m, 1 <k <m

lai ghép p,) Điều này được suy điễn bởi

'NST Vị được chọn để đột biển tại vị trí gen thứ năm, gen này hiện tại là

0, sau khi đột biến sẽ trở thành 1 Khi đồ NST v, trở thành v,

1.1.3 Các bước để áp dụng giải thuật di truyền cỗ điển

Bước 3: Tìm hàm số thích nghỉ cho vấn đề và tính hệ số thích nghỉ cho từng giải pháp (lời giã)

Bước 4: Dựa trên hệ số thích nghi của các giải pháp để thực hiện sự tạo sinh (reproduction) và biến hóa các giải pháp Các phương thức biến hóa 'bao gồm: lai ghép (crossover), đột biến (mutation)

Bước 5: Tính các hệ số thích nghỉ cho các giải pháp mới và loại bỗ những giải pháp kém nhất để chỉ còn giữ lại một số nhất định của giải pháp

Bước 6: Nếu chưa tìm được giải pháp tối ưu hay tương đối khá nhất hay chưa hết kỳ hạn Ấn định, trở lại bước 4 để tìm giải pháp mới

Bước 7: Tìm được giải pháp tối ưu hoặc niễu thời gian cho phép đã chấm đứt thì kết thúc giải thuật và báo cáo kết quả tìm được.

1.1.4 Các nguyên lý trong giải thuật di truyền

Nguyên lý xác định cấu trúc dữ liệu

Để có thể giải bài toán bằng GA cần “gen hóa” cấu trúc đữ liệu của bài toán Ta thường sử đụng một trong ba loại cấu trúc đữ liệu (CTDL) sau: chuỗi nhị phân, chuỗi số thực và cấu trúc c¿

thực thường được sử đụng hơn

Trong đó, chuỗi nhị phân và chuỗi số

* Biêu diễn gen bằng chuỗi nhị phân

'Về nguyên tắc, mọi cấu trúc đữ liệu trên tính, cuối cùng được

lỗi nhị phân Ở đây, chúng ta sử dụng chuỗi nhị phân một cách tường minh để thể hiện cấu trúc “gen” của một cá thê và để thực hiện chuyển về các chì

các thao tác lai ghép, đột biến trên cầu trúc này

Quy tắc biểu điễn gen qua chuỗi nhị phân: chọn chuỗi nhị phân ngắn nhất nhưng đủ đề thực hiện được tắt cả kiểu gen

* Biêu diễn gen bằng chuỗi số thực

Đối với những bài toán cô nhiều tham số, việc biểu điển gen bằng chuỗi nhị phân đôi lúc làm kiểu gen của cá thể trở lên phức tạp Khi đó, người ta sẽ chọn kiểu gen đưới dạng chuỗi số thực

'Quy tắc biểu diễn kiểu gen bằng chuỗi số thực :biễu diễn kiểu gen bằng chuỗi số thực phải đâm bão tiết kiệm không gian đối với từng thành phần gen

Khả năng được chọn vào quá trình sinh sản thể hệ kế tiếp đồng biến với

1g cao thì xác suất được chọn lọc

Nguyên lý đột biến lời gỉ

Để mở rộng kết quả tìm kiếm được quy định bởi thể hệ cá thể trước,

cần áp dụng các toán tir thay đổi giá trị cá thể mô phỏng hiện tượng đột biến trong sinh học

Quy tắc chọn xác suất đột biến : chọn xác suất đột biến

kích thước gen và không phụ thuộc kích thước quản thể

Tê nghịch với

1.1.5 Ứng dụng giải thuật di truyền giải bài toán tối ưu

“Xết bài toán tối ưu không ràng buộc sau:

Bài toán: Cho hâm f (%, x2) 21.5 +m sin(4ar x) + x) sin(470 2) với -3.0 Sx, $12.1 và 4.1 <x; < 5.8 Ta cần cực dai hoa him f (x, x2)

-Hình 2.2: Đô thị của hàm ƒ`

ng dụng giải thuật di truy:

Ta sẽ lần lượt trình bày về năm thành phần chính của giải thuật đi truyền đễ giải bài toán này

© Biểu diễn NST

Ta sử dụng một véc tơ nhị phân làm NST đễ biểu diễn các giá trị thực của biển xi, x2 Chiều đài của vectơ này phụ thuộc vào độ chính xác cần

có, trong ví đụ này độ chính xác cần 4 số lẽ

- Miễn của xỊ có chiều đài 15.1; điều kiện chính xác đòi hỏi đoạn

[-3.0, 12.1] cần được chia thành các khoảng có kích thước bằng nhau, ít nhất

'51000 khoảng bằng nhau Mỗi đoạn ta có thể nhận một lời

đoạn [4.1, 5.8] cần được chia thành các khoảng có kích thước bằng nhau, ít nhất 1.7 x 10000 = 17000 khoảng bằng nhau Điều này cô nghĩa là can 15 bit làm phần đầu tiên của NST

V= (by bạ bịo vì 29 < 151000 <25

Chiều đài toàn bộ NST lúc này là m= 1§ + 13 = 33 bịt

18 bít đầu tiên mã hóa xị và 15 bít còn lại mã hóa x:

Để chuyển một giá trị từ vectơ nhị phân sang giá trị xị, x; ta cần thực hiện 2 bước sau:

- Đối 18 bít đầu tiên (bạ; bụ, b) từ cơ số 2 sang cơ số 10

„ (ar big bo )2 = (Yb) 10 =%i

=o

- Tìm giá trị x1 tương ứng,

„ 15.1 x= -3.0+ Rigg 'Với -3.0 là cận đưới và 15.1 là độ dai của miễn giá trị

- Đi 15 bịt kế bys) từ cơ số 2 sang cơ số 10

‘Voi -3.0 la cin duéi va 15.1 là độ dai của miễn giá trị

Vidu

NST (010001001011010000111110010100010) tương ứng với

1.052426, 5.755330) vi (010001001011010000): = 70352,

và xị =-3.0 + 70352*15.1/2262143 =1.052426

3°; = (111110010100010); = 31906,

vax = 4.1 +31906 * 1.7 /32767 = 5.755330

+ Khéi tao quản thể ban đầu

Tién trình khởi tạo quần thê rất đơn giản: ta tạo một quần thê các NST, trong

đồ mỗi NST là một vectơ nhị phân 33 bít Tất cả 33 bít của mỗi NST đều được khởi tạo ngẫu nhiên

(Xị X:

«Hàm lượng giá

Hàm lượng giá cval của các vectơ nhị phân v chính là ham f: eval (x) = fịx)

Trong đó, NST v biểu điễn giá trị thực x như đã nôi ở trên, ham lượng giá đóng vai trò môi trường, đánh giá từng lời giải theo độ thích nghỉ của ching

Trong giai đoạn tiến hóa quân thể, ta có thể đùng 3 toán tử đi truyền

cổ điễn: chon loc, lai ghép, đột biến

- Toán tử chọn lọc: Giải mã tập NST v, và tính các giá trị x; tương ứng với (= 1, 2 popsize)

Tính giá trị hàm thích nghỉ của mỗi cá thể vụ tổng độ thích nghỉ Tính xác suất chọn lọc cho mỗi NST vi theo công thức: p: = eval (v) /F

với (4 = 1, 2 popsize) Thực hiện chọn ngẫu nhiên popsize lần bằng phương pháp bánh xe Roulete đựa trên xác suất của mỗi NST

~ Toán tử đột biến: Làm thay đổi gen trên NST với xác suất bằng tốc

độ đột biến Giả sử gen thứ 6 trong NST v; được chọn để đột biến Và đột 'biển chính là thay đổi giá trị gen này từ 0 thành 1 và ngược lại,

Ở đây, ta thấy rằng con thứ hai thích nghỉ hơn cả cha lẫn mẹ của nó

*_ Các tham số: Đối với bài toán này, ta sử đụng các tham số sau: kích thước quần thể popsize = 5 xác suất lai ghép pc = 0.25 (nghĩa là cá thể v trong quần thê có 25% cơ hội được chọn để thực hiện lai ghép), xác suất đột bién p„= 0.01 (nghĩa là 1% số bít bị đột biến)

* Các kết quả thử nghiệm: Bảng 2.3 sau đây trình bay kết quả hàm mục tiêu f sau 1000 thế hệ ta thu được quân thể sau : NST tốt nhất sau 1000 thế

2.2 Tim kiém tabu

Tabu được viết lại tit chit Taboo, Taboo mang ý nghĩa chỉ sự cắm ky trong tiếng Anh Ý tưởng chính của kỹ thuật tìm kiếm Tabu là sử đụng một danh sách lưu trữ các lời giải đã đi qua (Tabu List) dé dim bao rằng chúng ta

Tabu,

sẽ không viếng thăm một lời giải hai lần Trong giải thuat tim kié

những bước chuyên có chỉ phí hơn với lời giải hiện tại cũng vẫn chấp nhận chỉ cần nó không có trong “danh sách cấm” là danh sách các lời giải đã được viếng thăm So với giải thuật leo đôi, giải thuật tìm kiếm Tabu tiếp tục tìm kiểm trong trường hợp không: tìm ra được lời giải tốt hơn lời giải hiện tại với hi vọng sẽ vượt qua được những lời giải tối ưu cục bộ.

2

Tìm kiếm Tabu đựa trên giả thuyết vấn đề đã được giải, kết hợp chặt chẽ bộ nhớ thích nghĩ và thăm đò phân ứng (Responsve Exploration) Gidng như việc leo núi, người leo núi phải nhớ có chọn lọc các thành phần của quãng đường đi qua (sử dụng Adaptive Memory) và lập ra các lựa chọn chiến lược trên đường (sử dụng Responsve Exploration) Bộ nhớ thích nghĩ này cho phép việc tìm kiếm trong không gian lời giải một cách tiết kiệm và hiệu qu

Việc nhấn mạnh vào đặc điểm thăm đò phản ứng của tìm kiếm Tabu được hiểu rằng, đù một lựa chọn chiến lược kém thì vẫn cung cấp nhiều thông

1.2.1 Thuật toán tabu cô điện