TỐI ƯU ĐA MỤC TIÊU VÀ CÁC GIẢI THUẬT TIẾN HÓA ĐA MỤC TIÊU

TỐI ƯU ĐA MỤC TIÊU VÀ CÁC GIẢI THUẬT TIẾN HÓA ĐA MỤC TIÊU

1. Tối ưu đa mục tiêu

Một lời giải khả thi (feasible solution) x được gọi là vượt trội (dominate) lời giải y (x  y), nếu và chỉ nếu, z_i(x) ≤ z_i(y) (i=1,…, K) và z_j(x) < z_j(y) ở ít nhất một mục tiêu j. Một lời giải được nói là tối ưu Pareto (Pareto optimal) nếu nó không bị vượt trội bởi một lời giải nào trong không gian lời giải. Tập tất cả các lời giải khả thi không bị vượt trội trong X được gọi là tập tối ưu Pareto (Pareto optimal set). Với tập tối ưu Pareto đã cho, các giá trị hàm mục tiêu tương ứng trong không gian mục tiêu được gọi là Pareto Front.

Mục tiêu của các giải thuật tối ưu đa mục tiêu là xác định các lời giải trong tập tối ưu Pareto. Thực tế, việc chứng minh một lời giải là tối ưu thường không khả thi về mặt tính toán. Vì vậy, một tiếp cận thực tế với bài toán tối ưu đa mục tiêu là tìm kiếm tập các lời giải là thể hiện tốt nhất có thể của tập tối ưu Pareto, một tập các lời giải như vậy được gọi là tập Pareto được biết tốt nhất (Best-known Pareto set).

Với mối bận tâm nêu trên, cách tiếp cận tối ưu hóa đa mục tiêu cần thực hiện tốt ba tiêu chí mâu thuẫn nhau sau đây:

1. 
   Tập Pareto-được-biết-tốt-nhất nên là một tập con của tập Pareto tối ưu.
   
2. 
   Những lời giải trong tập Pareto-được-biết-tốt-nhất nên phân bố đều và đa dạng trên Pareto front để cung cấp cho người ra quyết định một hình ảnh về sự đánh đổi qua lại giữa các mục tiêu.
   
3. 
   Pareto front-được-biết-tốt-nhất phải biểu thị toàn cảnh của Pareto front.
   

2. Các giải thuật tiến hóa đa mục tiêu

Giải thuật MOEA đầu tiên được biết là Vector Evaluated Genetic Algorithm (VEGA) được đề nghị bởi Schaffer, 1985 [9]. Sau đó, nhiều MOEA khác đã được phát triển bao gồm Multi-objective Genetic Algorithm (MOGA) bởi Fonseca và Fleming, năm 1993 [10], Niched Pareto Genetic Algorithm (NPGA) bởi Horn và các cộng sự, năm 1994 [11], Weight-Based Genetic Algorithm (WBGA) bởi Hajela và Lin, năm 1992 [12], Random Weight Genetic Algorithm (RWGA) bởi Murata và Ishibuchi, năm 1995 [13], Nondominated Sorting Genetic Algorithm (NSGA) bởi Srinivas và Deb, năm 1994 [14], Strength Pareto Evolutionary Algorithm (SPEA) bởi Zitzler và Thiele năm 1999 [15], SPEA cải tiến (SPEA2) bởi Zitzler và các cộng sự năm 2001 [16], Pareto-Archived Evolution Strategy (PAES) bởi Knowles và Corne năm 2000 [17], Pareto Enveloped-based Selection Algorithm (PESA) bởi Corne và các cộng sự năm 2000 [18], Region-based Selection in Evolutionary Multiobjective Optimization (PESA-II) bởi Corne và các cộng sự năm 2001 [19], Fast Non-dominated Sorting Genetic Algorithm (NSGA-II) bởi Deb và các cộng sự năm 2002 [20], Rank-Density Based Genetic Algorithm (RDGA) bởi Lu và Yen năm 2003 [21] và Dynamic Multi-Objective Evolutionary Algorithm (DMOEA) Yen và Lu năm 2003 [22].

Điểm khác biệt giữa các giải thuật MOEA nằm ở cách gán độ thích nghi (fitness assignment), cách duy trì quần thể ưu tú (elitism) và các tiếp cận nhằm đa dạng hóa quần thể ([23]).

Một phương pháp hay dùng để gán độ thích nghi là xếp hạng Pareto (Pareto ranking) được mô tả sau đây.

 Xếp hạng Pareto

Phương pháp này bao gồm việc gán thứ hạng 1 cho các cá thể không bị vượt trội trong quần thể và đưa chúng ra ngoài vòng xem xét; rồi tìm tập cá thể không bị vượt trội mới để gán thứ hạng 2 và tiếp tục như vậy.

