面向客戶個(gè)性化需求的交互式遺傳算法

竇潤(rùn)亮， 郭均鵬， 田祥龍， 宗 超

(天津大學(xué)管理與經(jīng)濟(jì)學(xué)部， 天津 300072)

面向客戶個(gè)性化需求的交互式遺傳算法

竇潤(rùn)亮， 郭均鵬， 田祥龍， 宗 超

(天津大學(xué)管理與經(jīng)濟(jì)學(xué)部， 天津 300072)

針對(duì)交互式遺傳算法(IGA)中的評(píng)價(jià)噪聲問題，提出猶豫度的概念，建立猶豫度調(diào)整機(jī)制，并使用刪除策略和修改策略來(lái)處理形成初始種群以及交叉、變異過程中產(chǎn)生的約束不滿足個(gè)體.通過對(duì)汽車操控臺(tái)的概念設(shè)計(jì)問題進(jìn)行建模，建立人性化交互界面用以驗(yàn)證本論文提出的方法體系的先進(jìn)性和合理性.實(shí)驗(yàn)表明，此求解算法能夠有效的降低評(píng)價(jià)噪聲，加速收斂，降低疲勞度，提高結(jié)果的滿意度.

交互式遺傳算法； 猶豫度； 評(píng)價(jià)噪聲； 約束處理； 疲勞度

0 引 言

產(chǎn)品市場(chǎng)的競(jìng)爭(zhēng)，使得產(chǎn)品設(shè)計(jì)與生產(chǎn)企業(yè)對(duì)客戶個(gè)性化需求的重視程度日益提高，面向客戶個(gè)性化需求的產(chǎn)品配置需要對(duì)客戶的需求進(jìn)行快速、準(zhǔn)確響應(yīng).如何快速獲取客戶實(shí)時(shí)需求，建立產(chǎn)品優(yōu)化設(shè)計(jì)的用戶滿意模型，并將之轉(zhuǎn)換成相應(yīng)產(chǎn)品的功能需求，是進(jìn)行產(chǎn)品配置的首要環(huán)節(jié)[1-2].

遺傳算法被廣泛認(rèn)為是解決此類問題最有效的方法之一.由于遺傳算法不要求被優(yōu)化的目標(biāo)函數(shù)連續(xù)和可微，并且能在容許的時(shí)間內(nèi)找到大規(guī)模優(yōu)化問題的滿意解，自提出以來(lái)便引起了國(guó)內(nèi)外眾多學(xué)者的廣泛關(guān)注，在算法的應(yīng)用和理論研究方面，國(guó)內(nèi)諸多學(xué)者也進(jìn)行深入研究，取得了豐碩的研究成果.Ozcelik等人提出一種遺傳算法在工業(yè)路線設(shè)計(jì)中的應(yīng)用，指出單元構(gòu)成的重要性[3].Huang等人提出一種基于遺傳算法的具有共性的多層次產(chǎn)品族設(shè)計(jì)優(yōu)化問題，研制了一種多目標(biāo)遺傳算法的同步產(chǎn)品變異設(shè)計(jì)[4].此外，遺傳算法與其他智能算法結(jié)合，拓展了遺傳算法的適用范圍.如遺傳算法與人工神經(jīng)網(wǎng)絡(luò)結(jié)合[5]，鄒昊飛等人基于兩階段優(yōu)化算法的遺傳算法人工神經(jīng)網(wǎng)絡(luò)，并建立相應(yīng)的預(yù)測(cè)模型進(jìn)行實(shí)證研究，結(jié)果表明該模型能較大提高神經(jīng)網(wǎng)絡(luò)的全局收斂能力和收斂速度[6].遺傳算法與粒子群[7]、蟻群[8]等優(yōu)化算法的結(jié)合等.宋莉波等人針對(duì)柔性工作車間調(diào)度問題，提出了一種基于混合遺傳算法的求解方案，并在遺傳進(jìn)化的過程中增加基于混沌序列的鄰域搜索功能, 以提高遺傳算法的執(zhí)行效率[9].

