基于遺產(chǎn)算法的公交排班調(diào)度優(yōu)化實(shí)證研究摘要隨著安溪縣社會(huì)經(jīng)濟(jì)的迅速發(fā)展，居民汽車保有量隨之增加，高峰時(shí)間段對人流密集區(qū)域周邊道路的負(fù)擔(dān)也隨之增加，因此在高峰時(shí)間段學(xué)校、醫(yī)院等高密度人群路段在高峰時(shí)間段交通堵塞現(xiàn)象頻出。本文著眼于進(jìn)行公交車輛排版調(diào)度優(yōu)化，通過提高城市公共交通系統(tǒng)的運(yùn)行效率來提高道路的服務(wù)等級，減緩交通堵塞現(xiàn)象。本文以2路公交線路為研究對象，構(gòu)建公交車輛調(diào)度模型，使用python進(jìn)行編程，并通過遺傳算法進(jìn)行計(jì)算求解公交排班問題，通過遺傳算法求解得到的發(fā)車時(shí)刻表來相比傳統(tǒng)的人工調(diào)度的發(fā)車方式更具科學(xué)性、合理性、邏輯性。通過優(yōu)化公交排班來提高乘客的滿意度，提高公交出行占比，進(jìn)而提高道路空間利用率，改善交通擁堵的問題。關(guān)鍵字：遺傳算法；排班調(diào)度；數(shù)學(xué)建模；公共交通；python目錄TOC\o"1-3"\h\u摘要 引言1.1研究背景隨著社會(huì)經(jīng)濟(jì)的飛速發(fā)展，在安溪縣人口高速增長以及汽車保有量快速增加的同時(shí)，安溪縣市民的出行量也隨之提高，安溪縣城中心地段的交通擁堵問題愈發(fā)嚴(yán)重，改善安溪高峰時(shí)間段的交通堵塞問題刻不容緩。影響城市交通運(yùn)輸系統(tǒng)的因素有許多，但是城市公共交通系統(tǒng)是否能夠順暢運(yùn)行，無疑直接影響到出行者出行的效率，城市道路的服務(wù)水平以及人民的生活品質(zhì)。世界各國政府都極其重視城市公共交通的作用，諸如日本東京、美國紐約、英國倫敦、法國巴黎等城市在公共交通領(lǐng)域上都有極具特色的發(fā)展建樹。國內(nèi)的深圳、北京、上海、廣州等城市的城市公共交通系統(tǒng)也不斷深入發(fā)展并取得顯著成效。然而并非所有的城市地區(qū)都有完善先進(jìn)的城市公共交通系統(tǒng)，大多數(shù)縣城地區(qū)甚至部分城市都沒有投入建設(shè)快速便捷的城市地鐵系統(tǒng)，仍然以城市公交車輛作為主要的公共交通運(yùn)輸手段。并且我國許多地區(qū)仍然采用傳統(tǒng)的人工經(jīng)驗(yàn)調(diào)度的調(diào)度辦法。經(jīng)過調(diào)查，本文研究地點(diǎn)安溪縣便是采用人工經(jīng)驗(yàn)進(jìn)行公交車輛調(diào)度發(fā)車，這極大浪費(fèi)了城市道路資源，導(dǎo)致部分線路日均乘客量低下，同時(shí)經(jīng)過縣城中心的大部分公交線路在高峰時(shí)段也容易形成交通擁堵的現(xiàn)象。在全國范圍內(nèi)各縣城地區(qū)全面普及城市地鐵系統(tǒng)以及投入巨額的公共交通建設(shè)發(fā)展費(fèi)用顯然是不實(shí)際的，然而各縣城地區(qū)的公交堵塞問題越來越嚴(yán)重，改建拓展車道經(jīng)濟(jì)成本較高，經(jīng)濟(jì)效益過低，治標(biāo)不治本，難以有效地改善城市交通擁擠的問題，因此通過公交排班調(diào)度的優(yōu)化是來緩解交通擁堵問題顯然也是一條更具長遠(yuǎn)發(fā)展目光的可持續(xù)發(fā)展道路。本文從安溪縣的實(shí)際公交運(yùn)營中發(fā)現(xiàn)問題，并以安溪縣公交2路線路作為研究對象，期望通過優(yōu)化排班調(diào)度來達(dá)到改善縣城地區(qū)的公共交通系統(tǒng)的目的，進(jìn)一步提高公共交通系統(tǒng)的運(yùn)輸效率和道路空間資源的利用率，從而緩解高峰期交通擁堵的問題。本文采用遺傳算法的目的在于隨著交通行業(yè)的迅速發(fā)展，我們每天出行所要面臨的道路環(huán)境逐漸復(fù)雜，隨著交通理論發(fā)展的不斷精進(jìn)，在公交排班問題上要考慮的因素越來越多，傳統(tǒng)的數(shù)學(xué)模型求解方法逐漸不能夠滿足求解復(fù)雜繁冗的數(shù)學(xué)模型，得到的結(jié)果精確度不足，并且在很多實(shí)際復(fù)雜問題諸如交通問題等想要得到精確解是非常困難的，因此科學(xué)家們的研究逐漸從得到最優(yōu)解轉(zhuǎn)向得到近似最優(yōu)解。隨著科技革命和技術(shù)變革加速演進(jìn)，互聯(lián)網(wǎng)、人工智能等技術(shù)充分運(yùn)用到各個(gè)領(lǐng)域當(dāng)中，人工智能AI在各領(lǐng)域的高效運(yùn)用的實(shí)踐案例為公交排班優(yōu)化問題指明了前進(jìn)的方向，提供了全新的方法。遺傳算法是一種模仿自然界中的生物朝著更適合種群生存的方向進(jìn)化的算法，模仿生物在大自然的自然條件限制約束下尋求進(jìn)化的方向的進(jìn)化過程，使用遺傳算法求解數(shù)學(xué)模型的過程是一種在可行解中搜索最優(yōu)解的過程。該算法通過構(gòu)建數(shù)學(xué)模型,再使用MATLAB、LINGO、Python等軟件編寫代碼，進(jìn)行仿真模擬實(shí)驗(yàn),將在解域中搜索最優(yōu)解或近似最優(yōu)解的過程模擬成生物在遺傳進(jìn)化中的基因\t"/item/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95/_blank"染色體經(jīng)過交叉、變異等遺傳操作，經(jīng)過一代代的繁衍進(jìn)化過程，最終實(shí)現(xiàn)淘汰不適應(yīng)環(huán)境生存的劣種個(gè)體，保留適應(yīng)自然界環(huán)境條件的優(yōu)良個(gè)體的進(jìn)化過程。隨著信息時(shí)代的來臨，GA在機(jī)器學(xué)習(xí)、排班調(diào)度、信號控制以及深度學(xué)習(xí)等領(lǐng)域得到廣泛的應(yīng)用。而今GA作為一種高效的求解算法，活躍于解決實(shí)際問題的各個(gè)領(lǐng)域當(dāng)中，因此本文采取遺傳算法進(jìn)行公交調(diào)度優(yōu)化。希望通過對調(diào)查采集的實(shí)際數(shù)據(jù)進(jìn)行有理論支撐地分析，使用python進(jìn)行安溪縣公交2路線路的發(fā)車仿真實(shí)驗(yàn)，得到基于遺傳算法的行車時(shí)刻表。1.2國內(nèi)外研究綜述城市交通系統(tǒng)對城市的社會(huì)經(jīng)濟(jì)發(fā)展起到至關(guān)重要的作用，其中城市公共交通運(yùn)輸系統(tǒng)又直接影響著城市交通系統(tǒng)的運(yùn)行效率，而公交排班調(diào)度優(yōu)化是提高公共交通運(yùn)輸系統(tǒng)運(yùn)行效率的重要方式之一。隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展，越來越多的學(xué)者著眼于運(yùn)用編程算法對公交排班進(jìn)行優(yōu)化，通過大數(shù)據(jù)分析和建立模型，編碼解碼得到科學(xué)的發(fā)車時(shí)刻表來代替?zhèn)鹘y(tǒng)落后的人工調(diào)度方式。DebK，Chakroborty等以乘客總體等待時(shí)間為目標(biāo)函數(shù)，并引入遺傳算法進(jìn)行模型求解[[]DebK,ChakrobortyP.TimeSchedulingofTransitSystemsWithTransferConsiderationsUsingGeneticAlgorithms[J].EvolutionaryComputation,1998,6(1):1.]；Park通過遺傳算法進(jìn)行公交調(diào)度問題的研究[[]ParkSJ.BusNetworkSchedulingwithGeneticAlgorithmsandSimulation[D].2005.]；Chakroborty等研究利用遺傳算法解決公交調(diào)度優(yōu)化問題，以發(fā)車時(shí)間間隔等作為約束條件，并采用遺傳算法進(jìn)行計(jì)算，早年國外學(xué)者對遺傳算法應(yīng)用于公交排班調(diào)度問題的研究為國內(nèi)研究公交排班調(diào)度問題的學(xué)者提供另一條全新的道路，同時(shí)也為本文使用遺傳算法進(jìn)行求解提供了強(qiáng)有力的歷史依據(jù)和理論依據(jù)[[]ChakrobortyP,DebK,SubrahmanyamPS.Optimalschedulingofurbantransitsystemsusinggeneticalgorithms[J].JournalofTransportationEngineering,1995,121(6):544-553.]；崔世彬通過整合日總發(fā)車次數(shù)和日均乘客候車時(shí)間兩部分參數(shù)，構(gòu)建目標(biāo)函數(shù)，并加以日均車輛滿載率和發(fā)車間隔的約束進(jìn)行優(yōu)化模型構(gòu)建，通過選擇、交叉、變異、替換四種算子使用遺傳算法進(jìn)行計(jì)算，并對遺傳算法中引入模擬退火法以彌補(bǔ)遺傳算法較弱的局部搜索能力進(jìn)行簡單地闡述，其中對遺傳算法缺陷的闡述使我明確優(yōu)化傳統(tǒng)遺傳算法的目的[[]崔世彬.遺傳算法在公交調(diào)度中的應(yīng)用研究[D].吉林大學(xué)

理,2012,06]；徐瀟采用粒子群優(yōu)化算法進(jìn)行數(shù)學(xué)模型的求解，將自變量設(shè)置為發(fā)車間隔，以社會(huì)總成本作為目標(biāo)函數(shù)，以車輛滿載率、企業(yè)經(jīng)濟(jì)效益和發(fā)車時(shí)間間隔為約束條件構(gòu)建公交發(fā)車調(diào)度模型，其中發(fā)車間隔作為約束條件啟發(fā)我在構(gòu)建公交排班模型時(shí)，以發(fā)車間隔作為變量進(jìn)行建模[[]徐瀟.基于客流預(yù)測的公交調(diào)度優(yōu)化研究[D]鄭州大學(xué).2017]；張文貴以一個(gè)發(fā)車時(shí)間間隔序列作為決策變量，構(gòu)建乘客滿意度函數(shù)和公交公司滿意度的多目標(biāo)函數(shù)，并綜合考慮公交公司滿意度與乘客滿意度兩部分的影響構(gòu)建目標(biāo)函數(shù)，對決策變量進(jìn)行約束，采用遺傳算法進(jìn)行多目標(biāo)問題求解，并進(jìn)一步采用模擬退火算法的混合算法進(jìn)行研究，并將遺傳退火混合算法與單純遺傳算法的結(jié)果進(jìn)行比對，本文的適應(yīng)度參考張文貴的研究構(gòu)建適應(yīng)度函數(shù)，同時(shí)張文貴的研究中對于模型假設(shè)的設(shè)置也對本文起到重要的參考作用，并且參考其對比遺傳算法與遺傳退火模擬算法的做法，將遺傳算法優(yōu)化前后的收斂過程進(jìn)行比較分析[[]張文貴.基于遺傳算法的公交車輛調(diào)度優(yōu)化研究[D]中國地質(zhì)大學(xué)（北京）.2007]；王慶榮以兩個(gè)相鄰的發(fā)車間隔之差、最大最小發(fā)車時(shí)間間隔、乘客的滿載率等條件作為約束，以公交企業(yè)的運(yùn)營收入作為目標(biāo)函數(shù)構(gòu)建模型，本文對發(fā)車間隔的最大最小值進(jìn)行約束，正是參考王慶榮的模型進(jìn)行設(shè)置的，王慶榮通過遺傳退火算法進(jìn)行求解，并通過對約束條件的處理，優(yōu)化算法設(shè)計(jì)提供基于改進(jìn)GA-SA的優(yōu)化算法設(shè)計(jì)方案[[]王慶榮,袁占亭,張秋余.基于改進(jìn)遺傳—模擬退火算法的公交排班優(yōu)化研究[J].計(jì)算機(jī)應(yīng)用研究[]DebK,ChakrobortyP.TimeSchedulingofTransitSystemsWithTransferConsiderationsUsingGeneticAlgorithms[J].EvolutionaryComputation,1998,6(1):1.[]ParkSJ.BusNetworkSchedulingwithGeneticAlgorithmsandSimulation[D].2005.[]ChakrobortyP,DebK,SubrahmanyamPS.Optimalschedulingofurbantransitsystemsusinggeneticalgorithms[J].JournalofTransportationEngineering,1995,121(6):544-553.[]崔世彬.遺傳算法在公交調(diào)度中的應(yīng)用研究[D].吉林大學(xué)

理,2012,06[]徐瀟.基于客流預(yù)測的公交調(diào)度優(yōu)化研究[D]鄭州大學(xué).2017[]張文貴.基于遺傳算法的公交車輛調(diào)度優(yōu)化研究[D]中國地質(zhì)大學(xué)（北京）.2007[]王慶榮,袁占亭,張秋余.基于改進(jìn)遺傳—模擬退火算法的公交排班優(yōu)化研究[J].計(jì)算機(jī)應(yīng)用研究.2012(07)[]丁勇,姜楓,武玉艷.遺傳算法在公交調(diào)度中的應(yīng)用[J]計(jì)算機(jī)科學(xué).2016(S2)[]武斌.模糊多目標(biāo)規(guī)劃在公交優(yōu)化調(diào)度中的應(yīng)用[D].中國石油大學(xué),2010.[]韋尚成.臨界—遺傳算法在公交調(diào)度中的應(yīng)用[J].物流科技,2017,40(05):101-106.[]鄧芳玥,王歡.基于改進(jìn)遺傳算法的公交線路調(diào)度模型[J].交通世界,2017(33):158-159+176.[]陳曉旭,項(xiàng)煜,楊超,段紅勇,趙端.基于遺傳算法的公交線路發(fā)車間隔優(yōu)化[J].交通與運(yùn)輸,2020,36(05):86-90.徐晨暢,錢松榮.基于遺傳算法的突發(fā)公交智能調(diào)度算法[J].微型電腦應(yīng)用,2020,36(07):78-80.[]鞏舜妹,馮松寶,劉發(fā)明.基于遺傳算法的公交車發(fā)車間隔優(yōu)化模型[J].遼東學(xué)院學(xué)報(bào)(自然科學(xué)版),2020,27(04):284-289.[]徐晨暢,錢松榮.基于遺傳算法的突發(fā)公交智能調(diào)度算法[J].微型電腦應(yīng)用,2020,36(07):78-80.[]童剛.遺傳算法在公交調(diào)度中的應(yīng)用研究[J].計(jì)算工程,2005(13):29-31.[]岳大振.基于乘客到站率的公交發(fā)車時(shí)刻表優(yōu)化研究[D].山東大學(xué),2014.[]劉繼國.基于遺傳算法的公交排班系統(tǒng)研究[J].控制與信息技術(shù),2019(06):13-17+23.1.3研究現(xiàn)狀安溪縣隸屬于福建省泉州市，位于廈門、漳州、泉州三座城市的\t"/item/%E5%AE%89%E6%BA%AA%E5%8E%BF/_blank"閩南金三角西北部，又被稱作廈漳泉的后花園。總面積3057.28平方千米，2019年末戶籍人口121.10萬，常住人口102.7萬[[]安溪縣2018年國民經(jīng)濟(jì)和社會(huì)發(fā)展統(tǒng)計(jì)公報(bào)

．安溪縣人民政府][]安溪縣2018年國民經(jīng)濟(jì)和社會(huì)發(fā)展統(tǒng)計(jì)公報(bào)

．安溪縣人民政府安溪縣目前一共有17條公交線路正在營運(yùn)，部分線路承擔(dān)運(yùn)輸縣城與周邊鄉(xiāng)鎮(zhèn)之間旅客的功能，部分線路滿足起止點(diǎn)均在縣城范圍內(nèi)的旅客的出行需求。根據(jù)調(diào)查，安溪縣承擔(dān)運(yùn)輸縣城與周邊鄉(xiāng)鎮(zhèn)之間旅客的線路運(yùn)行狀況較為流暢，而在縣城范圍內(nèi)運(yùn)行的線路在非高峰時(shí)段運(yùn)行狀況流暢，道路交通量較穩(wěn)定，服務(wù)水平良好，然而高峰時(shí)間段在城區(qū)內(nèi)的道路交通量驟增，道路負(fù)擔(dān)加大，服務(wù)等級下降，所以縣城內(nèi)公交線路的運(yùn)行情況不佳，特別是在途徑縣政府路段、學(xué)校路段與醫(yī)院路段等人流密集區(qū)域的線路，經(jīng)常會(huì)出現(xiàn)道路堵塞的交通問題。本文以安溪縣2路公交運(yùn)營線路作為研究對象，通過交通調(diào)查和咨詢公交公司工作人員獲取相關(guān)數(shù)據(jù)，通過遺傳算法對2路公交線路的排班進(jìn)行優(yōu)化，經(jīng)過編碼解碼后得到基于遺傳算法的公交調(diào)度問題的仿真結(jié)果，從而優(yōu)化安溪縣2路公交線路的運(yùn)行效率并改善緩解2路公交車高峰時(shí)段在學(xué)校路段和縣城中心路段的交通擁堵情況。本文研究2路公交車線路的原因在于2路公交線路是一條典型的問題公交線路，作者通過與公交公司員工的交流和實(shí)際經(jīng)歷分析該路公交車是安溪縣公交線路中乘客量最大的線路之一，并且途徑恒興中學(xué)、沼濤小學(xué)、鳳城中學(xué)等學(xué)校路段以及銘選醫(yī)院、中山醫(yī)院等交通情況復(fù)雜的路段，在高峰時(shí)段經(jīng)常會(huì)遇到交通堵塞的問題。，因此以2路公交車線路作為研究對象來改善這一典型問題線路具有充分的現(xiàn)實(shí)依據(jù)和邏輯依據(jù)根據(jù)以往的傳統(tǒng)人工經(jīng)驗(yàn)調(diào)度的方式，在遇到高峰時(shí)期就容易出現(xiàn)調(diào)度員手忙腳亂，并未根據(jù)實(shí)際情況進(jìn)行合理的車輛調(diào)度，而是采用一刀切的方式按照調(diào)度員經(jīng)驗(yàn)進(jìn)行等時(shí)間間隔長度排班。這種經(jīng)驗(yàn)式排班并未有實(shí)際的理論數(shù)據(jù)支撐，全靠調(diào)度員的感性經(jīng)驗(yàn)進(jìn)行調(diào)度，這通常會(huì)引起兩種不利的結(jié)果，其一是發(fā)車間隔過小，導(dǎo)致公交發(fā)車頻繁，造成公交資源浪費(fèi)的同時(shí)使本就擁堵的道路承擔(dān)更多的交通負(fù)擔(dān)，惡化交通擁堵現(xiàn)象；其二是發(fā)車間隔過大，導(dǎo)致對該線路有出行需求的乘客在高峰期候車時(shí)間過長，公交車輛滿載率過高，車內(nèi)空間十分擁擠，導(dǎo)致乘客滿意度下降，使更多乘客出行選擇出租車、網(wǎng)約車等出行方式，導(dǎo)致道路空間資源利用率下降，惡化該路段的交通擁堵問題。1.4研究目的與意義通過調(diào)查得知安溪縣的道路在非高峰時(shí)間段服務(wù)水平處于較為優(yōu)良的水平，道路負(fù)擔(dān)較輕，只有在高峰時(shí)間段的一些人流密集區(qū)域，諸如學(xué)校、醫(yī)院、政府大樓等地區(qū)會(huì)發(fā)生擁堵狀況。為改善交通擁堵的問題，可以通過拓寬道路、道路改建的方式來提高道路的通行能力，從而提高高峰時(shí)間段的服務(wù)水平。但是考慮到該方法一來成本較高，二來大多數(shù)道路在非高峰時(shí)間段的服務(wù)等級本身就處于通暢水平，如果直接采用改建拓寬的方式未免過于浪費(fèi)資源；還可以通過改善縣城區(qū)域的道路網(wǎng)，提高相鄰道路的協(xié)同工作能力，從而提高路網(wǎng)的運(yùn)行效率，但由于完成整個(gè)路網(wǎng)的優(yōu)化工作量較大，作者當(dāng)前能力有限，難以順利完成，因此本文未采用路網(wǎng)優(yōu)化的方法；此外，還可以通過提高公共交通運(yùn)行效率從而吸引更多人選擇交通出行。因?yàn)楣卉囕v的道路空間利用率是最高的，所以吸引更多乘客乘坐公交車輛，提高道路的空間資源利用率，從而減少道路壓力，達(dá)到改善交通擁堵的目的。為緩解安溪縣高峰時(shí)間段縣政府地段、醫(yī)院路段、以及學(xué)校等人群密集區(qū)域發(fā)生交通擁擠以及交通堵塞的問題，通過優(yōu)化公交排班調(diào)度來提供公交車輛運(yùn)行的效率，從而吸引更多居民選擇公交出行，提供這些擁擠路段居民公交出行的比例，從而提高道路空間資源利用率，降低擁擠路段的道路交通量，減少道路負(fù)擔(dān)，提高道路服務(wù)水平，進(jìn)而從側(cè)面緩解交通壓力，改善交通堵塞的問題。1.5論文研究內(nèi)容作者主要由以下四個(gè)部分來進(jìn)行論文的研究：學(xué)習(xí)參考國內(nèi)外研究公交車輛排班優(yōu)化的遺傳算法求解問題的相關(guān)論文研究，確定論文的研究方向以及實(shí)現(xiàn)方法；根據(jù)實(shí)地調(diào)查安溪2路公交車的實(shí)際信息，通過咨詢公交公司員工以及網(wǎng)上查找相關(guān)資料等方式獲取安溪2路公交的現(xiàn)狀基本信息；根據(jù)調(diào)查獲得的基本信息進(jìn)行乘客滿意度模型的構(gòu)建，并且由現(xiàn)有的可運(yùn)營使用的公交車輛數(shù)、公交每趟周期運(yùn)行時(shí)間、相鄰兩發(fā)車間隔等條件設(shè)置約束條件，在構(gòu)建出公交排班調(diào)度的數(shù)學(xué)模型后，利用python實(shí)現(xiàn)遺傳算法進(jìn)行公交排班調(diào)度問題的求解，最終得出科學(xué)可行的公交車輛時(shí)刻表其中具體內(nèi)容如下：公交線路信息調(diào)查通過在2路公交線路首發(fā)站行政服務(wù)中心站觀測記錄研究時(shí)間段的每班車發(fā)車時(shí)刻，得到實(shí)際的發(fā)車時(shí)刻表，并且通過咨詢相關(guān)工作人員獲取該公交線路的基本信息，根據(jù)獲得的基本信息進(jìn)行公交排班模型的初步構(gòu)建；公交排班調(diào)度優(yōu)化模型求解當(dāng)前安溪公交公司仍然采用人工調(diào)度的傳統(tǒng)排班方式，發(fā)車頻率較低，未能充分利用公交車輛資源，本文結(jié)合實(shí)際線路信息進(jìn)行適應(yīng)度函數(shù)和約束條件的設(shè)立，并采用遺傳算法進(jìn)行求解；優(yōu)化結(jié)果分析根據(jù)標(biāo)準(zhǔn)遺傳算法求解公交排班問題，得到合理的最優(yōu)發(fā)車時(shí)刻表，并分析最優(yōu)發(fā)車時(shí)刻表的可行性和可靠性1.6研究思路和技術(shù)路線圖本文從提高城市公交車輛運(yùn)行效率入手，采用遺傳算法進(jìn)行2路公交線路的排班調(diào)度優(yōu)化，提高乘客的滿意度，從而吸引更多乘客選擇公交車輛出行，提高道路空間資源效率，改善城市的交通出行方式比例，逐漸形成健康的交通方式分布，可持續(xù)發(fā)展道路資源，改善交通擁堵問題。采用遺傳算法進(jìn)行計(jì)算求解，區(qū)別于傳統(tǒng)的分支定界法，遺傳算法具有以下幾個(gè)特點(diǎn)：首先遺傳算法對目標(biāo)函數(shù)的限制較少，目標(biāo)函數(shù)不需要連續(xù)可導(dǎo)，這對目標(biāo)函數(shù)的構(gòu)建提供了很大的幫助；其次遺傳算法并非傳統(tǒng)的隨機(jī)性地盲目枚舉，而是一種啟發(fā)性的算法，運(yùn)算的效率和準(zhǔn)確性更高；最后是遺傳算法的全局搜索能力強(qiáng)，并且具有良好的拓展性，可以和其他算法結(jié)合協(xié)同作用，比如模擬退火算法等[[]莫鴻強(qiáng).遺傳算法搜索能力和編碼方式研究[D].華南理工大學(xué),2001.][[]葛繼科,邱玉輝,吳春明,蒲國林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2008(10):2911-2916.[]莫鴻強(qiáng).遺傳算法搜索能力和編碼方式研究[D].華南理工大學(xué),2001.[]葛繼科,邱玉輝,吳春明,蒲國林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2008(10):2911-2916.[]趙振勇,王力,王保華,楊本娟.遺傳算法改進(jìn)策略的研究[J].計(jì)算機(jī)應(yīng)用,2006(S2):189-191.[]遺傳算法[M].西安交通大學(xué)出版社,王小平,曹立明著,2002[]遺傳算法原理及應(yīng)用[M].國防工業(yè)出版社,周明,孫樹棟編著,1999[]遺傳算法與工程優(yōu)化[M].清華大學(xué)出版社,[日]玄光男,[日]程潤偉著,2004根據(jù)調(diào)查安溪縣公交公司當(dāng)前仍采用人工調(diào)度的方法，高峰時(shí)間段每10-15分鐘發(fā)一趟車，而安溪公交公司2路公交車共有5輛，每輛車每趟行程35分鐘左右，因此完全可以做到將發(fā)車頻率進(jìn)一步提高，因?yàn)楦叻鍟r(shí)段公交車輛的滿載率通常處于較高的水平，因此如果發(fā)車間隔縮短，則公交車輛發(fā)車的班數(shù)就多，能夠承載的客流量越大，從而提高公交車運(yùn)行的效率。而采用遺傳算法實(shí)現(xiàn)智能信息化的優(yōu)化排班工作能得到更加科學(xué)合理的發(fā)車時(shí)刻表。其中技術(shù)路線圖如下所示圖1-1技術(shù)流程圖第二章公交調(diào)度排班模型2.1現(xiàn)狀分析安溪2路公交線路起點(diǎn)站為行政服務(wù)中心，終點(diǎn)站也是行政服務(wù)中心，首班車發(fā)車時(shí)間7：05，末班車發(fā)車時(shí)間18:40，共有34站。該線路經(jīng)過沼濤小學(xué)、安溪一中、鳳城中學(xué)、恒興中學(xué)、銘選醫(yī)院等地區(qū)，在高峰時(shí)段上下班車流與上下學(xué)車流混雜，極其容易形成交通擁堵，乘坐2路公交車的乘客多為學(xué)生與老人，學(xué)生乘坐公交車上下學(xué)的需求還是較大的。但是由于公交效率不高的原因使得部分家長選擇乘坐私家車進(jìn)行上下學(xué)接送，導(dǎo)致在高峰時(shí)間段本就擁堵的道路由于家長們將車輛?？吭诘缆分苓?，甚至部分私家車提前就在周邊道路停車等待孩子下課，造成道路負(fù)擔(dān)驟增，服務(wù)等級下降，道路越發(fā)擁堵，特別是途經(jīng)的鳳城中學(xué)、恒興中學(xué)學(xué)生人數(shù)眾多，且周邊私家車停車接送子女上下學(xué)的情況較多，因此導(dǎo)致高峰時(shí)間段交通堵塞問題嚴(yán)重。根據(jù)咨詢公交公司員工得知，安溪2路公交線路目前仍然采用落后的人工調(diào)度方法，一般采用10分鐘或者15分鐘的固定發(fā)車間隔進(jìn)行發(fā)車。固定發(fā)車間隔導(dǎo)致公交資源極大浪費(fèi)，經(jīng)濟(jì)效益低，同時(shí)固定的發(fā)車間隔必然導(dǎo)致發(fā)車次數(shù)降低，公交資源未能得到充分利用，公交公司盈利減少，并且人工調(diào)度在高峰時(shí)段采用固定發(fā)車間隔導(dǎo)致乘客候車時(shí)間長，滿意度下降，乘坐公交體驗(yàn)差，乘客滿意度低，同時(shí)還可能增加本就堵塞的交通道路的負(fù)擔(dān)，惡化交通擁堵。因此對2路公交排班調(diào)度優(yōu)化充分符合公交公司和乘客的共同利益。2.2發(fā)車時(shí)刻調(diào)查根據(jù)實(shí)地調(diào)查，2路公交首班車發(fā)車時(shí)刻7：05，末班車發(fā)車時(shí)刻18：20。因?yàn)榘蚕卉囋谄椒鍟r(shí)間段內(nèi)道路交通量較少，道路服務(wù)等級較高，通常只在高峰時(shí)間段內(nèi)道路服務(wù)等級才會(huì)處于擁堵的等級，因此本文優(yōu)化的研究對象時(shí)間段設(shè)置為安溪縣的高峰時(shí)段。通常交通工程學(xué)認(rèn)為7:00-10:00,17:00-20:00為一個(gè)城市的早晚高峰時(shí)段，但是不同城市的早晚高峰時(shí)段的劃分因?yàn)榫唧w情況不同而差別較大，本文依據(jù)掌上公交APP的發(fā)車時(shí)刻表系統(tǒng)根據(jù)歷史的發(fā)車時(shí)刻計(jì)算得到的安溪縣參考早高峰時(shí)段為7：05-10：00；晚高峰時(shí)段為16：00-20：00。但是結(jié)合2路公交車的運(yùn)行時(shí)間為早上7：05-18：40，因此對參考早晚高峰進(jìn)行修正為早高峰時(shí)段：7：05-10：00，晚高峰16：00-20：00。作者在2021年5月14-18日的7：05-10：00以及16：00-20：00，兩個(gè)時(shí)間段于路公交車首發(fā)站觀察記錄2路公交車的發(fā)車時(shí)刻。以這兩個(gè)高峰時(shí)間段作為研究對象進(jìn)行研究，高峰時(shí)間段2路公交車的實(shí)際發(fā)車時(shí)刻表如下圖所示：表2-12021年5月14日安溪2路公交早高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻17：0527：2637：4948：1158：3369：2079：45表2-22021年5月15日安溪2路公交早高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻17：0527：2938：1348：3659：0069：46表2-32021年5月16日安溪2路公交早高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻17：0527：2838：1048：3159：1369：37表2-42021年5月17日安溪2路公交早高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻17：0527：2238：1148：3659：0769：1279：36表2-32021年5月18日安溪2路公交早高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻17：0527：2138：0648：3359：0269：35表2-42021年5月14日安溪2路公交晚高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻116：01216：25316：46416：48517：10617：11717：31817：33918：051018：061118：18表2-52021年5月15日安溪2路公交晚高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻116：03216：27316：46416：47517：10617：11717：31817：55918：41表2-52021年5月16日安溪2路公交晚高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻116：01216：20316：47416：48517：09617：11717：29817：47918：34表2-52021年5月17日安溪2路公交晚高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻116：07216：12316：39416：40517：06617：08717：22817：42918：221018：40表2-52021年5月18日安溪2路公交晚高峰發(fā)車時(shí)刻表發(fā)車班次序號發(fā)車時(shí)刻116：02216：17316：37416：38517：01617：05717：27817：51918：37根據(jù)自變量設(shè)置方式，以5月14日的調(diào)查結(jié)果為例，早時(shí)間段首班車發(fā)車時(shí)刻為7：05，則第一個(gè)自變量為該發(fā)車時(shí)刻距首班車發(fā)車發(fā)車時(shí)刻的時(shí)間間隔，即為0，第二班公交車發(fā)車時(shí)刻為7：26，則第二個(gè)自變量為第二班車的發(fā)車時(shí)刻距首班車發(fā)車時(shí)刻的時(shí)間間隔，即為21，同理可得早高峰時(shí)間段的發(fā)車時(shí)刻表如下：0，21，44，66，99，135，160同理可得早高峰時(shí)間段的發(fā)車時(shí)刻表如下：0，24，45，47，69，70，90，92，124，125，137，139根據(jù)二進(jìn)制編碼形式將早高峰的發(fā)車時(shí)刻表轉(zhuǎn)化成二進(jìn)制形式，二進(jìn)制早高峰發(fā)車時(shí)刻表轉(zhuǎn)化結(jié)果如下：【00000000，00010101，00101100，01000010，01100011，10000111，10100000】根據(jù)二進(jìn)制編碼形式將晚高峰的發(fā)車時(shí)刻表轉(zhuǎn)化成二進(jìn)制形式，二進(jìn)制晚高峰發(fā)車時(shí)刻表轉(zhuǎn)化結(jié)果如下：【00000000，00011000，00101101，00101111，01000101，01000110，01011010，01011100，01111100，01111101，10001001，10001011】由適應(yīng)度函數(shù)計(jì)算可得，早高峰實(shí)際發(fā)車時(shí)刻表適應(yīng)度為0，晚高峰實(shí)際發(fā)車時(shí)刻表適應(yīng)度為5。2.3問題描述與模型假設(shè)公交運(yùn)行車輛的智能優(yōu)化一直是公共交通系統(tǒng)中需要解決的一個(gè)重要問題，本文研究的是搜索產(chǎn)生具有最佳乘客滿意度的公交發(fā)車時(shí)刻表。因此，本文研究的是公交調(diào)度問題中的靜態(tài)排班問題。本文以安溪2路公交車輛的發(fā)車班次作為研究對象，以乘客滿意度作為適應(yīng)度函數(shù)，以發(fā)車間隔作為變量設(shè)置約束條件，并通過對最大發(fā)車間隔進(jìn)行約束將研究的時(shí)間段控制在早高峰時(shí)段：7：05-10：00和晚高峰16：00-20：00之間。并且通過對外界條件進(jìn)行假設(shè)來簡化數(shù)學(xué)模型的復(fù)雜程度，在已知實(shí)際的發(fā)車時(shí)刻表的條件下，目標(biāo)是通過遺傳算法求解制定出可行的優(yōu)化時(shí)刻表，使優(yōu)化時(shí)刻表的適應(yīng)度相比實(shí)際情況得到較好的改善。同時(shí)，因?yàn)楣慌虐嗾{(diào)度優(yōu)化問題本身具有情況復(fù)雜，實(shí)際影響因素繁多，可能發(fā)生突發(fā)情況的特點(diǎn)，因此許多論文研究包括實(shí)際的調(diào)度工作也對復(fù)雜的交通環(huán)境進(jìn)行眾多約束，并做出諸多假設(shè)限制，在約束簡化之下構(gòu)建出理想環(huán)境下的數(shù)學(xué)模型。因此文章得出的優(yōu)化結(jié)果還遠(yuǎn)不能滿足實(shí)際公交排班方案的實(shí)時(shí)性要求，需要在文章構(gòu)建模型的基礎(chǔ)上，再投入公交線路運(yùn)營后，根據(jù)反饋的數(shù)據(jù)再進(jìn)行反復(fù)實(shí)驗(yàn)，優(yōu)化模型，才能夠提高數(shù)學(xué)模型的合理性和有效性。在構(gòu)建公交排班調(diào)度模型的研究上，雖然有許多學(xué)者在考慮各項(xiàng)因素的影響后，構(gòu)建與實(shí)際交通環(huán)境符合度較高的數(shù)學(xué)模型。但是考慮的因素越全面，數(shù)學(xué)模型的構(gòu)建就越復(fù)雜，一方面作者知識(shí)儲(chǔ)備有限，難以構(gòu)建過于復(fù)雜的模型，另一方面復(fù)雜的數(shù)學(xué)模型對計(jì)算軟件求解計(jì)算的負(fù)擔(dān)巨大，因而為了簡化計(jì)算，本文對數(shù)學(xué)模型進(jìn)行以下幾點(diǎn)假設(shè)：每輛公交車輛保持相同的速度勻速行駛，每趟行車時(shí)間保持一致且無變動(dòng)，期間不發(fā)生其他特殊交通情況；假設(shè)每輛車經(jīng)過后不留下乘客，時(shí)刻表最小單位為分鐘，每分鐘到達(dá)車站的乘客數(shù)量恒定，并且到達(dá)車站的乘客流量均勻；同一時(shí)間點(diǎn)乘客滿意度相同；并且忽略乘客上下車及停車時(shí)間公交車輛嚴(yán)格按發(fā)車時(shí)刻表時(shí)間到達(dá)車站。假設(shè)車輛勻速行駛能夠保證車輛每趟行程的行駛時(shí)間固定，便于以每趟行程時(shí)間作為限制的約束條件的設(shè)定，同時(shí)速度相同可以保證車輛在行駛過程中的行車序列保持一致；假設(shè)每輛車經(jīng)過后不留下乘客，公交車嚴(yán)格按時(shí)刻表到達(dá)站點(diǎn)以及不考慮車輛啟動(dòng)、制動(dòng)，以及乘客上下車的時(shí)間的目的在于將動(dòng)態(tài)的排班調(diào)度問題轉(zhuǎn)化為靜態(tài)調(diào)度問題；假設(shè)每分鐘到達(dá)車站的乘客數(shù)量固定，乘客流量均勻到達(dá)站點(diǎn)，同一時(shí)間點(diǎn)乘客滿意度相同，是為了構(gòu)建個(gè)體滿意度與整體乘客滿意度之間的聯(lián)系，最終以發(fā)車間隔作為變量構(gòu)建適應(yīng)度函數(shù)。2.4遺傳算法求解公交排班調(diào)度問題由如上模型假設(shè)（3）可推，當(dāng)乘客均勻到達(dá)車站且每單位時(shí)間到站乘客數(shù)量恒定，則我們可將每單位時(shí)間到站乘客數(shù)視為一個(gè)新的單位。由此容易得到在一個(gè)發(fā)車間隔內(nèi)，全體乘客的滿意度等于在各個(gè)單位時(shí)間到站乘客的滿意度之和。比如假設(shè)每分鐘到站乘客為5人，且之后乘客以每分鐘5人的速度均勻到達(dá)車站，在一個(gè)發(fā)車間隔為3分鐘的時(shí)間段內(nèi)，由假設(shè)（4）得，在第一個(gè)單位時(shí)間內(nèi)5個(gè)乘客每個(gè)乘客的為，在第二個(gè)單位時(shí)間內(nèi)5個(gè)乘客每個(gè)乘客的為，在第三個(gè)單位時(shí)間內(nèi)5個(gè)乘客每個(gè)乘客的為，則在這一時(shí)間段總的總的乘客滿意度為：由假設(shè)（3）可得，每分鐘到達(dá)站點(diǎn)乘客數(shù)量是恒定不變的，并且乘客均勻到站，這意味著以后每個(gè)單位都為5個(gè)乘客到站，因此可將共同因子5提出，由于每組數(shù)據(jù)到站乘客數(shù)相同，因此在后續(xù)滿意度計(jì)算比較過程中共同因子不影響比較結(jié)果，因此我們可將其忽略不計(jì)，精簡公式。同時(shí)由于interval_one_sat_degree主要取決于兩班車之間發(fā)車間隔的影響，因此為簡便計(jì)算，我們?nèi)“l(fā)車間隔作為構(gòu)建目標(biāo)函數(shù)的參數(shù)進(jìn)行滿意度的構(gòu)建。本文的編程邏輯如下，首先按照約束條件進(jìn)行初始化種群的生成；接下來對初始化種群中的個(gè)體分別計(jì)算其適應(yīng)度；第三步是根據(jù)各個(gè)個(gè)體的適應(yīng)度大小通過輪盤賭法進(jìn)行選擇，選出適應(yīng)度優(yōu)良的父代和母代初始種群；第四步將父代和母代進(jìn)行二進(jìn)制編碼，轉(zhuǎn)化為二進(jìn)制形式，方便接下來的交叉和變異；第五步是根據(jù)交叉概率隨機(jī)選擇父代與母代完成單點(diǎn)交叉；第六步則按照變異概率對種群中的個(gè)體進(jìn)行變異操作；最后循環(huán)多代后得到適應(yīng)度最高的個(gè)體，即乘客滿意度最高的發(fā)車時(shí)刻表。第三章遺傳算法求解3.1遺傳算法介紹遺傳算法（GA）是模仿生物再自然界中繁衍生殖、遺傳進(jìn)化的一種自適應(yīng)啟發(fā)式全局搜索算法，通過模擬自然界生物遺傳進(jìn)化過程中的優(yōu)勝劣汰、適者生存的模式來實(shí)現(xiàn)全局搜索最優(yōu)解的目的。遺傳算法是一種通過計(jì)算機(jī)仿真的方式進(jìn)行數(shù)學(xué)模型求解的方法，在求解情況復(fù)雜的組合優(yōu)化問題時(shí)，對比傳統(tǒng)的常規(guī)計(jì)算方法，具有運(yùn)算效率高，運(yùn)算速度快，對目標(biāo)函數(shù)無連續(xù)可導(dǎo)要求等特點(diǎn)，能夠較快的得到最優(yōu)或近似最優(yōu)結(jié)果。遺傳算法如今已經(jīng)被廣泛地應(yīng)用于機(jī)器學(xué)習(xí)、排版調(diào)度、信號配時(shí)以及人工智能等領(lǐng)域。遺傳算法（GA）是一種以進(jìn)化論和孟德爾遺傳理論為基礎(chǔ)地模擬自然界物競天擇，適者生存的啟發(fā)式搜索算法，它的核心在于模擬進(jìn)化論中的物競天擇，優(yōu)勝劣汰的效果，將滿足目標(biāo)函數(shù)約束條件的可行解空間作為遺傳算法中的初始化群體，即將滿足目標(biāo)函數(shù)約束條件下的每一個(gè)解看作一個(gè)個(gè)體，每一個(gè)個(gè)體以二進(jìn)制或進(jìn)制數(shù)字串表示。而個(gè)體中的每一個(gè)元素則代表著自然界中染色體所有的基因組成的群體，再根據(jù)構(gòu)建的適應(yīng)度函數(shù)對每一個(gè)染色體進(jìn)行評價(jià)，一個(gè)個(gè)體所有染色體的適應(yīng)度的總和則代表這個(gè)個(gè)體的適應(yīng)度。遺傳算法首先隨機(jī)地生成滿足約束條件的一系列可行解，再計(jì)算其適應(yīng)度，根據(jù)每個(gè)個(gè)體的適應(yīng)度數(shù)值大小，對初始化種群的個(gè)體進(jìn)行選擇、交叉、變異等工作，賦予適應(yīng)度高的個(gè)體更多進(jìn)行遺傳操作的機(jī)會(huì)，篩選出適應(yīng)度較高的具有優(yōu)良基因的個(gè)體，再將篩選出來的優(yōu)良個(gè)體作為新的群體繼續(xù)進(jìn)行下一代的遺傳操作，由于每一代的父代母代群體都是經(jīng)過上一輪選擇、交叉、變異篩選出來的子代個(gè)體，因此每一代個(gè)體都繼承了上一代個(gè)體的優(yōu)良基因，并且更加優(yōu)秀。同時(shí)遺傳算法作為一種仿生算法，考慮到自然界中的遺傳過程經(jīng)過交叉變異后的個(gè)體并非完全繼承父代母代的優(yōu)良基因，即兩個(gè)優(yōu)良個(gè)體在交叉變異后可能生成品質(zhì)相對父代個(gè)體較為低劣的子代個(gè)體，在自然界中這種現(xiàn)象普遍存在，在算法中則表現(xiàn)為允許交叉變異后產(chǎn)生的無效個(gè)體保留，避免可行解在進(jìn)行多輪遺傳操作后陷入局部解中趨于收斂的困境。遺傳算法就是這樣一種朝著更優(yōu)解的方向反復(fù)迭代，反復(fù)篩選，同時(shí)允許無效個(gè)體參與操作保證其多樣性的算法[[]HollandJB,HollandJ,HollandJH,etal.AdaptioninNaturalandArtificialSystems[J].AnnArbor,1975,6(2):126–137.][]HollandJB,HollandJ,HollandJH,etal.AdaptioninNaturalandArtificialSystems[J].AnnArbor,1975,6(2):126–137.生物是以種群為基本單位進(jìn)行生物生存和進(jìn)化的，同樣的，遺傳算法也以多個(gè)滿足條件的個(gè)體組成的集體作為研究對象。類似生物遺傳變異進(jìn)化的過程，遺傳算法是在一個(gè)可行的初始集體中不斷的迭代，篩選的過程。滿足條件的初始化群體一代又一代地反復(fù)進(jìn)行交叉、變異地遺傳操作，每次按照物競天擇，適者生存地原則讓適應(yīng)度高地個(gè)體有更多的機(jī)會(huì)參與到遺傳操作的同時(shí)，還保留適應(yīng)度函數(shù)較低的個(gè)體，允許其參與保留到下一代中，為交叉變異提供更多的方向，避免遺傳算法過早收斂，陷入死胡同中，如此以來，最終在經(jīng)過多輪遺傳后得到的最優(yōu)良的個(gè)體即滿足目標(biāo)函數(shù)約束條件的最優(yōu)或近似最優(yōu)解[[]Kidwai,F.A.etal.“AGENETICALGORITHMBASEDBUSSCHEDULINGMODELFORTRANSITNETWORK.”(2005).][]Kidwai,F.A.etal.“AGENETICALGORITHMBASEDBUSSCHEDULINGMODELFORTRANSITNETWORK.”(2005).生物主要是通過交叉、變異的遺傳操作來實(shí)現(xiàn)遺傳進(jìn)化的過程。因此遺傳算法中在可行解的解域中搜尋最優(yōu)或近似最優(yōu)解的過程也是通過選擇算子、交叉算子、變異算子三種遺傳算子來進(jìn)行實(shí)現(xiàn)的[[]Y.GaoandD.Song,"ANewImprovedGeneticAlgorithmsanditsPropertyAnalysis,"2009ThirdInternationalConferenceonGeneticandEvolutionaryComputing,Guilin,2009,pp.73-76,doi:10.1109/WGEC.2009.150.][]Y.GaoandD.Song,"ANewImprovedGeneticAlgorithmsanditsPropertyAnalysis,"2009ThirdInternationalConferenceonGeneticandEvolutionaryComputing,Guilin,2009,pp.73-76,doi:10.1109/WGEC.200編碼方案與初始化本文目標(biāo)函數(shù)選用距離首班車發(fā)車時(shí)間的整數(shù)集合（單位：分鐘）作為自變量，比如首班車發(fā)車時(shí)間為7：05，則自變量；第二班車發(fā)車時(shí)間若為7：15，則距離首班車發(fā)車時(shí)間經(jīng)過10分鐘，則自變量；第三班發(fā)車時(shí)間若為7：20，則距離首班車發(fā)車時(shí)間經(jīng)過15分鐘，則自變量；當(dāng)?shù)趍班車發(fā)車時(shí)間為10:05，則自變量，則一個(gè)發(fā)車時(shí)刻表即自變量為：（單位：分鐘）其中n表示種群個(gè)數(shù)，m表示基因長度。對自變量的約束條件如下：公式（3-1）本文的編碼方式采用二進(jìn)制編碼方式，即將原本十進(jìn)制的自變量轉(zhuǎn)化為二進(jìn)制形式進(jìn)行交叉、變異的操作，并且由于只考慮高峰時(shí)間段的排班調(diào)度，因此取高峰段進(jìn)行研究，故自變量X的定義域?yàn)閇0,180](單位：分鐘)，因?yàn)樽畲笾禐?80，因此轉(zhuǎn)化為二進(jìn)制為10110100，故二進(jìn)制形式的最多取8位。因此我們定義二進(jìn)制元素的長度為8位。比如將上文所舉例的自變量進(jìn)行二進(jìn)制編碼，將轉(zhuǎn)化為二進(jìn)制：使用距離首班車發(fā)車時(shí)間作為自變量有以下幾個(gè)優(yōu)點(diǎn)：非常直觀，容易對生成的數(shù)據(jù)進(jìn)行校核，可以非常直觀地看出經(jīng)過變異或交叉后生成的不滿足約束條件的新個(gè)體；方便目標(biāo)函數(shù)的構(gòu)建，便于處理復(fù)雜的約束條件，取相鄰兩自變量之差為發(fā)車間隔，即乘客候車最大時(shí)長。使用二進(jìn)制編碼方式有以下幾個(gè)優(yōu)點(diǎn)：二進(jìn)制對遺傳算法的敏感性較強(qiáng)；二進(jìn)制編碼方式在進(jìn)行遺傳算法的交叉步驟時(shí)方便進(jìn)行單點(diǎn)交叉，多點(diǎn)交叉等多種交叉方式；二進(jìn)制編碼方式在進(jìn)行遺傳算法的突變步驟時(shí)只需將原基因座上的指定位置上0突變?yōu)?,1突變?yōu)?即可實(shí)現(xiàn)突變的操作[[]M.Yue,B.Guo,T.HuandX.Guo,"Theresearchofparametersofgeneticalgorithmandcomparisonwithparticleswarmoptimizationandshuffledfrog-leapingalgorithm,"20092ndInternationalConferenceonPowerElectronicsandIntelligentTransportationSystem(PEITS),Shenzhen,2009,pp.77-80,doi:10.1109/PEITS.2009.5406960.][]M.Yue,B.Guo,T.HuandX.Guo,"Theresearchofparametersofgeneticalgorithmandcomparisonwithparticleswarmoptimizationandshuffledfrog-leapingalgorithm,"20092ndInternationalConferenceonPowerElectronicsandIntelligentTransportationSystem(PEITS),Shenzhen,2009,pp.77-80,doi:10.1109/PEITS.2009.5406960.種群初始化即生成滿足約束條件的種群個(gè)體pop,并且對pop進(jìn)行統(tǒng)一格式處理，方便后續(xù)的目標(biāo)函數(shù)計(jì)算。首先初始化生成bus_num個(gè)數(shù)，其中bus_num表示該線路能夠發(fā)車的車輛數(shù)。由調(diào)查可知安溪縣2路共有5輛車投入運(yùn)營，故bus_num取5，再根據(jù)首趟5輛車的發(fā)車時(shí)間進(jìn)行條件約束，生成后續(xù)的發(fā)車時(shí)間。首先由假設(shè)可得，各輛車保持相同速度運(yùn)行，因此通過相同線路所用時(shí)間相同，并且首趟的5輛車先后順序是固定的，即第2輛車一定位于第1輛車后，第3輛車前，同時(shí)因?yàn)橐构卉囕v發(fā)車次數(shù)盡可能多，盡可能的滿足乘客通行需求和公交公司盈利需求，因此在有限的公交車輛條件下要盡可能地發(fā)車，即5輛車都要在一趟行程時(shí)間內(nèi)發(fā)完。其次考慮相鄰兩班車發(fā)車間隔要控制在一個(gè)有限范圍，提高隨機(jī)生成個(gè)體的合理性，因此還需要對相鄰兩班車發(fā)車間隔進(jìn)行約束。由于該線路起點(diǎn)站就是終點(diǎn)站，是一條閉合繞行線路，因此不用考慮來回行程時(shí)間。根據(jù)調(diào)查可得每輛公交車從起點(diǎn)到終點(diǎn)一趟的時(shí)間為35分鐘，前面推得各車輛運(yùn)行順序是固定的，一共五輛車，因此可得相隔五班車之間的發(fā)車間隔要大于等于一趟車的行程，即要保證一輛車走完一趟才能開始下一趟，故設(shè)置約束條件保證相隔五班車之間的發(fā)車間隔要大于等于35分鐘。并且為了提高搜索效率，使發(fā)車班次盡可能增加，因此我們對同一輛車兩趟發(fā)車時(shí)間間隔設(shè)置一個(gè)上限，使其不超過60分鐘；同時(shí)為了增加公交車輛發(fā)車班次，提高公交車輛循環(huán)效率，為保證首趟五班車盡可能在一趟時(shí)間35分鐘內(nèi)全部發(fā)完，則需對首趟五班車的相鄰發(fā)車間隔進(jìn)行約束，使其間隔不能過長，否則發(fā)車班次將會(huì)減少。按照上述約束條件生成初始發(fā)車時(shí)刻表個(gè)體，考慮到后續(xù)適應(yīng)度函數(shù)計(jì)算，交叉，變異的步驟需對初始個(gè)體的位數(shù)有嚴(yán)格要求，如若不統(tǒng)一相同基因長度，則在進(jìn)行交叉或者變異的過程中，容易產(chǎn)生無效個(gè)體，降低計(jì)算效率，削弱優(yōu)良解的檢索能力。因此我們需要對生成的個(gè)體進(jìn)行統(tǒng)一格式操作，方便后續(xù)步驟的進(jìn)行。在編程工作上先隨機(jī)生成多組發(fā)車初始時(shí)刻表個(gè)體，記錄每一個(gè)個(gè)體的基因長度，循環(huán)結(jié)束后輸出最大基因長度，并將其他未達(dá)到最大基因長度的個(gè)體以最后一位數(shù)值進(jìn)行復(fù)制補(bǔ)齊。其中以最后一位基因長度補(bǔ)齊的原因在于目標(biāo)函數(shù)以相鄰兩發(fā)車間隔作為參數(shù)，因此復(fù)制最后一位數(shù)值能夠使達(dá)到末班車后，前后兩班發(fā)車時(shí)間之差為零，可自動(dòng)消除末班車后的基因位對目標(biāo)函數(shù)的影響誤差，并且又能夠滿足統(tǒng)一基因座格式的需求。最終生成滿足約束條件并且基因長度相同的初始化種群pop。3.3適應(yīng)度函數(shù)根據(jù)魏東洋的研究可知，公交乘客滿意度評價(jià)指標(biāo)體系中一級指標(biāo)快捷性所占權(quán)重為22.4%，其中二級指標(biāo)候車時(shí)間所占權(quán)重為6.86%，在同級指標(biāo)中所占權(quán)重僅次于最大出行時(shí)耗8.83%以及公交的票制標(biāo)價(jià)14.93%[[]魏東洋.公交乘客滿意度評價(jià)指標(biāo)體系研究及調(diào)查實(shí)例分析[]魏東洋.公交乘客滿意度評價(jià)指標(biāo)體系研究及調(diào)查實(shí)例分析[A].中國城市規(guī)劃學(xué)會(huì)城市交通規(guī)劃學(xué)術(shù)委員會(huì).交通治理與空間重塑——2020年中國城市交通規(guī)劃年會(huì)論文集[C].中國城市規(guī)劃學(xué)會(huì)城市交通規(guī)劃學(xué)術(shù)委員會(huì):中國城市規(guī)劃設(shè)計(jì)研究院城市交通專業(yè)研究院,2020:7.公式（3-2)其中i表示第i個(gè)個(gè)體，j表示第j個(gè)發(fā)車間隔，表示第i個(gè)發(fā)車時(shí)刻表中第j個(gè)發(fā)車間隔的乘客滿意度，表示表示第i個(gè)發(fā)車時(shí)刻表的適應(yīng)度。3.4選擇算子本文采用輪盤賭法進(jìn)行選擇操作，原理是根據(jù)不同個(gè)體的適應(yīng)度大小來進(jìn)行選擇，適應(yīng)度越高的個(gè)體被選中的概率越大，因此經(jīng)過選擇后的父代和母代整體的適應(yīng)度處于較高水平。在編碼上實(shí)現(xiàn)輪盤賭法的過程如下，首先將各個(gè)個(gè)體的適應(yīng)度進(jìn)行求和，得到一個(gè)整體適應(yīng)度F_sum，再利用python的隨機(jī)數(shù)函數(shù)隨機(jī)生成范圍[0,F_sum]的隨機(jī)數(shù)。通過循環(huán)語句進(jìn)行檢索，隨機(jī)數(shù)落在哪個(gè)長度區(qū)間，該區(qū)間所對應(yīng)的個(gè)體即被選擇添加至父代的列表中，直至添滿父代列表循環(huán)結(jié)束。同理對母代進(jìn)行選擇操作，由此得到適應(yīng)度優(yōu)良的父代母代。3.5交叉算子將選擇的父代母代轉(zhuǎn)化為二進(jìn)制，根據(jù)交叉概率進(jìn)行單點(diǎn)交叉操作。本文采用的編碼邏輯是只遍歷所有的父代，對于每個(gè)父代隨機(jī)選擇一個(gè)母代，其中通過python自帶的隨機(jī)數(shù)函數(shù)實(shí)現(xiàn)隨機(jī)選擇的功能，即隨機(jī)生成一個(gè)母代數(shù)量區(qū)間范圍內(nèi)的整數(shù)，隨機(jī)出來的數(shù)即代表選擇母代中的哪一個(gè)個(gè)體進(jìn)行交叉。并且根據(jù)設(shè)置的交叉概率進(jìn)行判斷是否個(gè)體是否進(jìn)行交叉。若不滿足則保留該父代和母代添加至子代列表中，滿足則隨機(jī)選取基因座上的某一點(diǎn)，截?cái)喔复复擖c(diǎn)處的基因并交叉，交叉后的子代添加至子代列表中。由于交叉操作是在二進(jìn)制代碼中實(shí)現(xiàn)，因此交叉后的個(gè)體轉(zhuǎn)化為十進(jìn)制形式可能不滿足初始化種群部分中的約束條件，則稱交叉后不滿足約束條件的個(gè)體為無效個(gè)體，對于交叉及變異可能產(chǎn)生的無效個(gè)體予以保留，遺傳算法允許無效個(gè)體的存在。3.6變異算子根據(jù)變異概率對進(jìn)行交叉步驟后的群體進(jìn)行單點(diǎn)變異操作。本文采用的編碼邏輯是遍歷所有的交叉群體中的個(gè)體，根據(jù)設(shè)置的變異概率，若不滿足則保留該父代和母代添加至子代列表中，滿足則隨機(jī)選取基因座上的某一點(diǎn)，將該點(diǎn)位上的0變異為1，1變異為0。由于變異操作是在二進(jìn)制代碼中實(shí)現(xiàn)，因此變異后的個(gè)體轉(zhuǎn)化為十進(jìn)制形式可能不滿足初始化種群部分中的約束條件，則稱變異后不滿足約束條件的個(gè)體為無效個(gè)體，為避免在計(jì)算迭代過程中陷入局部解的困境，允許適應(yīng)度較低的個(gè)體以及無效個(gè)體的存在，允許在計(jì)算途中接受差解進(jìn)入變異的群體當(dāng)中。3.7傳統(tǒng)遺傳算法總結(jié)根據(jù)查閱遺傳算法求解公交線網(wǎng)優(yōu)化以及公交排班調(diào)度問題的相關(guān)文獻(xiàn)和研究，本文利用python進(jìn)行編碼實(shí)現(xiàn)遺傳算法程序。先根據(jù)調(diào)查得到的公交線路信息構(gòu)建目標(biāo)函數(shù)，再根據(jù)約束條件隨即生成滿足約束限制的初始種群個(gè)體，再以初始化種群個(gè)體作為父代按照適應(yīng)度大小進(jìn)行擇優(yōu)選擇，之后再進(jìn)行交叉和變異，得到經(jīng)過一輪遺傳進(jìn)化后的子代，將子代作為下一輪遺傳進(jìn)化的父代返回到選擇步驟繼續(xù)下一輪循環(huán)，直至滿足設(shè)置的代數(shù)或者結(jié)果趨于收斂，即得到遺傳算法的最優(yōu)或近似最優(yōu)解。[[]MauroDell'Amico,MatteoFischetti,PaoloToth.HeuristicAlgorithmsfortheMultipleDepotVehicleSchedulingProblem.1993,39(1)[]MauroDell'Amico,MatteoFischetti,PaoloToth.HeuristicAlgorithmsfortheMultipleDepotVehicleSchedulingProblem.1993,39(1)近年來隨著智能交通的興起，越來越多學(xué)者使用遺傳算法求解公交排班調(diào)度問題，其原因在于遺傳算法本身就是用于求解組合優(yōu)化模型問題，而公交車的排班發(fā)車管理本身具有較大的組合優(yōu)化特征，因此越來越多的學(xué)者致力于遺傳算法在求解公交排班調(diào)度優(yōu)化問題上的研究[[]XiaoqiangWang,RenQing-dao-er-ji.Applicationofoptimizedgeneticalgorithmbasedonbigdatainbusdynamicscheduling.2019,22(6):15439-15446.][[]XiaoqiangWang,RenQing-dao-er-ji.Applicationofoptimizedgeneticalgorithmbasedonbigdatainbusdynamicscheduling.2019,22(6):15439-15446.[]XiaoqiangWang,RenQing-dao-er-ji.Applicationofoptimizedgeneticalgorithmbasedonbigdatainbusdynamicscheduling.2019,22(6):15439-15446.[]XiaoqiangWang,RenQing-dao-er-ji.Applicationofoptimizedgeneticalgorithmbasedonbigdatainbusdynamicscheduling.2019,22(6):15439-15446.3.8優(yōu)化基本思想遺傳算法作為一種全局搜索能力很強(qiáng)的算法，雖然由于其高效的搜索能力和簡單易懂的結(jié)構(gòu)再公交排班調(diào)度領(lǐng)域得到廣泛的應(yīng)用，但是遺傳算法在搜索最優(yōu)解的過程中仍然出現(xiàn)許多不可避免的問題。其中最主要的問題在于標(biāo)準(zhǔn)遺傳算法允許無效個(gè)體參與下一代的遺傳進(jìn)化過程，并且無效個(gè)體的這種參與行為往往是將更為優(yōu)良的個(gè)體所替換，如此以來就使得經(jīng)過按照適應(yīng)度函數(shù)擇優(yōu)選擇后的群體，在經(jīng)過交叉和變異后，引入適應(yīng)度較差的無效個(gè)體。無效個(gè)體在下一代的交叉中可能與優(yōu)良個(gè)體的基因交叉互換，對優(yōu)良個(gè)體的基因造成污染，這就導(dǎo)致了每一代優(yōu)良個(gè)體的性能離散度較高，運(yùn)行結(jié)果無法很好收斂，最優(yōu)個(gè)體適應(yīng)度曲線圖波動(dòng)起伏巨大。由此不難看出，導(dǎo)致結(jié)果波動(dòng)較大的元兇在于每代經(jīng)過交叉變異后產(chǎn)生的無效個(gè)體，一來可能將優(yōu)良個(gè)體所替換，二來引入的無效個(gè)體在下一代的交叉過程中又容易與其他優(yōu)良個(gè)體交叉，生成新的無效個(gè)體，污染種群的優(yōu)良基因，這就導(dǎo)致運(yùn)行結(jié)果可能驟然變差。但是保留無效個(gè)體并非沒有益處，無效個(gè)體與優(yōu)良個(gè)體的交叉結(jié)合為進(jìn)化提供更多的可能性，有可能雜交出更為優(yōu)良的超級個(gè)體。因此傳統(tǒng)遺傳算法輸出的結(jié)果表現(xiàn)為每代最優(yōu)良的個(gè)體經(jīng)過一段時(shí)間的遺傳進(jìn)化就會(huì)被改變或被取代，至于進(jìn)化方向好壞是隨機(jī)生成的結(jié)果。因此我們希望加強(qiáng)遺傳算法的優(yōu)勝劣汰的效果，并且在使遺傳算法運(yùn)行結(jié)果趨于收斂的同時(shí)，仍然要保留適應(yīng)度較低的無效個(gè)體參與下一輪遺傳的權(quán)力，避免遺傳算法過早進(jìn)入收斂狀態(tài)的問題。改進(jìn)傳統(tǒng)遺傳算法的基本思想在于要提高遺傳算法收斂性的同時(shí)還要避免其進(jìn)入過早成熟的狀態(tài)，保持進(jìn)化的多樣性。同時(shí)為了保證優(yōu)化后的算法仍然保證遺傳算法的固有優(yōu)勢，本文基于原來遺傳算法的邏輯結(jié)構(gòu)，在原有的編碼上對遺傳算子進(jìn)行改進(jìn)。對遺傳算子進(jìn)行改進(jìn)如下：首先我在交叉和變異的操作后都增加一個(gè)對無效個(gè)體的檢測步驟，在交叉和變異之后對產(chǎn)生的個(gè)體進(jìn)行檢測，檢測是否符合約束條件，若不符合約束條件則進(jìn)行標(biāo)記。并且在適應(yīng)度函數(shù)計(jì)算步驟，對標(biāo)記個(gè)體施加一個(gè)懲罰項(xiàng)。懲罰項(xiàng)大小根據(jù)傳統(tǒng)遺傳算法中個(gè)體的適應(yīng)度進(jìn)行初步擬定，再通過多次實(shí)驗(yàn)的結(jié)果調(diào)整懲罰項(xiàng)大小，根據(jù)多次調(diào)整的結(jié)果確定最為擬合實(shí)驗(yàn)結(jié)果的懲罰項(xiàng)數(shù)值。其次，交叉步驟中，改進(jìn)優(yōu)化為先將選擇出的父代母代復(fù)制一遍，之后將每一個(gè)復(fù)制的父代母代都隨機(jī)選擇一個(gè)個(gè)體進(jìn)行隨機(jī)點(diǎn)位上的單點(diǎn)交叉操作，并且將交叉后的個(gè)體與原有父代母代均放入交叉后的種群中進(jìn)行檢測，對無效個(gè)體進(jìn)行標(biāo)記后進(jìn)入變異操作。如此改進(jìn)的邏輯在于不同于原有交叉步驟的替換，而是先將父代母代進(jìn)行復(fù)制，之后的交叉操作在復(fù)制的個(gè)體上進(jìn)行操作，這樣做能夠保留父代母代的優(yōu)良個(gè)體，同時(shí)對交叉后的個(gè)體進(jìn)行懲罰，再進(jìn)入下一輪按照適應(yīng)度大小進(jìn)行擇優(yōu)選擇。這樣改進(jìn)后的好處在于在交叉過程中并沒有按照概率隨機(jī)選擇個(gè)體進(jìn)行交叉，而是保留父代母代與交叉后的子代進(jìn)入下一輪的擇優(yōu)競爭中，增加了優(yōu)良父代保留的可能性，避免優(yōu)良父代母代由于概率被隨機(jī)交叉抹殺其優(yōu)良性狀的問題出現(xiàn)。對無效個(gè)體進(jìn)行懲罰，這是因?yàn)楫a(chǎn)生的無效個(gè)體由于不受約束條件約束而適應(yīng)度飆升，在下一輪按照適應(yīng)大小被選中的概率也隨之大幅提高，若不施加懲罰項(xiàng)，則多代之后的子代均是適應(yīng)度極高但是不滿足約束條件的無效個(gè)體。同時(shí)，施加懲罰項(xiàng)還能夠保留無效個(gè)體被選中的概率，增加遺傳進(jìn)化的多樣性。但是這么做的缺點(diǎn)在于計(jì)算量驟增，不同于原有算法直接在原有數(shù)組上進(jìn)行修改操作，改進(jìn)后的算法對每個(gè)數(shù)組要進(jìn)行復(fù)制操作。每次復(fù)制一個(gè)數(shù)組操作相當(dāng)于把每個(gè)數(shù)字都計(jì)算一遍，特別是對于轉(zhuǎn)化為二進(jìn)制形式的數(shù)組，其計(jì)算量將成倍增加，程序運(yùn)行時(shí)間大幅增加。3.9優(yōu)化GA流程優(yōu)化算法流程如下：STEP1初始化種群，按照約束條件隨機(jī)生成一定數(shù)量pop_num規(guī)模的個(gè)體；STEP2計(jì)算適應(yīng)度大小。按照適應(yīng)度函數(shù)計(jì)算每個(gè)個(gè)體的適應(yīng)度大小，并且對標(biāo)記個(gè)體的適應(yīng)度減去一個(gè)懲罰值作為懲罰；STEP3根據(jù)適應(yīng)度大小按概率選擇從種群中選擇個(gè)體作為父代和母代；STEP4交叉：復(fù)制父代母代，對復(fù)制的父代母代進(jìn)行隨機(jī)單點(diǎn)交叉，將交叉后的子代與父代母代個(gè)體一同放入種群中；STEP5檢測群體中的個(gè)體，對檢測出的不符合約束條件的無效個(gè)體加以標(biāo)記；STEP6變異：根據(jù)變異概率對種群中個(gè)體進(jìn)行單點(diǎn)變異操作；STEP7檢測群體中的個(gè)體，對檢測出的不符合約束條件的無效個(gè)體加以標(biāo)記；STEP8若滿足收斂條件，達(dá)到預(yù)先設(shè)定的進(jìn)化代數(shù)，則輸出結(jié)果，否則返回STEP2優(yōu)化遺傳算法流程圖如圖所示：圖3-1優(yōu)化遺傳算法流程圖第四章仿真結(jié)果分析4.1參數(shù)確定初始擬定初始化種群個(gè)體數(shù)量500,選擇父代數(shù)量100，交叉概率0.9%，變異概率為0.02%。圖4-1首次運(yùn)行各代最優(yōu)個(gè)體適應(yīng)度曲線圖根據(jù)首次運(yùn)行的結(jié)果不難看出，在經(jīng)過前646代的遺傳進(jìn)化時(shí)就產(chǎn)生了本次實(shí)驗(yàn)的適應(yīng)度最高的最優(yōu)個(gè)體，在之后的遺傳過程中反而將優(yōu)良個(gè)體的優(yōu)良特征給遺失了，后代的最優(yōu)個(gè)體適應(yīng)度均不如前646代個(gè)體，同時(shí)每代最優(yōu)個(gè)體的適應(yīng)度離散度較低，說明交叉變異在遺傳進(jìn)化過程中的影響較小，遺傳算法可能出現(xiàn)陷入局部解的困境。為保證該參數(shù)條件下所進(jìn)行實(shí)驗(yàn)的結(jié)果具有普遍的參考意義，避免該實(shí)驗(yàn)為該參數(shù)設(shè)置下的特例，現(xiàn)保持當(dāng)前參數(shù)進(jìn)行多組實(shí)驗(yàn)。圖4-2第一次重復(fù)實(shí)驗(yàn)最優(yōu)個(gè)體適應(yīng)度曲線圖圖4-3第二次重復(fù)實(shí)驗(yàn)最優(yōu)個(gè)體適應(yīng)度曲線圖圖4-4第三次重復(fù)實(shí)驗(yàn)最優(yōu)個(gè)體適應(yīng)度曲線圖由以上多組實(shí)驗(yàn)可以看出遺傳進(jìn)化過程中每代個(gè)體在經(jīng)過交叉變異后仍保留上一代最優(yōu)個(gè)體的代數(shù)較長，即可能過早陷入局部解中而喪失搜索其他最優(yōu)解的可能。因此針對這個(gè)問題將交叉概率和遺傳變異調(diào)高，同時(shí)增大初始化種群的個(gè)體數(shù)量，以提供更多樣本提供更多的進(jìn)化方向。第一次調(diào)整后的參數(shù)如下：初始種群個(gè)體數(shù)量到1000，選擇父代數(shù)量200，交叉概率9%，變異概率為0.1%。圖4-5第一次參數(shù)調(diào)整后最優(yōu)個(gè)體適應(yīng)度曲線圖調(diào)整參數(shù)后的運(yùn)行結(jié)果如圖6-5所示，由圖可見，調(diào)整參數(shù)后產(chǎn)生的最優(yōu)良個(gè)體的適應(yīng)度相比調(diào)整前有所提高，并且結(jié)果波動(dòng)起伏較大，表明了相比調(diào)整前遺傳算子在遺傳進(jìn)化過程中起到較大的作用。證明調(diào)整后的結(jié)果與前期預(yù)計(jì)的改變趨勢相符合。經(jīng)過多次實(shí)驗(yàn)，確定初始化種群個(gè)體數(shù)量為2000，選擇父代數(shù)量為500，交叉概率為6%，變異概率為1%。當(dāng)采用這組參數(shù)時(shí)，實(shí)驗(yàn)?zāi)軌虻玫捷^為優(yōu)秀的結(jié)果，最終生成的發(fā)車時(shí)刻表符合約束條件且獲得較高的適應(yīng)度，按照該參數(shù)運(yùn)行結(jié)果如圖6-6所示。4.2遺傳算法實(shí)驗(yàn)結(jié)果分析根據(jù)標(biāo)準(zhǔn)遺傳算法求解公交排班問題，輸出每一代中具有最高適應(yīng)度的個(gè)體，再將每代的最高適應(yīng)度的個(gè)體按適應(yīng)度降序排列，選擇出經(jīng)過多代選擇交叉變異后具有最高適應(yīng)度的有效個(gè)體，并且將每代的最高適應(yīng)度的個(gè)體輸出繪制成圖表，得到每代最優(yōu)良個(gè)體適應(yīng)度較為發(fā)散，但計(jì)算得到的每一輪的最優(yōu)個(gè)體的適應(yīng)度均大于實(shí)際發(fā)車時(shí)刻表的適應(yīng)度，因此證明優(yōu)化的結(jié)果是合理可行的。經(jīng)過多次實(shí)驗(yàn)得到多組結(jié)果，每組實(shí)驗(yàn)可以得到每一代個(gè)體經(jīng)過交叉變異后所產(chǎn)生的具有最大適應(yīng)度的個(gè)體，再將每代最優(yōu)個(gè)體進(jìn)行比對，選擇具有最高適應(yīng)度的最優(yōu)個(gè)體作為比較對象，最后再比對各個(gè)實(shí)驗(yàn)所能產(chǎn)生最優(yōu)個(gè)體的適應(yīng)度，選出具有最高適應(yīng)度的最優(yōu)個(gè)體的實(shí)驗(yàn)最為實(shí)驗(yàn)結(jié)果分析對象進(jìn)行分析。將經(jīng)過交叉變異操作的代數(shù)作為橫坐標(biāo)，每代中產(chǎn)生的最優(yōu)個(gè)體的適應(yīng)度作為縱坐標(biāo)繪制成折線圖如下所示：圖4-6代數(shù)-每代最優(yōu)個(gè)體適應(yīng)度曲線圖由圖像可知，圖像整體波動(dòng)起伏較大，表示每代最優(yōu)個(gè)體的適應(yīng)度離散度較高，是由于在交叉以及變異過程可能將原有的優(yōu)良基因進(jìn)行交叉變異，產(chǎn)生適應(yīng)度較低的個(gè)體，也有可能交叉變異后產(chǎn)生適應(yīng)度更高的個(gè)體。遺傳算法允許適應(yīng)度較低的