Uso do Algoritmo Particle Swarm Optimization (PSO) para otimização de prioridades de tarefas.

Thales Eduardo Nazatto

UNIVERSIDADE ESTADUAL PAULISTA“JÚLIO DE MESQUITA FILHO”

CAMPUS DE RIO CLAROSEMINÁRIO DE COMPUTAÇÃO EVOLUTIVA

PROFª Drª ADRIANE BEATRIZ DE SOUZA SERAPIÃO

Computação Evolutiva PSO para otimização de prioridades de tarefas.

2

Índice

Introdução O algoritmo PSO O problema Implementação Procedimentos

Computação Evolutiva PSO para otimização de prioridades de tarefas.

3

Introdução

Computação Evolutiva PSO para otimização de prioridades de tarefas.

4

Introdução

Computação Evolutiva PSO para otimização de prioridades de tarefas.

5

Introdução

Computação Evolutiva PSO para otimização de prioridades de tarefas.

6

Introdução

Computação Evolutiva PSO para otimização de prioridades de tarefas.

7

Introdução

Computação Evolutiva PSO para otimização de prioridades de tarefas.

8

Introdução

Prioridades

Afazeres

Contas

Projetos

Viagens

Urgências

Estudos

Vida social

Dívidas

Tempo

Notícias

Lazer

Acabou?

Falta algo?Mais?

Computação Evolutiva PSO para otimização de prioridades de tarefas.

9

Introdução

Computação Evolutiva PSO para otimização de prioridades de tarefas.

10

Introdução

Em coisas como tarefas, não há um critério bem definido das coisas.

Há critérios que podem influir em outros. Os critérios variam de pessoa para pessoa. A implementação para organização é bastante complexa. Muitos programas simplificam essa organização. Os conceitos usados nos algoritmos evolutivos podem

ajudar a simplificar essa implementação sem simplificar a organização e seus critérios.

Computação Evolutiva PSO para otimização de prioridades de tarefas.

11

O algoritmo PSO

Algoritmo Evolutivo Metaheurístico

Baseado na dinâmica populacional

Criadores: Kennedy e Eberhart (1995)

Produz resultado semelhante aos algoritmos genéticos com uma rapidez bem maior

Computação Evolutiva PSO para otimização de prioridades de tarefas.

12

O algoritmo PSO

Baseado em 2 funções: Veloidade:

Posição:

Computação Evolutiva PSO para otimização de prioridades de tarefas.

13

O algoritmo PSO

Algoritmo: Atualizar pBest e gBest, Calcular novas posições e velocidades e atualizar partículas.

Isso é feito a cada nova geração. (iteração)

O primeiro termo é relacionado a inércia da partícula, o segundo ao fator cognitivo relacionado à atração da partícula ao melhor ponto encontrado e o terceiro ao fator social, que representa a colaboração entre as partículas.

Computação Evolutiva PSO para otimização de prioridades de tarefas.

14

O problema

Dado um número m de tarefas com n variáveis de diferentes domínios, o problema inicial é a formulação de um modelo para organização com a influência de variáveis tão distintas.

As variáveis que influenciam essa organização são (Variável/Domínio):

Prioridade da tarefa – Domínio dos números inteiros

Tempo restante da tarefa – Domínio do tempo / números reais

Tempo esperado da tarefa – Domínio do tempo / números reais

Porcentagem restante para conclusão da tarefa – Domínio dos números reais

Total de horas esperado da tarefa – Domínio do tempo / números reais

Total de horas trabalhadas nesta tarefa – Domínio do tempo / números reais

Computação Evolutiva PSO para otimização de prioridades de tarefas.

15

O problema

Solução: Transformar essas n variáveis em uma função de um único domínio.

Cada variável recebe uma pontuação Xi Є [0,1000] e um peso Pi

Com isso, um St é obtido com a seguinte função:

Nesse caso, n = 6

Computação Evolutiva PSO para otimização de prioridades de tarefas.

16

O problema

Agora, o problema consiste em usar o PSO para ordenar as tarefas tomando St como critério de ordenação.

Computação Evolutiva PSO para otimização de prioridades de tarefas.

17

Implementação

Computador: Core 2 Duo, 2 GB RAM HD 12o GB

SO: Windows 7 IDE: NetBeans 6.8 Linguagem de Implementação: Java

Computação Evolutiva PSO para otimização de prioridades de tarefas.

18

Implementação

Cada tarefa recebe uma pontuação, de acordo com as configurações colocadas.

O PSO é utilizado para achar uma “tarefa ótima” nessa população com base nas pontuações de cada tarefa.

Caso a convergência total não seja alcançada, ela é “forçada” fazendo a média entre as soluções da última geração do PSO.