客戶需求中技術(shù)類和非技術(shù)類需求普遍共存，而非技術(shù)類需求在算法上一般體現(xiàn)為隱性指標(biāo)，對(duì)其響應(yīng)需要與客戶的頻繁交互，傳統(tǒng)的遺傳算法已經(jīng)對(duì)于解決隱性指標(biāo)的優(yōu)化問題不再適用，從而本文引入交互式遺傳算法(interactive genetic algorithm，IGA).交互式遺傳算法是一種將人的主觀評(píng)價(jià)值作為個(gè)體適應(yīng)度值的進(jìn)化算法.特點(diǎn)是融入了人的智能，其個(gè)體的適應(yīng)度值由用戶指定而非通過函數(shù)，因而非常適合解決含隱式性能指標(biāo)的優(yōu)化問題，現(xiàn)已廣泛應(yīng)用于計(jì)算機(jī)圖形學(xué)[10-11]、工業(yè)設(shè)計(jì)[12-14]、音樂創(chuàng)作[15]、自動(dòng)控制與機(jī)器人技術(shù)[16]等多個(gè)領(lǐng)域.然而IGA也存在限制，由于用戶通過人機(jī)界面指定個(gè)體的適應(yīng)度，其頻繁的交互易引起用戶疲勞.因此，如何降低IGA中的用戶疲勞度便成為重點(diǎn)的研究方向.降低IGA用戶疲勞度的研究中，近年來(lái)的重點(diǎn)多集中在如何改進(jìn)進(jìn)化策略、提高適應(yīng)值估算的效果[17-19]，但是從降低評(píng)價(jià)誤差入手的研究目前仍然較少.Branke和Beyer等人認(rèn)為普通遺傳算法中的噪聲主要產(chǎn)生于三方面: 決策變量，適應(yīng)值的計(jì)算和優(yōu)化問題本身[20-21]，而Jin和Di等人認(rèn)為噪聲對(duì)進(jìn)化過程的影響表現(xiàn)為：學(xué)習(xí)效率低，難以保留學(xué)習(xí)的信息，決策變量空間的利用能力受限，種群適應(yīng)度值未隨進(jìn)化代數(shù)的增加而提高[22,23].但是以上文獻(xiàn)并沒有注重探究用戶在進(jìn)化過程中評(píng)價(jià)的心理過程，以及用戶的心理變化對(duì)于進(jìn)化噪聲的影響.考慮到交互式遺傳算法是由人來(lái)評(píng)價(jià)個(gè)體的適應(yīng)值，因此人的心理變化必然會(huì)對(duì)進(jìn)化過程和結(jié)果產(chǎn)生影響，尤其是猶豫的感覺.一般優(yōu)化進(jìn)化算法中的噪聲補(bǔ)償策略主要有3種[21-23]:增大種群規(guī)模，增加采樣次數(shù),取采樣的平均值，改進(jìn)遺傳算子.因此，重復(fù)采樣技術(shù)提高個(gè)體適應(yīng)度值是一般遺傳算法噪聲補(bǔ)償?shù)倪x擇策略.而在交互式遺傳算法中，大量重復(fù)地采樣評(píng)價(jià)，必然造成人的疲勞，從而影響到進(jìn)度的效果.因而上述補(bǔ)償策略不適合于交互式遺傳算法，必須針對(duì)其算法特點(diǎn)和噪聲的特性研究降噪策略.針對(duì)于此，本文從研究用戶的評(píng)價(jià)心理過程出發(fā)，提出了猶豫度概念，建立了猶豫度調(diào)整機(jī)制來(lái)降低噪聲.

在進(jìn)行仿真實(shí)驗(yàn)時(shí)，本文選擇汽車操控臺(tái)的概念設(shè)計(jì)來(lái)進(jìn)行實(shí)驗(yàn).汽車的操控臺(tái)形式多樣，結(jié)構(gòu)比較復(fù)雜，用戶在評(píng)價(jià)時(shí)候通常帶有很高的主觀性，這是能突出交互式遺傳算法強(qiáng)大優(yōu)勢(shì)的應(yīng)用領(lǐng)域，而且目前的汽車產(chǎn)品大部分還是處在大批量生產(chǎn)階段，沒有成熟的產(chǎn)品定制模式，因此本文試圖通過此方法，使得用戶能夠參與到汽車產(chǎn)品的設(shè)計(jì)中，同時(shí)相對(duì)于制造商，能充分利用企業(yè)自身的設(shè)計(jì)資源，達(dá)到大規(guī)模定制的目的.汽車操控臺(tái)的復(fù)雜性特點(diǎn)，導(dǎo)致配置算法求解時(shí)，在形成染色體的過程中很容易產(chǎn)生不滿足約束的個(gè)體，本文采用兩種約束處理策略——?jiǎng)h除策略和修改策略來(lái)解決約束問題.通過建立了汽車操控臺(tái)的設(shè)計(jì)系統(tǒng)，驗(yàn)證此方法能夠降低評(píng)價(jià)誤差，降低用戶疲勞度，提高算法結(jié)果的滿意度.

