【摘要】：旅行商問題是一個經(jīng)典的NP(non-deterministic polynomial)困難問題,在日常生活中比較常見,例如物流、旅游、抄表等等。由于旅行商問題的時間復(fù)雜度增長很快,精確算法很難在可接受的時間內(nèi)找到最優(yōu)答案。因此解決旅行商問題通常使用啟發(fā)式算法,遺傳算法就是其中之一。遺傳算法是一種仿生算法。遺傳算法將所需解決的問題抽象為種群,對種群的個體進行適應(yīng)度評估,按照人工方向進行定向選擇,淘汰適應(yīng)度低個體,保留適應(yīng)度高的個體進行基因重組和變異,經(jīng)過多次迭代,得到問題的一個近似最優(yōu)解。遺傳算法自誕生以來得到了廣泛的應(yīng)用。但是,遺傳算法存在對初始種群依賴性強、易早熟、收斂速度難以控制等方面的缺陷,需要對遺傳算法進行改進。為了克服遺傳算法的缺陷,提出遺傳蟻群算法。遺傳蟻群算法結(jié)合使用遺傳算法和蟻群算法,將蟻群算法中的信息素引入遺傳算法中。初始化過程中,遺傳蟻群算法對初始種群進行基因比對,淘汰重復(fù)率過高的個體。這樣可以保證初始群體均勻分布。遺傳蟻群算法分為兩個階段:全局搜索階段和快速收斂階段。不同階段中螞蟻種群對信息素的反應(yīng)是不同的。在全局搜索階段,遺傳蟻群算法需要充分搜索全局空間,此時螞蟻種群對信息素是抗拒的,螞蟻將會有更高的概率選擇未被訪問的路徑。在快速收斂階段,螞蟻種群對信息素是喜好的,螞蟻種群將會快速聚集到信息素高的路徑上。以供水收費系統(tǒng)為應(yīng)用場景,通過實際應(yīng)用論證遺傳蟻群算法的性能。在供水收費系統(tǒng)中存在抄表員抄表路徑優(yōu)化的問題,問題實質(zhì)為求解旅行商問題。抄表員每月都會對自己負(fù)責(zé)抄表的區(qū)域進行抄表工作。通過使用遺傳蟻群算法優(yōu)化抄表路徑,并對比、分析遺傳蟻群算法的性能,證明使用該算法能夠提高抄表工作的效率,節(jié)省抄表所需的時間,從而可以調(diào)整抄表工作的抄表員數(shù)量,節(jié)省人力財力。
[Abstract]:......
【學(xué)位授予單位】：山東科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18

【參考文獻】

相關(guān)期刊論文 前10條

1 陳順立;;農(nóng)業(yè)機器人路徑優(yōu)化及軌跡跟蹤研究—基于遺傳算法[J];農(nóng)機化研究;2017年08期

2 李純思;衣淑娟;;水稻浸種催芽箱溫度傳感器優(yōu)化配置——基于遺傳算法[J];農(nóng)機化研究;2017年06期

3 曹思聰;夏輝;孫可;;基于蟻群算法的TSP問題分析[J];鞍山師范學(xué)院學(xué)報;2017年02期

4 金保華;岳艷;周兵;;基于改進遺傳算法的otsu圖像分割算法[J];湖北民族學(xué)院學(xué)報(自然科學(xué)版);2017年01期

5 伍建偉;劉夫云;李嶠;;MATLAB遺傳算法函數(shù)ga優(yōu)化實例[J];機械工程與自動化;2017年02期

6 黃軼文;張梅;;基于蟻群算法的六自由度采摘機器人軌跡規(guī)劃研究[J];農(nóng)機化研究;2017年03期

7 孫文兵;;遺傳算法降維優(yōu)化的BP模型及葡萄酒質(zhì)量預(yù)測[J];邵陽學(xué)院學(xué)報(自然科學(xué)版);2017年01期

8 王春華;邱立鵬;潘德文;;改進蟻群算法的機器人焊接路徑規(guī)劃[J];傳感器與微系統(tǒng);2017年02期

9 王云松;孫佳林;龔躍;;基于蟻群算法的云任務(wù)調(diào)度研究[J];長春理工大學(xué)學(xué)報(自然科學(xué)版);2017年01期

10 李雅瓊;;基于粒子群算法的遺傳算法優(yōu)化研究[J];蘭州文理學(xué)院學(xué)報(自然科學(xué)版);2017年01期

相關(guān)碩士學(xué)位論文 前9條

1 張鵬程;基于改進遺傳算法的冷鏈物流路徑優(yōu)化研究[D];安徽理工大學(xué);2016年

2 葉晶晶;蛙跳算法的改進及在車輛路徑問題中的研究[D];廣東工業(yè)大學(xué);2016年

3 馬振;改進蟻群算法及其在TSP中的應(yīng)用研究[D];青島理工大學(xué);2016年

4 趙李明;基于遺傳算法和BP神經(jīng)網(wǎng)絡(luò)的廣州市空氣質(zhì)量預(yù)測與時空分布研究[D];江西理工大學(xué);2016年

5 王丹;基于改進遺傳算法的物流配送車輛路徑問題研究[D];長春工業(yè)大學(xué);2016年

6 潘挺雷;基于改進蟻群算法的區(qū)域車輛配送路徑優(yōu)化方法研究[D];浙江理工大學(xué);2016年

7 解英全;基于遺傳蟻群混合算法的機場停機位分配研究[D];西安工業(yè)大學(xué);2015年

8 邵娜娜;蟻群算法求解最大團問題研究與應(yīng)用[D];河北工業(yè)大學(xué);2015年

9 王霜;大型TSP問題的蟻群優(yōu)化規(guī)則研究[D];吉林大學(xué);2012年

，

本文編號：2476889