編者按：本文主要從單親演化過程；群體演化過程；實(shí)驗(yàn)結(jié)果與分析；結(jié)束語四個方面進(jìn)行論述。其中，主要包括：TSP的搜索空間是有限的、很可能不存在確定的算法能在多項(xiàng)式時(shí)間內(nèi)求到問題的解、遺傳算法是一種借鑒生物界自然選擇和遺傳機(jī)制的隨機(jī)化搜索算法、用遺傳算法求解TSP能得到令人滿意的結(jié)果、個體質(zhì)量的高低決定了算法的全局性能、TSP編碼表示、構(gòu)建TSP基因庫、單親演化算法、基因段錯位操作是隨機(jī)確定基因段、交叉算子、局部啟發(fā)式算子、選擇機(jī)制和收斂準(zhǔn)則、基于多重搜索策略的群體演化算法、所有的結(jié)果都是在P42.0G微機(jī)上完成、該文算法的求解質(zhì)量要優(yōu)于GA、PGA、MMGA算法等，具體材料請?jiān)斠姟?/p>

論文摘要：TSP是組合優(yōu)化問題的典型代表,該文在分析了遺傳算法的特點(diǎn)后,提出了一種新的遺傳算法(GB—MGA),該算法將基因庫和多重搜索策略結(jié)合起來,利用基因庫指導(dǎo)單親遺傳演化的進(jìn)化方向,在多重搜索策略的基礎(chǔ)上利用改進(jìn)的交叉算子又增強(qiáng)了遺傳算法的全局搜索能力。通過對國際TSP庫中多個實(shí)例的測試,結(jié)果表明:算法(GB—MGA)加快了遺傳算法的收斂速度,也加強(qiáng)了算法的尋優(yōu)能力。

論文關(guān)鍵詞：旅行商問題遺傳算法基因庫多重搜索策略

TSP(travelingsalesmanproblem)可以簡述為:有n個城市1,2,…,n,一旅行商從某一城市出發(fā),環(huán)游所有城市后回到原出發(fā)地,且各城市只能經(jīng)過一次,要求找出一條最短路線。TSP的搜索空間是有限的,如果時(shí)間不受限制的話,在理論上這種問題終會找到最優(yōu)解,但對于稍大規(guī)模的TSP,時(shí)間上的代價(jià)往往是無法接受的。這是一個典型的組合最優(yōu)化問題,已被證明是NP難問題,即很可能不存在確定的算法能在多項(xiàng)式時(shí)間內(nèi)求到問題的解[1]。由于TSP在工程領(lǐng)域有著廣泛的應(yīng)用,如貨物運(yùn)輸、加工調(diào)度、網(wǎng)絡(luò)通訊、電氣布線、管道鋪設(shè)等,因而吸引了眾多領(lǐng)域的學(xué)者對它進(jìn)行研究。TSP的求解方法種類繁多,主要有貪婪法、窮舉法、免疫算法[2]、螞蟻算法[3]、模擬退火算法、遺傳算法等。

遺傳算法是一種借鑒生物界自然選擇和遺傳機(jī)制的隨機(jī)化搜索算法,其主要特點(diǎn)是群體搜索策略和群體中個體之間的信息交換,搜索不依賴于梯度信息[4]。遺傳算法主要包括選擇、交叉和變異3個操作算子,它是一種全局化搜索算法,尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問題。遺傳算法雖然不能保證在有限的時(shí)間內(nèi)獲得最優(yōu)解,但隨機(jī)地選擇充分多個解驗(yàn)證后,錯誤的概率會降到可以接受的程度。

用遺傳算法求解TSP能得到令人滿意的結(jié)果,但是其收斂速度較慢,而且種群在交叉算子作用下,會陷入局部解。采用局部啟發(fā)式搜索算法等,雖然能在很短的時(shí)間內(nèi)計(jì)算出小規(guī)模城市的高質(zhì)量解,一旦城市規(guī)模稍大就容易陷入局部最優(yōu)解。因此,為了能夠加快遺傳算法的收斂速度,又能得到更好的近似最優(yōu)解,該文采納了文[5]中楊輝提出的基因庫的想法,并結(jié)合文[6]中Cheng-FaTsai提出的多重搜索策略思想,使用單親演化與群體演化相結(jié)合的方式來求解TSP問題。該文根據(jù)文[7]中最小生成樹MST(minimumcostspanningtree)的應(yīng)用,由MST建立TSP的基因庫,保存有希望成為最優(yōu)解的邊,利用基因庫提高初始群體的質(zhì)量進(jìn)行單親演化,然后利用改進(jìn)后的交叉算子和的多重搜索策略進(jìn)行群體演化。

