【正文】 大學(xué)學(xué)報(bào)（自然科學(xué)版） ，2022。[10] 李晨暉，杜友福，張興旺，劉俊，遺傳算法 TSP 問題的實(shí)現(xiàn)及免疫優(yōu)化，電腦知識(shí)與技術(shù)（學(xué)術(shù)交流） ，2022。[8] 范文廣，遺傳算法研究和探討，河北工程大學(xué)學(xué)報(bào)，2022。另外，經(jīng)過改進(jìn)后的遺傳算法中的交叉運(yùn)算，雖然說是以單個(gè)的基因?yàn)閱挝贿M(jìn)行繼承的，然而，由于后面的基因的選取是靠前一個(gè)基因來決定的，所以雖然看似零碎，實(shí)際上在擴(kuò)展了種群的多樣性的同時(shí)，很好的實(shí)現(xiàn)了路徑的遺傳。綜合上面的數(shù)據(jù)，需要適當(dāng)調(diào)整遺傳算法中的幾個(gè)變異算子。 // 雜交mutate()。count_distances()。}}}系統(tǒng)的主要架構(gòu)是按照設(shè)計(jì)中的模式來實(shí)現(xiàn)的，先構(gòu)建好每個(gè)功能模塊的函數(shù)以及數(shù)據(jù)結(jié)構(gòu)，然后在主函數(shù)中循環(huán)調(diào)用這些函數(shù)。種群初始化。void keep_the_best()。void Xover(int,int)。int randval()。struct genotype newpopulation[POPSIZE+1]。 // 個(gè)體的適應(yīng)度double cdown。其中 X,Y 是指城市的具體橫縱坐標(biāo)，而 Distances 則是通過計(jì)算后的城市之間的距離，X 和 Y 的維數(shù) N_CITIES 是一個(gè)宏定義常量，表示城市的數(shù)量，也是基因的長(zhǎng)度，17下同。155. 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)因?yàn)樵O(shè)計(jì)上的需要，系統(tǒng)是用 C 語(yǔ)言實(shí)現(xiàn)的，沒有界面圖，只有 dos 的運(yùn)行界面，現(xiàn)將運(yùn)行結(jié)果展示如下：圖 51程序運(yùn)行結(jié)果圖在上面的運(yùn)行結(jié)果圖里面，尋找的是中國(guó) 31 個(gè)城市之間的最短路徑，現(xiàn)在已證實(shí)，這 31 個(gè)城市之間的最短路徑的路程是 15377，而本程序在運(yùn)行一次的情況下獲得最優(yōu)解是 15416，初始種群和末代種群，打印出來的都是每個(gè)個(gè)體的路徑總路程，在最后打印出來的一串?dāng)?shù)值是代表路徑的序號(hào)。具體想法是，首先從兩個(gè)親代中隨機(jī)選取一個(gè)基因作為一個(gè)子代的開始，也就是這個(gè)子代的第一個(gè)基因，然后從第二子代開始，每次都隨機(jī)抽取一個(gè)親代，從中來選擇基因，當(dāng)確定了從哪個(gè)親代中繼承基因后，然后從當(dāng)前子代取得現(xiàn)在已有基因片段13的最后一個(gè)基因 ci，拿到這個(gè)基因后找到要繼承的親代中該基因的位置 li，然后拿到該位置相鄰位置右邊的基因，拿到右邊的基因后，在子代基因中查看是否已經(jīng)存在該基因，如果存在，那么就取得親代 li 左邊的基因，然后同樣在子代中查看該基因是否已經(jīng)存在，如果同樣存在，那么重新隨機(jī)在該親代中獲取一個(gè)基因，接著在子代中查看此基因是否已經(jīng)存在，如果有，則重復(fù)，直至找到一個(gè)不存在的基因。在計(jì)算每個(gè)個(gè)體的適應(yīng)值的時(shí)候，先將所有的偽適應(yīng)值累加起來，得到一個(gè)總的偽適應(yīng)值，然后用每一個(gè)偽適應(yīng)值來除以這個(gè)總的偽適應(yīng)值，獲得結(jié)果就是最終的適應(yīng)值。為了解決這一大難題，最終想到了，求倒數(shù)的方法，計(jì)算簡(jiǎn)單，效果也很明顯。遺傳算子保留了傳統(tǒng)的遺傳算法中的設(shè)計(jì)方式，仍舊采用選取[0,1]之間的浮點(diǎn)數(shù)作為遺傳算子，然后來進(jìn)行比較判斷，根據(jù)是否滿足條件來判斷是否能夠做下一步操作。基本步驟和操作流程基本上沒有改變，只是改變一些流程的操作和操作方式，大體流程依舊遵照傳統(tǒng)的遺傳算法，只是在過程中添加了一個(gè)精英策略的思想。例，個(gè)體基因?yàn)?00010010101，先產(chǎn)生一個(gè)[0,1]之間的浮點(diǎn)數(shù)，判斷它與變異算子之間的關(guān)系，則繼續(xù)下一步操作，然后產(chǎn)生一個(gè)正整數(shù)，將字串中該位置的基因反向，如果產(chǎn)生的正整數(shù)是 5 則，上面的個(gè)體變異后得到的新個(gè)體為 00010110101。常用的交叉方式有單點(diǎn)交叉、兩點(diǎn)交叉和一致交叉。. 終止在傳統(tǒng)的遺傳算法中，評(píng)價(jià)完新產(chǎn)生的種群后，會(huì)來判斷新產(chǎn)生的種群是否符合終止條件，如果符合，那么就得到最優(yōu)解并結(jié)束遺傳過程；如果不符合，則繼續(xù)遺傳操作，直到尋找到符合條件的最優(yōu)解或是直到自然結(jié)束遺傳操作過程。在傳統(tǒng)的遺傳算法中兩個(gè)遺傳算子都是一個(gè)小于 1 的浮點(diǎn)數(shù)。Rebine P (t) by probability pc。遺傳算子：選擇后代、遺傳后代和變異操作的一個(gè)選擇參數(shù)。在演練過程中，模仿生物的進(jìn)化過程，有雙親結(jié)合產(chǎn)生下一代個(gè)體，為了能夠保證種群的多樣化和過早的收斂于某一個(gè)局部最優(yōu)解，有了變異操作。. 遺傳算法缺點(diǎn)首先，傳統(tǒng)的遺傳算法編碼和解碼比較復(fù)雜，因?yàn)閭鹘y(tǒng)的遺傳算法的染色體是用二進(jìn)制編制的，一個(gè)染色體就是一串 0 和 1 組成的位串或是字符串，在進(jìn)化前需要做復(fù)雜的編碼工作，而在得到最優(yōu)解后還要做復(fù)雜的解碼工作，比較繁瑣和復(fù)雜，在遺傳操作過程中也不易掌控，容易出錯(cuò)；其次，算法對(duì)初始種群的選擇有一定的依賴性。之所以說是從多點(diǎn)而不是從單點(diǎn)出發(fā)，那是因?yàn)檎麄€(gè)算法的開始是從一個(gè)初始種群開始搜索演練最優(yōu)解，是從多個(gè)點(diǎn)開始搜索進(jìn)化尋找，這樣的做的一個(gè)好處是避免局部尋找最優(yōu)解，從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。隨著計(jì)算機(jī)在生活、學(xué)習(xí)、工作中的分量越來越大，對(duì)于計(jì)算機(jī)的各項(xiàng)性能指標(biāo)也是要求越來越高，硬件上，追求更快、更安全、更穩(wěn)定；軟件上追求智能、安全、人性化、更美觀。本文也是基于旅行商問題來進(jìn)行研究。遺傳算法 GA( geic algorithm) 最早由美國(guó)密歇根大學(xué)的 John Holland 提出。解決旅行商問題的各種優(yōu)化算法都是通過犧牲解的精確性來?yè)Q取較少的耗時(shí)，其他一些啟發(fā)式的搜索算法則依賴于特定的問題域，缺乏通用性，相比較而言遺傳算法是一種通用性很好的全局搜索算法。路徑問題中一個(gè)經(jīng)典的問題是旅行商問題，也證實(shí)了旅行商問題是 NP 難題，雖然旅行商現(xiàn)在已經(jīng)擁有了各種解法，結(jié)果也很好，但仍是業(yè)界追捧的一大話題。計(jì)算機(jī)在日常的娛樂、生活也起著不可估量的作用。. 遺傳算法優(yōu)點(diǎn)不是從單個(gè)點(diǎn)，而是從多個(gè)點(diǎn)構(gòu)成的群體開始搜索。但是，傳統(tǒng)的遺傳算法同樣擁有缺陷。在初始化種群后，就要開始進(jìn)入遺傳演練階段，遺傳的第一步操作是對(duì)種群的每個(gè)個(gè)體計(jì)算適應(yīng)度，然后進(jìn)入遺傳演練。適應(yīng)度( fitness)：個(gè)體對(duì)環(huán)境的適應(yīng)程度，也是反映問題的目標(biāo)函數(shù)，是操作過程中的一個(gè)重要衡量標(biāo)準(zhǔn)。Select P (t) from P (t1)。選擇算子則是用于選擇當(dāng)代種群中的個(gè)體來繁殖下一代個(gè)體。旅行商問題中，評(píng)價(jià)函數(shù)一般都是計(jì)算出每一條路徑的程度之和，也用此路程總和來作為每個(gè)個(gè)體的適應(yīng)度的計(jì)算參數(shù)。交叉是在選中的用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同個(gè)體的相同位置的基因進(jìn)行交換，產(chǎn)生新的個(gè)體，交叉操作以較大的概率進(jìn)行。通常變異的概率較小，但它可以防止算法‘早熟’ ，即收斂于局部最優(yōu)解。104. 改進(jìn)后的遺傳算法本系統(tǒng)基于傳統(tǒng)的遺傳算法以及其它的人工智能算法，結(jié)合變異而成了改進(jìn)的遺傳算法。最主要的是，在交叉遺傳時(shí)的檢測(cè)，不存在復(fù)雜的轉(zhuǎn)換工作，只需檢查路徑中是否有相同的序號(hào)，以此來判斷路徑中是否有重復(fù)的城市。另外，本系統(tǒng)在計(jì)算個(gè)體的適應(yīng)度上有了較大的改進(jìn)，在傳統(tǒng)的遺傳算法中，適應(yīng)度越大代表該個(gè)體越優(yōu)秀，那么同理，在本系統(tǒng)中，也應(yīng)該是適應(yīng)度越大那么就越好，然而個(gè)體的適應(yīng)度是基于總路程來計(jì)算的，從理論上來講，路程應(yīng)該是越短，那么該個(gè)體就越優(yōu)秀，這與遺傳算法的適應(yīng)值得定義背道而馳。系統(tǒng)在評(píng)價(jià)每個(gè)個(gè)體時(shí)就算出了它們個(gè)體總路程的倒數(shù)，并做了適當(dāng)放大處理，然后存儲(chǔ)起來，并給它命名為偽適應(yīng)值。在傳統(tǒng)的遺傳算法，交叉操作都是基于單點(diǎn)或多點(diǎn)交叉運(yùn)算，本系統(tǒng)也是基于這種想法，只是具體實(shí)現(xiàn)上做了較大改變。在傳統(tǒng)的遺傳算法中，本應(yīng)該是在變異操作過后對(duì)種群的個(gè)體進(jìn)行評(píng)價(jià)，評(píng)價(jià)完后應(yīng)該來判斷是到達(dá)遺傳的代數(shù)，如果到達(dá)遺傳的代數(shù)在本系統(tǒng)里沒有設(shè)置終結(jié)遺傳操作的終結(jié)條件，因?yàn)樵诼窂綄ふ抑袥]有一個(gè)好的參考條件，路徑的搜尋沒有固定的最優(yōu)解，只有更優(yōu)解，所以，在此處是采用自然終結(jié)的方式來終結(jié)系統(tǒng)的遺傳操作，當(dāng)然，遺傳的代數(shù)需要人手動(dòng)來指定，當(dāng)遺傳的代數(shù)到達(dá)指定的代數(shù)時(shí)，本應(yīng)該是退出系統(tǒng)，但本系統(tǒng)在采用了精英策略，每代繁殖出來后會(huì)從中選取最優(yōu)秀的個(gè)體，與以前的最優(yōu)個(gè)體比較，并保留最優(yōu)秀的那個(gè)個(gè)體，確保算法最終得到的是整個(gè)遺傳過程的最優(yōu)解，以避免錯(cuò)過最優(yōu)解機(jī)會(huì)。double Distances[N_CITIES][N_CITIES]。double fitness。系統(tǒng)中，種群是用一個(gè)全局的 genotype 來表示的：struct genotype population[POPSIZE+1]。對(duì)產(chǎn)生的種群中的個(gè)體進(jìn)行優(yōu)化，只在初始化種群時(shí)被 initialize 函數(shù)調(diào)用一次。交叉函數(shù)，在選擇函數(shù)確定了親代種群后，交叉函數(shù)來決定親代之間的遺傳操作，并且將要做交叉操作的個(gè)體傳遞給負(fù)責(zé)實(shí)現(xiàn)交叉操作的 Xover函數(shù)。 輔助函數(shù)，用來從外部文件中讀取城市的坐標(biāo)。. 系統(tǒng)實(shí)現(xiàn)在系統(tǒng)實(shí)現(xiàn)方面，就只介紹改進(jìn)后的遺傳算法的優(yōu)秀之處。 mem++){if (population[mem].sum_distance population[POPSIZE].sum_distance){population[POPSIZE] = population[mem]。read_tsp_file()。 // 遺傳crossover()。優(yōu)化后的遺傳算法不僅在結(jié)果上可以得到幾乎最優(yōu)解，而且在搜索時(shí)間上也在傳統(tǒng)的遺傳算法的基礎(chǔ)上大大的縮減了。首先在編碼上的改進(jìn)，使得最終的個(gè)體在進(jìn)化過程中操作簡(jiǎn)單，也符合人類的邏輯思維；在交叉復(fù)制上的改善，在保持種群多樣化的同