1 相關(guān)理論基礎(chǔ)

交互式遺傳算法求解傳統(tǒng)步驟如下：首先對(duì)需要優(yōu)化的問題的所有參數(shù)進(jìn)行編碼，一個(gè)字符串代表一個(gè)染色體(每個(gè)染色體都表示一個(gè)可行解)，所有染色體的集合稱為種群；然后以隨機(jī)方式產(chǎn)生一群初始解，通過人來(lái)賦予個(gè)體適應(yīng)值，根據(jù)適應(yīng)值大小使用遺傳算子(選擇、交叉、變異)對(duì)本代中的染色體進(jìn)行遺傳進(jìn)化操作，進(jìn)入下一代種群，再由人來(lái)評(píng)價(jià)個(gè)體適應(yīng)值，如此循環(huán)進(jìn)化，直至得到滿意解或者強(qiáng)制結(jié)束.

傳統(tǒng)的交互式遺傳算法如圖1所示.

1.1 猶豫度的概念

交互式遺傳算法區(qū)別于普通遺傳算法的最大特點(diǎn)就是其個(gè)體的適應(yīng)值不是由適應(yīng)值函數(shù)求得，而是來(lái)自人的評(píng)價(jià)，因此，由于人的主觀因素和疲勞度的增加，對(duì)于相同的個(gè)體在不同的評(píng)價(jià)階段可能會(huì)有不同的適應(yīng)值，即偏差，或噪聲.

按照交互時(shí)間的長(zhǎng)短，評(píng)價(jià)過程可以分為認(rèn)知階段、中間階段以及疲勞階段3個(gè)階段[18].

在用戶評(píng)價(jià)的認(rèn)知階段，由于對(duì)于目標(biāo)個(gè)體還不明確或者是只對(duì)于部分屬性明確，會(huì)使得評(píng)價(jià)結(jié)果與個(gè)體的真實(shí)適應(yīng)值產(chǎn)生噪聲.而此時(shí)噪聲產(chǎn)生的主要原因是用戶對(duì)于理想個(gè)體還不明確，而這種對(duì)于理想個(gè)體“迷茫”的感覺體現(xiàn)在用戶心理就是“猶豫感”.因此，用戶在評(píng)價(jià)個(gè)體時(shí)，會(huì)產(chǎn)生不同程度的猶豫感.當(dāng)用戶的理想個(gè)體還未明確，用戶的猶豫感比較強(qiáng)；而當(dāng)用戶的理想個(gè)體明確之后，用戶的猶豫感就會(huì)比較弱.對(duì)于第t代第i個(gè)個(gè)體xi(t)的猶豫感的強(qiáng)烈程度可用猶豫度hi(t)來(lái)表示

(1)

圖1 傳統(tǒng)IGA的算法流程

Fig. 1 Traditional IGA process

1.2 猶豫度調(diào)整機(jī)制的原理

將待解決的問題描述為如下形式

maxf(x)

s.t.x∈S

f(x)即是用戶對(duì)于個(gè)體x評(píng)價(jià)的適應(yīng)值，S是個(gè)體x的搜索空間.當(dāng)產(chǎn)生噪聲時(shí)，用戶賦予個(gè)體xi的適應(yīng)值f(xi)與其真實(shí)的適應(yīng)值f’(xi)會(huì)有偏差，f(xi)≠f’(xi).對(duì)于偏差，當(dāng)f(xi)f’(xi)時(shí)，稱f+=f(xi)-f’(xi)為正偏差.正偏差f+和負(fù)偏差f-構(gòu)成噪聲的主要內(nèi)容，因此，如何減少正負(fù)偏差就成為了降低噪聲的關(guān)鍵之一.

(2)

其中d(xi(t),xj)的實(shí)際含義是兩個(gè)個(gè)體xi(t)與xj之間的距離，即基因片段相似的程度.然后，應(yīng)用此距離，得出與猶豫個(gè)體xi(t)距離較近的個(gè)體的集合

L(xi(t))={xj|d(xi(t),xj)≤d0,xj∈Ne}

(3)

其中Ne是已評(píng)價(jià)過的個(gè)體的集合，d0是反映兩個(gè)體之間距離的臨界值，預(yù)先設(shè)定.通過計(jì)算該集合中個(gè)體的平均適應(yīng)值

