Thuật toán phỏng bầy kiến giải bài toán K - Median

- Tổng quan về cỏc hệ thống tớnh toỏn phỏng sinh học__ 9 1.1 Giới thiệu.
- 12 1.3.2 Cỏc đặc tả di truyền.
- 12 1.3.3 Cỏc hàm phự hợp.
- 13 1.4 Phõn loại cỏc thuật toỏn phỏng sinh học.
- 13 1.4.1 Cỏc ứng dụng trong quy hoạch.
- 14 1.4.2 Cỏc ứng dụng trong thiết kế.
- 16 1.4.3 Cỏc ứng dụng trong mụ phỏng và nhận dạng.
- 17 1.4.4 Cỏc ứng dụng trong điều khiển.
- 17 1.5 Nguyờn lý cơ bản của cỏc thuật toỏn phỏng sinh học.
- Thuật toỏn phỏng bầy kiến.
- 21 2.2 Mụ hỡnh mụ phỏng của thuật toỏn.
- 25 2.3.2 Trỡnh bày thuật toỏn.
- 26 2.4 Một số ứng dụng.
- 29 2.4.1 Giải thuật ACO cho bài toỏn TSP.
- 29 2.4.2 Bài toỏn SMTWTP.
- 31 2.4.3 Bài toỏn GAP.
- 32 2.4.4 Bài toỏn SCP.
- 34 42.4.5 Bài toỏn định tuyến mạng.
- Bài toỏn k-median.
- 44 3.1 Phỏt biểu bài toỏn.
- 44 3.2 Cỏc ứng dụng thực tế.
- 46 3.3.1 Thuật toỏn vột cạn.
- 48 3.3.2 Thuật toỏn Local Search.
- 49 3.3.3 Thuật toỏn Tabu Search.
- 50 3.3.4 Thuật toỏn GRASP.
- Giải thuật phỏng bầy kiến giải bài toỏn k-median.
- 53 4.1 Một số định nghĩa.
- 54 4.3 Lưu đồ thuật toỏn.
- 57 4.3.5 Nguyờn tắc chung của thuật toỏn.
- 58 4.3.6 Điều kiện dừng của thuật toỏn.
- 64 5.2.2 Cỏc kết quả tớnh toỏn.
- 75 5.3.1 Đỏnh giỏ về chất lượng thuật toỏn.
- 81 6CÁC THUẬT NGỮ VIẾT TẮT EC Evolutionary Computation Cỏc tớnh toỏn phỏng sinh học EA Evolutionary Algorithm Cỏc thuật toỏn phỏng sinh học ACO Ant Colony Optimize Bài toỏn tối ưu phỏng bầy kiến AS Ant System Hệ thống phỏng bầy kiến GA Genetic Algorithms Thuật toỏn di truyền TSP Traveling Salesman Problem Bài toỏn người bỏn hàng di động QAP Quadratic Assignment Problem Bài toỏn phương trỡnh bậc hai JSP Job-shop Scheduling Problem Bài toỏn lập lịch bỏn hàng GBAS Graph-Based Ant System Hệ thống Ant dựa trờn đồ thị SMTWTP Single Machine Total Weighted Tardiness Scheduling Problem Bài toỏn lập lịch sản xuất trờn một mỏy đơn.
- GAP Generalized Assignment Problem Bài toỏn lập lịch tổng quỏt SCP Set Covering Problem Bài toỏn phủ đỉnh 7LỜI NểI ĐẦU Cỏc hệ thống cụng nghệ thụng tin ngày nay càng phỏt triển, lối tư duy, cơ chế tớnh toỏn, suy diễn ngày càng tiến gần hơn với kiểu tư duy logic của con người.
- Cựng với nú, cỏc hệ thống tớnh toỏn mụ phỏng theo cỏc cơ chế hoạt động sinh học của cỏc thực thể trong cuộc sống cũng ngày càng được nghiờn cứu sõu hơn, chi tiết hơn.
- Cỏc bài toỏn trong thực tế cũng được cỏc nhà nghiờn cứu nắm bắt và giải quyết dễ dàng hơn thụng qua cỏc mối liờn hệ tồn tại và khụng ngừng phỏt triển của cỏc thực thể sinh học.
- Cỏc hệ thống tớnh toỏn như vậy được nghiờn cứu dưới tờn gọi cỏc hệ thống tớnh toỏn phỏng sinh học.
- Một trong cỏc hệ thống tớnh toỏn phỏng sinh học đó vận dụng rất tốt lối tư duy này vào cỏc bài toỏn tối ưu tổ hợp, đú chớnh là mụ hỡnh giải thuật phỏng bầy kiến, mụ phỏng lối di chuyển trong đời sống thực tế bầy đàn của cỏc con kiến.
- Đặc biệt, trong một số loại hỡnh dịch vụ mang tớnh khẩn cấp, cỏc yờu cầu cần phục vụ với thời gian nhanh nhất, thỡ vấn đề cài đặt cỏc trạm dịch vụ một cỏch hợp lý sao cho khả năng đỏp ứng là tốt nhất cú thể được lại trở nờn hết sức quan trọng.
- Bài toỏn k-median, một bài toỏn điển hỡnh đỏp ứng cỏc kiểu mụ hỡnh trờn đó được triển khai với nhiều nghiờn cứu chuyờn sõu.
- 8Với mục tiờu đi sõu nghiờn cứu về hệ thống giải thuật phỏng bầy kiến, cũng như ứng dụng nú để giải một lớp bài toỏn tối ưu tổ hợp đú là bài toỏn k-median, luận văn này sẽ cố gắng tỡm hiểu mụ hỡnh cơ bản nhất của hệ thống giải thuật phỏng bầy kiến, bài toỏn k-median và ứng dụng giải thuật phỏng bầy kiến để giải bài toỏn này.
- Chương 1 Giới thiệu tổng quan về cỏc hệ thống phỏng sinh học, cỏc phương phỏp tớnh toỏn phỏng sinh học, cũng như nguyờn lý cơ bản của một hệ thống thuật toỏn phỏng sinh học.
- Chương 2 Giới thiệu tổng quan về thuật toỏn phỏng bầy kiến.
- Chương 3 Giới thiệu tổng quan về bài toỏn k-median cũng như một số phương phỏp giải đó được ỏp dụng đối với bài toỏn này.
- Chương 4 Trỡnh bày giải thuật phỏng bầy kiến giải bài toỏn k-median.
- Thuật toỏn phỏng bầy kiến cũng như bài toỏn k-median thực tế đó được nghiờn cứu nhiều.
- Tuy nhiờn việc ỏp dụng thuật toỏn phỏng bầy kiến vào giải bài toỏn k-median cũn chưa được nghiờn cứu sõu sắc.
- TỔNG QUAN VỀ CÁC HỆ THỐNG TÍNH TOÁN PHỎNG SINH HỌC 1.1 Giới thiệu Cỏc kỹ thuật tớnh toỏn phỏng sinh học (EC) [10] được nghiờn cứu cho thấy chỳng hoàn toàn phự hợp với cỏc phương phỏp tớnh, giải cỏc bài toỏn tổ hợp.
- Nguyờn lý chung của cỏc kỹ thuật này đều dựa trờn cỏc hiện tượng sinh học tự nhiờn.
- Cỏc tớnh toỏn này bao gồm lớp cỏc thuật toỏn phỏng sinh học (EA), trong đú chứa cỏc giải thuật tỡm kiếm dựa trờn cỏc tri thức kinh nghiệm.
- Cỏc tri thức này cú thể được sử dụng để tỡm kiếm cỏc lời giải tốt cho cỏc bài toỏn khú (chứ khụng phải cỏc lời giải tối ưu).
- Cỏc tớnh toỏn đú luụn tỡm cỏch để suy diễn ra cỏc lời giải tốt hơn từ cỏc lời giải trước đú và đặc biệt phự hợp với cỏc dạng bài toỏn khụng tồn tại cỏc giải thuật hiệu quả (là giải thuật cú thời gian tớnh toỏn đa thức).
- Cỏc giải thuật này thường là đơn giản, mang tớnh tổng quỏt và cú thể được ứng dụng trong lớp cỏc bài toỏn tỡm kiếm và tối ưu.
- Tất nhiờn, để cú một sự đỏnh giỏ đỳng về việc tại sao và làm thế nào cỏc thuật toỏn cú thể làm việc, cần cú cỏc hiểu biết cơ bản về di truyền và sự tiến hoỏ.
- Hơn nữa, cỏc đột biến ngẫu nhiờn này cú thể biểu hiện hoàn toàn ở một số tớnh trạng nhất định.
- chỳng cú thể bị chết bởi thỳ ăn thịt, chỳng phải tranh thức ăn với cỏc chuột khỏc, hoặc chỳng cú thể phải chống chọi với cỏc mối đe dọa từ tự nhiờn hoặc bất ngờ khỏc trước khi chỳng cú thể sinh sản.
- Đặc biệt, những con chuộc cú kiểu hỡnh tốt, như cú thể chạy nhanh hoặc cú màu lụng cho phộp chỳng lẩn trốn được trong cỏc bụi để trỏnh được thỳ ăn thịt, mới sống sút và sinh sản.
- Một cỏch nhỡn đặc biệt về tiến húa đó trở nờn phổ biến là tiến húa chớnh là cỏch phõn tớch bài toỏn.
- Bài toỏn ở đõy chớnh là sự tồn tại và sinh sản, và sự tiến húa qua chọn lọc tự nhiờn chớnh là một kỹ thuật phõn tớch bài toỏn.
- Núi cỏch khỏc, tiến hoỏ sẽ tỡm kiếm trong khụng gian cỏc phần tử DNA (kiểu gen) để mó hoỏ cỏc thành cỏc kiểu hỡnh cú thể đảm bảo tồn tại và phỏt triển.
- Theo cỏch này, qua nhiều thế hệ kế 12tiếp, cỏc cỏ thể trong quần thể sẽ trở nờn ngày càng thành cụng trong việc “phõn tớch bài toỏn”.
- 1.3 Cỏc khụng gian tỡm kiếm, đặc tả và cỏc hàm phự hợp Để cú thể sử dụng cỏc nguyờn lý tiến hoỏ sinh học trong việc xõy dựng cỏc thuật toỏn tỡm kiếm, đầu tiờn ta cần tỡm hiểu cỏc khỏi niệm khụng gian tỡm kiếm, cỏc đặc tả di truyền và cỏc hàm phự hợp.
- Khụng gian tỡm kiếm Khụng gian tỡm kiếm của một bài toỏn đơn giản chớnh là khụng gian của tất cảc cỏc lời giải cú thể cú để giải bài toỏn.
- Chẳng hạn với bài toỏn tớnh tổng: Đưa ra một tập gồm n số xi, thỡ cú tồn tại hay khụng một tập con S cỏc số này mà tổng của chỳng khụng vượt quỏ một số m cho trước? Khi đú tập cỏc lời giải cho bài toỏn này (khụng gian tỡm kiếm) là tập tất cả cỏc tập con cú thể của n số, là 2n.
- Một vớ dụ khỏc là bài toỏn người bỏn hàng di động (TSP).
- Ở đõy khụng gian tỡm kiếm chớnh là tập tất cả cỏc hành trỡnh cú thể qua n thành phố này, chớnh là n!.
- Cỏc đặc tả di truyền Đụi khi cỏc đặc tả này là cỏc cỏch mụ tả cỏc lời giải cho một vài bài toỏn theo nguyờn tắc đơn giản, thuận tiện để tớnh toỏn, chẳng hạn thụng qua cỏc xõu ký tự.
- Vớ dụ trong bài toỏn tớnh tổng con trờn, mỗi lời giải cú thể được mụ tả bởi một chuỗi bit cú độ dài n.
- Tương tự trong bài toỏn TSP, mỗi bộ lời giải cú thể được mụ tả bởi một hoỏn vị của n số tự nhiờn từ 1 đến n.
- Cỏc cỏch mụ tả cỏc lời giải này làm cho bài toỏn tương tự như mụ tả kiểu gen/kiểu hỡnh trong cỏc hiện tượng sinh học tự nhiờn.
- Cỏc mụ tả (cỏc chuỗi bit, cỏc hoỏn vị) là cỏc kiểu gen và cỏc lời giải tương ứng là cỏc kiểu hỡnh.
- Khi đú khụng gian tỡm kiếm cú thể được mụ tả như là khụng gian của cỏc chuỗi bit hay là khụng gian của cỏc hoỏn vị.
- Cỏc hàm phự hợp Để ỏp dụng một thuật toỏn phỏng sinh học vào một bài toỏn, ta cần cú một vài cỏch đỏnh giỏ cỏc lời giải.
- Điều này cú thể được thực hiện thụng qua cỏc hàm phự hợp.
- Một hàm phự hợp là một hàm mà đầu vào là cỏc mụ tả (hay cỏc kiểu gen), dịch cỏc mụ tả này ra cỏc lời giải tương ứng (hay cỏc kiểu hỡnh), kiểm tra cỏc lời giải này trờn bài toỏn đặt ra, sau đú trả về một giỏ trị đỏnh giỏ mức độ tốt của lời giải.
- Chẳng hạn trong bài toỏn TSP, đầu vào là một hoỏn vị, được tớnh thành hành trỡnh tương ứng qua cỏc thành phố, và độ dài của hành trỡnh này sẽ được tớnh ra.
- Xem xột với một bài toỏn tỡm cực đại, sự phự hợp nờn là cực đại, hàm phự hợp khi đú được cấu trỳc sao cho giỏ trị phự hợp càng cao thỡ lời giải sẽ càng tốt.
- 1.4 Phõn loại cỏc thuật toỏn phỏng sinh học Cỏc ứng dụng của cỏc hệ thống tớnh toỏn phỏng sinh học hết sức rộng rói [12].
- Tuy nhiờn, về cơ bản cú thể phõn loại cỏc thuật toỏn phỏng sinh học dựa theo cỏc ứng dụng 14trong thực tế của cỏc thuật toỏn đú.
- Để thuận tiện, cú thể phõn chia thành cỏc dạng ứng dụng tiờu biểu như sau.
- Cỏc ứng dụng quy hoạch • Cỏc ứng dụng thiết kế • Cỏc ứng dụng mụ phỏng và nhận dạng • Cỏc ứng dụng điều khiển Việc phõn loại này chỉ mang tớnh chất tương đối.
- Cú thể cú một vài bài toỏn cụ thể nào đú đỳng trong đồng thời nhiều dạng ứng dụng.
- 1.4.1 Cỏc ứng dụng trong quy hoạch 1.4.1.1 Bài toỏn định tuyến Một trong cỏc bài toỏn nổi tiếng trong hệ thống cỏc bài toỏn tối ưu tổ hợp dạng này chớnh là bài toỏn người bỏn hàng di động (TSP.
- Một bài toỏn khỏc dạng này là bài toỏn vận chuyển (Transportation Problem).
- Trong bài toỏn này, hàng hoỏ cần được lấy từ một số kho hàng và phõn phối cho một số khỏch hàng.
- Vậy đõu sẽ là giải phỏp đảm bảo tối ưu chi phớ? Bài toỏn dẫn đường cho cỏc rụbốt cũng là một dạng trong nhúm bài toỏn này.
- 1.4.1.2 Bài toỏn lập lịch Cỏc vấn đề lập lịch chủ yếu tập trung phõn tớch cỏc kế hoạch đặt ra để thực hiện một số yờu cầu trong một khoảng thời gian nào đú, trong đú cỏc yờu cầu là cú giới hạn, cỏc ràng buộc thay đổi và sẽ cú một số đối tượng được tối ưu.
- Bài toỏn lập lịch cụng việc bỏn hàng là một dạng bài toỏn NP đầy đủ.
- Làm sao để lịch đưa ra cú thể thực hiện tất cả cỏc nhiệm vụ với chi phớ tối ưu? Một dạng bài toỏn lập lịch khỏc là đặt ra một thời gian cú thể cho một tập cỏc bài kiểm tra, cỏc bài giảng, hoặc một thể loại tương tự.
- Trong tớnh toỏn, cỏc bài toỏn lập lịch cũn bao gồm cả bài toỏn phõn phối cỏc cụng việc một cỏch cú hiệu quả cho từng bộ xử lý trong một hệ thống rất nhiều bộ xử lý.
- 1.4.1.3 Bài toỏn đúng gúi Cỏc thuật toỏn phỏng sinh học được ứng dụng trong rất nhiều cỏc bài toỏn đúng gúi, mà đơn giản nhất là bài toỏn balụ rỗng một chiều (Zero-One Knapsack Problem).
- Tỡm tập cỏc đồ vật với giỏ trị lớn nhất cú thể chứa được trong balụ đú.
- Cú nhiều bài toỏn thực tế cú cựng kiểu này, chẳng hạn bài toỏn cấp phỏt cỏc kờnh truyền thụng cho khỏch hàng với chi phớ cho cỏc kờnh là khỏc nhau.
- Cú rất nhiều dạng bài toỏn đúng gúi hai chiều.
- Một bài toỏn tương tự trong lĩnh vực thiết kế mạch điện tử tớch hợp, đú là làm thế nào cỏc mạch điện được sắp xếp để tối thiểu hoỏ tổng số lượng linh kiện và đường mạch dẫn được sử dụng.
- 1.4.2 Cỏc ứng dụng trong thiết kế Việc thiết kế cỏc hệ thống lọc trong điện tử nhận được nhiều sự quan tõm.
- Cỏc thuật toỏn phỏng sinh học thường được sử dụng để thiết kế cỏc hệ thống điện tử hoặc hệ thống số, được thực hiện tại tần số trả lời mong muốn.
- Cỏc thuật toỏn phỏng sinh học cũng đồng thời được sử dụng trong vấn đề tối ưu cỏc thiết kế của cỏc hệ thống xử lý tớn hiệu và trong thiết kế mạch tớch hợp.
- Cỏc kỹ thuật tớnh toỏn phỏng sinh học được sử dụng rộng rói trong cỏc mạng Nơron nhõn tạo, cả trong thiết kế giao thức mạng cũng như trong tỡm kiếm cỏc tập trọng số tối ưu.
- Cú rất nhiều cỏc ứng dụng kỹ thuật trong tớnh toỏn phỏng sinh học: thiết kế cấu trỳc, thay thế cỏc suy hao trong cỏc khụng gian cấu trỳc, thiết kế mỏy gia tốc tuyến tớnh, thiết kế hộp số, thiết kế lũ phản ứng hoỏ học

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt