遺傳算法在貨郎擔(dān)問(wèn)題的應(yīng)用.pdf

1、遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法，其應(yīng)用優(yōu)勢(shì)在于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性問(wèn)題。 旅行商(TSP)問(wèn)題是組合優(yōu)化領(lǐng)域中的一個(gè)典型問(wèn)題，涉及求多個(gè)變量的函數(shù)的最小值。雖然它陳述起來(lái)很簡(jiǎn)單，但求解卻很困難，并且已經(jīng)被證明是NP完全問(wèn)題。但它確實(shí)廣泛存在，且是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問(wèn)題的集中概括和簡(jiǎn)化形式?？焖佟⒂行У亟鉀QTSP問(wèn)題有著較高的理論意義和實(shí)際應(yīng)用價(jià)值，這就是本文提出的用改進(jìn)遺傳

2、算法求解TSP問(wèn)題的目的。 本文對(duì)影響遺傳算法性能的因素進(jìn)行了分析，引入了啟發(fā)式遺傳算子的設(shè)計(jì)，交叉概率Pc和變異概率Pm能隨適應(yīng)度值自動(dòng)改變，提出了一種改進(jìn)的遺傳算法IGA(ImprovedGenericAlgorithm)。對(duì)于適應(yīng)值高于群體平均適應(yīng)度的個(gè)體，對(duì)應(yīng)于較低的Pc和Pm，，使得該解得以保護(hù)進(jìn)入下一代；而低于平均值的個(gè)體，對(duì)應(yīng)于較高的Pc和Pm，使該解被淘汰掉，自適應(yīng)遺傳算法在保持群體多樣性的同時(shí)，也可保證遺傳算法