驅(qū)動(dòng)形式 ..................................................................后置后驅(qū)

(4)

來(lái)得出猶豫個(gè)體xi(t)的近似真實(shí)適應(yīng)值f’(xi(t))，最后，利用此值調(diào)整用戶賦予個(gè)體xi(t)的適應(yīng)值

f(xi(t))=f′(xi(t))

通過此過程，可以找出用戶產(chǎn)生猶豫的個(gè)體，并且通過計(jì)算與其相似個(gè)體的平均適應(yīng)值來(lái)得出其近似的真實(shí)適應(yīng)值f’(xi(t)), 然后調(diào)整其適應(yīng)值，從而減少正負(fù)偏差，加速算法的進(jìn)行，減少用戶疲勞度.

本文以客戶對(duì)于理想個(gè)體是否明確作為認(rèn)識(shí)階段的分界點(diǎn)：當(dāng)客戶對(duì)于理想個(gè)體不明確時(shí)，還處在認(rèn)識(shí)階段，此時(shí)在用戶評(píng)價(jià)個(gè)體時(shí)應(yīng)用猶豫度調(diào)整機(jī)制；當(dāng)客戶對(duì)于理想個(gè)體明確了之后，便進(jìn)入穩(wěn)定階段，此時(shí)不再應(yīng)用猶豫度調(diào)整機(jī)制.

1.3 約束不滿足個(gè)體的處理

針對(duì)復(fù)雜產(chǎn)品特性，應(yīng)用交互式遺傳算法進(jìn)行配置求解時(shí)，很容易由于不滿足約束條件而產(chǎn)生不合理的個(gè)體，因此，約束不滿足問題也是困擾交互式遺傳算法的一個(gè)大問題.針對(duì)于此，本文應(yīng)用兩種處理策略：刪除策略和修改策略.如圖2所示.

1)刪除策略是指將不滿足約束的個(gè)體直接刪除，不在交互界面中顯示.由于初始種群的生成是從大規(guī)模的種群中篩選出來(lái)的，因此大規(guī)模初始種群生成時(shí)可以使用刪除策略，將不滿足約束的個(gè)體直接刪除，而不會(huì)使得優(yōu)秀基因減少.而進(jìn)化階段由于交互界面的限制，種群較小，如果將不滿足約束的個(gè)體直接刪除，可能會(huì)是某些優(yōu)秀的基因消失，不利于進(jìn)化.因此，刪除策略只在生成初始種群時(shí)應(yīng)用.

2)修改策略是指在進(jìn)化過程中，對(duì)于交叉、變異形成的不滿足約束的個(gè)體，將其數(shù)量控制在一定范圍之內(nèi)(但不在交互界面中顯示，其適應(yīng)度默認(rèn)為平均值)，對(duì)于超出范圍的個(gè)體進(jìn)行修改.之所以將不滿足約束的個(gè)體保留一定數(shù)量，是因?yàn)椴粷M足約束的個(gè)體可能包含有具有優(yōu)勢(shì)的基因.修改是指根據(jù)事先建立好的約束數(shù)據(jù)庫(kù)中儲(chǔ)存的各種約束，按照IF-THEN規(guī)則將其不滿足約束的部件或模塊改成滿足約束的部件或模塊.修改策略應(yīng)用在種群的進(jìn)化過程中.

圖2 約束不滿足個(gè)體的處理

2 基于猶豫度調(diào)整機(jī)制的IGA

結(jié)合猶豫度調(diào)整機(jī)制和約束不滿足個(gè)體的處理方法，本文對(duì)于傳統(tǒng)的IGA進(jìn)行了一些改進(jìn)，提出基于猶豫度調(diào)整機(jī)制的IGA.

2.1 算法步驟

1)在初始階段，如果客戶目標(biāo)個(gè)體的某些屬性已有確定的偏好，則系統(tǒng)會(huì)詢問并確定其偏好，從而鎖定基因類型，加速收斂.

2)初始種群的生成.針對(duì)復(fù)雜產(chǎn)品，如果種群規(guī)模較小，很容易陷入局部收斂，而若種群規(guī)模較大，則會(huì)大大增加客戶的疲勞度.本文提出一種折中的方法：隨機(jī)生成一個(gè)較大規(guī)模的種群，并對(duì)其進(jìn)行交互評(píng)價(jià)，然后按適應(yīng)值排序，取適應(yīng)值高的前n個(gè)個(gè)體，并且在其余個(gè)體中隨機(jī)選出m個(gè)個(gè)體，共同組成初始種群.這個(gè)步驟的原理是如果只選擇適應(yīng)值高的個(gè)體，可能會(huì)造成存在于適應(yīng)值低的個(gè)體中的優(yōu)秀基因流失，而這個(gè)步驟可以有效的解決這個(gè)問題.

