ĐẠ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 THỊ DUYÊN

CƠ SỞ CỦA THUẬT TOÁN DI TRUYỀN VÀ

ỨNG DỤNG ĐỐI VỚI MỘT SỐ BÀI TOÀN LỚP NP

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

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

THÁI NGUYÊN, 2020

ĐẠ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 THỊ DUYÊN

CƠ SỞ CỦA THUẬT TOÁN DI TRUYỀN VÀ

ỨNG DỤNG ĐỐI VỚI MỘT SỐ BÀI TOÀN LỚP NP

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

Mã số: 8 48 01 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

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

THÁI NGUYÊN, 2020

LỜI CAM ĐOAN

Sau quá trình học tập tại Trường Đại học công nghệ thông tin &

truyền thông, với những kiến thức lý thuyết và thực hành đã tích lũy được,

với việc vận dụng các kiến thức vào thực tế, em đã tự nghiên cứu các tài liệu,

các công trình nghiên cứu, đồng thời có sự phân tích, tổng hợp, đúc kết và

phát triển để hoàn thành luận văn thạc sĩ của mình.

Em xin cam đoan luận văn này là công trình do bản thân em tự tìm

hiểu, nghiên cứu và hoàn thành dưới sự hướng dẫn của thầy giáo TS. Vũ

Vinh Quang.

Thái Nguyên, tháng 7 năm 2020

Sinh viên

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Nguyễn Thị Duyên

LỜI CẢM ƠN

Trong thời gian hai năm của chương trình đào tạo thạc sỹ, trong đó gần

một nửa thời gian dành cho các môn học, thời gian còn lại dành cho việc lựa

chọn đề tài, giáo viên hướng dẫn, tập trung vào nghiên cứu, viết, chỉnh sửa và

hoàn thiện đề tài. Với quỹ thời gian như vậy và với vị trí công việc đang phải

đảm nhận, không riêng bản thân em mà hầu hết các sinh viên cao học muốn

hoàn thành tốt luận văn của mình trước hết đều phải có sự sắp xếp thời gian hợp

lý, có sự tập trung học tập và nghiên cứu với tinh thần nghiêm túc, nỗ lực hết

mình; tiếp đến cần có sự ủng hộ về tinh thần, sự giúp đỡ về chuyên môn một

trong những điều kiện không thể thiếu quyết định đến việc thành công của đề tài.

Để hoàn thành được đề tài này trước tiên em xin gửi lời cảm ơn đến

thầy giáo hướng dẫn TS. Vũ Vinh Quang, người đã có những định hướng

cho em về nội dung và hướng phát triển của đề tài, người đã có những đóng

góp quý báu cho em về những vấn đề chuyên môn của đề tài, giúp em tháo gỡ

kịp thời những vướng mắc trong quá trình làm luận văn.

Em cũng xin cám ơn các thầy cô giáo Trường Đại học Công nghệ

thông tin và Truyền thông cũng như bạn bè cùng lớp đã có những ý kiến đóng

góp bổ sung cho đề tài luận văn của em. Xin cảm ơn gia đình, người thân

cũng như đồng nghiệp luôn quan tâm, ủng hộ hỗ trợ về mặt tinh thần trong

suốt thời gian từ khi nhận đề tài đến khi hoàn thiện đề tài này.

Em xin hứa sẽ cố gắng hơn nữa, tự trau dồi bản thân, tích cực nâng cao

năng lực chuyên môn của mình để sau khi hoàn thành đề tài này sẽ có hướng

tập trung nghiên cứu sâu hơn, không ngừng hoàn thiện hơn nữa đề tài của

mình để có những ứng dụng thực tiễn cao trong thực tế.

Thái Nguyên, tháng 7 năm 2020

Sinh viên

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Nguyễn Thị Duyên

MỤC LỤC

LỜI CAM ĐOAN .............................................................................................. i

LỜI CẢM ƠN ................................................................................................... ii

DANH MỤC CÁC BẢNG.............................................................................. vii

DANH MỤC CÁC HÌNH .............................................................................. viii

LỜI MỞ ĐẦU ................................................................................................... 1

CHƯƠNG 1 GIẢI THUẬT DI TRUYỀN ........................................................ 3

1.1 Giới thiệu về GA ......................................................................................... 3

1.2 Các khái niệm cơ bản .................................................................................. 5

1.2.1 Cá thể, nhiễm sắc thể ............................................................................ 5

1.2.2 Quần thể ................................................................................................ 5

1.2.3 Chọn lọc (Selection) ............................................................................. 5

1.2.4 Lai ghép (Cross-over) .......................................................................... 6

1.2.5 Đột biến (Mutation) ............................................................................. 6

1.3 Mô hình GA ................................................................................................ 6

1.4 Các tham số của GA .................................................................................... 7

1.4.1 Kích thước quần thể .............................................................................. 7

1.4.2 Xác suất lai ghép ................................................................................... 7

1.4.3 Xác suất đột biến .................................................................................. 8

1.5 Cơ chế thực hiện GA ................................................................................... 8

1.5.1 Mã hóa .................................................................................................. 8

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

1.5.3 Xác định hàm thích nghi ..................................................................... 10

1.5.4 Cơ chế lựa chọn ................................................................................... 10

1.5.5 Các toán tử di truyền ........................................................................... 10

1.6. Thuật toán di truyền kinh điển ................................................................. 12

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

1.6.1. Mã hóa ................................................................................................ 12

1.6.2. Toán tử lai ghép .................................................................................. 13

1.6.3. Toán tử đột biến .................................................................................. 15

1.6.4. Thuật toán di truyền mã hóa số thực (RCGA) ..................................... 15

CHƯƠNG 2 LỚP BÀI TOÁN NP VÀ MỘT SỐ MÔ HÌNH ........................ 22

2.1 Khái niệm về thuật toán và độ phức tạp thuật toán ................................... 22

2.1.1 Khái niệm về thuật toán ...................................................................... 22

2.1.2. Các yêu cầu của thuật toán ................................................................ 22

2.2. Độ phức tạp của thuật toán ....................................................................... 23

2.2.1. Chi phí phải trả cho một quá trình tính toán ...................................... 23

2.2.2. Độ phức tạp của thuật toán ................................................................ 24

2.2.3. Các qui tắc xác định độ phức tạp thuật toán ...................................... 25

2.3. Vấn đề phân lớp các bài toán dựa trên độ phức tạp thuật toán. ............... 25

2.3.1. Lớp bài toán P .................................................................................... 25

2.3.2. Lớp NP ............................................................................................... 26

2.3.3. Lớp NPC ............................................................................................ 26

2.4 Một số mô hình bài toán lớp NP ............................................................... 27

2.4.1 Mô hình bài toán KNAPSACK .......................................................... 27

2.4.2 Bài toán quân cờ Domino ................................................................... 30

2.4.3 Mô hình bài toán TSP ......................................................................... 33

CHƯƠNG 3: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN

LẬP LỊCH GIẢNG DẠY THỰC HÀNH....................................................... 35

3.1 Mô hình bài toán thực tế ........................................................................... 35

3.2 Thiết kế giải thuật di truyền GA ............................................................... 37

3.2.1 Xây dựng cấu trúc cá thể, các hàm kiểm tra ....................................... 37

3.2.2 Xây dựng các toán tử trong GA .......................................................... 38

3.3 Các kết quả thực nghiệm ........................................................................... 39

3.3.1 Bộ số liệu Test 1 ................................................................................. 39

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

3.3.2 Bộ số liệu Test 2 ................................................................................. 42

KẾT LUẬN ..................................................................................................... 46

TÀI LIỆU THAM KHẢO ............................................................................... 47

PHẦN PHỤ LỤC ............................................................................................ 48

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN ............................................ 60

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

GA – Genetic Algorithm: giải thuật di truyền

TSP - Travelling Salesman Problems: bài toán người du lịch

EC - Evolutionary computation: tính toán tiến hóa

EP - Evolutionary Programming: quy hoạch tiến hóa

ES - Evolutionary Strategies: các chiến lược tiến hóa

GP - Genetic Programming: lập trình di truyền

CS - Classifier Systems: các hệ thống phân loại

NST – nhiễm sắc thể

Selection: chọn lọc

Cross-over: lai ghép

Mutation: đột biến

Reproduction: sinh sản

pop-size: kích cỡ quần thể

RCGA: thuật toán di truyền mã hóa số thực

BLX-α - Blend Crossover: lai ghép BLX-α

CMX - Center of Mass Crossover: lai ghép CMX

NP-hard: bài toán NP khó

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

NP-complete: bài toán NP đầy đủ

DANH MỤC CÁC BẢNG

Bảng 2.1: Bảng giá trị độ phức tạp tính toán của các hàm số ......................... 24

Bảng 3.1: Giáo viên phù hợp chuyên môn với phòng thực hành ................... 40

Bảng 3.2: Giáo viên sẵn sàng nhận buổi hướng dẫn ....................................... 40

Bảng 3.3: Lịch giảng dạy Test 1 ..................................................................... 41

Bảng 3.4: Số buổi giảng dạy đối với các giáo viên Test 1 .............................. 41

Bảng 3.5: Lịch giảng dạy Test 1 ..................................................................... 41

Bảng 3.6: Số buổi giảng dạy đối với các giáo viên ......................................... 41

Bảng 3.7 Lịch giảng dạy ................................................................................. 41

Bảng 3.8 Số buổi giảng dạy đối với các giáo viên .......................................... 42

Bảng 3.9: Bảng các giáo viên phù hợp chuyên môn với phòng thực hành .... 42

Bảng 3.10: Bảng các giáo viên sẵn sàng nhận buổi hướng dẫn ...................... 43

Bảng 3.11: Lịch giảng dạy Test 2 ................................................................... 44

Bảng 3.12: Số buổi giảng dạy đối với các giáo viên Test 2 ............................ 44

Bảng 3.13: Lịch giảng dạy .............................................................................. 44

Bảng 3.14: Số buổi giảng dạy đối với các giáo viên....................................... 45

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Bảng 3.15: Lịch giảng dạy .............................................................................. 45

DANH MỤC CÁC HÌNH

Hình 1.1: Sơ đồ mô tả GA ................................................................................. 6

Hình 1.2: Lai ghép CMX ............................................................................... 19

Hình 1.3: Phân bố của ............................................................................... 19

Hình 1.4: Toán tử lai ghép SX ........................................................................ 20

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 2.1: Các lớp P, NP và NPC .................................................................... 26

LỜI MỞ ĐẦU

Trong thực tế, việc tìm kiếm các phương pháp giải lớp các bài toán tối

