遺傳算法論文范文第1篇
摘要：家具生產線的運行效率，直接決定著家具的生產效率以及生產成本，為了提升家具生產效益，需要對其進行優化.基于此，本文將首先介紹家具生產線運行現狀，其次，進行家具生產線平衡分析，最后，分析遺傳算法基礎上家具生產線的優化措施，最終達到對家具生產線進行有效優化的目的.
關鍵詞：家具生產線;遺傳算法;優化設計
目前我國經濟發展的速度較快，企業在實際發展的過程中需要根據時代的發展不斷完善，只有這樣才能保證自身的經營發展質量.本文將以家具生產線為例，在遺傳算法的基礎上對家具生產線進行優化，提升家具生產線的運行質量以及運行成本，不斷提升家具生產企業的經營效益，促進我國經濟的發展.
1 家具生產線運行現狀
本次研究的家具生產線主要生產的家具為沙發，該沙發在實際生產的過程中，由左三位、右三位以及腳踏構成，在左三位上安裝兩個枕頭.整個沙發的生產過程共需要24道工序，在實際研究的過程中，針對每道工序進行時間測量，針對一項工序共測量6次，進而保證時間檢測的準確性，根據6次的測量結果計算平均值，將其作為實際工作時間[1].圖1為沙發組裝圖.
在實際沙發制作的過程中，可以將24道工序分為10部分進行，第一，取木架，第二，釘白紗布、裝彈簧、釘網以及安裝松緊帶.第三，噴澆水、貼三位棉、安裝腳踏步.第四，套粘布.第五，釘粘布.第六，釘腳、安裝五金架，第七，安裝頭枕、安裝外套，第八，放粘子、放靠包，第九，檢驗，第十，包裝.以上步驟為沙發制作的大致流程，在研究家具生產線優化的過程中，需要根據以上步驟作為主要對象，利用遺傳算法對其進行研究[2].
2 家具生產線平衡分析
通過分析家具生產線中各流程使用的時間發現，以上十個流程平均使用的時間分別為243s，526s，398s，375s，500s，410s，339s，140s，99s，270s.通過以上時間分析能夠看出，在實際家具生產中，第二階段所用的時間最長，是影響生產效率的主要影響因素，另外，各個工作流程中所用時間的差異性較大，最少用時為99s，與549s相差450s，這也是導致平均加工時間增加的主要因素之一.在計算家具生產線平衡率的過程中，需要用總時間/最大時間與總人數的乘積=5251s/（526x15）=66.55%，因此家具生產線平衡率為66.55%，則平衡損失率為1-66.55%=33.45%.通過以上計算能夠得出，在生產該家具的過程中，平衡損失率為33.45%，平衡損失率為20%，由于33.45%大于20%，因此該項家具生產線處于時間浪費超標的情況，整個家具生產線的效率較低，也就是說，根據這一生產時間，每生產一套沙發，浪費的時間為2639s，整體生產平衡的效果較差，因此需要對其進行優化[3].
在整個生產過程中，最嚴重的問題就是工作流程時間分配不均衡的問題，時間差異較大，整個家具生產線的生產效率無法提升，另外，這種情況還會導致工作流程之間的加工商品堆積或者供應不足，浪費生產空間以及生產時間，提升生產勞動成本的同時，降低經營利潤，最終對企業生產效益產生影響.因此在實際家具生產線優化的過程中，需要針對加工時間分配不均勻這一問題進行有效解決，提升整個家具生產線的生產力，減少時間浪費的情況，最終降低生產成本，提升經企業的經濟效益.
3 遺傳算法基礎上家具生產線的優化措施
3.1 家具生產線優化模型的建立
由于本次家具生產線優化主要針對的對象為時間和指定生產元素，因此需要根據生產的產量，計算相應的生產節拍，保證各個生產流程的獨立進行，其中作業元素只能與一個工作站相互對應.在分配工作站時間的過程中，必須滿足相應的約束條件，各個工作站的生產時間不能大于約束條件，在此基礎上確定工作站數量的最小值.工作站使用矩陣利用B來表示，B（J）=0/1，J=1，2，3…M.如果B=0，則說明該工作站上并不存在作業，當B=1時，則說明該工作站上存在一項工作，I表示工作作業元素的合集，J為工作站的合集.其中I=“1，2，fi，fN，J=”1，2，fj，fM，其中i為時間元素.如果約束條件的計算結果為1，則說明一個工作站智能對應一項作業，在分配作業的過程中，必須將約束條件作為前提條件，同時工作站的運行時間需要與生產節拍相等或者小于生產節拍.根據家具生產線的實際運行情況，可以采用遺傳算法數學模型對其進行計算[4].表1為相關參數在遺傳算法中的對應關系.
3.2 家具生產線優化算法設計
家具生產線優化過程中的算法設計主要包括以下內容;
第一，編碼，這一過程需要利用作業元素序列進行，將作業元素根據工作站的實際情況進行分配，并將其中對應的序號排列成染色體，其中各項作業元素與染色體的基因位置相互對應.編碼完成之后，染色體中的各項作業元素需要滿足優先級別的條件，編碼染色體的呈現形式1，2，3，4，5，6，8，9，12， 10，13，7，11，14，15，16，17，18，19，20，21，22，23，24.其中每個數字代表著一項作業元素，例如2對應著第二個作業項目元素，根據編碼的順序進行工作站排列.
第二，編碼翻譯，由于以上染色體中只能將作業元素的順序顯示出來，因此在翻譯編碼的過程中，需要將染色體分配到相應的工作站中，根據對應的生產節拍原則進行翻譯.其中作業時間用tt表示，M的初始值為0，翻譯過程包括以下步驟，第一，tt=tt+time（xi），若tt≤CT<tt+time（xi+1），則M=M+1，tt=0.若i=N-1，M=M+1，符合以上要求進行第二部分翻譯.：i=i+1.若i≤N-1，將其轉到第一步翻譯中，如果最終結果i=N，則完成全部翻譯.
第三，選擇算子，可以使用保存最優的方法進行選擇，在相應函數值的基礎上，除去種群中的劣質個體，保存優質的個體，在遺傳算法中，保留最優算法能夠將工作站數值中的最小M值代替M值中的最大個體[5].
第四，交叉算子，在此過程中需要利用交叉概率進行，利用Pc針對個體進行相互匹配，兩個兩個為一對，進而出現新生的個體，采用交叉算子的方式能夠將群體中的優質基因保存下來.例如，進行交叉算子相互匹配的個體分別為A1，A2，則得到的新個體為A1’，A2’.在此過程中需要在這兩個父代序列中選擇交叉點，在[1，N-1]的范圍中選擇，假如m=8，則二者之間的交叉點為如下所示.
3.3 家具生產線優化算法計算
在算法求解的過程中，需要根據遺傳算法理論進行，根據家具生產線的實際情況進行，采用MATLAB進行編程，程序中的生產節拍時間為418秒，s=100，進化代數為200，最優個體數為15，交叉概率為0.8，變異概率為0.06.在實際平衡的過程中，工作站從15個變為14個，最小的工作站數量為14個，節拍時間為410s，平衡率為91.5%，平滑系數ST=157.7.圖2為優化完成后個工作站工作對應的時間.
3.4 家具生產線優化效果對比
優化完成之后，家具生產線的運行效益得到了有效提升，在經濟方面，家具生產線優化提升效益為29.4%x14x3500x12=172930元，（效益提升數量x作業人數x人均月薪x每年工作月數）.由此可以看出，利用遺傳算法對家具生產線進行優化，取得了顯著的研究效果，無論在經濟效益還是在人工勞動成本中，都取得了非常明顯的提升，促進家具生產線能夠高效的運行，不斷提升企業的經濟效益，促進我國經濟的穩定發展[6].
綜上所述，隨著人們對家具生產線的關注程度逐漸提升，如何提升家具生產線的運行效率，成為有關人員關注的重點問題.本文通過研究遺傳算法基礎上家具生產線的優化措施發現，對其進行研究，能夠大大提升家具生產線的生產質量，促進今后遺傳算法在家具生產線優化中的發展.
參考文獻：
〔1〕蘇冬勝.家具模塊化設計的應用與發展[J].廣西輕工業，2008（11）：100-101.
〔2〕歐立華科技.安通為瑞典家具巨頭Kinnarps提供一站式板式家具生產線[J].林產工業，2017，44（05）：54.
〔3〕林時峰.河南襄城始建年產15萬m～3秸稈生態板及70萬套環保成品家具項目[J].林產工業，2016，41（04）：43.
〔4〕劉林.基于先進制造理念的板式家具生產線的規劃與設計[D].中南林業科技大學，2016.
〔5〕魏玲.基于EM-Plant的家具自動化生產線的仿真研究[J].哈爾濱理工大學學報，2015，15（02）：110-114.
〔6〕林海.家具模塊化設計方法實例分析[J].家具與室內裝飾，2005（09）：20-22.
遺傳算法論文范文第2篇
相控陣天線的波束快速捷變性能使其在通信、導航、雷達、探測等領域應用非常廣泛[1,2,3,4,5,6,7]。而隨著相控陣天線的波束形成算法研究的深入, 其應用領域也越來越廣泛, 對波束形成算法的要求也因具體化而有所區別[8,9,10,11,12,13]。相控陣天線的波束形成能力直接影響了系統的快速捕獲跟蹤性能。相控陣的波束形成算法需要滿足系統對天線增益、波束寬度、波束指向精度、旁瓣要求等指標實現滿足。尤其是毫米波頻段相控陣天線的陣列間距非常小, 天線間的互耦效應對波束形成能力也帶來了非常大的影響。
對衛星導航領域相控陣天線的波束形成算法進行了分析與設計。導航相控陣天線對波束形成算法的主要需求是在各陣元均勻幅度加權的情況下實現良好的旁瓣抑制和窄波束形成[8]。
1 基于遺傳算法的波束形成算法
導航領域的相控陣天線一般需要滿足無柵瓣掃描條件, 對于平面陣列, 陣元間距需滿足如下公式:
一般而言, 陣列增益隨著波束指向偏離陣列法線而下降。以投影面積分析, 掃描增益與掃描角θ0 (波束指向與陣列法向的夾角) 的關系可以近似為:
在實際工程中, 由于波束指向偏離法向后, 端口阻抗失配以及陣元耦合影響加劇, 實際的掃描增益可以表示為:
式中, α的典型值為1~1.5之間。如果陣列同時產生M個波束, 假定每個波束具有相同的波束寬度, 則其公式可以寫為:
在以下的討論中, 簡單起見, 波束形成算法以邊長為2N-1 (指包含2N-1個振元) , 振元間距為d=λ/2的方形柵格陣列進行說明, 如圖1所示。
當陣列天線產生的波束模式主瓣指向空間方位 (θ0, φ0) 時, 一般有:
式中, w'mn為實數, 當w'mn滿足象限對稱分布 (即w'mn=w' (-m) n, w'mn=w'm (-n) ) 時, 容易得到陣列天線產生的波束模式為:
式中:
由以上公式可知, 加權系數wmn即為波束形成算法需求求解的對象。這里應用遺傳算法[14]對加權系數wmn進行優化運算, 其算法運行流程如下:
①確定主瓣指向空間方位 (θ0, φ0) ;初始化加權系數wmn, 概率設定為繼承概率p150%, 變異概率p210%, 互耦系數0.9;
②計算當前加權系數下的陣列天線波束形成F (θ, φ, W) ;
③判斷當前狀態是否收斂;
④若收斂, 算法結束;若未收斂, 按以下流程操作得到新的加權系數, 然后重新執行②操作:
Ⅰ繼承:當前加權系數按概率p1繼承到新的加權系數;
Ⅱ交叉:未繼承當前加權系數的元素按最陡下降法進行篩選;
Ⅲ變異:繼承與交叉操作過程中, 按概率p2進行變異操作, 變異操作方法為在優化空間內隨機進行篩選。
該波束形成算法在24*24陣元總數, 陣元間距7.2 mm, 工作頻率25 GHz的相控陣天線布局上進行了仿真計算。法向計算結果如圖2所示。旁瓣抑制15 d B, 半波束寬度約4°。
2 幅相誤差對波束形成的影響
陣列天線通常由小天線按一定的幾何排列在一起, 組成一個增益較高的天線陣列。為改變天線陣列方向圖的波束指向, 可通過改變陣列天線中各個天線單元的信號相位及幅度關系, 這樣就實現了簡單的相控陣天線。相控陣波束形成所需的幅度加權和移相可以在射頻部分通過微波網絡 (衰減器和移相器) 來實現。
一個波束形成系統要包括以下基本單元:天線陣、方向圖形成網絡和波束形成處理器 (方向圖控制器) , 原理框圖如圖3所示。其中波束形成處理器是用來調整方向圖形成網絡中的可變加權系數的。
波束合成過程中的幅相誤差是影響相控陣波束形成準確性的重要因素。相控陣權重的幅相誤差主要由2部分組成:1相控陣通道之間的幅相不一致性;2器件移相、衰減步進精度。
通道之間的幅相不一致性w1mn是相控陣天線的設計誤差。為了減小該因素對波束形成的影響, 可通過有線標定各通道之間的幅度、相位差異, 并在波束形成算法中, 作為初始加權系數的修正量進行校正。
波束形成算法給出的權重最終是靠移相器和衰減器來實現的, 而物理器件的移相、衰減存在調整范圍、步進以及步進精度等設計精度。通過在算法優化過程中, 考慮物理器件的實現能力, 對算法做出如下調整:
①繼承:當前加權系數按概率p1繼承到新的加權系數;②交叉:未繼承當前加權系數的元素按最陡下降法進行篩選, 最陡下降路徑步進按移相器、衰減器步進選擇;③變異:繼承與交叉操作過程中, 按概率p2進行變異操作, 變異操作方法為在優化空間內隨機進行篩選;④調整:根據調整范圍、步進精度對加權系數進行調整。
更新后的優化算法的計算結果如圖4所示, 波束指向為電掃20°?？紤]衰減精度0.5 d B, 移相精度5°下的波束形成算法優化結果與理想結果之間的差異如圖5所示。
結果顯示450個波束形成結果中, 最大的增益差別0.1 d B。
3 結束語
遺傳算法論文范文第3篇
遺傳算法 (Genetic Algorithm, 縮寫為GA) , 是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型, 是一種通過模擬自然進化過程搜索最優解的方法。它是由美國的J.Holland教授1975年首先提出來的, 近年來, 由于遺傳算法求解復雜優化問題的巨大潛力和工程等領域的成功應用, 受到了國內外學者的廣發關注。
2 遺傳算法的發展
早在上個世紀40年代, 就有學者開始研究如何利用計算機進行生物模擬的技術, 他們從生物學的角度進行了生物的進化過程模擬、遺傳過程模擬等研究工作。進入60年代后, 美國密執安大學的Holland教授及其學生們受到這種模擬技術的啟發, 創造出了一種基于生物遺傳和進化機制的適合于復雜系統優化計算的自適應概率優化技術---遺傳算法。
進入90年代, 遺傳算法迎來了興盛發展時期, 無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳算法的應用研究顯得格外活躍, 不但它的應用領域擴大, 而且利用遺傳算法進行優化和規則學習的能力也顯著提高, 同時產業應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發展, 這些無疑都給遺傳算法增添了新的活力。遺傳算法的應用研究已從初期的組合優化求解擴展到了許多更新、更工程化的應用方面。
3 遺傳算法的特點
GA是一種利用自然選擇和進化思想在高維空間中尋優的方法, 它不一定能尋得最優點, 但是它可以找到更優點。因此GA可能會暫時停留在某些非最優點上, 直到變異發生使它躍居到另一個更優點上。GA尋優過程的一個重要特點是它始終保持整個種群的進化, 這樣即使某個體在某時刻喪失了有用的特征, 這種特征也會被其他個體所保留并延續發展下去。由于GA僅需知道目標函數的信息, 而不需要其連續可微等要求, 因而具有廣泛的適應性。同時它又是一種采用啟發性知識的智能搜索算法, 所以往往能在搜索空間高度復雜的問題上取得比其他算法更好的效果。
盡管如此, 遺傳算法也有不足:一是容易過早收斂, 這樣就會使其它個體中的有效基因不能得到有效復制, 最終丟失;二是在進化后期染色體之間的差別極小, 整個種群進化停滯不前, 搜索效率較低, 這樣就會導致搜索到的結果不是全局最優解。
4 遺傳算法的發展動向
GA在應用方面的豐碩成果, 使人們對它的發展前景充滿信心。其主要應用領域在于函數優化, 機器人學, 控制, 設計、組合優化、圖象處理、信號處理、人工生命等領域。
另外遺傳算法的研究出現了幾個引人注目的新動向:
4.1 基于遺傳算法的機器學習。
這一新的研究方向把遺傳算法從歷史離散的搜索空間的優化搜索算法擴展到具有獨特的規則生成功能的嶄新的機器學習算法。這一新的學習機制對于解決人工智能中知識獲取和知識優化精煉的瓶頸難題帶來了希望。
4.2 遺傳算法與其他計算智能方法的相互滲透和結合。
遺傳算法正日益和神經網絡、模糊推理以及混沌理論等其他智能計算方法相互滲透和結合, 必能達到取長補短的作用。近年來在這方面已經取得不少研究成果, 并形成了“計算智能”的研究領域, 這對開拓2 1世紀中新的智能計算技術將具有重要的意義。
4.3 并行處理的遺傳算法。
并行處理的遺傳算法的研究不僅是遺傳算法本身的發展, 而且對于新一代智能計算機體系結構的研究都是十分重要的。GA在操作上具有高度的并行性, 許多研究人員都正在探索在并行機上高效執行GA的策略。近幾年也發表了不少這方面的論文, 研究表明, 只要通過保持多個群體和恰當地控制群體間的相互作用來模擬并執行過程, 即使不使用并行計算機, 我們也能提高算法的執行效率。
4.4 遺傳算法與人工生命的滲透。
人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統特有行為的人造系統, 人工生命與遺傳算法有著密切的關系, 基于遺傳算法的進化模型是研究人工生命現象的重要理論基礎。雖然人工生命的研究尚處于啟蒙階段, 但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力, 并且必將得到更為深入的應用和發展。
4.5 遺傳算法與進化規則及進化策略的結合。
遺傳算法、進化規則及進化策略是演化計算的三個主要分支, 這三種典型的進化算法都以自然界中生物的進化過程為自適應全局優化搜索過程的借鑒對象, 所以三者之間有較大的相似性;另一方面, 這三種算法又是從不完全相同的角度出發來模擬生物的進化過程, 分別是依據不同的生物進化背景、不同的生物進化機制而開發出來的, 所以三者之間也有一些差異。隨著各種進化計算方法之間相互交流深入, 以及對各種進化算法機理研究的進展, 要嚴格地區分它們既不可能, 也沒有必要。在進化計算領域內更重要的工作是生物進化機制, 構造性能更加優良、適應面更加廣泛的進化算法。
5 結束語
遺傳算法的未來是非常的美好的, 只要我們對它們進行細致的分析, 對它的缺點加以改造, 優點進行繼承, 把它應用到我們的生產當中去, 這樣在生產當中還可以對它的缺點進行完善。
摘要：近年來遺傳算法越來越廣泛地受到世界各國學者的關注, 本文簡述了遺傳算法的發展、特點及其應用。
關鍵詞：遺傳,搜索,遺傳算法
參考文獻
[1]趙振勇等.遺傳算法改進策略的研究[J].計算機應用, 2006, 26:189-191.
遺傳算法論文范文第4篇
該算法由Michigan大學教授Holland及其學生于1975年創建。眾多學者一直致力于推動遺傳算法的發展, 就傳統遺傳算法的關鍵技術如編碼方式、控制參數的確定、選擇方式和交叉機理等進行了深入的探究, 引入了動態策略和自適應策略以改善遺傳算法的性能, 提出了各種變形的遺傳算法, 例如混合遺傳算法, 并行遺傳算法, 合作演化算法, 混亂遺傳算法等。經過近30余年的努力, 遺傳算法不論是在應用上、算法設計上, 還是在基礎理論上, 均取得了長足的發展, 已成為信息科學、計算機科學、運籌學、經濟管理、交通運輸、工業設計和應用數學等諸多學科所共同關注的熱點研究領域, 解決了許多問題。
本文在對遺傳算法一定研究的基礎上敘述了該算法的基本原理、算法流程, 并且概述在算法設計中的常見問題, 同時對遺傳算法當今的應用進行總結。
1 遺傳算法的描述
1.1 GA基本原理
遺傳算法是建立在自然選擇和群體遺傳學機理基礎上的隨機迭代和進化, 是一種啟發式算法, 具有很強的全局優化搜索能力。它采用某種編碼方式將解空間映射到編碼空間, 每個編碼對應問題的一個解, 稱為個體或染色體, 再隨機確定初始的一個群體, 稱為初始種群。在后續迭代中, 按照適者生存原理, 挑選適應度大的個體, 并借助各種遺傳算子對個體進行交叉和變異, 生成下一代種群, 該種群比前代更適應環境, 如此進化下去直到滿足某種優化準則。此時末代的個體, 經過解碼, 作為問題的近似最優解。
1.2 算法流程
Ste p1:對解空間進行編碼;
Ste p2:隨機產生包含n個個體的初始群體;
Ste p3:適應度評估檢測個體適應度;
Ste p4:w hile<為滿足迭代終止條件>;
Ste p5:利用選擇算子選擇出若干個體進入交配池;
Ste p6:隨機選擇交配池中的兩個個體, 按照交叉概率進行交叉操作;
Ste p7:變異算子通過按變異概率隨機反轉某些 (個) 基因位;
Ste p8:適應度評估檢測個體適應度;
Ste p9:e nd
1.3 GA設計
1.3.1 編碼問題 (e ncoding)
編碼是遺傳算法要解決的首要問題, 通過編碼從而將問題空間映射成解空間, 并直接影響遺傳算子的作用。問題編碼一般應滿足完備性、健全性和非冗余性三個原則。Holland的編碼方法是二進制編碼, 但對于許多遺傳算法的應用, 特別是在工業工程上的應用, 這種簡單的編碼方法很難直接描述問題的性質, 因此, 近十年來, 人們又提出了其他的編碼方法, 主要有一維染色體編碼、動態編碼、多維實數編碼等。
1.3.2 適應度函數 (e valuation)
適應度函數用于評價個體適應環境的能力, 是選擇操作的依據, 它的好壞能直接影響遺傳算法的性能。一般來說適應度函數時由目標函數變換而來的, 對適應度函數的唯一要求是結果為非負值, 并且任何情況下總是希望越大越好。常用的適應度函數尺度變換有:線性變換、冪函數變換、指數變換。
1.3.3 遺傳算子
1) 選擇算子 (s e le ction) :選擇即從當前群體中選擇適應值高的個體以生成交配池的過程。
2) 交叉算子 (cros s ove r) :交叉指把兩個父代個體的部分結構加以替換重組而生成新個體的操作, 交叉操作的作用是組合出新的個體, 在串空間進行有效搜索, 同時降低對有效模式的破壞概率, 是決定算法收斂性能的關鍵。
3) 變異算子 (m utation) :變異即對群體中個體串的某些基因值作變動。通過變異使遺傳算法具有局部的隨機搜索能力, 同時保持群體的多樣性, 在克服早熟方面起著重要作用。
1.3.4 算法參數選擇
在遺傳算法的運行過程中存在著對其性能產生重大影響的一組參數。通過控制這組參數使GA以最佳的搜索軌跡達到最優解。主要的參數包括染色體位串長度L、群體規模n、交叉概率以及變異概率。
1.4 算法改進
雖然遺傳算法有很強的全局搜索能力, 但局部搜索能力較差, 主要原因是遺傳算法的交叉操作容易破壞當前模式, 使得小范圍的精確搜索很困難, 鑒于此, 于是提出了與啟發式搜索技術相結合的混合遺傳算法。實驗證明這種將全局搜索能力強的遺傳算法與局部搜索能力強的傳統啟發式搜索方法相結合的混合遺傳算法能產生很好的優化效果。
遺傳算法的另一個缺點是進化時間長, 進化過程中產生大量數據, 計算大, 時間長。為了解決這個問題, 我們利用遺傳算法本身具有的并行性, 提出了并行遺傳算法, 從而加快進化速度。
2 遺傳算法的應用
無論是算法設計還是理論分析, 最終都得歸結于實際應用。各形式的算法設計是否合理有效, 評價的最終標準只能是解決問題時表現出來的實際效果。遺傳算法的全局搜索策略和優化搜索方法在計算時不依賴于梯度信息或其它輔助知識, 而只需要影響搜索方向的目標函數和相應的適應度函數, 因而遺傳算法提供了一種求解復雜系統問題的通用框架, 它不依賴于問題的具體領域, 對問題的種類有很強的魯棒性。因而如今廣泛應用于函數優化、機器學習、作業調度問題、圖像處理、數據挖掘等眾多科學領域, 為這些領域的發展提供了新的方法。
3 結論
遺傳算法是一種基于概率意義隨機迭代進化、具有廣泛適用性的全局優化搜索方法。目前遺傳算法在基礎理論、算法設計上取得了長足的發展, 但其數學基礎比較薄弱, 算法本身還有待改進。遺傳算法是一個十分活躍的研究領域, 它的研究正從理論的深度、技術的多樣化以及應用廣度不斷探索朝著計算機擁有甚至超過人類智能的方向發展。
摘要：遺傳算法是一種在群體的逐代遺傳中, 搜索出全局最優解的搜索優化算法。近年來由于遺傳算法在解決復雜優化問題中顯現出巨大優勢, 因此受到國內外學者的廣泛關注。本文介紹了遺傳算法的簡單原理、設計方法, 并概述了它的技術和應用領域。
關鍵詞：遺傳算法,優化,搜索
參考文獻
[1]張文修, 梁怡.遺傳算法的數學基礎[M].西安:西安交通大學出版社, 2000.
遺傳算法論文范文第5篇
關鍵詞：大規模文本分類,特征提取,直觀無協方差增量主元分析,獨立成分分析
隨著網絡和信息技術的快速發展,大規模的文本處理成為一個挑戰。文本分類[1]是處理和組織大量文本數據的實用技術,分類系統研究的主要目標是提高分類的效率和效果。
向量空間模型(VSM)[2]是文本表示的主要方法,在該模型中,每篇文檔都被表示成如下形式的向量:di=(wi1,wi2,wi3,…,wi N),其中wij表示特征詞tj(1≤j≤N)在文檔di中的權重。把di作為D的第i行,就可以將一個文檔集表示成一個特征-文本矩陣D=(dij)M×N,dij表示特征詞tj在文本di中的權重。由于中文詞匯較多,且一篇文檔只出現少量的特征詞,所以D是一個高維稀疏矩陣。
高維的特征空間對分類算法帶來極高的計算復雜度和空間復雜度,且影響算法的可擴展性,若對特征空間進行有效的降維,可以提高文本分類的效率和效果。
特征選擇(Feature Selection)和特征提取(Feature Extraction)是特征空間降維的主要方法[3,4]。特征選擇方法不能挖掘出文本深層次的含義,且其特征獨立性假設在實際中很難滿足?；诰仃嚪纸獾奶卣魈崛∷惴?如主成分分析(PCA)[5]、潛在語義分析(LSA)[6]等,對存儲要求較高,不能處理高維的特征空間。大規模文本分類面對的是龐大的文本和類別數量,訓練集的特征空間具有很大的維數,這時傳統的特征提取方法就無法處理。
增量主元分析(CCIPCA)和獨立成分分析(ICA)是將原始數據從高維空間映射到低維空間的非線性降維方法[7]。本文使用這兩種方法實現大規模的文本數據降維,給出了分類對比實驗,并對其進行了比較分析。
1 基于迭代的特征提取方法
語料集中的每一個文檔對應1個列向量,假設整個語料集對應的向量序列為u'(n),n=1,2,…,第n篇文檔輸入時均值為,它的協方差矩陣為:
其中u(i)=u'(i)-m(n),A(n)的第i個特征值和特征向量的計算公式為:
其中xi(n)為第n個文檔向量輸入時待求的第i個特征向量,λi為對應的特征值。
傳統的PCA方法基于奇異值分解,直接計算樣本協方差矩陣的特征值和特征向量,將特征值進行排序,選取若干個最大的特征值對應的特征向量(主元)作為一組基來表示原始數據。
1.1 增量主元分析方法
CCIPCA對數據進行預處理,能夠對依次輸入的樣本增量計算其主元,通過迭代的方法逐步收斂得到待求的特征向量。再將原始數據從高維空間映射到低維空間,達到降維的目的。CCIPCA迭代公式為:
CCIPCA算法不用計算樣本協方差矩陣,所需計算空間小,能處理一般的基于矩陣分解的特征提取算法無法解決的大規模高維問題。通過迭代提取K個主成分,再將原始數據從高維空間映射到低維空間,達到降維的目的。
1.2 獨立成分分析
ICA是一種用于信號處理和數據分析的特征提取方法。ICA的基本含義是將多道觀測信號按照統計獨立的原則通過優化算法分解為若干個獨立成分。
Fast ICA算法無需選擇迭代步長,收斂迅速,Fast ICA算法步驟如下:
步驟1:數據預處理
1)中心化,即X=X-E{X},使訓練樣本均值為0。
2)白化,即,其中E是E{XXT}的特征向量矩陣,D是特征值的對角矩陣;
步驟2:任意選取up(0),要求‖up(0)‖2=1
步驟3:迭代
其中f和f'分別是函數F的一階、二階導數,函數F可以取:
步驟4:正交化
步驟5:歸一化
步驟6:若未收斂,回到步驟3。
2 分類實驗
文本分類器是文本分類系統的核心,常用的文本分類器有Na觙ve Bayes[8]、KNN[9]、SVM[10]等?；诮y計學習理論的SVM相比其他分類器具有良好的泛化能力,SMO算法提高了SVM的訓練速度,因此本文實驗中的文本分類器采用臺灣大學計算機科學與信息工程系Chang Chih-Chun和Lin Chih-Jen的LIBSVM軟件[11]。
對于系統的性能評價,采用F1測試值(Micro-F1)和宏平均F1(Macro-F1)這兩個評價指標。
本文實驗中采用的語料集來源于中文文本分類語料庫-Tan Corp V1.0,該語料集包括12個類別,14150篇文檔,72641個特征詞[8]。
為了減小訓練集中類別分布不均衡對分類結果的影響,從12類中各取150篇文檔,共1800篇文檔做為實驗語料,按7:3的比例分為訓練集和測試集,分類結果宏平均F1=47.10%。
采用CCIPCA和ICA算法對特征空間降維,將文本集映射到低維的特征空間后,訓練集和測試集分別降為1260×m、540×m,m為降維空間的特征數。其分類效果如圖1所示。
從圖1可以得到如下結論:
1)分類效果的比較:CCIPCA和ICA兩種特征提取方法對分類器整體性能指標(宏平均F1)有很大程度的提高。
2)降維的尺度:隨著選取的主元數或獨立成分數的增加,分類器效果指標(宏平均F1)逐步提高并接近平穩,但若個數過大,性能反而出現緩慢降低。如何確定合理的降維尺度來達到最佳的分類效果,是一個值得研究的問題。
3)兩種降維方法的比較:對于宏平均F1值,ICA比CCIPCA平均提高了約18.2%;在CCIP-CA方法中,當m=10時,分類效果最好,宏平均F1=73.12%;在ICA方法中,當m=8時,分類效果最好,宏平均F1=92.05%,比CCIPCA方法提高了18.93%,此時,F1測試值的比較如表1所示。
從表1可以看到經CCIPCA和ICA兩種方法降維后的分類結果與原始數據的分類結果相比,對類別的F1測試值有較大提升。
對相同的數據集進行降維處理,CCIPCA和ICA兩種方法顯示出各自的優勢和不足:
1)在效率上,CCIPCA要優于ICA,因為ICA的預處理階段就需要很大的運算量;
2)在效果上,ICA要優于CCIPCA,這是由于CCIPCA方法提取的特征向量是彼此正交的,而ICA提取的特征向量是相互獨立但不一定正交的,獨立而非正交的基向量表示高維數據更符合實際情況。
在上面實驗的基礎上,采用獨立成分分析與信息增益[4]組合的方法對特征空間進行降維,分類效果如圖2所示。
從圖2可以看到,獨立成分分析與信息增益的組合降維方法比單獨采用ICA降維的分類效果還有所下降。
3 結束語