3)將遺傳進(jìn)化分為兩階段：目標(biāo)個(gè)體不明確階段和目標(biāo)個(gè)體明確階段.在目標(biāo)個(gè)體不明確階段，對(duì)于客戶的交互評(píng)價(jià)實(shí)施猶豫度調(diào)整機(jī)制，減少認(rèn)識(shí)階段的噪聲，從而加速收斂.在目標(biāo)個(gè)體明確階段，不再實(shí)施猶豫度調(diào)整機(jī)制，并提供手動(dòng)配置功能，方便用戶自主配置.

4)對(duì)于約束不滿足的個(gè)體處理，在初始種群的生成階段，實(shí)施刪除策略；對(duì)于進(jìn)化階段的新種群的生成，實(shí)施修改策略.

2.2 算法流程圖

如圖3所示.

圖3 基于猶豫度調(diào)整機(jī)制的IGA流程圖

Fig.3 IGA process based on hesitation degree adjusting mechanism

3 仿真實(shí)驗(yàn)

3.1 系統(tǒng)的建立

本文建立了汽車操控臺(tái)的概念設(shè)計(jì)系統(tǒng)，以此來(lái)驗(yàn)證算法的性能.

1)編碼模式.本系統(tǒng)用二進(jìn)制來(lái)對(duì)操控臺(tái)進(jìn)行編碼.如圖4所示，一條染色體(即一個(gè)產(chǎn)品)總體分為6個(gè)部分，分別對(duì)應(yīng)操控臺(tái)的五大模塊和顏色模塊.每一部分又進(jìn)一步分為若干基因，每一個(gè)基因的二進(jìn)制代碼均代表一個(gè)具體的實(shí)例.圖4中中控臺(tái)的編碼001001001即代表“第一類GPS導(dǎo)航、DVD音響系統(tǒng)、6寸液晶顯示屏”的實(shí)例.

圖4 編碼模式

Fig.4 Coding pattern

2)約束的處理.對(duì)于操控臺(tái)的約束本文采用IF-THEN的結(jié)構(gòu)來(lái)表示，如表1所示.在產(chǎn)生初始種群的過程中，如果所產(chǎn)生的個(gè)體不滿足約束，那么直接刪除此個(gè)體，此即刪除策略；在進(jìn)化過程中如果所產(chǎn)生的個(gè)體不滿足約束，那么保留一定數(shù)量的不滿足約束個(gè)體，以免優(yōu)秀基因流失，對(duì)于超出數(shù)量的不滿足約束個(gè)體按照約束規(guī)則進(jìn)行修改，修改方法為用滿足約束的基因替換不滿足約束的基因.

表1 操控臺(tái)的部分約束

3)參數(shù)設(shè)置.初始大規(guī)模種群數(shù)量N0=45，初始種群中的n=6，m=3考慮到用戶評(píng)價(jià)每一代的時(shí)間和顯示器大小的限制，將每一代種群數(shù)量定為ng=9，截止進(jìn)化代數(shù)G0=25，交叉與變異概率分別為0.8和0.07，約束修改策略中保留不滿足約束個(gè)體數(shù)量為2，適應(yīng)值取0到100的整數(shù).猶豫度調(diào)整機(jī)制中合適的閥值h0和d0通過實(shí)驗(yàn)來(lái)確定：在不同的h0和d0的數(shù)值下，系統(tǒng)獨(dú)立運(yùn)行10次并取平均值，運(yùn)行情況如表2和表3所示，可以看出當(dāng)d0=0.7和h0=1.1時(shí)系統(tǒng)運(yùn)行的時(shí)間最短，評(píng)價(jià)的代數(shù)也最少，然后通過分析其收斂性，如圖5和圖6，其中，縱坐標(biāo)fitness是指每一代種群的平均適應(yīng)值，橫坐標(biāo)generation指的是系統(tǒng)運(yùn)行的代數(shù)，四條曲線分別代表不同h0和d0取值下的每代平均適應(yīng)值的走勢(shì)，可以看到當(dāng)d0=0.7和h0=1.1時(shí)收斂性也最好，因此可以確定h0和d0取值分別為1.1和0.7.

