基本介紹
- 中文名：種群初始化
- 外文名：Population initialization
- 內容：種群的初始解
- 方法：M類隨機方法、定值設定法等
- 隨機：常用的是RNG
- 定值：產生均勻分布的點
大規模最佳化問題,數學表述,種群初始化,不分組策略,子代產生策略,新的進化策略,種群初始化流程,
大規模最佳化問題
當今很多最佳化問題已經從簡單問題發展成為複雜問題，許多科學和工程套用問題都可以設計成大規模最佳化問題來進行求解，例如大型電力系統、大量的資源調度問題、大規模交通網路的車輛路徑規劃等。然而隨著最佳化問題越來越複雜，一些經典的算法已經不能滿足實際需要，最近幾年進化最佳化在許多實值和組合最佳化問題上取得了很大的成功，但是大多數的隨機最佳化算法都會遭受“維數災難”。因此，近些年學者們利用進化算法進行了多種有價值的嘗試，並且針對大規模最佳化問題組織了特別會議，顯示出此研究領域的重要性。
數學表述
大規模最佳化問題可以用數學式表述，介紹的解決方案主要針對該問題中最小化問題進行求解。在算法開始階段，給出了針對大規模問題的初始化方法，可以更加有效的尋找極點。而對於算法的主體部分，一般來說主流的策略可以分為兩大類協同進化策略和不分組策略。協同進化策略是由分治策略進化而來，主要思想是把大規模複雜問題分解成單變數或低維簡單問題逐一解決。而不分組策略是運用一些特殊的策略或聯合其它有效的算法來改進它們在解決大規模問題時的性能。
種群初始化
算法在開始時都要進行種群的初始化，根據初始化方法的不同形式可以將其分成M類隨機方法、定值設定法、兩步式方法、混合方法和具體套用法，隨機數生成器是最常用的方法，然而，在面對大規模最佳化問題（決策變數超過100）時，這種初始化方法效果不佳。在隨機方法中，比較常用的是RNG。而定值設定法則比較偏向於在搜尋空間中產生均勻分布的點。在缺乏問題先驗知識的情況下，一個比較均勻的種群可以促進算法在疊代早期的探索能力。近些年，兩步式初始化方法在文獻中較為常用，此方法分為前期產生初始點，後期根據條件改進這些點，混合方法一般來說是一些基礎方法的組合，具體套用法則是指根據一些特殊的實值問題專門設計的初始化方法。
不分組策略
學者們一般根據算法不同階段的特性設定不同的策略來解決低維問題，所以，針對大規模最佳化問題改進這些策略是一種比較常用的方法。
子代產生策略
一般來說，每種進化算法都有固定的子代產生策略。但是，對於大規模問題，使個體廣泛分布在高維空間中比較困難，在每次疊代過程中，算法不斷的收斂，因此下一代的產生策略很重要，不僅要向好的方向進化還要在搜尋空間中廣泛探索。這種產生策略具有空間的導向性，可以增加種群的多樣性，將其插入算法來解決大規模最佳化問題。
新的進化策略
在解決大規模最佳化問題上，除了在原有的算法中加入新的策略，提出了一些新的群集智慧型算法用於解決此類問題。提出了社會學習的粒子群最佳化算法，不同於經典的粒子群最佳化算法，利用歷史信息（包括整個種群的最優位置和每個粒子的歷史最優位置）更新粒子新算法中，粒子向當前種群中比它優秀的個體學習。
種群初始化流程
種群的初始化就是依據編碼規則給出種群的初始解。傳統的遺傳算法求解VRP問題時,初始種群多半採取隨機生成法,即從所有的配送點中隨機選取點直到滿足一定的條件或接近滿足一定條件後停止,形成一條子路徑,乃至形成一條染色體(一套配送方案)。但這種方式使初始種群的形成過於隨意,以致於一開始就可能形成許多不可行的方案,之後要進行大量的計算後才能得到最佳化的方案,這樣很大程度上降低了算法的運算效率。
掃描法求解VRP初始種群的思路是:通過掃描法形成一套路徑配送的完整方案,將其作為遺傳操作中的一條染色體;重複這個過程,得到種群數量為N的染色體。具體流程如下：
(1)過配送中心與某配送點生成射線順時針轉動。
(2)累計扇面覆蓋的配送點需求量之和,直至滿足運量約束停止構成一個客戶分群。
(3)採用節約插入算法將該客戶群形成最佳化為一條有序的子路徑。
（4）以原射線末位置為新射線的初始位重複上述過程。直至形成一條包含所有子路徑的染色體序列。
(5)將射線順位偏移某一角度,同樣按以上方法產生第二染色體。最終形成N/2條染色體的種群。
(6)為保證種群多樣性,上述方法逆時針做同樣操作,再形成N/2條染色體。子路徑內部是一個路徑最佳化的序列組合,子路徑之間同樣按序列編號排列。
