(123doc) - Thuat-Toan-Bay-Dan-Pso-Giai-Thuat-Di-Truyen-Va-Ung-Dung-Giai-Cac-Bai-Toan-Toi-Uu-Da-Muc-Tieu [PDF]

Zitiervorschau

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN QUANG LẬP

THUẬT TOÁN BẦY ĐÀN PSO, GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG GIẢI CÁC BÀI TOÁN TỐI ƢU ĐA MỤC TIÊU Chuyên ngành: Khoa học máy tính Mã số: 60 48 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: TS. VŨ VINH QUANG

Thái Nguyên - 2013

i

LỜI CẢM ƠN Em xin chân thành cảm ơn Trường Đại Học Công Nghệ Thông Tin và truyền thông đã tạo điều kiện cho em thực hiện luận văn này. Em cũng xin chân thành cảm ơn tới toàn thể thầy cô giáo ở Viện công nghệ thông tin và trường Đại học công nghệ thông tin và truyền thông đã tận tình giảng dạy và hướng dẫn, trang bị cho em những kiến thức cần thiết trong quá trình thực hiện luận văn được thành công. Dựa trên sự chỉ bảo tận tình của TS. Vũ Vinh Quang dựa trên những kiến thức đã học và tìm hiểu được, em đã hoàn thành luận văn theo đúng thời gian quy định. Tuy nhiên trong quá trình thiết kế và thực hiện luận văn không tránh khỏi sai sót, do thời gian có hạn và khả năng còn hạn chế. Em mong quý thầy cô và các bạn thông cảm và có những ý kiến quý báu nhằm hoàn thiện hơn cho sản phẩm. Em xin chân thành cảm ơn! Thái nguyên, ngày 15 tháng 9 năm 2013 Học viên

Nguyễn Quang Lập

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

ii

LỜI CAM ĐOAN Em xin cam đoan luận văn tốt nghiệp: “Thuật toán bầy đàn PSO, giải thuật di truyền và ứng dụng giải các bài toán tối ưu đa mục tiêu” do em tự thực hiện dưới sự hướng dẫn của thầy giáo Vũ Vinh Quang. Các kết quả và số liệu hoàn toàn trung thực. Ngoài các tài liệu tham khảo đã dẫn ra ở cuối luận văn em đảm bảo rằng không sao chép các công trình hay luận văn tốt nghiệp của người khác. Nếu phát hiện có sự sai phạm với điều cam đoan trên, em xin hoàn toàn chịu trách nhiệm.

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

iii

MỤC LỤC LỜI CẢM ƠN ................................................................................................................ i LỜI CAM ĐOAN .......................................................................................................... ii MỤC LỤC ................................................................................................................... iii DANH MỤC CÁC BẢNG ............................................................................................. v DANH MỤC CÁC HÌNH VẼ ....................................................................................... vi MỞ ĐẦU...................................................................................................................... 1 CHƢƠNG 1: MÔ HÌNH BÀI TOÁN TỐI ƢU ............................................................ 3

1.1 Mô hình bài toán tối ưu hóa .................................................................................. 3 1.1.1 Mô hình tổng quát .............................................................................................. 3 1.1.2 Phân loại bài toán tối ưu..................................................................................... 4 1.2 Bài toán quy hoạch tuyến tính............................................................................... 4 1.3 Bài toán tối ưu đa mục tiêu ................................................................................... 6 1.3.1 Phương pháp ràng buộc...................................................................................... 6 1.3.2 Phương pháp tổng trọng số ................................................................................ 8 1.3.3 Phương pháp nhượng bộ dần ............................................................................. 8 1.3.4 Phương pháp thoả hiệp ....................................................................................... 9 1.3.5 Phương pháp tìm nghiệm có khoảng cách nhỏ nhất đến nghiệm lý tưởng ........ 9 1.3.6 Phương pháp giải theo dãy mục tiêu đã được sắp ............................................. 9 1.3.7 Phương pháp từng bước của Benayoun ........................................................... 10 1.3.8 Phương pháp trọng số ...................................................................................... 11 CHƢƠNG 2: CƠ SỞ THUẬT TOÁN DI TRUYỀN .................................................. 13

2.1 Các khái niệm cơ bản .......................................................................................... 14 2.1.1 Cá thể, nhiễm sắc thể ....................................................................................... 14 2.1.2 Quần thể ........................................................................................................... 14 2.1.3 Chọn lọc (Selection) ......................................................................................... 14 2.1.4 Lai ghép (Cross-over) ..................................................................................... 15 2.1.5 Đột biến (Mutation)......................................................................................... 15 2.1.6 Mô hình GA ..................................................................................................... 15

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

iv

2.1.7 Các tham số của GA ......................................................................................... 16 2.2 Cơ chế thực hiện GA ........................................................................................... 17 2.2.1 Mã hóa .............................................................................................................. 17 2.2.2 Khởi tạo quần thể ban đầu ................................................................................. 18 2.2.3 Xác định hàm thích nghi .................................................................................. 19 2.2.4 Cơ chế lựa chọn ................................................................................................. 19 2.2.5 Các toán tử di truyền ........................................................................................ 20 2.3. Thuật toán di truyền kinh điển ........................................................................... 22 2.3.1. Mã hóa.............................................................................................................. 22 2.3.2. Toán tử chọn lọc ............................................................................................... 23 2.3.3. Toán tử lai ghép ................................................................................................ 24 2.3.4. Toán tử đột biến ................................................................................................ 25 2.3.5. Thuật toán di truyền mã hóa số thực (RCGA) ................................................... 27 2.4 Thuật toán tối ưu bầy đàn PSO ........................................................................... 33 2.4.1 Giới thiệu.......................................................................................................... 33 2.4.2 Khái niệm về bầy đàn thông minh................................................................... 34 2.4.3 Thuật toán PSO truyền thống .......................................................................... 35 2.5 Một số kết quả cải tiến đối với PSO ............................................................... 43 CHƢƠNG 3: ỨNG DỤNG THUẬT TOÁN GA VÀ PSO CHO CÁC BÀI TOÁN THỰC TẾ .................................................................................................................. 56

3.1 Đặt vấn đề ......................................................................................................... 56 3.2 Mô hình bài toán thức ăn gia súc ...................................................................... 58 3.2.1 Yêu cầu của bài toán........................................................................................ 58 3.2.2 Dữ liệu đầu vào của bài toán ........................................................................... 58 3.3 Bài toán thực tế ................................................................................................. 61 KẾT LUẬN ................................................................................................................ 68 TÀI LIỆU THAM KHẢO .......................................................................................... 69 PHỤ LỤC .................................................................................................................. 70

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

v

DANH MỤC CÁC BẢNG Bảng 2.1: Phân tích kết quả một vài bài toán tối ưu thông dụng .............................. 53 Bảng 2.2: Kích thước quần thể và miền giá trị khởi tạo cho các bài toán tối ưu ...... 53 Bảng 3.1 Giá trị các tham số của bài toán ................................................................. 57 Bảng 3.2 Tiêu chuẩn dinh dưỡng .............................................................................. 61 Bảng 3.3 Tỉ lệ chất dinh dưỡng trong các loại nguyên liệu ...................................... 61 Bảng 3.4: Nghiệm của bài toán với một số bộ dữ liệu .............................................. 63 Bảng 3.5: Nghiệm của bài toán với một số bộ dữ liệu .............................................. 66

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

vi

