/**
* 2012-5-10
* Main.java
* author:helong
*/
package com.cqut;
import java.util.Random;
/**
* @author helong
*
*/
public class Algorithm {
/**
* 定义的一些全局变量
*/
public static String[] CITYNAME={"北京","天津","沈阳","长春","哈尔滨","济南","合肥","南京","上海","杭州"};
public static int[][] distance={
{0, 137, 741, 1046,1288,497, 1074,1160,1463,1589},
{137, 0, 707, 1012,1354,360, 973, 1023,1326,1452},
{741, 707, 0, 305, 547, 1067,1680,1730,2033,2159},
{1046,1012,305, 0, 242, 1372,1985,2035,2335,2464},
{1288,1354,547, 242, 0, 1614,2227,2277,2577,2706},
{497, 360, 1067,1372,1614,0, 613, 663, 966, 1092},
{1074,973, 1680,1985,2227,613, 0, 312, 615, 451},
{1160,1023,1730,2035,2277,663, 312, 0, 303, 429},
{1463,1326,2033,2335,2577,966, 615, 303, 0, 201},
{1589,1452,2159,2464,2706,1092,451, 429, 201, 0}
};
public static int CHROMOSOME_SIZE=9;//染色体的长度,也就是城市的数目
public static int POPULATION_SIZE=10;//种群数量
public static int GENERATION_NUM=1000;//产生的代数
public static int[][] POPULATION = new int[POPULATION_SIZE][CHROMOSOME_SIZE];
public static float pc=0.5f;//杂交概率
public static float pm=0.7f;//变异概率
public static float bestFitness=0;//最优适应度
public static int[] bestSolution;//最优解
public static int bestIndex;//最优解在population数组中的下标
/**
* 主程序
* @param args
*/
public static void main(String args[]) {
/*int[] first={1,2,3,4,5,6,7,8,9};
int[] second={4,5,3,6,8,9,7,2,1};
int[][] result;
Algorithm algorithm=new Algorithm();
result=algorithm.crossoverWithChromosome1(first, second);
algorithm.printArray("first", result[0]);
algorithm.printArray("first", result[1]);*/
System.out.println("初始化数据为:");
Algorithm algorithm = new Algorithm();
int[] temp={0,4,3,2,1,5,7,8,6};
System.out.println("最优解为"+1/algorithm.fitness(temp));
algorithm.init();
algorithm.reproduce();
}
/**
* 初始化数据
*/
public void init(){
Random random=new Random();
for(int i=0;i<POPULATION_SIZE;i++){
int begin=random.nextInt(CHROMOSOME_SIZE-1);
int[] temp=randomArray(begin,CHROMOSOME_SIZE-1);
POPULATION[i]=temp;
}
}
/**
*计算染色体的适应度 这个适应度路程的长度的倒数
*/
public float fitness(int[] chromosome){
float result=0;
for(int i=0;i<CHROMOSOME_SIZE-1;i++){
result+=distance[chromosome[i]][chromosome[i+1]];
}
result+=distance[chromosome[CHROMOSOME_SIZE-1]][chromosome[0]];
//System.out.println("路程 result is "+result);
return 1/result;
}
/**
* 从当前的POPULATION中找出目前的最佳的fitness 和最优解并更新 并产生当前种群的适应度的数组
*/
public float[] getBestAndFitness(){
float[] populationFitness=new float[POPULATION_SIZE];
for(int i=0;i<POPULATION.length;i++){
float tempFitness=fitness(POPULATION[i]);
populationFitness[i]=tempFitness;
if(tempFitness>bestFitness){
bestFitness=tempFitness;
bestSolution=POPULATION[i];
bestIndex=i;
}
}
System.out.print("最优解为:");
for (int i : bestSolution) {
System.out.print(CITYNAME[i]+" ");
}
System.out.println("路程为"+1/bestFitness);
return populationFitness;
}
/**
* 模拟的遗传过程 包括选择、交配、变异
*/
public void reproduce(){
float[] populationFitness=getBestAndFitness();
int index=0;
while(index<GENERATION_NUM){//代数
index++;
System.out.println("第"+index+"代");
//选择参加交配的个体
int[][] selectPopulation=select(populationFitness);//选择过程产生的种群为selectPopulation;
//对选择的群体进行交配
int[][] crossoverPolulation=crossover(selectPopulation);//交配过程之后产生的种群为crossoverPolulation
//对交配后的群体进行变异
int[][] mutatePopulation=mutate(crossoverPolulation);
//更新POPULATION
POPULATION=mutatePopulation;
populationFitness=getBestAndFitness();
}
}
/**
* 选择过程 采用赌轮盘
* @return 选择出来的群体 int[][]
*/
public int[][] select(float[] fitness){
int[][] result=new int[POPULATION_SIZE][CHROMOSOME_SIZE];
float[] fitnessScale=new float[POPULATION_SIZE];//适应度的比例
float sumFitness=0;
//得到适应度的总值
for(int i=0;i<fitness.length;i++){
sumFitness+=fitness[i];
}
//计算适应度的比例
for(int i=0;i<fitnessScale.length;i++){
fitnessScale[i]=fitness[i]/sumFitness;
}
//print("fitnessScale is",fitnessScale);
int[] index=roulette(fitnessScale,POPULATION_SIZE);
for(int i=0;i<index.length;i++){
result[i]=POPULATION[index[i]];
}
//System.out.println("over select");
return result;
}
/**
* 实现赌轮盘方式 fitnessScale数组表示所占的比例,num表示要返回的结果个数
* @param fitnessScale
* @param num
* @return 下标数组 int[]
*/
public int[] roulette(float[] fitnessScale,int num){
int[] result=new int[num];
Random random = new Random();
int index=0;
float begin=random.nextFloat();
while(index<num){
begin+=random.nextFloat();
begin%=1;
float low=0;
int i=-1;
while(low<begin){
i++;
low+=fitnessScale[i];
}
result[index]=i;
index++;
}
return result;
}
/**
* 杂交过程
* @param population 参与杂交的种群
* @return
*/
public int[][] crossover(int[][] population){
int[][] result=new int[POPULATION_SIZE][CHROMOSOME_SIZE];
//选择要参加交配的个体,这里假设选择出来的个体全部参与的交配
int[][] populationForCrossOver=population;
//开始交配过程
for(int i=0;i<populationForCrossOver.length;i+=2){
if(i==populationForCrossOver.length-1){//相当于自己与自己杂交,复制了一个自己
result[i]=population[i];
}
else{
int[][] twoChildren=crossoverWithChromosome(populationForCrossOver[i], populationForCrossOver[i+1]);
result[i]=twoChildren[0];
result[i+1]=twoChildren[1];
}
}
//System.out.println("crossover over");
return result;
}
/**
* 实现杂交 采用的是部分映射杂交
* @param fatherChromosome
* @param motherChromosome
* @return 返回两个后代
*/
public int[][] crossoverWithChromosome(int[] firstChromosome,int[] secondChromosome){
//System.out.println("crossoverWithChromosome is begin");
int[][] result=new int[2][CHROMOSOME_SIZE];
Random random=new Random();
int[] firstChild=new int[CHROMOSOME_SIZE];
int[] secondChild=new int[CHROMOSOME_SIZE];
//初始化后代 -1表示该位的值待定
for(int i=0;i<CHROMOSOME_SIZE;i++){
firstChild[i]=-1;
secondChild[i]=-1;
}
//映射表
EqualMap<Integer> map=new EqualMap<Integer>();
//产生两个杂交点 0-size 也就是有size+1个交叉位
int firstPoint=random.nextInt(CHROMOSOME_SIZE);
int secondPoint=0;
while(true){
int r=random.nextInt(CHROMOSOME_SIZE);
if(r>firstPoint){
secondPoint=r;
break;
}
else if(firstPoint==CHROMOSOME_SIZE-1){
secondPoint=CHROMOSOME_SIZE-1;
break;
}
}
/*int firstPoint=3;
int secondPoint=7;*/
//System.out.println("firstPoint is "+firstPoint+" secondPoint is "+secondPoint);
//先把交叉点内的值填入
for(int i=firstPoint;i<secondPoint;i++){
int firstValue=firstChromosome[i];
int secondValue=secondChromosome[i];
secondChild[i]=firstValue;
firstChild[i]=secondValue;
//填写映射表
if(firstValue!=secondValue){
map.add(firs
遗传算法实现的旅行商问题(Java)
5星 · 超过95%的资源 需积分: 22 151 浏览量
2012-06-21
13:15:54
上传
评论 1
收藏 14KB ZIP 举报
wsdydmw
- 粉丝: 11
- 资源: 8
最新资源
- STM32单片机FPGA毕设电路原理论文报告一种基于st62单片机的称重显示控制器
- STM32单片机FPGA毕设电路原理论文报告一种基于SPCE061A单片机的信号发生器
- Ruby菜鸟入门指南.md
- STM32单片机FPGA毕设电路原理论文报告一种基于PIC系列单片机的SPWM逆变电源
- exp01A.cpp
- Rust语言学习万字指南!.md
- STM32单片机FPGA毕设电路原理论文报告一种基于msp430单片机的心电模块设计
- STM32单片机FPGA毕设电路原理论文报告一种基于MSP430单片机的日程管理系统
- web-screen-capture.jar
- 2024最新计算机二级真题练习题库含答案.md
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
- 1
- 2
- 3
前往页