馬昌威

（阿壩師范高等專(zhuān)科學(xué)校 計(jì)算機(jī)科學(xué)系，四川 汶川 623002）

多目標(biāo)優(yōu)化問(wèn)題的遺傳算法改進(jìn)研究

馬昌威

（阿壩師范高等專(zhuān)科學(xué)校 計(jì)算機(jī)科學(xué)系，四川 汶川 623002）

基于Nash均衡的思想在NSGA所求得的Pareto最優(yōu)解基礎(chǔ)上，探討一種能對(duì)多目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解的遺傳算法。采用Nash均衡的思想在多目標(biāo)優(yōu)化的遺傳算法，結(jié)合NSGA算法，提出一種能得到多個(gè)Pareto最優(yōu)解的多目標(biāo)優(yōu)化算法。通過(guò)目標(biāo)函數(shù)線(xiàn)性加權(quán)法、NSGA對(duì)函數(shù)進(jìn)行了試驗(yàn)分析，對(duì)部分自變量進(jìn)行固定，對(duì)其他的自變量進(jìn)行優(yōu)化，對(duì)Pareto最優(yōu)解進(jìn)行持續(xù)優(yōu)化，進(jìn)而實(shí)現(xiàn) 加速算法的收斂，從實(shí)驗(yàn)中得出了這種算法具有較快的收斂性，但是其運(yùn)行時(shí)間和NSGA相比沒(méi)有多少改善。

遺傳算法；多目標(biāo)；博弈論；Nash均衡；最優(yōu)解集

多目標(biāo)優(yōu)化問(wèn)題的起源是實(shí)際中復(fù)雜系統(tǒng)設(shè)計(jì)、建模與規(guī)劃問(wèn)題，這些系統(tǒng)所在的領(lǐng)域包含了生產(chǎn)、生活中的方方面面。在現(xiàn)實(shí)生活中幾乎每一個(gè)決策問(wèn)題都必須要考慮如何在不同的約束條件下同時(shí)處理多個(gè)相互沖突的目標(biāo)，這些問(wèn)題都涉及到了多個(gè)目標(biāo)的優(yōu)化，在這些問(wèn)題中各個(gè)目標(biāo)并不是單獨(dú)獨(dú)立存在的，往往是混合在一起相互競(jìng)爭(zhēng)的目標(biāo)，每一個(gè)目標(biāo)都具有不同的意義與方法，而它們之間所存在的競(jìng)爭(zhēng)性與復(fù)雜性使得優(yōu)化變得相當(dāng)困難。在多目標(biāo)優(yōu)化問(wèn)題的解決中，遺傳算法是一種較為有效的方法。同時(shí)遺傳算法將決策者納入到了問(wèn)題的討論范圍中，使得決策更加的合理。

1 多目標(biāo)遺傳算法

在過(guò)去的多年中，作為多目標(biāo)優(yōu)化問(wèn)題的新求解方法，遺傳算法受到了較大程度的關(guān)注，進(jìn)而誕生了遺傳多目標(biāo)優(yōu)化。傳統(tǒng)的多目標(biāo)優(yōu)化方法有約束法[1]、加權(quán)法、距離函數(shù)法[2]、分層序列法[3]等。而傳統(tǒng)的方法卻存在一定的缺陷[3-4]，這些缺陷的存在促使了遺傳算法的發(fā)展。

將遺傳算法的思想運(yùn)用到多目標(biāo)優(yōu)化問(wèn)題中最早可以追溯到1967年，Rosenberg在其研究中模擬單細(xì)胞有機(jī)物的化學(xué)遺傳特性時(shí)采用的多屬性研究方法[5]，并且提到了可考慮利用遺傳的搜索算法對(duì)多目標(biāo)問(wèn)題進(jìn)行求解。雖然最后他只是采用了單一屬性方法，但是其研究卻是開(kāi)創(chuàng)了遺傳算法應(yīng)用到多目標(biāo)優(yōu)化領(lǐng)域中的先河。

