求解隱式目標優(yōu)化問題的交互式進化算法研究.pdf

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

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

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

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

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

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

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