Một phương pháp hay dùng để đa dạng hóa quần thể là chia sẻ độ thích nghi (fitness sharing). Phương pháp chia sẻ độ thích nghi khuyến khích tìm kiếm trên những vùng chưa được thăm dò của Pareto front bằng cách giảm bớt độ thích nghi của các lời giải ở những vùng cá thể mật độ cao. Kỹ thuật chia sẻ độ thích nghi với số đếm vùng lân cận (niche count) được mô tả như sau.

 Chia sẻ độ thích nghi dựa vào số đếm vùng lân cận.

Phương pháp này đòi hỏi phải giảm bớt độ thích nghi f_i của một cá thể i bằng cách chia nó cho số đếm vùng lân cận m_i được tính cho cá thể đó. Tức là độ thích nghi dùng chung được tính bằng f_i/m_i. Số đếm vùng lân cận m_i là giá trị ước lượng vùng lân cận của cá thể i đông đúc như thế nào. Nó được tính cho từng cá thể trong quần thể hiện hành theo công thức: m_i = _jPop Sh[d[i, j]], với d[i, j] là khoảng cách Euclid giữa hai cá thể i và j và Sh[d] là hàm chia sẻ (sharing function). Sh[d] là một hàm của d[i, j] sao cho Sh[0] = 1 và Sh[d  _share] = 0. Thông thường Sh[d] = 1-d/_share với d  _share và Sh[d] = 0 với d  _share. Ở đây _share là bán kính vùng lân cận, được người dùng xác định để ước lượng độ cách biệt tối thiểu mong muốn giữa hai lời giải cuối cùng. Các cá thể có khoảng cách trong phạm vi _share bị giảm bớt độ thích nghi vì chúng ở trong cùng vùng lân cận.

Một phương pháp đa dạng hóa quần thể khác không phải xác định thông số _share là dùng khoảng cách mật độ (crowding distance) mà được mô tả sơ lược như sau.

 Phương pháp dùng khoảng cách mật độ

Phương pháp này đòi hỏi tính khoảng cách mật độ là giá trị ước lượng mật độ lời giải bao quanh một điểm được xét i trong quần thể. Đại lượng này là giá trị trung bình của hai điểm lấy hai bên của điểm được xét i dọc theo mỗi trục mục tiêu. Đại lượng này được dùng trong cơ chế chọn cha mẹ như sau: lấy ngẫu nhiên hai lời giải x và y; nếu chúng có cùng mức không vượt trội (non-domination rank) thì lời giải nào có khoảng cách mật độ cao hơn sẽ được chọn; ngược lại lời giải có mức không vượt trội thấp hơn sẽ được chọn.

Ngoài ra, việc duy trì quần thể ưu tú là một vấn đề quan trọng trong tối ưu hóa đa mục tiêu bằng giải thuật MOEA. Trong ngữ cảnh của giải thuật MOEA, tất cả những lời giải không bị vượt trội được phát hiện bởi MOEA được coi như là những lời giải ưu tú. Có hai chiến lược thường dùng để hiện thực việc duy trì quần thể ưu tú: (i) lưu trữ các lời giải ưu tú trong chính quần thể và (ii) lưu trữ các lời giải ưu tú trong một danh sách thứ cấp bên ngoài quần thể và đưa chúng trở lại quần thể.

Đặc điểm của một số giải thuật MOEA tiêu biểu nhất được mô tả sơ lược như sau:

 VEGA

Gán độ thích nghi: quần thể được phân thành K tiểu quần thể (K là số mục tiêu). Các cá thể trong mỗi tiểu quần thể được đánh giá theo một mục tiêu riêng.

Cơ chế đa dạng hóa: không có.

Cách duy trì quần thể ưu tú: không có.

 MOGA

Gán độ thích nghi: dùng cách xếp hạng Pareto (Pareto ranking).

Cơ chế đa dạng hóa: chia sẻ độ thích nghi (fitness sharing) dùng số đếm vùng lân cận.

Cách duy trì quần thể ưu tú: không có.

 NSGA

Gán độ thích nghi: xếp hạng dựa vào sắp thứ tự mức độ không vượt trội (non-domination sorting).

Cơ chế đa dạng hóa: chia sẻ độ thích nghi (fitness sharing) dùng số đếm vùng lân cận.

Cách duy trì quần thể ưu tú: không có.

NSGA-II

Gán độ thích nghi: xếp hạng dựa vào sắp thứ tự mức độ không vượt trội (non-domination sorting).

