Nghiên cứu giải bài toán cực tiểu hóa độ trễ bằng các thuật toán tối ưu

Luận án tiến sĩ nghiên cứu các thuật toán đúng gần đúng giải bài toán cực tiểu hóa độ trễ, phát triển phương pháp mới, đánh giá hiệu quả ứng dụng trong lĩnh vực toán học tại Việt

• Tác giả: Ban Hà Bằng
• Người hướng dẫn: PGS. Nguyễn Đức Nghĩa
• Trường học: Đại học Bách Khoa Hà Nội
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên cứu giải bài toán cực tiểu hóa độ trễ bằng các thuật toán tối ưu
• Loại tài liệu: luận án
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng Quan Về Bài Toán Cực Tiểu Hóa Độ Trễ MLP Là Gì

Bài toán cực tiểu hóa độ trễ (Minimum Latency Problem - MLP) là một vấn đề quan trọng trong lĩnh vực tối ưu hóa tổ hợp. Nó xuất hiện trong nhiều ứng dụng thực tế, từ lập lịch công việc đến tìm đường đi trên mạng và tìm kiếm thông tin. Về cơ bản, bài toán MLP tìm cách xác định một hành trình đi qua tất cả các đỉnh của một đồ thị, bắt đầu từ một đỉnh xuất phát, sao cho tổng độ trễ của tất cả các đỉnh trên hành trình là nhỏ nhất. Độ trễ của một đỉnh được định nghĩa là độ dài đường đi từ đỉnh xuất phát đến đỉnh đó. Bài toán MLP là một dạng khác của bài toán thợ sửa chữa lưu động (Traveling repairman problem – TRP) và bài toán người giao hàng (Delivery man problem – DMP).

1.1. Ứng dụng thực tiễn của bài toán cực tiểu hóa độ trễ

Bài toán cực tiểu hóa độ trễ có nhiều ứng dụng thực tiễn quan trọng. Trong lý thuyết lập lịch, nó giúp lên kế hoạch phục vụ các yêu cầu sao cho tổng thời gian chờ đợi là nhỏ nhất. Trong mạng máy tính, nó được dùng để tìm hành trình với tổng độ trễ thấp nhất. Trong tìm kiếm thông tin, nó giúp giảm độ trễ khi tìm kiếm trên mạng. Theo nghiên cứu của Ban Hà Bằng, bài toán MLP có thể ứng dụng để cực tiểu hóa độ trễ của việc tìm kiếm thông tin trên mạng [42].

1.2. Tính chất NP khó của bài toán cực tiểu hóa độ trễ

Bài toán cực tiểu hóa độ trễ (MLP) thuộc lớp bài toán NP-khó trong trường hợp tổng quát, ngay cả khi đồ thị là cây có trọng số. Điều này có nghĩa là không có thuật toán nào có thể giải bài toán này một cách tối ưu trong thời gian đa thức, trừ khi P=NP. Do đó, các nhà nghiên cứu thường tìm kiếm các thuật toán gần đúng hoặc heuristic để tìm ra các giải pháp chấp nhận được trong thời gian hợp lý. Ban Hà Bằng đã chỉ ra rằng, ngoại trừ P = NP, một lược đồ xấp xỉ với thời gian đa thức trong trường hợp tổng quát là không tồn tại [41].

II. Thách Thức Trong Giải Bài Toán Tối Ưu Hóa Độ Trễ MLP

Giải bài toán tối ưu hóa độ trễ (MLP) đặt ra nhiều thách thức đáng kể. Một trong những khó khăn chính là tính chất NP-khó của bài toán, khiến việc tìm kiếm giải pháp tối ưu trở nên bất khả thi đối với các bài toán có kích thước lớn. Hơn nữa, bài toán MLP không có đặc tính cục bộ giống như bài toán TSP, nghĩa là một thay đổi nhỏ trong hành trình có thể dẫn đến sự thay đổi lớn trong hàm mục tiêu. Điều này gây khó khăn cho việc thiết kế các thuật toán chia để trị. Theo Blum et al. [6], bài toán MLP được xem là khó hơn so với bài toán TSP.

2.1. Sự khác biệt giữa MLP và bài toán người du lịch TSP

