android电脑ai寻路1.0——源码

package epoch.generation; import java.util.ArrayList; import java.util.Random; import java.util.Vector; public class CgaBob { public class SGenome { ArrayList<Integer> vecBits=new ArrayList<Integer>(); double dFitness; public SGenome(int num_bits) { //create a random bit string for (int i=0; i<num_bits; ++i) { vecBits.add(Math.random()>0.5?1:0); } } }; //double RAND_MAX 0x7fff; private double RandFloat() { //return (Math.random())/(RAND_MAX+1.0); return Math.random(); } public CgaBob() { m_vecGenomes.clear(); for(int i=0;i<m_iPopSize;i++) { m_vecGenomes.add(new SGenome(m_iChromoLength)); } //reset all variables m_iGeneration = 0; m_iFittestGenome = 0; m_dBestFitnessScore = 0; m_dTotalFitnessScore = 0; } //--------------------------RouletteWheelSelection----------------- // // selects a member of the population by using roulette wheel // selection as described in the text. //------------------------------------------------------------------ private SGenome RouletteWheelSelection() { double fSlice = RandFloat() * m_dTotalFitnessScore; //double fSlice = m_dTotalFitnessScore; double cfTotal = 0.0; int SelectedGenome = 0; for (int i=0; i<m_iPopSize; ++i) { cfTotal += m_vecGenomes.get(i).dFitness; if (cfTotal > fSlice) { SelectedGenome = i; break; } } return m_vecGenomes.get(SelectedGenome); } double m_dMutationRate=0.001; double m_dCrossoverRate=0.7; int m_iChromoLength=70; private boolean m_isExecute=false; public void setIsExecute(boolean bol) { m_isExecute=bol; } public boolean getIsExecute() { return m_isExecute; } //----------------------------Mutate--------------------------------- // iterates through each genome flipping the bits acording to the // mutation rate //-------------------------------------------------------------------- private void Mutate(ArrayList<Integer> vecBits) { for (int curBit=0; curBit<vecBits.size(); curBit++) { //do we flip this bit? if (RandFloat() < m_dMutationRate) { //flip the bit vecBits.set(curBit, vecBits.get(curBit)==1?0:1); } }//next bit } //----------------------------Crossover-------------------------------- // Takes 2 parent vectors, selects a midpoint and then swaps the ends // of each genome creating 2 new genomes which are stored in baby1 and // baby2. //--------------------------------------------------------------------- private void Crossover(SGenome mum,SGenome dad,SGenome baby1,SGenome baby2) { //just return parents as offspring dependent on the rate //or if parents are the same if ( (RandFloat() > m_dCrossoverRate) || (mum == dad)) { baby1 = mum; baby2 = dad; return; } //determine a crossover point int cp = RandInt(0, m_iChromoLength - 1); System.out.println("cp-"+Integer.valueOf(cp)+" mum size-" + Integer.valueOf(mum.vecBits.size()) +" dad size-" + Integer.valueOf(dad.vecBits.size())); //swap the bits baby1.vecBits.clear(); baby2.vecBits.clear(); for (int i=0; i<cp; ++i) { baby1.vecBits.add(mum.vecBits.get(i)); baby2.vecBits.add(dad.vecBits.get(i)); } for (int i=cp; i<mum.vecBits.size(); ++i) { baby1.vecBits.add(dad.vecBits.get(i)); baby2.vecBits.add(mum.vecBits.get(i)); } } //----------------------------------------------------------------------- // some random number functions. //----------------------------------------------------------------------- private int RandInt(int x,int y) { return (int) (Math.random()*(y-x+1)+x); } public void Epoch() { UpdateFitnessScores(); //Now to create a new population int NewBabies = 0; //create some storage for the baby genomes ArrayList<SGenome> vecBabyGenomes=new ArrayList<SGenome>(); while (NewBabies < m_iPopSize) { //select 2 parents SGenome mum = RouletteWheelSelection(); SGenome dad = RouletteWheelSelection(); //operator - crossover SGenome baby1=new SGenome(m_iChromoLength); SGenome baby2=new SGenome(m_iChromoLength); Crossover(mum, dad, baby1, baby2); System.out.println("new babies" + Integer.valueOf(NewBabies)); //operator - mutate Mutate(baby1.vecBits); Mutate(baby2.vecBits); //add to new population vecBabyGenomes.add(baby1); vecBabyGenomes.add(baby2); System.out.println("baby1 size-" + Integer.valueOf(baby1.vecBits.size()) + " baby2 size-" + Integer.valueOf(baby2.vecBits.size())); NewBabies += 2; //System.out.println(Integer.valueOf(NewBabies) + "-mum size:" + Integer.valueOf(mum.vecBits.size()) + " dady size:" + Integer.valueOf(dad.vecBits.size())); } //copy babies back into starter population m_vecGenomes = vecBabyGenomes; //increment the generation counter ++m_iGeneration; m_BobsMap.setGeneration(m_iGeneration); } private void LogSgenome(SGenome gen,String prefix) { String str=prefix; ArrayList<Integer> decode=Decode(gen.vecBits); for(int i=0;i<decode.size();i++) { str+=decode.get(i).toString(); } System.out.println(str); } public void setBobsMap(ScreenView view) { m_BobsMap=view; view.ResetMemory(); } private ScreenView m_BobsMap; private ArrayList<SGenome> m_vecGenomes=new ArrayList<SGenome>(); private int m_iGeneration; int m_iPopSize=140; private int m_iFittestGenome; private double m_dBestFitnessScore; private double m_dTotalFitnessScore; private void UpdateFitnessScores() { m_iFittestGenome=0; m_dBestFitnessScore=0; m_dTotalFitnessScore=0; for(int i=0;i<m_iPopSize;i++) { ArrayList<Integer> vecDirections=Decode(m_vecGenomes.get(i).vecBits); double dfitness=m_BobsMap.TestRoute(vecDirections,m_BobsMap); m_vecGenomes.get(i).dFitness=dfitness; m_dTotalFitnessScore+=dfitness; if(dfitness>m_dBestFitnessScore) { m_dBestFitnessScore=dfitness; m_iFittestGenome=i; // if(dfitness==1) { setIsExecute(false); } } } m_BobsMap.ResetMemory(); m_BobsMap.TestRoute(Decode(m_vecGenomes.get(m_iFittestGenome).vecBits),m_BobsMap); } private int m_iGeneLength=2; //---------------------------Decode------------------------------------- // // decodes a vector of bits into a vector of directions (ints) // // 0=North, 1=South, 2=East, 3=West //----------------------------------------------------------------------- private ArrayList<Integer> Decode(ArrayList<Integer> bits) { //System.out.println("Decode started"); ArrayList<Integer> directions=new ArrayList<Integer>(); //step through the chromosome a gene at a time for (int gene=0; gene < bits.size(); gene += m_iGeneLength) { //System.out.println("Decode " + String.valueOf(gene)); //get the gene at this position ArrayList<Integer> ThisGene=new ArrayList<Integer>(); for (int bit = 0; bit < m_iGeneLength; ++bit) { ThisGene.add(bits.get(gene+bit)); } //convert to decimal and add to list of directions directions.add(BinToInt(ThisGene)); } return directions; } //-------------------------------BinToInt------------------------------- // converts a vector of bits into an integer //---------------------------------------------------------------------- private Integer BinToInt(ArrayList<Integer> vec) { int val = 0; int multiplier = 1; for (int cBit=vec.size(); cBit>0; cBit--) { val += vec.get(cBit-1) * multiplier; multiplier *= 2; } return val; } }