Cơ chế đa dạng hóa: phương pháp dùng khoảng cách mật độ (crowding distance).

Cách duy trì quần thể ưu tú: có.

 SPEA

Gán độ thích nghi: xếp hạng dựa vào kho lưu ngoài (external archive) của những lời giải không bị vượt trội.

Cơ chế đa dạng hóa: gom cụm (clustering) để tỉa bớt quần thể ngoài (external population).

Cách duy trì quần thể ưu tú: có.

 SPEA-2

Gán độ thích nghi: dựa vào sức mạnh của các cá thể vượt trội (dominator).

Cơ chế đa dạng hóa: dùng mật độ dựa vào láng giềng gần nhất thứ k.

Cách duy trì quần thể ưu tú: có.

Độc giả có quan tâm đến các giải thuật MOEA tiêu biểu khác, có thể tham khảo bài tổng quan về MOEA khá đầy đủ của Konak và các cộng sự, 2006 ([23]).

4. PHƯƠNG PHÁP GIẢI CHO BÀI TOÁN THIẾT KẾ TỐI ƯU MẠNG VIỄN THÔNG

Một cách tổng quát, việc thiết kế mạng bao gồm việc tìm mô hình mạng và xác định lưu lượng cho các đường liên kết. Trong đó, mô hình mạng cần tìm phải liên thông và thỏa ràng buộc về bậc của nút; lưu lượng cho các đường liên kết phải bảo đảm có tổng lưu lượng cung cấp cho từng cặp nguồn - đích bằng với giá trị lưu lượng yêu cầu, cũng như thỏa các ràng buộc về độ trễ, dung lượng nút mạng, dung lượng liên kết và giới hạn số trạm trung gian. Theo hướng tiếp cận của nghiên cứu này, giải thuật tiến hóa có nhiệm vụ tìm mô hình mạng. Với mỗi nhiễm sắc thể, tức mô hình mạng đã tìm được, giải thuật Monte Carlo được sử dụng để xác định độ tin cậy và giải thuật qui hoạch tuyến tính được sử dụng để ấn định lưu lượng tối ưu cho các đường liên kết, từ đó tính ra được chi phí truyền tải của từng mô hình. Một giải thuật sửa chữa cũng được sử dụng với các mô hình mạng không đáp ứng được ràng buộc về độ trễ gói cực đại cho phép (r11).

1. Biểu diễn nhiễm sắc thể

Một đồ thị bất kỳ có thể được biểu diễn duy nhất bằng một ma trận kề nút-nút. Các phần tử của ma trận nhận các giá trị trong khoảng [0, t] tương ứng với loại liên kết (=0 tương ứng với không có liên kết) giữa từng cặp nút hàng-cột. Vì các liên kết là hai chiều, nên chỉ cần xét phần tam giác trên của ma trận. Chọn một thứ tự đọc ma trận tùy ý (ở đây ta chọn đọc theo thứ tự từ trái sang phải, từ trên xuống dưới), ma trận có thể được chuyển thành vectơ mà không làm mất thông tin (xem Hình 1).

0	3	0	2	0	0	0	0	0
0	0	1	0	3	0	0	0	0
0	0	0	0	0	4	0	0	0
0	0	0	0	0	0	1	0	0
0	0	0	0	0	0	0	2	0
0	0	0	0	0	0	0	0	3
0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0

  

  

  


302000001030000004000001000020003000

Hình 1. Ví dụ biểu diễn của một nhiễm sắc thể (t = 4)

Tổng quát, nếu n là số nút trong đồ thị, thì chiều dài nhiễn sắc thể là: n(n-1)/2 và không gian tìm kiếm của bài toán là:

2. 
   
   Каталог: download -> version
   version -> Nhật Bản Đất nước mặt trời mọc (Phần 1) Lịch sử Nhật Bản
   version -> CÁc hàm thông dụng các hàm tóan học (math & trig)
   version -> ĐỀ CƯƠng kt hoc ky 1 khốI 10 2013-2014
   version -> CHƯƠng II: TỔng quan về ĐẦu tư quốc tế Khái niệm và đặc điểm của đầu tư quốc tế
   version -> BÊn thắng cuộC – chưƠng III: ĐÁnh tư SẢN
   version -> Nhà Tây Sơn
   version -> United States of America Hợp chúng quốc Hoa Kỳ
   version -> Hiệp hội các Quốc gia Đông Nam Á tiếng Anh: Association of Southeast Asia Nations, viết tắt là asean
   version -> BÊn thắng cuộC – chưƠng IX: XÉ RÀO
   
   
   
   tải về 0.98 Mb.
   
   Chia sẻ với bạn bè của bạn: