tspopulation__define.pro

采用蚁群算法解决旅行商问题

;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

PRO TsPopulation::TSPopSort, population
	;sorts the population from the smallest distance to the greatest
	numInPop = N_Elements(population)
	fitnessArray = FltArr(numInPop)
	;get the fitness of each individual chromosome.
	FOR i=0, numInPop-1 DO $
	  	fitnessArray[i] = population[i]->getFitness()
	indices = Sort(fitnessArray)
	population = population[indices]

	Return
END

;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

FUNCTION TsPopulation::Crossover, parents
	;crossover breeding method

	children = ObjArr(2)
	;start off with the kids being the same as the parents
	children[0] = parents[0]->copy()
	children[1] = parents[1]->copy()

	;only crossover IF the ranDOmness says so
	IF (Randomu(seed,1))[0] lt self.crossOverRate THEN BEGIN
	  	;find out how Long they are
	  	children[0] ->GetProperty, numGenes=numGenes,xPos=momsX, yPos=momsY, $
	                             names=momsNames
	  	children[1] ->GetProperty, xPos=dadsX, yPos=dadsY, names=dadsNames
	  	;mix the kids genes instead of the parents (identical at this point)
	  		crossOverPoint =  Fix((Randomu(seed,1) * numGenes)[0]) > 1
	  	;get the initial points
	  	child1X = momsX[0:crossOverPoint-1]
	  	child1Y = momsY[0:crossOverPoint-1]
	  	child1names = momsNames[0:crossOverPoint-1]
	  	child2X = dadsX[0:crossOverPoint-1]
	  	child2Y = dadsY[0:crossOverPoint-1]
	  	child2names = dadsNames[0:crossOverPoint-1]
	  	;now have to find the points that are missing from the other parent
	  	;and in the order that they are present in the other parent
	  	missingNamesFromMom = momsNames[crossOverPoint:*]
	  	missingNamesFromDad = dadsNames[crossOverPoint:*]
	  	;child 1 first
	  	numMissing = N_Elements(missingNamesFromMom)
	  	indices = IntArr(numMissing)
	  	FOR i=0,N_Elements(missingNamesFromMom)-1 DO BEGIN
	    	indices[i] = Where(missingNamesFromMom[i] eq dadsNames,count)
	    	IF count ne 1 THEN Stop ;should never happen
	  	ENDFOR
	  	;sort the indices in the order they came from dad
	  	indices = indices[Sort(indices)]
	  	tempX = dadsX[indices]
	  	tempY = dadsY[indices]
	  	tempNames = dadsNames[indices]
	  	;put the two arrays together to FORm the new sequence
	  	newXpos0 = [child1X,tempX] & newYpos0 = [child1Y,tempY]
	  	newNames0 = [child1Names,tempNames]
	  	;now child 2
	  	numMissing = N_Elements(missingNamesFromDad)
	  	indices = IntArr(numMissing)
	  	FOR i=0,N_Elements(missingNamesFromDad)-1 DO BEGIN
	  		indices[i] = Where(missingNamesFromDad[i] eq momsNames,count)
	    	IF count ne 1 THEN Stop ;should never happen
	  	ENDFOR
	  	;sort the indices in the order they came from mom
	  	indices = indices[Sort(indices)]
	  	tempX = momsX[indices]
	  	tempY = momsY[indices]
	  	tempNames = momsNames[indices]

	  	newXpos1 = [child2X,tempX] & newYpos1 = [child2Y,tempY]
	  	newNames1 = [child2Names,tempNames]
	  	;give the new children their traversal order
	  	children[0]->SetProperty,xPos=newXpos0, yPos=newYpos0, names=newNames0
	  	children[1]->SetProperty,xPos=newXpos1, yPos=newYpos1, names=newNames1
	ENDIF

	Return, children
END
;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

FUNCTION TsPopulation::mutate, children
	;mutation method swaps two positions in each child

	;only mutate IF the ranDOmness says so
	IF (Randomu(seed,1))[0] LT self.mutationRate THEN BEGIN
	  	;find out how Long they are
	  	children[0] ->GetProperty, numGenes=numGenes,xPos=xPos0, yPos=yPos0, $
	                             names=names0
	  	;mix the kids genes instead of the parents
	  	randomPoint1 =  Long((Randomu(seed,1) * numGenes)[0])
	  	randomPoint2 =  Long((Randomu(seed,1) * numGenes)[0])
	  	children[1] ->GetProperty, xPos=xPos1, yPos=yPos1, names=names1
	  	;save the first point
	  	xRan0a = xPos0[randomPoint1]
	  	yRan0a = yPos0[randomPoint1]
	  	nameRan0a = names0[randomPoint1]
	  	;replace it with the second
	  	xPos0[randomPoint1] = xPos0[randomPoint2]
	  	yPos0[randomPoint1] = yPos0[randomPoint2]
	  	names0[randomPoint1] = names0[randomPoint2]
	  	;replace the second with the first
	  	xPos0[randomPoint2] = xRan0a
	  	yPos0[randomPoint2] = yRan0a
	  	names0[randomPoint2] = nameRan0a
	  	;same sequence FOR the second child
	  	xRan1a = xPos1[randomPoint1]
	  	yRan1a = yPos1[randomPoint1]
	  	nameRan1a = names1[randomPoint1]
	  	xPos1[randomPoint1] = xPos1[randomPoint2]
	  	yPos1[randomPoint1] = yPos1[randomPoint2]
	  	names1[randomPoint1] = names1[randomPoint2]
	  	xPos1[randomPoint2] = xRan1a
	  	yPos1[randomPoint2] = yRan1a
	  	names1[randomPoint2] = nameRan1a
	  	;update the chromosomes
	  	children[0] ->SetProperty, xPos=xPos0, yPos=yPos0, names=names0
	  	children[1] ->SetProperty, xPos=xPos1, yPos=yPos1, names=names1
	ENDIF

	Return, children
