tsevolve.pro

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

;@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
;
;求视论坛 By Intently.xyz 2007-12-7
;程序说明：本程序应用了遗传算法解决了售货员行走的问题。
;
;@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
PRO TsEvolve, numCities=numCities, initPopulationSize=initPopulationSize, $
              populationSize=populationSize, numGenerations=numGenerations, $
              offspringPerGen=offspringPerGen, tournamentSize=tournamentSize, $
              crossOverRate=crossOverRate, elitism=elitism,mutationRate=mutationRate
	;Genetic evolution example.
	;Loosely based upon "An introduction to genetic algorithms in Java" by
	;Michael Lacy. In Java Developers Journal, volume 6,issue 3.
	;
	; keywords
	; numCities = number of cities the salesman visits
	; initPopulationSize = initial size of the population to cull from
	; populationSize = size of each generation
	; numGenerations = how long you want the process to evolve.
	; offspringPerGen = how many kids are born each generation
	; tournamentSize = how many parents compete for mating.
	; crossOverRate = how likey it is that parents will mate (0 to 1)
	; elitsm = how many parents survive to the next generation
	; mutationRate = how likely it is that a child will have a mutation

	IF NOT KeyWord_Set(numCities) then numCities = 25
	IF NOT KeyWord_Set(initPopulationSize) then initPopulationSize = 500
	IF NOT KeyWord_Set(populationSize) then populationSize = 100
	IF NOT KeyWord_Set(numGenerations) then numGenerations = 5000
	IF NOT KeyWord_Set(offspringPerGen) then offspringPerGen = 90
	IF NOT KeyWord_Set(tournamentSize) then tournamentSize = 6
	IF NOT KeyWord_Set(crossOverRate) then crossOverRate = 0.9
	IF NOT KeyWord_Set(elitism) then elitism = 10
	IF NOT KeyWord_Set(mutationRate) then mutationRate = 0.1

	IF (elitism + offspringPerGen) lt populationSize then begin
	  	void = Dialog_Message(['elitsm + offspringPerGen must be at least',$
	                         'equal to or greater than the populationSize'])
	  	Return
	ENDIF

	;create the gene object. (Chromosomes are made up of genes)
	oGenePool = Obj_New('tsGenePool',numCities)
	;create a population
	oPopulation = Obj_New('tsPopulation'						,$
						initPopulationSize=initPopulationSize	,$
						populationSize=populationSize			,$
						oGenePool=oGenePool						,$
						offspringPerGen=offspringPerGen			,$
						elitism=elitism							,$
						tournamentSize=tournamentSize			,$
						crossOverRate=crossOverRate				,$
						mutationRate=mutationRate				 $
						)


	;evolve over the number of generations
	Window,0,xs=400,ys=400
	Window,1,xs=400,ys=400
	Window,xs=400,ys=400,/free,/pix
	pix1 = !d.Window
	Window,xs=400,ys=400,/free,/pix
	pix2 = !d.Window
	FOR i=0,numGenerations-1 DO BEGIN
	  	oPopulation->reproduce
	  	oPopulation->getBestChromosome,xPos=xPos, yPos=yPos, fitness=fitness
	  	WSet,pix1
	  	title = 'Generation = ' + String(i) + '  ' + String(fitness)
	  	Plot,xPos,yPos,psym=-1,title=title,xrang=[0,100],yra=[0,100], $
	       xstyle=1,ysty=1
	  	WSet,0
	  	Device,copy=[0,0,400,400,0,0,pix1]
	  	WSet,pix2
	  	Plot,FIndgen(10),xran=[0,numGenerations],yrange=[0,50000],xsty=1,$
	                      ystyle=1,title='Fitness',/noerase
	  	Plots,i,fitness,psym=1
	  	WSet,1
	  	Device,copy=[0,0,400,400,0,0,pix2]
	ENDFOR
	;free the resources
	Obj_Destroy, oGenePool
	Obj_Destroy, oPopulation
	WDelete,pix1, pix2
	Return
END