void SA(int n, int *s, int *p, int *w, int b, int penalidade, int *peso_objetos, int *fo, int *inv, double alfa, double temperatura_inicial, double temperatura_final, int SAmax) { double x; // numero aleatorio entre ZERO e UM double temperatura; // temperatura corrente int iter; // numero de iteracoes na temperatura corrente int num_mudancas_temp; // numero de mudancas de temperatura int posicao_escolhida; // objeto escolhido int delta; // variacao de energia int fo_star; int *s_star; s_star = cria_vetor(n); inicializa_vetor(s_star,n); atualiza_melhor_solucao(s, s_star, n); fo_star = *fo; temperatura = temperatura_inicial; num_mudancas_temp = 0; printf("Solucao inicial: fo corrente = %d peso dos objetos = %2d \n", *fo,*peso_objetos); /* enquanto o sistema nao congelar faca */ while (temperatura > temperatura_final) { iter = 0; /* enquanto o equilibrio termico nao for atingido faca */ while (iter < SAmax){ iter++; /* escolha um vizinho qualquer */ posicao_escolhida = random(n); troca_bit(s, posicao_escolhida); /* calcule a variacao de energia */ int peso_modificado = (*peso_objetos) - w[posicao_escolhida]*(!s[posicao_escolhida]) + w[posicao_escolhida]*s[posicao_escolhida]; delta = - p[posicao_escolhida]*(!s[posicao_escolhida]) + penalidade * calcula_inviabilidade((*peso_objetos), b) + p[posicao_escolhida]*s[posicao_escolhida] - penalidade * calcula_inviabilidade(peso_modificado,b); // printf("variacao de energia = %3d \n",delta); /* se houver melhora, aceite o vizinho */ if (delta > 0){ (*fo) += delta; (*peso_objetos) = (*peso_objetos) - (w[posicao_escolhida])*(!s[posicao_escolhida]) + (w[posicao_escolhida])*(s[posicao_escolhida]); // printf("Solucao de melhora: fo corrente = %d peso dos objetos = %2d \n",*fo,*peso_objetos); if (*fo > fo_star){ atualiza_melhor_solucao(s, s_star, n); fo_star = *fo; // imprime_solucao(s_star,n); printf("********** fo_star = %3d \n",fo_star); } } else { /* se houver piora, aceite o vizinho com uma determinada probabilidade */ x = randomico(0,1); if (x < exp(delta/temperatura)){ (*fo) += delta; (*peso_objetos) = (*peso_objetos) - (w[posicao_escolhida])*(!s[posicao_escolhida]) + (w[posicao_escolhida])*(s[posicao_escolhida]); // printf("Solucao de piora: fo corrente = %d peso dos objetos = %2d \n",*fo,*peso_objetos); } else { /* Se o vizinho nao foi aceito, desfaca o movimento */ troca_bit(s, posicao_escolhida); } } } /* decresca a temperatura */ temperatura *= alfa; // printf("Temperatura atual = %10.3f\n", temperatura); num_mudancas_temp += 1; } printf("********* Melhor Solucao obtida pelo SA ************** \n"); // imprime_solucao(s_star,n); (*peso_objetos) = calcula_peso_objetos(s_star, n, w); (*inv) = calcula_inviabilidade(*peso_objetos, b); printf("peso dos objetos = %2d inviabilidade = %d \n",*peso_objetos, *inv); printf("funcao objetivo = %3d \n",fo_star); printf("Num. max. de solucoes analisadas = %ld \n",num_mudancas_temp*SAmax); printf("Numero de solucoes existentes = %.0f \n", exp(n*log(2))); printf("****************************************************** \n"); atualiza_melhor_solucao(s_star, s, n); (*fo) = fo_star; libera_vetor(s_star); getchar(); }