ưu là một lĩnh vực được các nhà khoa học trên thế giới đặc biệt quan tâm. Đã

có rất nhiều các công trình nghiên cứu về lĩnh vực này, chủ yếu được phát

triển trong lý thuyết tối ưu hóa đối với mô hình các bài toán quy hoạch và mô

hình các bài toán trong công nghệ thông tin để tìm kiếm các thuật toán giải

các lớp bài toán NP. Trong thời gian gần đây một hướng nghiên cứu quan

trọng được phát triển trong lĩnh vực tính toán tiến hóa, đó chính là nghiên cứu

về thuật toán di truyền (Genetic Algorithm - GA). Chính vì vậy, GA đã trở

thành một trong những đề tài nghiên cứu thu hút được nhiều sự quan tâm và

hiện nay đã và đang đem đến rất nhiều ứng dụng trong thực tiễn.

Xuất phát từ thuyết tiến hóa muôn loài của Darwin, các nhà toán học John

Holland (1975) và Goldberg (1989) đã đề xuất và phát triển GA. GA là một

thuật toán đưa ra lời giải tương đối tối ưu. Tư tưởng chính của thuật toán là tìm

kiếm lời giải tối ưu dựa trên cơ chế lai ghép, chọn lọc, sử dụng các nguyên lý

về tính di truyền, sự thích nghi và sự sống các cá thể thích nghi nhất trong tự

nhiên từ đó tiếp cận đến lời giải tối ưu của bài toán đang xét.

Ngày nay, GA được ứng dụng khá nhiều trong các lĩnh vực như khoa

học, kinh doanh và giải trí. Đầu tiên phải kể đến là các bài toán tối ưu bao

gồm: Tối ưu số và tối ưu tổ hợp đã sử dụng GA để tìm lời giải như là bài toán

người du lịch (Travelling Salesman Problems - TSP). Một ứng dụng khác

cũng đang được ứng dụng rộng rãi của GA là giải quyết vấn đề bùng nổ về

lượng thông tin trên mạng internet bao gồm: Thư viện điện tử, thông tin điện

tử... dẫn đến phát sinh một số lượng lớn văn bản với tốc độ tăng chóng mặt.

Nội dung chính của luận văn là nghiên cứu thuật toán di truyền và một

số ứng dụng với lớp các bài toán NP.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Cấu trúc luận văn gồm 3 chương:

Chương 1 trình bày các khái niệm cơ bản, mô hình, các tham số cơ bản,

các phép toán, cơ chế thực hiện tổng quát của thuật toán di truyền.

Chương 2 trình bày khái niệm về thuật toán và độ phức tạp của thuật toán,

sự phân lớp các bài toán qua độ phức tạp, một số mô hình bài toán lớp NP.

Chương 3 trình bày kết quả sử dụng GA xây dựng thuật toán giải bài

toán lập lịch phân công giảng dạy tại mô hình trường cao đẳng dạy nghề.

Các kết quả kiểm tra thuật toán GA giải một số mô hình bài toán NP đã

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

được lập trình trên môi trường Matlab version 7.0.

Chương 1.

GIẢI THUẬT DI TRUYỀN

Nội dung chính của chương 1 trình bày một số khái niệm về giải thuật di

truyền, mô hình thiết kế giải thuât, các toán tử trong GA. Thuật toán di truyền

mã hóa số thực. Các kết quả được tham khảo trong các tài liệu [2, 3, 4, 5, 6, 7, 8]

1.1 Giới thiệu về GA

Giải thuật di truyền GA(GENETIC ALGORITHM) do D.E. Goldberg đề

xuất, sau đó được L. Davis và Z. Michalevicz phát triển là kỹ thuật phỏng

theo quá trình thích nghi tiến hóa của các quần thể sinh học dựa trên học

thuyết Darwin, đây cũng chính là một trong các thuật toán tiến hóa. Thuật

toán tiến hóa là các chương trình máy tính có dùng các thuật toán tìm kiếm,

tối ưu hóa dựa trên nguyên lý tiến hóa tự nhiên. GA là phương pháp tìm kiếm

tối ưu ngẫu nhiên bằng cách mô phỏng theo sự tiến hóa của con người hay

của sinh vật. Tư tưởng của thuật toán di truyền là mô phỏng các hiện tượng tự

nhiên, là kế thừa và đấu tranh sinh tồn.

GA thuộc lớp các giải thuật xuất sắc nhưng lại rất khác các giải thuật

ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên.

Khác biệt quan trọng giữa tìm kiếm của GA và các phương pháp tìm kiếm

khác là GA duy trì và xử lý một tập các lời giải, gọi là một quần thể

(population). Trong GA, việc tìm kiếm giả thuyết thích hợp được bắt đầu với

một quần thể, hay một tập hợp có chọn lọc ban đầu của các giả thuyết. Các cá

thể của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt

động lai ghép và đột biến ngẫu nhiên – được lấy mẫu sau các quá trình tiến

hóa sinh học. Ở mỗi bước, các giả thuyết trong quần thể hiện tại được ước

lượng liên hệ với đại lượng thích nghi, với các giả thuyết phù hợp nhất được

chọn theo xác suất là các hạt giống cho việc sản sinh thế hệ kế tiếp, gọi là cá

thể (individual). Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ

tồn tại và ngược lại sẽ bị đào thải. GA có thể dò tìm thế hệ mới có độ thích

nghi tốt hơn. GA giải quyết các bài toán quy hoạch toán học thông qua các

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

quá trình cơ bản: lai tạo (crossover), đột biến (mutation) và chọn lọc

(selection) cho các cá thể trong quần thể. Dùng GA đòi hỏi phải xác định

được: khởi tạo quần thể ban đầu, hàm đánh giá các lời giải theo mức độ thích

nghi – hàm mục tiêu, các toán tử di truyền tạo hàm sinh sản.

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ì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

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

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 .

1.2 Các khái niệm cơ bản

1.2.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 Nhiễm sắc thể(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.

1.2.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.

1.2.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 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

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

ứng mục tiêu là các cá thể tốt sẽ có khả năng được chọn cao hơn.

1.2.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.

1.2.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ệ.

1.3 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

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 1.1: Sơ đồ mô tả GA

Như vậy giải thuật GA được xây dựng qua các bước cơ bản sau đây:

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.

1.4 Các tham số của GA

1.4.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.

1.4.2 Xác suất lai ghép

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

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ẹ.

1.4.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.

1.5 Cơ chế thực hiện GA

1.5.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ế,

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

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.

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ố

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

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 đó.

1.5.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 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.

1.5.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.

1.5.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ể để

thực hiện việc lai ghép và đột biến, tạo ra quần thể . Có nhiều cách để

lựa chọn các cá thể từ một quần thể. Tùy từng mô hình bài toán khác nhau,

chúng ta có thể xây dựng các phương pháp lựa chọn khác nhau: thông thường

người ta sử dụng một trong 2 phương pháp sau để lựa chọn các cá thể vào quá

trình lai ghép

+ Lựa chọn ngẫu nhiên từ quần thể lấy N cá thể để thực hiện lại ghép

+ Chọn tất cả các cá thể cùng tham gia lai ghép.

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

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

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à độ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í dụ: 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 : 11001010

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Mẹ : 10101001

Mặt nạ : 10101000

Con sinh ra do lai ghép mặt nạ :

Con : 10001001

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

1.6. Thuật toán di truyền kinh điển

1.6.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 (độ 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 .

Tỷ lệ co giãn của ánh xạ:

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

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 truyền sau một số bước lặp cố định

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

tùy thuộc vào điều kiện về tốc độ hay tài nguyên máy tính.

1.6.2. 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

Toán tử này cần sinh ngẫu nhiên một vị trí , 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 , 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á

vị trí thể cha mẹ đã chọn P1, P2, toán tử này cần sinh ngẫu nhiên

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

(giả thiết ). Các điểm cắt chia các cá thể đã chọn

thành các đoạn được đá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

.

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];

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

End;

End;

End;

1.6.3. 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.

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.

1.6.4. Thuật toán di truyền mã hóa số thực (RCGA)

Giới thiệu

Bài toán RCGA có thể xem là một cặp trong đó: và

là một hàm n biến. Bài toán đặt ra là tìm véc tơ

sao cho đạt giá trị cực tiểu trên S, nghĩa là với

mọi phải có . Hàm ở đây không liên tục nhưng cần bị

chặn trên S.

Trong RCGA, mỗi cá thể được biểu diễn bởi một véc tơ thực n chiều:

Như vậy một quần thể kích cỡ m là một tập véc tơ có m véc tơ trong

hay có thể xem như một ma trận thực cấp (m x n). Cách mã hóa này tự nhiên

và thuận tiện trong việc thực hiện các toán tử tiến hóa.

Các toán tử của RCGA

+ Toán tử chọn lọc

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Trong RCGA, toán tử chọn lọc vẫn được áp dụng như trong GA kinh

điển bao gồm: Chọn lọc tỷ lệ, chọn lọc xếp hạng hoặc chọn lọc cạnh tranh.

+ Toán tử lai ghép

RCGA cũng áp dụng các toán tử lai ghép như GA kinh điển bao gồm:

lai ghép một điểm, lai ghép nhiều điểm, lai ghép mặt nạ. Ngoài ra, do cách mã

hóa quần thể, người ta còn nghiên cứu và đề xuất nhiều dạng khác nhau của

toán tử lai ghép. Phần này sẽ giới thiệu một số dạng toán tử lai ghép thường

dùng với giả thiết cặp cá thể cha mẹ chọn để tiến hành lai ghép là:

và

a/ Lai ghép một điểm

Với cặp cha mẹ X, Y là các véc tơ m chiều, toán tử lai ghép một điểm

chọn ngẫu nhiên một vị trí rồi sinh ra cá thể con theo công thức:

b/ Lai ghép đa điểm

Chọn ngẫu nhiên k điểm

Lai ghép đa điểm tạo ra cặp (X’,Y’) bằng cách đánh số các đoạn [jt,

jt+1] từ 0 trở đi, sau đó lấy:

bằng tại những đoạn có số hiệu chẵn và bằng tại những đoạn

có số hiệu lẻ.

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

số hiệu chẵn.

c/ Lai ghép mặt nạ hoặc lai ghép đều

Chọn ngẫu nhiên vị trí 1 < i1 < i2 < ... < ik< m

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Các cá thể con X’, Y’ được sinh ra như sau:

d/ Lai số học (Arithmetic Crossover)

Chọn một số thực a (0 < a < 1).

Các cá thể con X’ và Y’ được tính bởi:

e/ Lai ghép Heuristic

Với cặp cha mẹ (X,Y) đã chọn, trong đó cá thể X có độ thích nghi tốt

hơn cá thể Y thì toán tử này tạo một cá thể con duy nhất X’ từ cặp X,Y được

xác định bởi:

với 0 < r < 1

f/ Lai ghép BLX-α (Blend Crossover)

Với cặp cha mẹ được chọn lai ghép:

Đặt

Khi đó thành phần thứ i của cá thể con tạo ra là một số ngẫu nhiên chọn

. trong khoảng

Toán tử BLX-α thông qua kết quả thực nghiệm đã khẳng định tính hiệu

quả tốt nhất khi giá trị α là 0.5.

g/ Lai ghép UNDX (Unimodal Normal Distributed Crossover)

Trong UNDX-m, (m+2) cha mẹ được chọn ngẫu nhiên từ quần thể,

trong đó m+1 cá thể đầu được dùng để tính một véc tơ trung bình. Cá thể cuối

cùng được sử dụng để định hướng cá thể con sẽ sinh ra.

Thuật toán được mô tả như sau:

1) Chọn (m+1) cá thể cha mẹ x1, x2 , … , xm+1 một cách ngẫu nhiên từ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