遺傳算法的思想由來已久。早在20世紀(jì)50年代，一些生物學(xué)家就著手于計(jì)算機(jī)模擬生物的遺傳系統(tǒng)。1967年，美國芝加哥大學(xué)的Holland,J.H.教授在研究適應(yīng)系統(tǒng)時(shí)，進(jìn)一步涉及進(jìn)化演算的思考，并于1968年提出模式理論。1975年，Holland教授的專著《自然界和人工系統(tǒng)的適應(yīng)性》問世，全面地介紹了遺傳算法，為遺傳算法奠定了基礎(chǔ)[228]。此后，遺傳算法無論在理論研究方面，還是實(shí)際應(yīng)用方面都有了長足發(fā)展。

伴隨遺傳算法的發(fā)展，其獨(dú)特的優(yōu)越性逐漸被體現(xiàn)出來，且各種理論、方法都得到了進(jìn)一步發(fā)展和完善。但是，遺傳算法的實(shí)際應(yīng)用仍然存在著缺陷，具體表現(xiàn)在：

遺傳算法在尋優(yōu)過程中易出現(xiàn)“早熟”、設(shè)計(jì)變量增多時(shí)效率較低以及結(jié)構(gòu)分析時(shí)間長，在線功能差。為此，在實(shí)際運(yùn)用中尚需改進(jìn)，尋找更優(yōu)秀的算子和編碼方法等。目前，改進(jìn)的方法也各有優(yōu)劣，有對遺傳算法遺傳算子進(jìn)行改進(jìn)的，也有將遺傳算法與其他方法結(jié)合起來的。編碼方法有二進(jìn)制編碼、多值編碼、實(shí)值編碼、區(qū)間值編碼、Delta編碼等多種編碼方法。在執(zhí)行策略方面有如下幾種方法值得注意：遺傳算法與模擬退火算法的結(jié)合、遺傳算法與局部優(yōu)化方法的結(jié)合、并行遺傳算法、共存演化遺傳算法、混亂遺傳算法。

遺傳算法的噪聲適應(yīng)性問題。遺傳算法主要是針對無噪聲的確定性環(huán)境設(shè)計(jì)的，在應(yīng)用過程中，知識的不確定性、訓(xùn)練樣本的錯誤、人為因素等都可導(dǎo)致問題求解環(huán)境包含一個或多個噪聲。事實(shí)上，噪聲是不可避免的，在實(shí)際工程測量中，測量得到的靜態(tài)應(yīng)變常常會伴有一定的噪聲。遺傳算法的進(jìn)化過程是通過適應(yīng)度大小來進(jìn)行選擇、變異、交*等遺傳算子操作，從而對個體進(jìn)行優(yōu)勝劣汰。然而在噪聲環(huán)境下，目標(biāo)函數(shù)或適應(yīng)度帶有噪聲，不能反映個體真正的適應(yīng)度。顯然，用有噪聲的適應(yīng)度去進(jìn)化，其結(jié)果可能會被誤導(dǎo)。在這種情況下，遺傳算法的性能如何，怎樣改進(jìn)，還有待深入研究。

摘要本文通過對基本遺傳算法添加初始化啟發(fā)信息、改進(jìn)交叉算子和利用本身所固有的并行性構(gòu)架粗粒度并行遺傳算法等方法提高了遺傳算法的收斂性及其尋優(yōu)能力。

關(guān)鍵詞遺傳算法；TSP；交叉算子

1引言

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法?？偟恼f來，遺傳算法是按不依賴于問題本身的方式去求解問題。它的目標(biāo)是搜索這個多維、高度非線性空間以找到具有最優(yōu)適應(yīng)值(即最小費(fèi)用的)的點(diǎn)[1]。

基本遺傳算法是一個迭代過程，它模仿生物在自然環(huán)境中的遺傳和進(jìn)化機(jī)理，反復(fù)將選擇算子、交叉算子和變異算子作用于種群，最終可得到問題的最優(yōu)解和近似最優(yōu)解。

2遺傳算法程序設(shè)計(jì)改進(jìn)比較

1遺傳算法設(shè)計(jì)