DANH MỤC CÁC HÌNH VẼ Hình 2.1: Sơ đồ mô tả GA ....................................................................................................15 Hình 2.2: Lai ghép CMX ......................................................................................................30 Hình 2.3: Phân bố của x cij ...................................................................................................31 Hình 2.4: Toán tử lai ghép SX ..............................................................................................32 Hình 2.5: Mô tả cách thức tìm kiếm thức ăn của bầy kiến ...................................................34 Hình 2.6: Mô tả cách thức tìm đường của đàn chim.............................................................35 Hình 2.7: Bầy đàn với 10 cá thể trong không gian tìm kiếm 2 chiều ...................................36 Hình 2.8: Quan hệ vị trí – vận tốc trong không gian 2 chiều................................................37 Hình 2.9: Một bầy đàn toàn cục và lân cận cục bộ ...............................................................38 Hình 2.10: Các topology lân cận đơn giản ...........................................................................38 Hình 2.11:Chuyển động của cá thể .......................................................................................42 Hình 2.12: Áp dụng kỹ thuật làm lệch cho hàm (2.13) tại điểm x*

4.60095589 , với λ=1 ....46

Hình 2.13 Áp dụng kỹ thuật làm lệch cho hàm (2.13) tại điểm x*

4.60095589 ,với λ=10 ...46

Hình 2.14:Áp dụng kỹ thuật làm lệch cho hàm (2.13) tại điểm x*

4.60095589 ,với λ=0.1. ..47

Hình 2.15: Áp dụng kỹ thuật làm lệch cho hàm (2.14) tại điểm x*

( ) , với λ=1 .....................47 2

Hình 2.16: Áp dụng kỹ thuật làm lệch cho hàm (2.14) tại điểm x* Hình 2.17: Áp dụng kỹ thuật làm lệch cho hàm (2.14) tại điểm x*

2

2

,với λ=10 ..............48

, với λ=0.1 ...................48

Hình 2.18: Đồ thị của hàm Levy No.5 trong khối [-2,2]2 .....................................................50 Hình 2.19: Giai đoạn đầu G(x) của kỹ thuật kéo giãn cho hàm Levy No.5 trong khối [-2,2]2 ........50 Hình 2.20: Hàm Levy No.5 trong khối [-2,2]2 sau giai đoạn hai H(x) của kỹ thuật kéo giãn ........51 Hình 3.1: Kết quả bài toán khi sử dụng thuật toán GA – Test 2...........................................64 Hình 3.2 Kết quả giải bài toán khi sử dụng thuật toán PSO – Test 2 ...................................66

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

1

MỞ ĐẦU Trong thực tế, rất nhiều ngành khoa học phải giải quyết các bài toán tối ưu đa mục tiêu đặc biệt là trong ngành kinh tế. Chẳng hạn, người chế tạo sản phẩm thường phải đưa ra phương án sao cho vừa tiết kiệm vật liệu, chi phí sản xuất thấp và lại muốn giá trị sản phẩm là cao nhất. Nghiên cứu giải bài toán tối ưu đa mục tiêu là một vấn đề không đơn giản vì chưa chắc có lời giải thỏa mãn đồng thời các mục tiêu đặt ra (thường là các mục tiêu đối nghịch như ví dụ trên) mà không vi phạm các ràng buộc nào đó. Đã có nhiều phương pháp giải bài toán tối ưu đa mục tiêu được đề xuất, việc nghiên cứu phát triển các phương pháp này và ứng dụng chúng để giải quyết các bài toán thực tế là một vấn đề đang được quan tâm. Trong nhiều bài toán tối ưu thực tế, việc trọng tâm là tìm vị trí cực tiểu toàn cục của hàm mục tiêu giá trị thực f: E

R, nghĩa là tìm điểm x* E sao cho

f ( x* )

với tập đóng E

f ( x), x

E

R d , trong đó d là số chiều.

Đã có nhiều phương pháp tối ưu toàn cục (Global Optimization - GO) được phát triển để giải quyết vấn đề như trên như: Mô phỏng việc luyện thép (Simulated Annealing), Tabu search, Tính toán tiến hóa (Evolutionary computation). Về mặt lý thuyết tổng quát, các phương pháp GO có tính hội tụ mạnh, hay ít ra về nguyên tắc cũng dễ hiểu trong việc thực hiện và ứng dụng. Tính toán tiến hóa (Evolutionary computation) là kỹ thuật đặc biệt trong số các phương pháp GO. Phương pháp này làm việc trên một tập hợp những lời giải tiềm năng, được gọi là quần thể (population) và tìm lời giải tối ưu thông qua việc cộng tác và cạnh tranh giữa các lời giải tiềm năng. Thường được sử dụng nhất là các thuật toán di truyền (Genetic Algorithms – GA) và Artificial Life, dựa trên sự tiến hóa tự nhiên và cư xử xã hội. Các phương pháp này thường có thể tìm tốt nhất trong các bài toán tối ưu phức tạp với các phương pháp tối ưu truyền thống. Thuật toán tối ưu Particle Swarm Optimization (PSO) được R.C.Eberhat và J.Kennedy đề nghị năm 1995. Từ lúc ra đời đến nay PSO đã được nhiều nhà khoa Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

2

học tham gia nghiên cứu, cải tiến và ứng dụng nó để giải nhiều bài toán lý thuyết và thực tế. Đề tài “Thuật toán bầy đàn PSO, giải thuật di truyền và ứng dụng giải các bài toán tối ưu đa mục tiêu” nhằm tìm hiểu khả năng ứng dụng của thuật toán PSO, GA trong việc giải quyết các bài toán tối ưu đa mục tiêu trong thực tế. Với mục đích đó, đề tài tập trung trình bày về việc giải bài toán tối ưu bằng giải thuật PSO, GA và thực nghiệm về khả năng ứng dụng thực tế của hai thuật toán này. Nội dung đề tài gồm 3 chƣơng: Chương 1: Mô hình bài toán tối ưu đa mục tiêu. Chương 2: Cơ sở thuật toán di truyền.

Chương 3: Ứng dụng thuật toán GA, và PSO cho các bài toán thực tế. Trong luận văn, các kết quả thực nghiệm được thực hiện bằng các chương trình viết trên nền Matlab version 7.0.

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

3

CHƢƠNG 1

MÔ HÌNH BÀI TOÁN TỐI ƢU Trong chương này, luận văn sẽ trình bày một số kiến thức cơ bản về mô hình tổng quát của bài toán tối ưu hóa, việc phân loại các bài toán tối ưu và một số phương pháp giải bài toán tối ưu đa mục tiêu, các kiến thức của chương này được tham khảo từ các tài liệu [1,2]. 1.1 Mô hình bài toán tối ƣu hóa 1.1.1 Mô hình tổng quát 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ệ và 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ị, người 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. Bài toán tối ưu tổng quát được phát biểu như sau: Cực đại hóa (cực tiểu hóa) hàm: f (X )

max(min)

Với các điều kiện: gi ( X ) bi , i

J1

(1.1)

g j ( X ) bj , j

J2

(1.2)

g k ( X ) bk , k

J3

(1.3)

x1 , x2 ,..., xn

(1.4)

0.

Trong đó f ( X ) được gọi là hàm mục tiêu, Các điều kiện (1.1) được gọi là ràng buộc đẳng thức. Các điều kiện (1.2), (1.3) được gọi là ràng buộc bất đẳng thức. Các điều kiện (1.4) được gọi là ràng buộc về dấu. X

( x1 , x2 ,..., xn ) là véc tơ thuộc

không gian R n . Tập các véc tơ X thỏa mãn hệ ràng buộc lập nên một miền D được

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

4

