遺傳算法GA ( Genetic Algorithms)是受生物學(xué)進(jìn)化學(xué)說和遺傳學(xué)理論的啟發(fā)而發(fā)展起來的，是一類模擬自然生物進(jìn)化過程與機(jī)制求解問題的自組織與自適應(yīng)的人工智能技術(shù)，是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)的搜索算法，由Holland教授于1975年提出。

         經(jīng)過十幾年的努力，遺傳算法不論是在應(yīng)用研究上，算法設(shè)計(jì)上，還是在基礎(chǔ)理論上，均取得了長足的發(fā)展，己經(jīng)成為信息科學(xué)、計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)和應(yīng)用科學(xué)等諸多學(xué)科所共同關(guān)注的熱點(diǎn)研究領(lǐng)域。

        遺傳算法雖然在過去的20年中得到了廣泛的應(yīng)用，但研究人員己經(jīng)意識到，遺傳算法采用簡單的、固定不變的進(jìn)化策略對復(fù)雜應(yīng)用場合的效果并不理想，傳統(tǒng)的遺傳算法逐漸暴露出一些缺點(diǎn)。所以，為了提高遺傳算法的性能，使其更好地應(yīng)用于實(shí)際問題的解決中，研究者們開始對基本遺傳算法進(jìn)行改進(jìn)，通過不同的遺傳基因表達(dá)方式，不同的交叉和變異算子的選擇，特殊算子的引用，以及不同的再生和選擇方法，產(chǎn)生了以基本遺傳算法為核心的各種算法。遺傳算法的這些擴(kuò)展和改進(jìn)給一般問題特別是工業(yè)工程中的難以求解的優(yōu)化問題帶來了新的希望和方向。

        由于多目標(biāo)優(yōu)化問題在科學(xué)和工程實(shí)踐中普遍存在，但又缺少確實(shí)有效的解決方法，研究人員把目光投向了具有多方向和全局搜索特點(diǎn)的遺傳算法。遺傳算法的這一基本特點(diǎn)可以確保帶有潛在解的種群能夠一代一代地維持下來，這種從種群到種群的方法對于搜索Pareto解非常有益，因此，利用遺傳算法解決多目標(biāo)優(yōu)化問題極具研究意義。于是，遺傳算法應(yīng)用于單目標(biāo)問題之后的20多年以后，多目標(biāo)遺傳算法逐漸成為研究熱點(diǎn)。

           非支配排序遺傳算法NSGA (Non-dominated Sorting Genetic Algorithms)是由Srinivas和Deb于1995年提出的。這是一種基于Pareto最優(yōu)概念的遺傳算法，它是眾多的多目標(biāo)優(yōu)化遺傳算法中體現(xiàn)Goldberg思想最直接的方法。該算法就是在基本遺傳算法的基礎(chǔ)上，對選擇再生方法進(jìn)行改進(jìn):將每個(gè)個(gè)體按照它們的支配與非支配關(guān)系進(jìn)行分層，再做選擇操作，從而使得該算法在多目標(biāo)優(yōu)化方面得到非常滿意的結(jié)果。

        2000年，他們又提出NSGA的改進(jìn)算法—帶精英策略的非支配排序遺傳算法(NSGA-II)。 NSGA-II改進(jìn)了原來算法的不足之處，提高了算法的運(yùn)算速度和魯棒性，并保證了非劣最優(yōu)解的均勻分布。因而，NSGA-II比NSGA更具優(yōu)越性。

        NSGA-II的三大優(yōu)點(diǎn)分別是引入了非支配排序、提出擁擠度和擁擠度比較算子以及引入精英策略等。非支配排序利用Pareto最優(yōu)解的概念將種群中的個(gè)體進(jìn)行分級，非支配狀態(tài)越高的個(gè)體層級越靠前，從而能夠挑選出個(gè)體中較為優(yōu)異的，使其有較大機(jī)會進(jìn)入下一迭代。擁擠度只適用于同一支配層級的個(gè)體之間的比較，通過對每個(gè)個(gè)體的每個(gè)目標(biāo)函數(shù)進(jìn)行計(jì)算擁擠度，進(jìn)而得出每個(gè)個(gè)體的擁擠度，通過擁擠度比較個(gè)體的優(yōu)異程度。精英策略是把當(dāng)前種群和通過選擇、交叉和變異產(chǎn)生的子種群合并，共同競爭產(chǎn)生下一種群，保證具有較好特性的個(gè)體能夠保留在種群中，提高了種群的多樣性和計(jì)算效率。

        以下是NSGA-II算法的Matlab代碼，需要的可以嘗試下載。