1．1基因編碼設(shè)計(jì)

編碼就是將遺傳算法中處理不了的空間參數(shù)轉(zhuǎn)換成遺傳空間的由基因組成的染色體或個體的過程．其中基因在一定意義上包含了它所代表的問題的解．基因的編碼方式有很多，這也取決于要解決的問題本身．常見的編碼方式有：二進(jìn)制編碼，基因用0或1表示，通常用于解決01背包問題，如基因A：00100011010（代表一個個體的染色體）；互換編碼，主要用于解決排序問題，如調(diào)度問題和旅行商問題，用一串基因編碼來表示遍歷城市順序，如234517986，表示在9個城市中先經(jīng)過城市2，再經(jīng)過城市3，依此類推；樹形編碼，用于遺傳規(guī)劃的演化編程或表示，其編碼的方法就是樹形結(jié)構(gòu)中的一些函數(shù)，本文采用的是樹形編碼．

1．2交叉算子設(shè)計(jì)

交叉運(yùn)算的含義是參照某種方式和交叉概率，將兩組相互配對的個體互換部分基因，生成新個體的過程．交叉運(yùn)算在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法．交叉操作流程如圖1所示．交叉操作首先判定要交叉的基因是否相同，如果相同進(jìn)行子基因組的交叉，然后再判定交叉是否完成，沒完成就繼續(xù)，完成就退出；如果交叉的基因不相同，就要選擇是否依據(jù)概率進(jìn)行基因交換，選擇交換就交換其所有的次級基因結(jié)構(gòu)，然后再判定交叉是否完成，選擇不交換就直接判定交叉是否完成．

1．3變異算子設(shè)計(jì)

摘要：本文運(yùn)用遺傳算法的全局尋優(yōu)對考試中的自動化組卷進(jìn)行了研究，并得到了一個解決適合考方要求的試題模型的好的算法。

關(guān)鍵詞：遺傳算法全局尋優(yōu)自動化組卷

1引言

計(jì)算機(jī)輔助考試系統(tǒng)的自動組卷的效率與質(zhì)量完全取決于抽題算法的設(shè)計(jì)。如何設(shè)計(jì)一個算法從題庫中既快又好的抽出一組最佳解或是抽出一組非常接近最佳解的實(shí)體，涉及到一個全局尋優(yōu)和收斂速度快慢的的問題，很多學(xué)者對其進(jìn)行了研究。遺傳算法以其自適應(yīng)尋優(yōu)及良好的智能搜索技術(shù)，受到了廣泛的運(yùn)用。PottsJC等人基于變異和人工選擇的遺傳算法對最優(yōu)群體規(guī)模進(jìn)行了論述；HamiltonMA等結(jié)合遺傳算法把其運(yùn)用到神經(jīng)網(wǎng)絡(luò)中，并取得了良好的效果[4]；也有眾多的學(xué)者對保留最佳狀態(tài)的遺傳算法的收斂速度做了討論。通過理論推導(dǎo)和事實(shí)運(yùn)用，發(fā)現(xiàn)遺傳算法在尋優(yōu)和收斂性方面都是非常有效的。

本文結(jié)合遺傳算法的原理和思想，對考試自動出題組卷的問題進(jìn)行了研究，找到了一種獲得與考試試題控制指標(biāo)符合的試題模型的解決方法。

2問題描述

摘要在浮點(diǎn)編碼遺傳算法中加入Powell方法，構(gòu)成適于不可微函數(shù)全局優(yōu)化的混合遺傳算法?；旌纤惴ǜ纳屏诉z傳算法的局部搜索能力，顯著提高了遺傳算法求得全局解的概率。由于只利用函數(shù)值信息，混合算法是一種求解可微和不可微函數(shù)全局優(yōu)化問題的通用方法。

關(guān)鍵詞全局最優(yōu)；混合算法；遺傳算法；Powell方法

1引言

不可微非線性函數(shù)優(yōu)化問題具有廣泛的工程和應(yīng)用背景，如結(jié)構(gòu)設(shè)計(jì)中使得結(jié)構(gòu)內(nèi)最大應(yīng)力最小而歸結(jié)為極大極小優(yōu)化（minmax）問題、數(shù)據(jù)魯棒性擬合中采取最小絕對值準(zhǔn)則建立失擬函數(shù)等。其求解方法的研究越來越受到人們的重視，常用的算法有模式搜索法、單純形法、Powell方法等，但是這些方法都是局部優(yōu)化方法，優(yōu)化結(jié)果與初值有關(guān)。