gọi là miền phương án (hay miền chấp nhận được), mỗi điểm X D gọi là một phương án. Một phương án X * D làm cho hàm mục tiêu f ( X ) đạt max (min) được gọi là phương án tối ưu. 1.1.2 Phân loại bài toán tối ưu Dựa trên mô hình tổng quát, người ta thường phân loại lớp các bài toán tối ưu như sau: Qui hoạch tuyến tính: là những bài toán mà hàm mục tiêu f ( X ) và tất cả các hàm ràng buộc gi ( X ), g j ( X ), gk ( X ) là tuyến tính. Qui hoạch phi tuyến: là những bài toán một trong hàm mục tiêu f ( X ) hoặc các hàm ràng buộc gi X , g j X , g k X là phi tuyến. Qui hoạch lồi: Là các bài toán qui hoạch mà các hàm mục tiêu f ( X ) là lồi trên tập các ràng buộc D lồi. Qui hoạch lõm: Là các bài toán qui hoạch mà các hàm mục tiêu f ( X ) là lõm trên tập các ràng buộc D lõm. Qui hoạch rời rạc: Bài toán tối ưu được gọi là qui hoạch rời rạc nếu miền ràng buộc D là tập hợp rời rạc. Trong trường hợp riêng khi các biến chỉ nhận giá trị nguyên thì ta có qui hoạch nguyên. Qui hoạch đa mục tiêu: Nếu trên cùng một miền ràng buộc ta xét đồng thời các hàm mục tiêu khác nhau. Trong các lĩnh vực kinh tế kỹ thuật thì qui hoạch phi tuyến, qui hoạch tuyến tính là những bài toán thường gặp. 1.2 Bài toán quy hoạch tuyến tính Từ một số các mô hình trong thực tế, ta có mô hình tổng quát cho bài toán quy hoạch tuyến tính như sau: Xác định các biến x j ( j 1, 2,..., n) sao cho: n

F ( x)

cj x j

Max( Min)

j 1 n

aij x j

bi i

I1

M

j 1

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

(1.5)

5

n

aij x j

bi i

I2

(1.6)

M \ I1

j 1

xj

Với

M

Vectơ X

0( j

J

1, 2,..., m , N

(1.7)

N)

1, 2,..., n

x1 , x2 ,..., xn thỏa mãn các điều kiện (1.5) - (1.7) được gọi là một

phương án của bài toán. Tập các nghiệm thỏa mãn hệ ràng buộc được gọi là miền phương án ký hiệu là D . Phương án thỏa mãn điều kiện để hàm mục tiêu đạt Max(min) được gọi là phương án tối ưu. Dạng chính tắc: n

F ( x)

cj x j

Min

j 1 n

aij x j

bi i

M

j 1

xj

0( j

N)

Dạng chuẩn tắc: n

F ( x)

cj x j

Min

j 1 n

aij x j

bi i

M

j 1

xj

0( j

N)

Sử dụng các ký hiệu vectơ và ma trận, mô hình bài toán quy hoạch tuyến tính tổng quát được biểu diễn như sau: f X

CT X AX X

Max(min)

b 0

Trong đó: X ( x1, x2 ,..., xn ), C (c1, c2 ,..., cn )

A

a11 a21 ... am1

Số hóa bởi trung tâm học liệu

a12 a22

... a1n ... a2 n

am 2 ... amn

x1

,X

x2 ... xn

b1

,b

b2 ... bm

http://www.lrc.tnu.edu.vn/

6

1.3 Bài toán tối ƣu đa mục tiêu Trong các bài toán kinh tế, kỹ thuật, khoa học công nghệ, ... nảy sinh từ thực tế, chúng ta phải xem xét tối ưu hóa đồng thời nhiều mục tiêu. Việc làm tốt hơn mục tiêu này thường dẫn tới việc làm xấu đi một số mục tiêu khác (nghĩa là không có lời giải nào tối ưu theo mọi mục tiêu). Như vậy, chúng ta cần phải tối ưu hóa (cực đại hóa hoặc cực tiểu hóa tùy theo tình huống cụ thể) không phải là chỉ một mục tiêu nào đó, mà là đồng thời tất cả các mục tiêu đã đặt ra thường là không tương thích với nhau. Xét mô hình tổng quát

F (X ) = (f1(X ), f2(X ),..., fn (X )) ® Min (M ax), G (X ) > = (= , < = ) 0.

(1.8)

Trong đó + F (X ) được gọi là hàm mục tiêu + G (X ) được gọi là các biểu thức ràng buộc + X là phương án của bài toán Tập tất cả các phương án thỏa mãn hệ điều kiện ràng buộc được gọi là miền phương án, phương án thỏa mãn điều kiện để F (X ) ® Min (Max) được gọi là phương án tối ưu. Rõ ràng so đối với bài toán tối ưu 1 mục tiêu, việc tìm nghiệm của bài toán tối ưu nhiều mục tiêu khó khăn hơn rất nhiều và đại đa số, chúng ta không thể xác định được phương án tối ưu thật sự. Sau đây chúng ta sẽ nghiên cứu một số phương pháp giải bài toán tối ưu đa mục tiêu. 1.3.1 Phương pháp ràng buộc Xét bài toán

F (X ) = (f1(X ), f2 (X ),..., f p (X )) ® Min , G (X ) > = (= , < = ) 0.

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

7

Ta chuyển bài toán trên về bài toán

fh (X ) ® M ax, fk (X ) ³ Lk , k = 1, 2,..., h - 1, h, h + 1,..., p. Trong đó mục tiêu thứ h được chọn tùy ý để lấy Max . Như vậy bài toán đa mục tiêu đã được chuyển về bài toán đơn mục tiêu và có thể áp dụng các thuật toán thông thường ví dụ như thuật toán đơn hình. Thuật toán trên được giải bằng phương pháp xây dựng bảng thỏa hiệp các hàm mục tiêu và từ đó xác định phương án tối ưu. Thuật toán: Bước 1: Xây dựng bảng thỏa hiệp + Giải lần lượt p các bài toán đơn mục tiêu tương ứng với các ràng buộc. Gọi

(

)

nghiệm của mục tiêu thứ k là x k = x 1k ,..., x nk , k = 1, 2,..., p . Sau đó tính giá trị của p hàm mục tiêu đạt được tại các x k

tương ứng. Kí hiệu là

f1(x 1k ), f2 (x 2k ),..., f p (x pk ) . + Sắp xếp p giá trị ứng với p mục tiêu vừa tính được ở trên vào bảng thỏa hiệp. ……

f p (x k )

f1(x k )

f2 (x k )

x1

f1(x 1 )

f2 (x 1 )

f p (x 1 )

x2

f1(x 2 )

f2 (x 2 )

f p (x 2 )

….

….

….

….

xp

f1(x p )

f2 (x p )

f p (x p )

+ Xác định số lớn nhất và nhỏ nhất trọng cột thứ k, kí hiệu lần lượt là

M k , m k ,(k = 1, 2,..., p). Bước 2: Quy ước một bài toán đa mục tiêu tương ứng với bài toán một mục tiêu Bước 3: Chọn giá trị L k với k ¹ h trong đoạn éêm k , M k ù ú ë û bằng cách chia đoạn éêm k , M k ù ú ra r phần bằng nhau. Khi đó L k có thể nhận 1 trong r giá trị sau

ë

û

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

8

Lk = n k +

t (M - m k ), t = 0,1, 2,..., r - 1 . r- 1 k

Bước 4: Ứng với mỗi giá trị của L k , ta giải bài toán đơn mục tiêu tương ứng và mỗi bài toán cho một nghiệm chấp nhận được. Trong những nghiệm này ta sẽ chọn nghiệm tối ưu nhất. 1.3.2 Phương pháp tổng trọng số

F (X ) = (f1(X ), f2 (X ),..., f p (X )) ® Min , G (X ) > = (= , < = ) 0. Ta chuyển bài toán trên thành bài toán

F (X ) = w1 f1(X ) + w2 f2(X ) + ... + w p f p (X ) ® Min , G (X ) > = (= , < = ) 0. p

Trong đó wi ³ 0,(i = 1, 2,..., p),

å

wi = 1.

i= 1