quần thể ban đầu.

2) Tính véc tơ trung bình của các cá thể đã chọn :

Tính .

3) Chọn ngẫu nhiên cá thể cha từ quần thể

4) Tính độ dài d của trực giao với d1 , … , dm+1 .

5) Lấy một cơ sở trực giao em+2 , … , en của không gian con trực giao với

không gian sinh bởi d1 , … , dm+1 .

6) Sinh ra các con theo công thức :

trong đó wi và vj là các biến ngẫu nhiên tương ứng với các phân phối

chuẩn và .

Các nhà toán học Kita và Yamamura đã sử dụng thành công với các

giá trị

và

h/ Lai ghép CMX (Center of Mass Crossover)

Giả sử quần thể đang xét là {X1, ..., XN}. Mỗi cá thể là một véc tơ trong Rn.

Thuật toán được mô tả như sau:

1) Chọn ngẫu nhiên m cá thể từ quần thể (1 < m < N)

i = 1, .., m.

2) Tính

3) Với mỗi i= 1, .. , m tính các véc tơ "cha mẹ ảo" đối xứng với

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

qua

4) Với mỗi cặp và tạo một cá thể con bằng cách sử dụng

BLX-. Như vậy với m cá thể cha mẹ sẽ sinh được m cá thể con.

Mô phỏng lai ghép CMX được biểu diễn bởi hình 2.

Hình 1.2: Lai ghép CMX

Với cách lai ghép này, các cá thể con sinh ra sẽ phân bố gần với tâm

của “đám đông” các cá thể cha mẹ.

i/ Lai ghép MFX (Multi-parent Feature-wise Crossover)

Thuật toán này chọn từ mỗi cá thể cha mẹ một tính chất đặc trưng nào

đó rồi thực hiện tiến hoá sử dụng thông tin đặc trưng này.

Thuật toán như sau:

1) Chọn ngẫu nhiên m cá thể từ quần thể (1 < m < N)

2) Cá thể con được sinh ra như sau :

Với mỗi , chọn ngẫu nhiên một số tự nhiên k trong khoảng

sao cho k  i . Sau đó được sinh từ và là một số ngẫu

nhiên được chọn trong khoảng trong đó l là khoảng cách

l

l

l

và .

Hình 1. 3: Phân bố của

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Bằng cách trên, nếu cố định một cá thể cha sẽ sinh được một cá

thể con tương ứng mà mỗi thành phần của véc tơ được kế thừa một

thông tin đặc trưng nào đó của cá thể cha với một cá thể mẹ .

j/ Lai ghép SX (Seed Crossover)

Thuật toán này thực hiện lai ghép đôi một cá thể, cá thể con sinh ra lại

tiếp tục lai ghép với cá thể cha mẹ có độ thích nghi tăng dần.

Thuật toán được trình bày như sau:

1) Chọn ngẫu nhiên m cá thể từ quần thể (1 < m < N)

2) Xếp hạng các cá thể cha mẹ giảm dần theo độ thích nghi.

3)

4) Cho j chạy từ đến 1 thực hiện

Trong đó là toán tử lai ghép 2 cha mẹ dạng BLX-.

Như vậy với cách này, tại mỗi bước lặp, cá thể tạo được có khả năng kế

thừa những đặc trưng của cá thể cha mẹ với độ thích nghi tăng dần. Toán tử

Cha mẹ

Con

này chỉ sinh ra một cá thể con từ m cá thể cha mẹ đã chọn.

Hình 1.4: Toán tử lai ghép SX

+ Toán tử đột biến

a/ Đột biến đều

Với một gen i được chọn ngẫu nhiên để đột biến từ cá thể

, thành phần được thay thế bởi một số ngẫu nhiên trong

khoảng xác định của .

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

b/ Đột biến biên

Từ cá thể cha mẹ đã chọn đột biến và vị trí chọn đột biến , thành

phần thứ của được thay bởi hay , trong đó là khoảng xác

định của .

Trong các bài toán biên của các biến không lớn và giải pháp cần tìm

nằm gần biên thì phép đột biến biên tỏ ra rất hữu ích.

c/ Đột biến không đều

Giả sử là một số cực đại được định nghĩa trước. Thành phần

được thay thế bởi một trong hai giá trị theo công thức sau:

Việc chọn giá trị nào được tiến hành tùy theo giá trị ngẫu nhiên khởi

tạo với xác suất . Biến ngẫu nhiên xác định một bước đột biến trong

khoảng theo công thức:

- thường là số ngẫu nhiên phân bố đều trong khoảng đơn vị.

- tham số xác định ảnh hưởng của lần tạo sinh thứ t trên phân bố của đột

biến trong miền .

Kết luận

Trong chương 1 đã đưa ra các khái niệm tổng quát của giải thuật di

truyền, mô tả chi tiết các toán tử được sử dụng trong GA như: phép khởi tạo,

phép lai, các toán tử đột biến, các phương pháp lựa chọn NST, đồng thời mô

tả chi tiết giải thuật di truyền mã hóa số thực RCGA. Đây là các kiến thức cơ

bản sử dụng để trình bày các nội dung sẽ được đưa ra trong chương 2 và

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

chương 3 của luận văn.

Chương 2.

LỚP BÀI TOÁN NP VÀ MỘT SỐ MÔ HÌNH

Trong chương này, luận văn sẽ trình bày các khái niệm cơ bản về thuật

toán và độ phức tạp của thuật toán. Nguyên tắc phân lớp các bài toán theo độ

phức tạp của thuật toán. Nghiên cứu chi tiết lớp bài toán NP và phân tích một

số mô hình của bài toán thuộc lớp NP kinh điển. Các kết quả được tham khảo

trong tài liệu [1].

2.1 Khái niệm về thuật toán và độ phức tạp thuật toán

2.1.1 Khái niệm về thuật toán

Trong tin học, người ta quan niệm bài toán là một công việc nào đó

muốn máy tính thực hiện. Khi dùng máy tính để giải bài toán, ta cần quan

tâm tới 2 vấn đề: Dữ liệu cần được đưa vào máy tính (Input) là gì và cần lấy

ra (Output) thông tin gì? Nói một cách khác, cho một bài toán trong tin học là

việc mô tả rõ Input và Output của bài toán.

Khác với toán học, việc giải một bài toán Tin học là việc đi tìm một lời

giải cụ thể, tường minh để đưa ra Output của bài toán dựa trên Input đã cho.

Việc chỉ ra một cách tìm Output của bài toán gọi là một thuật toán.

Định nghĩa: Thuật toán là một dãy hữu hạn các thao tác được sắp xếp

theo một trình tự nhất định để sau khi thực hiện dãy các thao tác đó, từ

input ta có output cần tìm.

Trong lĩnh vực máy tính, cụm từ “thuật toán” đôi khi người ta dùng

bằng một từ khác: “giải thuật”.

2.1.2. Các yêu cầu của thuật toán

Thuật toán phải đảm bảo được các yêu cầu sau đây:

- Tính xác định: Các bước của thuật toán phải được trình bày rõ ràng,

mạch lạc, đảm bảo cho người đọc chỉ hiểu theo một nghĩa duy nhất.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

- Tính khả thi: Thuật toán phải thực hiện được, nghĩa là ta có thể sử

dụng máy tính kết hợp giữa các ngôn ngữ lập trình để thể hiện thuật toán

trong một khoảng thời gian chấp nhận được.

- Tính dừng: Nếu dữ liệu vào thỏa mãn điều kiện đầu vào thì thuật toán

phải kết thúc và cho ra kết quả sau một số hữu hạn bước.

- Tính đúng đắn: Thuật toán phải cho kết quả chính xác và thể hiện

đúng đắn trên cơ sở toán học.

- Tính tổng quan: Thuật toán phải đúng với mọi bộ dữ liệu đầu vào.

- Tính tối ưu: Thuật toán phải có chi phí về không gian bộ nhớ ít nhất

và chạy trong thời gian nhanh nhất.

2.2. Độ phức tạp của thuật toán

2.2.1. Chi phí phải trả cho một quá trình tính toán

Chi phí phải trả cho một quá trình tính toán bao gồm chi phí về không

gian (bộ nhớ - số ô nhớ cần sử dụng trong quá trình tính toán) và chi phí về

thời gian (thời gian cần sử dụng cho một quá trình tính toán).

Nếu cho một thuật toán A. Thuật toán này thực hiện trên bộ dữ liệu e.

Khi đó kí hiệu

+ LA(e) là giá phải trả về không gian

+ TA(e) là giá phải trả về thời gian.

Khi đó ta có các khái niệm về chi phí phải trả trong các trường hợp như sau:

 Chi phí phải trả trong trường hợp xấu nhất: là chi phí trong trường hợp

ứng Input là xấu nhất đối với bài toán

 Chi phí phải trả trung bình: là tổng số các chi phí khác nhau ứng với

các bộ số liệu chia cho tổng số số bộ số liệu.

 Chi phí phải trả tiệm cận: là biểu thức biểu diễn tốc độ tăng của chi phí

thực tế phải trả. Nó có giá trị tiệm cận với chi phí thực tế.

Nhận xét: Ngày nay do sự phát triển không ngừng của khoa học công

nghệ kỹ thuật điện tử nên chi phí về bộ nhớ không còn là vấn đề cần thiết phải

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

bàn tới mà ta chỉ quan tâm tới chi phí phải trả về thời gian thực hiện giải

