本文最早發(fā)表于本人博客：http://www.gotoli.us/?p=1773
很多優(yōu)化問題是多目標(biāo)優(yōu)化問題，目標(biāo)之間一般都是互相沖突的较木。比如在公路路線設(shè)計中脆侮，需要兼顧至少兩個目標(biāo)：1）路線經(jīng)過多的居民點她奥，方便大家出行敷硅，2）路線盡量少經(jīng)過居民點附近，減少土地征用和房屋拆遷費用鞠值。在遺傳算法出現(xiàn)之后媚创，有人提出了各種方法將遺傳算法應(yīng)用于多目標(biāo)優(yōu)化。多目標(biāo)遺傳算法按照選擇方法可以分為兩種類型：基于線性加權(quán)和基于Pareto排序彤恶。
1）基于線性加權(quán)的多目標(biāo)遺傳算法
這種算法的思路很簡單钞钙，將多目標(biāo)按照線性加權(quán)的方式轉(zhuǎn)化為單目標(biāo)，然后應(yīng)用傳統(tǒng)遺傳算法求解声离，如下公式所示
其中w_i表示第i個目標(biāo)的權(quán)重芒炼，f_k表示歸一化之后的第i個目標(biāo)值。我們很容易知道术徊，這類方法的關(guān)鍵是怎么設(shè)計權(quán)重本刽。比如，Random Weight Genetic Algorithm (RWGA) 采用隨機權(quán)重的方式赠涮，每次計算適應(yīng)度都對所有個體隨機地產(chǎn)生不同目標(biāo)的權(quán)重子寓，然后進行選擇操作。 Vector-Evaluated Genetic Algorithm (VEGA) 也是基于線性加權(quán)的多目標(biāo)遺傳算法笋除。如果有K個目標(biāo)斜友，VEGA 會隨機地將種群分為K個同等大小子種群，在不同的子種群按照不同的目標(biāo)函數(shù)設(shè)定目標(biāo)值垃它，然后再進行選擇操作鲜屏。VEGA 實質(zhì)上是基于線性加權(quán)的多目標(biāo)遺傳算法。VEGA 是第一個多目標(biāo)遺傳算法国拇，開啟了十幾年的研究潮流洛史。
2）基于Pareto排序的多目標(biāo)遺傳算法
基于線性加權(quán)的多目標(biāo)遺傳算法給大家的感覺怪怪的，并不是真正多目標(biāo)優(yōu)化的實質(zhì)酱吝。那么什么是真正的多目標(biāo)優(yōu)化也殖。Pareto 在1986 年提出 Pareto 支配概念，其定義為：假設(shè)兩個解決方案 I1 和 I2务热，對所有目標(biāo)而言毕源，I1 均優(yōu)于 I2，則我們稱 I1 支配I2陕习。若 I1 沒有被其他解所支配霎褐，則 I1 稱為 Pareto 解。Pareto 解的集合被稱為Pareto front该镣。真正的多目標(biāo)優(yōu)化應(yīng)該求解出Pareto front冻璃，選擇Pareto front中的解應(yīng)該提交人工解決。基于Pareto 排序的多目標(biāo)遺傳算法便是致力求解出 Pareto front省艳。Multi Objective Genetic Algorithm (MOGA)娘纷、 Non -dominated Sorting Genetic Algorithm (NSGA) 和 improved Non-dominated Sorting Genetic Algorithm (NSGA-II) 都是常用的基于 Pareto 排序的多目標(biāo)遺傳算法。
基于 Pareto 排序的多目標(biāo)遺傳算法首先要解決的是適應(yīng)度函數(shù)設(shè)計問題跋炕。MOGA 采用的適應(yīng)度函數(shù)fitness(I) = 1 + nq(I)赖晶，其中nq(I)表示被個體 I 支配的個體數(shù)量。NSGA 和 NSGA-II 再采用另外一種計算適應(yīng)度函數(shù)的方法
step 1: 令i=1
step 2: 在種群 P 中找到所有不支配其他個體的個體辐烂，將它們的適應(yīng)度設(shè)為i遏插；
step 3: 令i = i + 1
step 4: 將step2中找到的個體從種群刪除。如果種群不為空纠修，則重新從step2開始執(zhí)行胳嘲；否則結(jié)束。
上面兩種適應(yīng)度函數(shù)都能夠挖掘種群中 Pareto 支配關(guān)系扣草，效果如下圖所示(左邊的圖表示 NSGA 和 NAGA-II 的適應(yīng)度函數(shù)了牛，右邊的圖是 MOGA 的適應(yīng)度函數(shù))。
基于Pareto排序的多目標(biāo)遺傳算法還有另一個關(guān)鍵點：我們要找的是 Pareto 解的集合辰妙，而不是一個 Pareto 解鹰祸，因此我們需要鼓勵多樣性。不同算法有不同鼓勵多樣性的手段密浑。MOGA 和 NSGA 采用的多樣性方法被稱為 fitness sharing 蛙婴。fitness sharing 方法首先用下面的公式計算不同個體之間的距離。
其中f_k{max}表示目前找到的最大k目標(biāo)值肴掷，同理可知f_k{min}敬锐。對于個體 I 背传，我們可以計算它的 niche count (求高手翻譯呆瞻，這個是啥玩意？)
再用個體的 niche count 調(diào)整個體的適應(yīng)度
NSGA-II采用的是另一種被稱為 crowding distance 的方法径玖。個體 I 的crowding distance 用 cd(I) 表示痴脾。適應(yīng)度值為i的個體用集合F_i表示。對于每個集合F_i梳星，我們執(zhí)行如下操作：
step 1:對于每一個目標(biāo)k, 我們按照目標(biāo)值從小到大將集合F_i中個體排序赞赖；
step 2:假設(shè)集合 F_i 中個體有l(wèi)個，則cd_k(I(1,k))和cd_k(I(l,k))等于無限冤灾，其他
其中 I[i,k]表示按照第k個目標(biāo)值排在第i位的個體前域。
step 3:計算cd(I) = \sum_{k=1}^{K}cd_k(I)。
計算得到每個個體的 crowding distance 之后韵吨，我們不用它去調(diào)整適應(yīng)度匿垄，而是用了一種別樣的選擇方法。我們隨機選擇兩個個體。如果兩個適應(yīng)度不同椿疗，則選擇適應(yīng)度大的個體漏峰；如果適應(yīng)度相同，則選擇 crowding distance 大的個體届榄。下圖就是 fitness sharing 和 crowding distance 的示意圖（左邊圖表示 fitness sharing, 右邊圖表示 crowding distance）浅乔。
自1985年VEGA發(fā)表之后，F(xiàn)onseca铝条、Deb 和 Goldberg 等大神引領(lǐng)著研究者們?yōu)榱烁玫亩嗄繕?biāo)遺傳算法貢獻自己的聰明才智靖苇，引發(fā)了一波研究潮流。時光荏苒攻晒，歲月如梭顾复。幾十年過去了，轉(zhuǎn)眼到了 2000 年后鲁捏，多目標(biāo)遺傳算法的坑大部分被填完芯砸，研究基本定型，便很難看到有影響力的多目標(biāo)遺傳算法研究了给梅。一篇 2006 年綜述對十幾年來的研究成果進行總結(jié)假丧，算是給多目標(biāo)遺傳算法的研究畫上了一句號。潮起了十幾年又潮落了动羽。