1.3.3 Phương pháp nhượng bộ dần Bước 1: Giải k bài toán 1 mục tiêu riêng rẽ, sau đó lập bảng thưởng phạt Bước 2: Căn cứ vào bảng thưởng phạt, với giá trị Y 10 , ta buộc Y 1 nhượng bộ một lượng D Y 1 và giải bài toán:

M axY 2(X ) với X Î D;Y 1(X ) ³ Y 10 - D Y 1 Giả sử Y 2* là giá trị tối ưu của bài toán này, chuyển sang bước 3 Bước 3: Căn cứ vào Y 20 và Y 2* buộc Y 2 nhượng bộ lượng D Y 2 và giải bài toán:

M axY 3 (X ) với X Î D ;Y 1(X ) ³ Y 10 - D Y 1;Y 2 (X ) ³ Y 2* - D Y 2 ; Giả sử Y 3* là giá trị tối ưu của bài toán này, chuyển sang bước tiếp ………….. Bước k: Căn cứ vào Y k0- 1 và Y k*- 1 buộc Yk-1 nhượng bộ lượng D Y k - 1 và giải bài toán:

M axY k (X ) với X Î D ;Y 1(X ) ³ Y 10 - D Y 1;Y 2 (X ) ³ Y 2* - D Y 2 ;...;Y k - 1(X ) ³ Y k*- 1 - D Y k - 1; Nghiệm của bài toán cuối cùng này được lấy làm nghiệm của bài toán ban đầu.

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

9

1.3.4 Phương pháp thoả hiệp Bước 1: Giải k bài toán 1 mục tiêu riêng rẽ, giả sử nghiệm tối ưu là

X i (i = 1, 2,...k ) . Đặt M i = Y i (X i ) và đưa vào biến phụ w : M i - Y i (X i ) £ W với mọi i = 1, 2,..., k . Mi

Vế trái trong công thức trên gọi là độ lệch tương đối chung Bước 2: Giải bài toán Min (w) với X Î D từ đó tìm được nghiệm tối ưu X opt và

wopt Trong trường hợp này, lợi ích tỷ lệ với độ lệch tương đối, phương án X 1 là tốt hơn X 2 nếu độ lệch tương đối chung của X 1 nhỏ hơn của X 2 . 1.3.5 Phương pháp tìm nghiệm có khoảng cách nhỏ nhất đến nghiệm lý tưởng Phương pháp này giả định có một nghiệm lý tưởng, X 1 là tốt hơn X 2 nếu khoảng cách từ X 1 đến nghiệm lý tưởng nhỏ hơn khoảng cách tương ứng của X 2 Định nghĩa: Giả sử X 1 , X 2 Î Rn, khoảng cách giữa X 1 và X 2 là số da xác định bởi da =

å

X 1i - X 2i

a

a là tham số a >1

Khi đó bài toán Max(Y (X )) với X Î D đưa về bài toán min

{å

Y i (X ) - Y i *

a

}

Vấn đề xác định tham số a phụ thuộc vào từng bài toán. 1.3.6 Phương pháp giải theo dãy mục tiêu đã được sắp Trong phương pháp này, thứ tự của các hàm mục tiêu thể hiện sự quan trọng của các tiêu chuẩn, các mục tiêu xếp trước được ưu tiên hơn. Bước 0: Sắp xếp thứ tự các mục tiêu Y 1,Y 2,...,Y k Bước 1: Giải bài toán M ax(Y 1(X )) với X Î D , ký hiệu D 1 = {X 1 Y 1(X 1 ) = m axY1(X ), X Î D } Í D

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

10

Bước 2: Giải bài toán M ax(Y 2(X )) với X Î D 1 , ký hiệu

{

}

D 2 = X 2 Y 2 (X 2 ) = m axY2 (X ), X Î D 1 Í D 1

….. Bước k: Giải bài toán M ax(Y k (X )) với X Î D k - 1 , ký hiệu

{

}

D k = X k Y k (X k ) = m axYk (X ), X Î D k - 1 Í D k - 1

Ta có dãy bao hàm thức: D Ê D 1 Ê ... Ê D k . Khi đó tập các nghiệm thuộc D k sẽ thỏa mãn tính chất tối ưu của bài toán đa mục tiêu. 1.3.7 Phương pháp từng bước của Benayoun Phương pháp này gần giống phương pháp tìm nghiệm xấp xỉ nghiệm lý tưởng. Thường có hai biến dạng sau: -

Các độ lệch tương đối của hàm mục tiêu được gắn với một bộ trọng số. Trọng số này được xác định dựa trên khoảng biến động của từng mục tiêu.

-

Miền chấp nhận được của nó có thể thay đổi qua các bước giải

Hàm lợi ích và các quan hệ xác định như phương pháp tìm nghiệm xấp xỉ nghiệm lý tưởng. Bài toán cơ bản mà phương pháp này xét là:

Õ

i

M i - Y i (X ) £ da*

X Î Di trong đó M i = M ax(Y i (X ))

Thuật toán như sau: Bước 1: Tính thưởng phạt, xác định M i , m i ở cột thứ i

M i = M ax(Y i (X )) , m i = Min (Y i (X )) Bước 2: Tìm các trọng số, xác định a i để tính i

M i mi * M1

Õ

i

:

1 n

(C1j ) 2 j 1

Với C ij là các hệ số của hàm mục tiêu thứ i. Đặt i=0 chuyển sang bước 3

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

11

Bước 3: Tính 1 1 i

Bước 4: Giả sử nghiệm của bài toán thứ i là X (i ) và i £ k - 1 Xét các trường hợp: 1) Nếu chấp nhận X (i ) thì kết thúc. 2) Nếu không chấp nhận X (i ) và i £ k - 1 thì chuyển Bước 5 3) Nếu không chấp nhận X (i ) và i = k thì tìm phương án giải khác. Bước 5: Phân tích kết quả và tìm ra mục tiêu i * có thể nhượng bộ, cho nhượng bộ một lượng D i* chuyển Bước 6 Bước 6: Xác định miền chấp nhận mới D i + 1 Di

X

1

i ¹ i*

YI ( X ) YI X (i ) YI ( X ) YI * X (i )

Coi

I*

0

I*

* i

0

Với i ¹ i * thì tính

i

theo công thức trên.

i = i + 1. Chuyển về Bước 3 Thuật toán kết thúc sau k lần lặp 1.3.8 Phương pháp trọng số Trong phương pháp này hàm lợi ích U tuyến tính theo các giá trị của phương án U (Y ( X ))

p; Y ( X )

piYi ( X )

Bài toán quy hoạch đa mục tiêu ở dạng này là: max

piYi ( X ) với

pi (i = 1, 2,..., k ) là các trọng số; thường xét với pi không âm và

Số hóa bởi trung tâm học liệu

pi

1.

http://www.lrc.tnu.edu.vn/

12

Về mặt thực tiễn, có thể xem các trọng số pi là tỷ lệ quy đổi thứ nguyên của mục tiêu thứ i. Chẳng hạn quy đổi tất cả các mục tiêu về dạng tiền tệ thì pi biểu hiện cho số đơn vị tiền tệ của mục tiêu thứ i. Đây cũng là phương pháp quy đa mục tiêu về một mục tiêu phụ thuộc tham số. Kết luận: Nội dung chương 1 đã trình bày một số kiến thức cơ bản về mô hình của bài toán tối ưu tổng quát, mô hình của bài toán tối ưu đa mục tiêu cùng một số phương pháp giải. Các kiến thức này là cơ sở để trình bày các kết quả trong chương 2 và chương 3 của luận văn.

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

13

CHƢƠNG 2