thuật. Từ đây ta chỉ xét đến thời gian thực hiện giải thuật T(n), hay đó chính

là độ phức tạp của thuật toán.

2.2.2. Độ phức tạp của thuật toán

Định nghĩa 1: Một hàm f(n) được xác định là O(g(n)), kí hiệu f(n) = O(g(n))

và được gọi là có cấp g(n) nếu tồn tại các hằng số c và n0 sao cho f(n) ≤

c.g(n) khi n ≥ n0.

Định nghĩa 2: Cho thuật toán T với bộ dữ liệu đầu vào có kích thước n. Nếu

số phép toán cơ bản để thực hiện việc biến đổi Input(T) thành Output(T) là

f(n). Khi đó ta gọi O(T)=f(n) là độ phức tạp của thuật toán T.

Chú ý: Khái niệm về độ phức tạp của thuật toán trên được hiểu theo nghĩa

khái niệm về vô cùng lớn khi n tiến ra vô cùng.

Thông thường các hàm thể hiện độ phức tạp tính toán của giải thuật có dạng:

O(log2n), O(n), O(nlog2n), O(n2), O(n3), O(2n), O(n!), O(nn).

Dưới đây là một số hàm số hay dùng để ký hiệu độ phức tạp tính toán

và bảng giá trị của chúng để tiện theo dõi sự tăng của hàm theo đối số n.

N n2 n3 2n log2n nlog2n

1 1 1 2 0 0

2 4 8 4 2 1

4 16 64 16 8 2

8 64 512 256 24 3

16 256 4096 65536 64 4

32 1024 32768 2.147.483.648 160 5

Bảng 2.1: Bảng giá trị độ phức tạp tính toán của các hàm số

Các hàm như 2n, nn được gọi là hàm loại mũ, ngoài ra còn có hàm n!

Và một số hàm khác có độ phức tạp lớn hơn các hàm mũ. Một giải thuật mà

thời gian thực hiện của nó có cấp là các hàm loại mũ thì tốc độ rất chậm. Các

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

như n3, n2, nlog2n, log2n được gọi là các hàm loại đa thức. Giải thuật với thời

gian thực hiện có cấp hàm đa thức thì thường hiệu quả và chấp nhận được.

2.2.3. Các qui tắc xác định độ phức tạp thuật toán

 Quy tắc cộng: Giả sử thuật toán T gồm 2 đoạn chương trình T1 và T2

thực hiện nối tiếp nhau Khi đó O(T)=O(T1)+O(T2).

 Quy tắc nhân: Giả sử thuật toán T gồm 2 đoạn chương trình T1 và T2

trong đó T2 được lồng trong T1. Khi đó O(T)=O(T1).O(T2).

 Quy tắc tổng quát:

- Thời gian thực hiện mỗi câu lệnh Gán, Read, Write là O(1).

- Thời gian thực hiện mỗi chuỗi tuần tự các câu lệnh được tính theo

quy tắc cộng

- Thời gian thực hiện vòng lặp được tính là tổng trên tất cả số lần lặp

thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng

lặp là hằng số thì thời gian thực hiện vòng lặp là tích của số lần lặp

với thời gian thực hiện thân vòng lặp.

2.3. Vấn đề phân lớp các bài toán dựa trên độ phức tạp thuật toán.

Khi cho một bài toán, có hai khả năng xảy ra là: bài toán không giải

được hoặc bài toán giải được. Trong thực tế có rất nhiều các bài toán không

thể giải trong thời gian chấp nhận được. Ví dụ bài toán treo (Halting Problem)

nổi tiếng của Turing không thể giải bất kỳ máy tính nào, bất kể cung cấp bao

nhiêu thời gian. Cũng có các bài toán có thể giải được, nhưng không phải trong thời gian đa thức O(nk) với một hằng k. Nói chung, ta xem các bài toán

có thể giải được bằng các thuật toán thời gian đa thức là “dễ trị”, và các bài

toán yêu cầu thời gian siêu đa thức là “khó trị”.

Vì độ phức tạp giải thuật đối với mỗi bài toán là khác nhau thông qua

thời gian, trên cơ sở đó các bài toán cũng được phân chia thành các lớp thông

qua độ phức tạp thuật toán.

2.3.1. Lớp bài toán P

Lớp bài toán P (Polynomial time – thời gian đa thức) là lớp các bài

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

toán dễ, có thể giải được bằng thuật toán đơn định đa thức.

2.3.2. Lớp NP

Lớp NP (Nondeterministic Polynomial – thời gian đa thức không tất

định) là lớp các bài toán có thể giải được bằng các thuật toán không đơn định

đa thức.

Nhận xét: Nhiều giả thiết đặt ra rằng liệu lớp P và lớp NP có đồng nhất

với nhau hay không? Điều đó đang còn là vấn đề mở chưa được làm sáng tỏ.

Bởi trong NP vẫn tồn tại lớp các bài toán không giải được bằng các thuật toán

đa thức, đó chính là sự có mặt của lớp NPC. Như vậy, chúng ta đang chấp

nhận P NP.

2.3.3. Lớp NPC

Định nghĩa 1: (Khái niệm dẫn về được): Bài toán B được gọi là dẫn về được

bài toán A một cách đa thức nếu có một thuật toán đơn định đa thức để giải

bài toán A thì cũng có một thuật toán đơn định đa thức để giải bài toán B. ký

hiệu B A. Khi đó bài toán A khó hơn bài toán B hay còn gọi B dễ hơn A

hay B là trường hợp riêng của A.

Quan hệ có tính bắc cầu: B C, C A B A.

Định nghĩa 2: (NP hard): Bài toán A được gọi là NP – khó nếu L A với L

NP.

Định nghĩa 3: (Bài toán NP đầy đủ): Bài toán A được gọi là NP đầy đủ nếu A

là NP khó và đồng thời A thuộc NP

Định nghĩa 4: Lớp NPC là lớp các bài toán NP đầy đủ, có độ phức tạp hàm

mũ. Qua đó cho thấy: P NPC = Ø.

NP

Hình 5: minh họa các lớp P, NP, NPC dưới dạng tập hợp.

NPC

P

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 2.1: Các lớp P, NP và NPC

2.4 Một số mô hình bài toán lớp NP

2.4.1 Mô hình bài toán xếp ba lô

Mô hình bài toán xếp ba lô là một trong những mô hình quan trọng

trong lý thuyết thuật toán. Chúng ta xét 2 mô hình cơ bản của bài toán:

2.4.1.1 Bài toán xếp ba lô 0-1

Input: + Cho n đồ vật, đồ vật thứ i có thể tích là a(i)

+ Cho 1 ba lô có thể tích b

Output: Hãy xác định nhóm đồ vật để đặt vừa khít ba lô

Nhận xét:

+ Bài toán trên có thể xác định lời giải chính xác bằng thuật toàn duyệt

toàn bộ theo tư tưởng như sau: Hãy duyệt mọi tổ hợp của các đồ vật, ứng với

mỗi tổ hợp (i1,i2,..,ik) thử điều kiện a(i1)+a(i2)+…+a(ik)=b để xác định

nghiệm đúng. Khi đó số phương án được duyệt chính bằng

tức là chúng ta có độ phức tạp của thuật toán

là hàm mũ.

+ Chúng ta có thể giải bài toán bằng thuật toán không đơn định đa thức

như sau: sử dụng hàm: CHOICE(0,1): là hàm chọn các đồ vật. Khi đó bài toán

được đưa về bài toán sau đây

Liệu có tồn tại tập chỉ số T {1,2,.. ,n} thỏa mãn .

Khi đó bài toán được giải bằng thuật toán sau đây:

For i:=1 to n do

xi:= CHOICE({0,1});

if =B then TRUE else FALSE

Thuật toán trở thành thuật toán không đơn định đa thức với độ phức tạp

O(n).

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

+ Bài toán trên có thể đưa về dạng tổng quát hơn bằng cách thay Output bằng:

“Hãy xác định nhóm đồ vật đặt trong balo sao cho phần thừa còn lại là ít

nhất”. Khi đó việc giải bài toán cũng được thực hiện tương tự, tuy nhiên

chúng ta phải đưa thêm hàm mục tiêu f=b-(a(i1)+a(i2)+…+a(ik)). Khi đó

phương án cần xác định là phương án thỏa mãn f đạt giá trị nhỏ nhất (f>=0).

2.4.1.2 Bài toán xếp ba lô mở rộng

Input: + Cho n đồ vật, đồ vật thứ i có thể tích là ai, có giá trị là pi

+ Cho 1 ba lô có thể tích b

Output: Hãy xác định nhóm đồ vật thỏa mãn: tổng thể tích không vượt quá ba

lô đồng thời tổng giá trị là lớn nhất

Nhận xét:

+ Bài toán trên có thể xác định lời giải chính xác bằng thuật toàn duyệt

toàn bộ theo tư tưởng như sau: Kí hiệu (x1,x2,…,xn) là một phương án lựa

chọn các đồ vật với xi {0,1}. Khi đó hãy duyệt mọi phương án

(x1,x2,…,xn), ứng với mỗi phương án xác định điều kiện

. Nếu thỏa mãn thì xác định tiếp giá trị hàm mục

tiêu từ đó xác định phương án tốt nhất.

Hiển nhiên bài toán đưa về bài toán duyệt mọi dãy nhị phân có độ dài n với

độ phức tạp hàm mũ.

Thuật toán giải được mô tả như sau:

using namespace std;

int X[N],A[N],b,P[N],n,fmax,Xluu[N];

void input()

{

cout<<"Nhap so do vat: ";cin>>n;

cout<<"Nhap the tich ba lo: ";cin>>b;

cout<<"Nhap the tich cac do vat: ";printf("\n");

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

for (int i=1;i<=n;i++) {cout<<"Do vat: "<>A[i];}

cout<<"Nhap gia tri cac do vat : ";printf("\n");

for (int i=1;i<=n;i++) {cout<<"Do vat: "<>P[i];}

fmax=0;

}

void output()

{ int f,T;

f=0;T=0;

for (int i=1;i<=n;i++) {T=T+X[i]*A[i];f=f+X[i]*P[i];}

if ((T<=b)&(f>fmax))

fmax=f; {

for (int i=1;i<=n;i++) Xluu[i]=X[i];}

}

void Try(int k)

{

int j;

for (j=0;j<=1;j++)

{ X[k]=j;if (k==n) output();else Try(k+1);}

}

int main()

{ input();

Try(1);

cout<<"Phuong an toi uu: ";

for (int i=1;i<=n;i++) cout<

cout<<"Gia tri toi uu fmax= "<

}