20世紀(jì)90年代，遺傳算法開(kāi)始在多目標(biāo)優(yōu)化領(lǐng)域中正式運(yùn)用。在90年代多目標(biāo)遺傳算法主要分為兩類(lèi)，其中一類(lèi)是采用Pareto機(jī)制的多目標(biāo)演化算法[6-7]，這種算法是當(dāng)前研究中的熱點(diǎn)，而另外一類(lèi)則是非Pareto機(jī)制的多目標(biāo)演化算法[8]。

1985年，David Schaffer為了能給對(duì)整合方法的缺點(diǎn)進(jìn)行改進(jìn)，在Grefenstette 的單目標(biāo)優(yōu)化程序GENESIS的基礎(chǔ)上提出了一種基于向量評(píng)估的遺傳算法（VEGA）。這是第一種多目標(biāo)不演化算法。但是這種方法并不是基于Pareto。1993年，Hom與Nafpliotis提出了一種基于Pareto的錦標(biāo)賽選擇機(jī)制方法——小組決勝遺傳算法。

隨著多目標(biāo)演化算法在各個(gè)領(lǐng)域中的應(yīng)用越來(lái)越廣泛，對(duì)其所進(jìn)行的研究也基本是直接受實(shí)際工程問(wèn)題推動(dòng)的[9-11]。當(dāng)前在多目標(biāo)優(yōu)化技術(shù)方面還存在很多需要解決的困難與問(wèn)題，例如非劣最優(yōu)解域收斂性分析、種群更新終止條件及其穩(wěn)定性分析等的。

2 基于博弈論的多目標(biāo)遺傳算法

博弈論所研究的是決策主體的行為發(fā)生直接的相互作用時(shí)決策以及這種決策的均衡問(wèn)題。在博弈論中研究的典型問(wèn)題是兩個(gè)或者兩個(gè)以上的參加者在某種對(duì)抗性或者競(jìng)爭(zhēng)性的情況下各自做出決策，讓自己的一方可以最大限度的得到最有利的結(jié)果。博弈就是一組規(guī)則，整個(gè)過(guò)程中都有需要遵循的辦法與章程，包括了局中人、策略、選定策略后的結(jié)局等等都需要符合規(guī)則。接下來(lái)就將博弈論用于多目標(biāo)優(yōu)化問(wèn)題進(jìn)行探討。

2.1 Nash均衡與博弈論

在博弈論中所研究的對(duì)象是多個(gè)決策主體之間的相互作用，也就是決策主體具有相互依存性，在博弈中任何一個(gè)決策主體都會(huì)受到其他決策主體的影響，同時(shí)每一個(gè)決策主體的決策都會(huì)影響到其他的主體。

1）博弈要素

博弈的要素主要有參與人、策略以及效用函數(shù)。

參與人指的是參與博弈的決策主體，同時(shí)也被稱(chēng)為局中人，用Yi（i=1，2，…，n）表示。

策略指的是每一個(gè)參與人可以做出的行動(dòng)。

純策略集，指的是每一個(gè)參與人通常會(huì)有多個(gè)策略進(jìn)行選擇，這些策略構(gòu)成了這個(gè)參與人的純策略集，參與人Yi（i=1，2，…，n）的純策略集用Si={Si1，Si2，…，Simi}進(jìn)行表示，其中mi則是表示第i個(gè)參與人可以選擇的策略個(gè)數(shù)。

局勢(shì)，指的是博弈中參與的各方所采取的策略的組合，可以是純策略的組合，記為 S=S1×S2×…×Sn，也可以是采取的混合策略組合，記為S=Q1×Q2×…×Qn。