CƠ SỞ THUẬT TOÁN DI TRUYỀN Trong chương 2, luận văn sẽ trình bày các kiến thức cơ bản về lĩnh vực tính toán mềm bao gồm thuật toán di truyền (GA) và thuật toán bầy đàn (PSO) giải các bài toán đa mục tiêu. Các kiến thức về các thuật toán này được tham khảo từ các tài liệu [3, 4, 5, 6, 7, 8, 9, 10].

Mở đầu Trong công nghệ thông tin, GA là một thành phần của Tính toán tiến hóa (Evolutionary computation – EC), một lĩnh vực được coi là có tốc độ phát triển nhanh của trí tuệ nhân tạo. Có thể chia EC thành 5 hướng nghiên cứu như sau : - GA (Genetic Algorithm - GA): Dựa vào quá trình di truyền trong tự nhiên để cải tiến lời giải qua các thế hệ bắt nguồn từ một tập các lời giải ban đầu. - Quy hoạch tiến hoá (Evolutionary Programming - EP): Dựa vào quy luật tiến hoá, tìm phương pháp kết hợp đủ khả năng giải quyết trọn vẹn một bài toán từ một lớp các phương pháp giải quyết được một số phần của bài toán. - Các chiến lƣợc tiến hoá (Evolutionary Strategies - ES): Dựa trên một số chiến lược ban đầu, tiến hoá để tạo ra những chiến lược mới phù hợp với môi trường thực tế một cách tốt nhất. - Lập trình di truyền (Genetic Programming - GP): Mở rộng GA trong lĩnh vực các chương trình của máy tính. Mục đích của nó là để sinh ra một cách tự động các chương trình máy tính giải quyết một cách tối ưu một vấn đề cụ thể. - Các hệ thống phân loại (Classifier Systems- CS): Các GA đặc biệt được dùng trong việc học máy và việc phát hiện các quy tắc trong các hệ dựa trên các quy tắc. GA cũng như các thuật toán tiến hoá đều được hình thành dựa trên một quan niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm "Quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu". Quá trình tiến hoá thể hiện tính tối ưu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước. Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

14

Sự hình thành và phát triển của GA trên thế giới có thể được điểm qua các mốc thời gian quan trọng như sau: Năm 1960, ý tưởng đầu tiên về Tính toán tiến hoá được Rechenberg giới thiệu trong công trình “Evolution Strategies” (Các chiến lược tiến hoá). Ý tưởng này sau đó được nhiều nhà nghiên cứu phát triển. Năm 1975, Giải thuật gen do John Holland phát minh và được phát triển bởi ông cùng với các đồng nghiệp và những sinh viên. Cuốn sách "Adaption in Natural and Artificial Systems" (Sự thích nghi trong các hệ tự nhiên và nhân tạo) đã tổng hợp các kết quả của quá trình nghiên cứu và phát triển đó. Năm 1992, John Koza đã dùng GA để xây dựng các chương trình giải quyết một số bài toán và gọi phương pháp này là “lập trình gen”. Ngày nay GA càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu hoá, một lĩnh vực có nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng thường khó và chưa có giải thuật hiệu quả để giải . 2.1 Các khái niệm cơ bản 2.1.1 Cá thể, nhiễm sắc thể Trong GA, một cá thể biểu diễn một phương án của bài toán. Trong trường hợp tổng quát, một cá thể có nhiều NST (NST), ở đây ta quan niệm một cá thể chỉ có một NST. Do đó khái niệm cá thể và NST trong GA coi như là tương đương. Một NST được tạo thành từ nhiều gen, mỗi gen có thể có các giá trị khác nhau để quy định một tính trạng nào đó. Trong GA, một gen được coi như một phần tử trong chuỗi NST. 2.1.2 Quần thể Quần thể là một tập hợp các cá thể có cùng một số đặc điểm nào đấy. Trong GA ta quan niệm quần thể là một tập các lời giải của một bài toán. 2.1.3 Chọn lọc (Selection) Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay đổi các cá thể trong quần thể. Những cá thể tốt, thích nghi được với điều kiện sống thì có khả năng đấu tranh lớn hơn, do đó có thể tồn tại và sinh sản. Các cá thể không thích Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

15

nghi được với điều kiện sống thì dần mất đi. Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh sinh tồn trong tự nhiên, chọn lựa các cá thể trong GA chính là cách chọn các cá thể có độ thích nghi tốt để đưa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục đích là sinh ra các cá thể mới tốt hơn. Có nhiều cách để lựa chọn nhưng cuối cùng đều nhằm đáp ứng mục tiêu là các cá thể tốt sẽ có khả năng được chọn cao hơn. 2.1.4 Lai ghép (Cross-over) Lai ghép trong tự nhiên là sự kết hợp các tính trạng của bố mẹ để sinh ra thế hệ con. Trong GA, lai ghép được coi là một sự tổ hợp lại các tính chất (thành phần) trong hai lời giải cha mẹ nào đó để sinh ra một lời giải mới mà có đặc tính mong muốn là tốt hơn thế hệ cha mẹ. Đây là một quá trình xảy ra chủ yếu trong GA. 2.1.5 Đột biến (Mutation) Đột biến là một sự biến đổi tại một (hay một số) gen của NST ban đầu để tạo ra một NST mới. Đột biến có xác suất xảy ra thấp hơn lai ghép. Đột biến có thể tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban đầu. Tuy nhiên trong GA thì ta luôn muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua từng thế hệ. 2.1.6 Mô hình GA Với các khái niệm được giới thiệu ở trên, GA được mô tả bởi sơ đồ sau đây Bắt đầu

Nhận các tham số của bài toán

Khởi tạo quần thể ban đầu

Tính giá trị thích nghi

Điều kiện dừng

Sinh sản

Lai ghép

Lựa chọn giải pháp tốt nhất

Đột biến

Kết thúc

Hình 2.1: Sơ đồ mô tả GA Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

16

1. Xác lập các tham số ban đầu của bài toán. 2. Khởi tạo: Sinh ngẫu nhiên một quần thể gồm n cá thể (là n lời giải ban đầu của bài toán). 3. Xác lập quần thể mới: tạo quần thể mới bằng cách lặp lại các bước sau cho đến khi quần thể mới hoàn thành, bao gồm: 3.1 Tính độ thích nghi của mỗi cá thể. 3.2 Kiểm tra điều kiện kết thúc giải thuật. 3.3 Chọn lọc các cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn). 3.4 Tiến hành lai ghép các cặp bố-mẹ với một xác suất lai ghép được chọn để tạo ra một cá thể mới. 3.5 Tiến hành đột biến với xác suất đột biến được chọn xác định cá thể đột biến. 4. Kiểm tra điều kiện dừng: Nếu điều kiện được thỏa mãn thì thuật toán kết thúc và trả về lời giải tốt nhất chính là quần thể hiện tại. 2.1.7 Các tham số của GA 1. Kích thƣớc quần thể Kích thước quần thể cho biết có bao nhiêu cá thể trong một quần thể (trong một thế hệ). Qua các nghiên cứu cũng như các thử nghiệm đã cho thấy kích thước quần thể không nên quá bé cũng như không quá lớn. Nếu có quá ít cá thể thì ít có khả năng thực hiện lai giống và chỉ một phần nhỏ không gian tìm kiếm được dùng. Như vậy sẽ dễ xảy ra trường hợp bỏ qua các lời giải tốt. Nhưng quá nhiều cá thể cũng không tốt vì GA sẽ chạy chậm đi, ảnh hưởng đến hiệu quả của giải thuật. Các nghiên cứu cũng đã chỉ ra không có lợi khi tăng kích thước quần thể lên quá một giới hạn cho phép. 2. Xác suất lai ghép Xác suất lai ghép cho biết việc lai ghép tạo ra thế hệ mới được thực hiện thường xuyên như thế nào. Nếu xác suất lai ghép là pc, khi đó khả năng để một cá thể được lai ghép là pc. Nếu không thực hiện lai ghép, con sinh ra sẽ giống hoàn toàn bố mẹ. Nếu được lai ghép, con sinh ra sẽ có một phần giống bố và một phần giống mẹ. Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