+ Tương tự, chúng ta có thể giải bài toán bằng thuật toán không đơn

định đa thức như sau: sử dụng hàm: CHOICE(0,1): là hàm chọn các đồ vật.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Khi đó bài toán được đưa về bài toán sau đây

và Liệu có tồn tại tập chỉ số T {1,2,.. ,n} thỏa mãn

đạt max. Khi đó bài toán được giải bằng thuật toán sau đây:

For i:=1 to n do

xi:= CHOICE({0,1});

if <=B then else FALSE

Thuật toán trở thành thuật toán không đơn định đa thức với độ phức tạp

O(n).

+ Bài toán Knaspack có thể giải bằng thuật toán GA với cấu trúc gen là dãy

nhị phân và toán tử lai ghép đa điểm hoặc lại ghép mặt nạ (Xem phụ lục)

2.4.2 Bài toán quân cờ Domino

2.4.2.1 Mô tả bài toán

Định nghĩa 1: Một quân bài Domino là một bộ (a,b) trong đó a là số hàng

trên, b là số hàng dưới

a

B

Định nghĩa 2: Phép lật quân được hiểu là một phép biến đổi bộ (a,b) thành bộ

(b,a)

Bài toán:

Input: Cho n quân bài Domino (a1,b1),(a2,b2),...(an,bn) xếp thành một hàng

ngang. Output: Hãy xác định các phép lật quân để sao cho độ chênh lệnh giữa

tổng các số hàng trên so với tổng các số hàng dưới đạt giá trị nhỏ nhất.

a1 a2 .... an-1 An

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

b1 b2 bn-1 Bn

Phân tích

+ Kí hiệu một phương án lật quân là một bộ X=(x1,x2,…,xn) trong đó

x(i)=1 tức là lật quân thứ i, x(i)=0 tức là không lật quân thứ i. Khi đó để tìm

phương án lật quân tối ưu, chúng ta có thể sử dụng thuật toàn duyệt toàn bộ

tất cả các phương án từ đó xác định phương án có độ chênh lệch nhỏ nhất. Kí

hiệu hàm mục tiêu

Khi đó sử dụng thuật toán duyệt tất cả các dãy nhị phân độ dài n bằng thuật

toán quay lui, ta mô tả thuật toán tìm lời giải chính xác của bài toán trên như

sau:

using namespace std;

int X[N],A[N],B[N],n,fmin,Xluu[N];

void swap(int &a,int &b)

{ int tg;tg=a;a=b;b=tg;}

void input()

{ int tren,duoi;

tren=0;duoi=0;

cout<<"Nhap so quan bai: ";cin>>n;

cout<<"Nhap gia tri hang duoi: ";printf("\n");

for (int i=1;i<=n;i++) {cin>>A[i];duoi=duoi+A[i];}

cout<<"Nhap gia tri hang tren : ";printf("\n");

for (int i=1;i<=n;i++) { cin>>B[i];tren=tren+B[i];}

fmin=abs(tren-duoi); cout<<"Do chenh ban dau "<

}

void output()

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

