package?liwu29;
/**
?*?
?*?@author?liwu
?*?遺傳算法解決TSP旅行商問題
?*/
import?java.io.BufferedReader;??
import?java.io.FileInputStream;??
import?java.io.IOException;??
import?java.io.InputStreamReader;??
import?java.util.Random;??

public?class?GA?{

	private?int?scale;//?種群規模??
????private?int?cityNum;?//?城市數量，染色體長度??
????private?int?MAX_GEN;?//?運行代數??
????private?int[][]?distance;?//?距離矩陣??
????private?int?bestT;//?最佳出現代數??
????private?int?bestLength;?//?最佳長度??
????private?int[]?bestTour;?//?最佳路徑??
??
????//?初始種群，父代種群，行數表示種群規模，一行代表一個個體，即染色體，列表示染色體基因片段??
????private?int[][]?oldPopulation;??
????private?int[][]?newPopulation;//?新的種群，子代種群??
????private?int[]?fitness;//?種群適應度，表示種群中各個個體的適應度??
??
????private?float[]?Pi;//?種群中各個個體的累計概率??
????private?float?Pc;//?交叉概率??
????private?float?Pm;//?變異概率??
????private?int?t;//?當前代數??
??
????private?Random?random;??
??
????public?GA（）?{??
??
????}??
??
????/**?
?????*?constructor?of?GA?
?????*??
?????*?@param?s?
?????*????????????種群規模?
?????*?@param?n?
?????*????????????城市數量?
?????*?@param?g?
?????*????????????運行代數?
?????*?@param?c?
?????*????????????交叉率?
?????*?@param?m?
?????*????????????變異率?
?????*??
?????**/??
????public?GA（int?s?int?n?int?g?float?c?float?m）?{??
????????scale?=?s;??
????????cityNum?=?n;??
????????MAX_GEN?=?g;??
????????Pc?=?c;??
????????Pm?=?m;??
????}??
??
????//?給編譯器一條指令，告訴它對被批注的代碼元素內部的某些警告保持靜默??
????@SuppressWarnings（“resource“）??
????/**?
?????*?初始化GA算法類?
?????*?@param?filename?數據文件名，該文件存儲所有城市節點坐標數據?
?????*?@throws?IOException?
?????*/??
????public?void?init（String?filename）?throws?IOException?{??
????????//?讀取數據??
????????int[]?x;??
????????int[]?y;??
????????String?strbuff;??
????????BufferedReader?data?=?new?BufferedReader（new?InputStreamReader（??
????????????????new?FileInputStream（filename）））;??
????????distance?=?new?int[cityNum][cityNum];??
????????x?=?new?int[cityNum];??
????????y?=?new?int[cityNum];??
????????for?（int?i?=?0;?i?????????????//?讀取一行數據，數據格式1?6734?1453??
????????????strbuff?=?data.readLine（）;??
????????????//?字符分割??
????????????String[]?strcol?=?strbuff.split（“?“）;??
????????????x[i]?=?Integer.valueOf（strcol[1]）;//?x坐標??
????????????y[i]?=?Integer.valueOf（strcol[2]）;//?y坐標??
????????}??
????????//?計算距離矩陣??
????????//?，針對具體問題，距離計算方法也不一樣，此處用的是att48作為案例，它有48個城市，距離計算方法為偽歐氏距離，最優值為10628??
????????for?（int?i?=?0;?i?????????????distance[i][i]?=?0;?//?對角線為0??
????????????for?（int?j?=?i?+?1;?j?????????????????double?rij?=?Math??
????????????????????????.sqrt（（（x[i]?-?x[j]）?*?（x[i]?-?x[j]）?+?（y[i]?-?y[j]）??
????????????????????????????????*?（y[i]?-?y[j]））?/?10.0）;??
????????????????//?四舍五入，取整??
????????????????int?tij?=?（int）?Math.round（rij）;??
????????????????if?（tij?????????????????????distance[i][j]?=?tij?+?1;??
????????????????????distance[j][i]?=?distance[i][j];??
????????????????}?else?{??
?????????????

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????396??2018-09-12?19:37??liwu29\.classpath

?????文件????????382??2018-09-12?19:37??liwu29\.project

?????文件????????642??2018-09-12?19:37??liwu29\.settings\org.eclipse.jdt.core.prefs

?????文件???????8744??2018-09-16?13:55??liwu29\bin\liwu29\GA.class

?????文件???????3357??2018-09-16?13:56??liwu29\bin\liwu29\Panel.class

?????文件??????18868??2018-09-16?13:55??liwu29\src\liwu29\GA.java

?????文件???????2400??2018-09-16?13:56??liwu29\src\liwu29\Panel.java

?????目錄??????????0??2018-09-16?13:53??liwu29\bin\liwu29

?????目錄??????????0??2018-09-12?20:16??liwu29\src\liwu29

?????目錄??????????0??2018-09-12?19:37??liwu29\.settings

?????目錄??????????0??2018-09-16?13:53??liwu29\bin

?????目錄??????????0??2018-09-12?20:08??liwu29\src

?????目錄??????????0??2018-09-12?19:37??liwu29

-----------?---------??----------?-----??----

????????????????34789????????????????????13