17

3. Xác suất đột biến Xác suất đột biến cho biết các gen của NST thay đổi thường xuyên như thế nào. Nếu xác suất đột biến là pm, khi đó khả năng để mỗi gen của một NST bất kỳ bị đột biến là pm. Toán tử đột biến có tác dụng ngăn ngừa GA rơi vào tình trạng cực trị địa phương, tuy nhiên nếu thực hiện đột biến với xác suất quá cao sẽ biến GA thành giải thuật tìm kiếm ngẫu nhiên. Nhận xét: Xuất phát từ sơ đồ thực hiện GA, chúng ta có thể có một số nhận xét như sau: + GA lập luận mang tính chất ngẫu nhiên để tìm giải pháp tối ưu cho những vấn đề phức tạp, thay vì xác định như toán học giải tích. Tuy nhiên đây là hình thức ngẫu nhiên có hướng dẫn bởi trị số thích nghi. Chính hàm thích nghi giúp GA tìm giải pháp tối ưu trong rất nhiều giải pháp có thể có. + GA không để ý đến chi tiết vấn đề, trái lại chỉ chú ý đến giải pháp cho vấn đề, hay tìm điều kiện tối ưu cho việc điều hành và phân nhóm những giải pháp có được. + GA được sử dụng đặc biệt cho những bài toán yêu cầu tìm kiếm tối ưu toàn cục với không gian tìm kiếm lớn và không thể kiểm soát nhờ khả năng duyệt qua không gian tìm kiếm đại diện mà không thực sự đi qua từng điểm của toàn bộ không gian. 2.2 Cơ chế thực hiện GA 2.2.1 Mã hóa Để có thể thực hiện GA, vấn đề đầu tiên là xuất phát từ bài toán thực tế, ta cần phải mô tả các phương án của bài toán dưới một dạng nào đó (mô hình toán học, tin học, …). Vấn đề mô tả đó được gọi là các phương pháp mã hóa. Thông thường người ta sử dụng một trong các phương pháp như sau:

+ Mã hoá nhị phân Mã hoá nhị phân là phương pháp mã hoá NST phổ biến nhất. Trong mã hoá nhị phân, mỗi NST là một chuỗi nhị phân, mỗi bit trong nó có thể biểu diễn một đặc tính của nghiệm. Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

18

Mã hoá nhị phân thường hay dùng trong các bài toán tối ưu các hàm một biến hay nhiều biến. Khi đó, mỗi chuỗi nhị phân sẽ biểu diễn hàm tại một tập giá trị của các biến. Ngoài ra nó còn được áp dụng trong nhiều loại bài toán khác. Mã hoá nhị phân tuy là phổ biến nhưng nó có một nhược điểm là có thể tạo ra không gian mã hoá lớn hơn so với không gian giá trị của NST. Do đó, với nhiều bài toán thì biểu diễn nhị phân là không hữu hiệu. + Mã hoá hoán vị Trong mã hoá hoán vị, mỗi NST là một chuỗi các số biểu diễn một thứ tự sắp xếp. Mã hoá hoán vị phù hợp cho các bài toán liên quan đến thứ tự. Đối với các bài toán này, việc thao tác trên các NST chính là hoán vị các số trong chuỗi đó làm thay đổi thứ tự của nó. Mã hoá hoán vị có thể được sử dụng trong các bài toán liên quan đến thứ tự như bài toán du lịch hay bài toán lập lịch. + Mã hoá số thực Mã hoá trực tiếp theo giá trị có thể được dùng trong các bài toán sử dụng giá trị phức tạp như trong số thực. Trong đó, mỗi NST là một chuỗi các giá trị. Các giá trị có thể là bất cứ cái gì liên quan đến bài toán, từ số nguyên, số thực, kí tự cho đến các đối tượng phức tạp hơn. Mã hoá số thực thường dùng cho các bài toán đặc biệt. Trong cách mã hoá này ta thường phải phát triển các toán tử đột biến và lai ghép cho phù hợp với từng bài toán. Thông thường mỗi NST được mã hóa là một véc tơ trong không gian. Cách mã hóa này thường sử dụng đối với các bài toán tối ưu số và được phát triển mạnh trong giai đoạn hiện nay. + Mã hóa dạng cây Phương pháp này được sử dụng trong các biểu thức toán học. Mỗi NST là một cây của một nhóm đối tượng nào đó. 2.2.2 Khởi tạo quần thể ban đầu Khởi tạo quần thể ban đầu là bước đầu tiên trong GA. Thông thường để khởi tạo quần thể trong bài toán tối ưu, ta tạo ra một cách ngẫu nhiên các lời giải có thể (thường là các lời giải thỏa mãn ràng buộc của bài toán nhưng chưa biết là đại

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

19

lượng cần tối ưu đã là tối ưu hay chưa). Tuỳ vào từng bài toán cụ thể mà ta có các phương pháp khởi tạo khác nhau. Chất lượng của quần thể ban đầu càng cao thì lời giải mà GA đưa ra càng tốt. 2.2.3 Xác định hàm thích nghi Theo các nghiên cứu và các thử nghiệm của nhiều nhà nghiên cứu về GA thì hàm tính độ thích nghi là một trong hai yếu tố quan trọng nhất quyết định sự thành công hay thất bại của GA. Hàm thích nghi được xây dựng sao cho giá trị thích nghi phải phản ánh được giá trị thực của NST trong việc đáp ứng yêu cầu của bài toán. 2.2.4 Cơ chế lựa chọn Cơ chế lựa chọn được áp dụng khi chọn các cá thể từ quần thể P(t ) để thực hiện việc lai ghép và đột biến, tạo ra quần thể P(t 1) . Có nhiều cách để lựa chọn các cá thể từ một quần thể. Sau đây sẽ giới thiệu một số cơ chế hay áp dụng. Ta sử dụng các kí hiệu như sau: - Kí hiệu NST thứ i là v i . - Hàm tính độ thích nghi của NST v i là f (vi ) - Kích thước quần thể là pop_size(). - Số NST cần chọn là N. + Cơ chế lựa chọn theo bánh xe Roulette pop _ size

å

Bước 1: Tính tổng độ thích nghi của cả quần thể: F =

f (vi )

i= 1

f (v i ) F

Bước 2: Tính xác suất chọn pi cho mỗi NST vi : pi Bước 3: Tính vị trí xác suất qi của mỗi NST: q i

i

pi j 1

Bước 4: Sử dụng cơ chế lựa chọn theo bánh xe Roulette được thực hiện bằng cách quay bánh xe Roulette N lần. Mỗi lần chọn một NST từ quần thể hiện hành vào quần thể mới theo nguyên tắc: - Phát sinh ngẫu nhiên một số r trong khoảng [0,1] .

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

20

- Nếu r sao cho qi-1

r

q1 thì chọn NST v1; ngược lại thì chọn NST thứ i (2

i

pop_size)

qi.

