粗粒度并行遺傳算法的計算性能及其應(yīng)用研究.pdf

1、遺傳算法是一種隨機(jī)性的全局優(yōu)化算法。粗粒度并行遺傳算法作為遺傳算法的一個重要改進(jìn)型，具有比經(jīng)典遺傳算法更好的計算性能，可以比較有效地平衡未成熟收斂和局部收斂速度過慢這對矛盾。本文主要討論粗粒度并行遺傳算法。 作為一種啟發(fā)式搜索算法，遺傳算法的計算結(jié)果具有不穩(wěn)定性和不可重現(xiàn)性?，F(xiàn)在學(xué)術(shù)界對遺傳算法中的某些遺傳操作的作用機(jī)制還不十分清楚，遺傳算法的許多性能特點(diǎn)無法在數(shù)學(xué)上嚴(yán)格證明。遺傳算法的計算過程也會受到各種隨機(jī)因素的影響。但是大

2、量的實(shí)際計算表明，遺傳算法的計算結(jié)果具有一定的規(guī)律性，在統(tǒng)計意義上具有一定的可靠性。 本文采用了對同一參數(shù)組合進(jìn)行多次重復(fù)計算的方法，提高實(shí)證分析的準(zhǔn)確性和可信度。多次重復(fù)計算所得的最優(yōu)解的均方差和產(chǎn)生這些最優(yōu)解的代數(shù)的平均值來評價計算結(jié)果的穩(wěn)定性和收斂性。通過遺傳算法和隨機(jī)遍歷搜索算法的對比分析，評價遺傳算法的計算效率。 通過對多個具有不同典型數(shù)學(xué)特性的經(jīng)典測試函數(shù)進(jìn)行實(shí)際計算以及計算結(jié)果的對比分析，得到了遺傳算法計算

3、性能的特點(diǎn)和最佳參數(shù)設(shè)置的相關(guān)結(jié)論；通過從統(tǒng)計學(xué)角度對多次重復(fù)計算的結(jié)果進(jìn)行分析，得到了遺傳算法的穩(wěn)定性和可信度方面的相關(guān)結(jié)論，這說明可以利用分析遺傳算法及其改進(jìn)型求解解析問題的計算效果所得到的結(jié)論，使遺傳算法在求解復(fù)雜的大型實(shí)際工程優(yōu)化問題時獲得更好的計算效果。 為了改善變異操作的性能，本文提出了三種不同的思路共六種具體實(shí)施方法對遺傳算法的變異操作進(jìn)行改進(jìn)。實(shí)證分析表明這六種改進(jìn)方法的計算結(jié)果都明顯優(yōu)于不采用任何改進(jìn)措施的經(jīng)典遺

4、傳算法，其中每隔一定進(jìn)化代數(shù)再隨機(jī)產(chǎn)生新個體的方法為最優(yōu)。 對粗粒度并行遺傳算法的子種群個數(shù)、種群規(guī)模和進(jìn)化代數(shù)進(jìn)行了實(shí)證分析，總結(jié)出這三個參數(shù)對算法的計算效果和計算效率的實(shí)際影響的結(jié)論。并通過與經(jīng)典遺傳算法的計算結(jié)果的比較和分析，論證了粗粒度并行遺傳算法擁有較為理想的計算結(jié)果和運(yùn)行過程，具有較高的種群多樣性和計算穩(wěn)定性。 對同步遷移和異步遷移這兩種遷移方式進(jìn)行了統(tǒng)一描述，并對同步遷移和不同參數(shù)設(shè)置的異步遷移的具體計算性

5、能進(jìn)行了實(shí)證分析。計算結(jié)果表明：同步遷移作為異步遷移的一種特例，既不是異步遷移中最優(yōu)的形式，也不是最差的形式；想要使算法達(dá)到最佳的計算效果，關(guān)鍵在于基礎(chǔ)遷移間隔和遷移概率這兩個參數(shù)的設(shè)置；單峰問題比多峰問題更適合采取同步遷移方式。 本文對各子種群使用不同參數(shù)設(shè)置的改進(jìn)型粗粒度并行遺傳算法進(jìn)行了討論和實(shí)證分析，這種經(jīng)過改進(jìn)的新方法通過提高各個子種群之間進(jìn)化行為的差別來提高整個種群的多樣性，使粗粒度并行遺傳算法能真正達(dá)到不同子種群搜

6、索不同的局部最優(yōu)解的目的，提高了粗粒度并行遺傳算法的種群多樣性和計算性能。實(shí)算顯示這種改進(jìn)具有實(shí)際效果，對多峰問題效果尤為明顯。以往為了提高應(yīng)用遺傳算法求解實(shí)際工程優(yōu)化問題的計算性能所采取的措施都必須了解待求解問題的具體特性后，才能找到合適的進(jìn)化策略設(shè)定方法，這種改進(jìn)的新型粗粒度并行遺傳算法可以避免這種缺陷，為求解實(shí)際工程優(yōu)化問題帶來了方便，提高了遺傳算法的實(shí)用性和可行性。 用粗粒度并行遺傳算法對瀾滄江上的梯級水電站的短期調(diào)度問

7、題這一實(shí)際案例進(jìn)行求解計算。本文首先對問題建模，根據(jù)遺傳算法的特點(diǎn)對模型進(jìn)行變換，然后利用已得到的進(jìn)化策略設(shè)定方法用粗粒度并行遺傳算法對模型進(jìn)行優(yōu)化求解，并對計算結(jié)果進(jìn)行分析討論。通過對工程實(shí)際問題的求解，說明粗粒度并行遺傳算法可以很好地解決工程實(shí)際問題，特別是對于需要對不同初始數(shù)據(jù)進(jìn)行多次求解的模型，遺傳算法是具有優(yōu)勢的。 通過本文中的實(shí)證分析研究，為使用遺傳算法對大型復(fù)雜的工程實(shí)際問題進(jìn)行計算提供了進(jìn)化策略設(shè)定方法的參照依據(jù)