近年來，由Holland研究自然現(xiàn)象與人工系統(tǒng)的自適應(yīng)行為時(shí)，借鑒“優(yōu)勝劣汰”的生物進(jìn)化與遺傳思想而首先提出的遺傳算法，是一種較為有效的求不可微非線性函數(shù)全局最優(yōu)解的方法。以遺傳算法為代表的進(jìn)化算法發(fā)展很快，在各種問題的求解與應(yīng)用中展現(xiàn)了其特點(diǎn)和魅力，但是其理論基礎(chǔ)還不完善，在理論和應(yīng)用上暴露出諸多不足和缺陷，如存在收斂速度慢且存在早熟收斂問題[1,2]。為克服這一問題，早在1989年Goldberg就提出混合方法的框架[2]，把GA與傳統(tǒng)的、基于知識的啟發(fā)式搜索技術(shù)相結(jié)合，來改善基本遺傳算法的局部搜索能力，使遺傳算法離開早熟收斂狀態(tài)而繼續(xù)接近全局最優(yōu)解。近來，文獻(xiàn)[3]和[4]在總結(jié)分析已有發(fā)展成果的基礎(chǔ)上，均指出充分利用遺傳算法的大范圍搜索性能，與快速收斂的局部優(yōu)化方法結(jié)合構(gòu)成新的全局優(yōu)化方法，是目前有待集中研究的問題之一，這種混合策略可以從根本上提高遺傳算法計(jì)算性能。文獻(xiàn)[5]采用牛頓－萊佛森法和遺傳算法進(jìn)行雜交求解旅行商問題，文獻(xiàn)[6]把最速下降法與遺傳算法相結(jié)合來求解連續(xù)可微函數(shù)優(yōu)化問題，均取得良好的計(jì)算效果，但是不適于不可微函數(shù)優(yōu)化問題。

本文提出把Powell方法融入浮點(diǎn)編碼遺傳算法，把Powell方法作為與選擇、交叉、變異平行的一個算子，構(gòu)成適于求解不可微函數(shù)優(yōu)化問題的混合遺傳算法，該方法可以較好解決遺傳算法的早熟收斂問題。數(shù)值算例對混合方法的有效性進(jìn)行了驗(yàn)證。

摘要在浮點(diǎn)編碼遺傳算法中加入Powell方法，構(gòu)成適于不可微函數(shù)全局優(yōu)化的混合遺傳算法?；旌纤惴ǜ纳屏诉z傳算法的局部搜索能力，顯著提高了遺傳算法求得全局解的概率。由于只利用函數(shù)值信息，混合算法是一種求解可微和不可微函數(shù)全局優(yōu)化問題的通用方法。

關(guān)鍵詞全局最優(yōu)；混合算法；遺傳算法；Powell方法

1引言

不可微非線性函數(shù)優(yōu)化問題具有廣泛的工程和應(yīng)用背景，如結(jié)構(gòu)設(shè)計(jì)中使得結(jié)構(gòu)內(nèi)最大應(yīng)力最小而歸結(jié)為極大極小優(yōu)化（minmax）問題、數(shù)據(jù)魯棒性擬合中采取最小絕對值準(zhǔn)則建立失擬函數(shù)等。其求解方法的研究越來越受到人們的重視，常用的算法有模式搜索法、單純形法、Powell方法等，但是這些方法都是局部優(yōu)化方法，優(yōu)化結(jié)果與初值有關(guān)。