Với cơ chế lựa chọn như thế này thì có một số nhiếm sắc thể sẽ được chọn nhiều lần. Điều này phù hợp với lý thuyết lược đồ: các NST tốt nhất thì có nhiều bản sao, NST trung bình thì không đổi , NST kém thì chết đi. + Cơ chế lựa chọn xếp hạng Cơ chế lựa chọn xếp hạng được mô tả như sau: Bước 1: Sắp xếp các NST trong quần thể theo độ thích nghi từ thấp đến cao. Bước 2: Đặt lại độ thích nghi cho quần thể đã sắp xếp theo kiểu: NST thứ nhất có độ thích nghi là 1, NST thứ hai có độ thích nghi là 2, .v.v., NST thứ pop_size có độ thích nghi là pop_size. Theo phương pháp này việc một NST được chọn nhiều lần như trong lựa chọn theo kiểu bánh xe Roulette đã giảm đi. Nhưng nó có thể dẫn đến sự hội tụ chậm và NST có độ thích nghi cao cũng không khác mấy so với các NST khác. + Cơ chế lựa chọn theo lấy mẫu ngẫu nhiên Cơ chế lựa chọn theo mẫu được thực hiện như sau: Bước 1: Biểu diễn xác suất chọn các NST lên trên một đường thẳng. Bước 2: Đặt N điểm chọn lên đường thẳng. Các điểm chọn này cách nhau 1 1 , điểm đầu tiên đặt ngẫu nhiên trong khoảng [0, ] N N

Bước 3: Với một điểm chọn, NST gần với nó nhất về bên phải sẽ được chọn. Phương pháp này có đặc điểm là các điểm chọn được phân bố đều trên trục số, do đó sẽ gần với điểm xứng đáng được chọn. 2.2.5 Các toán tử di truyền Các toán tử di truyền của GA là toán tử lai ghép và đột biến. Đây là hai toán tử có tác động lớn đến chất lượng của giải thuật. Các toán tử này được xây dựng phụ thuộc vào cách mã hoá các NST. Ở đây chỉ đưa ra toán tử lai ghép và đột biến trên một số cách mã hoá NST để chỉ ra được ý tưởng xây dựng toán tử lai ghép và

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

21

đột biến trong GA. Còn tuỳ thuộc vào các bài toán cụ thể và cách mã hoá NST mà ta xây dựng hai loại toán tử này. Toán tử lai ghép + Lai ghép đơn điểm: - Một điểm cắt được chọn tại một vị trí thứ k trên NST. - Từ đầu NST đến vị trí thứ k, NST con sao chép từ cha, phần còn lại sao chép từ mẹ. Với NST cha: X = 11001010, NST mẹ Y = 11101001 Con sinh ra do lai ghép đơn (điểm cắt k=4): Con : 1100 | 1001 + Lai ghép hai điểm: - Hai điểm cắt được chọn . - Từ đầu cho đến điểm cắt thứ nhất được sao chép từ cha, từ điểm cắt thứ nhất đến điểm cắt thứ hai sao chép từ mẹ và phần còn lại sao chép từ cha. Xét

Cha : 11| 0010 | 10 Mẹ : 11| 1010 | 01

Con sinh ra do lai ghép hai điểm cắt : Con : 11 | 1010| 10 + Lai ghép mặt nạ : - Xây dựng một mặt nạ là một chuỗi nhị phân có chiều dài bằng chiều dài NST, Mặt nạ được phát sinh ngẫu nhiên đối với từng cặp cha mẹ. - Xây dựng NST mới: Duyệt qua mặt nạ, bit có giá trị 1 thì sao chép gen tại vị trí đó từ NST cha sang con, bit có giá trị 0 thì sao chép từ mẹ. Ví dụ xét Cha : Mẹ

11001010 :

Mặt nạ :

10101001 10101000

Con sinh ra do lai ghép mặt nạ : Con : Số hóa bởi trung tâm học liệu

10001001

http://www.lrc.tnu.edu.vn/

22

+ Lai ghép số học: NST con được tạo thành bằng cách thực hiện một phép toán logic nào đó như AND, OR, … với cặp NST bố mẹ. Ví dụ xét Cha

:

11001010

Mẹ

:

10101001

Con (AND): 10001000 Toán tử đột biến Phép đảo bit : Bit được chọn sẽ bị đảo (Bit được chọn có gạch chân) Nếu

trước đột biến :

11011001

Thì

sau đột biến :

11010001

2.3. Thuật toán di truyền kinh điển 2.3.1. Mã hóa GA kinh điển sử dụng mã hóa nhị phân, mỗi cá thể được mã hóa là một chuỗi nhị phân có chiều dài cố định. Sử dụng véc tơ nhị phân có độ dài L như một NST để biểu diễn giá trị của biến x [l x , u x ] (độ dài L của NST phụ thuộc vào yêu cầu cụ thể của bài toán). Một bit mã hóa x ứng với một giá trị trong khoảng [0, 2L] sẽ được ánh xạ lên giá trị thực thuộc miền [l x , u x ] . Tỷ lệ co giãn của ánh xạ: g

ux lx 2L

Giá trị x tương ứng với chuỗi NST nhị phân là: x

lx

decimal( NST ) * g

Decimal(NST) là giá trị thập phân của chuỗi NST nhị phân. Để khởi tạo quần thể chỉ cần tạo pop-size (kích cỡ quần thể) NST ngẫu nhiên theo từng bit. Tiếp theo, lượng giá từng NST (tính giá trị hàm f trên các chuỗi biến nhị phân đã được giải mã), chọn quần thể mới thỏa mãn phân bố xác suất dựa trên độ thích nghi và thực hiện các phép đột biến và lai tạo để tạo các cá thể thế hệ mới. Sau một số thế hệ, nếu không được cải thiện thêm gì nữa, NST tốt nhất sẽ được xem như lời giải tối ưu (thường là toàn cục). Thông thường sẽ cho dừng thuật giải di Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

23

truyền sau một số bước lặp cố định tùy thuộc vào điều kiện về tốc độ hay tài nguyên máy tính. 2.3.2. Toán tử chọn lọc a/ Sử dụng bánh xe Roulette Có nhiều cách để thực hiện toán tử chọn lọc, chủ yếu theo cách nếu các thể có độ thích nghi cao hơn thì khả năng được chọn nhiều hơn. Tuy nhiên, để đơn giản và hiệu quả nhất là sử dụng bánh xe Roulette. Mỗi cá thể trong quần thể chiếm một khe có độ rộng tỷ lệ thuận với giá trị phù hợp. Độ rộng của khe được tính bằng tỷ lệ % giá trị phù hợp của một cá thể trên tổng giá trị phù hợp toàn quẩn thể. Giả sử f i là độ phù hợp của cá thể thứ i trong quần thể gồm N cá thể. Khi đó, cá thể i sẽ được chọn với xác suất pi

fi

.

N

fi i 1

b/ Thủ tục xếp hạng các cá thể Trong thủ tục này các cá thể được sắp xếp theo giá trị của hàm mục tiêu. Cá thể đầu tiên là các thể tốt nhất, cá thể cuối cùng là cá thể tồi nhất. Cá thể thứ ( N

j ) trong dãy có xác suất chọn lựa: p N

j j

N

k k 1

Các bước tiến hành thủ tục là: - Sắp xếp các chuỗi theo thứ tự giảm dần của hàm mục tiêu (bài toán cực đại) hoặc theo thứ tự tăng dần của hàm mục tiêu (bài toán cực tiểu). - Tính độ phù hợp của chuỗi. c/ Thủ tục chọn lọc cạnh tranh Trong thủ tục này cách tiến hành như sau: - Chọn t cá thể từ quần thể hiện tại một cách ngẫu nhiên và chọn cá thể tốt nhất trong t cá thể đó để sao chép sang quần thể tạm thời. - Lặp lại bước trên N lần sẽ được quần thể tạm thời.

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

24

Giá trị t khi đó gọi là kích cỡ của chọn lọc cạnh tranh. Khi t

2 ta có chọn

lọc cạnh tranh nhị phân. 2.3.3. Toán tử lai ghép a/ Lai ghép một điểm Giả sử với hai cá thể cha và mẹ đã được chọn P1, P2: P1= (1110001010), P2= (0101100111), độ dài L 10 . Toán tử này cần sinh ngẫu nhiên một vị trí k (1 k

L) , sau đó hai cá thể

