基于遺傳算法和gis技術(shù) 基于遺傳算法和gis技術(shù)的區(qū)別

Python實現(xiàn)基于遺傳算法的排課優(yōu)化

排課問題的本質(zhì)是將課程、教師和學(xué)生在合適的時間段內(nèi)分配到合適的教室中，涉及到的因素較多，是一個多目標(biāo)的調(diào)度問題，在運籌學(xué)中被稱為時間表問題（Timetable Problem，TTP）。設(shè)一個星期有n個時段可排課，有m位教師需要參與排課，平均每位教師一個星期上k節(jié)課，在不考慮其他限制的情況下，能夠推出的可能組合就有 種，如此高的復(fù)雜度是目前計算機所無法承受的。因此眾多研究者提出了多種其他排課算法，如模擬退火，列表尋優(yōu)搜索和約束滿意等。

創(chuàng)新互聯(lián)建站長期為近1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為封丘企業(yè)提供專業(yè)的成都做網(wǎng)站、成都網(wǎng)站建設(shè)，封丘網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

Github ：

遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。遺傳算法的流程如下所示：

遺傳算法首先針對待解決問題隨機生成一組解，我們稱之為種群（Population）。種群中的每個個體都是問題的解，在優(yōu)化的過程中，算法會計算整個種群的成本函數(shù)，從而得到一個與種群相關(guān)的適應(yīng)度的序列。如下圖所示：

為了得到新的下一代種群，首先根據(jù)適應(yīng)度對種群進行排序，從中挑選出最優(yōu)的幾個個體加入下一代種群，這一個過程也被稱為精英選拔。新種群余下的部分通過對選拔出來的精英個體進行修改得到。

對種群進行修改的方法參考了生物DAN進化的方法，一般使用兩種方法： 變異 和 交叉 。 變異 的做法是對種群做一個微小的、隨機的改變。如果解的編碼方式是二進制，那么就隨機選取一個位置進行0和1的互相突變；如果解的編碼方式是十進制，那么就隨機選取一個位置進行隨機加減。 交叉 的做法是隨機從最優(yōu)種群中選取兩個個體，以某個位置為交叉點合成一個新的個體。

經(jīng)過突變和交叉后我們得到新的種群（大小與上一代種群一致），對新種群重復(fù)重復(fù)上述過程，直到達到迭代次數(shù)（失敗）或者解的適應(yīng)性達到我們的要求（成功），GA算法就結(jié)束了。

算法實現(xiàn)

首先定義一個課程類，這個類包含了課程、班級、教師、教室、星期、時間幾個屬性，其中前三個是我們自定義的，后面三個是需要算法來優(yōu)化的。

接下來定義cost函數(shù)，這個函數(shù)用來計算課表種群的沖突。當(dāng)被測試課表沖突為0的時候，這個課表就是個符合規(guī)定的課表。沖突檢測遵循下面幾條規(guī)則：

使用遺傳算法進行優(yōu)化的過程如下，與上一節(jié)的流程圖過程相同。

init_population ：隨機初始化不同的種群。

mutate ：變異操作，隨機對 Schedule 對象中的某個可改變屬性在允許范圍內(nèi)進行隨機加減。

crossover ：交叉操作，隨機對兩個對象交換不同位置的屬性。

evolution ：啟動GA算法進行優(yōu)化。

實驗結(jié)果

下面定義了3個班，6種課程、教師和3個教室來對排課效果進行測試。

優(yōu)化結(jié)果如下，迭代到第68次時，課程安排不存在任何沖突。

選擇1203班的課表進行可視化，如下所示，算法合理的安排了對應(yīng)的課程。

遺傳算法

優(yōu)化的算法有很多種，從最基本的梯度下降法到現(xiàn)在的一些啟發(fā)式算法，如遺傳算法(GA)，差分演化算法(DE)，粒子群算法(PSO)和人工蜂群算法(ABC)。

舉一個例子，遺傳算法和梯度下降：

