UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” CAMPUS DE RIO CLARO SEMINÁRIO DE COMPUTAÇÃO EVOLUTIVA PROFª Drª ADRIANE BEATRIZ DE SOUZA SERAPIÃO Uso do Algoritmo Particle Swarm Optimization (PSO) para otimização de prioridades de tarefas. Thales Eduardo Nazatto Índice Introdução O algoritmo PSO O problema Implementação Procedimentos Computação Evolutiva PSO para otimização de prioridades de tarefas. 2 Introdução 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 Prioridades Falta algo? Contas Afazeres Urgências Lazer Vida social Dívidas Notícias Acabou? Mais? Projetos Viagens Estudos Tempo Computação Evolutiva PSO para otimização de prioridades de tarefas. 8 Introdução Computação Evolutiva PSO para otimização de prioridades de tarefas. 9 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. 10 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. 11 O algoritmo PSO Baseado em 2 funções: Veloidade: Posição: Computação Evolutiva PSO para otimização de prioridades de tarefas. 12 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. 13 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. 14 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. 15 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. 16 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. 17 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. 18 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. 19 Procedimentos Parâmetros para teste Computação Evolutiva PSO para otimização de prioridades de tarefas. 20 Procedimentos Tabela de pontuações de tarefas: Tarefa ótima Tarefa 1 Tarefa 2 Tarefa 3 Tarefa 4 Tarefa 5 Tarefa 6 Tarefa 7 Tarefa 8 Tarefa 9 Tarefa 10 Tarefa 11 Tarefa 12 Tarefa 13 Tarefa 14 Tarefa 15 Tarefa 16 Tarefa 17 Tarefa 18 Tarefa 19 Tarefa 20 Tarefa 21 Tarefa 22 Tarefa 23 Tarefa 24 Tarefa 25 Média Desvio-padrão Média geral Desvio-padrão geral Teste 1 5890,98712 5900,67507 5927,10999 5888,80043 5872,30931 5868,79810 5864,49129 5858,43941 5964,27200 5839,35575 5837,75055 5837,38851 5831,75064 5825,84514 5819,56391 5817,98857 5811,34170 5808,80705 5807,12316 5806,14922 5803,30392 5802,55644 5801,95951 5801,15460 6576,48082 6785,66085 5910,36304 237,67281 Computação Evolutiva Base 1 Teste 2 5870,22935 5870,95361 5863,55008 5849,96248 5893,40597 5835,45785 5917,68784 5821,80866 5783,51861 5770,58545 5762,72665 5756,52067 5992,98083 5743,53698 5737,44597 5731,74657 5731,40028 5729,49549 5729,48570 5725,05536 5724,90110 5721,85394 5721,58460 6062,48915 6572,58537 6704,99447 5870,22935 249,07798 6085,10781 376,95916 Teste 3 6474,73104 6478,16212 6493,57139 6427,00938 6425,63778 6399,98644 6379,24693 6373,67982 6361,78165 6359,45736 6354,89140 6344,08917 6343,31431 6337,79476 6331,45927 6326,97057 6325,88246 6325,69333 6325,37882 6323,18665 6319,18809 6642,06630 6253,86812 7204,74205 7205,29419 7205,92353 6474,73104 285,60768 Teste 1 6142,99723 6161,17734 6162,33086 6162,33086 6162,32723 6162,32723 6162,32723 6162,32723 6106,58086 6106,58086 6106,58086 6073,58086 6073,58086 6073,58086 6050,44234 6050,44234 6050,44234 6243,34277 6243,34277 6243,34277 6032,33086 6032,33086 6018,58086 6018,58086 6015,38633 6900,71789 6142,99665 173,54059 Base 2 Teste 2 6412,85899 6366,06113 6366,06113 6366,06113 6366,06113 6285,04922 6285,04922 6542,49695 6542,96589 6196,29922 6196,29922 6196,29922 6196,29922 6196,29922 6173,16069 6173,16069 6173,16069 6155,04922 6141,29922 6141,29922 6141,29922 7022,03103 7022,60280 7025,62933 7025,67841 7025,80228 6412,85899 331,62063 6267,85620 306,42364 Teste 3 6247,74241 6171,64903 6171,64903 6348,55379 6348,55379 6348,55379 6348,55379 6348,55379 6090,63713 6090,63713 6034,88713 6034,88713 5978,74860 5978,74860 5978,74860 5978,74860 5960,63713 5960,63713 5946,88713 5946,70739 5945,04606 6835,97803 6835,97803 6835,97803 6835,97803 6836,88713 6247,71296 332,95399 Teste 1 8230,87249 8208,42593 8208,42593 8208,42593 8255,37037 8255,37037 8186,75926 8175,03704 8175,03704 8175,03704 8168,00076 8163,45569 8163,45569 8163,45569 8163,45569 8160,35494 8160,35494 8160,35494 8160,35494 8160,35494 8160,35494 8158,14815 8157,56524 8389,25926 8389,25926 9045,73839 8230,87249 181,52386 Base 3 Teste 2 6077,56913 6120,98091 6122,03568 6122,51118 6125,07838 6125,23230 5996,97156 5996,91350 5995,64009 5994,99421 5994,58011 5950,37696 5950,37696 5949,69122 5916,98807 5916,98807 5909,95179 5905,40672 5902,30597 5902,30597 5900,09918 5900,09918 5900,09918 6777,82027 6778,57178 6783,20910 6077,56913 276,69566 6661,15096 1146,23461 PSO para otimização de prioridades de tarefas. Teste 3 5691,62173 5696,65629 5717,67582 5717,67582 5717,67582 5729,39804 5653,84541 5653,84541 5653,84541 5653,43075 5646,80913 5646,80913 5646,26976 5642,26406 5639,16331 5639,16331 5639,16331 5636,95652 5636,95652 5636,95652 5636,95652 5527,71624 5526,20197 5858,68579 5860,36673 5860,79379 5675,01126 84,23235 Teste 1 6125,82448 6124,90581 6092,62817 6081,94113 6080,07643 6079,32773 6175,97636 6177,39560 6068,36481 6063,31632 6062,28425 6056,29332 6051,99952 6051,80466 6050,58197 6047,92117 6047,60023 6044,20792 6040,14744 6039,74148 6032,55586 6023,12171 6244,88570 6323,04328 6334,51919 6508,99077 6116,14523 118,86179 Base 4 Teste 2 5996,20438 5981,43312 5969,35258 6026,24889 6027,71828 5956,99347 5952,35224 5940,25019 6054,95076 5937,40692 6058,26492 5925,50438 6068,03167 5913,15816 5912,59870 5904,19585 6091,01967 6091,07287 5895,74332 5890,82947 5889,23630 5889,10193 5882,64089 5878,06819 6302,63880 6466,29963 5996,20445 137,92205 6168,38607 213,75372 Teste 3 6392,80854 6391,16831 6389,04273 6384,13733 6407,42072 6339,30514 6330,22064 6320,75728 6319,88318 6314,40908 6311,63197 6307,51400 6299,50286 6296,26023 6282,09050 6281,29958 6280,26477 6279,24288 6278,67392 6266,49802 6528,89736 6541,57930 6598,53558 6600,78920 6633,25128 6837,83766 6392,80854 146,76609 21 Procedimentos Tabela de match de pontuação: Tempo de Execução(s) Tarefa 1 Tarefa 2 Tarefa 3 Tarefa 4 Tarefa 5 Tarefa 6 Tarefa 7 Tarefa 8 Tarefa 9 Tarefa 10 Tarefa 11 Tarefa 12 Tarefa 13 Tarefa 14 Tarefa 15 Tarefa 16 Tarefa 17 Tarefa 18 Tarefa 19 Tarefa 20 Tarefa 21 Tarefa 22 Tarefa 23 Tarefa 24 Tarefa 25 Média Desvio-padrão Média geral Desvio-padrão geral Teste 1 28 9,67879 16,74697 21,56259 38,05371 41,56492 45,87173 51,92360 53,90898 71,00726 72,61246 72,97451 78,61238 84,51788 90,79953 92,37444 99,02131 101,55597 103,23986 104,21380 107,05909 107,80658 108,40361 109,20822 666,11781 875,29783 128,96535 197,89718 Computação Evolutiva Base 1 Teste 2 37 0,72426 6,67927 20,26687 23,17662 34,77150 47,45849 48,42068 86,71073 99,64389 107,50270 113,70868 122,75148 126,69237 132,78338 138,48277 138,82907 140,73386 140,74365 145,17399 145,32825 148,37541 148,64475 192,25980 702,35602 834,76512 153,87934 193,32451 157,78486 199,16020 Teste 3 33 3,43108 18,84036 47,72165 49,09325 74,74460 95,48410 101,05121 112,94939 115,27367 119,83963 130,64186 131,41673 136,93628 143,27176 147,76047 148,84857 149,03771 149,35222 151,54439 155,54295 167,33526 220,86292 730,01102 730,56316 731,19250 190,50987 209,20202 Teste 1 39 18,18012 19,33363 19,33363 19,33000 19,33000 19,33000 19,33000 36,41636 36,41636 36,41636 69,41636 69,41636 69,41636 92,55489 92,55489 92,55489 100,34554 100,34554 100,34554 110,66636 110,66636 124,41636 124,41636 127,61089 757,72066 95,43455 143,62831 Base 2 Teste 2 29 46,79786 46,79786 46,79786 46,79786 127,80977 127,80977 129,63796 130,10690 216,55977 216,55977 216,55977 216,55977 216,55977 239,69829 239,69829 239,69829 257,80977 271,55977 271,55977 271,55977 609,17204 609,74381 612,77034 612,81942 612,94329 265,37550 191,34719 212,17701 189,10512 Teste 3 33 76,09338 76,09338 100,81138 100,81138 100,81138 100,81138 100,81138 157,10528 157,10528 212,85528 212,85528 268,99381 268,99381 268,99381 268,99381 287,10528 287,10528 300,85528 301,03502 302,69635 588,23563 588,23563 588,23563 588,23563 589,14472 275,72098 177,95707 Teste 1 31 22,44657 22,44657 22,44657 24,49788 24,49788 44,11323 55,83546 55,83546 55,83546 62,87174 67,41681 67,41681 67,41681 67,41681 70,51755 70,51755 70,51755 70,51755 70,51755 70,51755 72,72434 73,30725 158,38677 158,38677 814,86590 94,45082 153,81238 Base 3 Teste 2 32 43,41178 44,46655 44,94205 47,50925 47,66317 80,59757 80,65564 81,92905 82,57493 82,98902 127,19218 127,19218 127,87791 160,58107 160,58107 167,61735 172,16241 175,26316 175,26316 177,46995 177,46995 177,46995 700,25114 701,00265 705,63997 186,79092 200,53891 115,97618 155,81815 PSO para otimização de prioridades de tarefas. Teste 3 36 5,03456 26,05409 26,05409 26,05409 37,77631 37,77631 37,77631 37,77631 38,19098 44,81260 44,81260 45,35197 49,35766 52,45841 52,45841 52,45841 54,66520 54,66520 54,66520 54,66520 163,90548 165,41975 167,06407 168,74500 169,17207 66,68681 52,44106 Teste 1 36 0,91866 33,19630 43,88335 45,74804 46,49675 50,15189 51,57113 57,45967 62,50815 63,54023 69,53116 73,82496 74,01982 75,24251 77,90331 78,22425 81,61656 85,67704 86,08299 93,26862 102,70277 119,06122 197,21880 208,69471 383,16629 90,46837 75,49947 Base 4 Teste 2 34 14,77126 26,85180 30,04451 31,51389 39,21091 43,85215 55,95419 58,74638 58,79747 62,06054 70,70000 71,82728 83,04622 83,60568 92,00853 94,81529 94,86848 100,46106 105,37491 106,96809 107,10246 113,56349 118,13619 306,43442 470,09525 97,63242 95,35843 99,99763 87,37612 Teste 3 53 1,64023 3,76581 8,67121 14,61218 53,50340 62,58790 72,05126 72,92535 78,39946 81,17656 85,29454 93,30568 96,54831 110,71804 111,50896 112,54377 113,56566 114,13462 126,31052 136,08882 148,77076 205,72704 207,98066 240,44274 445,02912 111,89210 92,18885 22 Procedimentos Computação Evolutiva PSO para otimização de prioridades de tarefas. 23 Procedimentos Tabela de variações de desvio padrão: Variação dos desvios Média Teste 1 39,78 Computação Evolutiva Base 1 Teste 2 55,75 57,31 Teste 3 76,41 Teste 1 29,91 Base 2 Teste 2 140,27 108,39 Teste 3 155 Teste 1 27,71 Base 3 Teste 2 76,16 45,22 PSO para otimização de prioridades de tarefas. Teste 3 31,79 Teste 1 43,36 Base 4 Teste 2 42,56 46,83 Teste 3 54,58 24 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. Computação Evolutiva PSO para otimização de prioridades de tarefas. 25
Download