效用函數(shù)，指的是局勢(shì)集合S上的函數(shù)，主要是用來(lái)對(duì)博弈中的參與人盈利是多少，可以為參與人做出更加理性的決策提供重要的依據(jù)。當(dāng)所有的參與人所做出的決策集合在一起時(shí)，就會(huì)引起相應(yīng)的結(jié)果，著寫(xiě)結(jié)果能夠反映出參與人的目標(biāo)實(shí)現(xiàn)的具體情況，因此，就存在一個(gè)對(duì)客觀現(xiàn)實(shí)進(jìn)行反映的映射：Fij（s）→R1，s∈S，（j=1，2，…，ki）。在這個(gè)式子中，F(xiàn)ij代表的是第i個(gè)參與人的第j個(gè)目標(biāo)函數(shù)，ki則是表示第i個(gè)參與人做考慮的目標(biāo)個(gè)數(shù)，那么參與人 的效用函數(shù)就可以記為：

F1=（Fi1，F(xiàn)i2，…Fik），i=1，2，…n

記Y1=（Y1，Y2，…Yn），F(xiàn)1=（F1，F(xiàn)2，…Fn），用G=（Y，S，F(xiàn)）來(lái)對(duì)博弈的策略模型進(jìn)行表示。

2）Nash均衡

Nash均衡又被稱(chēng)為合作博弈均衡，是博弈論中的一個(gè)相當(dāng)重要的術(shù)語(yǔ)，是數(shù)學(xué)家Nash在1954年提出的。其定義是：假設(shè)在博弈中有n個(gè)人參與其中，如果在某種情況下沒(méi)有一個(gè)參與者能獨(dú)自行動(dòng)而使得收益得到增加（也就是為了自身的利益達(dá)到最大化，沒(méi)有任何一個(gè)單獨(dú)的一方愿意對(duì)其策略進(jìn)行改變），那么這種策略組合就被成為Nash均衡。Nash均衡從實(shí)質(zhì)上來(lái)講，是一種非合作博弈的狀態(tài)。當(dāng)Nash均衡達(dá)成時(shí)，并不代表博弈的各方都是處于一種不同的狀態(tài)，而是在順序博弈中這個(gè)均衡在博弈者的連續(xù)動(dòng)作與各種反應(yīng)中大程度的。Nash均衡并并不是代表博弈的各方達(dá)到了整體的最優(yōu)狀態(tài)。

Pareto-Nash均衡是多目標(biāo)博弈中的均衡，這個(gè)概念也被稱(chēng)為有效Nash均衡策略。這種策略是博弈中的眾多策略中的一個(gè)“不壞”的策略，因此，其又被稱(chēng)為非劣Nash均衡策略。因此，通常情況下，并不會(huì)像單目標(biāo)博弈中的那樣唯一的或者不多的幾個(gè)Nash均衡策略，而是往往存在多個(gè)Pareto-Nash均衡策略。而全部的Pareto-Nash均衡策略所組成的集合則是叫做Pareto-Nash均衡策略。

2.2 算法改進(jìn)

1）基本思想

這里在Nash Gas的基礎(chǔ)上，結(jié)合NSGA算法，提出一種能得到多個(gè)Pareto最優(yōu)解的多目標(biāo)優(yōu)化算法。

2）算法測(cè)試

為了能夠進(jìn)行比較，這里選取參考文獻(xiàn)[12]中的函數(shù)來(lái)進(jìn)行測(cè)試（這個(gè)問(wèn)題是由Deb設(shè)計(jì)的[13]），描述如下

其中：

對(duì)這個(gè)問(wèn)題分別使用目標(biāo)函數(shù)線(xiàn)性加權(quán)法、NSGA與文中上述算法進(jìn)行求解，其結(jié)果如下：

線(xiàn)性加權(quán)法：

運(yùn)用線(xiàn)性加權(quán)法求解50次，結(jié)果如下：

3

求解的過(guò)程使用的是實(shí)數(shù)編碼方法，種群規(guī)模為20，最大進(jìn)化代數(shù)則為2000.

NSGA算法：

