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

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

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

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