É calculada a distância entre a pontuação da tarefa ótima e a pontuação de cada tarefa, denominada no sistema por match.

As tarefas são ordenadas com base no match e caso ele seja igual, o fitness é o critério base.

Computação Evolutiva PSO para otimização de prioridades de tarefas.

19

Procedimentos

Foram implementados 4 critérios para gerar bases de dados.

Base 1 – Nenhum critério utilizado. (Base randômica)

Base 2 – Elementos com maior prioridade são menos urgentes.

Base 3 – Elementos com maior prioridade são mais urgentes.

Base 4 – Equilíbrio de urgência entre os elementos.

Cada base foi testada 3 vezes.

Computação Evolutiva PSO para otimização de prioridades de tarefas.

20

Procedimentos

Parâmetros para teste

Computação Evolutiva PSO para otimização de prioridades de tarefas.

21

Procedimentos

Tabela de pontuações de tarefas:Base 1 Base 2 Base 3 Base 4

Teste 1 Teste 2 Teste 3 Teste 1 Teste 2 Teste 3 Teste 1 Teste 2 Teste 3 Teste 1 Teste 2 Teste 3Tarefa ótima 5890,98712 5870,22935 6474,73104 6142,99723 6412,85899 6247,74241 8230,87249 6077,56913 5691,62173 6125,82448 5996,20438 6392,80854

Tarefa 1 5900,67507 5870,95361 6478,16212 6161,17734 6366,06113 6171,64903 8208,42593 6120,98091 5696,65629 6124,90581 5981,43312 6391,16831Tarefa 2 5927,10999 5863,55008 6493,57139 6162,33086 6366,06113 6171,64903 8208,42593 6122,03568 5717,67582 6092,62817 5969,35258 6389,04273Tarefa 3 5888,80043 5849,96248 6427,00938 6162,33086 6366,06113 6348,55379 8208,42593 6122,51118 5717,67582 6081,94113 6026,24889 6384,13733Tarefa 4 5872,30931 5893,40597 6425,63778 6162,32723 6366,06113 6348,55379 8255,37037 6125,07838 5717,67582 6080,07643 6027,71828 6407,42072Tarefa 5 5868,79810 5835,45785 6399,98644 6162,32723 6285,04922 6348,55379 8255,37037 6125,23230 5729,39804 6079,32773 5956,99347 6339,30514Tarefa 6 5864,49129 5917,68784 6379,24693 6162,32723 6285,04922 6348,55379 8186,75926 5996,97156 5653,84541 6175,97636 5952,35224 6330,22064Tarefa 7 5858,43941 5821,80866 6373,67982 6162,32723 6542,49695 6348,55379 8175,03704 5996,91350 5653,84541 6177,39560 5940,25019 6320,75728Tarefa 8 5964,27200 5783,51861 6361,78165 6106,58086 6542,96589 6090,63713 8175,03704 5995,64009 5653,84541 6068,36481 6054,95076 6319,88318Tarefa 9 5839,35575 5770,58545 6359,45736 6106,58086 6196,29922 6090,63713 8175,03704 5994,99421 5653,43075 6063,31632 5937,40692 6314,40908

