Luận văn Tóm tắt Nghiên cứu định tuyến và gán bước sóng trong mạng WDM sử dụng phương pháp tính toán tiến hóa lai

1 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- TIÊU VĂN GIANG NGHIÊN CỨU ĐỊNH TUYẾN VÀ GÁN BƯỚC SÓNG TRONG MẠNG WDM SỬ DỤNG PHƯƠNG PHÁP TÍNH TOÁN TIẾN HÓA LAI NGÀNH : KHOA HỌC MÁY TÍNH MÃ SỐ : 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2012 LỜI NÓI ĐẦU Sự bùng nổ của mạng Internet, sự phát triển số lượng người sử dùng, sự phát triển của các ứng dụng và dịch vụ mới trên nền IP, đó là những gì mà chúng ta đã chứng kiến trong vòng gần một thập kỉ qua [7]. Mạng truyền dẫn quang đã đáp ứng được rất nhiều yêu cầu về dung lượng, chi phí xây dựng và tính bảo mật thông tin. Hai công nghệ quan trọng gần đây giúp tăng dung lượng mạng quang đó là ghép kênh theo bước sóng WDM và khuếch đại sợi quang EDFA [25]. Định tuyến và gán bước sóng (RWA) có thể được coi là một bài toán cổ điển trong mạng quang WDM [17]. Trong đó nó có thể được phân thành hai bài toán con: (i) định tuyến và (ii) gán bước sóng. Bài toán con định tuyến là tìm đường từ nguồn tới đích, còn bài toán con gán bước sóng thực hiện gán một bước sóng cho tuyến được thiết lập bởi bài toán con định tuyến. Bài toán RWA có tính kết hợp bởi bản chất của nó và thuộc lớp bài toán tối ưu hóa, do vậy phù hợp với cách tiếp cận heuristic [13]. Đối với vấn đề RWA ta có thể xem xét nhiều mục tiêu thiết kế mạng đồng thời như tối đa hóa số lượng yêu cầu liên lạc để được phục vụ và giảm thiểu số lượng kênh bước sóng được chỉ định[3][6]. Để giải bài toán thiết kế đa mục tiêu, các kỹ thuật tối ưu hóa đa mục tiêu thường được sử dụng. Một số phương pháp sử dụng các gần đúng đơn mục tiêu để giải các bài toán đa mục tiêu như ràng buộc  và tổng trọng số [1]. Tuy nhiên các gần đúng đơn mục tiêu có một nhược điểm là rất khó tìm được các nghiệm tối ưu[16]. Do vậy mà các thuật toán tiến hóa đa mục tiêu được áp dụng để giải các bài toán thiết kế đa mục tiêu này [18] sẽ thu được những kết quả quan trọng cho việc thiết kế mạng toàn quang trên cơ sở công nghệ WDM. 2 Qua đây tôi xin trân trọng cảm ơn TS.Nguyễn Đức Nhân và các thầy cô trong hội đồng khoa học nhà trường, Khoa Quốc tế và sau đại học đã giúp đỡ rất nhiều cho tôi để hoàn thiện luận văn này. Tuy nhiên, do thời gian và trình độ còn giới hạn, tôi kính mong được các thầy cô tiếp tục đóng góp, giúp đỡ để luận văn được hoàn thiện tốt hơn và được ứng dụng vào thực tế. Tôi xin trân trọng cảm ơn! TÁC GIẢ TIÊU VĂN GIANG CHƯƠNG 1: TỔNG QUAN Hệ thống thông tin của con người có lịch sử phát triển từ rất lâu. Cho tới nay, đã có rất nhiều các hệ thống thông tin dưới các hình thức đa dạng. Các hệt hống thông tin này được gán cho các tên gọi nhất định theo môi trường truyền dẫn và đôi khi theo cả tính chất dịch vụ của hệ thống. So với hệ thống thông tin hiện đại đầu tiên là thông tin điện báo (đưa vào khai thác năm 1844) thì hệ thống thông tin quang (mới được khai thác từ những năm 1980) là hệ thống có tuổi đời còn khá trẻ. Tuy vậy cùng với sự phát triển của các dịch vụ mạng và đòi hỏi ngày càng cao về dung lượng và băng thông, hệ thống thông tin quang cũng đã phát triển rất mạnh mẽ về công nghệ trong gần 3 thập niên qua. Do có ưu điểm như vậy nên các hệ thống thông tin quang nhanh chóng được áp dụng rộng rãi trên mạng lưới. Chúng còn tiềm tàng những khả năng rất lớn trong việc hiện đại hoá các mạng lưới viễn thông trên thế giới. 1.1. Mạng WDM. 1.1.1. Định nghĩa: WDM (Wavelength Division Multiplexing – Ghép kênh theo bước sóng) là công nghệ “trong một sợi quang truyền dẫn đồng thời nhiều tín hiệu quang với nhiều bước sóng khác nhau”. ở đầu phát, nhiều tín hiệu quang có bước sóng khác nhau được tổ hợp lại (ghép kênh) để truyền đi trên một sợi quang. ở đầu thu, tín hiệu tổ hợp đó được phân giải ra (tách kênh), khôi phục lại tín hiệu gốc rồi đưa vào các đầu cuối khác nhau. 1.1.2. Các công nghệ dùng trong mạng thông tin quang. Phần này sẽ trình bày về các công nghệ đã, đang và sẽ được dùng trong hệ thống thông tin quang. 1.1.2.1. TDM (Time Division Multiplexing): TDM là phương pháp ghép kênh phân chia theo thời gian. Đây là phương pháp giúp tăng số lượng tín hiệu được gửi trên đường truyền vật lý. Hình 1.1 : Ghép kênh theo thời gian 3 1.1.2.2. SONET/SDH: SONET (Sychronous Optical Network : Mạng quang đồng bộ) là một chuẩn của American National Standards Institute để truyền dữ liệu đồng bộ trên môi trường truyền là cáp sợi quang. Tương đương với SONET về mặt quốc tế là SDH. SONET/SDH lấy các luồng n bit, ghép chúng lại, điều chế quang tín hiệu và sử dụng thiết bị phát quang để gửi nó ra ngoài với một tốc độ bit tương đương với : (tốc độ bit đi vào)  n . Vì vậy lưu lượng đi đến bộ ghép kênh SONET tù bốn đầu vào với tốc độ 2,5 Gbps sẽ đi ra như một luồng đơn ở tốc độ 4  2,5 Gbps = 10 Gbps. Nguyên tắc này được minh họa trong hình 1.2. Hình 1.2 : Nguyên tắc ghép kênh trong mạng SONET SONET cung cấp các chuẩn cho một số lượng lớn các tốc độ truyền (tốc độ truyền thực tế vào khoảng 20 Gbps). 1.1.2.3. Gigabit Ethernet: Công nghệ Ethernet 10 Gigabit được xây dựng trên nghi thức Ethernet, nhưng có tốc độ nhanh gấp 10 lần Ethernet (1000 Mbps). Ethernet Gigabit được triển khai như một công nghệ xương sống cho các mạng đô thị. Đối với mạng diện rộng WAN, Ethernet 10 Gigabit cho phép các ISP (Internet Service Provider) và NSP (Network Service Provider) tạo ra các liên kết tốc độ rất cao với giá thành thấp từ các bộ chuyển mạch và các bộ định tuyến trong phạm vi công ty cho đến thiết bị quang gán trực tiếp vào SONET/SDH. Công nghệ Ethernet Gigabit hỗ trợ cả cáp sợi quang đơn mode và đa mode. Tuy vậy, các khoảng cách được hỗ trợ tùy vào các kiểu cáp sợi quang và bước sóng được thực thi trong ứng dụng. 1.1.3. Hệ thống thông tin quang nhiều kênh Trên thực tế, sự ra đời của các hệ thống quang đa kênh đã giải quyết được những hạn chế của hệ thống đơn kênh, đồng thời cũng tận dụng được những công nghệ hiện có để phát triển mạnh mẽ. Cụ thể là : Thứ nhất, đối với hệ thống đơn kênh, khi tốc độ đạt tới mức khoảng vài chục Gbit/s thì khoảng cách tuyến truyền dẫn sẽ bị rút ngắn lại, các thiết bị điện tử sẽ đạt đến giới hạn của nó và không đáp ứng được các xung tín hiệu cực kì hẹp; thêm vào đó chi phí dành cho các giải pháp trên tuyến truyền dẫn trở nên tốn kém vì cấu trúc, thuật toán phức tạp và đòi hỏi các thiết bị có công nghệ cao. Thứ hai, kỹ thuật ghép kênh quang được sử dụng sẽ tận dụng được phổ hẹp của Laser, tận dụng được băng tần rất lớn của sợi quang. 1.1.4. Nguyên lý cơ bản của ghép kênh theo bước sóng quang. Nguyên lý cơ bản của ghép kênh theo bước sóng mang có thể minh họa như hình 1.3. Hình 1.3 : Quá trình ghép và giải ghép WDM 4 1.1.5. Mục đích công nghệ WDM. Do băng thông quang rất lớn nên nếu chỉ sử dụng cho mục đích đơn lẻ sẽ rất hao phí. Vì vậy sử dụng công nghệ WDM nhằm mục đích tận dụng băng tần truyền dẫn của sợi quang bằng cách truyền đồng thời nhiều kênh bước sóng trên cùng một sợi quang. 1.1.6. Phân loại hệ thống truyền dẫn WDM. 1.1.6.1. Hệ thống ghép bước sóng đơn hướng: Chỉ thực hiện truyền theo một chiều trên sợi quang. Do vậy để truyền thông tin giữa hai điểm cần hai sợi quang. Hình 1.4: Hệ thống WDM đơn hướng 1.1.6.2. Hệ thống ghép bước sóng song hướng: Có thể truyền theo hai chiều trên một sợi quang nên chỉ cần một sợi quang để có thể trao đổi thông tin giữa hai điểm. Hình 1.5: Hệ thống WDM song hướng 1.2. Định tuyến và gán bước sóng trong mạng WDM. 1.2.1. Định tuyến (Routing) 1.2.1.1. Giới thiệu Định tuyến được coi là thành phần cốt yếu của kiến trúc mạng, thiết kế mạng và điều hành mạng của mọi mạng thông tin, là thành phần không thể thiếu trong mạng viễn thông. 1.2.1.2. Phân loại định tuyến Có nhiều cách phân loại định tuyến, có thể đưa ra một số loại định tuyến như sau:  Dựa vào chức năng thích nghi với trạng thái hiện thời của mạng để phân loại thành: định tuyến tĩnh và định tuyến động + Định tuyến tĩnh: với định tuyến tĩnh, đường dẫn được chọn trước cho mỗi cặp nguồn – đích của các node trong mạng. + Định tuyến động: định tuyến động lựa chọn tuyến dựa trên thông tin trạng thái hiện thời của mạng.  Dựa vào phạm vi định tuyến, ta phân loại thành: định tuyến trong và định tuyến ngoài. Định tuyến trong: định tuyến xảy ra bên trong một hệ thống độc lập (AS – Autonomous System), các giao thức thường dùng là RIP (Router Information Protocol), IGRP (Interior Gateway Routing Protocol), OSPF (Open Shortest Path First), EIGRP (Enhanced IGRP),… Định tuyến ngoài: định tuyến xảy ra giữa các hệ thống độc lập (AS), liên quan tới dịch vụ của nhà cung cấp mạng sử dụng giao thức định tuyến ngoài rộng và phức tạp. Giao thức thường dùng là BGP (Border Gateway Protocol). 5 Hình 1.6: Định tuyến trong và định tuyến ngoài 1.2.2. Định tuyến và gán bước sóng (Routing and Wavelength Assignment - RWA). Tìm đường được hiểu theo hai khía cạnh, đó là tìm đường vật lí mang được mẫu lưu lượng yêu cầu (Routing) và đưa ra bước sóng phù hợp để mang lưu lượng trên mỗi link dọc path (Wavelength Assignment) trong số các bước sóng cho phép (bởi mỗi path gồm một số fiber, mà trên mỗi fiber này, bạn có thể có W sub-chanels, cũng là W bưóc sóng và W lựa chọn cho yêu cầu kết nối hiện tại). Vấn đề này được viết tắt là RWA. Rắc rối đặt ra đối với bài toán RWA là nó đưa ra hai điều kiện sau: Điều kiện tính liên tục bước sóng: một lightpath phải sử dụng chung một bước sóng trên tất cả các link dọc theo đường đi của nó từ nguồn đến đích. Hình 1.7: Điều kiện tính liên tục bước sóng Điều kiện tính riêng biệt về bước sóng: tất cả các lightpath sử dụng cùng một link (fiber) phải được gán các bước sóng riêng biệt. Hình 1.8: Mạng WDM định tuyến bước sóng 1.3. Động cơ và mục tiêu nghiên cứu. 1.3.1. Động Cơ Để giải bài toán thiết kế đa mục tiêu, các kỹ thuật tối ưu hóa đa mục tiêu thường được sử dụng. Một số phương pháp sử dụng các gần đúng đơn mục tiêu để giải các bài toán đa mục tiêu như ràng buộc  và tổng trọng số. Tuy nhiên các gần đúng đơn mục tiêu có một nhược điểm là rất khó tìm được các nghiệm tối ưu. Do vậy mà các thuật toán tiến hóa đa mục tiêu được áp dụng để giải các bài toán thiết kế đa mục tiêu này. 1.3.2. Mục tiêu nghiên cứu Nghiên cứu giải quyết bài toán định tuyến và gán bước sóng đa mục tiêu trong mạng WDM bao gồm: + Xây dựng bài toán RWA như là một bài toán tối ưu đa mục tiêu. 6 + Giải bài toán RWA được xây dựng ở trên bằng thuật toán di truyền để tối ưu hóa các tham số mạng khác nhau. 1.4. Nội dung và đóng góp của luận văn. 1.4.1. Nội dung của luận văn Nội dung của luận văn dự kiến sẽ được chia thành 4 chương với những nội dung cụ thể như sau: Chương 1: Trình bày tổng quan về mạng WDM, các vấn đề cơ bản về định tuyến và gán bước sóng trong mạng WDM, nhiệm vụ, hướng nghiên cứu và những đóng góp của luận văn. Chương 2: Giới thiệu bài toán RWA, các mục tiêu thiết kế, các phương pháp tiếp cận bài toán RWA: heuristic và meta- heuristic. Chương 3: Trình bày bài toán tối ưu hóa đa mục tiêu, các giải thuật tiến hóa trong tối ưu hóa đa mục tiêu, các giải thuật di truyền trong RWA đa mục tiêu. Chương 4: Trình bày mô hình mô phỏng RWA đa mục tiêu, cách thức giải bài toán RWA đa mục tiêu bằng phương pháp tính toán tiến hóa lai và kết quả mô phỏng bài toán RWA. 1.4.2. Những đóng góp của luận văn. Kết quả của đề tài có thể ứng dụng cho thiết kế mạng quang định tuyến bước sóng WDM hiệu quả hơn. Bằng việc sử dụng tiếp cận đa mục tiêu thay cho chỉ xem xét từng mục tiêu một cách độc lập, nghiệm thu được trong việc giải bài toán RWA bằng phương pháp tiến hóa lai cho kết quả khả thi tốt hơn, hay nói cách khác nó cung cấp cho nhà thiết kế mạng những thông tin bù trừ bổ ích giữa nhiều mục tiêu khác nhau. Hơn nữa các thuật toán tiến hóa được nghiên cứu có thể áp dụng cho việc điều khiển mạng quang định tuyến bước sóng động một cách hiệu quả hơn. Đề tài cũng làm cơ sở định hướng nghiên cứu cho các đề tài tốt nghiệp của sinh viên đại học và cho các nghiên cứu chuyên sâu tiếp theo đối với sinh viên cao học. CHƯƠNG 2:ĐỊNH TUYẾN VÀ GÁN BƯỚC SÓNG TRONG MẠNG WDM 2.1. Giới thiệu bài toán RWA. Phân loại bài toán RWA được thể hiện trong Bảng 2.1. Bảng 2.1: Phân loại RWA Phân loại RWA Kiểu lưu lượng Static,Dynamic Hàm mục tiêu Max-RWA,Min-RWA Công thức ILP Link-based, Path-based Chuyển đổi bước sóng Full,Sparse,None Cáp quang Single,Multiple Yêu cầu Request multiplicity RWA bài toán được coi là một bài toán NP-đầy đủ. Phức tạp của bài toán RWA phát sinh từ hai sự kiện sau đây: (i) Ràng buộc bước sóng liên tục : Một lightpath phải chiếm cùng bước sóng trên tất cả các sợi liên kết mà qua đó nó đi qua. (ii) Ràng buộc bước sóng riêng biệt: Hai lightpaths phải không được chỉ định cùng một bước sóng trên một liên kết nào. 7 2.2. Cách tiếp cận heuristic đối với bài toán RWA. Chlamtac[8] đề xuất khái niệm về Lightnet kiến trúc để đối phó với các vấn đề không phù hợp giữa tốc độ xử lý điện tử và truyền dẫn quang băng thông trong WDM dựa trên các mạng diện rộng. Zhang và Acampora[26] đã đề xuất một thuật toán hiệu quả để gán một số giới hạn các bước sóng giữa các trạm truy cập của mạng trong đó các phương tiện vật lý bao gồm các phân đoạn sợi quang được kết nối qua các thiết bị chuyển mạch bước sóng quang chọn lọc. Banerjee [4] đã xem xét các vấn đề thiết kế một cấu trúc liên kết mạng quang học hợp lý cho một mô hình vật lý và một ma trận nhu cầu giao thông giữa những người sử dụng cuối cùng. Banerjee và Mukherjee[2] đã trình bày một công thức lập trình tuyến tính số nguyên để đưa ra một giải pháp tối thiểu khoảng cách bước nhảy đến các vấn đề thiết kế cấu trúc liên kết ảo trong một mạng bước sóng định tuyến quang học, trong trường hợp không có ràng buộc bước sóng liên tục. 2.3. Cách tiếp cận meta-heuristic đối với bài toán RWA. Các giải pháp meta Heuristic thiết kế các cấu trúc liên kết trong khu vực mạng mesh diện rộng để giảm thiểu chi phí mạng. Các thuật toán di truyền đã được sử dụng để giải quyết bài toán RWA theo giả định khác nhau. Các tác giả đã xây dựng các vấn đề RWA tĩnh trong các mạng quang học là một vấn đề tối ưu hóa mục tiêu duy nhất và giải quyết nó bằng cách sử dụng một thuật toán tiến hóa. MC Sinclair[23] đã đề xuất một chi phí tối thiểu định tuyến đường đi bước sóng và phương án phân bổ bước sóng bằng cách sử dụng một thuật toán di truyền / Heuristic dựa trên thuật toán lai ghép. Zhong Pan [21] phát triển một chức năng phù hợp mới để giải quyết các bài toán con của của bài toán RWA bằng cách sử dụng thuật toán di truyền. Mục tiêu là để định tuyến mỗi lightpath theo cách để giảm thiểu số lượng bước sóng cần thiết để nhường quyền tất cả các lightpaths tĩnh. Các mục tiêu thứ yếu là giảm thiểu chi phí trong việc thiết lập các lightpaths. D. Bisbal[5] đề xuất một thuật toán di truyền để thực hiện định tuyến động và gán bước sóng trong định tuyến bước sóng mạng quang không có bước sóng chuyển đổi. Le[15] đã đề xuất một thuật toán di truyền cải tiến để giải quyết bài toán RWA động. Để đạt được cân bằng tải tốt hơn giữa các cá thể, họ đã xây dựng một hàm thích hợp mới, đồng thời liên quan đến chiều dài đường đi, số bước sóng tự do và khả năng chuyển đổi bước sóng trong tuyến đường đánh giá. 2.4. Các mục tiêu thiết kế trong bài toán RWA. Bài toán thiết kế đa mục tiêu được thể hiện với các hàm đa mục tiêu thường được giải quyết với "kỹ thuật tối ưu hóa đa mục tiêu". Tối ưu hóa đa mục tiêu là một kỹ thuật để tìm ra giải pháp tốt nhất từ các giải pháp lớn có thể xem xét tất cả các mục tiêu cùng một lúc. Có một số nghiên cứu[20] được lồng ghép trong các tài liệu mà hình thành heuristics và meta-heuristics cho việc thiết kế hiệu quả của biểu đồ tổng quát dựa trên các cấu trúc liên kết mạng. CHƯƠNG 3: MÔ HÌNH ĐA MỤC TIÊU CHO BÀI TOÁN RWA 8 3.1. Xây dựng bài toán đa mục tiêu. Bài toán RWA là một bài toán tối ưu hóa tổ hợp và một loạt các phương pháp tối ưu đã được sử dụng để giải quyết bài toán này. Các bài toán RWA có thể được mô hình hóa như một bài toán lập trình số nguyên tuyến tính (ILP) và giải quyết ILP được đảm bảo để cung cấp cho các tối ưu toàn phần 3.1.1. ký hiệu sử dụng. Ký hiệu được sử dụng trong việc xây dựng ILP được quy định như sau: + V = Thiết lập các nút trong mạng. + E = Thiết lập các liên kết sợi hai chiều trong mạng. + W = Thiết lập các kênh bước sóng không nhiễu hỗ trợ bởi tất cả các liên kết sợi trong mạng. + (i,j) Là cặp nút nguồn-đich; {i,j}  V. + D = Ma trận nhu cầu của các yêu cầu kết nối, nơi Dij dùng để chỉ một giá trị đầy đủ ghi rõ nhu cầu tối đa giữa các cặp nút (i, j) và Dij = Dji. + -(v) = Thiết lập các liên kết sợi được sử dụng bởi lightpath vào nút v. + +(v) = Thiết lập các liên kết sợi được sử dụng bởi lightpath rời khởi nút v. 3.1.2. Các biến sử dụng Các biến được sử dụng trong việc xây dựng ILP được quy định như sau: 3.1.3. Xây dựng ILP đa mục tiêu. Trong phần này, xây dựng các bài toán RWA như là một bài toán đa mục tiêu ILP. Lightpaths được nhóm lại theo cặp nút nguồn-đích của nó. K là tập hợp các yêu cầu lightpath. Thì K được tính theo công thức: jiandijKjiKjiKK VVji    ),( |),(),();,( 2     Vi Vj ijD K jiij DDijKjiK  ),(),( 3.1 Các hàm mục tiêu mà chúng ta muốn tối ưu hóa được quy định như sau: + Giảm thiểu ách tắc của nhiều nhất liên kết tắc nghẽn trong mạng:        0:),( ),( , ),(max ijDVVji jiKk Ww ew k Ee jibMinimize (3.4) Bk(i,j) = 1 nếu lightpath k giữa cặp nút (i, j) được thiết lập 0 nếu không ),( jiBk  1 nếu lightpath k giữa cặp nút (i, j) được thiết lập bước sóng w 0 nếu không ),(, jiB ek  (i,j) = 1 nếu lightpath k giữa cặp nút (i, j) được thiết lập bước sóng w với liên kết e 0 nếu không 9 + Giảm thiểu sự khác biệt giữa tắc nghẽn nhiều nhất và tắc nghẽn ít nhất liên kết trong mạng:               0:),( ),( 0:),( ),( ,, }),(min),(max{ ij ijDVVji jiKk DVVji jiKk Ww ew k Ee Ww ew k Ee jibjibMin (3.5) + Giảm thiểu sự khác biệt giữa các liên kết tắc nghẽn nhiều nhất và ùn tắc trung bình của tất cả các liên kết trong mạng: Min { E jib jib ij ij DVVji jiKk Ww ew k DVVji jiKk Ww ew k Ee               0:),( ),( , 0:),( ),( , ),( ),(max } (3.6) + Hạn chế số lượng tối đa của bước nhảy đi qua trung gian:     Ee Ww ew k jiKk jibMinimize ijDji ),(max , ),( 0:),(  (3.7) + Giảm thiểu số lượng các liên kết sợi được sử dụng để cho tất cả các lightpaths:        0:),( ),( , }0),(|{ ijDji jiKk Ww ew k jibEeMinimize (3.8) + Hạn chế chiều dài tuyến đường tối đa:       Ee Ww ew ke jiKk jibdMinimize ijDji 0),(|(max , ),( 0:),(  (3.9) Trong đó de = Trễ liên quan đến liên kết e. + Hạn chế tối đa tổng chiều dài tuyến đường:          0:),( ),( , )0),(|( ijDji jiKk Ee Ww ew ke jibdMinimize (3.10) 3.2. Các giải thuật tiến hóa trong tối ưu hóa đa mục tiêu. 3.2.1. Thuật toán đáp ứng tiến hóa. EA là một thủ tục lặp ngẫu nhiên để tạo ra các nghiệm thăm dò cho một bài toán P nào đó. Thuật toán điều khiển một bộ sưu tập P của các cá nhân (quần thể), một trong số đó bao gồm một hoặc nhiều nhiễm sắc thể. Các nhiễm sắc thể này cho phép mỗi cá nhân đại diện cho một nghiệm tiềm năng cho các bài toán đang được xem xét. Toàn bộ quá trình được phác thảo trong hình 3.1. Hình 3.1: Tác giả của phương pháp tiến hóa để tối ưu hóa. Thuật toán tiến hóa như sau: 1. P ← áp dụng ι trên G để có được các cá nhân μ (quản thể ban đầu); 10 2. while Tiêu chuẩn kết cuối