java實現(xiàn)遺傳算法實例分享(打印城市信息)
更新時間：2014年01月09日 09:48:32 投稿：zxhpj
本文介紹java實現(xiàn)遺傳算法的實例，代碼中使用城市名做為數(shù)據(jù)，可以打印當前代數(shù)的所有城市序列，以及其相關(guān)的參數(shù)，大家參考使用吧
復制代碼 代碼如下:
import java.util.*;
public class Tsp {
//private String cityEnd[]=new String[34];
private int cityNum=cityName.length; //城市個數(shù)
private int popSize = 50; //種群數(shù)量
private int maxgens = 20000; //迭代次數(shù)
private double pxover = 0.8; //交叉概率
private double pmultation = 0.05; //變異概率
private long[][] distance = new long[cityNum][cityNum];
private int range = 2000; //用于判斷何時停止的數(shù)組區(qū)間
private class genotype {
int city[] = new int[cityNum]; //單個基因的城市序列
long fitness; //該基因的適應度
double selectP; //選擇概率
double exceptp; //期望概率
int isSelected; //是否被選擇
}
private genotype[] citys = new genotype[popSize];
/**
* 構(gòu)造函數(shù)，初始化種群
*/
public Tsp() {
for (int i = 0; i < popSize; i++) {
citys[i] = new genotype();
int[] num = new int[cityNum];
for (int j = 0; j < cityNum; j++)
num[j] = j;
int temp = cityNum;
for (int j = 0; j < cityNum; j++) {
int r = (int) (Math.random() * temp);
citys[i].city[j] = num[r];
num[r] = num[temp - 1];
temp--;
}
citys[i].fitness = 0;
citys[i].selectP = 0;
citys[i].exceptp = 0;
citys[i].isSelected = 0;
}
initDistance();
}
/**
* 計算每個種群每個基因個體的適應度，選擇概率，期望概率，和是否被選擇。
*/
public void CalAll(){
for( int i = 0; i< popSize; i++){
citys[i].fitness = 0;
citys[i].selectP = 0;
citys[i].exceptp = 0;
citys[i].isSelected = 0;
}
CalFitness();
CalSelectP();
CalExceptP();
CalIsSelected();
}
/**
* 填充，將多選的填充到未選的個體當中
*/
public void pad(){
int best = 0;
int bad = 0;
while(true){
while(citys[best].isSelected <= 1 && best<popSize-1)
best ++;
while(citys[bad].isSelected != 0 && bad<popSize-1)
bad ++;
for(int i = 0; i< cityNum; i++)
citys[bad].city[i] = citys[best].city[i];
citys[best].isSelected --;
citys[bad].isSelected ++;
bad ++;
if(best == popSize ||bad == popSize)
break;
}
}
/**
* 交叉主體函數(shù)
*/
public void crossover() {
int x;
int y;
int pop = (int)(popSize* pxover /2);
while(pop>0){
x = (int)(Math.random()*popSize);
y = (int)(Math.random()*popSize);
executeCrossover(x,y);//x y 兩個體執(zhí)行交叉
pop--;
}
}
/**
* 執(zhí)行交叉函數(shù)
* @param 個體x
* @param 個體y
* 對個體x和個體y執(zhí)行佳點集的交叉，從而產(chǎn)生下一代城市序列
*/
private void executeCrossover(int x,int y){
int dimension = 0;
for( int i = 0 ;i < cityNum; i++)
if(citys[x].city[i] != citys[y].city[i]){
dimension ++;
}
int diffItem = 0;
double[] diff = new double[dimension];
for( int i = 0 ;i < cityNum; i++){
if(citys[x].city[i] != citys[y].city[i]){
diff[diffItem] = citys[x].city[i];
citys[x].city[i] = -1;
citys[y].city[i] = -1;
diffItem ++;
}
}
Arrays.sort(diff);
double[] temp = new double[dimension];
temp = gp(x, dimension);
for( int k = 0; k< dimension;k++)
for( int j = 0; j< dimension; j++)
if(temp[j] == k){
double item = temp[k];
temp[k] = temp[j];
temp[j] = item;
item = diff[k];
diff[k] = diff[j];
diff[j] = item;
}
int tempDimension = dimension;
int tempi = 0;
while(tempDimension> 0 ){
if(citys[x].city[tempi] == -1){
citys[x].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi ++;
}
Arrays.sort(diff);
temp = gp(y, dimension);
for( int k = 0; k< dimension;k++)
for( int j = 0; j< dimension; j++)
if(temp[j] == k){
double item = temp[k];
temp[k] = temp[j];
temp[j] = item;
item = diff[k];
diff[k] = diff[j];
diff[j] = item;
}
tempDimension = dimension;
tempi = 0;
while(tempDimension> 0 ){
if(citys[y].city[tempi] == -1){
citys[y].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi ++;
}
}
/**
* @param individual 個體
* @param dimension 維數(shù)
* @return 佳點集 (用于交叉函數(shù)的交叉點） 在executeCrossover()函數(shù)中使用
*/
private double[] gp(int individual, int dimension){
double[] temp = new double[dimension];
double[] temp1 = new double[dimension];
int p = 2 * dimension + 3;
while(!isSushu(p))
p++;
for( int i = 0; i< dimension; i++){
temp[i] = 2*Math.cos(2*Math.PI*(i+1)/p) * (individual+1);
temp[i] = temp[i] - (int)temp[i];
if( temp [i]< 0)
temp[i] = 1+temp[i];
}
for( int i = 0; i< dimension; i++)
temp1[i] = temp[i];
Arrays.sort(temp1);
//排序
for( int i = 0; i< dimension; i++)
for( int j = 0; j< dimension; j++)
if(temp[j]==temp1[i])
temp[j] = i;
return temp;
}
/**
* 變異
*/
public void mutate(){
double random;
int temp;
int temp1;
int temp2;
for( int i = 0 ; i< popSize; i++){
random = Math.random();
if(random<=pmultation){
temp1 = (int)(Math.random() * (cityNum));
temp2 = (int)(Math.random() * (cityNum));
temp = citys[i].city[temp1];
citys[i].city[temp1] = citys[i].city[temp2];
citys[i].city[temp2] = temp;
}
}
}
/**
* 打印當前代數(shù)的所有城市序列，以及其相關(guān)的參數(shù)
*/
public void print(){
/**
* 初始化各城市之間的距離
*/
private void initDistance(){
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++){
distance[i][j] = Math.abs(i-j);
}
}
}
/**
* 計算所有城市序列的適應度
*/
private void CalFitness() {
for (int i = 0; i < popSize; i++) {
for (int j = 0; j < cityNum - 1; j++)
citys[i].fitness += distance[citys[i].city[j]][citys[i].city[j + 1]];
citys[i].fitness += distance[citys[i].city[0]][citys[i].city[cityNum - 1]];
}
}
/**
* 計算選擇概率
*/
private void CalSelectP(){
long sum = 0;
for( int i = 0; i< popSize; i++)
sum += citys[i].fitness;
for( int i = 0; i< popSize; i++)
citys[i].selectP = (double)citys[i].fitness/sum;
}
/**
* 計算期望概率
*/
private void CalExceptP(){
for( int i = 0; i< popSize; i++)
citys[i].exceptp = (double)citys[i].selectP * popSize;
}
/**
* 計算該城市序列是否較優(yōu)，較優(yōu)則被選擇，進入下一代
*/
private void CalIsSelected(){
int needSelecte = popSize;
for( int i = 0; i< popSize; i++)
if( citys[i].exceptp<1){
citys[i].isSelected++;
needSelecte --;
}
double[] temp = new double[popSize];
for (int i = 0; i < popSize; i++) {
// temp[i] = citys[i].exceptp - (int) citys[i].exceptp;
// temp[i] *= 10;
temp[i] = citys[i].exceptp*10;
}
int j = 0;
while (needSelecte != 0) {
for (int i = 0; i < popSize; i++) {
if ((int) temp[i] == j) {
citys[i].isSelected++;
needSelecte--;
if (needSelecte == 0)
break;
}
}
j++;
}
}
/**
* @param x
* @return 判斷一個數(shù)是否是素數(shù)的函數(shù)
*/
private boolean isSushu( int x){
if(x<2) return false;
for(int i=2;i<=x/2;i++)
if(x%i==0&&x!=2) return false;
return true;
}
/**
* @param x 數(shù)組
* @return x數(shù)組的值是否全部相等，相等則表示x.length代的最優(yōu)結(jié)果相同，則算法結(jié)束
*/
private boolean isSame(long[] x){
for( int i = 0; i< x.length -1; i++)
if(x[i] !=x[i+1])
return false;
return true;
}
/**
* 打印任意代最優(yōu)的路徑序列
*/
private void printBestRoute(){
CalAll();
long temp = citys[0].fitness;
int index = 0;
for (int i = 1; i < popSize; i++) {
if(citys[i].fitness<temp){
temp = citys[i].fitness;
index = i;
}
}
System.out.println();
System.out.println("最佳路徑的序列：");
for (int j = 0; j < cityNum; j++)
{
String cityEnd[]={cityName[citys[index].city[j]]};
for(int m=0;m<cityEnd.length;m++)
{
System.out.print(cityEnd[m] + " ");
}
}
//System.out.print(citys[index].city[j] + cityName[citys[index].city[j]] + " ");
//System.out.print(cityName[citys[index].city[j]]);
System.out.println();
}
/**
* 算法執(zhí)行
*/
public void run(){
long[] result = new long[range];
//result初始化為所有的數(shù)字都不相等
for( int i = 0; i< range; i++)
result[i] = i;
int index = 0; //數(shù)組中的位置
int num = 1; //第num代
while(maxgens>0){
System.out.println("----------------- 第 "+num+" 代 -------------------------");
CalAll();
print();
pad();
crossover();
mutate();
maxgens --;
long temp = citys[0].fitness;
for ( int i = 1; i< popSize; i++)
if(citys[i].fitness<temp){
temp = citys[i].fitness;
}
System.out.println("最優(yōu)的解："+temp);
result[index] = temp;
if(isSame(result))
break;
index++;
if(index==range)
index = 0;
num++;
}
printBestRoute();
}
/**
* @param a 開始時間
* @param b 結(jié)束時間
*/
public void CalTime(Calendar a,Calendar b){
long x = b.getTimeInMillis() - a.getTimeInMillis();
long y = x/1000;
x = x - 1000*y;
System.out.println("算法執(zhí)行時間："+y+"."+x+" 秒");
}
/**
* 程序入口
*/
public static void main(String[] args) {
Calendar a = Calendar.getInstance(); //開始時間
Tsp tsp = new Tsp();
tsp.run();
Calendar b = Calendar.getInstance(); //結(jié)束時間
tsp.CalTime(a, b);
}
}
相關(guān)文章
這篇文章主要介紹了Java main 方法面試題的詳細整理的相關(guān)資料,這里介紹了10個經(jīng)典面試題的方法，需要的朋友可以參考下2017-09-09
java實現(xiàn)字符串和數(shù)字轉(zhuǎn)換工具
這篇文章主要為大家詳細介紹了java實現(xiàn)字符串和數(shù)字轉(zhuǎn)換工具，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-04-04
下面小編就為大家?guī)硪黄猄pring Boot修改啟動端口的方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-07-07
SpringBoot整合Mybatis-Plus、Jwt實現(xiàn)登錄token設(shè)置
Spring Boot整合Mybatis-plus實現(xiàn)登錄常常需要使用JWT來生成用戶的token并設(shè)置用戶權(quán)限的攔截器,本文就來詳細的介紹一下,具有一定的參考價值,感興趣的可以了解一下2024-02-02
Spring?Boot?+?EasyExcel?+?SqlServer?進行批量處理數(shù)據(jù)的高效方法
在日常開發(fā)和工作中,我們可能要根據(jù)用戶上傳的文件做一系列的處理,本篇文章就以Excel表格文件為例,主要介紹了Spring?Boot?+?EasyExcel?+?SqlServer?進行批量處理數(shù)據(jù)的高效方法,需要的朋友可以參考下2024-06-06
Java實現(xiàn)List反轉(zhuǎn)的方法總結(jié)
在Java中,反轉(zhuǎn)一個List意味著將其元素的順序顛倒,使得第一個元素變成最后一個,最后一個元素變成第一個,依此類推,這一操作在處理數(shù)據(jù)集合時非常有用,所以本文給大家總結(jié)了Java實現(xiàn)List反轉(zhuǎn)的方法,需要的朋友可以參考下2024-04-04
一次"java:程序包org.aspectj.lang不存在"問題解決實戰(zhàn)記錄
這篇文章主要給大家介紹了一次"java:程序包org.aspectj.lang不存在"問題解決的實戰(zhàn)過程,這個錯誤提示意味著你的Java程序中引用了org.aspectj.lang這個包,但是該包并不存在,文章通過圖文介紹的非常詳細,需要的朋友可以參考下2023-06-06
Java中for、while、do while三種循環(huán)語句的區(qū)別介紹
這篇文章主要介紹了Java中for、while、do while三種循環(huán)語句的區(qū)別介紹的相關(guān)資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-07-07
本文主要詳細介紹了Java如何實現(xiàn)一致性Hash算法，其實現(xiàn)原理將key映射到?2^32?-?1?的空間中，將這個數(shù)字的首尾相連，形成一個環(huán)。想了解更多的同學，可以參考本文2023-03-03
java 異常被catch后 將會繼續(xù)執(zhí)行的操作
這篇文章主要介紹了java 異常被catch后 將會繼續(xù)執(zhí)行的操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-02-02