近年來，由Holland研究自然現(xiàn)象與人工系統(tǒng)的自適應(yīng)行為時(shí)，借鑒“優(yōu)勝劣汰”的生物進(jìn)化與遺傳思想而首先提出的遺傳算法，是一種較為有效的求不可微非線性函數(shù)全局最優(yōu)解的方法。以遺傳算法為代表的進(jìn)化算法發(fā)展很快，在各種問題的求解與應(yīng)用中展現(xiàn)了其特點(diǎn)和魅力，但是其理論基礎(chǔ)還不完善，在理論和應(yīng)用上暴露出諸多不足和缺陷，如存在收斂速度慢且存在早熟收斂問題[1,2]。為克服這一問題，早在1989年Goldberg就提出混合方法的框架[2]，把GA與傳統(tǒng)的、基于知識的啟發(fā)式搜索技術(shù)相結(jié)合，來改善基本遺傳算法的局部搜索能力，使遺傳算法離開早熟收斂狀態(tài)而繼續(xù)接近全局最優(yōu)解。近來，文獻(xiàn)[3]和[4]在總結(jié)分析已有發(fā)展成果的基礎(chǔ)上，均指出充分利用遺傳算法的大范圍搜索性能，與快速收斂的局部優(yōu)化方法結(jié)合構(gòu)成新的全局優(yōu)化方法，是目前有待集中研究的問題之一，這種混合策略可以從根本上提高遺傳算法計(jì)算性能。文獻(xiàn)[5]采用牛頓－萊佛森法和遺傳算法進(jìn)行雜交求解旅行商問題，文獻(xiàn)[6]把最速下降法與遺傳算法相結(jié)合來求解連續(xù)可微函數(shù)優(yōu)化問題，均取得良好的計(jì)算效果，但是不適于不可微函數(shù)優(yōu)化問題。

本文提出把Powell方法融入浮點(diǎn)編碼遺傳算法，把Powell方法作為與選擇、交叉、變異平行的一個算子，構(gòu)成適于求解不可微函數(shù)優(yōu)化問題的混合遺傳算法，該方法可以較好解決遺傳算法的早熟收斂問題。數(shù)值算例對混合方法的有效性進(jìn)行了驗(yàn)證。

摘要：遺傳算法是根據(jù)生物學(xué)上的染色體基因因子構(gòu)成機(jī)制而產(chǎn)生的一種啟發(fā)式算法。該算法以群體中的所有個體為對象，通過選擇、交叉、變異和重排序等類似生物遺傳的操作算子，得到滿足一定群體適應(yīng)度的新種群。遺傳算法為頻率分配問題提供了解決途徑。

關(guān)鍵字：頻率分配遺傳算法GECP組合優(yōu)化

1.通信網(wǎng)頻率分配問題的背景

無線通信設(shè)備之間通過相互發(fā)射電磁波達(dá)成信息溝通。相互通信的設(shè)備之間使用特定的頻率（信道）構(gòu)成無線通信鏈路。由于電磁波的自然特性，無線通信設(shè)備發(fā)射的電磁波可能對位于附近、滿足一定功率和頻率條件的其它設(shè)備形成干擾。頻率分配（FAP）的目的就是給工作在一定地域內(nèi)的無線通信設(shè)備指定使用的工作頻率(或信道)，使所有設(shè)備都以盡量小的概率被干擾，從而使整個網(wǎng)絡(luò)的可用性得到優(yōu)化。FAP可以描述為：對N個給定的待分配工作頻率的鏈路，設(shè)G={S1,S2,…Sn}為所有狀態(tài)構(gòu)成的解空間，C(si)為狀態(tài)si對應(yīng)的目標(biāo)函數(shù)值，尋找最優(yōu)解s*，使任意si∈G，C(s*)=minC（si）。因此FAP是一種組合優(yōu)化問題。

具體設(shè)備頻率分配方法雖然會隨著設(shè)備的工作方式（單工、雙工）、工作頻段、天線類型、信號的調(diào)制解調(diào)方式的不同而有所區(qū)別，但是大部分頻率分配算法都可以轉(zhuǎn)換為等價(jià)的圖的邊著色問題。從圖論算法理論上講，圖的廣義邊著色問題是NPC問題[7]，也就是說無法在多項(xiàng)式時(shí)間內(nèi)求得問題的最優(yōu)解。例如對于存在n條邊的無向圖，使用c種顏色對其著色，在沒有其它約束條件下，其解空間是cn。即使在不考慮顏色重復(fù)使用（c>n）的情況下，其解空間也達(dá)到n!。這兩者都是超越數(shù)，在c和n的值較大的情況下想利用窮舉搜索的方法求得問題的最優(yōu)解在時(shí)間上是不可行的。

在工程實(shí)踐中許多NPC問題使用一些使用的近似算法得到問題的可行解。這些方法包括[]：只對問題的特殊實(shí)例求解；動態(tài)規(guī)劃（DP）或者分支界限算法（BC）；概率算法；求近似解；啟發(fā)式算法（HeufisticAlgorithms）等。這些方法的和核心是分割問題的解空間，按照特定規(guī)則搜索典型解作為次最優(yōu)解。

