Thiết kế topo logic cho mạng quang wdm

ng tri thức cục bộ- chỉ biết đến bít đang bị đột biến. Giả sử nếu bít đó nằm ở phần bên trái của chuỗi mã hóa đột biến, thì tác động đột biến trên biến đó rất có ý nghĩa. Ngược lại, những bít ở tít đầu bên phải của chuỗi lại có tác động hoàn toàn nhỏ khi đột biến. Do đó ta cần có một kiểu đột biến thích hợp khi quần thể già đi tùy theo từng bài toán cụ thể. Đột biến cấu trúc cũng là một giải pháp trong nhiều kiểu đột biến để tăng khả năng tìm kiếm cho thuật giải di truyền khi mà số thế hệ càng tăng và quần thể trở nên già đi đối với các bài toán tối ưu có ràng buộc. Đột biến cấu trúc được định nghĩa là hoán vị của hai số trong chuỗi số của nhiễm sắc thể cha me. Ví dụ một nhiễm sắc thể cha có chuỗi số như sau: A = 112133212233 Có thể tạo ra cá thể con sau đây.( các số ở vị trí 4 và 6 được hoán vị ) A’ = 112331212233 Cách áp dụng một bài toán vào thuật giải GA. Để có thể áp dụng thuật giải GA để giải một bài toán tối ưu cần thực hiện những bước cơ bản sau [1]. Các bước chuẩn bị: Trước tiên cần xác định không gian giải pháp, sau đó thực hiện việc mã hóa cho các giải pháp bằng cách gán cho mỗi giải pháp một tập hợp các ký hiệu tượng trưng cho nhiễm sắc thể có thể có dạng chuỗi, dạng cây hay dạng ma trận…Các phần tử trong chuỗi có thể là số nhị phân, số thập phân… Tiếp theo cần xây dựng hàm thích nghi để đánh giá độ thích nghi cho từng giải pháp dựa trên hàm mục tiêu. Hàm thích nghi nhận giá trị không âm, và các giải pháp càng gần tối ưu thì giá trị độ thích nghi càng lớn. Chọn các hình thức chọn lọc, lai tạo và đột biến phù hợp với cách mã hóa của các giải pháp. Chọn điều kiện dừng phù hợp với yêu cầu đặt ra cho bài toán. Các bước thực hiện: Đầu tiên khởi tạo quần thể ban đầu: Quần thể ban đầu có thể khởi tạo một cách ngẫu nhiên hoặc dựa trên một số thông tin biết trước. Tính độ thích nghi cho từng giải pháp trong quần thể bằng hàm thích nghi vừa xây dựng. Chọn phương pháp chọn lọc để chọn các cá thể tạo quần thể kế tiếp dựa vào độ thích nghi của các giải pháp. Áp dụng các phép toán lai tạo, đột biến, sao chép. Thực hiện chính sách thay thế và tạo lập thế hệ mới. Kiểm tra điều kiện dừng, nếu chưa thỏa mãn điều kiện dừng thì lặp lại các bước chọn lọc, lai tạo, đột biến và thay thế để tạo lập thế hệ tiếp theo. Nếu thỏa mãn điều kiện dừng thì đưa ra giải pháp tốt nhất trong quần thể hiện hành. Lưu đồ của thuật toán GA. Khởi tạo quần thể ban đầu G = 0 Đánh giá độ thích nghi của mỗi cá thể Đưa ra kết quả tốt nhất Áp dụng chính sách thay thế và tạo lập thế hệ mới G = G +1 Áp dụng các phép toán lai tạo,đột biến và sao chép Chọn lọc các cá thể để tái tạo Kiểm tra điều kiện dừng Hình 3.13- Lưu đồ thuật toán của GA. * Chú ý : Đối với các bài toán tối ưu có ràng buộc thì ngoài việc áp dụng các bước trên để giải một bài toán theo phương pháp dùng thuật toán GA thì ta cần có các phương pháp để xử lý các điều kiện ràng buộc tùy vào từng điều kiện ràng buộc của bài toán cụ thể mà ta tìm phương pháp xử lý ràng buộc một cách thích hợp cho bài toán. Ưu nhược điểm và những ứng dụng của GA. Ưu điểm của GA. GA thuộc lớp các thuật giải xác suất, nhưng lại rất khác những thuật giải 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 (ta gọi là một quần thể )- Hầu như các phương pháp khác chỉ xử lý một điểm trong không gian tìm kiếm chính vì thế mà GA được đánh giá là mạnh hơn rất nhiều so với các phương pháp tìm kiếm đó. Nhược điểm của GA. Có lẽ nhược điểm của GA là thời gian tìm kiếm và tính toán của nó khi mà số cá thể trong quần thể tăng lên hoặc phải trải qua nhiều thế hệ tìm kiếm, có thể là chậm hơn so với các phương pháp khác nhưng ngày nay với nền công nghiệp máy tính phát triển như vũ bão thì đó không còn là vấn đề lớn nữa Những ứng dụng của GA. Từ khi thuật giải di truyền ra đời đã góp phần giải quyết những vấn đề khó khăn, các bài toán phức tạp và ngày nay thuật giải di truyền vẫn được áp dụng rộng rãi ở nhiều lĩnh vực khác nhau để tìm ra giải pháp tối ưu và thuật giải di truyền được đánh giá là giải quyết vấn đề rất có hiệu quả. Ứng dụng trong ngànhh khai thác dầu khí: Năm 1985, David E. Goldberg đã thành công trong việc dùng GA và với máy Apple II ông đã thực hiện được chương trình tin học sử dụng ngôn ngữ Pascal để điều chỉnh mạng lưới phân phối dầu khí một cách tốt đẹp. Từ đó GA đã thực sự góp vào việc giải quyết những vấn đề phức tạp. Ứng dụng trong lĩnh vực thiết kế: Genetic Elictronic Co. (GE) đã dùng GA trong việc yểm trợ chương trình tin học vẽ kỹ nghệ để tối ưu hóa việc thiết kế các bộ phận cho máy bay, tua bin nhà máy nhiệt điện và nhiều phụ tùng khác. Động cơ cho máy bay mới nhất của Boeing đã được GE thiết kế với chương trình tin học về GA. Ứng dụng trong ngànhh khai thác hầm mỏ: Chuck Karr đã vận dụng những hiểu biết về lý thuyết GA thành những ứng dụng thực tế để chế tạo dụng cụ đo lường cho kỹ nghệ khai thác khoáng sản. Nhiều ứng dụng khác đang được sử dụng trong các lĩnh vực như: Tìm lộ trình tối ưu cho người chào hàng (Travelling Saleman) Tìm địa điểm để khoan dầu tại đại dương. Trên một vùng hàng chục ngàn cây số vuông, việc lựa chọn những điểm khoan dầu khí thích hợp không những giảm chi phí mà còn rút ngắn thời gian dò tìm. Thiết kế máy biến thế cho các nhà máy điện…. Ứng dụng trong lĩnh vực giao thông: Hoạch định lộ trình xe chở hàng từ các kho đến các công trường sao cho nhanh và ngắn nhất… Ứng dụng trong sản xuất: Nhiều ứng dụng của GA tại các trung tâm sản xuất nhằm tăng cường khả năng sản xuất và chuyển giao thành phẩm, tránh việc di chuyển hàng hóa nhiều lần, tồn trữ quá lâu trong kho giữ các phương tiện chuyển vận trong trình trạng chờ đợi. CHƯƠNG IV: ÁP DỤNG GENETIC ALGORITHM ĐỂ GIẢI BÀI TOÁN LTD (LOGICAL TOPOLOGY DESIGN) Mô tả bài toán LTD. Như trong các tài liệu [5],[7],thì bài toán thiết kế topologic được mô tả dưới dạng công thức là bài toán tối ưu loại MILP. Và người ta đã khẳng định bài toán thiết kế mạng là bài toán phức tạp, đặc biệt khi mà số node trong mạng tăng lên. Và để giảm độ phức tạp của bài toán thông thường người ta tìm cách chia nhỏ bài toán lớn thành các bài toán con để lần lược giải quyết từng vấn đề. Trong khuôn khổ luận văn này Bài toán LTD được nêu ra với các giả định sau: Các giả định chung: Với các giả định đường nối vật lý là song hướng, nghĩa là nếu có một kết nối từ một node i đến node j thì sẽ có kết nối theo chiều ngược lại từ node j đến node i. Các đường nối logic ( tức là các đường quang) là đơn hướng. Điều này có nghĩa nếu có một kết nối từ một node i đến một node j thì chưa chắc có kết nối theo hướng ngược lại từ node j đến node i. Ma trận traffic đưa vào là không đối xứng, có nghĩa lượng traffic từ node i sang node j có thể khác lượng traffic từ node j sang node i. Traffic đưa vào được thể hiện dưới dạng ma trận và đó là ma trận không đối xứng. Xem như các thiết bị chuyển mạch quang đặt ở các node có chức năng chuyển đổi bước sóng có nghĩa là nới lỏng điều kiện ràng buộc về bước sóng liên tục trong các đường quang. Các thiết bị thu phát tại mỗi node được giả định số thiết bị thu bằng số lượng thiết bị phát. Các thông số và mục tiêu của bài toán LTD. Các thông số đầu vào của bài toán LTD. Topo vật lý: Topo của mạng cáp quang cụ thể. Traffic yêu cầu: đó là nhu cầu kết nối giữa các node trong mạng thể hiện bằng ma trận traffic. Các thông số đầu ra của bài toán LTD. Topo logic : Topo của các đường quang tương ứng trên mạng vật lý. Kết quả định tuyến traffic và phân định bước sóng Kết quả định tuyến cho từng đường quang trên topo vật lý. Mục tiêu của bài toán LTD. Thông thường bài toán thiết kế mạng tối ưu thường được xây dựng theo một trong những mục tiêu sau: Tối thiểu độ nghẽn trong mạng. Tối thiểu độ trễ trong mạng. Tối thiểu theo số hop trung bình trong mạng. Và trong luận văn tốt nghiệp này giải bài toán thiết kế topo logic hướng tới mục tiêu tối thiểu theo số hop trung bình như ở (2.1) và được viết lại như ở trong (4.1). (4.1) Ở đó hsd được xem là số hops (hay số chặn) trên đường quang truyền từ node s đến node d và ttot=là tổng traffic trong mạng, tsd là traffic lưu thông từ node s đến node d Như đã giới thiệu thì mục tiêu tối thiểu số hop trung bình có quan hệ rất lớn với mục tiêu tối thiểu độ nghẽn trong mạng, cũng như trong [1] đã giới thiệu thì giảm số hop trung bình cũng đồng nghĩa với việc tăng độ thông của mạng (network throughput). Phân tích bài toán thiết kế topo logic. Như đã giới thiệu bài toán thiết kế mạng là bài toán phức tạp đặc biệt khi mà số lượng node trong mạng tăng lên. Do đó để có thể làm giảm độ phức tạp của một bài toán thiết kế mạng lớn người ta thực hiện ý tưởng chia nhỏ bài toán lớn thành các bài toán con nhỏ và thay vì giải bài toán lớn phức tạp người ta sẽ lần lượt đi giải quyết các bài toán con. Lời giải của bài toán con phía trước sẽ là dữ liệu đầu vào cho các bài toán con phía sau. Vì các bài toán con không hoàn toàn độc lập với nhau nên phương pháp tìm lời giải lần lượt qua các bài toán con này chỉ có thể đưa ra kết quả gần đúng. Tuy nhiên với phương pháp phân tích này thì sẽ giúp ta có cái nhìn trực tiếp vào từng vấn đề cụ thể. Với các giả định ở trên thì bài toán thiết kế mạng ở trên có thể chia thành ba bài toán con nhỏ mà không quan tâm đến bài toán phân định bước sóng đó là: Bài toán thiết kế topo logic đơn thuần. là bài toán xác định sự tồn tại của các đường quang thông qua các cặp nguồn đích của mỗi đường quang. Bài toán định tuyến cho traffic là bài toán định tuyến cho các luồng traffic trên topo logic, nói cách khác đó là việc xác định đường truyền logic cho từng luồng traffic. Bài toán định tuyến cho đường quang: là bài toán định tuyến cho các đường quang trên mạng vật lý. Nói cách khác là xác định đường truyền vật lý cho từng đường quang. Và trong khuôn khổ luận văn tốt nghiệp với khả năng tìm hiểu và thời gian hạn hẹp cho phép nên ở đây, chỉ có thể áp dụng Genetic algorithms để giải quyết bài toán thiết kế topo logic đơn thuần. tức giải quyết xác định sự tồn tại của các đường quang thông qua các cặp nguồn đích của mỗi đường quang. Mô tả bài toán LTD đơn thuần. Khi chỉ xét đến bài toán thiết kế topo logic đơn thuần thì bài toán có thể được mô tả như sau: Dữ liệu đầu vào : Đối với bài toán thiết kế topo logic đơn thuần thì dữ liệu đầu vào cho bài toán bao gồm : Mạng vật lý cụ thể hay còn gọi là mạng cáp quang. Trong đó các thông tin về số lượng và vị trí các node được trích ra để làm dữ liệu vào cho bài toán thiết kế topo logic đơn thuần. Traffic trao đổi theo yêu cầu giữa các node: Với điều kiện thực tế hiện nay thì các mạng cáp quang WDM giữ nhiệm vụ cung cấp đường nối cho các mạng SDH nên traffic yêu cầu được thể hiện bằng số lượng luồng STM-1 cần nối giữa các cặp nguồn đích và trong khuôn khổ luận văn này bài toán thiết kế topo logic chỉ có thể giải quyết trao đổi dung lượng traffic giữa các node chỉ có thể nhỏ hơn dung lượng của đường quang có thể có. Dữ liệu đầu ra của bài toán: Topo logic với số hop trung bình tối thiểu được xác định như ở công thức (4.1) Các điều kiện ràng buộc của bài toán: Số lượng các thiết bị thu phát quang được trang bị tại mỗi node. Trong mạng quang thì số lượng thiết bị phát quang tại mỗi node quyết định số lượng các đường quang xuất phát từ node đó và số lượng thiết bị thu quang sẽ quyết định số lượng đường quang kết thúc ở node đó. Và trong luận văn này với giả định ở trên thì tại mỗi node số thiết bị thu bằng số thiết bị phát. Số hop logic lớn nhất mà luồng traffic có thể vượt qua khi truyền từ node nguồn đến node đích. Và xem như khi traffic vượt qua h hop thì phải qua (h-1) lần chuyển đổi quang – điện – quang ngoài hai lần chuyển đổi ở hai đầu nguồn và đích. Giải bài toán LTD bằng thuật toán GA. Trong phần này sẽ trình bày cách biểu diễn bài toán thiết kế topo logic đơn thuần và áp dụng thuật toán GA cũng như các thông số để giải bài toán nói trên. Mã hóa kiểu gen cho bài toán LTD. Xét trường hợp tổng quát đối với một topo logic của mạng N node có thể được diễn tả dưới dạng một mạng ma trận kết nối cấp NxN như ở bên dưới (4.2), ở đó thì mỗi phần tử lij của ma trận kết nối miêu tả số đường kết nối từ node i đến node j. (4.2) Nếu xét tại một node thì đường nối từ node đó đến chính nó là không cần thiết vì vầy mà các phần tử trên đường chéo của ma trận L trong (4.2) có thể được xem đều bằng 0 có nghĩa là: lii = 0 "i = 1… N. (4.3) Lúc đó ma trận kết nối ở (4.2) có thể được viết lại như ở (4.4). (4.4) Và từ ma trận L ở (4.4) ta có thể dễ dàng biểu diễn topo của mạng N node dưới dạng một vector hàng có N(N – 1) phần tử như ở dạng (4.5): L = [l12, l13,…, l1N, l21, l23, l24, …,l2N, …,lN1, lN2, …,lN(N-1) ] (4.5) Nếu như chỉ xét trường hợp số đường nối từ node nguồn đến node đích không quá một thì vector hàng diễn tả topo của mạng theo như ở (4.5) là một chuỗi nhị phân với chiều dài N(N – 1) bit. Sau đây ta xét một ví dụ đối với mạng 6 node như ở hình 4.1 bên dưới. Hình 4.1- Topo logic của mạng 6 node. Và topo logic đã cho ở hình 4.1 có thể được biểu diễn ở dạng ma trận kết nối như hình vẽ 4.2 sau đây: Hình 4.2- Biểu diễn topo logic dưới dạng ma trận. Mặc khác với topo logic ở hình 4.1 ta cũng có thể biểu diễn dưới dạng chuỗi nhị phân như ở bảng 4.1 bên dưới: bảng gồm hai hàng và N(N – 1) cột với N là số node mạng. Trong đó ở hàng thứ nhất diễn tả cặp nguồn đích và hàng thứ hai miêu tả số lượng đường kết nối. Ví dụ biểu diễn cho mạng topo logic 6 node của hình 4.1 ở trên ta có bảng sau: 1 2 1 3 1 4 1 5 1 6 2 1 2 3 2 4 2 5 2 6 3 1 3 2 3 4 3 5 3 6 4 1 4 2 4 3 4 5 4 6 5 1 5 2 5 3 5 4 5 6 6 1 6 2 6 3 6 4 6 5 1 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 Bảng 4.1- Biểu diễn topo logic dưới dạng chuỗi nhị phân. Tóm lại với topo của mạng N node ta có thể thiết lập một song ánh giữa tập hợp các topo logic của mạng N node và tập hợp các chuỗi nhị phân có chiều dài N(N – 1) bit. Và biểu diễn topo dưới dạng chuỗi nhị phân khi áp dụng vào thuật toán GA ta xem chuỗi nhị phân như là một nhiễm sắc thể. Mối liên quan giữa các khái niệm của GA và mạng. Để có thể giải bài toán LTD bằng cách dùng thuật giải GA. Trước tiên ta cần xây dựng mối liên hệ giữa các khái niệm của GA và các khái niệm về mạng của bài toán LTD. Khái niệm theo GA Khái niệm theo mạng Một cá thể (individual) Quần thể (Population) Nhiễm sắc thể (Chromosome) Gen trong nhiễm sắc thể Vị trí của gen trong nhiễm sắc thể Nội dung của gen. Một topo của mạng cụ thể. Tập hợp nhiều topo Chuỗi nhị phân mô tả các kết nối tạo nên topo. Bit trong chuỗi nhị phân thể hiện đường nối trong mạng. Vị trí đường nối trong mạng. Số lượng đường nối của mạng. Bảng 4.2- Mô tả mối liên hệ giữa các khái niệm của GA và mạng. Xây dựng hàm thích nghi cho bài toán LTD. Để có thể kiểm tra được khả năng tối ưu của một topo đối với mạng. Hay có thể đánh giá được độ tốt của một cá thể đối với thuật giải GA, chúng ta cần có một hàm thích nghi dựa theo hàm mục tiêu cho trước để thông qua đó có thể kiểm tra được độ tốt cho mỗi cá thể trong quần thể. Và hàm thích nghi thường là một hàm đơn điệu tăng và có miền giá trị không âm. Và như đã giới thiệu ở trên thì trong luận văn này bài toán LTD được giải quyết theo hướng mục tiêu tối thiểu số hop trung bình như ở trong (4.1). Do đó hàm thích nghi được xây dựng như ở trong (4.6). (4.6) Trong đó A là một số dương, quyết định đến biên độ của f của hàm thích nghi và trong luận văn này giá trị A chọn là 200. là giá trị hop trung bình của mạng. Đối với một mạng có N node thì = max = N – 1 và = min = 1. Vậy khi = max = N – 1 thì f = fmin = Và khi = min = 1 thì f = fmax = A. f A A/(N – 1) 0 1 N-1 Hình 4.3- Hình vẽ biểu diễn hàm thích nghi theo hàm mục tiêu. Các bước áp dụng để giải quyết bài toán LTD bằng GA. Để tiến hành giải bài toán thiết kế topo logic bằng cách áp dụng thuật giải GA, ta sẽ tiến hành các bước sau: Khởi tạo quần thể ban đầu. Như đã giới thiệu thì thuật toán GA hoạt động với một quần thể chứ không chỉ một cá thể riêng lẻ, do đó ta có thể khởi tạo quần thể ban đầu bằng cách tạo ngẫu nhiên hoặc khởi tạo quần thể ban đầu dựa vào một số thông tin đã biết trước. Và trong khuôn khổ luận văn này thì quần thể ban đầu được tạo random một cách ngẫu nhiên với số cá thể trong quần thể được cho trước. Sau khi có được quần thể ban đầu. Ta tiến hành tính toán độ thích nghi cho mỗi cá thể tương ứng đồng thời kiểm tra điều kiện ràng buộc cho mỗi cá thể. Nếu cá thể nào thỏa điều kiện ràng buộc thì giữ nguyên giá trị độ thích nghi, nếu cá thể nào không thỏa ta sẽ tiến hành phạt cá thể đó. Độ thích nghi mới cho các cá thể không thỏa là độ thích nghi sau khi đã tiến hành phạt chúng. Chọn phương án chọn lọc. Như đã giới thiệu ở chương ba, có nhiều cách chọn lọc để tạo nên thế hệ tiếp theo. Và trong khuông khổ luận này thì trình bày cách chọn lọc theo bàn roulette để chọn ra số cá thể để tham gia vào các phép toán của GA và tạo nên thế hệ mới. Và cách thức thực hiện như sau: Bước 1: Với số lượng cá thể được biết trước trong quần thể ta tiến hành tính độ thích nghi cho mỗi cá thể theo công thức hàm thích nghi ở (4.6) Bước 2: Tiếp theo tính xác suất chọn lọc cho mỗi cá thể theo công thức (3.7) và xác suất chọn lọc của mỗi cá thể là một số thực dương nhỏ hơn một. Và tổng tất cả các xác suất của các cá thể là bằng một. Bước 3: Sau đó xếp các giá trị xác suất tương ứng của các cá thể lên trên đoạn [0,1]. Như thế ta có cá thể thứ nhất sẽ chiếm đoạn từ [0, f1], cá thể thứ hai chiếm đoạn (f1, f1+f2], tiếp theo cá thể thứ ba chiếm đoạn (f1+ f2, f1+ f2+f3 ] và cứ thế đến cá thể cuối cùng sẽ chiếm đoạn còn lại. Giả sử có n cá thể thì cá thể cuối cùng sẽ chiếm đoạn (f1+f2+…+fn-1, 1]. Và việc chọn các cá thể để tạo lập thế hệ mới ta chỉ cần tạo ngẫu nhiên n số thực trong khoảng (0,1). mỗi số thực rơi vào đoạn nào thì ta sẽ chọn cá thể tương ứng. Và ta cũng sẽ chọn được n cá thể cho thế hệ tiếp theo. Theo như cách này thì một cá thể có thể được chọn nhiều lần tùy vào xác suất được chọn của nó lớn hay nhỏ. Quá trình chọn lọc được tóm tắt theo hình vẽ sau. Hình 4.4- Các bước tiến hành chọn lọc cá thể theo bàn roulette. Sử dụng phép toán lai tạo. Sau khi đã chọn lọc đủ số lượng cá thể để tạo thế hệ kế tiếp. Thì ta tiến hành bước tiếp theo của phép toán GA, đó là phép toán lai tạo. Không phải cá thể nào cũng được lai tạo. Lai tạo chỉ xảy ra với một xác xuất Pc cho trước. với Pc nằm trong khoảng (0,1). Tùy vào từng đối tượng bài toán mà giá trị Pc sẽ khác nhau để GA có thể hoạt động một cách có hiểu quả. Và lai tạo cũng có nhiều kiểu lai tạo khác nhau như đã giới thiệu ở chương III. Trong khuông khổ luận văn này sử dụng kiểu lai tạo đơn giản đó là lai tạo đơn điểm để giải bài toán LTD, sau đây là tóm tắt và các bước thực hiện cho quá trình lai tạo đơn điểm. Hình 4. 5- Các bước tiến lai tạo đơn điểm. Bước 1: Sau khi đã chọn lọc được đủ số lượng cá thể cho quần thể bây giờ ta sẽ tiến hành chọn ra một số cá thể để thực hiện phép lai tạo. Cũng như trên với quần thể có n cá thể ta sẽ tạo ngẫu nhiên n số thực trong khoảng (0,1) và đánh số theo thứ tự tương ứng cho mỗi cá thể. Với mỗi số thực tương ứng ta đem so sánh với xác suất chọn lọc cho trước nếu số thực đó nhỏ hơn xác suất chọn lọc, ta sẽ chọn cá thể tương ứng với số thực đó để thực hiện phép lai tạo. Bước 2: Xem thử số lượng cá thể tham gia lai tạo là chẵn hay lẻ. Nếu là chẵn ta sẽ tiến hành bắt cặp từng đôi một và chuẩn bị để lai tạo. Nếu là lẻ sẽ bỏ bớt một cá thể hoặc cộng thêm vào một cá thể bất kỳ để có thể bắt cặp từng đôi một và chuẩn bị lai tạo. Bước 3: Xem thử có bao nhiêu cặp cá thể tham gia lai tạo.Giả sử có Z cặp tham gia lai tạo, tiến hành tạo ngẫu nhiên Z số tự nhiên trong khoảng chiều dài gen của mỗi cá thể. Mỗi số tự nhiên tương ứng cho mỗi vị trí lai tạo cho mỗi cặp cá thể tương ứng. (ví dụ mỗi cá thể có chiều dài 30 gen vậy số tự nhiên tương ứng cho vị trí lai tạo sẽ nằm trong đoạn [2,29] ). Bước 4: Tiến hành cắt làm đôi mỗi cá thể tương ứng tại vị trí lai tạo của mỗi cặp tương ứng. Sau đó tiến hành ghép chéo phần đầu của cá thể cha mẹ thứ nhất với phần sau của cha mẹ thứ hai, và ngược lại để tạo ra các cá thể con tương ứng cho mỗi cặp tham gia lai tạo. Trong luận văn này sau phép lai tiến hành lấy các cá thể con và bỏ các cá thể bố mẹ để tham gia vào quần thể mới. Sử dụng phép toán đột biến. Sau khi thực hiện phép toán lai tạo, ta tiến hành phép toán tiếp theo của thuật toán di truyền đó là phép đột biến. Tuy phép toán đột biến chỉ thay đổi một thành phần gen của cá thể nhưng sự thay đổi đó mang lại hiệu quả, đem lại cái mới cho phép toán lai sau này. Sự kết hợp của các phép toán chọn lọc và lai tạo đôi khi làm thất thoát những nhiễm sắc thể có tiềm năng, điều đó có thể dẫn đến kết quả tối ưu cục bộ thay vì tối ưu toàn cục. Do đó cần có phép toán đột biến để khắc phục tình trạng trên. Thường thì đột biến chỉ xảy ra với một xác suất Pm rất thấp thường từ 0.01 đến 0.1 [1]. Đột biến cũng có nhiều kiểu khác nhau. Trong luận văn này sử dụng phép đột biến đảo bít (đơn giản nếu nội dung gen là 0 sau khi đột biến sẽ có nội dung là 1 và ngước lại),đồng thời kết hợp với đột biến cấu trúc. Và ý tưởng đột biến được thực hiện như sau: Hình 4.6- Các bước đột biến đảo bít. Bước 1:Mỗi gen trên mỗi cá thể đều có xác suất đột biến như nhau, xác định chiều dài gen của mỗi cá thể, và đem nhân với số lượng cá thể trong quần thể.( ví dụ mỗi cá thể có chiều dài gen là 30 và trong quần thể có 20 cá thể vậy số gen tổng cộng trong quần thể là 30×20 = 600 gen ) Bước 2: tiếp theo tạo ngẫu nhiên một tập số thực trong khoảng (0,1),quần thể có bao nhiêu gen tạo bấy nhiêu số thực tương ứng cho mỗi gen,(ví dụ có 600 gen tạo ngẫu nhiên 600 số thực) và so sánh mỗi số thực với xác suất đột biến Pm, nếu số thực đó nhỏ hơn Pm thì thực hiện đột biến gen đó, nếu số thực đó lớn hơn Pm thì không đột biến gen đó. Ngoài đột biến đảo bít trong luận văn này còn sử dụng đột biến cấu trúc như đã giới thiệu ở chương III. Sử dụng chính sách thay thế. Sau khi thực hiện các phép toán lai tạo và đột biến để có thể giữ lại cá thể tốt nhất của quần thể trước ta thực hiện chính sách thay thế bằng cách sao chép cá thể tốt nhất của thế hệ trước, cất tại một vị trí đặc biệt để bảo đảm cá thể tốt nhất của thế hệ trước được truyền lại cho thế hệ sau. Chọn điều kiện dừng. Đối với một bài toán giải bằng thuật giải GA. Thì có nhiều tiêu chuẩn để qui định điều kiện dừng khác nhau như. Dừng lại sau một khoảng thời gian chạy qui định trước. Dừng lại sau một số thế hệ qui định trước. Dừng lại sau một khoảng thế hệ mà kết quả tìm kiếm không được cải thiện. Dừng lại sau một khoảng thời gian mà kết quả tìm kiếm không được cải thiện. Và trong luận văn này điều kiện dừng đối với bài toán thiết kế topo logic đơn thuần đó là sau một số thế hệ qui định trước. Xử lý ràng buộc cho bài toán LTD. Đối với bài toán thiết kế topo logic đơn thuần vì là bài toán thuộc dạng tối ưu có ràng buộc do đó trong quá trình tính toán độ thích nghi và kiểm tra điều kiện ràng buộc của mỗi cá thể trong quần thể. Có thể xảy ra trường hợp cá thể không thỏa mãn các điều kiện ràng buộc do đó cần phải xử lý các trường hợp này thông thường người ta sử dụng kỹ thuật phạt để phạt các cá thể vi phạm [1],[11]. Có rất nhiều kĩ thuật phạt để xử lý các trường hợp vi phạm. có thể dùng hàm cộng, hàm nhân, hoặc có thể phạt chết cá thể vi phạm… Và đối với bài toán thiết kế topo logic đơn thuần để giải quyết vấn đề trên thì trong luận văn này sử dụng kỹ thuật phạt là hàm nhân với nghịch đảo của giá trị hop trung bình thỏa điều kiện ràng buộc lớn nhất. Mục đích đảm bảo cho mọi cá thể vi phạm trong quần thể sẽ có độ thích nghi nhỏ hơn cá thể có độ thích nghi nhỏ nhất nhưng thỏa điều kiện ràng buộc. Nếu cá thể thỏa điều kiện ràng buộc. (4.7) Nếu cá thể không thỏa điều kiện ràng buộc. Trong đó f(xi) là độ thích nghi của cá thể thứ i khi chưa dùng hàm phạt.Và là giá trị hop trung bình lớn nhất trong tất cả các cá thể thỏa điều kiện ràng buộc. Và F(xi) là độ thích nghi của cá thể thứ i sau khi đã sử dụng hàm phạt. Lưu đồ bài toán thiết kế topo logic đơn thuần. Hình 4.7- Lưu đồ áp dụng GA giải bài toán LTD đơn thuần. Một số kết quả chạy chương trình mô phỏng: Chạy chương trình mô phỏng bằng Matlab 6.5. Kết quả thiết kế topo logic cho mạng 6 node: Dữ liệu đầu vào: Mạng vật lý dạng ring 6 node Traffic yêu cầu số luồng STM-1 trao đổi giữa các node như trong (4.9) (4.9) Điều kiện ràng buộc: Số lượng thu phát tại mỗi node TR = 2 Số hop logic lớn nhất H = 4 Các thông số của GA: Số cá thể trong quần thể = 100 Các xác suất lai tạo và đột biến: Pc = 0.80; Pm = 0.03 Chạy 150 thế hệ. Kết quả: Topo do GA tìm được. Giá trị hop trung bình = 1.37055837563452 Độ thích nghi của cá thể = 145.9259259259259 Topo logic: Hình 4. 8-Topo logic của mạng 6 node thiết kế cho traffic ở (4.9). Số port tại mỗi node 2 Số đường quang tổng cộng 12 Số hop logic tối đa Hopmax = 2 Giá trị hop trung bình 1.37055837563452 Bảng 4. 3- Các thông số của topo logic thiết kế cho traffic (4.9). Hình 4.9- Mô tả giá trị hop trung bình GA tìm được của traffic (4.9) qua các thế hệ. Kết quả thiết kế topo logic cho mạng 6 node (tt). Dữ liệu đầu vào: Mạng vật lý dạng ring 6 node Traffic yêu cầu số luồng STM-1 trao đổi giữa các node như trong (4.10) (4.10) Điều kiện ràng buộc: Số lượng thu phát tại mỗi node TR = 3 Số hop logic lớn nhất H = 3 Các thông số của GA: Số cá thể trong quần thể = 100 Các xác suất lai tạo và đột biến: Pc = 0.80; Pm = 0.03 Chạy 120 thế hệ. Kết quả: - Giá trị hop trung bình = 1.10998307952623 - Độ thích nghi của cá thể = 180.1829268292683 - Topo logic: Hình 4.10- Topo logic của mạng 6 node thiết kế cho traffic ở (4.10). Hình 4.11- Mô tả giá trị hop trung bình GA tìm được của traffic (4.10) qua các thế hệ. Số port tại mỗi node 3 Số đường quang tổng cộng 18 Số hop logic tối đa Hopmax = 2 Giá trị hop trung bình 1.10998307952623 Bảng 4.4- Các thông số của topo logic thiết kế cho traffic (4.10). Kết quả thiết kế topo logic cho mạng 6 node (tt). Dữ liệu đầu vào: Mạng vật lý dạng ring 6 node Traffic yêu cầu số luồng STM-1 trao đổi giữa các node như trong (4.11) (4.11) Điều kiện ràng buộc: Số lượng thu phát tại mỗi node TR = 4 Số hop logic lớn nhất H = 3 Các thông số của GA: Số cá thể trong quần thể = 100 Các xác suất lai tạo và đột biến: Pc = 0.80; Pm = 0.03 Chạy 120 thế hệ. Kết quả: - Giá trị hop trung bình = 1.02368866328257 - Độ thích nghi của cá thể = 195.3719008264463 Số port tại mỗi node 4 Số đường quang tổng cộng 24 Số hop logic tối đa Hopmax = 2 Giá trị hop trung bình 1.02368866328257 Bảng 4.5- Các thông số của topo logic thiết kế cho traffic (4.11). Hình 4.12- Mô tả giá trị hop trung bình GA tìm được của traffic (4.11) qua các thế hệ. * Nhận xét : Qua ba kết quả của bài toán thiết kế topo logic cho mạng 6 node ở trên. Với cùng một traffic ta thấy nếu số lượng thiết bị thu phát tại mỗi node tăng lên thì kết quả Topo logic tìm được sẽ có giá trị hop trung bình càng giảm xuống. KẾT LUẬN – NHỮNG HẠN CHẾ - HƯỚNG MỞ CỦA ĐỀ TÀI. KẾT LUẬN Như đã biết công nghệ WDM đem lại những khả năng và thuận lợi to lớn cho các nhà khai thác mạng, tuy nhiên để có thể tận dụng và vận hành một cách có hiệu quả nhất đòi hỏi các nhà khai thác phải xây dựng cho mình một mạng lưới phù hợp trên những tài nguyên sẵn có qua đó để có thể vận hành và khai thác một cách có hiệu quả nhất tránh những lãng phí, cũng như công tác bảo dưỡng.... Với những vấn đề đã trình bày, lý thuyết về mạng WDM, các vấn đề liên quan đến bài toán LTD đồng thời tìm hiểu thuật toán GA. Trong khuôn khổ luận văn đã vận dụng một công cụ mới GA để giải bài toán thiết kế topo logic cho mạng cáp quang WDM. Trong điều kiện hiện nay các mạng ngày càng phát triển do đó việc xây dựng một mạng logic hợp lý để có thể đáp ứng được nhu cầu thông tin là một điều rất cần thiết. NHỮNG HẠN CHẾ Trong những điều kiện và thời gian cho phép luận văn chỉ có thể giải quyết bài toán thiết kế topo logic với những traffic hạn chế mà sợi quang có thể truyền tải được. Chưa giải quyết cho các traffic lớn vượt khả năng của sợi quang. Chưa giải quyết triệt để bài toán thiết kế mạng. Chỉ giải quyết bài toán thiết kế topo logic đơn thuần mà chưa giải quyết các bài toán định tuyến traffic, và định tuyến đường quang. Để có thể áp dụng chạy cho một mạng thực tế. Chưa nghiên cứu thêm một thuật toán khác để có thể so sánh. HƯỚNG MỞ CỦA ĐỀ TÀI. Cần nghiên cứu thêm lý thuyết về mạng WDM cũng như tìm hiểu kỹ về thuật toán di truyền để có thể giải quyết bài toán một cách có hiểu quả và tối ưu nhất. Giải quyết tiếp các bài toán định tuyến traffic và định tuyến đường quang mà đề tài còn bỏ ngỏ để có thể xây dựng một bài toán thiết kế mạng hoàn chỉnh. Nghiên cứu thêm các phép toán đặc biệt của thuật toán GA như lai ghép thông minh, đột biến biên... để có thể tối ưu cho thuật giải và giải quyết bài toán có hiệu quả nhất. Thử viết chương trình bằng ngôn ngữ khác xem tốc độ thực hiện... Chạy thử cho một mạng thực tể nếu có thể. PHỤ LỤC. PHỤ LỤC A : Sử dụng chương trình mô phỏng. Chương trình sử dụng Matlab 6.5 để viết . Vì vẫn còn đang trong thời kỳ nghiên cứu và thử nghiệm, chưa giải quyết triệt để một bài toán thiết kế mạng do đó chương trình chỉ thiết kế giao diện cho bài toán thiết kế topo logic và kết quả chỉ thực hiện tìm kiếm ma trận kết nối cho bài toán thiết kế topo logic đơn thuần. Cách chạy chương trình :  Để sử dụng được chương trình yêu cầu máy tính phải có cấu hình cài đặt và chạy được môi trường Matlab từ 6.5 trở lên.  Sau khi đã cài đặt Matlab chạy chương trình Matlab và đổi đường dẫn hiện hành đến ổ đĩa có chứa thư mục DesignTopologicalforNnodeNetworks.  Trong thư mục DesignTopologicalforNnodeNetworks. Kích đúp vào figure-file có tên là Giao_dien_Design_Topo_logic11. Sau đó thực hiện nhập dữ liệu như yêu cầu của bài toán. Giao diện của bài toán thiết kế topo logic có dạng như sau. Hình vẽ mô tả giao diện của chương trình thiết kế topo logic  Trong khung Node_number ta tiến hành nhập vào số node của mạng vật lý. Tiếp theo trong khung INPUT MATRIX TRAFFIC ta nhập vào ma trận traffic theo yêu cầu....tiếp theo đến các điều kiện ràng buộc của bài toán. Trong khung PORT_number ta tiến hành nhập vào số lượng thiết bị thu phát tại mỗi node, và trong khung HOP_max ta nhập vào số chặn tối đa cho phép mỗi luồng traffic truyền đi. Tiếp đến ta sẽ nhập vào các thông số của GA. Trong khung Pop_size ta sẽ nhập vào số cá thể trong quần thể. (trong bài toán này thường sử dụng với số lượng 100 với số node lớn hơn hoặc bằng 6 ). Và sau đó trong khung Pc ta nhập vào xác suất lai tạo, xác suất này được chọn tùy thuộc vào bài toán cụ thể đối với bài toán này qua kết quả thống kê ta thấy giá trị Pc = 0.8 tương đối phù hợp. Còn trong khung Pm ta nhập vào giá trị của xác suất đột biến và trong bài toán này xác suất đột biến được lấy theo tỉ lệ nghịch với chiều dài gen cá thể.[9], tiếp đến trong khung GENERATIONS, ta nhập vào số thế hệ mà GA sẽ tiến hóa. Sau khi đã nhập số liệu ta sẽ kích nút DONE và chương trình được thực thi, sau khi chương trình chạy xong. Ở phần OUT PUT trong các khung trắng của topo logic matrix , hop logic matrix , và value average hop ta kích chuột vào và nhấn enter các kết quả của ma trận kết nối topo logic và ma trận hop logic của traffic vượt qua ngắn nhất sẽ được hiển thị, đồng thời ta cũng sẽ biết được giá trị hop trung của các luồng traffic trên topo logic sau khi được thiết kế. Chú ý: Các xác suất lai tạo từ 0.6 đến 0.9 ; xác suất đột biến từ 0.01 đến 0.1 Các xác suất này lấy theo đề nghị trong [1], [9] PHỤ LỤC B : Mô tả chi tiết hoạt động của GA. ví dụ minh họa chi tiết hoạt động của GA. Sau đây ta sẽ tiến hành xét một ví dụ đơn giản cho mạng 5 node.Và tiến hành giải bài toán thiết kế topo logic đơn thuần. Giả sử cho một mạng vật lý dạng ring 5 node. Hình 4.8- Topo vật lý dạng ring 5 node. Và traffic trao đổi giữa các node như sau: (4.8) Các điều kiện ràng buộc gồm có : Thiết bị thu phát tại mỗi node là 2 thiết bị. Hop logic lớn nhất mà traffic được phép đi qua là 3 Và chúng ta cần giải bài toán trên bằng thuật toán di truyền với các thông số giả định như sau: Pop size: Số cá thể trong quần thể là 20 Xác suất lai tạo cá thể là 0.6 Xác suất đột biến cá thể là 0.05 * Và sau đây là các bước tiến hành để giải bài toán thiết kế đơn thuần như đã nêu đối với giả thiết ở trên. Khởi tạo quần thể ban đầu: Đầu tiên ta khởi tạo ngẫu nhiên quần thể ban đầu bằng cách tạo ngẫu nhiên 20 ma trận kích kỡ [5×5] với đường chéo ma trận bằng 0, mỗi ma trận tương ứng cho một topo logic của mạng. Sau đó tiến hành mã hóa kiểu gen theo như ở (4.5) và ta được 20 nhiễm sắc thể tương ứng cho 20 topo như sau. N(:,:,1) = 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 0 0 N(:,:,2) = 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,3) = 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 N(:,:,4) = 1 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 N(:,:,5) = 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 N(:,:,6) = 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 N(:,:,7) = 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 N(:,:,8) = 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 1 N(:,:,9) = 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 N(:,:,10) = 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 N(:,:,11) = 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 N(:,:,12) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 N(:,:,13) = 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 N(:,:,14) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,15) = 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0 1 0 N(:,:,16) = 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 N(:,:,17) = 1 0 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 N(:,:,18) = 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 N(:,:,19) = 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 N(:,:,20) = 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 Tính toán giá trị thích nghi theo công thức: Để tính toán giá trị thích nghi cho mỗi topo ta cần chuyển ma trận topo logic sang ma trận hoplogic tương ứng. Sử dụng thuật toán tìm đường đi ngắn nhất để chuyển từ ma trận topo logic sang ma trận hoplogic (tức xác định con đường đi ngắn nhất từ một node nguồn đến một node đích) Tương ứng với hai topo thứ nhất và topo thứ hai ta có hai ma trận hoplogic như sau: Và tương tự như thế ta cũng sẽ có được ma trận hoplogic của các topo từ 3 đến 20. Sau khi đã chuyển sang ma trận hoplogic ta tiến hành tính giá trị hop trung bình cho mỗ topo theo công thức ở (4.1). Sau khi đã tính giá trị hop trung bình song ta tiếp tục tính độ thích nghi cho mỗi topo theo công thức (4.6) với A là một số chọn trước A=200. Ta có độ thích nghi (chưa tiến hành phạt ) tương ứng của các topo như sau: f(:,:,1) = 0 f(:,:,2) = 120.6543967280164 f(:,:,3) = 0 f(:,:,4) = 0 f(:,:,5) = 0 f(:,:,6) = 110.9022556390978 f(:,:,7) = 111.5311909262760 f(:,:,8) = 0 f(:,:,9) = 0 f(:,:,10) = 122.6611226611227 f(:,:,11) = 1.206543967280164e+002 f(:,:,12) = 125 f(:,:,13) = 0 f(:,:,14) = 127.1551724137931 f(:,:,15) = 0 f(:,:,16) = 0 f(:,:,17) = 113.4615384615385 f(:,:,18) = 98.00664451827244 f(:,:,19) = 0 f(:,:,20) = 95.16129032258064 Ta thấy ở trên có các giá trị có độ thích nghi bằng 0 là vì trong quá trình tạo ngẫu nhiên các topo thì có những topo ở đó không xác định được đường đi từ một node nguồn đến một node đích. Trong những trường hợp đó thì coi như đừơng đi từ node nguồn đó đến node đích đó là vô cùng và kí hiệu inf. Và áp dụng vào công thức (4.1) tính giá trị hop trung bình cho topo thì giá trị hop trung bình cũng xem như bằng vô cùng. Tiếp tục tính giá trị thích nghi theo công thức (4.6) ta có các giá trị thích nghi đó bằng 0. Kiểm tra điều kiện ràng buộc Sau khi tính giá trị thích nghi song ta sẽ tiến hành xem xét điều kiện ràng buộc cho mỗi topo nếu chúng thỏa điều kiện ràng buộc thì độ thích nghi được giữ nguyên, nếu chúng không thỏa điều kiện thì sẽ tiến hành phạt để giảm độ thích nghi của chúng xuống và đảm bảo độ thích nghi của những topo không thỏa phải nhỏ hơn độ thích nghi của các topo thỏa điều kiện và có giá trị thích nghi nhỏ nhất trong tất cả các topo thỏa. Kiểm tra điều kiện ràng buộc và tiến hành phạt theo công thức (4.7). Để có thể phạt đựơc các cá thể trước tiên ta phải tính giá trị Sau khi kiểm tra ta có hai topo thỏa điều kiện ràng buộc và có cùng giá trị hop trung bình lớn nhất như sau: (:,:,2) = 1.65762711864407 (:,:,11) = 1.65762711864407 Từ đó ta tính được các giá trị Pi : P(:,:,2) = 0.60327198364008 P(:,:,11) = 0.60327198364008 lúc đó ta tính được giá trị thích nghi của các topo sau khi kiểm tra điều kiện ràng buộc và qua hàm phạt theo công thức (4.7) ta được các giá trị thích nghi mới như sau: F(:,:,1) = 0 F(:,:,2) = 72.78741724900782 F(:,:,3) = 0 F(:,:,4) = 0 F(:,:,5) = 0 F(:,:,6) = 66.90422374955794 F(:,:,7) = 67.28364278783521 F(:,:,8) = 0 F(:,:,9) = 0 F(:,:,10) = 73.99801878329485 F(:,:,11) = 120.6543967280163 F(:,:,12) = 75.40899795501022 F(:,:,13) = 0 F(:,:,14) = 76.70915309216557 F(:,:,15) = 0 F(:,:,16) = 0 F(:,:,17) = 68.44816737454774 F(:,:,18) = 59.12466284844656 F(:,:,19) = 0 F(:,:,20) = 57.40814037865294 Tổng độ thích nghi quần thể là = 738.72682094653515 Lúc này đã hoàn tất thế hệ đầu và cá thể tốt nhất trong thế hệ đầu tiên là một trong hai topo L(:,:,2) hoặc L(:,:,11) với hop trung bình là = 1.65762711864407 Tiếp theo ta tiến hành chọn lọc các cá thể để tham gia vào các phép toán GA. Để có thể chọn lọc ta sẽ tính xác suất chọn lọc các cá thể theo công thức (3.7) và sắp xếp các xác suất đó trên đoạn [0,1]. Và các giá trị được sắp xếp như sau: Fs(:,:,1) = 0.00000000000000 Fs(:,:,2) = 0.09853089827677 Fs(:,:,3) = 0.09853089827677 Fs(:,:,4) = 0.09853089827677 Fs(:,:,5) = 0.09853089827677 Fs(:,:,6) = 0.18909783297103 Fs(:,:,7) = 0.28017837977130 Fs(:,:,8) = 0.28017837977130 Fs(:,:,9) = 0.28017837977130 Fs(:,:,10) = 0.38034804558698 Fs(:,:,11) = 0.54367553459492 Fs(:,:,12) = 0.64575521522488 Fs(:,:,13) = 0.64575521522488 Fs(:,:,14) = 0.74959489034846 Fs(:,:,15) = 0.74959489034846 Fs(:,:,16) = 0.74959489034846 Fs(:,:,17) = 0.84225183122797 Fs(:,:,18) = 0.92228772700429 Fs(:,:,19) = 0.92228772700429 Fs(:,:,20) = 1.00000000000000 Sau khi đã sắp xếp các giá trị xác suất trên đoạn [0.1] bây giờ ta tiến hành quay ngẫu nhiên 20 lần bàn roullete, mỗi lần chọn ra một cá thể. Quay(:,:,1) = 0.60854036122399 Quay(:,:,2) = 0.01575981791975 Quay(:,:,3) = 0.01635493355000 Quay(:,:,4) = 0.19007458907973 Quay(:,:,5) = 0.58691847188467 Quay(:,:,6) = 0.05758108987829 Quay(:,:,7) = 0.36756803882634 Quay(:,:,8) = 0.63145116474444 Quay(:,:,9) = 0.71763442146570 Quay(:,:,10) = 0.69266939471779 Quay(:,:,11) = 0.08407906075044 Quay(:,:,12) = 0.45435514975555 Quay(:,:,13) = 0.44182829690634 Quay(:,:,14) = 0.35325045500069 Quay(:,:,15) = 0.15360636252349 Quay(:,:,16) = 0.67564464963341 Quay(:,:,17) = 0.69921332774126 Quay(:,:,18) = 0.72750912921793 Quay(:,:,19) = 0.47838438095666 Quay(:,:,20) = 0.55484198634168 Với các giá trị quay ở trên ta lần lược chọn được các cá thể của thế hệ trước như sau: 12,2,2,7,12,2,10,12,14,14,2,11,11,10,6,14,14,14,11,12. Các cá thể này lần lược là các cá thể của thế hệ tiếp theo và đánh số thứ tự từ 1 đến 20. Và các nhiễm sắc mới tương ứng là: N(:,:,1) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 N(:,:,2) = 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,3) = 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,4) = 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 N(:,:,5) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 N(:,:,6) = 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,7) = 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 N(:,:,8) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 N(:,:,9) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,10) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,11) = 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,12) = 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 N(:,:,13) = 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 N(:,:,14) = 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 N(:,:,15) = 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 N(:,:,16) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,17) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,18) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,19) = 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 N(:,:,20) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 Sau khi đã chọn lọc được các cá thể ta tiến hành lai tạo. Để có thể lai tạo ta cũng tạo ngẫu nhiên 20 số thực trong khoảng (0,1) tương ứng cho mỗi cá thể và số thực nào nhỏ hơn xác suất lai tạo thì sẽ chọn cá thể đó để lai tạo. Sau khi tạo ngẫu nhiên giả sử ta chọn được các cá thể sau để lai tạo. (2,4,7,8,10,15,16,19). Và cứ hai cá thể bắt thành một cặp để lai tạo ta có các cặp (2,4);(7,8);(10,15);(16,19). Tiếp theo ta tạo ngẫu nhiên vị trí lai tạo cho mỗi cặp và vị trí được tạo ngẫu nhiên như sau: (3,8,16,2), và tiến hành lai tạo ta được các nhiễm sắc thể mới trong quần thể như sau: N(:,:,1) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 N(:,:,2) = 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 N(:,:,3) = 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,4) = 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,5) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 N(:,:,6) = 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,7) = 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 N(:,:,8) = 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 N(:,:,9) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,10) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 N(:,:,11) = 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,12) = 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 N(:,:,13) = 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 N(:,:,14) = 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 N(:,:,15) = 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 N(:,:,16) = 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 N(:,:,17) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,18) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,19) = 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,20) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 Sau khi lai tạo song bước tiếp theo là phép đột biến ví có 20 cá thể mỗi cá thể có 20 gen vậy số gen tổng cộng trong quân thể là 20×20=400 gen. ta cũng tạo ngẫu nhiên 400 số thực trong khoảng (0,1) tương ứng cho 400 gen. Gen đầu tiên của cá thể thứ nhất tương ứng vơi số thứ tự là một và gen cuối cùng của cá thể thứ 20 tương ứng với số thứ tự 400. Số thực nào nhỏ hơn xác suất đột biến sẽ đột biến gen đó và ngược lại lớn hơn xác suất đột biến sẽ không phải bị đột biến. Sau khi tạo các số ngẫu nhiên ta có các gen tương ứng sẽ đột biến là. (7;9;38;44;49;73;96;105;129;142;144;149;187;212;223;240;241;292;305;307;315;317;333;349;357;396;399 ) Và các nhiễm sắc thể sau khi đột biến là: N(:,:,1) = 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 N(:,:,2) = 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 N(:,:,3) = 1 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0 0 N(:,:,4) = 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 N(:,:,5) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 0 0 N(:,:,6) = 1 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 N(:,:,7) = 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 N(:,:,8) = 1 0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 0 N(:,:,9) = 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,10) = 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 N(:,:,11) = 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 N(:,:,12) = 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 N(:,:,13) = 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 N(:,:,14) = 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 N(:,:,15) = 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1 0 N(:,:,16) = 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 N(:,:,17) = 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 0 N(:,:,18) = 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 0 0 1 0 N(:,:,19) = 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 N(:,:,20) = 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 1 0 Sau khi đã thực hiện phép đột biến song, tiến hành sao chép cá thể tốt nhất của thế hệ trước giữ lại ở vị trí thứ nhất và chuyển nhiểm sắc thể về ma trận topo đồng thời quay lại tính độ thích nghi và kiểm tra điều kiện ràng buộc cho các topo mới trong quần thể vừa tạo ra, và ta có các giá trị thích nghi (đã có hàm phạt) của thế hệ mới như sau: F(:,:,1) = 120.6543967280163 F(:,:,2) =64.95081575687011 F(:,:,3) =75.56910198463869 F(:,:,4) =67.15669251842419 F(:,:,5) =67.28364278783521 F(:,:,6) =57.13169668501577 F(:,:,7) =71.04400605741481 F(:,:,8) =0 F(:,:,9) =76.70915309216557 F(:,:,10) = 0 F(:,:,11) = 77.71407649511970 F(:,:,12) = 80.34547863378063 F(:,:,13) = 65.91305006437929 F(:,:,14) = 73.99801878329485 F(:,:,15) = 73.84449592274859 F(:,:,16) = 0 F(:,:,17) = 77.20834497779788 F(:,:,18) = 69.92740085415485 F(:,:,19) = 79.62650343347835 F(:,:,20) = 72.63887149952004 Tổng độ thích nghi của quần thể mới = 1271.715746274655 Ta thấy ở thế hệ mới này GA vẫn chưa tìm thấy cá thể nào tốt hơn so với thế hệ trước, và vẫn tiếp tục giữ lại cá thể tốt nhất của thế hệ trước làm cá thể tốt nhất cho thế hệ hiện tại. Tuy nhiên qua đó ta thấy được sự tiến hóa của GA, Tổng độ thích nghi của các cá thể ở thế hệ thứ này (1271.72) lớn hơn nhiều so với tổng độ thích nghi của các cá thể của thế hệ trước (738.72). Và cứ tiếp tục như thế cho đến hàng trăm thế hệ tiếp theo GA sẽ tiến hóa và tìm được cá thể tốt hơn rất nhiều so với cá thể tốt nhất hiện tại. Cụ thể sau 150 thế hệ cho chạy thử trên máy tính thì các giá trị tìm được là: Giá trị hop trung bình = 1.15593220338983 Độ thích nghi của topo = 173.020527859238 Tổng độ thích nghi của quần thể:= 2922.346152288134 PHỤ LỤC C : Một số kết quả mô phỏng. Một số kết quả chạy chương trình Thiết kế Topo logic với mạng vật lý có số node khác nhau và traffic yêu cầu khác nhau : Kết quả I : + Dữ liệu vào : - Mạng vật lý bấc kỳ 5 node. - Trafficc yêu cầu  + Ràng buộc : Số Thiết bị thu phát tại mỗi node  : Port = 3 Hop logic tối đa traffic vượt qua   : Hmax= 3 + Kết quả chạy chương trình : Thông số chạy GA. Pop size = 100 ; Pm = 0.80 ; Pc = 0.05 ; Chạy 120 thế hệ. + Kết quả topo logic tìm được và ma trận hop logic tương ứng Giá trị hop trung bình = 1.08902077151335 Hình vẽ biểu diễn giá trị hop trung bình tìm được theo từng thế hệ Kết quả một lần chạy GA cho mạng 5 node với traffic yêu cầu ở trên. Kết quả II : + Dữ liệu vào : - Mạng vật lý bấc kỳ 6 node. - Trafficc yêu cầu  + Ràng buộc : Số Thiết bị thu phát tại mỗi node  : Port = 3 Hop logic tối đa traffic vượt qua   : Hmax= 3 + Kết quả chạy chương trình : Thông số chạy GA. Pop size = 100 ; Pm = 0.80 ; Pc = 0.03 ; Chạy 120 thế hệ. + Kết quả topo logic tìm được và ma trận hop logic tương ứng Giá trị hop trung bình = 1.17619047619048 Hình vẽ biểu diễn giá trị hop trung bình tìm được theo từng thế hệ Kết quả một lần chạy GA cho mạng 6 node với traffic yêu cầu ở trên. Kết quả III : Dữ liệu vào : - Mạng vật lý bấc kỳ 10 node. - Trafficc theo yêu cầu  + Ràng buộc : Số Thiết bị thu phát tại mỗi node  : Port = 4 Hop logic tối đa traffic vượt qua   : Hmax= 6 + Kết quả chạy chương trình : Thông số chạy GA. Pop size = 100 ; Pm = 0.80 ; Pc = 0.025 ; Chạy 160 thế hệ. + Kết quả topo logic tìm được và ma trận hop logic tương ứng Ma trận kết nối topo logic Ma trận Hoplogic tương ứng Giá trị hop trung bình = 1.24239543726236 Độ thích nghi của topo trong quần thể = 160.9793420045907 Hình vẽ biểu diễn giá trị hop trung bình tìm được theo từng thế hệ Kết quả một lần chạy GA cho mạng 10 node với traffic yêu cầu ở trên TÀI LIỆU THAM KHẢO. [1] Thiết kế topologic cho mạng cáp quang Theo phương pháp dùng thuật toán di truyền. Mã số 30-HV-2005-RD-VT. Học Viện Công Nghệ Bưu Chính Viễn Thông Khoa Viễn Thông II. Tphcm-12/2005 – Th.S Ngô Thanh Ngọc & Th.S Võ Nguyễn Quốc Bảo. [2] Towards the Optimal Design of wavelength – Convertible switches in WDM Networks By Xueli Hou Quee’n University at Kingston Ontario, Canada August 2001 Copyright Xueli Hou, 2001 [3] survivability and traffic grooming in wdm optical networks - Arun K. Somani-©Cambridge University Press 2005. [4] Optical Networks A Practical Perspective - second edition -Rajiv Ramaswami, Kuma N. Sivarajan [5] Algorithms for the logical topology design in WDM All-Optical Networks E.Leonardi, M.Mellia, M.Ajmone Marsan ( Dipartimento di Elettronica, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy August 26, 1999.) [6] A fast logical Topology Design with Simulated Annealing in IP over WDM networks - Sugang Xu, Nobuhiro Koyama, Yoshiaki Tanaka- (ICITA-2004)-pp.21-26 [7] Routing and Wavelength Assignment in Optical WDM Networks-George.N. Rouskas Deparment of Computer Science North Carolina State University. [8] Design of Logical Topologies for Wavelength-Routed Optical Networks-Rajiv Ramaswami, Kuma N. Sivarajan [9] Giải một bài toán trên máy tính như thế nào?- Hoàng Kiếm –Nhà xuất bản giáo dục [10]Chuyển mạch gói quang và khả năng ứng dụng trong mạng viễn thông Việt Nam ThS. Nguyễn Bá Hưng-Theo tập san” Nghiên cứu Khoa học và Công nghệ 2006”Viện Khoa học Kỹ thuật Bưu Điện [11] Trí tuệ nhân tạo Lập trình tiến hóa :cấu trúc dữ liệu + thuật giải di truyền = chương trình tiến hóa –T.s. Nguyễn Đình Thúc (chủ biên)- Nhà xuất bản giáo dục [12] Hệ thống ghép kênh theo bước sóng quang. Biên soạn Lê Quốc Cường 2003-Học Viện công nghệ Bưu Chính Viễn Thông. [13] Luận văn Định tuyến bước sóng trong mạng WDM - Lê Huỳnh Bích Ngân -2003. Đại học ĐTVT Học Viện Công Nghệ Bưu Chính Viễn Thông. [14] luận văn thiết kế WDM - Nguyễn Thanh Vân. Đại học ĐTVT 2003 Học Viện Công Nghệ Bưu Chính Viễn Thông. [15] IP OVER WDM Building the Next- Generation Optical Internet- Edited by Sudhir Dixit- wiley interscience-copyright 2003 by A John Wiley & Sons Pubbication *Và Nguồn tài liệu từ Internet. + A Genetic Algorithm Tutorial-Darrell Whitley -Computer Science-Department, Colorado State University + Genetic Algorithm for Routing and Wavelength Assignment Problem in All-optical Networks -Zhong Pan. + Topological Design of Local-Area Networks Using Genetic Algorithms-Reuven Elbaum and Moshe Sidi, Senior member, IEEE/ACM Transactions on networking. Vol 4. No 5, Otober 1996- pp766-778