表2 不同h0的系統(tǒng)運(yùn)行情況(d0=0.7)

圖5 不同取值的h0對(duì)系統(tǒng)的收斂性的影響

d0測(cè)試次數(shù)平均代數(shù)平均評(píng)價(jià)個(gè)體數(shù)平均運(yùn)行時(shí)間0．41023．8214．286min52s0．51022．3200．779min18s0．61020．1180．972min25s0．71018．7168．369min46s0．81019．9179．171min12s0．91021．2190．876min08s

圖6 不同取值的d0對(duì)系統(tǒng)收斂性的影響

4)交互界面.本系統(tǒng)使用人性化的交互界面，提高客戶評(píng)價(jià)效率的同時(shí)減少疲勞度.如圖7所示，每一代種群數(shù)量為9，且同時(shí)顯示“目前最優(yōu)個(gè)體”和“上代最優(yōu)個(gè)體”兩個(gè)個(gè)體以供參考.在交互過程中，當(dāng)客戶對(duì)于理想個(gè)體明確之后，可以點(diǎn)擊“目標(biāo)個(gè)體明確”按鈕來(lái)終止猶豫度調(diào)整機(jī)制.

圖7 操控臺(tái)定制設(shè)計(jì)系統(tǒng)交互界面

Fig.7 Console customization system interface

3.2 對(duì)比實(shí)驗(yàn)

為了研究此方法對(duì)于IGA的貢獻(xiàn)，將傳統(tǒng)IGA(TIGA)與基于猶豫度調(diào)整機(jī)制的IGA(HAM-IGA)對(duì)比，獨(dú)立運(yùn)行20次.這兩種方法的運(yùn)行性能如表4所示，HAM-IGA的平均進(jìn)化代數(shù)只占TIGA的77.6%，運(yùn)行時(shí)間縮短了21.5%，達(dá)到了加速收斂的效果，從而減少了用戶的疲勞度.

此后，進(jìn)行了兩種方法的收斂性分析，如圖8所示，其中，縱坐標(biāo)fitness指的是每一代種群的平均適應(yīng)值，橫坐標(biāo)generation指的是系統(tǒng)運(yùn)行的代數(shù)，兩條曲線分別代表TIGA和HAM-IGA這兩種方法下的每代平均適應(yīng)值的走勢(shì).從中可以看出，HAM-IGA比TIGA收斂性能要好，尤其是在前期(大概8,9代)效果非常明顯，通過分析HAM的應(yīng)用對(duì)于系統(tǒng)運(yùn)行的影響，如表5所示，發(fā)現(xiàn)平均在8.3代之前，應(yīng)用HAM-IGA的系統(tǒng)都在使用HAM，因此證明HAM確實(shí)能夠有效降低評(píng)價(jià)噪聲，從而加速收斂.此外，應(yīng)用HAM的階段是用戶對(duì)于目標(biāo)個(gè)體不明確階段，而停止使用HAM是在用戶對(duì)于目標(biāo)個(gè)體明確階段，這兩個(gè)階段的評(píng)價(jià)每代評(píng)價(jià)時(shí)間相差將近一倍，這說(shuō)明當(dāng)用戶對(duì)于目標(biāo)個(gè)體明確之后，會(huì)有目的的來(lái)進(jìn)行評(píng)價(jià)，從而減少每個(gè)個(gè)體的評(píng)價(jià)時(shí)間.

最后，進(jìn)行HAM-IGA與TIGA的滿意度對(duì)比，首先將系統(tǒng)的最終結(jié)果分為三類：第一類是由于沒有在規(guī)定代數(shù)能發(fā)現(xiàn)最優(yōu)個(gè)體，而由系統(tǒng)強(qiáng)制停止；第二類是由于用戶感到非常疲勞，不愿去找最優(yōu)個(gè)體，而選擇比較滿意的個(gè)體(cool one)；第三類是成功找到了最優(yōu)個(gè)體，如圖9所示，其中，橫坐標(biāo)指的是以上三類情況，縱坐標(biāo)代表每一類情況在所有測(cè)試結(jié)果中所占的比例，從圖中可以看出，第一類和第二類的情況HAM-IGA比TIGA分別少40%和62.5%，而對(duì)于第三類情況，HAM-IGA比TIGA提高了100%，由此可以看出，HAM有效的提高了IGA的成功率，提高了用戶的滿意度.

表4 HAM-IGA與TIGA的性能對(duì)比

