基于云模型的粒編碼遺傳算法.pdf

1、隨著自然科學(xué)的不斷發(fā)展和現(xiàn)代科技的不斷進(jìn)步，最優(yōu)化問題的理論研究中涌現(xiàn)出許多高維、大規(guī)模、優(yōu)化難度高的優(yōu)化問題，如高維、多目標(biāo)、多模態(tài)函數(shù)優(yōu)化問題、旅行商問題(Traveling Salesman Problem，TSP)、0-1背包問題(Knapsack Problem)、裝箱問題(Bin Packing Problem)、調(diào)度問題(Scheduling Problem)、圖像平滑問題(Image Smoothing)、布林可滿足性問

2、題(Boolean Satisfiability Problem;SAT)等。與此同時(shí)，在實(shí)際應(yīng)用中的各個(gè)領(lǐng)域也相繼涌現(xiàn)出許多大規(guī)模、優(yōu)化難度高的最優(yōu)化問題，如最優(yōu)設(shè)計(jì)、最優(yōu)分配、最優(yōu)調(diào)度、大規(guī)模集成電路布線問題等。此時(shí)運(yùn)用傳統(tǒng)的優(yōu)化方法對(duì)以上優(yōu)化問題進(jìn)行求解很難獲得滿意的結(jié)果，甚至無法對(duì)這些問題進(jìn)行求解。因此，高效、性能好的優(yōu)化算法已經(jīng)成為學(xué)者、專家們的研究熱點(diǎn)。
　　 遺傳算法(Genetic Algorithm，GA)是2

3、0世紀(jì)70年代初由美國Michigan大學(xué)Holland教授提出的一種借鑒生物體自然選擇和遺傳機(jī)制的隨機(jī)搜索算法，由于遺傳算法較以往傳統(tǒng)的搜索算法具有使用方便、魯棒性強(qiáng)、便于并行處理等特點(diǎn)，因而廣泛應(yīng)用于函數(shù)優(yōu)化、生產(chǎn)調(diào)度問題、組合優(yōu)化、結(jié)構(gòu)設(shè)計(jì)、圖像處理、自動(dòng)控制、人工智能等領(lǐng)域。
　　 傳統(tǒng)遺傳算法在優(yōu)化高維、復(fù)雜函數(shù)問題時(shí)，存在易陷入局部最優(yōu)點(diǎn)、過早“早熟”、演化效率低等缺點(diǎn)。經(jīng)過分析，傳統(tǒng)遺傳算法易陷入局部最優(yōu)點(diǎn)的原因之

4、一是遺傳算子對(duì)個(gè)體的一次操作的結(jié)果是對(duì)解空間中一個(gè)特定點(diǎn)作用，而對(duì)該點(diǎn)鄰域的采樣密度影響不大。本文以實(shí)現(xiàn)對(duì)解空間某一鄰域進(jìn)行一定密度的采樣為目標(biāo)，采用粒編碼，使傳統(tǒng)遺傳算法中“點(diǎn)到點(diǎn)”的搜索變?yōu)椤傲５搅！钡拇至６人阉鬟^程，壓縮了編碼長度，使算法具有更高的演化效率。本文的主要工作為:
　　 (1)設(shè)計(jì)了一種以二進(jìn)制數(shù)為編碼、云為采樣機(jī)制的粒編碼方式。同時(shí)設(shè)計(jì)了粒編碼方式下個(gè)體的表現(xiàn)形式以及個(gè)體的評(píng)價(jià)方法。
　　 (2)設(shè)計(jì)

5、了粒信息保存策略和En非線性減小策略。粒信息保存策略為算法的設(shè)計(jì)和順利執(zhí)行奠定了基礎(chǔ);En非線性減小策略保證了算法在演化前期具有高的空間覆蓋度做全局搜索，演化中期從全局搜索向精確搜索過渡，演化后期做精確搜索，進(jìn)一步提高算法的收斂精度。
　　 (3)針對(duì)數(shù)值優(yōu)化問題，基于粒編碼方式，設(shè)計(jì)了遺傳算子和粒編碼遺傳算法。測(cè)試了GCGA的全局搜索能力和算法參數(shù)對(duì)GCGA性能的影響。高維和低維復(fù)雜函數(shù)的數(shù)值優(yōu)化實(shí)驗(yàn)表明，GCGA能夠跳出局部