Mặc dù cả MLP và TSP đều liên quan đến việc tìm kiếm một hành trình tối ưu, nhưng có những khác biệt quan trọng giữa hai bài toán này. Trong TSP, việc hoán đổi vị trí của một vài đỉnh trong hành trình chỉ gây ra sự thay đổi cục bộ trong hàm mục tiêu. Tuy nhiên, trong MLP, việc hoán đổi tương tự có thể dẫn đến sự thay đổi lớn trong tổng độ trễ. Điều này làm cho MLP trở nên khó giải hơn so với TSP.

2.2. Tính nhạy cảm của MLP với thay đổi trong đồ thị đầu vào

Một thách thức khác của bài toán cực tiểu hóa độ trễ là tính nhạy cảm của nó với những thay đổi nhỏ trong đồ thị đầu vào. Một thay đổi nhỏ trong đồ thị có thể dẫn đến sự thay đổi lớn trong hành trình tối ưu. Điều này gây khó khăn cho việc thiết kế các thuật toán ổn định và hiệu quả. Ban Hà Bằng đã chỉ ra rằng chỉ cần một thay đổi nhỏ trong đồ thị đầu vào, đã có thể dẫn đến sự thay đổi lớn trong hành trình tối ưu của bài toán [43].

2.3. Khó khăn trong việc áp dụng phương pháp chia để trị

Do tính chất phức tạp của bài toán tối ưu hóa độ trễ, việc áp dụng phương pháp chia để trị trở nên khó khăn. Các bài toán bộ phận có mối liên hệ chặt chẽ với nhau, khiến việc tìm ra cách chia bài toán thành các phần nhỏ hơn và giải chúng một cách độc lập trở nên bất khả thi. Do đó, cần có các phương pháp tiếp cận khác để giải quyết bài toán MLP.

III. Thuật Toán Nhánh Cận Giải Bài Toán Cực Tiểu Hóa Độ Trễ

Thuật toán nhánh cận (Branch and Bound) là một phương pháp tiếp cận đúng để giải bài toán cực tiểu hóa độ trễ. Thuật toán này tìm kiếm lời giải tối ưu bằng cách duyệt qua không gian tìm kiếm một cách có hệ thống, đồng thời loại bỏ các nhánh không tiềm năng dựa trên việc đánh giá cận dưới của chi phí. Mặc dù thuật toán nhánh cận có thể tìm ra lời giải tối ưu, nhưng nó có thể tốn rất nhiều thời gian tính toán, đặc biệt đối với các bài toán có kích thước lớn.

3.1. Lược đồ thuật toán nhánh cận cho bài toán MLP

Thuật toán nhánh cận cho bài toán cực tiểu hóa độ trễ bắt đầu bằng việc xây dựng một cây tìm kiếm, trong đó mỗi nút đại diện cho một phần của hành trình. Thuật toán sử dụng một hàm đánh giá để tính cận dưới của chi phí cho mỗi nút. Nếu cận dưới của một nút lớn hơn chi phí của lời giải tốt nhất hiện tại, thì nút đó và tất cả các nút con của nó sẽ bị loại bỏ. Quá trình này tiếp tục cho đến khi tìm thấy lời giải tối ưu hoặc toàn bộ không gian tìm kiếm đã được duyệt qua.

3.2. Kết quả thực nghiệm của thuật toán nhánh cận

Ban Hà Bằng đã thực hiện các thử nghiệm trên các bộ dữ liệu ngẫu nhiên và thực tế để đánh giá hiệu quả của thuật toán nhánh cận. Kết quả cho thấy thuật toán có thể tìm ra lời giải tối ưu cho các bài toán có kích thước nhỏ (lên đến 40 đỉnh). Tuy nhiên, thời gian chạy của thuật toán tăng lên đáng kể khi kích thước bài toán tăng lên.

IV. Các Thuật Toán Gần Đúng Cận Tỷ Lệ Cho Bài Toán MLP

Các thuật toán gần đúng cận tỷ lệ là một hướng tiếp cận khác để giải bài toán cực tiểu hóa độ trễ. Các thuật toán này không đảm bảo tìm ra lời giải tối ưu, nhưng chúng đảm bảo rằng lời giải tìm được sẽ không tệ hơn một tỷ lệ nhất định so với lời giải tối ưu. Các thuật toán gần đúng cận tỷ lệ thường có thời gian chạy nhanh hơn so với các thuật toán đúng, nhưng chúng có thể không tìm ra lời giải tốt nhất.

