API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 5th, 2019
121
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.15 KB | None | 0 0
raw download clone embed print report
  1. :-dynamic geracoes/1.
  2. :-dynamic populacao/1.
  3. :-dynamic prob_cruzamento/1.
  4. :-dynamic prob_mutacao/1.
  5.  
  6.  
  7. % tarefa(Id,TempoProcessamento,TempConc,PesoPenalizacao).
  8. %tarefa(t1,2,5,1).
  9. %tarefa(t2,4,7,6).
  10. %tarefa(t3,1,11,2).
  11. %tarefa(t4,3,9,3).
  12. %tarefa(t5,3,8,2).
  13. tarefa(t1,65,100,1).
  14. tarefa(t2,36,100,1).
  15. tarefa(t3,65,110,1).
  16. tarefa(t4,36,150,1).
  17. tarefa(t5,48,300,1).
  18.  
  19. % tarefas(NTarefas).
  20. tarefas(5).
  21.  
  22. % Heuristica EDD para tarefas
  23. heuristica_edd(ListaTarefasOrdenadas*Avaliacao):-
  24. findall(Tarefa,tarefa(Tarefa,_,_,_),ListaTarefas),
  25. tconc_tarefa_lista_ordenada(ListaTarefas,ListaTarefasOrdenadas),
  26. avalia(ListaTarefasOrdenadas,Avaliacao).
  27.  
  28. tconc_tarefa_lista_ordenada(ListaTarefas, ListaTarefasOrdenadas):-
  29. maplist(par_valor_tarefa,ListaTarefas,ListaPares),
  30. keysort(ListaPares,ListaParesOrdenados),
  31. pairs_values(ListaParesOrdenados,ListaTarefasOrdenadas).
  32.  
  33. par_valor_tarefa(Tarefa,Tconc-Tarefa):- tarefa(Tarefa,_,Tconc,_).
  34.  
  35. % Heuristica MIN.SLACK para tarefas
  36. heuristica_min_slack(ListaFinal*Avaliacao):-
  37. findall(Valor*Tarefa,(tarefa(Tarefa,Texec,Prazo,_),Valor is Prazo - Texec),ListaTarefas),
  38. calcular_valor(ListaTarefas,0,[],ListaTarefasPesadas),
  39. sort(ListaTarefasPesadas,ListaTarefasOrdenadas),
  40. ListaTarefasOrdenadas = [TarefaInicial|RestoLista],
  41. TarefaInicial = _*Tarefa,
  42. tarefa(Tarefa,Texec,_,_),
  43. heuristica_min_slack2(RestoLista,Texec,[TarefaInicial],ListaParesFinal),
  44. remover_chaves(ListaParesFinal,[],ListaFinal),
  45. avalia(ListaFinal,Avaliacao).
  46.  
  47. heuristica_min_slack2([],_,ListaFinal,ListaFinalReversed):- reverse(ListaFinal,ListaFinalReversed),!.
  48. heuristica_min_slack2(ListaTarefas,TExecAnterior,Lista,ListaFinal):-
  49. calcular_valor(ListaTarefas,TExecAnterior,[],ListaTarefasPesadas),
  50. sort(ListaTarefasPesadas,ListaTarefasOrdenadas),
  51. ListaTarefasOrdenadas = [TarefaInicial|RestoLista],
  52. TarefaInicial = _*Tarefa,
  53. tarefa(Tarefa,Texec,_,_),
  54. TExecAtual is TExecAnterior + Texec,
  55. heuristica_min_slack2(RestoLista,TExecAtual,[TarefaInicial|Lista],ListaFinal).
  56.  
  57. calcular_valor([],_,ListaTarefasPesadas,ListaTarefasPesadas).
  58. calcular_valor([Valor*Tarefa|ListaTarefas],TExecAnterior,ListaTarefasPesadas,ListaFinal):-
  59. tarefa(Tarefa,Texec,Prazo,Peso),
  60. (Valor > 0 -> ValorPesado is (Prazo - Texec - TExecAnterior)* Peso; ValorPesado is (Prazo - Texec - TExecAnterior) / Peso),
  61. calcular_valor(ListaTarefas,TExecAnterior,[ValorPesado*Tarefa|ListaTarefasPesadas],ListaFinal).
  62.  
  63. remover_chaves([],ListaValues, ListaFinal):- reverse(ListaValues,ListaFinal).
  64. remover_chaves([_*Tarefa|ListaPairs],ListaValues, ListaFinal):-
  65. remover_chaves(ListaPairs,[Tarefa|ListaValues], ListaFinal).
  66.  
  67. % parameterizacao
  68. inicializa:-write('Numero de novas Geracoes: '),read(NG),
  69. (retract(geracoes(_));true), asserta(geracoes(NG)),
  70. write('Dimensao da Populacao: '),read(DP),
  71. (retract(populacao(_));true), asserta(populacao(DP)),
  72. write('Probabilidade de Cruzamento (%):'), read(P1),
  73. PC is P1/100,
  74. (retract(prob_cruzamento(_));true),asserta(prob_cruzamento(PC)),
  75. write('Probabilidade de Mutacao (%):'), read(P2),
  76. PM is P2/100,
  77. (retract(prob_mutacao(_));true), asserta(prob_mutacao(PM)).
  78.  
  79.  
  80. gera:-
  81. inicializa,
  82. gera_populacao(Pop),
  83. write('Pop='),write(Pop),nl,
  84. avalia_populacao(Pop,PopAv),
  85. ordena_populacao(PopAv,PopOrd),
  86. write('PopAv='),write(PopOrd),nl,
  87. geracoes(NG),
  88. gera_geracao(0,NG,PopOrd).
  89.  
  90. gera_populacao(Pop):-
  91. populacao(TamPop),
  92. tarefas(NumT),
  93. findall(Tarefa,tarefa(Tarefa,_,_,_),ListaTarefas),
  94. gera_populacao(TamPop - 2,ListaTarefas,NumT,Pop).
  95.  
  96. gera_populacao(0,_,_,[H1,H2]):- gerar_heuristicas_iniciais([H1,H2]),!.
  97.  
  98. gera_populacao(TamPop,ListaTarefas,NumT,[Ind|Resto]):-
  99. TamPop1 is TamPop-1,
  100. gera_populacao(TamPop1,ListaTarefas,NumT,Resto),
  101. gera_individuo(ListaTarefas,NumT,Ind),
  102. not(member(Ind,Resto)).
  103. gera_populacao(TamPop,ListaTarefas,NumT,L):-
  104. gera_populacao(TamPop,ListaTarefas,NumT,L).
  105.  
  106. gera_individuo([G],1,[G]):-!.
  107.  
  108. gera_individuo(ListaTarefas,NumT,[G|Resto]):-
  109. NumTemp is NumT + 1, % To use with random
  110. random(1,NumTemp,N),
  111. retira(N,ListaTarefas,G,NovaLista),
  112. NumT1 is NumT-1,
  113. gera_individuo(NovaLista,NumT1,Resto).
  114.  
  115. retira(1,[G|Resto],G,Resto).
  116. retira(N,[G1|Resto],G,[G1|Resto1]):-
  117. N1 is N-1,
  118. retira(N1,Resto,G,Resto1).
  119.  
  120. avalia_populacao([],[]).
  121. avalia_populacao([Ind|Resto],[Ind*V|Resto1]):-
  122. avalia(Ind,V),
  123. avalia_populacao(Resto,Resto1).
  124.  
  125. avalia(Seq,V):-
  126. avalia(Seq,0,V).
  127.  
  128. avalia([],_,0).
  129. avalia([T|Resto],Inst,V):-
  130. tarefa(T,Dur,Prazo,Pen),
  131. InstFim is Inst+Dur,
  132. avalia(Resto,InstFim,VResto),
  133. ((InstFim =< Prazo,!, VT is 0);
  134. (VT is (InstFim-Prazo)*Pen)),
  135. V is VT+VResto.
  136.  
  137. ordena_populacao(PopAv,PopAvOrd):-
  138. bsort(PopAv,PopAvOrd).
  139.  
  140. bsort([X],[X]):-!.
  141. bsort([X|Xs],Ys):-
  142. bsort(Xs,Zs),
  143. btroca([X|Zs],Ys).
  144.  
  145.  
  146. btroca([X],[X]):-!.
  147.  
  148. btroca([X*VX,Y*VY|L1],[Y*VY|L2]):-
  149. VX>VY,!,
  150. btroca([X*VX|L1],L2).
  151.  
  152. btroca([X|L1],[X|L2]):-btroca(L1,L2).
  153.  
  154.  
  155. gera_geracao(G,G,Pop):-!,
  156. write('Geracao'), write(G), write(':'), nl, write(Pop), nl.
  157.  
  158. gera_geracao(N,G,Pop):-
  159. write('Geracao '), write(N), write(':'), nl, write(Pop), nl,
  160. cruzamento(Pop,NPop1),
  161. mutacao(NPop1,NPop),
  162. avalia_populacao(NPop,NPopAv),
  163. ordena_populacao(NPopAv,NPopOrd),
  164. N1 is N+1,
  165. gera_geracao(N1,G,NPopOrd).
  166.  
  167. gerar_pontos_cruzamento(P1,P2):-
  168. gerar_pontos_cruzamento1(P1,P2).
  169.  
  170. gerar_pontos_cruzamento1(P1,P2):-
  171. tarefas(N),
  172. NTemp is N+1,
  173. random(1,NTemp,P11),
  174. random(1,NTemp,P21),
  175. P11\==P21,!,
  176. ((P11<P21,!,P1=P11,P2=P21);(P1=P21,P2=P11)).
  177. gerar_pontos_cruzamento1(P1,P2):-
  178. gerar_pontos_cruzamento1(P1,P2).
  179.  
  180.  
  181. cruzamento([],[]).
  182. cruzamento([Ind*_],[Ind]).
  183. cruzamento([Ind1*_,Ind2*_|Resto],[NInd1,NInd2|Resto1]):-
  184. gerar_pontos_cruzamento(P1,P2),
  185. prob_cruzamento(Pcruz),random(0.0,1.0,Pc),
  186. ((Pc =< Pcruz,!,
  187. cruzar(Ind1,Ind2,P1,P2,NInd1),
  188. cruzar(Ind2,Ind1,P1,P2,NInd2))
  189. ;
  190. (NInd1=Ind1,NInd2=Ind2)),
  191. cruzamento(Resto,Resto1).
  192.  
  193. preencheh([],[]).
  194.  
  195. preencheh([_|R1],[h|R2]):-
  196. preencheh(R1,R2).
  197.  
  198.  
  199. sublista(L1,I1,I2,L):-
  200. I1 < I2,!,
  201. sublista1(L1,I1,I2,L).
  202.  
  203. sublista(L1,I1,I2,L):-
  204. sublista1(L1,I2,I1,L).
  205.  
  206. sublista1([X|R1],1,1,[X|H]):-!,
  207. preencheh(R1,H).
  208.  
  209. sublista1([X|R1],1,N2,[X|R2]):-!,
  210. N3 is N2 - 1,
  211. sublista1(R1,1,N3,R2).
  212.  
  213. sublista1([_|R1],N1,N2,[h|R2]):-
  214. N3 is N1 - 1,
  215. N4 is N2 - 1,
  216. sublista1(R1,N3,N4,R2).
  217.  
  218. rotate_right(L,K,L1):-
  219. tarefas(N),
  220. T is N - K,
  221. rr(T,L,L1).
  222.  
  223. rr(0,L,L):-!.
  224.  
  225. rr(N,[X|R],R2):-
  226. N1 is N - 1,
  227. append(R,[X],R1),
  228. rr(N1,R1,R2).
  229.  
  230.  
  231. elimina([],_,[]):-!.
  232.  
  233. elimina([X|R1],L,[X|R2]):-
  234. not(member(X,L)),!,
  235. elimina(R1,L,R2).
  236.  
  237. elimina([_|R1],L,R2):-
  238. elimina(R1,L,R2).
  239.  
  240. insere([],L,_,L):-!.
  241. insere([X|R],L,N,L2):-
  242. tarefas(T),
  243. ((N>T,!,N1 is N mod T);N1 = N),
  244. insere1(X,N1,L,L1),
  245. N2 is N + 1,
  246. insere(R,L1,N2,L2).
  247.  
  248.  
  249. insere1(X,1,L,[X|L]):-!.
  250. insere1(X,N,[Y|L],[Y|L1]):-
  251. N1 is N-1,
  252. insere1(X,N1,L,L1).
  253.  
  254. cruzar(Ind1,Ind2,P1,P2,NInd11):-
  255. sublista(Ind1,P1,P2,Sub1),
  256. tarefas(NumT),
  257. R is NumT-P2,
  258. rotate_right(Ind2,R,Ind21),
  259. elimina(Ind21,Sub1,Sub2),
  260. P3 is P2 + 1,
  261. insere(Sub2,Sub1,P3,NInd1),
  262. eliminah(NInd1,NInd11).
  263.  
  264.  
  265. eliminah([],[]).
  266.  
  267. eliminah([h|R1],R2):-!,
  268. eliminah(R1,R2).
  269.  
  270. eliminah([X|R1],[X|R2]):-
  271. eliminah(R1,R2).
  272.  
  273. mutacao([],[]).
  274. mutacao([Ind|Rest],[NInd|Rest1]):-
  275. prob_mutacao(Pmut),
  276. random(0.0,1.0,Pm),
  277. ((Pm < Pmut,!,mutacao1(Ind,NInd));NInd = Ind),
  278. mutacao(Rest,Rest1).
  279.  
  280. mutacao1(Ind,NInd):-
  281. gerar_pontos_cruzamento(P1,P2),
  282. mutacao22(Ind,P1,P2,NInd).
  283.  
  284. mutacao22([G1|Ind],1,P2,[G2|NInd]):-
  285. !, P21 is P2-1,
  286. mutacao23(G1,P21,Ind,G2,NInd).
  287. mutacao22([G|Ind],P1,P2,[G|NInd]):-
  288. P11 is P1-1, P21 is P2-1,
  289. mutacao22(Ind,P11,P21,NInd).
  290.  
  291. mutacao23(G1,1,[G2|Ind],G2,[G1|Ind]):-!.
  292. mutacao23(G1,P,[G|Ind],G2,[G|NInd]):-
  293. P1 is P-1,
  294. mutacao23(G1,P1,Ind,G2,NInd).
  295.  
  296. gerar_heuristicas_iniciais(ListaHeuristicas):-
  297. heuristica_edd(HeuristicaEDD*ValorEDD),
  298. heuristica_min_slack(HeuristicaMinSlack*ValorMinSlack),
  299. (ValorEDD == ValorMinSlack,!,
  300. (swap12(HeuristicaMinSlack,HeuristicaMutada),
  301. ListaHeuristicas = [HeuristicaEDD,HeuristicaMutada]);
  302. (ListaHeuristicas = [HeuristicaEDD,HeuristicaMinSlack])).
  303.  
  304. swap12([X, Y|T], [Y, X|T]).
  305.  
  306. mantem_melhores(_,0,MelhoresFinal,MelhoresFinal).
  307. mantem_melhores([Melhor*_|Pop],Num,MelhoresAnteriores,MelhoresFinal):-
  308. Num1 is Num - 1,
  309. (Num > 0 -> mantem_melhores(Pop, Num1, [Melhor|MelhoresAnteriores], MelhoresFinal)),!.
  310.  
  311. torneios_2a2(Ind1*V1,Ind2*V2,MenorInd*MenorV):-
  312. Max1 is V1/(V1 + V2), random(0,Max1,R1),
  313. Max2 is V2/(V1 + V2), random(0,Max2,R2),
  314. write("R1: "), write(R1),write(" R2: "), write(R2),nl,
  315. (R1 < R2 -> (MenorInd = Ind1, MenorV = V1);(MenorInd = Ind2, MenorV = V2)).
  316.  
  317.  
  318. % Melhor Escalonamento com Tempo de Atraso sem Find All
  319. :- dynamic melhor_sol_to/2.
  320.  
  321. melhor_escalonamento_tempos_atraso_pesados(Lm,Tm):-
  322. get_time(Ti),
  323. findall(Tarefa,tarefa(Tarefa,_,_,_),ListaTarefas),
  324. (melhor_escalonamento_tempos_atraso_pesados1(ListaTarefas);true),
  325. retract(melhor_sol_to(Lm,Tm)),
  326. get_time(Tf),Tcomp is Tf-Ti,
  327. write('GERADO EM '),write(Tcomp),
  328. write(' SEGUNDOS'),nl.
  329.  
  330. melhor_escalonamento_tempos_atraso_pesados1(L):-
  331. asserta(melhor_sol_to(_,10000)),!,
  332. permuta_tempoAtraso(L,LP,Tempo),
  333. update(LP,Tempo),
  334. fail.
  335.  
  336. update(LP,T):- melhor_sol_to(_,Tm),
  337. T<Tm,retract(melhor_sol_to(_,_)),asserta(melhor_sol_to(LP,T)),!.
  338.  
  339. permuta_tempoAtraso(L,LP,Tempo):-
  340. permuta(L,LP),avalia(LP,Tempo).
  341.  
  342. permuta([ ],[ ]).
  343. permuta(L,[X|L1]):-apaga1(X,L,Li),permuta(Li,L1).
  344.  
  345. apaga1(X,[X|L],L).
  346. apaga1(X,[Y|L],[Y|L1]):-apaga1(X,L,L1).
  347.  
  348. melhor_permuta([p(LP,Tempo)],LP,Tempo):-!.
  349. melhor_permuta([p(LP,Tempo)|LL],LPm,Tm):-melhor_permuta(LL,LP1,T1),((Tempo<T1,!,Tm is Tempo,LPm=LP);(Tm is T1,LPm=LP1)).
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!