論文摘要:將一種在在水質(zhì)評價(jià)中得到廣泛應(yīng)用的評價(jià)方法——投影尋蹤評價(jià)法引入生態(tài)城市評價(jià)領(lǐng)域中。采用基于實(shí)數(shù)遺傳算法的投影尋蹤評價(jià)法，以生態(tài)城市課題組建立的指標(biāo)體系(指標(biāo)涉及資源，經(jīng)濟(jì)，社會，環(huán)境，體制等各方面因素)為基礎(chǔ)，利用M棚AB軟件對石家莊市2000~~2007年的生態(tài)城市建設(shè)進(jìn)行了評價(jià)。

論文關(guān)鍵詞:投影尋蹤法；生態(tài)城市評價(jià)；石家莊市

“生態(tài)城市”是20世紀(jì)80年代產(chǎn)生的一個全新概念，指將“生態(tài)系統(tǒng)”思想引入到城市建設(shè)和管理的過程中。它最早是由前蘇聯(lián)生態(tài)學(xué)家0．Yanitsky1971年在聯(lián)合國教科文組織發(fā)起“人與生物圈計(jì)劃(MAB)”時(shí)提出的。之后，很多學(xué)者都對其進(jìn)行了研究，并給出了定義。如1984年城市生態(tài)學(xué)家0．Yanistky提出，生態(tài)城市是指自然、技術(shù)、人文充分融合，物質(zhì)、能量、信息高效利用，人的創(chuàng)造力和生產(chǎn)力得到最大限度的發(fā)揮，居民的身心健康和環(huán)境質(zhì)量得到維護(hù)，一種生態(tài)、高效、和諧的人類聚居新環(huán)境。美國生態(tài)學(xué)家R．Richard認(rèn)為，生態(tài)城市即生態(tài)健康的城市，是低污、緊湊、節(jié)能、充滿活力并與自然和諧共存的聚居地。雖然生態(tài)城市的概念尚處于不停的爭論、探索、修改、完善之中，但在原則問題上，人們已經(jīng)達(dá)成一些基本共識：“生態(tài)城市”的核心思想是它的區(qū)域整體觀和可持續(xù)發(fā)展的生態(tài)觀，且一般要求具有以下幾種特性：和諧性、高效性、持續(xù)性、整體性、區(qū)域性、結(jié)構(gòu)合理以及關(guān)系協(xié)調(diào)。

1生態(tài)城市測評方法概述

生態(tài)城市評價(jià)是生態(tài)城市建設(shè)的基礎(chǔ)工作，一套科學(xué)客觀的生態(tài)城市評價(jià)體系應(yīng)具備以下功能：①幫助在操作層次理解什么是生態(tài)城市；②使城市建設(shè)轉(zhuǎn)向生態(tài)城市建設(shè)；③衡量生態(tài)城市建設(shè)的趨勢和速度，綜合衡量生態(tài)城市各子系統(tǒng)的協(xié)調(diào)程度。

具體到測評方法而言，不同的測評方法從不同的角度描述指標(biāo)體系的屬性，由于各種方法的機(jī)理不同，方法的層次屬性相異，在應(yīng)用不同的測評方法時(shí)，測評的結(jié)果也存在差異。因此，要反映一個城市的全貌，體現(xiàn)上述生態(tài)城市的內(nèi)涵要求，必須從多角度、全方位進(jìn)行研究，這樣得出的結(jié)論才能體現(xiàn)城市系統(tǒng)的本質(zhì)和原貌。在數(shù)學(xué)分析方面，系統(tǒng)科學(xué)專家運(yùn)用定量分析技術(shù)開發(fā)了幾十種測評方法。目前，常用的主要有層次分析法(AnalyticHierarchyProcess，AHP)，因子分析法(FactorAnalysis，F(xiàn)A)以及網(wǎng)絡(luò)層次分析法(ANP)等。但是，這些方法都有其局限性。層次分析法對應(yīng)生態(tài)城市評價(jià)是不適用的，因?yàn)橹笜?biāo)之間是不完備、不互斥的；因子分析法是較常用且簡單的方法，能夠反映生態(tài)城市建設(shè)的大概狀況，但會丟失部分信息；網(wǎng)絡(luò)分析法能夠比因子分析法更全面地反映生態(tài)城市的概況，但其前提是各因子之間的關(guān)系比較清晰，這一過程需要作大量的研究工作。該文借鑒在水質(zhì)評價(jià)中得到廣泛應(yīng)用，并被實(shí)踐證明比較科學(xué)、合理的評價(jià)方法——投影尋蹤評價(jià)法，將其應(yīng)用到生態(tài)城市評價(jià)體系中。