4.1. Đánh giá hiệu quả của các thuật toán gần đúng cận tỷ lệ

Ban Hà Bằng đã đánh giá hiệu quả của một số thuật toán gần đúng cận tỷ lệ hiện có cho bài toán cực tiểu hóa độ trễ. Kết quả cho thấy các thuật toán này có thể tìm ra các giải pháp chấp nhận được trong thời gian hợp lý, nhưng chất lượng của các giải pháp này có thể khác nhau tùy thuộc vào thuật toán và bộ dữ liệu.

4.2. Thuật toán dựa trên phương pháp Subgradient

Một trong những thuật toán gần đúng cận tỷ lệ được nghiên cứu là thuật toán dựa trên phương pháp Subgradient. Thuật toán này sử dụng phương pháp Subgradient để tìm cận dưới của chi phí và sau đó sử dụng cận dưới này để xây dựng một lời giải gần đúng. Kết quả thực nghiệm cho thấy thuật toán này có thể tìm ra các giải pháp tốt trong một số trường hợp.

V. Các Thuật Toán Meta Heuristic Giải Bài Toán Cực Tiểu Độ Trễ

Các thuật toán meta-heuristic là một họ các thuật toán tìm kiếm gần tối ưu được sử dụng rộng rãi để giải các bài toán tối ưu hóa tổ hợp khó, bao gồm cả bài toán cực tiểu hóa độ trễ. Các thuật toán meta-heuristic không đảm bảo tìm ra lời giải tối ưu, nhưng chúng thường có thể tìm ra các giải pháp tốt trong thời gian hợp lý. Một số thuật toán meta-heuristic phổ biến bao gồm thuật toán di truyền, thuật toán đàn kiến, thuật toán Tabu và thuật toán lân cận biến đổi.

5.1. Thuật toán di truyền GA cho bài toán MLP

Thuật toán di truyền (GA) là một thuật toán meta-heuristic dựa trên các nguyên tắc của tiến hóa sinh học. Trong thuật toán GA, một quần thể các lời giải tiềm năng được duy trì và cải thiện thông qua các phép toán như lai ghép và đột biến. Ban Hà Bằng đã đề xuất một thuật toán GA để giải bài toán cực tiểu hóa độ trễ và tích hợp một số kỹ thuật mới vào từng bước của thuật toán.

5.2. Thuật toán lai ghép đàn kiến ACO GA

Để nâng cao chất lượng lời giải và thời gian chạy thuật toán, Ban Hà Bằng đã đề xuất một thuật toán meta-heuristic lai ghép giữa thuật toán di truyền (GA) và thuật toán đàn kiến (ACO). Thuật toán này kết hợp các ưu điểm của cả hai thuật toán để tìm ra các giải pháp tốt hơn.

5.3. Thuật toán lai Tabu và lân cận biến đổi TS VNS

Một thuật toán meta-heuristic lai khác được đề xuất là thuật toán lai ghép giữa thuật toán Tabu (TS) và thuật toán lân cận biến đổi (VNS). Thuật toán này sử dụng thuật toán Tabu để tránh các lời giải cục bộ và thuật toán lân cận biến đổi để khám phá không gian tìm kiếm một cách hiệu quả.

VI. Đánh Giá Hiệu Quả Các Thuật Toán Tối Ưu Hóa Độ Trễ MLP

Để đánh giá hiệu quả của các thuật toán đề xuất, Ban Hà Bằng đã tiến hành thực nghiệm trên các bộ dữ liệu chuẩn và so sánh kết quả thu được với kết quả của các công trình nghiên cứu liên quan. Kết quả thực nghiệm chỉ ra rằng các thuật toán đề xuất đưa ra lời giải tốt hơn các thuật toán tốt nhất hiện biết trên nhiều bộ dữ liệu.

6.1. So sánh kết quả thực nghiệm trên các bộ dữ liệu chuẩn

Các thuật toán được đánh giá trên nhiều bộ dữ liệu chuẩn khác nhau để đảm bảo tính khách quan và toàn diện. Kết quả cho thấy các thuật toán đề xuất có hiệu quả tốt hơn so với các thuật toán hiện có trên nhiều bộ dữ liệu.

6.2. So sánh với các công trình nghiên cứu liên quan