梯度下降和遺傳算法都是優(yōu)化算法，而梯度下降只是其中最基礎(chǔ)的那一個，它依靠梯度與方向?qū)?shù)的關(guān)系計算出最優(yōu)值。遺傳算法則是優(yōu)化算法中的啟發(fā)式算法中的一種，啟發(fā)式算法的意思就是先需要提供至少一個初始可行解，然后在預(yù)定義的搜索空間高效搜索用以迭代地改進解，最后得到一個次優(yōu)解或者滿意解。遺傳算法則是基于群體的啟發(fā)式算法。

遺傳算法和梯度下降的區(qū)別是：

1.梯度下降使用誤差函數(shù)決定梯度下降的方向，遺傳算法使用目標(biāo)函數(shù)評估個體的適應(yīng)度

2.梯度下降是有每一步都是基于學(xué)習(xí)率下降的并且大部分情況下都是朝著優(yōu)化方向迭代更新，容易達到局部最優(yōu)解出不來；而遺傳算法是使用選擇、交叉和變異因子迭代更新的，可以有效跳出局部最優(yōu)解

3.遺傳算法的值可以用二進制編碼表示，也可以直接實數(shù)表示

遺傳算法如何使用它的內(nèi)在構(gòu)造來算出 α 和 β ：

主要講一下選擇、交叉和變異這一部分：

1.選擇運算:將選擇算子作用于群體。選擇的目的是把優(yōu)秀（適應(yīng)值高）的個體直接遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的。

2.交叉運算：將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。交叉算子是將種群中的個體兩兩分組，按一定概率和方式交換部分基因的操作。將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。例如：（根據(jù)概率選取50個個體，兩兩配對，交換x,y，比如之前兩個是(x1,y1),(x2,y2)，之后變成了（x1,y2）,(x2,y1)）

3.變異運算：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。（x2可能變?yōu)閤2+δ，y1變?yōu)閥1+δ）

種群P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代種群P(t+1)。

遺傳算法就是通過對大量的數(shù)據(jù)個體使用選擇、交叉和變異方式來進化，尋找適合問題的最優(yōu)解或者滿意解。

遺傳算法參數(shù)的用處和設(shè)置：

1.編碼選擇：通常使用二進制編碼和浮點數(shù)編碼，二進制適合精度要求不高、特征較少的情況。浮點數(shù)適合精度高、特征多的情況

2.種群：種群由個體組成，個體中的每個數(shù)字都代表一個特征，種群個體數(shù)量通常設(shè)置在40-60之間；迭代次數(shù)通?？辞闆r定若計算時間較長可以在100內(nèi)，否則1000以內(nèi)都可以。

3.選擇因子：通常有輪盤賭選擇和錦標(biāo)賽選擇，輪盤賭博的特點是收斂速度較快，但優(yōu)勢個體會迅速繁殖，導(dǎo)致種群缺乏多樣性。錦標(biāo)賽選擇的特點是群多樣性較為豐富，同時保證了被選個體較優(yōu)。

4.交叉因子：交叉方法有單點交叉和兩點交叉等等，通常用兩點交叉。交叉概率則選擇在0.7-0.9。概率越低收斂越慢時間越長。交叉操作能夠組合出新的個體，在串空間進行有效搜索，同時降低對種群有效模式的破壞概率。

5.變異因子：變異也有變異的方法和概率。方法有均勻變異和高斯變異等等；概率也可以設(shè)置成0.1。變異操作可以改善遺傳算法的局部搜索能力，豐富種群多樣性。

6.終止條件：1、完成了預(yù)先給定的進化代數(shù)；2、種群中的最優(yōu)個體在連續(xù)若干代沒有改進或平均適應(yīng)度在連續(xù)若干代基本沒有改進；3、所求問題最優(yōu)值小于給定的閾值.

基于遺傳算法的水文頻率計算與研究

1)根據(jù)大任水庫的實際情況，對各種參數(shù)估計方法進行比較，以矩法、概率權(quán)重矩法、單權(quán)函數(shù)法和雙權(quán)函數(shù)法的參數(shù)估計成果為依據(jù)，然后，根據(jù)實際情況分析，適當(dāng)調(diào)整后作為GA(遺傳算法)決策變量的取值范圍;評價個體適應(yīng)度應(yīng)把目標(biāo)函數(shù)求極小值轉(zhuǎn)換為求極大值。