摘要：復(fù)雜函數(shù)的全局最優(yōu)化問題是在求解各種復(fù)雜工程與科學(xué)計(jì)算問題中提煉出來的亟待解決的計(jì)算問題，均勻設(shè)計(jì)具有讓試驗(yàn)點(diǎn)在高維空間內(nèi)均勻分散的特點(diǎn)，而Powell算法具有很好的求解局部最優(yōu)解的能力，將兩種方法進(jìn)行有效改進(jìn)后使之相結(jié)合，設(shè)計(jì)出并行全局最優(yōu)化算法。通過經(jīng)典的全局最優(yōu)化函數(shù)對算法進(jìn)行了比較測試，發(fā)現(xiàn)該算法具有比以前的算法更好的尋優(yōu)能力，并對算法時(shí)間、空間復(fù)雜度以及并行性進(jìn)行分析和測試?；诰鶆蛟O(shè)計(jì)與Powell算法的全局最優(yōu)化并行算法具有尋優(yōu)能力強(qiáng)，時(shí)間開銷與問題因素個數(shù)的平方和布點(diǎn)數(shù)成線性復(fù)雜度，空間開銷與因素個數(shù)和布點(diǎn)數(shù)成線性復(fù)雜度，并行效率好的特點(diǎn)。

關(guān)鍵詞：并行計(jì)算；均勻設(shè)計(jì)；Powell算法；全局最優(yōu)化

0引言

最優(yōu)化理論方法是應(yīng)用數(shù)學(xué)的一門分支，研究決策問題的最佳選擇，構(gòu)造尋找最佳解的計(jì)算方法，探討這些計(jì)算方法的理論性質(zhì)及計(jì)算表現(xiàn)。目前，求解線性規(guī)劃、非線性規(guī)劃、隨機(jī)規(guī)劃、非光滑規(guī)劃、多目標(biāo)規(guī)劃、組合優(yōu)化等各種最優(yōu)化問題的新方法不斷涌現(xiàn)。除了自然科學(xué)的各個領(lǐng)域之外，在建筑設(shè)計(jì)、金融設(shè)計(jì)、醫(yī)藥設(shè)計(jì)、生產(chǎn)管理、交通運(yùn)輸?shù)戎T多方面均涉及最優(yōu)化的應(yīng)用。隨著高速計(jì)算機(jī)的普及和優(yōu)化方法的不斷進(jìn)步，規(guī)模越來越大的優(yōu)化問題得到解決。

面對最優(yōu)化問題，目前的困難主要表現(xiàn)在兩個方面：①目標(biāo)函數(shù)常常多峰，隨著優(yōu)化問題規(guī)模的增大，局部最優(yōu)解的數(shù)目將會迅速增加，往往得到的是局部最優(yōu)解，而不能得到全局最優(yōu)解。如何有效地跳出局部最優(yōu)點(diǎn)而又不大幅度地增加計(jì)算代價(jià)，是目前的一個難題。②許多在串行計(jì)算環(huán)境下的最優(yōu)化算法并不適合于并行環(huán)境，并行化難度大。

首先利用均勻設(shè)計(jì)具有使實(shí)驗(yàn)點(diǎn)高維空間均勻分散的特點(diǎn)，與Powell算法結(jié)合，并適當(dāng)改進(jìn)，經(jīng)過經(jīng)典的全局最優(yōu)化函數(shù)測試發(fā)現(xiàn)它能夠跳出局部最優(yōu)陷阱，從而準(zhǔn)確地找到全局最優(yōu)點(diǎn)。最后，對算法的時(shí)間空間復(fù)雜度進(jìn)行了測試，數(shù)據(jù)統(tǒng)計(jì)顯示本文算法時(shí)間復(fù)雜度與計(jì)算問題需要考慮的因素個數(shù)的二次方和布點(diǎn)數(shù)成線性關(guān)系，空間復(fù)雜度與因素個數(shù)和布點(diǎn)數(shù)成線性關(guān)系。對算法進(jìn)行了并行化，經(jīng)測試得知并行效率很高。該算法具有很好的求解大型優(yōu)化問題的潛力。