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