package?text;


import?java.util.ArrayList;
import?java.util.List;

/**
?*?遺傳算法
?*?
?*?@author?陳成
?*
?*/
public?class?GeneticAlgorithm?{

	/**
	?*?種群大小
	?*/
	private?int?pop_size?=?10000;//?種群大小
	/**
	?*?種群
	?*/
	private?Route[][]?pop;//?種群
	/**
	?*?交叉概率
	?*/
	private?double?cross_rate?=?0.5;//?交叉概率
	/**
	?*?突變概率
	?*/
	private?double?mutation_rate?=?0.2;//?突變概率

	/**
	?*?DNA長度
	?*/
	private?int?DNA_length;//?DNA長度
	/**
	?*?基因庫
	?*/
	private?Route[]?Gene;

	/**
	?*?構造器
	?*?
	?*?@param?city_xy
	?*?@param?cityName
	?*/
	public?GeneticAlgorithm（int[][]?city_xy?String[]?cityName）?{
		setGene（city_xy?cityName）;
		setEarliest_pop（city_xy）;
		DNA_length?=?cityName.length?-?1;
	}

	/**
	?*?設置基因庫
	?*/
	private?void?setGene（int[][]?city_xy?String[]?cityName）?{
		/**
		?*?城市數量
		?*/
		int?len?=?city_xy.length;

		Gene?=?new?Route[len?*?（len?-?1）];

		int?k?=?0;
		for?（int?i?=?0;?i?			for?（int?j?=?0;?j?				if?（i?!=?j）?{
					Gene[k]?=?new?Route（）;
					Gene[k].setStartingCity（cityName[i]）;
					Gene[k].setTargetCity（cityName[j]）;
					Gene[k].setDistance（Math.sqrt（Math.pow（absolute_value（city_xy[i][0]?-?city_xy[j][0]）?2）
							+?Math.pow（absolute_value（city_xy[i][1]?-?city_xy[j][1]）?2）））;
					k++;
				}
			}
		}
	}

	/**
	?*?絕對值
	?*?
	?*?@param?num
	?*?@return
	?*/
	private?int?absolute_value（int?num）?{

		if?（num?>=?0）?{
			return?num;
		}?else?{
			return?-num;
		}

	}

	/**
	?*?設置初代種群
	?*/
	private?void?setEarliest_pop（int[][]?city_xy）?{
		int?gene_num?=?Gene.length;
		pop?=?new?Route[pop_size][city_xy.length?-?1];

		for?（int?i?=?0;?i?			for?（int?j?=?0;?j?				pop[i][j]?=?Gene[（int）?（Math.random（）?*?gene_num）];
			}
		}
	}

	/**
	?*?得到適應性
	?*?
	?*?@return
	?*/
	private?double?get_fitness（Route[]?dna）?{

		double?fitness?=?0;

		for?（int?i?=?0;?i?			fitness?+=?dna[i].getDistance（）;
		}

		for?（int?i?=?0;?i?			if?（dna[i].getTargetCity（）.equals（dna[i?+?1].getStartingCity（）））?{
				fitness?-=?50;
			}
		}

		for?（int?i?=?0;?i?			for?（int?j?=?i?+?1;?j?				if?（（dna[i].getStartingCity（）.equals（dna[j].getStartingCity（））
						&&?dna[i].getTargetCity（）.equals（dna[j].getTargetCity（）））
						||?（dna[i].getStartingCity（）.equals（dna[j].getTargetCity（））
								&&?dna[i].getTargetCity（）.equals（dna[j].getStartingCity（））））?{
					fitness?+=?100;
				}
			}
		}

		if?（dna[0].getTargetCity（）.equals（dna[1].getStartingCity（））
				&&?dna[1].getTargetCity（）.equals（dna[2].getStartingCity（））
				&&?dna[2].getTargetCity（）.equals（dna[3].getStartingCity（））
				&&?dna[3].getTargetCity（）.equals（dna[4].getStartingCity（））
				&&?dna[4].getTargetCity（）.equals（dna[5].getStartingCity（））
				&&?dna[5].getTargetCity（）.equals（dna[6].getStartingCity（））
				&&?dna[6].getTargetCity（

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件?????????232??2018-04-15?11:25??遺傳算法—最短路徑問題\.classpath
?????文件?????????409??2018-04-15?11:25??遺傳算法—最短路徑問題\.project
?????目錄???????????0??2018-04-30?11:01??遺傳算法—最短路徑問題\bin\
?????目錄???????????0??2018-04-30?11:01??遺傳算法—最短路徑問題\bin\text\
?????文件????????4584??2018-04-23?10:13??遺傳算法—最短路徑問題\bin\text\GeneticAlgorithm.class
?????文件?????????476??2018-04-15?11:36??遺傳算法—最短路徑問題\bin\text\MyMain.class
?????文件????????1101??2018-04-23?09:28??遺傳算法—最短路徑問題\bin\text\MyThread.class
?????文件?????????935??2018-04-15?19:58??遺傳算法—最短路徑問題\bin\text\Route.class
?????文件?????????999??2018-04-23?08:42??遺傳算法—最短路徑問題\bin\text\Util.class
?????文件?????????951??2018-04-23?09:56??遺傳算法—最短路徑問題\bin\text\Window$1.class
?????文件????????3264??2018-04-23?09:56??遺傳算法—最短路徑問題\bin\text\Window.class
?????目錄???????????0??2018-04-30?11:01??遺傳算法—最短路徑問題\src\
?????目錄???????????0??2018-04-30?11:01??遺傳算法—最短路徑問題\src\text\
?????文件????????5357??2018-04-23?10:13??遺傳算法—最短路徑問題\src\text\GeneticAlgorithm.java
?????文件?????????135??2018-04-15?11:36??遺傳算法—最短路徑問題\src\text\MyMain.java
?????文件?????????545??2018-04-23?09:28??遺傳算法—最短路徑問題\src\text\MyThread.java
?????文件?????????700??2018-04-15?19:58??遺傳算法—最短路徑問題\src\text\Route.java
?????文件?????????663??2018-04-23?08:42??遺傳算法—最短路徑問題\src\text\Util.java
?????文件????????2889??2018-04-23?09:56??遺傳算法—最短路徑問題\src\text\Window.java