Kết quả của các thuật toán đề xuất được so sánh với kết quả của các công trình nghiên cứu liên quan để đánh giá mức độ cải thiện so với các phương pháp hiện có. Kết quả cho thấy các thuật toán đề xuất có thể đưa ra các giải pháp tốt hơn so với các thuật toán tốt nhất hiện biết.

Trích đoạn nội dung tài liệu

ĐH Bách khoa Hà Nội Ban Hà Bằng Các thuật toán đúng gần đúng giải bài toán cực tiểu hóa độ trễ Chuyên ngành: Khoa học máy tính Mã số: 62480101 Nghiên cứu sinh: Ban Hà Bằng Người hướng dẫn khoa học: PGS. Nguyễn Đức Nghĩa 2014 LỜI CAM ĐOAN Tôi xin cam đoan luận án này là kết quả nghiên cứu của tôi. Các kết quả viết chung với các tác giả khác đều đã được sự nhất trí của các đồng tác giả khi đưa vào luận án. Những kiến thức tham khảo để hoàn thành luận án đều được trích dẫn đầy đủ từ danh mục tài liệu tham khảo.

Hà Nội, 04-2014 Người hướng dẫn khoa học Tác giả luận án PGS. Nguyễn Đức Nghĩa Ban Hà Bằng i LỜI CẢM ƠN Luận án này được hoàn thành tại Bộ môn Khoa học Máy tính, Viện Công nghệ Thông tin và Truyền thông, Trường Đại học Bách Khoa Hà Nội dưới sự hướng dẫn của PGS. Nguyễn Đức Nghĩa. Tôi xin chân thành cảm ơn Thầy hướng dẫn, người đã trực tiếp hướng dẫn khoa học và tận tình giúp đỡ tôi trong quá trình nghiên cứu.

Tôi xin bày tỏ lòng biết ơn tới Bố Mẹ và Gia đình đã giúp đỡ, tạo điều kiện cho tôi trong quá trình học tập và hoàn thành luận án này. Tôi cũng xin gửi lời cảm ơn tới các thầy cô trong Viện Công Nghệ Thông Tin, cũng như các thầy cô trong trường Đại học Bách khoa Hà Nội đã truyền thụ những kiến thức bổ ích trong quá trình tôi học tập và nghiên cứu tại Trường. Mặc dù đã rất cố gắng nhưng do thời thời gian và kiến thức còn hạn chế nên luận án chắc còn có nhiều thiếu sót. Tôi rất mong nhận được những ý kiến đóng góp quý báu từ các Thầy Cô và các bạn.

ii Mục Lục LỜI CAM ĐOAN .v Danh mục thuật ngữ .vii Danh mục bảng .viii Danh mục hình vẽ .x CHƢƠNG 1 TỔNG QUAN VỀ BÀI TOÁN .1 Mô hình toán học của bài toán cực tiểu hóa độ trễ .2 Một số hướng tiếp cận giải bài toán tối ưu hóa tổ hợp .1 Thuật toán nhánh cận .2 Thuật toán di truyền .3 Thuật toán đàn kiến .4 Thuật toán Tabu .5 Thuật toán lân cận biến đổi .3 Các nghiên cứu liên quan giải bài toán MLP .1 Thuật toán đúng .2 Thuật toán gần đúng cận tỷ lệ .3 Thuật toán meta-heuristic .4 Mục đích, phạm vi nghiên cứu .5 Dữ liệu thực nghiệm.6 Kết quả của luận án .7 Cấu trúc của luận án. 20 CHƢƠNG 2 THUẬT TOÁN NHÁNH CẬN .1 Lược đồ thuật toán .2 Kết quả thực nghiệm .1 Thực nghiệm bộ dữ liệu ngẫu nhiên.2 Thực nghiệm bộ dữ liệu thực .3 Kết luận chương 2. 35 CHƢƠNG 3 CÁC THUẬT TOÁN GẦN ĐÚNG CẬN TỶ LỆ .1 Đánh giá thực nghiệm hiệu quả của các thuật toán gần đúng cận tỷ lệ .1 Các thuật toán gần đúng cận tỷ lệ .2 Kết quả thực nghiệm .2 Thuật toán dựa trên phương pháp Subgradient .1 Lược đồ thuật toán .2 Kết quả thực nghiệm .3 Kết luận chương 3. 65 CHƢƠNG 4 CÁC THUẬT TOÁN META-HEURISTIC.

