Ant Colony Optimization

18/May/11 16:02

Kısayol

Şikayet

Özel Mesaj

sacrifice

Kayıt Tarihi: 25/Ağustos/2005

Bir endustrici arkimin projesi ben kodladim. Belki bir gun isinize yarar.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
/* constant definitions */
#define M 1000 //# of ants
#define N 100 //# of cities


/* end constant definitions */

typedef struct a {
	bool visited[N];
	int tour[N+1];
	int tour_length;
}Ant;

Ant ant[M]; // initialize "ANTS" Amount : K

int dist[N][N]; // distance matrix
int nn_list[N][N]; //nearest neighbour list
float pheromone[N][N]; // pheromone matrix
float choice_info[N][N]; // combined matrix

/* prototype definitions */
void ConstructSolutions();
void ASDecisionRule(int k,int i);
void NeighborListASDecisionRule(int k, int i);
void ChooseBestNext(int k, int i);
void ASPheromoneUpdate();
void Evaporate();
void DepositPheromone(int k);
void ACSLocalPheromoneUpdate(int k, int i);
void ComputeChoiceInformation();
int ComputeTourLength(int k);
/* end prototype definitions */


void ConstructSolutions() {
	int k=0;	int l=0;	int r;
	for(;k<M;k++) {
		for(;l<=N;l++) {
			ant[k].visited[l] = true;
		}
	}
	
	int step = 1;

	for(k=0;k<M;k++) {
		r= rand() % N;
		ant[k].tour[step] = r;
		ant[k].visited[r] = true;
	}

	while(step<N) {
		step = step+1;
		for(k=0;k<M;k++) {
			ASDecisionRule(k,step);
		}
	}
	printf("buraya kdr ok");
	for(k=0;k<M;k++) {
		ant[k].tour[N] = ant[k].tour[1];
		ant[k].tour_length = ComputeTourLength(k);
	}
}


void ASDecisionRule(int k,int i) {
		int j=0;
		int c= ant[k].tour[i-1];

	float sum_probability = 0.0;
	float selection_probability[N];
	for(;j<N;j++) {
printf("%d",j);
		if(ant[k].visited[j] == true) { selection_probability[j] = 0.0; }
		else
		{
				selection_probability[j] = choice_info[c][j];
				sum_probability = sum_probability + selection_probability[j];
		}

	}
	while( sum_probability < 1 ) sum_probability = sum_probability *10;
	float r = (float)(rand() % (int)sum_probability) +(float) ((rand() % 1000)/100); // advanced FP pseudo randomizer;;
	j=1;
	int p = selection_probability[j];
	while(p<r) {
		printf("buraya kdr ok");
		j = j+1;
		p = p + selection_probability[j];
	}
	ant[k].tour[i] = j;
	ant[k].visited[j] = true;
}

void NeighborListASDecisionRule(int k, int i) {
	int c = ant[k].tour[i-1];
	int j=0;
	float selection_probability[N];
	float sum_probability = 0.0;
	for(;j<N;j++) {
		if(ant[k].visited[nn_list[c][j]]) 
		{
			selection_probability[j] = 0.0;
		}
		else 
		{
			selection_probability[j] = choice_info[c][nn_list[c][j]];
			sum_probability = sum_probability + selection_probability[j];
		}
	}

	if( sum_probability == 0.0 ) { ChooseBestNext(k,i); }
	else {
		float r = (float)(rand() % (int)sum_probability) +(float) ((rand() % 1000)/100); // float rand sayi uretme sıkıntı;
		j=1;
		int p = selection_probability[j];
		while(p<r) {
			j = j+1;
			p = p + selection_probability[j];
		}
		ant[k].tour[i] = nn_list[c][j];
		ant[k].visited[nn_list[c][j]] = true;
	}
}

void ChooseBestNext(int k, int i) {
	float v = 0.0;
	int c = ant[k].tour[i-1];
	int j=0;
	int nc;
	for(;j<N;j++) {
		if( (ant[k].visited == false) && (choice_info[c][j] > v)) {
			nc = j;
			v = choice_info[c][j];
		}
	}

	ant[k].tour[i] = nc;
	ant[k].visited[nc] = true;
}