2)采用12組GA運行參數(shù)組分別進行計算，然后分析GA運行輸出的成果圖，確定GA運行參數(shù)較合理的取值。

3)采用30次連續(xù)計算的方案，對GA進行操作，然后分別計算這30次GA計算所得的降雨量值與實測降雨量值之間的相對誤差，選出相對誤差較小的一組所對應(yīng)的水文特征值，計算理論降雨量，與實測降雨量一起繪于圖上，分析擬合情況，并與傳統(tǒng)的矩法、概率權(quán)重矩法、單權(quán)函數(shù)法和雙權(quán)函數(shù)法計算成果相比較，分析計算成果的合理性。最后，計算設(shè)計洪水，繪制洪水過程線。

遺傳算法研究進展

遺傳算法［56，53］研究的興起是在20世紀80年代末和90年代初期，但它的歷史起源可追溯到20世紀60年代初期。早期的研究大多以對自然遺傳系統(tǒng)的計算機模擬為主。早期遺傳算法的研究特點是側(cè)重于對一些復(fù)雜的操作的研究。雖然其中像自動博弈、生物系統(tǒng)模擬、模式識別和函數(shù)優(yōu)化等給人以深刻的印象，但總的來說這是一個無明確目標(biāo)的發(fā)展時期，缺乏帶有指導(dǎo)性的理論和計算工具的開拓。這種現(xiàn)象直到20世紀70年代中期由于Holland和De Jong的創(chuàng)造性研究成果的發(fā)表才得到改觀。當(dāng)然，早期的研究成果對于遺傳算法的發(fā)展仍然有一定的影響，尤其是其中一些有代表性的技術(shù)和方法已為當(dāng)前的遺傳算法所吸收和發(fā)展。

在遺傳算法作為搜索方法用于人工智能系統(tǒng)中之前，已有不少生物學(xué)家用計算機來模擬自然遺傳系統(tǒng)。尤其是Fraser的模擬研究，他于1962年提出了和現(xiàn)在的遺傳算法十分相似的概念和思想。但是，F(xiàn)raser和其他一些學(xué)者并未認識到自然遺傳算法可以轉(zhuǎn)化為人工遺傳算法。Holland教授及其學(xué)生不久就認識到這一轉(zhuǎn)化的重要性，Holland認為比起尋找這種或那種具體的求解問題的方法來說，開拓一種能模擬自然選擇遺傳機制的帶有一般性的理論和方法更有意義。在這一時期，Holland不但發(fā)現(xiàn)了基于適應(yīng)度的人工遺傳選擇的基本作用，而且還對群體操作等進行了認真的研究。1965年，他首次提出了人工遺傳操作的重要性，并把這些應(yīng)用于自然系統(tǒng)和人工系統(tǒng)中。

1967年，Bagley在他的論文中首次提出了遺傳算法（genetic algorithm）這一術(shù)語，并討論了遺傳算法在自動博弈中的應(yīng)用。他所提出的包括選擇、交叉和變異的操作已與目前遺傳算法中的相應(yīng)操作十分接近。尤其是他對選擇操作做了十分有意義的研究。他認識到，在遺傳進化過程的前期和后期，選擇概率應(yīng)合適地變動。為此，他引入了適應(yīng)度定標(biāo)（scaling）概念，這是目前遺傳算法中常用的技術(shù)。同時，他也首次提出了遺傳算法自我調(diào)整概念，即把交叉和變異的概率融于染色體本身的編碼中，從而可實現(xiàn)算法自我調(diào)整優(yōu)化。盡管Bagley沒有對此進行計算機模擬實驗，但這些思想對于后來遺傳算法的發(fā)展所起的作用是十分明顯的。

