史上最全I(xiàn)SIGHT優(yōu)化算法（2）

2016-10-24 by:CAE仿真在線來源:互聯(lián)網(wǎng)

ISIGHT軟件是一款高度智能的軟件機(jī)器人,為用戶提供了高效、全面、強(qiáng)大、豐富、快捷、靈活、方便的優(yōu)化集成平臺,可以和市面上絕大多數(shù)工程軟件、有限元分析軟件、三維軟件、辦公軟件、數(shù)值計算軟件、數(shù)據(jù)庫等進(jìn)行集成,實(shí)現(xiàn)產(chǎn)品設(shè)計、仿真、優(yōu)化的全流程,尤其是ISIGHT提供了非常全面的優(yōu)化算法,下面我們就來一探究竟!

ISIGHT的優(yōu)化算法分為四大類,分別為直接搜索法、梯度優(yōu)化算法、全局優(yōu)化算法、多目標(biāo)優(yōu)化算法,如下圖所示。每種類都提供了大量的高效優(yōu)化算法,各算法之間相互補(bǔ)充,各有所長,大大擴(kuò)展了ISIGHT的優(yōu)化能力。

全局優(yōu)化算法

優(yōu)勢:

適應(yīng)性強(qiáng):只評價設(shè)計點(diǎn),不計算任何函數(shù)的梯度;
具有全局性:能求解全局最優(yōu)解,避免了集中在局部區(qū)域的搜索;

缺點(diǎn):

相比數(shù)值優(yōu)化算法,全局探索法的計算量比較大;

l MIGA算法

Isight中的MIGA多島遺傳算法本質(zhì)上是日本Doshisha大學(xué)知識工程系(Department of KnowledgeEngineering)的M. Kaneko, M. Miki, T. Hiroyasu等人對并行分布遺傳算法(PDGAs, ParallelDistributed Genetic Algorithms)的改進(jìn),它具有比傳統(tǒng)遺傳算法更優(yōu)良的全局求解能力和計算效率。遺傳算法(GA,Genetic Algorithm)是Holland在60年代提出的,主要借助生物進(jìn)化過程中“適者生存”的規(guī)律,模仿生物進(jìn)化過程中的遺傳繁殖機(jī)制,對優(yōu)化問題解空間的個體進(jìn)行編碼(二進(jìn)制或其他進(jìn)制),然后對編碼后的個體種群進(jìn)行遺傳操作(如:選擇、交叉、變異等),通過迭代從新種群中尋找含有最優(yōu)解或較優(yōu)解的組合。

l ASA算法

模擬退火算法(Simulated Annealing,簡稱SA)和遺傳算法有很多相似之處,他們都需要從舊的設(shè)計點(diǎn)通過變異產(chǎn)生新的設(shè)計點(diǎn)。模擬退火算法比遺傳算法簡單,因?yàn)樗看卧谒阉骺臻g中只檢查一個設(shè)計點(diǎn),而遺傳算法檢查一組設(shè)計點(diǎn)(一個種群)。

SA的思想最早由Metropolis等提出,通過模擬退火過程,將組合優(yōu)化問題與統(tǒng)計力學(xué)中的熱平衡問題類比,從初始點(diǎn)開始每前進(jìn)一步就對目標(biāo)函數(shù)進(jìn)行一次評估,只要函數(shù)值下降,新的設(shè)計點(diǎn)就被接受,反復(fù)進(jìn)行,只到找到最優(yōu)點(diǎn)。函數(shù)值上升的點(diǎn)也可能被接受,這樣能夠避免找到的是局部最優(yōu)點(diǎn)。是否接受函數(shù)值上升點(diǎn)是依據(jù)Metropolis判據(jù)決定的,它是溫度的函數(shù),溫度高則更容易接受。伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解,即在局部優(yōu)解能概率性的跳出并最終趨于全局最優(yōu)。

SA對離散變量的組合優(yōu)化問題和連續(xù)變量函數(shù)的極小化問題都獲得了很大成功。經(jīng)過多年的研究,SA算法有多種改進(jìn)算法,比如:加溫退火法、記憶模擬退火法等。Isight中的ASA自適應(yīng)模擬退火算法是Ingber等人提出的改進(jìn)算法,它具有比傳統(tǒng)SA算法更優(yōu)良的全局求解能力和計算效率。

PSO算法

粒子群優(yōu)化(Particle SwarmOptimization, PSO),又稱微粒群算法,是由Kennedy和Eberhart等于1995年開發(fā)的一種演化計算技術(shù),最初是為了研究鳥群捕食的行為。PSO算法采用了演化計算的原則:1.從一組隨機(jī)種群開始初始化;2.通過更新種群代搜索最優(yōu)解;3.進(jìn)化依賴于前面的種群。

PSO采用粒子群在解空間中追隨最優(yōu)粒子進(jìn)行搜索,而不再有遺傳算法的交叉和變異操作。因此相對遺傳算法而言,PSO的優(yōu)勢在于簡單容易實(shí)現(xiàn),并且沒有太多參數(shù)需要調(diào)整。

l Pointer算法

Pointer優(yōu)化器是Isight提供的智能自動優(yōu)化專家。Pointer優(yōu)化器會自動捕捉設(shè)計空間的信息,自動組合四種優(yōu)化算法形成一個最優(yōu)的優(yōu)化策略,在一定給程度上大大降低了工程師的使用門檻,特別適合于那些對設(shè)計空間不太了解、對算法使用不太了解的設(shè)計者。

Pointer包括四個方法的組合:線性單純形法(linear simplex)、序列二次規(guī)劃法(sequential quadraticprogramming(SQP))、最速下降法(downhill simple)和遺傳算法(genetic algorithms)。