{ int f,tren,duoi;

tren=0;duoi=0;

for (int i=1;i<=n;i++) if (X[i]==1) swap(A[i],B[i]);

for (int i=1;i<=n;i++) {tren=tren+B[i];duoi=duoi+A[i];}

f=abs(tren-duoi);

if (f

}

void Try(int k)

{int j;

for (j=0;j<=1;j++)

{ X[k]=j;if (k==n) output();else Try(k+1);}

}

int main()

{ input();

Try(1);

cout<<"Phuong an lat quan toi uu: ";

for (int i=1;i<=n;i++) cout<

cout<<"do chenh be nhat= "<

}

Hiển nhiên thuật toán trên có độ phức tạp O(2n).

+ Ta có thể sử dụng thuật toán quy hoạch động để giải bài toán trên như

sau: Xây dựng mảng Wi là độ chênh lệch giữa phần trên và phần dưới của

quân bài thứ i. Gọi C(i,j) là số các phép lật nhỏ nhất với các quân cờ từ 1 đến

i, để hàng trên có tổng là j. Khi đó ta có công thức quy hoạch động:

C(i,j) = min {C(i-1, j-Tren(i)), C(i-1, Duoi(i))+1}.

Từ các C(i,j) ta dễ dàng tìm ra chênh lệch tối thiểu bằng thuật toán quy hoạch

động xác định mảng C. Tuy nhiên thuật toán trên cần đòi hỏi số ô nhớ là rất

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

lớn nếu số n là lớn

Có thể thấy rằng mô hình bài toán trên cũng là bài toán thuộc lớp NP.

+ Bài toán Domino có thể giải bằng thuật toán GA với cấu trúc gen là

dãy nhị phân và toán tử lai ghép đa điểm hoặc lại ghép mặt nạ (Xem phụ lục)

2.4.3 Mô hình bài toán TSP

Bài toán: Người giao hàng cần đi giao hàng tại n địa điểm. Người giao hàng

xuất phát từ một địa điểm xuất phát, đi qua các địa điểm khác để giao hàng và

trở về địa điểm ban đầu trong đó yêu cầu mỗi địa điểm chỉ đến một lần. Hãy

tìm một chu trình sao cho tổng quãng đường đi là nhỏ nhất.

Định lý 1: Bài toán TSP là NP đầy đủ. (Xem [1])

Nhận xét:

+ Bài toán trên có thể tìm được nghiệm chính xác bằng cách sử dụng

chiến lược duyệt toàn bộ các chu trình trong đồ thị bằng thuật toán quay lui từ

đó suy ra nghiệm tối ưu. Tuy nhiên độ phức tạp của thuật toán là O(n!) nên

thuật toán là không khả thi trong thực tế.

+ Có thể xây dựng thuật toán tìm nghiệm xấp xỉ tìm hành trình gần

đúng bằng cách sử dụng thuật toán cây cực tiểu MST-PRIM (áp dụng tìm cây

khung nhỏ nhất, hoạt động tương tự Dijkstra) để tìm các lộ trình ngắn nhất

trong đồ thị. Thuật toán được mô phỏng như sau

Procedure APPROX-TSP-TOUR:

APPROX-TSP-TOUR(G, c);

1 Lựa chọn đỉnh r V(G) là một đỉnh “gốc”.

2 Tăng tưởng một cây tỏa nhánh cực tiểu T cho G từ gốc r

(dùng MST-PRIM (G, c, r)) – Thuật toán tìm cây tỏa nhánh cực

tiểu.

3 Cho L là danh sách các đỉnh được ghé thăm trong một tầng cây

tiền cấp của T.

4 Return chu trình hamilton H ghé thăm các đỉnh theo thứ tự L có

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

độ dài nhỏ nhất.

Ta có thể chứng minh thuật toán APPROX-TSP-TOUR với một số điều

kiện nào đó về bộ dữ liệu đầu vào sẽ trả về một hành trình gần tối ưu .

Định lý 2: APPROX-TSP-TOUR là một thuật toán xấp xỉ có một cận tỷ số là

2 cho bài toán người bán hàng với bất đẳng thức tam giác” (Xem [1]).

Thời gian thực hiện của APPROX-TSP-TOUR là O(E) = O(V2), trong thời

gian đa thức. Thuật toán APPROX-TSP-TOUR trả về một hành trình có mức hao

phí không nhiều hơn gấp hai lần mức hao phí của một hành trình tối ưu.

+ Bài toán TSP có thể giải bằng thuật toán GA với vấn đề chọn cấu trúc

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

gen là dãy hoán vị và toán tử lai ghép đặc biệt (Xem [2])

Chương 3.

ỨNG DỤNG GIẢI THUẬT DI TRUYỀN

GIẢI BÀI TOÁN LẬP LỊCH GIẢNG DẠY THỰC HÀNH

3.1 Mô hình bài toán thực tế

Trong lớp các bài toán dạng NP và NPC thì lớp các bài toán lập lịch là

một lớp các bài toán rất quan trọng trong thực tế, có thể kể đến các mô hình:

Lập lịch kế hoạch sản xuất trong các xí nghiệp, lập lịch giảng dạy trong các

trường học, lập lịch bay cho các sân bay,… Trong luận văn, chúng tôi sẽ

nghiên cứu chi tiết bài toán lập lịch hướng dẫn thực hành tại mô hình trường

cao đẳng dạy nghề. Mô hình được tham khảo từ trường Cao đẳng Cơ khí

Luyện kim.

Chúng ta xét bài toán: Giả sử có một danh sách gồm NS các giáo viên

giảng dạy thực hành và một danh sách gồm NP các phòng giảng dạy thực

hành nghề cho sinh viên (Tiện, hàn, Cơ, Điện, Điện tử, Rèn,…). Biết rằng

mỗi giáo viên chỉ có thể hướng dẫn thực hành tại một số phòng thực hành phù

hợp với chuyên môn đào tạo và đồng thời mỗi giáo viên chỉ có thể sẵn sàng

nhận hướng dẫn thực hành theo lịch trong một số buổi xác định. Yêu cầu xếp

lịch hướng dẫn thực hành cho tất cả các giáo viên tại tất cả các phòng thực

hành trong 1 số hữu hạn các buổi để sao cho tại mọi buổi, tất cả các phòng

thực hành phải có giáo viên hướng dẫn phù hợp với chuyên môn đào tạo đồng

thời số buổi hướng dẫn của các giảng viên là tương đương nhau.

Xuất phát từ bài toán trên, chúng ta có mô hình toán học chi tiết cho bài

toán như sau:

Input

- Tập S={1,2,…,NS} số hiệu các giáo viên.

- Tập P={1,2,…,NP} số hiệu các phòng thực hành.

- Tập T={1,2,…,NT} số hiệu các buổi trong lịch toàn lịch hướng dẫn.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

- Mảng trạng thái TS(s,t) trạng thái sẵn sàng nhận hướng dẫn của giáo viên có

số hiệu s trong buổi hướng dẫn thứ t trong đó TS(s,t)=1 là sẵn sàng, TS(s,t)=0

là không sẵn sàng

- Mảng PS(s,p) biểu diễn sự phù hợp chuyên môn giữa các giáo viên và phòng

thực hành trong đó: PS(s,p)=1 chuyên môn giáo viên số hiệu s phù hợp với

phòng thực hành p, PS(s,p)=0 – Không phù hợp.

Các biến số

- Các biến quyết định X(p,t)=s – Giáo viên s được xếp vào phòng thực

hành p trong buổi hướng dẫn t.

- Các biến C(s) - Ghi lại tổng số buổi hướng dẫn của giáo viên s trong

toàn lịch phân công giảng dạy.

Các điều kiện ràng buộc:

H1: Tại một thời điểm t, 1 giáo viên chỉ được hướng dẫn nhiều nhất là 1

phòng thực hành.

H2: Chỉ xếp lịch hướng dẫn cho các giáo viên sẵn sàng trong buổi giảng dạy.

H3: Các giáo viên chỉ được phép hướng dẫn tại các phòng thực hành phù hợp

về chuyên môn.

H4: Tại mọi thời điểm, các phòng thực hành đều phải có giáo viên hướng dẫn.

Output

Hãy xếp lịch phân công hướng dẫn thực hành cho tất cả các giáo viên

thỏa mãn tất cả các ràng buộc H1,…,H4 sao cho tại mọi buổi, tất cả các

phòng thực hành phải có giáo viên hướng dẫn phù hợp với chuyên môn đào

tạo đồng thời số buổi hướng dẫn của các giảng viên là tương đương nhau.

Nhận xét: Bài toán trên là một dạng bài toán quy hoạch rời rạc có ràng buộc phi

tuyến tính. Để nhận được lời giải đúng, chúng ta có thể sử dụng phương pháp duyệt

toàn bộ từ đó kiểm tra các điều kiện để từ đó suy ra nghiệm tối ưu. Tuy nhiên việc

thiết kế thuật toán duyệt toàn bộ là rất khó đồng thời độ phức tạp của thuật toán là

hàm mũ. Do đó phương án duyệt toàn bộ là không khả thi. Sau đây chúng ta sẽ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

nghiên cứu việc thiết kế lời giải bài toán bằng giải thuật di truyền.

3.2 Thiết kế giải thuật di truyền GA

3.2.1 Xây dựng cấu trúc cá thể, các hàm kiểm tra

 Lựa chọn cấu trúc cá thể (phương án): Kí hiệu 1 phương án xếp lịch là

một ma trận X(NP,NT) trong đó X(p,t)=s, được hiểu là phân giáo viên

có số hiệu s hướng dẫn phòng thực hành p, tại buổi t, . Như vậy

tập hợp các phương án chính là tập hợp các ma trận các phần tử là các số

nguyên dương 0

 Xây dựng hàm C(s) chính bằng tổng tất cả các phần tử trong ma trận

phương án X thỏa mãn điều kiện X(p,t)=s, với mọi

Như vậy C(s) chính là tổng số buổi hướng dẫn của giáo viên s trong toàn lịch

phân công giảng dạy.

 Các ràng buộc cứng:

+ H1: Tại một thời điểm t, 1 giáo viên chỉ được giảng dạy nhiều nhất là 1

phòng thực hành sẽ tương đương với điều kiện: Trên một cột của ma trận X

không tồn tại 2 phần tử bằng nhau. Chúng ta kí hiệu hàm FH1(X) để kiểm tra

điều kiện H1 trong phương án X.

+ H2: Chỉ xếp lịch giảng dạy cho các giáo viên sẵn sàng trong buổi

giảng dạy tương ứng sẽ tương đương với điều kiện: Nếu X(p,t)=s thì T(s,t)=1

hay T(X(p,t),t)=1.

+ H3: Các giáo viên chỉ được phép hướng dẫn tại các phòng thực hành

phù hợp về chuyên môn đào tạo sẽ tương đương với điều kiện: Nếu X(p,t)=s

thì P(s,p)=1 hay P(X(p,t),p)=1.

Kết hợp 2 điều kiện H2 và H3, điều kiện thỏa mãn đồng thời H2 và H3

chính là

T(X(p,t),t)× P(X(p,t),p)=1; với mọi

Chúng ta kí hiệu hàm FH23(X) là hàm kiểm tra điều kiện H2 và H3 trong

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

phương án X.

+ H4: Tại mọi thời điểm, các phòng thực hành đều phải có giáo viên

hướng dẫn sẽ tương đương với tất cả các phần tử trong ma trận X đều dương.

X(p,t)>0; với mọi

Chúng ta kí hiệu hàm FH4(X) để kiểm tra điều kiện H4.

 Hàm mục tiêu của bài toán: Vì tổng số các buổi hướng dẫn của các

giáo viên luôn bằng NP×NT (Giả thiết tất cả các phòng thực hành đều phải xếp

kín tất cả các buổi), do đó để đảm bảo yêu cầu của bài toán: số các buổi hướng

dẫn của các giáo viên là xấp xỉ bằng nhau sẽ tương đương với: Hãy xác định

phương án X thỏa mãn tất cả các ràng buộc để sao cho hàm mục tiêu:

Như vậy bài toán lập lịch giảng dạy được đưa về bài toán: Hãy xác định

phương án X thỏa mãn các ràng buộc mô tả bởi các hàm ràng buộc FH1(X),

FH23(X), FH4(X) để sao cho hàm mục tiêu

3.2.2 Xây dựng các toán tử trong GA

 Các tham số đầu vào thuật toán

+ NS – Số các giáo viên cần xếp lịch giảng dạy (Các giáo viên được đánh số

liên tiếp từ 1..NS)

+ NP – Số các phòng thực hành (Các phòng được đánh số liên tiếp từ 1..NP).

+ NT - số các buổi trong lịch giảng dạy (Các buổi được đánh số liên tiếp từ

1..NT)

+ Mảng TS mô tả trạng thái sẵn sàng của các giáo viên

+ Mảng PS mô tả sự phù hợp chuyên môn của các giáo viên

+ Biến size – Kích thước của quần thể khởi tạo

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

Khởi tạo ngẫu nhiên N=size ma trận X kích thước NP×NT các phần tử

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

trong khoảng (0,NS+1), trên các cột của ma trận thỏa mãn các điều kiện

FH1(X) và FH23(X).

 Xác định độ thích nghi của các các cá thể trong quần thể.

 Xác định giá trị hàm mục tiêu ban đầu bằng cách với mỗi phương án

hãy xác định tất cả các giá trị C(s) từ đó tính tất cả các giá trị hàm F(X) tại

mọi cá thể từ đó suy ra F max xuất phát.

B2: Quá trình lai ghép-lựa chọn-đột biến

 Sử dụng toán tử lai ghép 2 điểm cắt theo chiều thời gian t giữa cá thể

thứ i (Bố) với cá thể thứ j (i

1)×(N-2) cá thể.

 Kiểm tra độ thích nghi của tất cả các cá thể, ta thu được M các thể thỏa mãn.

 Tính giá trị hàm F(X) với mọi các thể từ đó lựa chọn lấy N cá thể tốt nhất.

 Đột biến m các thể bất kì bằng cách thay đổi ngẫu nhiên 1 giá trị trong

ma trận X phù hợp với bài toán. ( - Xác suất đột biến).

 Quay lại bước 2 với N cá thể trong thế hệ tiếp sau.

Toàn bộ thuật toán được lập trình trong môi trường Matlab version 7.0 (Xem

phần phụ lục)

3.3 Các kết quả thực nghiệm

Sử dụng thuật toán đã thiết kế trên, chúng tôi thử nghiệm trên các bộ dữ

liệu thực trong các trường hợp sau đây:

3.3.1 Bộ số liệu Test 1

+ Số các giáo viên tham gia giảng dạy NS=10

+ Số các phòng thực hành cần hướng dẫn NP=5

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

+ Số các buổi trong lịch: NT=7 .

Bảng 3.1: Giáo viên phù hợp chuyên môn với phòng thực hành

(1-Phù hợp, 0-Không phù hợp)

Phòng 1 Phòng 2 Phòng 3 Phòng 4 Phòng 5

GV 1 0 1 1 1 1

GV 2 1 1 1 1 0

GV 3 1 0 1 1 1

GV 4 1 1 0 1 1

GV 5 1 1 1 0 1

GV 6 1 0 1 1 1

GV 7 1 1 1 1 0

GV 8 1 1 1 0 1

GV 9 0 1 1 1 1

GV 10 1 1 0 1 1

Bảng 3.2: Giáo viên sẵn sàng nhận buổi hướng dẫn

(1-Sẵn sàng, 0-Không sẵn sàng)

Buổi 1 Buổi 2 Buổi 3 Buổi 4 Buổi 5 Buổi 6 Buổi 7

GV 1 0 1 1 1 1 1 1

GV 2 1 1 1 1 0 1 1

GV 3 1 0 1 1 1 1 1

GV 4 1 1 0 1 1 1 1

GV 5 1 1 1 1 1 1 1

GV 6 1 1 1 0 1 1 1

GV 7 1 1 1 1 1 1 1

GV 8 1 1 1 1 1 1 1

GV 9 1 1 1 1 1 1 1

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

GV 10 1 1 1 1 1 1 1

Kết quả lần chạy thứ nhất : (popsize=40)

Bảng 3.3: Lịch giảng dạy Test 1

Buổi 1 Buổi 2 Buổi 3 Buổi 4 Buổi 5 Buổi 6 Buổi 7

4 2 7 5 6 5 Phòng 1 3

7 8 2 10 4 4 Phòng 2 9

6 6 9 6 8 3 Phòng 3 7

10 3 3 1 2 2 Phòng 4 10

9 1 5 8 9 1 Phòng 5 4

Bảng 3.4: Số buổi giảng dạy đối với các giáo viên Test 1

Gv1 Gv2 Gv3 Gv4 Gv5 Gv6 Gv7 Gv8 Gv9 Gv10

3 4 4 4 3 4 3 3 4 3

Kết quả Lần chạy thứ hai : (popsize=40)

Bảng 3.5: Lịch giảng dạy Test 1

Buổi 1 Buổi 2 Buổi 3 Buổi 4 Buổi 5 Buổi 6 Buổi 7

5 2 3 3 7 6 Phòng 1 3

10 9 8 10 4 2 Phòng 2 8

1 5 9 7 2 9 Phòng 3 2

6 7 7 1 9 10 Phòng 4 6

8 1 5 5 8 4 Phòng 5 4

Bảng 3.6 Số buổi giảng dạy đối với các giáo viên

Gv1 Gv2 Gv3 Gv4 Gv5 Gv6 Gv7 Gv8 Gv9 Gv10

3 4 3 3 4 3 4 4 4 3

Kết quả Lần chạy thứ ba (popsize=40)

Bảng 3.7 Lịch giảng dạy

Buổi 1 Buổi 2 Buổi 3 Buổi 4 Buổi 5 Buổi 6 Buổi 7

5 6 8 4 2 6 Phòng 1 10

8 9 5 9 8 2 Phòng 2 4

9 2 7 5 7 3 Phòng 3 8

1 3 4 3 1 7 Phòng 4 6

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

4 1 3 10 10 1 Phòng 5 9

Bảng 3.8 Số buổi giảng dạy đối với các giáo viên

Gv1 Gv2 Gv3 Gv4 Gv5 Gv6 Gv7 Gv8 Gv9 Gv10

4 3 4 4 3 3 3 4 4 3

3.3.2 Bộ số liệu Test 2 + Số các giáo viên tham gia giảng dạy NS=15 + Số các phòng thực hành cần hướng dẫn NP=7 + Số các buổi trong lịch: NT=14 .

Bảng 3.9: Bảng các giáo viên phù hợp chuyên môn với phòng thực hành

(1-Phù hợp, 0-Không phù hợp)

Phòng 1 Phòng 2 Phòng 3 Phòng 4 Phòng 5 Phòng 6 Phòng 7

Gv 1 0 1 1 1 1 1 0

Gv 2 0 1 1 1 1 1 0

Gv 3 1 0 0 1 1 1 1

Gv 4 1 0 0 1 1 1 1

Gv 5 1 1 1 0 1 0 1

Gv 6 1 1 1 0 1 0 1

Gv 7 1 1 1 1 0 1 0

Gv 8 1 1 1 1 0 1 0

Gv 9 0 1 0 1 1 1 1

Gv 10 0 1 0 1 1 1 1

Gv 11 1 0 1 0 1 1 1

Gv 12 1 0 1 0 1 1 1

Gv 13 1 1 1 1 0 0 1

Gv 14 1 1 1 1 0 0 1

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Gv 15 1 1 1 1 0 1 0

Bảng 3.10: Bảng các giáo viên sẵn sàng nhận buổi hướng dẫn

(1-Sẵn sàng, 0-Không sẵn sàng)

B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14

Gv 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1

Gv 2 1 1 1 1 0 1 1 0 1 1 1 1 1 1

Gv 3 1 0 1 1 1 0 1 1 1 1 1 1 1 1

Gv 4 1 1 0 1 1 1 1 1 1 1 1 1 0 1

Gv 5 1 1 1 0 1 1 1 1 1 1 0 1 1 1

Gv 6 1 1 1 1 0 1 1 1 1 1 1 1 1 0

Gv 7 1 1 1 1 1 1 0 1 1 1 1 0 1 1

Gv 8 1 1 0 1 1 1 1 1 1 1 1 1 0 1

Gv 9 1 1 1 1 1 1 1 0 1 0 1 1 1 1

Gv 1 1 1 1 0 1 1 1 1 1 1 1 1 0

10

Gv 1 0 1 1 1 1 1 1 1 1 1 1 0 1

11

Gv 1 1 0 1 1 1 1 1 1 1 1 0 1 1

12

Gv 1 1 1 0 1 1 1 1 1 1 0 1 1 1

13

Gv 1 1 1 1 0 1 1 1 1 0 1 1 1 1

14

Gv 1 1 1 1 1 0 1 1 0 1 1 1 1 1

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

15

Kết quả lần chạy thứ nhất:(popsize=40)

Bảng 3.11: Lịch giảng dạy Test 2

B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14

7 P1 8 7 7 8 5 5 12 6 14 13 12 13 11

5 P2 9 6 15 14 14 10 10 15 2 13 2 9 2

4 P3 15 10 3 7 15 2 15 8 4 1 9 2 12

P4 11 5 13 10 13 9 6 13 11 3 3 5 13 11

1 P5 12 1 11 12 14 12 8 6 2 7 12 14 14

9 P6 7 2 10 15 4 4 7 1 8 4 3 1 4

3 P7 5 9 9 6 10 5 11 6 9 6 11 5 3

Bảng 3.12: Số buổi giảng dạy đối với các giáo viên Test 2

G G G G G G G G G Gv Gv Gv Gv Gv Gv

v1 v2 v3 v4 v5 v6 v7 v8 v9 10 11 12 13 14 15

5 7 6 6 8 7 7 5 8 6 7 7 7 6 6

Kết quả Lần chạy thứ hai (popsize=40)

Bảng 3.13: Lịch giảng dạy

B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14

8 P1 14 5 14 11 6 14 15 6 3 15 14 7 12

1 P2 5 13 7 2 10 13 13 15 6 1 13 2 5

P3 2 15 10 15 11 1 1 3 10 15 2 4 15 2

P4 12 10 9 9 5 11 9 6 11 4 4 11 12 11

P5 8 6 11 7 13 12 8 5 6 8 12 8 13 13

P6 7 1 2 10 7 9 7 4 14 7 8 9 14 14

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

P7 9 12 6 4 4 2 3 11 12 5 11 3 1 9

Bảng 3.14: Số buổi giảng dạy đối với các giáo viên

G G G G G G G G G Gv Gv Gv Gv Gv Gv

v1 v2 v3 v4 v5 v6 v7 v8 v9 10 11 12 13 14 15

6 7 4 6 6 7 7 6 7 5 9 7 7 7 7

Kết quả Lần chạy thứ ba (popsize=40)

Bảng 3.15: Lịch giảng dạy

B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14

P1 14 12 6 13 14 11 15 5 3 3 3 8 6 7

P2 2 2 10 7 5 15 8 15 8 8 6 9 13 15

P3 10 8 2 11 11 1 10 11 7 12 15 12 12 12

P4 9 5 9 9 12 6 6 6 9 13 13 11 5 11

15 8 P5 12 15 1 13 14 14 2 2 7 5 7 8

10 9 P6 13 1 7 9 1 3 14 10 3 4 3 14

4 P7 5 10 11 4 4 1 3 4 1 5 12 5 11

Bảng 3.16: Số buổi giảng dạy đối với các giáo viên

G G G G G G G G G Gv Gv Gv Gv Gv Gv

v1 v2 v3 v4 v5 v6 v7 v8 v9 10 11 12 13 14 15

6 5 7 5 8 6 6 7 7 6 8 8 6 6 7

Thông qua các kết quả thực nghiệm kiểm tra thuật toán GA tìm phương

án xếp lịch giảng dạy tối ưu tại mô hình trường cao đẳng dạy nghề qua 2 bộ

số liệu Test1 và Test 2 giả định, chúng ta có thể thấy rằng thuật toán GA đề

xuất là khả thi, các kết quả nhận được là chấp nhận được trong thực tế. Thuật

toán có thể áp dụng tốt với bài toán lập lịch giảng dạy cho các trường dạy

nghề với các ràng buộc trong thực tế phát sinh. Trong trường hợp khi đề xuất

thêm các ràng buộc phức tạp hơn nữa, thuật toán vẫn có thể tìm ra lịch biểu

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

tối ưu (Trong trường hợp các ràng buộc đảm bảo bài toán phải có nghiệm).

KẾT LUẬN

Với mục tiêu đặt ra là tìm hiểu giải thuật di truyền ứng dụng vào lớp

các bài toán NP, luận văn đã đạt được một số kết quả như sau:

1. Tìm hiểu cơ chế cơ bản của giải thuật di truyền, các bước cơ bản

trong vấn đề thiết kế giải thuật. Các yêu cầu cần thiết.

2. Nghiên cứu các khái niệm cơ bản về thuật toán và độ phức tạp thuật

toán, vấn đề phân lớp các bài toán theo độ phức tạp

3. Tìm hiểu về lớp các bài toán NP và NPC. Nghiên cứu một số bài

toán cơ bản thuộc lớp NP cùng lời giải gần đúng.

4. Nghiên cứu xây dựng mô hình toán học của bài toán lập lịch giảng

dạy thực hành tại mô hình trường cao đẳng dạy nghề.

5. Xây dựng thuật toán GA giải mô hình bài toán lập lịch giảng dạy

thực hành.

6. Lập trình kiểm tra độ chính xác của thuật toán trên môi trường

Matlab với các bộ Test giả định.

Hướng phát triển tiếp theo của luận văn là tiếp tục nghiên cứu mô hình

lập lịch giảng dạy với các hệ ràng buộc phức tạp hơn. Ứng dụng thuật toán tại

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

các trường dạy nghề trong thực tế..

TÀI LIỆU THAM KHẢO

Tài liệu tiếng Việt

[1] Vũ Vinh Quang, Trương Hà Hải (2007), Lý thuyết thuật toán, Bài

giảng trường ĐH CNTT&TT.

[2] Vũ Vinh Quang, Nguyễn Hiền Trinh (2010), Giải thuật di truyền ,

Bài giảng trường ĐH CNTT&TT.

[3] Trần Kim Hương, Nguyễn Thị Ngọc Chi, Giải thuật di truyền (Gas)

và các ứng dụng, Hội nghị NCKH khoa SP Toán –Tin, Tháng 5/2015.

Tài liệu tiếng Anh

[4] David, A.Coley: An Instroduction to Genetic Algorithm.

[5] Eiben, E. et al (1994), Genetic algorithms with multi-parent

recombination. PPSN III: Proceedings of the International Comference on

Evolutionary Computation 78-87.

[6] Charbonneau, Paul (1995), Genetic algorithms in astronomy and

astrophysics, The Astrophysical Jornal Supplement Series, vol 101, pp. 309-

334.

[7] Adam Marcryk (2004), Genetic Algorithms and Evolutionary

Computation.

[8] Randy L.Haupt and Douglas, Genetic Algorithms in

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Electromagnetics.

PHẦN PHỤ LỤC

1. Bộ số liệu Test 1

function lap_lich=lap_lich

clear all;

clc;

popsize=40;

NP=5;NT=7;NS=10;

TS=ones(NS,NT);

PS=ones(NS,NP);

PS(1,2)=0;PS(1,5)=0;

PS(2,1)=0;PS(2,3)=0;

PS(3,3)=0;PS(3,5)=0;

PS(4,1)=0;PS(4,2)=0;

PS(5,3)=0;

PS(6,5)=0;

PS(7,3)=0;

PS(8,4)=0;

PS(9,1)=0;PS(9,5)=0;

PS(10,1)=0;PS(10,5)=0;

TS(1,2)=0;

TS(2,5)=0;

TS(3,6)=0;

TS(4,7)=0;

TS(5,4)=0;

TS(6,2)=0;

TS(7,1)=0;

TS(8,5)=0;

TS(9,7)=0;

TS(10,6)=0;

% Khoi tao Quan the ban dau

k=0;

while (k

cathe=Y(TS,PS,NP,NT,NS);

k=k+1

X(:,:,k)=cathe;

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

cathe

end;

n=0;

while n<100

n=n+1;

% Lai ghep 2 diem cat

K=3;L=5;

N=popsize;

for i=1:popsize-1;

for j=i+1:popsize

bo=X(:,:,i);me=X(:,:,j);

for p=1:NP

for t=1:K

con1(p,t)=bo(p,t);con2(p,t)=me(p,t);

end;

for t=K+1:L

con1(p,t)=me(p,t);con2(p,t)=bo(p,t);

end;

for t=L+1:NT

con1(p,t)=bo(p,t);con2(p,t)=me(p,t);

end;

end;

if (FH23(con1,TS,PS,NP,NT)==1)

N=N+1;

X(:,:,N)=con1;

end;

if (FH23(con2,TS,PS,NP,NT)==1)

N=N+1;

X(:,:,N)=con2;

end;

end;

end;

% Chon loc

for k=1:N

FF(k)=F(X(:,:,k),NP,NT,NS);

end;

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

for i=1:N-1

for j=i+1:N

if FF(i)

tgf=FF(i);FF(i)=FF(j);FF(j)=tgf;

tgX=X(:,:,i);X(:,:,i)=X(:,:,j);X(:,:,j)=tgX;

end;

end;

end;

end;

for s=1:NS

C(s)=0;

for p=1:NP

for t=1:NT

if (X(p,t,1)==s)

C(s)=C(s)+1;

end;

end;

end;

end;

C

phuong_an_toi_uu=X(:,:,1)

%%%%%% cac ham

function Y=Y(TS,PS,NP,NT,NS)

for t=1:NT

B=ones(NS,1);

p=1;

while (p<=NP)

a=round(NS*rand(1))+1;

if and(a>0,a<=NS)

if and(and(B(a)==1,TS(a,t)==1),PS(a,p)==1)

B(a)=0;A(p,t)=a;

p=p+1;

end;

end;

end;

end;

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Y=A;

function FH23=FH23(Y,TS,PS,NP,NT)

count=0;

p=0;a=1;

while and(p

p=p+1;t=p+1;

while and(t

t=t+1;

if (TS(Y(p,t),t)*PS(Y(p,t),p)==0)

a=0;

end;

end;

end;

FH23=a;

%if (count==NT*NP) FH23=1; else FH23=0;end;

function F=F(Y,NP,NT,NS)

T=1;

for s=1:NS

C(s)=0;

for p=1:NP

for t=1:NT

if (Y(p,t)==s)

C(s)=C(s)+1;

end;

end;

end;

T=T*C(s);

end;

F=T;

2. Bộ số liệu Test 2

function lap_lich=lap_lich

clear all;

clc;

popsize=40;

NP=7;NT=14;NS=10;

TS=ones(NS,NT);

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

PS=ones(NS,NP);

PS(1,2)=0;PS(1,6)=0;

PS(2,1)=0;PS(2,5)=0;

PS(3,2)=0;PS(3,4)=0;

PS(4,1)=0;PS(4,7)=0;

PS(5,5)=0;PS(5,6)=0;

PS(6,3)=0;PS(6,7)=0;

PS(7,4)=0;PS(7,5)=0;

PS(8,4)=0;PS(8,6)=0;

PS(9,3)=0;PS(9,5)=0;

%PS(10,1)=0;PS(10,5)=0;

%PS(11,2)=0;PS(11,6)=0;

%PS(12,2)=0;PS(12,6)=0;

%PS(13,3)=0;PS(13,7)=0;

%PS(14,3)=0;PS(14,7)=0;

%PS(15,4)=0;PS(15,7)=0;

TS(1,1)=0;

TS(2,5)=0;

TS(3,7)=0;

TS(4,13)=0;

TS(5,14)=0;

TS(6,6)=0;

TS(7,12)=0;

TS(8,11)=0;

TS(9,6)=0;

TS(10,2)=0;

%TS(11,2)=0;TS(10,13)=0;

%TS(12,3)=0;TS(10,12)=0;

%TS(13,4)=0;TS(10,11)=0;

%TS(14,5)=0;TS(10,10)=0;

%TS(15,6)=0;TS(10,9)=0;

% Khoi tao Quan the ban dau

k=0;

while (k

cathe=Y(TS,PS,NP,NT,NS);

k=k+1

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

X(:,:,k)=cathe;

cathe

end;

n=0;

while n<100

n=n+1;

% Lai ghep 2 diem cat

K=5;L=10;

N=popsize;

for i=1:popsize-1;

for j=i+1:popsize

bo=X(:,:,i);me=X(:,:,j);

for p=1:NP

for t=1:K

con1(p,t)=bo(p,t);con2(p,t)=me(p,t);

end;

for t=K+1:L

con1(p,t)=me(p,t);con2(p,t)=bo(p,t);

end;

for t=L+1:NT

con1(p,t)=bo(p,t);con2(p,t)=me(p,t);

end;

end;

if (FH23(con1,TS,PS,NP,NT)==1)

N=N+1;

X(:,:,N)=con1;

end;

if (FH23(con2,TS,PS,NP,NT)==1)

N=N+1;

X(:,:,N)=con2;

end;

end;

end;

% Chon loc

for k=1:N

FF(k)=F(X(:,:,k),NP,NT,NS);

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

end;

for i=1:N-1

for j=i+1:N

if FF(i)

tgf=FF(i);FF(i)=FF(j);FF(j)=tgf;

tgX=X(:,:,i);X(:,:,i)=X(:,:,j);X(:,:,j)=tgX;

end;

end;

end;

end;

for s=1:NS

C(s)=0;

for p=1:NP

for t=1:NT

if (X(p,t,1)==s)

C(s)=C(s)+1;

end;

end;

end;

end;

C

phuong_an_toi_uu=X(:,:,1)

%%%%%% cac ham

function Y=Y(TS,PS,NP,NT,NS)

for t=1:NT

B=ones(NS,1);

p=1;

while (p<=NP)

a=round(NS*rand(1))+1;

if and(a>0,a<=NS)

if and(and(B(a)==1,TS(a,t)==1),PS(a,p)==1)

B(a)=0;A(p,t)=a;

p=p+1;

end;

end;

end;

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

end;

Y=A;

function FH23=FH23(Y,TS,PS,NP,NT)

count=0;

p=0;a=1;

while and(p

p=p+1;t=p+1;

while and(t

t=t+1;

if (TS(Y(p,t),t)*PS(Y(p,t),p)==0)

a=0;

end;

end;

end;

FH23=a;

%if (count==NT*NP) FH23=1; else FH23=0;end;

function F=F(Y,NP,NT,NS)

T=1;

for s=1:NS

C(s)=0;

for p=1:NP

for t=1:NT

if (Y(p,t)==s)

C(s)=C(s)+1;

end;

end;

end;

T=T*C(s);

end;

F=T;

3. Bài toán Domino

function domino=domino(tren,duoi,KK)

clc;

N=length(tren);

M=10;%popsize

%Khoi tao

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

z=round(rand(M,N));

for i=1:M

for j=1:N

if z(i,j)==0

A(i,j)=tren(j);

B(i,j)=duoi(j);

else

A(i,j)=duoi(j);

B(i,j)=tren(j);

end;

end;

end;

% thuat toan GA

count=0;k=3;

while count

count=count+1;

% Lai ghep

socon=M;

for i=1:M-1

for j=i+1:M

bo=[A(i,:);B(i,:)];me=[A(j,:);B(j,:)];

for j1=1:k

con1(:,j1)=bo(:,j1);

con2(:,j1)=me(:,j1);

end;

for j2=k+1:N

con1(:,j2)=me(:,j2);

con2(:,j2)=bo(:,j2);

end;

socon=socon+1;

A(socon,:)=con1(1,:);

B(socon,:)=con1(2,:);

socon=socon+1;

A(socon,:)=con2(1,:);

B(socon,:)=con2(2,:);

end;

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

end;

for i=1:socon

sa=0;

sb=0;

for j=1:N

sa=sa+A(i,j);

sb=sb+B(i,j);

end;

f(i)=abs(sa-sb);

end;

% Phep chon loc

for i=1:socon-1

for j=i+1:socon

if f(i)>f(j)

tgf=f(i);f(i)=f(j);f(j)=tgf;

tgA=A(i,:);A(i,:)=A(j,:);A(j,:)=tgA;

tgB=B(i,:);B(i,:)=B(j,:);B(j,:)=tgB;

end;

end;

end;

% Dot bien con thu 7 vi tri so 5

tg=A(7,5);A(7,5)=B(7,5);B(7,5)=tg;

end;

% Phuong an toi uu

quan_hang_tren=tren

quan_hang_duoi=duoi

phuong_an_toi_uu=A(1,:)

B(1,:)

Gia_tri_toi_uu=f(1)

4. Bài toán Knaspsack

function balo=balo(A,C,b,KK)

clc;

N=length(A);

M=10;%popsize

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

%Khoi tao

M=0;

while M<=10

z=round(rand(1,N));

s=0;

for i=1:N

s=s+A(i)*z(i);

end;

if s<=b

M=M+1;

Quan_the(M,:)=z;

end;

end;

% thuat toan GA

count=0;k=3;

while count

count=count+1;

% Lai ghep

socon=M;

for i=1:M-1

for j=i+1:M

bo=Quan_the(i,:);me=Quan_the(j,:);%Lai ghep don diem

for j1=1:k

con1(j1)=bo(j1);

con2(j1)=me(j1);

end;

for j2=k+1:N

con1(j2)=me(j2);

con2(j2)=bo(j2);

end;

s1=0;

for l=1:N

s1=s1+A(l)*con1(l);

end;

if s1<=b

socon=socon+1;

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Quan_the(socon,:)=con1;

end;

s2=0;

for l=1:N

s2=s2+A(l)*con2(l);

end;

if s2<=b

socon=socon+1;

Quan_the(socon,:)=con2;

end;

end;

end; %Ket thuc lai ghep

% Chon loc

for i=1:socon

f(i)=0;

for j=1:N

f(i)=f(i)+Quan_the(i,j)*C(j);

end;

end;

for i=1:socon-1

for j=i+1:socon

if f(i)

tgf=f(i);f(i)=f(j);f(j)=tgf;

tgz=Quan_the(i,:);Quan_the(i,:)=Quan_the(j,:);Quan_the(j,:)=tgz;

end;

end;

end;

end; %ket thuc GA

% Phuong an toi uu

The_tich_do_vat=A

Gia_tri_do_vat=C

The_tich_ba_lo=b

phuong_an_toi_uu=Quan_the(1,:)

gia_tri_toi_uu=f(1)

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

.............................................................................................................................

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

.............................................................................................................................