Tarefa 10 5837,75055 5762,72665 6354,89140 6106,58086 6196,29922 6034,88713 8168,00076 5994,58011 5646,80913 6062,28425 6058,26492 6311,63197Tarefa 11 5837,38851 5756,52067 6344,08917 6073,58086 6196,29922 6034,88713 8163,45569 5950,37696 5646,80913 6056,29332 5925,50438 6307,51400Tarefa 12 5831,75064 5992,98083 6343,31431 6073,58086 6196,29922 5978,74860 8163,45569 5950,37696 5646,26976 6051,99952 6068,03167 6299,50286Tarefa 13 5825,84514 5743,53698 6337,79476 6073,58086 6196,29922 5978,74860 8163,45569 5949,69122 5642,26406 6051,80466 5913,15816 6296,26023Tarefa 14 5819,56391 5737,44597 6331,45927 6050,44234 6173,16069 5978,74860 8163,45569 5916,98807 5639,16331 6050,58197 5912,59870 6282,09050Tarefa 15 5817,98857 5731,74657 6326,97057 6050,44234 6173,16069 5978,74860 8160,35494 5916,98807 5639,16331 6047,92117 5904,19585 6281,29958Tarefa 16 5811,34170 5731,40028 6325,88246 6050,44234 6173,16069 5960,63713 8160,35494 5909,95179 5639,16331 6047,60023 6091,01967 6280,26477Tarefa 17 5808,80705 5729,49549 6325,69333 6243,34277 6155,04922 5960,63713 8160,35494 5905,40672 5636,95652 6044,20792 6091,07287 6279,24288Tarefa 18 5807,12316 5729,48570 6325,37882 6243,34277 6141,29922 5946,88713 8160,35494 5902,30597 5636,95652 6040,14744 5895,74332 6278,67392Tarefa 19 5806,14922 5725,05536 6323,18665 6243,34277 6141,29922 5946,70739 8160,35494 5902,30597 5636,95652 6039,74148 5890,82947 6266,49802Tarefa 20 5803,30392 5724,90110 6319,18809 6032,33086 6141,29922 5945,04606 8160,35494 5900,09918 5636,95652 6032,55586 5889,23630 6528,89736Tarefa 21 5802,55644 5721,85394 6642,06630 6032,33086 7022,03103 6835,97803 8158,14815 5900,09918 5527,71624 6023,12171 5889,10193 6541,57930Tarefa 22 5801,95951 5721,58460 6253,86812 6018,58086 7022,60280 6835,97803 8157,56524 5900,09918 5526,20197 6244,88570 5882,64089 6598,53558Tarefa 23 5801,15460 6062,48915 7204,74205 6018,58086 7025,62933 6835,97803 8389,25926 6777,82027 5858,68579 6323,04328 5878,06819 6600,78920Tarefa 24 6576,48082 6572,58537 7205,29419 6015,38633 7025,67841 6835,97803 8389,25926 6778,57178 5860,36673 6334,51919 6302,63880 6633,25128Tarefa 25 6785,66085 6704,99447 7205,92353 6900,71789 7025,80228 6836,88713 9045,73839 6783,20910 5860,79379 6508,99077 6466,29963 6837,83766

Média 5910,36304 5870,22935 6474,73104 6142,99665 6412,85899 6247,71296 8230,87249 6077,56913 5675,01126 6116,14523 5996,20445 6392,80854Desvio-padrão 237,67281 249,07798 285,60768 173,54059 331,62063 332,95399 181,52386 276,69566 84,23235 118,86179 137,92205 146,76609

Média geral 6085,10781 6267,85620 6661,15096 6168,38607Desvio-padrão geral 376,95916 306,42364 1146,23461 213,75372

Computação Evolutiva PSO para otimização de prioridades de tarefas.

22

Procedimentos

Tabela de match de pontuação:Base 1 Base 2 Base 3 Base 4

Teste 1 Teste 2 Teste 3 Teste 1 Teste 2 Teste 3 Teste 1 Teste 2 Teste 3 Teste 1 Teste 2 Teste 3Tempo de Execução(s) 28 37 33 39 29 33 31 32 36 36 34 53

Tarefa 1 9,67879 0,72426 3,43108 18,18012 46,79786 76,09338 22,44657 43,41178 5,03456 0,91866 14,77126 1,64023Tarefa 2 16,74697 6,67927 18,84036 19,33363 46,79786 76,09338 22,44657 44,46655 26,05409 33,19630 26,85180 3,76581Tarefa 3 21,56259 20,26687 47,72165 19,33363 46,79786 100,81138 22,44657 44,94205 26,05409 43,88335 30,04451 8,67121Tarefa 4 38,05371 23,17662 49,09325 19,33000 46,79786 100,81138 24,49788 47,50925 26,05409 45,74804 31,51389 14,61218Tarefa 5 41,56492 34,77150 74,74460 19,33000 127,80977 100,81138 24,49788 47,66317 37,77631 46,49675 39,21091 53,50340Tarefa 6 45,87173 47,45849 95,48410 19,33000 127,80977 100,81138 44,11323 80,59757 37,77631 50,15189 43,85215 62,58790Tarefa 7 51,92360 48,42068 101,05121 19,33000 129,63796 100,81138 55,83546 80,65564 37,77631 51,57113 55,95419 72,05126Tarefa 8 53,90898 86,71073 112,94939 36,41636 130,10690 157,10528 55,83546 81,92905 37,77631 57,45967 58,74638 72,92535Tarefa 9 71,00726 99,64389 115,27367 36,41636 216,55977 157,10528 55,83546 82,57493 38,19098 62,50815 58,79747 78,39946