使用實(shí)數(shù)編碼、基于Pareto排序與共享機(jī)制的NSGA來(lái)對(duì)這個(gè)問(wèn)題進(jìn)行求解。種群的規(guī)模為50，在表1中顯示了不同的進(jìn)化代數(shù)，全局Pareto最優(yōu)解在所有解中所占的比例。

表1 NSGA算法求解結(jié)果Tab.1 NSGA algorithm results

從表中能夠看出，當(dāng)種群規(guī)模為50時(shí)，該算法需要運(yùn)行400代才能100％的保證收斂到最優(yōu)解。

文中所述算法：

針對(duì)兩目標(biāo)、兩自變量函數(shù)優(yōu)化問(wèn)題，將第一個(gè)目標(biāo)函數(shù)來(lái)作為第一個(gè)參與人，對(duì)f1進(jìn)行優(yōu)化；將第二個(gè)目標(biāo)函數(shù)作為第二個(gè)參與人，對(duì)x1進(jìn)行固定，對(duì)f2進(jìn)行優(yōu)化，種群規(guī)模選定為50，分別使用線(xiàn)性加權(quán)法、NSGA與上訴的算法進(jìn)行求解，得到如下結(jié)果：

表2 不同Pareto算法的最優(yōu)解所占比例Tab.2 Different Pareto optimal solution algorithms

從上表中能給看出，本文所提出的算法在收斂速度上比線(xiàn)性加權(quán)法與NSGA都要優(yōu)秀，只需要200代就能夠100％收斂到全局Pareto最優(yōu)解。因?yàn)樵贜SGA中嵌入了Nash均衡的過(guò)程，因此算法的時(shí)間上與NSGA相比沒(méi)有多少改善。

2.3 展 望

將Nash均衡的思想在多目標(biāo)優(yōu)化的遺傳算法中進(jìn)行運(yùn)用，在這個(gè)算法中將優(yōu)化對(duì)象中的每一個(gè)目標(biāo)，對(duì)應(yīng)到博弈中的一個(gè)參與人，將所有的自變量在這些參與人之間進(jìn)行分配，其中每一個(gè)參與人分配的是自變量的一個(gè)子集。在優(yōu)化的過(guò)程中，每一個(gè)局中人都通過(guò)遺傳算法來(lái)對(duì)自己對(duì)應(yīng)的目標(biāo)進(jìn)行優(yōu)化，通過(guò)這樣的方法來(lái)對(duì)NSGA方法繼續(xù)優(yōu)化得到Pareto最優(yōu)解，并將Pareto最優(yōu)解注入到NSGA的外部種群中，這樣就能讓算法快速收斂。

隨著社會(huì)與科技的發(fā)展，很多問(wèn)題的規(guī)模都在增大，使得組合優(yōu)化問(wèn)題的搜索空間也急劇的增加，有時(shí)在當(dāng)前的計(jì)算上利用枚舉法是很難找到最優(yōu)解的。對(duì)于這種復(fù)雜的問(wèn)題，人們已經(jīng)意識(shí)到了尋求滿(mǎn)意解的重要性，而遺傳算法則是尋求滿(mǎn)意解的最佳工具之一。遺傳算法對(duì)于組合優(yōu)化中的NP問(wèn)題有著良好的效果，例如在求解旅行商問(wèn)題、背包問(wèn)題、工作日程安排、試題組卷問(wèn)題、裝箱問(wèn)題、圖形劃分問(wèn)題等很多方面，遺傳算法都取得了一定的成功[14]。同時(shí)GA在生產(chǎn)調(diào)度問(wèn)題、自動(dòng)控制、機(jī)器人學(xué)、圖像處理等很多方面都有著廣泛的運(yùn)用。

3 結(jié)束語(yǔ)

