Simulated annealing to solve the assignment problem of c + + program, thank you

CodePudding user response:

I also want to ask this question

CodePudding user response:

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * simulated annealing algorithm solving the problem of work assigned randomly generated N working time matrix
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include
#include
#include
#include
using namespace std;
Const int MAXN=50;//maximum number of constraints to n
Const double INIT_T=2000;//initial temperature
Const double RATE=0.95;//temperature decrement
Const double FINAL_T=0;//end temperature
Const int IN_LOOP=13000;//number of inner loop
Const int OUT_LOOP=20000;//outer cycles
Struct work {//define the type of work structure
Int [MAXN] p;//workers number
Double time.//time
};
Int N;//the number of workers
Double D [MAXN] [MAXN];//work time
Int x [MAXN] [MAXN];//select workers with work
The work bestwork;//the most optimal traversal path

Void swap (int & amp; A, int & amp; B)//attention & amp; A and b & amp; B we want p [] the data stored in the
{
int t;
T=a; a=b; b=t;
}
The inline double totaldist (work q)//calculate the total time
{
Int a, I, j;
Double cost=0;
For (I=0, j=0; i{
A=q.p [I];
Cost=D [a] [j];
}
The return cost.
}
Void init ()//read the data and the initialization time//input matrix D [I] [j] format: workers I work j
{cout<& lt;" Input "N" & lt; Cin> N;
Int I=0, j=0;
for(i=0; i{
for(j=0; J
D [I] [j]=rand () % 100;

}

for (i=0; i{
Bestwork. P [I]=I;

}
Bestwork. Time=totaldist (bestwork);
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * have assigned method
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
Work getnext (5 p)//the new produce function
{
Int x, y;
The work ret.
Ret=p;
Do {
X=rand () % 4;
Y=rand () % 4;//x, y generating random Numbers from 0 to 3
} while (x==y);
Swap (ret) p [x], ret. P [y]);//exchange two workers position order
Ret. Time=totaldist (ret);
return ret;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
annealing and cooling process* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
The work sa ()
{
Double T;//temperature
The work curwork newwork;//the current assignment and new assigned
Int I, A_t=0;
Double delta;
T=INIT_T;//assign initial temperature
Curwork=bestwork;
While (true) circulate in//
{
For (I=1; i<=IN_LOOP; I++)
{
Newwork=getnext (curwork);//the new path
The delta=newwork. Time - curwork. Time;
If (delta & lt; 0.0)
{
Curwork=newwork;
}
The else
{
Double RND=rand () % 1001/1000;//random floating point Numbers from 0 to 1
Double p=exp (- delta/T);
If (p & gt; RND)
Curwork=newwork;
The else
Curwork=curwork;
}
A_t + +;
}
T=T * RATE;//cooling
If (A_t & gt;=OUT_LOOP | | T & lt; FINAL_T) break;//cycle stop condition

}
Return newwork.
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * program main function
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
Int main ()
{
init();
for(int i=0; i{
for(int j=0; JCoutCout}
Initial work assigned: printf (" %. 4 f \ n ", bestwork. Time);
for(int i=0; i{
Printf (" % d - & gt;" The bestwork. [I] p + 1);
}
printf("\n");
Bestwork=sa ();
The optimal work assigned: printf (" %. 4 f \ n ", bestwork. Time);
for(int j=0; J{
Printf (" % d - & gt;" The bestwork. P [j] + 1);
}
printf("\n");
system("pause");
return 0;
}