void ASPheromoneUpdate() {
	Evaporate();
	int k=0;
	for(;k<M;k++) {
		DepositPheromone(k);
	}
	ComputeChoiceInformation();
}

void Evaporate() {
	int i=0;	int j;	
	for(;i<N;i++) {
		for(j=i;j<N;j++) {
			pheromone[i][j] = (1-(float)((rand()%100)/100)) * pheromone[i][j]; // edited for a random probability;;
			pheromone[j][i] = pheromone[i][j];
		}
	}
}

void DepositPheromone(int k) {
	float dT = (1 / ant[k].tour_length);
	int i=0;
	int j,l;
	for(;i<N;i++) {
		j = ant[k].tour[i];
		l = ant[k].tour[i+1];
		pheromone[j][l] = pheromone[j][l] + dT;
		pheromone[l][j] = pheromone[j][l];
	}
}

void ACSLocalPheromoneUpdate(int k, int i) {
	int h,j;
	int T0=1;
	float prob = (rand()%100)/100;
	h = ant[k].tour[i-1];
	j = ant[k].tour[i];
	pheromone[h][j] = (1-prob) * pheromone[h][j] + prob* T0; // edited to run;;
	pheromone[j][h] = pheromone[h][j];
	pheromone[h][j] = pheromone[h][j] * 1; //part to be edited;;
	pheromone[j][h] = choice_info[h][j];
}



void ComputeChoiceInformation() {
	int k=0;
	int j=0;
	for(;k<M;k++) {
		printf("Ant %d chosen cities: \t",k);
		for(;j<N;j++) {
			if(ant[k].visited[j] == true) printf("%d\t",j);
		}
		printf("\n path_length = %d",ComputeTourLength(k) );
	}
}

int ComputeTourLength(int k) {
	int i; int j=0; int total=0;
	for(;j<N;j++) {
		for(i=j;i<i+1;i++) {
			if(ant[k].visited[j] == true) total = total + dist[i][j];
		}
	}
	return total;
}
	
void main() {
	ConstructSolutions();

	getch();
}

#Coding Sacrifice Perl FSO#

Alıntı yap

18/May/11 16:10

Kısayol

Şikayet

Özel Mesaj

kafkafkaf

Kayıt Tarihi: 18/Ağustos/2007

Güzel... Buradada ne olduğu var:

http://www.eksisozluk.com/show.asp?t=ant%20colony%20optimization

http://emorcraft.blogspot.com.tr/

Alıntı yap

18/May/11 16:23

Kısayol

Şikayet

Özel Mesaj

renegadealien

Kayıt Tarihi: 23/Mart/2003

Üniversitedeki son sınavımın sorusu...

Allahtan bitmiş...

İlk profesyonel uygulanış yerlerinden birisi Ford fabrikasında, bozuk olan üretim hatlarının, bozuk olmayan hatlara yönlendirilmesi şeklinde olduğunu biliyorum, kesin olmamakla birlikte...

Sanıyorum kendi atasözümü yaptım, kaynak belirterek kullanabilirsiniz. 10.05.2013 tarihli google arama sonucu : Aradığınız - "herşeyin hayırlısı rampanın bayırlısı" - ile ilgili hiçbir arama sonucu mevcut değil. Not : Söyleyeni belli olduğu için(Ben) atasözü değil, özlüsöz oluyormuş, dolayısı ile kendi özlüsözümü yapmış oldum :)

Alıntı yap

18/May/11 16:31

Kısayol

Şikayet

Özel Mesaj

sacrifice

Kayıt Tarihi: 25/Ağustos/2005

renegadealien bunu yazdı:
-----------------------------

Üniversitedeki son sınavımın sorusu...

Allahtan bitmiş...

-----------------------------

korkunc gercekten daha editlemem gereken yerleri de var :( Biz de bitirsek hayırlısıyla iyi olacak :)

#Coding Sacrifice Perl FSO#

Alıntı yap