文中在Nash均衡的基礎(chǔ)上，根據(jù)NSGA算法，提出了一種能對(duì)多目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解的遺傳算法，該算法使用Nash均衡的思想在NSGA所求得的Pareto最優(yōu)解的基礎(chǔ)上，對(duì)部分自變量進(jìn)行固定，對(duì)其他的自變量進(jìn)行優(yōu)化，對(duì)Pareto最優(yōu)解進(jìn)行持續(xù)優(yōu)化，進(jìn)而實(shí)現(xiàn) 加速算法的收斂。從實(shí)驗(yàn)中能給出，這種算法具有較快的收斂性，但是其運(yùn)行時(shí)間和NSGA相比沒(méi)有多少的改善。

[1] 唐煥文，秦學(xué)志.實(shí)用最優(yōu)化方法[M]，大連：大連理工大學(xué)出版社，2004.

[2] 高媛.非支配排序遺傳算法（NSGA）的研究與應(yīng)用[D].杭州：浙江大學(xué)，2006.

[3] 崔遜學(xué).多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2006.

[4] 周盛強(qiáng)，向錦武.基于BP網(wǎng)絡(luò)和Pareto的遺傳算法的多目標(biāo)協(xié)同優(yōu)化[J].機(jī)械設(shè)計(jì)與研究，2006，22（5）：10-13.

ZHOU Sheng-qiang，XIANG Jin-wu Based on BP network and Pareto genetic algorithm for multi-objective collaborative optimization[J].Mechanical Design and Research，2006，22（5）：10-13.

[5] 劉瑞，許峰.基于 支配擂臺(tái)賽法則的多目標(biāo)遺傳算法[J].軟件導(dǎo)刊，2012，11（8）：53-55.

LIU Rui，XU Feng.Disposable Challenge Cup rule based multi-objective genetic algorithm [J].Software Tribune，2012，11（8）：53-55.

[6] 高堅(jiān).基于免疫機(jī)制和遺傳進(jìn)化的網(wǎng)絡(luò)組播路由優(yōu)化算法[J].微電子學(xué)和計(jì)算機(jī)，2003，20（8）：20-21.

GAO Jian.Based on Immune Mechanism and Genetic network multicast routing optimization algorithm [J].Microelectronics and Computer，2003，20（8）：20-21.

[7] 孫強(qiáng)，楊俊茹.一種基于多目標(biāo)遺傳算法的高層次測(cè)試綜合方法[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（5）：245-247.

SUN Qiang，YANG Jun-ru.A multi-objective genetic algorithm based on high-level test synthesis method [J].Computer Applications and Software，2013，30（5）：245-247.

[8] 李煥勤，錢(qián)展.解決混合裝配線(xiàn)平衡問(wèn)題的多目標(biāo)遺傳算法研究[J].河南科學(xué)，2012，30（6）：724-729.

LI Huan-qin，QIAN Zhan.Hybrid assembly line balancing problem to solve multi-objective genetic algorithm [J].Henan Science，2012，30（6）：724-729.

Improvement of genetic algorithm for multi-objective optimization problem

MA Chang-wei
（Dept.of Computer Science of Aba Teachers College，Wenchuan 623002，China）

Purpose of this paper the idea of Nash equilibrium based on NSGA Pareto optimal solutions are obtained based on the right to explore a multi-objective optimization problem can be solved genetic algorithms.Methods idea of Nash equilibrium in a multi-objective optimization genetic algorithm，combined with NSGA algorithm is proposed to get multiple Pareto optimal solution of multi-objective optimization algorithm.Results The linear weighted objective function method，NSGA tested for function analysis，on the part of the independent variable and fixed，for other independent variables are optimized for Pareto optimal solution for continuous optimization，thus achieving accelerated convergence of the algorithm，the conclusion from the experimental derive this algorithm has faster convergence，but its running time and NSGA little improvement compared.

genetic algorithm；multi-objective；game theory；Nash equilibrium；optimal solution set

TN01

A

1674-6236（2014）11-0145-03

2013-11-21 稿件編號(hào)：201311182

四川省教育廳2012年立項(xiàng)課題（12ZB001；12ZB169）

馬昌威（1972—），男，四川茂縣人，碩士，副教授。研究方向：計(jì)算機(jī)應(yīng)用和高等教育信息化。