con được tạo thành bằng cách tráo đổi các gen của cặp cha mẹ tính từ điểm cắt. Giả sử điểm cắt đã chọn k 8 , hai con được sinh ra như sau: C1= (1110001011), C2= (0101100110) Thủ tục lai ghép một điểm Procedure lai1diem(k, P1, P2: var C1,C2); Begin For i:=1 to k do Begin C1[i]:=P1[i]; C2[i]:=P2[i]; End; For i:=k+1 to L do Begin C1[i]:=P1[i]; C2[i]:=P2[i]; End; End; b/ Lai ghép nhiều điểm Lai ghép nhiều điểm thực hiện tương tự lai ghép một điểm. Với hai cá thể cha k mẹ đã chọn P1, P2, toán tử này cần sinh ngẫu nhiên k vị trí i1 , i2 ,..., ik (giả thiết i1

i2

... ik ). Các điểm cắt chia các cá thể đã chọn thành các đoạn được

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

25

đánh số chẵn và lẻ. Hai cá thể con được tạo thành bằng cách tráo đổi các gen cha mẹ tùy theo đoạn chẵn hay đoạn lẻ. Giả sử các điểm cắt đã chọn là: 2,4,6,9. P1= 1001110101, P2= 0100111110 C1= 1000111111, C2= 0101110101 c/ Lai ghép mặt nạ Với hai cá thể cha mẹ đã chọn P1, P2 và phát sinh một chuỗi nhị phân ngẫu nhiên cũng có độ dài L gọi là chuỗi mặt nạ. P1= (1110001010), P2= (0101100111), U= (0110011001), độ dài L 10 . Các con được tạo ra dựa trên chuỗi mặt nạ này để quyết định lấy thành phần của cá thể cha hay cá thể mẹ dựa trên nguyên tắc: Gen thứ i của cá thể con C1 được lấy gen thứ i của P1 nếu bit mặt nạ tương ứng là 1 và lấy gen thứ i của P2 nếu bit mặt nạ là 0. C2 thì ngược lại. C1= (0111101110), C2= (1100000011) Thủ tục lai ghép mặt nạ: Procedure laimatna(u, P1, P2; var C1, C2); Begin For i:=1 to L do Begin If U[i]=1 then Begin C1[i]:=P1[i]; C2[i]:=P2[i]; End Else Begin C1[i]:=P2[i]; C2[i]:=P1[i]; End; End; End; 2.3.4. Toán tử đột biến Toán tử đột biến làm thay đổi các thông tin của quần thể ở mức bit (gen). Đột biến làm thay đổi giá trị của một bit bất kỳ theo xác suất pm. Mỗi bit đều có cơ hội đột biến như nhau. Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

26

Toán tử đột biến bao gồm: toán tử đột biến chuẩn, đột biến đều và không đều. Thuật toán đột biến: For i:=1 to m do If random[0,1] < pm then invert (parent[i]); Với invert(u) là hàm đảo ngược bit u. Thuật toán GA cổ điển đƣợc mô tả một cách tƣờng minh nhƣ sau: Algorithm GA_codien; Begin {Khởi tạo quần thể gồm m quần thể} t:=0; Creat initial population B0=(b10,b20,…,bm0); While (stopping condition not fulfilled) do Begin {Chọn lọc tỷ lệ} For i:=1 to m do Begin r:=random[0,1]; k:=1; i

f (b j , t )

While (kt(k); tg=t(k); end; end; f2(i)=tg; f3(i)=abs(f1(i))-abs(f2(i)); end; % Qua trinh sinh san va chon loc tu nhien demmax=100; dem=0; c=[10.20 11.90 39.00 45.34 61.49; 1.20 8.10 5.90 6.12 0.74; 0.08 0.20 0.19 0.35 5.39; 0.05 1.17 0.15 6.51 2.05; 2.60 12.35 15.00 6.03 4.05]; while demt(i); tg=t(i); end; end; f2(k)=tg; f3(k)=abs(f1(k))-abs(f2(k)); end; % sap xep ham muc tieu tang dan for k=1:m-1 for l=k+1:m if f3(k)>f3(l) tg=f3(k);f3(k)=f3(l);f3(l)=tg; tgy=y(k,:);y(k,:)=y(l,:);y(l,:)=tgy; end; end; end; % Lay lai n zen tot nhat for k=1:n; x(k,:)=y(k,:); end; % xac dinh zen tot nhat vt=1;tg=f3(1); for i=2:n; if tg>f3(i) tg=f3(i); vt=i; end; end; g=x(vt,:); dem g f3(vt) end; %Ket thuc vong while bar(g) xlabel('Cac nguyen lieu') set(gca,'Xticklabel',{'Ngo','Cam gao','Dau tuong','Kho dau','Bot ca'}) --------------------------------------------------------

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

73

Phụ lục 2: Chƣơng trình giải bài toán thức ăn gia súc bằng PSO clear; close; % nhap cac gia tri ban dau cua bai toan n=30;%So ca the % Gia cac nguyen lieu (don vi ngan dong) a1=15; a2=11.5; a3=60; a4=20.6; a5=30; % Luong trong kho ca nguyen lieu (don vi tan) b1=500; b2=200; b3=50; b4=75.5; b5=2; d1=19; d2=5; d3=0.8; d4=0.6; d5=1.1; MT1=0;MT2=0; x=zeros(n,5); f1=zeros(n,1); f2=zeros(n,1); f3=zeros(n,1); f=zeros(n,1); % Tao quan the ngau nhien ban dau for i=1:n % Dieu kien rang buoc: x(i,1)+x(i,2)+x(i,3)+x(i,4)+x(i,5)=1 x(i,2)=rand; x(i,1)=rand; while x(i,1)>(1-x(i,2)) x(i,1)=rand; end; x(i,5)=rand; while x(i,5)>(1-x(i,1)-x(i,2)) x(i,5)=rand; end; x(i,4)=rand; while x(i,4)>(1-x(i,1)-x(i,2)-x(i,5)) x(i,4)=rand;

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

74

end; x(i,3)=1-x(i,1)-x(i,2)-x(i,5)-x(i,4); f1(i)=a1*x(i,1)+a2*x(i,2)+a3*x(i,3)+a4*x(i,4)+a5*x(i,5); t=[b1/x(i,1), b2/x(i,2),b3/x(i,3),b4/x(i,4),b5/x(i,5)]; tg=t(1); for k=2:5 if tg>t(k); tg=t(k); end; end; f2(i)=tg; f3(i)=abs(f1(i)-MT1)-abs(f2(i)-MT2); end; % cac tham so cua bai toan da muc tieu c=[10.20 11.90 39.00 45.34 61.49; 1.20 8.10 5.90 6.12 0.74; 0.08 0.20 0.19 0.35 5.39; 0.05 1.17 0.15 6.51 2.05; 2.60 12.35 15.00 6.03 4.05]; %bien cua thuat toan PSO c1=0.5+log(2); c2=c1; v=zeros(n,5); %vi tri tot nhat cua ca the da di qua p_x =x; %tinh gia tri ham muc tieu cho moi ca the for k=1:n f3(k)=f1(k)+f2(k); end; % khoi tao vecto van toc cho moi ca the for i=1:1:n v(i,:)=0;%0.01*rand(); end count=0;MIN=inf; while countt(k); tg=t(k); end;

Số hóa bởi trung tâm học liệu

http://www.lrc.tnu.edu.vn/

75

end; f2(i)=tg; f3(i)=abs(f1(i)-MT1)-abs(f2(i)-MT2); end; f=f3; p_f =f; % tim thong tin tot nhat quan the for s=1:n if (p_f(s) < MIN)&(p_f(s)>0) MIN=p_f(s); g_best=s; end; end; for i=1:n if f(i)