Thuật toán di truyền .1 Lược đồ của thuật toán .2 Kết quả thực nghiệm .2 Thuật toán di truyền lai ghép đàn kiến .1 Lược đồ của thuật toán .2 Kết quả thực nghiệm .3 Thuật toán lai thuật toán Tabu và thuật toán lân cận biến đổi .1 Lược đồ của thuật toán .2 Kết quả thực nghiệm .4 Kết luận chương 4 .113 DANH MỤC CÁC CÔNG TRÌNH .116 CÔNG BỐ ĐƢỢC SỬ DỤNG TRONG LUẬN ÁN .116 TÀI LIỆU THAM KHẢO .117 iv Tóm tắt Bài toán cực tiểu hóa độ trễ (Minimum latency problem - MLP) dưới dạng tổng quát có thể phát biểu trong ngôn ngữ của lý thuyết đồ thị như sau: Cho G = (V, E) là đồ thị vô hướng có trọng số không âm trên mỗi cạnh e  E. Giả sử, T là một hành trình xuất phát từ đỉnh s, chúng ta định nghĩa độ trễ của một đỉnh v bất kỳ thuộc T là độ dài của đường đi từ đỉnh xuất phát s đến v trên T. Độ trễ của hành trình T được định nghĩa như là tổng độ trễ của tất cả các đỉnh thuộc hành trình T. Bài toán cực tiểu hóa độ trễ MLP yêu cầu tìm một hành trình T bắt đầu từ đỉnh xuất phát s đi qua tất cả các đỉnh còn lại của đồ thị với tổng độ trễ là nhỏ nhất.

Bài toán MLP có nhiều ứng dụng trong thực tiễn. Cụ thể, trong lý thuyết lập lịch khi một máy chủ hay một người thợ phải lên kế hoạch phục vụ một tập các yêu cầu sao cho tổng (trung bình) thời gian chờ đợi của các yêu cầu là cực tiểu. Trong tìm đường đi trên mạng, bài toán cũng được ứng dụng để tìm hành trình với tổng độ trễ là nhỏ nhất. Trong bài toán tìm kiếm thông tin, bài toán MLP được ứng dụng để cực tiểu hóa độ trễ của việc tìm kiếm thông tin trên mạng.

Mục đích nghiên cứu của chúng tôi trong luận án này là đề xuất các thuật toán giải bài toán MLP với chất lượng lời giải tốt hơn chất lượng lời giải của các thuật toán giải bài toán MLP đã được công bố. Đối với một bài toán NP-khó như bài toán MLP, hiện tại có ba hướng tiếp cận chính để phát triển thuật toán giải: 1) hướng tiếp cận đúng, 2) hướng tiếp cận gần đúng cận tỷ lệ, 3) hướng tiếp cận meta-heuristic. Đóng góp của chúng tôi trong luận án là đề xuất các thuật toán giải theo cả ba hướng tiếp cận:  Phát triển thuật toán đúng đưa ra lời giải tối ưu cho bài toán MLP với kích thước bài toán lên đến 40 đỉnh.  Khảo sát thực nghiệm về hiệu quả của các thuật toán gần đúng cận tỷ lệ hiện biết, là cơ sở để đề xuất thuật toán gần đúng mới có cận tỷ lệ tốt hơn.

 Phát triển ba thuật toán theo hướng tiếp cận meta-heuristic. Chúng tôi đề xuất thuật toán dựa trên lược đồ của thuật toán di truyền để giải bài toán MLP và một số kỹ thuật mới được tích hợp vào từng bước của thuật toán. Nhằm nâng cao chất lượng lời giải và thời gian chạy thuật toán, chúng tôi đề xuất hai thuật toán meta- heuristic lai là: Thuật toán (ACO-GA) lai ghép giữa thuật toán di truyền (GA) và thuật toán đàn kiến (ACO); và thuật toán TS-VNS lai ghép giữa thuật toán Tabu (TS) và thuật toán lân cận biến đổi (VNS). v Để đánh giá hiệu quả của các thuật toán đề xuất, chúng tôi tiến hành thực nghiệm trên các bộ dữ liệu chuẩn và so sánh kết quả thu được với kết quả của các công trình nghiên cứu liên quan.