表5 HAM的應(yīng)用對(duì)于系統(tǒng)運(yùn)行的影響

圖8 HAM-IGA與TIGA的收斂性比較

圖9 HAM-IGA與TIGA滿意度對(duì)比

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

本文在交互式遺傳算法的領(lǐng)域提出猶豫度的概念，根據(jù)此概念建立了猶豫度調(diào)整機(jī)制，用于補(bǔ)償由于用戶猶豫產(chǎn)生的評(píng)價(jià)噪聲，從而改善交互式遺傳算法的首要問題——用戶疲勞度問題.然后選擇汽車操控臺(tái)的概念設(shè)計(jì)作為實(shí)驗(yàn)對(duì)象，根據(jù)汽車操控臺(tái)的復(fù)雜性特點(diǎn)，采用兩種約束處理方法——?jiǎng)h除策略和修改策略以改善交互式遺傳算法的約束滿足問題.最后，基于此方法建立汽車操控臺(tái)概念設(shè)計(jì)系統(tǒng)，并通過多次試驗(yàn)，分析試驗(yàn)結(jié)果，發(fā)現(xiàn)此方法能夠有效的降低評(píng)價(jià)過程中，尤其是評(píng)價(jià)前期中的評(píng)價(jià)噪聲，從而減少用戶的評(píng)價(jià)代數(shù)和評(píng)價(jià)時(shí)間，避免由于長(zhǎng)時(shí)間的評(píng)價(jià)而產(chǎn)生的用戶疲勞，同時(shí)此方法能夠明顯的提高用戶對(duì)于系統(tǒng)結(jié)果的滿意度.在后續(xù)的研究中，將繼續(xù)深入研究猶豫度的概念，完善猶豫度調(diào)整機(jī)制，更加有效地減少評(píng)價(jià)噪聲，以提高用戶的滿意度.

[1]唐加福, 汪定偉, 劉士新, 等. 產(chǎn)品優(yōu)化設(shè)計(jì)的用戶滿意模型[J]. 管理科學(xué)學(xué)報(bào), 2003, 6(3): 46-51. Tang Jiafu, Wang Dingwei, Liu Shixin, et al. Study on relationships between manager’s behavior and managerial performance[J]. Journal of Management Sciences in China, 2003, 6(3): 45-51.(in Chinese)

[2]經(jīng)有國(guó)， 但 斌， 張旭梅， 等. MC 半結(jié)構(gòu)化客戶需求信息表達(dá)與處理方法[J]. 管理科學(xué)學(xué)報(bào)， 2011， 14(1)： 78-85. Jing Youguo, Dan Bin, Zhang Xumei, et al.X Expressing and processing approach for semi-structured customer needs under mass customization[J]. Journal of Management Sciences in China, 2011， 14(1)： 78-85. (in Chinese)

[3]Ozcelik F, Sarac T. A genetic algorithm extended modified sub-gradient algorithm for cell formation problem with alternative routings[J]. International Journal of Production Research， 2012, 50(15): 4025-4037.

[4]Huang G Q, Li L, Schulze L. Genetic algorithm-based optimization method for product family design with multi-level commonality[J]. Journal of Engineering Design， 2008， 19(5)： 401-416.

[5]Haq A N, Ramanan T R. A hybrid neural network-genetic algorithm approach for permutation flow shop scheduling[J]. International Journal of Production Research， 2010， 48(14)： 4217-4231.

[6]鄒昊飛, 夏國(guó)平, 楊方廷. 基于兩階段優(yōu)化算法的神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型[J]. 管理科學(xué)學(xué)報(bào), 2006, 9(5): 28-35. Zou Haofei, Xia Guoping, Yang Fangting. Neural network forecasting model using multi-stage optimization approach based on GMDH and genetic algorithm[J]. Journal of Management Sciences in China, 2006, 9(5): 28-35. (in Chinese)

[7]Kuo R J. Integration of genetic algorithm and particle swarm optimization for investment portfolio optimization[J]. Applied Mathematics & Information Sciences， 2013, 7(6): 2397-2408.

[8]Gao Zhijun. A genetic ant colony algorithm for routing in CPS heterogeneous network[J]. International Journal of Computer Applications in Technology, 2013， 48(4)： 288-296.