END
;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

FUNCTION TsPopulation::selectParents
	;uses tournament selection to pick the parents

	;ranDOm spot to start looking
	startIndex = (Fix(Randomu(seed,1) * self.populationSize))[0]
	;handle the case Where we are too close to the END
	StopIndex = startIndex + self.tournamentSize-1
	;check to make sure that we DOn't try running off the END of the array
	IF StopIndex GT (self.populationSize-1) THEN BEGIN
	   	StopIndex = self.populationSize-1
	   	startIndex = StopIndex - self.tournamentSize
	ENDIF
	;pull out the contestants
	gladiators = (*self.population)[startIndex:StopIndex]
	;find out who is best
	self->TSPopSort,gladiators
	;pick the best two
	bestParents = gladiators[0:1]
	Return,bestParents
END

;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

PRO TsPopulation::Shuffle
	;ranDOmizes the order

	;get the indices in ranDOm order
	indices = Sort(Randomu(seed,self.populationSize))
	;resort the population
	*self.population = (*self.population)[indices]
	Return
END

;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

PRO TsPopulation::RePROduce
	;method to create a new generation

	;ranDOmize the order
	self->shuffle
	;blank object array FOR kids
	children = ObjArr(self.offspringPerGen)
	;use crossover to beget children
	FOR i=0,self.offspringPerGen-1,2 DO BEGIN ;2 kids FOR each crossover so skip by 2
	  	;have a tournament to get the best parents
	  	parents = self->selectParents()
	  	;breed the parents and get twins each time
	  	children[i:i+1] = self->crossover(parents)
	  	;give an opportunity FOR mutations
	  	children[i:i+1] = self->mutate(children[i:i+1])
	END
	;find out who is best
	population = *self.population
	self->TSPopSort,population
	;only keep the elitism best from the old population.
	FOR i=self.elitism,N_Elements(population)-1 DO Obj_Destroy,population[i]
	;replace the old population with the children. Note that IF we have
	;more children than populationSize - elitism they will be destroyed
	count = 0L
	FOR i = self.elitism,N_Elements(population)-1 DO BEGIN
	  	population[i] = children[count]
	  	count = count + 1L
	ENDFOR
	;destroy any remaining children
	FOR i=count,self.offspringPerGen-1 DO Obj_Destroy,children[i]
	;update the population
	*self.population = population

	Return
END

;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

PRO TsPopulation::GetBestChromosome,xPos=xPos, yPos=yPos, fitness=fitness
	;gets the best current chromosome

	;find out who is best
	population = *self.population
	self->TSPopSort,population
	;the first is always the best
	population[0]->GetProperty,xPos=xPos, yPos=yPos, fitness=fitness

	Return
END

;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

FUNCTION TsPopulation::Init, initPopulationSize=initPopulationSize, $
                       populationSize=populationSize, oGenePool=oGenePool, $
                       offspringPerGen=offspringPerGen, elitism=elitism, $
                       tournamentSize=tournamentSize, crossOverRate=crossOverRate, $
                       mutationRate=mutationRate


	;make an array FOR all the initial population chromosomes.
	;By having a large initial array we cover more search space. Culling
	;it DOwn later speeds up the solution finding
	oInitialPopulation = ObjArr(initPopulationSize)
	FOR i=0,initPopulationSize-1 DO $
	  oInitialPopulation[i] = oGenePool->createRanDOmChromosome()

	;find out how fit the initial population is. oInitialPopulation is scored
	;and sorted in place.
	self->TSPopSort,oInitialPopulation
	newPopulation = oInitialPopulation[0:populationSize-1]
	;release the other objects
	FOR i=populationSize,initPopulationSize-1 DO Obj_Destroy,oInitialPopulation[i]
	self.populationSize = populationSize
	self.population = Ptr_New(newPopulation,/No_Copy)
	self.offspringPerGen = offspringPerGen
	self.tournamentSize  = tournamentSize
	self.crossOverRate   = crossOverRate
	self.mutationRate    = mutationRate
	self.elitism  		 = elitism

	Return,1
END

;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

PRO TsPopulation::cleanup

	IF Ptr_Valid(self.population) THEN BEGIN
	  population = *self.population
	  FOR i=0,N_Elements(population)-1 DO BEGIN
	  		IF Obj_Valid(population[i]) THEN Obj_Destroy,population[i]
	  ENDFOR
	  Ptr_Free,self.population
	ENDIF

	Return
END

;{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|{{:|

PRO TsPopulation__Define
    void = {TsPopulation				,$
            populationSize 	: 0L		,$ ;size for each generation
            population 		: Ptr_New()	,$ ;pointer that holds the chromosomes
            offspringPerGen : 0L		,$ ;how many kids each generation
            tournamentSize 	: 0L		,$ ;how big each tournament round is
            crossOverRate 	: 0.0		,$ ;how likely it is that two parents will mate
            mutationRate 	: 0.0		,$ ;how often a mutation occurs
            elitism 		: 0L } 		   ;how many individuals survive each generation

	Return
END