遺傳算法的種群退化分析及其抑制技術.pdf

1、本文以求解固定費用運輸問題的遺傳算法為研究對象，分析遺傳算法的種群退化現(xiàn)象，研究種群退化的條件及其抑制技術。 證明了基于矩陣編碼的遺傳算法(GA-M：Genetic Algorithm with Mattix Code)的重組算子導致種群退化，并從編碼方式、運輸網(wǎng)絡各節(jié)點的供給和需求能力及整體運輸成本三個方面來判斷種群退化的算法，這些算法的時間復雜度皆為多項式時間的高效算法。并且從運輸網(wǎng)絡節(jié)點的供給和需求能力及整體運輸成本兩個方

2、面證明了GA-M算法的變異算子不能抑制種群退化。提出了抑制由算法(SM-GA-M：Suppressing Method for GA-M)，嚴格證明了在不增加算法的時間復雜度的條件下，SM-GA-M能夠抑制GA-M算法所引發(fā)的種群退化現(xiàn)象，試驗結果表明SM-GA算法的求解能力和抑制能力顯著高于GA-M算法。 分析了基于邊集編碼的遺傳局部搜索算法(GLSA：Genetic Local Search Al-gorithm)和有序邊集

3、算法(GA-ES：GA with Edge Set)，證明了GLSA和GA-ES的基于子樹補充式單點交叉算子引發(fā)完全種群退化現(xiàn)象，并解析地給出了種群退化的發(fā)生概率，該概率正比于生成樹的葉子節(jié)點數(shù)。提出了抑制生成樹的葉子節(jié)點的算法(SM-GLSA：Suppressing Method for GLSA)，從理論和實驗兩方面證明了SM-GLSA在抑制種群退化現(xiàn)象的顯著優(yōu)勢。 為解決SM-GA-M和SM-GLSA在求解能力與抑制能力專