[9]宋莉波, 徐學(xué)軍, 孫延明, 等. 一種求解柔性工作車間調(diào)度問題的混合遺傳算法[J]. 管理科學(xué)學(xué)報(bào)， 2010, 13(11): 49-54. Song Libo, Xu Xuejun, Sun Yanming, et al. A hybrid genetic algorithm for flexible job shop scheduling problem[J]. Journal of Management Sciences in China, 2010, 13(11): 49-54.(in Chinese)

[10]Yoon D M, Kim K J. 3D Game Model and Texture Generation using Interactive Genetic Algorithm[C]. WASA’12 Proceedings of the Workshop at SIGGRAPH Asia, Singapore, 2012: 53-58.

[11]Munteanu C, Morales F C, Ruiz-Alzola J. Speckle reduction through interactive evolution of a general order statistics filter for clinical ultrasound imaging[J]. IEEE Trans. on Biomedical Engineering, 2008, 55(1): 365-369.

[12]Brintrup A M, Ramsden J, Takagi H, et al. Ergonomic chair design by fusing qualitative and quantitative criteria using interactive genetic algorithms[J]. IEEE Trans. on Evolutionary Computation, 2008, 12(3): 343-354.

[13]Nathan-Roberts D, Liu Yili. Investigation of RelativeMobile Phone Size Preference Using Interactive Genetic Algorithms[C]. Proceedings of the Human Factors and Ergonomics Society Annual Meeting, San Diego: 2010: 1807-1811.

[14]Bandte O, Malinchik S. A broad and narrow approach to interactive evolutionary design: An aircraft design example[J]. Applied Soft Computing, 2009, 9(1): 448-455.

[15]Zhu H, Wang S F, Wang Z. Emotional music generation using interactive genetic algorithm[C]. Int Confon Computer Science and Software Engineering, Wuhan, 2008: 345-348.

[16]Babbar-Sebensa M, Minskerb B S. Interactive genetic algorithm with mixed initiative interaction for multi-criteria ground water monitoring design[J]. Applied Soft Computing, 2012， 12: 182-195.

[17]Wang L H. A comparison of three fitness prediction strategies for interactive genetic algorithms[J]. Journal of Information Science and Engineering, 2007, 23(2): 605-616.

[18]Sun Xiaoyan, Gong Dunwei, Zhang Wei. Interactive genetic algorithms with large population and semi-supervised learning[J]. Applied Soft Computing, 2012, 12: 3004-3013.

[19]Babbar-Sebensa M, Minskerb B S. Interactive genetic algorithm with mixed initiative interaction for multi-criteria ground water monitoring design[J]. Applied Soft Computing, 2012, 12: 182-195.

[20]Branke J, Schmidt C. Sequential Sampling in Noisy Environments[M]//Lecture Notes in Computer Science, Berlin: Springer, 2004: 202-211.

[21]Beyer H G. Actuator noise in recombinant evolution strategies on general quadratic fitness models[C]//Proceedings of Genetic and Evolutionary Computation Conf(GECCO2004), Seattle: Springer, 2004: 654-665.

[22]Jin Yaochu, Branke Jürgen. Evolutionary optimization in uncertain environments: A survey[J]. IEEE Transactions on Evolutionary Computation, 2005, 9(3): 303-317.

[23]Di Pietro A, While L. Applying evolutionary algorithms to problems with noisy, time-consuming fitness functions[C]. Proceedings of the 2004 Congress on Evolutionary Computation, Portland: [s.n.], 2004: 1254-1261.

Interactive genetic algorithm based on customer demand

DOURun-liang,GUOJun-peng,TIANXiang-long,ZONGChao

Collage of Management and Economics, Tianjin University， Tianjin 300072， China

s: To solve the problem of evaluation noise in the interactive genetic algorithm (IGA), the concept of hesitancy degree is put forward, hesitancy degree adjustment mechanism is set up, and the deletion strategy and modification strategy are applied to handle the unsatisfied individuals generated in the process of initial population generation, crossover and mutation. By emulating the concept design of car console, the interactive interface with humanization is established to validate the advance and rationality of the method system brought forward in the paper. The experiment shows that the IGA can effectively reduce the evaluation noise, speed up the convergence, lower the fatigue degree and increase users’ satisfaction about the result.

interactive genetic algorithm; hesitancy degree; evaluation noise; constraint handling; fatigue degree

2013-07-16；

2015-11-04.

國(guó)家自然科學(xué)基金資助項(xiàng)目(71201115).

竇潤(rùn)亮(1977—)， 男， 天津人， 博士， 副教授. Email： drl@tju.edu.cn

F49

A

1007-9807(2016)01-0024-11