Tarefa 10 72,61246 107,50270 119,83963 36,41636 216,55977 212,85528 62,87174 82,98902 44,81260 63,54023 62,06054 81,17656Tarefa 11 72,97451 113,70868 130,64186 69,41636 216,55977 212,85528 67,41681 127,19218 44,81260 69,53116 70,70000 85,29454Tarefa 12 78,61238 122,75148 131,41673 69,41636 216,55977 268,99381 67,41681 127,19218 45,35197 73,82496 71,82728 93,30568Tarefa 13 84,51788 126,69237 136,93628 69,41636 216,55977 268,99381 67,41681 127,87791 49,35766 74,01982 83,04622 96,54831Tarefa 14 90,79953 132,78338 143,27176 92,55489 239,69829 268,99381 67,41681 160,58107 52,45841 75,24251 83,60568 110,71804Tarefa 15 92,37444 138,48277 147,76047 92,55489 239,69829 268,99381 70,51755 160,58107 52,45841 77,90331 92,00853 111,50896Tarefa 16 99,02131 138,82907 148,84857 92,55489 239,69829 287,10528 70,51755 167,61735 52,45841 78,22425 94,81529 112,54377Tarefa 17 101,55597 140,73386 149,03771 100,34554 257,80977 287,10528 70,51755 172,16241 54,66520 81,61656 94,86848 113,56566Tarefa 18 103,23986 140,74365 149,35222 100,34554 271,55977 300,85528 70,51755 175,26316 54,66520 85,67704 100,46106 114,13462Tarefa 19 104,21380 145,17399 151,54439 100,34554 271,55977 301,03502 70,51755 175,26316 54,66520 86,08299 105,37491 126,31052Tarefa 20 107,05909 145,32825 155,54295 110,66636 271,55977 302,69635 70,51755 177,46995 54,66520 93,26862 106,96809 136,08882Tarefa 21 107,80658 148,37541 167,33526 110,66636 609,17204 588,23563 72,72434 177,46995 163,90548 102,70277 107,10246 148,77076Tarefa 22 108,40361 148,64475 220,86292 124,41636 609,74381 588,23563 73,30725 177,46995 165,41975 119,06122 113,56349 205,72704Tarefa 23 109,20822 192,25980 730,01102 124,41636 612,77034 588,23563 158,38677 700,25114 167,06407 197,21880 118,13619 207,98066Tarefa 24 666,11781 702,35602 730,56316 127,61089 612,81942 588,23563 158,38677 701,00265 168,74500 208,69471 306,43442 240,44274Tarefa 25 875,29783 834,76512 731,19250 757,72066 612,94329 589,14472 814,86590 705,63997 169,17207 383,16629 470,09525 445,02912

Média 128,96535 153,87934 190,50987 95,43455 265,37550 275,72098 94,45082 186,79092 66,68681 90,46837 97,63242 111,89210Desvio-padrão 197,89718 193,32451 209,20202 143,62831 191,34719 177,95707 153,81238 200,53891 52,44106 75,49947 95,35843 92,18885

Média geral 157,78486 212,17701 115,97618 99,99763Desvio-padrão geral 199,16020 189,10512 155,81815 87,37612

Computação Evolutiva PSO para otimização de prioridades de tarefas.

23

Procedimentos

Computação Evolutiva PSO para otimização de prioridades de tarefas.

24

Procedimentos

Tabela de variações de desvio padrão:

Base 1 Base 2 Base 3 Base 4Teste 1 Teste 2 Teste 3 Teste 1 Teste 2 Teste 3 Teste 1 Teste 2 Teste 3 Teste 1 Teste 2 Teste 3

Variação dos desvios 39,78 55,75 76,41 29,91 140,27 155 27,71 76,16 31,79 43,36 42,56 54,58Média 57,31 108,39 45,22 46,83

Computação Evolutiva PSO para otimização de prioridades de tarefas.

25

Bibliografia

Poli, R., Kennedy, J., Blackwell, T. (2007); Particle Swarm Optimization – An Overview. Berlin: Springer. p1-8.

Ricardo, R. F., Neto, S. P. Utilização de PSO para otimização de locais candidatos à instalação de antenas. Faculdade de Jaguariúna - FAJ. Disponível em: <http://bibdig.poliseducacional.com.br/document/?down=155>. Acesso em: 07 de jun. De 2011.

Esmin, A. A. A. (2005), Estudo de Aplicação do Algoritmo de Otimização por Enxame de Partícula na Resolução de Problemas de Otimização Ligados ao SEP. UNIFEI – Universidade Federal de Itajubá – Programa de Pós-Graduação em Engenharia Elétrica. Disponível em: <http://adm-net-a.unifei.edu.br/phl/pdf/0030246.pdf>. Acesso em: 07 de jun. De 2011.

Costa, A. A. B., Biazi, E., Vitor, J. F. d. A.. Aplicação da Metaheurística PSO na Identificação de Pontos Influentes por meio da Função de Sensibilidade de Casos, Anais do CNMAC v.2, ISSN 1984-820X. Disponível em: <www.sbmac.org.br/eventos/cnmac/xxxii_cnmac/pdf/320.pdf>. Acesso em: 13 de jun. de 2011.