import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;
public class GA {
int gennum; //种群的代数，初始为0
int popsize; //种群的大小
double crossp; //交叉概率
double mutationp; //变异概率
ArrayList<individual> population; //以链表保存种群数据
double lastprime=-1; //上一代种群中的最适应值
double prime=-1; //当前种群中的最适应值
double primedur=0; //最适应值保持的代数
GA(){
gennum=0;
popsize=10;
crossp=1.0;
mutationp=0.01;
population=new ArrayList<individual>();
}
void printinfo(){ //打印当前种群中所有个体的信息
for(individual ind:population){
System.out.println(ind);
}
}
void printtheprime(){ //打印当前种群中适应度最大的个体信息
System.out.println("第"+gennum+"代：");
sortbyfitness();
System.out.println("prime:"+population.get(0));
}
void printtoptenfit(){ //对当前代的种群中适应度前十的个体信息进行输出
printtheprime();
for(int i=1;i<9;i++){
System.out.print(i+1+" :");
System.out.println(population.get(i));
}
System.out.println("10 :"+population.get(9));
}
void sortbyfitness(){ //将当前种群中的个体按适应度从大到小排序
Comparator<individual> comparator=new Comparator<individual>(){
public int compare(individual in1,individual in2){ //fitness从大到小
if(in1.getfitness()>in2.getfitness())
return -1;
else if(in1.getfitness()==in2.getfitness())
return 0;
else
return 1;
}
};
Collections.sort(population,comparator);
}
void cal_floor_and_ceiling(){ //在完全生成一代新种群后开始生成下一代前，对种群中的每个个体的floor和ceiling值重新计算，以用于产生新一代的选择过程
double fitsum=0;
sortbyfitness(); //排序，fitness从大到小
//进行最适值出现判断，作为遗传终结信号
prime=this.population.get(0).x;
if(prime!=lastprime){
primedur=0;
lastprime=prime;
}
else{
primedur++;
}
//计算所有个体的适应度之和
for(individual in:population){
fitsum+=in.getfitness();
}
//根据fitsum计算单个个体的floor和ceiling值
double lastnum=0; //上一个个体的ceiling值，初始化为0
for(int i=0;i<popsize;i++){
//individual temp=population.get(i);
population.get(i).floor=lastnum;
lastnum+=population.get(i).getfitness()/fitsum;
population.get(i).ceiling=lastnum;
}
//为了避免小数不完全表示产生的微小误差，将最后一个个体的ceiling值强制设置为1
population.get(popsize-1).ceiling=1.0;
}
void select(){ //遗传操作第一步：选择
Random rand=new Random();
//计算新的floor和ceiling
this.cal_floor_and_ceiling();
//产生个数为popsize的新种群
ArrayList<individual> temp=new ArrayList<individual>(); //放入新的临时种群ArrayList信息
double randselect=0;
for(int i=0;i<popsize;i++){
randselect=rand.nextDouble();
//查找转盘中对应的个体
for(int j=0;j<popsize;j++){
individual tempin=this.population.get(j);
if(tempin.floor<=randselect&&tempin.ceiling>=randselect){ //找到符合条件的个体
individual newone=new individual(tempin);
temp.add(newone);
break; //找到即跳出循环
}
}
}
this.population.clear();
this.population=temp;
}
void crossover(){ //交叉
int pair_num_of_cross=(int) (crossp*popsize/2); //一共有popsize/2对的个体，根据交叉概率计算出进行交叉的对数
Random rand=new Random();
int in1,in2; //随机选出的一对交配个体的序号
int crosspoint;
for(int i=0;i<pair_num_of_cross;i++){
in1=rand.nextInt(popsize);
in2=rand.nextInt(popsize);
crosspoint=rand.nextInt(19); //在0~18之间选出一个随机整数作为交叉点，大于这个数的部分被交换
individual temp1=this.population.get(in1);
individual temp2=this.population.get(in2);
String ts1=new String(temp1.code);
String ts2=new String(temp2.code);
temp1.code=ts1.substring(0, crosspoint+1)+ts2.substring(crosspoint+1,20);
temp2.code=ts2.substring(0, crosspoint+1)+ts1.substring(crosspoint+1,20);
temp1.numfromcode(temp1.code); //重新计算编码对应值
temp2.numfromcode(temp2.code);
temp1.calnewfitness(); //重新计算适应度
temp2.calnewfitness();
}
}
void mutation(){ //变异
Random rand=new Random();
int mutpoint=-1; //变异点（编码某位的index）
int mutin=-1; //变异个体在population中的index
int muttimes=(int)(popsize*this.mutationp); //根据变异概率计算出变异的次数
for(int i=0;i<muttimes;i++){
mutin=rand.nextInt(popsize);
mutpoint=rand.nextInt(20);
individual temp=this.population.get(mutin);
String ts=temp.code;
if(ts.charAt(mutpoint)=='0') ts=ts.substring(0, mutpoint)+'1'+ts.substring(mutpoint+1, 20);
if(ts.charAt(mutpoint)=='0') ts=ts.substring(0, mutpoint)+'0'+ts.substring(mutpoint+1, 20);
temp.numfromcode(temp.code); //重新计算编码对应值
temp.calnewfitness(); //重新计算适应度
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
GA myGA=new GA(); //创建一个遗传算法结构
//随机产生初始种群
Random rand=new Random();
for(int size=0;size<myGA.popsize;size++){
String tempcode="";
for(int i=0;i<20;i++){
tempcode+=Integer.toString(Math.abs(rand.nextInt()%2)); //将tempcode变为长度为20的二进制编码串
}
individual temp=new individual(tempcode);
myGA.population.add(temp);
}
//遗传操作
while(myGA.primedur<10){
myGA.printtheprime(); //排序并打印当前的最佳值
System.out.println(myGA.population.size());
myGA.gennum++; //开始新一代的产生，代数增加1
//step1：使用转盘度选择方式从当前种群中选择个体生成新的未交叉变异种群
myGA.select();
//step2:交叉操作，根据交叉概率选择出一定数量的交配对，进行交配
myGA.crossover();
//step3:变异操作，根据变异概率选择出一定数量的个体，随机选出一位编码进行变异
myGA.mutation();
}
}
}