線性單純形法適合與解決線性問題;序列二次規(guī)劃法適合于解決光滑的問題,具有非常好的收斂性和數(shù)值穩(wěn)定性;最速下降法適合于非光滑的問題,它一般從約束邊界開始計算,而且具有非常高的效率;遺傳算法適合于全局的,非光滑的,不連續(xù)的優(yōu)化問題,但是它的計算比較耗時。

多目標(biāo)優(yōu)化算法

優(yōu)勢:

能夠?qū)Χ嗄繕?biāo)函數(shù)的優(yōu)化問題給出有效的優(yōu)化解;
可對凹陷解集進(jìn)行有效求解;

缺點(diǎn):

有些情況下,非劣解較多,不好選擇;
一般優(yōu)化時間較長;

NSGA-II算法

NSGA-Ⅱ,作為1994年發(fā)布的NSGA(Non-Dominated Sorting Genetic Algorithm)的改良版,由K.Ded,S.Agrawal等在2000年提出。NSGA-Ⅱ優(yōu)點(diǎn)在于探索性能良好。在非支配排序中,因?yàn)榻咏黀areto前沿的個體被選擇,使Pareto前進(jìn)能力增強(qiáng)。

導(dǎo)入了“擁擠距離”和“擁擠距離排序”的方法,在具有同樣的Pareto順序的層內(nèi),可以對個體進(jìn)行排序,稱為擁擠距離排序。擁擠距離排序中不會削除frontier的端頭部分,所以Pareto前沿不會收束一部分的領(lǐng)域里。

進(jìn)化過程中,將當(dāng)前父代群體進(jìn)行交叉和變異得到子群體,將兩個群體合并。在目標(biāo)空間中按照Pareto最優(yōu)關(guān)系將群體中個體兩兩按其目標(biāo)函數(shù)向量進(jìn)行比較,將群體中所有個體分成多個依次控制的前沿層。在屬于不同的Pareto層的情況下,利用評價Pareto優(yōu)越性來評價個體的優(yōu)劣。屬于同一個Pareto層的個體,具有更大的擁擠距離的個體更優(yōu)秀。

在NSGA-Ⅱ中,作為交叉和突然變異的運(yùn)算機(jī)制使用叫做SBX(Simulated Binary crossover)的方法。根據(jù)SBX方法生成子個體:交叉運(yùn)算。

NCGA算法

NCGA方法是由最早的GA(GeneticAlgorithm)算法發(fā)展而來,它視各目標(biāo)同等重要,通過排序后分組進(jìn)行交叉的方法實(shí)現(xiàn)“相鄰繁殖”的機(jī)制,從而使接近于Pareto前沿的解進(jìn)行交叉繁殖的概率增大,加速了計算收斂過程。NCGA步驟如下:

第1步初始化:令t=0,,設(shè)置第一代個體P0,種群數(shù)為N,計算個體對應(yīng)的適應(yīng)值函數(shù),計為A;

第2步另t=t+1,Pt=At-1

第3步排序:個體Pt按向聚集的目標(biāo)值的方向進(jìn)行排序;

第4步分組:個體Pt根據(jù)上述排序分為若干組,每組由兩個個體組成;

第5步交叉和變異:在每一組中執(zhí)行交叉和變異操作,由兩個父代個體產(chǎn)生兩個子代個體,同時父代個體被刪除;

第6步重組:所有子代個體組成一組新的Pt;

第7步更新:將At-1與Pt組合,按環(huán)境選擇(Envirment selection)機(jī)制,從2N個個體中,選出其中的N個個體;

第8步終止:如果滿足終止條件,則終止優(yōu)化程序,否則返回至第2步。

AMGA算法

AMGA算法在進(jìn)化過程之外設(shè)立一個存檔(Archive),用于保存進(jìn)化過程中的非支配個體及相應(yīng)的多目標(biāo)函數(shù)值,方法如下:

1. 通過支配關(guān)系選擇出當(dāng)前代種群X(t)中的非支配個體X*;
2. 將X*與檔案A(t)中的個體放在一起進(jìn)行比較:若X*被檔案A(t)中的個體所支配,則X*不能進(jìn)入檔案A(t);若X*與檔案A(t)中的個體無支配關(guān)系,則X*進(jìn)入檔案;若X*支配檔案A(t)中的某些個體,則X*進(jìn)入檔案,并剔除那些被支配的個體。檔案A(t)中的個體在進(jìn)化過程中保持支配地位。
3. 當(dāng)準(zhǔn)則終止時,檔案A(t)中的解集即為所要求的Pareto最優(yōu)解集的近似解集。
l PE算法

由于傳統(tǒng)多目標(biāo)遺傳算法(包括NSGA-II、NCGA、AMGA等)在整個設(shè)計空間搜索Pareto最優(yōu)解,需要通過大量的迭代獲得高精度的Pareto前沿,從而限制了其解決復(fù)雜、大規(guī)模多目標(biāo)優(yōu)化問題的能力。

PE算法(ParetoExplorer)是樹優(yōu)公司和美國eArtius公司聯(lián)合為Isight開發(fā)的高效全局多目標(biāo)探索算法組件。PE算法包含的四個子算法,其中的HMGE算法是由遺傳算法和梯度算法兩部分構(gòu)成的全局優(yōu)化策略:首先,用多目標(biāo)遺傳算法獲得非支配解集,然后對每一個非支配解,尋找能夠同時改進(jìn)所有目標(biāo)函數(shù)的梯度方向(多目標(biāo)梯度探索法MGE,Multi-GradientExploration)繼續(xù)精確收斂到局部Pareto解。

開放分享：優(yōu)質(zhì)有限元技術(shù)文章,助你自學(xué)成才