Kết quả thực nghiệm chỉ ra các thuật toán đề xuất đưa ra lời giải tốt hơn các thuật toán tốt nhất hiện biết trên nhiều bộ dữ liệu. vi Danh mục thuật ngữ STT Từ viết tắt Giải nghĩa tiếng Anh Giải nghĩa tiếng Việt 1 ACO Ant conoly optimization Tối ưu hoá đàn kiến Thuật toán di truyền lai ghép thuật 2 ACO-GA - toán đàn kiến 3 GA Genetic algorithm Thuật toán di truyền 4 TS Tabu search Tìm kiếm Tabu 5 VNS Variable neighborhood search Tìm kiếm lân cận biến đổi Thuật toán tabu lai ghép thuật toán 6 TS-VNS - đa lân cận 7 MLP Minimum latency problem Bài toán cực tiểu hóa độ trễ 8 TSP Traveling salesman problem Bài toán người du lịch 9 TRP Traveling repairman problem Bài toán thợ sửa chữa lưu động 10 DMP Delivery man problem Bài toán người giao hàng Time dependent traveling Bài toán người du lịch với thời gian 11 TDTSP Salesman pproblem bị chặn 12 DP Dynamic programming Quy hoạch động 13 B&B Branch and bound Phương pháp nhánh cận 14 CP Constraint programming Quy hoạch ràng buộc 15 - Approximation algoirthm Thuật toán gần đúng 16 - Simulated annealing algorithm Thuật toán phỏng tôi luyện 17 - Local search Tìm kiếm địa phương Greedy randomized adaptive Thủ tục tìm kiếm tham lam ngẫu 18 GRASP search procedure nhiên tự thích nghi 19 ILS Iterated local search Tìm kiếm địa phương leo đồi Random variable neighborhood 20 RVND Tụt lân cận biến đổi ngẫu nhiên descend Bài toán cây khung nhỏ nhất đi qua 21 k-MST k-minimum spanning tree k đỉnh Bài toán hành trình ngắn nhất đi qua 22 k-troll Minimum k-troll problem k đỉnh 23 PCST Prize collecting steiner tree Bài toán cây Steiner Polynomial time algorithm 24 - Thuật toán thời gian tính đa thức (Polynomial algorithm) 25 Benchmark test Bộ dữ liệu chuẩn 26 OPT Best known solution Lời giải tốt nhất hiện biết 27 SDT Social disaster technique Kỹ thuật hủy diệt vii Danh mục bảng Bảng 1. 1 Mô tả các bộ dữ liệu. 1 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 1 (tính theo phút).

2 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 2 (tính theo phút). 3 Thời gian chạy của thuật toán trong bộ dữ liệu thực 2 (tính theo phút). 4 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 3 (TPR-10-Rx) (tính theo giây). 5 Thời gian chạy của thuật toán trong bộ dữ liệu ngẫu nhiên 3 (TPR-20-Rx) (tính theo giây).

6 Thời gian chạy của thuật toán cho các file dữ liệu nhỏ trong. 1 Kết quả thực nghiệm các thuật toán trong các bộ dữ liệu nhỏ. 2 Kết quả thực nghiệm các thuật toán trên bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx). 3 Kết quả thực nghiệm các thuật toán trên bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx).

4 Kết quả thực nghiệm các thuật toán trên bộ dữ liệu thực 1. 5 Kết quả thực nghiệm cho các bộ dữ liệu nhỏ. 6 Kết quả thực nghiệm với bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx). 7 Mô tả gap1 , gap 2 đối với các bộ dữ liệu nhỏ.

8 Mô tả T đối với các bộ dữ liệu nhỏ. 9 Kết quả thực nghiệm với bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx). 10 Kết quả thực nghiệm với bộ dữ liệu thực 1 .11 Mô tả gap1 , gap 2 đối với các bộ dữ liệu lớn. 12 Mô tả T đối với các bộ dữ liệu lớn.

1 Thực nghiệm lựa chọn kích thước quần thể. 2 Thực nghiệm lựa chọn tham số xác xuất lai ghép và đột biến. 3 Thực nghiệm lựa chọn kích thước nhóm. 4 Thực nghiệm lựa chọn tỷ lệ  1.

5 Thực nghiệm xác định giá trị NGD. 6 Thực nghiệm xác định giá trị NGT. 7 Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu nhỏ. 8 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-50-Rx).

9 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-100-Rx). 10 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu ngẫu nhiên 3 (TPR-200-Rx). 11 Kết quả thực nghiệm các thuật toán cho bộ dữ liệu thực 1.