Evolver 4.0
Introdução ao Uso da
Ferramenta
Prof. Marco Aurélio C. Pacheco
1
Evolver 4.0 - Palisade Corp.


Otimizador Genético Add-in para o Excel
Permite especificar:
–
–
–
–


Operadores Genéticos
Método de Solução (representação, manipulação)
Parâmetros (população, taxas, condição parada, etc)
Visualização de resultados (Evolver Watcher)
Inclui Examples de aplicações e Tutorial
Versão trial (10 dias ou 100 runs) pode ser
obtida no site www.palisade.com
2
Características dos Modelos
Genéticos do Evolver







Reprodução Steady State
Uniform Crossover
Normalização Linear (Rank Based Selection )
Outros Operadores Genéticos e Heurísticos
Retrições: Range, Soft, Hard
Problemas: Minimum, Maximum, Closest_Value To
6 Métodos de Solução (Solving Methods)
3
Interface com Excel

Células do Excel podem ser:
– Ajustáveis (cromossoma):
• conjunto de variáveis (genes), representando uma
solução do problema (cromossoma), cujos conteúdos
serão manipulados e alterados pelo Evolver.
– Função de Avaliação:
• função (Excel) que calcula a avaliação numérica dos
cromossomas.

Diretórios: Dtools
– Evolve32
– Examples
– System
4
Solving Methods


Definem: representação e operadores
Métodos principais:
– Recipe Solving Method
– Order Solving Method
– Grouping Solving Method
Métodos originados a partir dos principais:
– Budget Solving Method
– Project Solving Method
– Schedule Solving Method
5
Recipe Solving method


Método “Receita de Bolo” onde as variáveis
podem ser ajustadas independentemente
umas das outras.
Restrição apenas do domínio: (mín, máx)
Cromossoma
Outros Cromossomas Possíveis
Original
23.472
145
9
65,664
15.344
101
32.44
14,021
37.452
190
7.073
93,572
6
Order Solving Method


Busca a melhor maneira de ordenar os itens
de uma lista.
Valores dos itens devem ser definidos nas
células Excel ajustáveis, antes da execução.
Cromossoma
Outros Possíveis Cromossomas
Original
23.472
145
9
65,664
145
9
65,664
23.472
65,664
145
23.472
9
7
Grouping Solving Method



Usado em problemas que envolvem múltiplas variáveis
para serem arranjadas em grupos.
# grupos = # símbolos diferentes co cromossoma
EX: Agrupar 80 investimentos em 5 carteiras de modo
que o valor das carteiras seja o mais próximo possível.
Investimentos
value
group
$10.992
2
$11.259
$18.993
1
$13.270
4
$19.159
5
$27.999
$4.901
4
5
$14.771
1
3
Group 1 total= $618.934
Group 2 total= $376.397
Group 3 total= $353.789
Group 4 total= $708.995
Group 5 total= $761.152
deviation
$168.697,15 8
Budget Solving Method

Similar ao Recipe com a restrição de que a soma das
variáveis deve se manter constante.
Encontrar a melhor maneira de distribuir o orçamento anual
entre departamentos:
Cromossoma
Outros Possíveis Cromossomas
Original
200
3.5
10
10
93.1
30
100
0.4
223.5
0
-67
67
A soma permanece constante e igual a 223.5.
9
Project Solving Method


Similar ao Order , exceto que certos itens (tarefas)
devem atender a restrições de precedência.
Encontrar a menor rota entre cidades, garantindo
que certas cidades são visitadas antes de outras.
T his
Tow n & Tow n ID
1 Alexander
2 Ambrose
3 Ashley
4 Beach
5 Belden
6 Bismarck
7 Bottineau
8 Bow man
x
10
12
50
6
22
37
40
11
y
42
58
17
30
46
28
55
19
Order
1
2
3
4
5
6
7
8
C o mes after
t o wn t he s e
to Visit
1
3
23
2
4
34
3 23
40
4 14
29
5 32
10
6
25
7 12
24
8
17
t o wns
total:
52365,00
North Dakota Tow n Locations
7
16
8
13
10
Schedule Solving Method


Similar a Grouping, onde tarefas com a mesma
duração são escalonadas em n time blocks
Restrições: 1(with), 2(not with), 3(before), 4(at),
5(not after), 6(not before), 7(not at), 8(after).
Tarefa
5
12
2
7
6
9
Restrição
4
2
3
1
2
3
Tarefa/Time Block
2 5 deve ocorrer no time block 2
8
1
5 7,5 devem ocorre no mesmo block
4 6 não deve ocorrer com 4
11
1
Restrições

Problemas podem envolver restrições nos
valores das variáveis ou no resultado para se
encontrar uma solução viável.

Há 3 tipos de restrições nos valores das células:
– Range: domínio (mín,máx) dos valores das variáveis.
– Hard: devem sempre ser satisfeitas (recalc x trial).
– Soft: desejáveis mas podem ser relaxadas num
compromisso por maior aptidão.
12
Funções Penalty



Restrições Soft podem ser criadas através de
funções que penalizam soluções inválidas.
Função Penalty:
Penalty = f (desvio_do_objetivo)
Se restrição Soft não foi atendida:
Avaliação (cromossoma)= Avaliação - Penalty (se máx)
Avaliação (cromossoma)= Avaliação + Penalty (se mín)

Método Budget contém função penalty intrínseca
para manter a soma das variáveis constante. 13
Exemplo


Investidores desejam minimizar o risco e
maximizar o retorno de investimentos.
Suponha as seguintes escalas:
– Risco entre [0, 1]
– Retorno entre [0,5]

Se ambos igualmente importantes:
– target cell= return - (risk * 5)

Se buscamos investimentos com risco < 0,3:
– If(risk>.3,-1,0) ; */ IF(condition, thenTrue, elseFalse)
 target cell= return - (risk * 5) - 1, se risk  0,3
 target cell= return - (risk * 5)
, se risk  0,3
14
Operadores








Crossover Uniforme
Mutação
Linear Operators
Boundary Mutation
Cauchy Mutation
Non-uniform Mutation
Arithmetic Crossover
Heuristic Crossover
Para o conjunto de operadores selecionado, Evolver
apresenta o desempenho de cada um no log file. 15
Visualização de Resultados

Evolver Watcher
– ferramenta stand-alone com várias funções

Evolver Log
– arquivo com resultados para relatório, comparação
e dados para a re-execução do GA

Status Bar
– best, valores originais, recalcs (total de cálculos do
modelo) e trials (soluções válidas) e tempo

Células Ajustáveis
– valor das variáveis e avaliações (todos ou best)
16
Evolver Watcher


Progress Graph
– best e média da população corrente
Population Settings
– ajuste de taxas de crossover e mutação

Population Bar Graph
– distribuição dos organismos da população (avaliação)

Population Report
– resumo da evolução

Color Table
– diversidade da população (convergência)

Population Chart
– valores dos cromossomas e aptidões
17
Exemplos do Evolver










Advertising Selection
Alphabetize
Assignment of Tasks
Bakery
Budget Allocation
Chemical Equilibrium
Class Scheduler
Code Segmenter
Dakota: Routing With
Constraints
Job Shop Scheduling
B
R
O
R
B
R
S
G
P










Radio Tower Location
Portfolio Balancing
Portfolio Mix
Power Stations
Purchasing
Salesman Problem
Space Navigator
Trader
Transformer
R
Transportation
R
G
B
R
R
O
R
R
R
O
Recipe, Budget, Order, Grouping, Project, Schedule
18