1、在通訊網絡設計、X射線結晶學問題、VISI(超大規(guī)模集成電路)制造問題、渠道鋪設問題等問題中都涉及組合優(yōu)化問題的求解,且其中大部分問題是NP-難問題(傳統(tǒng)的優(yōu)化方法往往只適合于求解小規(guī)模的問題,對于大規(guī)模的問題,啟發(fā)式方法如遺傳算法,已被證明是一種比較有效的方法).近幾年來,應用遺傳算法求解組合優(yōu)化問題的近似解成為一個新的研究方向,如用遺傳算法求解旅行商問題(TSP)、最小生成樹問題(MST).首先,本文對不固定起點和終點的旅行商問題設

2、計了一個新的遺傳算法.這種算法將不固定起點和終點的旅行商問題化簡,根據化簡以后的問題,設計了一種新的編碼方法和解碼方法.針對編碼的特點,設計了一種新的直接產生可行后代的雜交算子和變異算子.為提高算法的收斂速度,結合了一個局部搜索算子改進雜交后得到的個體.并且證明了算法的全局收斂性,計算機仿真結果表明算法是有效的.其次,本文提出了一種求解度約束最小生成樹問題的遺傳算法.算法采用邊集表示法表示問題的解,用Di jkstra算法的某些思想產生