[인공지능]Simulated Annealing - TSP561

소개글

Traveling Salesman Problem 을 SA(Simulated Annealing)으로 해를 구하는 프로그램입니다. TSP 입력파일은 561개의 도시이며, 웹에서 구할수 있는 것입니다.(tsp561.txt)
학교 팀 프로젝트의 과제로서 완성하였습니다.
SA 프로그래밍을 어떻게 해야 할지 갈피를 못 잡으시는 분들께, 조그마한 참고 자료가 되길 바랍니다.

컴파일 실행환경

Visual C++ 6.0

본문내용

// Function List
void TSPFileLoad( int **TargetArray ); // TSP file load
double randomGene(); // RandomNumber [0, 1] Generator
int* seqGene(int *sequence); // Random Sequence Generator
long seqEval(int* sequence); // Sequence total cost Evaluator
void wrt2File(int* sequence); // Write to file a sequence
void printSeq(int* sequence); // Printout a sequence
bool cmpSeq(int* seq1, int* seq2); // Compare two sequences
int* updateSeq(int* sequence); // update the sequence by moving subSequence [1, 5]

// In Main Function
for (double Temperature = TEMPER_MAX; Temperature > TEMPER_MIN; Temperature *= TEMPER_RATE)
{
// probability = exp(Delta E / T)

nextSeqPtr = updateSeq(curSeq);
if (seqEval(curSeqPtr) > seqEval(nextSeqPtr)) // If the nextSeq is better than curSeq,
{ // then, replace curSeq with nextSeq.
for (i = 0; i < NODEMAX; i++)
{
curSeq[i] = nextSeq[i];
}
cout << seqEval(curSeq);
}
// If the same evaluation of another sequence is generated again and again,
// then, we accept that the sequence is solution.

else {
probability = (exp( (seqEval(curSeqPtr) - seqEval(nextSeqPtr) ) / Temperature ));
if ( randomGene() < (probability) )
{ // if RandomNumber < exp(Delta E / T)
for (i = 0; i < NODEMAX; i++)
{
curSeq[i] = nextSeq[i];
}
cout << seqEval(curSeq);
}
}
cout << endl << "T: " << Temperature << " P: " << probability << " S: ";
}

압축파일 내 파일목록

Simulated Anealing.dsw
Simulated Anealing.ncb
Simulated Anealing.opt
Simulated Anealing.plg
Simulated Anealing.exe
AI_Project_Docu.doc
result.txt
SA.CPP
sample.txt
Simulated Anealing.dsp

참고 자료

없음