求解隱式目標(biāo)優(yōu)化問(wèn)題的交互式進(jìn)化算法研究.pdf

1、隱式目標(biāo)優(yōu)化問(wèn)題是指優(yōu)化目標(biāo)不能用明確的數(shù)學(xué)函數(shù)表達(dá)的最優(yōu)化問(wèn)題?，F(xiàn)實(shí)生活中的許多問(wèn)題都可以看成隱式目標(biāo)優(yōu)化問(wèn)題，例如服裝設(shè)計(jì)、音樂(lè)創(chuàng)作、圖像檢索等。這類問(wèn)題的優(yōu)化目標(biāo)一般是“滿足人的某種需求”，往往涉及到人的偏好、直覺、經(jīng)驗(yàn)、價(jià)值觀、信仰等因素，因此難以量化。交互式進(jìn)化算法是一種基于人的主觀評(píng)價(jià)得到個(gè)體適應(yīng)值的進(jìn)化優(yōu)化方法。作為解決隱式目標(biāo)優(yōu)化問(wèn)題的主要方法，交互式進(jìn)化算法得到了國(guó)內(nèi)外許多學(xué)者的廣泛關(guān)注。由于交互式進(jìn)化算法中加入了人的

2、因素，因此如何減輕用戶疲勞并增強(qiáng)算法的求解效率，是一個(gè)十分迫切而有意義的課題。
　　 本論文從三個(gè)方面對(duì)交互式進(jìn)化算法進(jìn)行了深入的研究與探索，包括：用戶交互方式研究、多用戶交互式進(jìn)化算法研究、交互式PBIL算法研究。具體而言，本論文的主要研究?jī)?nèi)容包括：
　　 (1)提出一種基于錦標(biāo)賽選擇的用戶評(píng)估方式。該評(píng)估方式既減輕了傳統(tǒng)的評(píng)分賦值方式給用戶帶來(lái)的心理壓力，又避免了基于兩個(gè)體對(duì)比的評(píng)估方式所需要的大量比較次數(shù)。當(dāng)用戶采

3、用該評(píng)估方式對(duì)交互式進(jìn)化算法中的個(gè)體進(jìn)行評(píng)估時(shí)，首先，需要將種群劃分為若干子種群；然后，用戶選擇出每個(gè)子種群中的優(yōu)勝個(gè)體；接著，這些優(yōu)勝個(gè)體參與下一輪的錦標(biāo)賽。如此循環(huán)，直到選擇出最后的優(yōu)勝個(gè)體。此時(shí)，個(gè)體的適應(yīng)值為該個(gè)體在錦標(biāo)賽樹中的高度。我們將基于錦標(biāo)賽選擇評(píng)估方式的交互式遺傳算法應(yīng)用于服裝色彩優(yōu)化系統(tǒng)，研究了種群規(guī)模和子種群規(guī)模的選擇對(duì)算法性能的影響。然后，將該算法與基于兩個(gè)體對(duì)比的交互式遺傳算法進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明本文提出的算

4、法在選擇合適的子種群規(guī)模的情況下，能有效地減少用戶的比較次數(shù)和算法收斂時(shí)間，從而減輕用戶疲勞。
　　 (2)提出一種用戶動(dòng)態(tài)干預(yù)進(jìn)化過(guò)程的操作——子染色體固定操作。這種操作能夠防止進(jìn)化過(guò)程中出現(xiàn)的優(yōu)秀的基因片段被交叉算子和變異算子破壞，而且能夠極大地縮小問(wèn)題的搜索空間。由于引入了子染色體固定操作，傳統(tǒng)的交叉和變異算子都可能失效，為此，我們給出了改進(jìn)的交叉和變異算子。為驗(yàn)證子染色體固定操作的有效性，我們將基于子染色體固定操作的交互

5、式遺傳算法和傳統(tǒng)的交互式遺傳算法分別應(yīng)用于服裝設(shè)計(jì)系統(tǒng)，進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明：子染色體固定操作能夠加快交互式進(jìn)化算法的收斂速度并提高設(shè)計(jì)結(jié)果的質(zhì)量。
　　 (3)提出一種能滿足大眾化需求的多用戶交互式遺傳算法模型。該模型用群體評(píng)估代替單用戶評(píng)估，即個(gè)體適應(yīng)度的評(píng)估取決于多個(gè)用戶的評(píng)估結(jié)果，而不是取決于單個(gè)用戶。給出了算法的三個(gè)主要模塊——種群初始化模塊、單種群模塊和多種群模塊的詳細(xì)設(shè)計(jì)。最后，將多用戶交互式遺傳算法和一般

6、的單用戶交互式遺傳算法分別應(yīng)用于服裝設(shè)計(jì)系統(tǒng)進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明：多用戶交互式遺傳算法的設(shè)計(jì)結(jié)果能更好地滿足多個(gè)用戶的偏好和要求，因而能更好地滿足大眾化需求。
　　 (4)首次將基于群體的增量學(xué)習(xí)(Population-based Incremental Learning，PBIL)算法應(yīng)用于解決隱式目標(biāo)優(yōu)化問(wèn)題，提出了交互式PBIL(IPBIL)算法。IPBIL相對(duì)于傳統(tǒng)的交互式進(jìn)化算法的最大優(yōu)勢(shì)在于：其用戶評(píng)估方式大大簡(jiǎn)化

7、。IPBIL僅需要用戶從種群中選擇出最優(yōu)個(gè)體，而不需要用戶對(duì)每個(gè)個(gè)體都進(jìn)行評(píng)估。將IPBIL和IGA分別應(yīng)用于服裝設(shè)計(jì)問(wèn)題，進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明：雖然IPBIL比IGA需要更多的進(jìn)化代數(shù)才能達(dá)到收斂，但是IPBIL收斂時(shí)的時(shí)間消耗和鼠標(biāo)點(diǎn)擊數(shù)均大大小于IGA，因而能夠顯著減輕用戶疲勞。
　　 (5)為解決多峰隱式目標(biāo)優(yōu)化問(wèn)題，在IPBIL算法基礎(chǔ)上，進(jìn)一步提出基于多概率向量的交互式PBIL(IPBIL with Multipl