在同一時期，Rosenberg也對遺傳算法進行了研究，他的研究依然是以模擬生物進化為主，但他在遺傳操作方面提出了不少獨特的設(shè)想。1970年Cavicchio把遺傳算法應(yīng)用于模式識別中。實際上他并未直接涉及到模式識別，而僅用遺傳算法設(shè)計一組用于識別的檢測器。Cavicchio對于遺傳操作以及遺傳算法的自我調(diào)整也做了不少有特色的研究。

Weinberg于1971年發(fā)表了題為《活細胞的計算機模擬》的論文。由于他和Rosenberg一樣注意于生物遺傳的模擬，所以他對遺傳算法的貢獻有時被忽略。實際上，他提出的多層次或多級遺傳算法至今仍給人以深刻的印象。

第一個把遺傳算法用于函數(shù)優(yōu)化的是Hollstien。1971年他在論文《計算機控制系統(tǒng)中的人工遺傳自適應(yīng)方法》中闡述了遺傳算法用于數(shù)字反饋控制的方法。實際上，他主要是討論了對于二變量函數(shù)的優(yōu)化問題。其中，對于優(yōu)勢基因控制、交叉和變異以及各種編碼技術(shù)進行了深入的研究。

1975年在遺傳算法研究的歷史上是十分重要的一年。這一年，Holland出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的適配》。該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極為重要的模式理論（schemata theory）。該理論首次確認了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性。直到這時才知道遺傳操作到底在干什么，為什么又干得那么出色，這對于以后陸續(xù)開發(fā)出來的遺傳操作具有不可估量的指導(dǎo)作用。

同年，De Jong完成了他的重要論文《遺傳自適應(yīng)系統(tǒng)的行為分析》。他在該論文中所做的研究工作可看作是遺傳算法發(fā)展進程中的一個里程碑，這是因為他把Holland的模式理論與他的計算實驗結(jié)合起來。盡管De Jong和Hollstien一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將選擇、交叉和變異操作進一步完善和系統(tǒng)化，同時又提出了諸如代溝（generation gap）等新的遺傳操作技術(shù)。可以認為，De Jong的研究工作為遺傳算法及其應(yīng)用打下了堅實的基礎(chǔ)，他所得出的許多結(jié)論迄今仍具有普遍的指導(dǎo)意義。

進入20世紀80年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但它的應(yīng)用領(lǐng)域擴大，而且利用遺傳算法進行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高，同時產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中。此外一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。

隨著應(yīng)用領(lǐng)域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向：一是基于遺傳算法的機器學(xué)習(xí)（Genetic Base Machine Learning），這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴展到具有獨特的規(guī)則生成功能的嶄新的機器學(xué)習(xí)算法。這一新的學(xué)習(xí)機制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其他智能計算方法相互滲透和結(jié)合，這對開拓21世紀中新的智能計算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用。五是遺傳算法和進化規(guī)劃（Evolution Programming，EP）以及進化策略（Evolution Strategy，ES）等進化計算理論日益結(jié)合。EP和ES幾乎是和遺傳算法同時獨立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，既同遺傳算法具有相同之處，也有各自的特點。

隨著遺傳算法研究和應(yīng)用的不斷深入和發(fā)展，一系列以遺傳算法為主題的國際會議十分活躍。從1985年開始，國際遺傳算法會議，即ICGA（International Conference on Genetic Algorithm）每兩年舉行一次。在歐洲，從1990年開始也每隔一年舉辦一次類似的會議，即 PPSN（Parallel Problem Solving from Nature）會議。除了遺傳算法外，大部分有關(guān)ES和EP的學(xué)術(shù)論文也出現(xiàn)在PPSN中。另外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會議有FOGA（Foundation of Genetic Algorithm）。它也是從1990年開始，隔年召開一次。這些國際學(xué)術(shù)會議論文集中反映了遺傳算法近些年來的最新發(fā)展和動向。

文章名稱：基于遺傳算法和gis技術(shù) 基于遺傳算法和gis技術(shù)的區(qū)別
URL鏈接：http://muchs.cn/article46/dohdehg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號、關(guān)鍵詞優(yōu)化、網(wǎng)站內(nèi)鏈、響應(yīng)式網(wǎng)站、搜索引擎優(yōu)化、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)