Aplicação de Algoritmos Genéticos na Otimização de Contratos de

Transcrição

Nota Técnica em Inteligência Computacional, ICA, PUC-Rio
1
Aplicação de Algoritmos Genéticos na Otimização de Contratos de
Demanda de Energia Elétrica
Marco Aurélio C. Pacheco1, José Eduardo N. da Rocha,2
1
ICA: Laboratório de Inteligência Computacional,
Departamento de Engenharia Elétrica, PUC-Rio
R. Marques de S. Vicente 225, Gávea, Rio de Janeiro, CEP 22453-900, RJ, Brasil
{marco, jerocha}@ele.puc-rio.br
2 Light Serviços de Eletricidade S/A
Gerência de Sistemas Comerciais,
Praia do Flamengo, 66-A, Flamengo, Rio de Janeiro, CEP 22228-900, RJ, Brasil
[email protected]
Resumo. Para os clientes supridos em Média Tensão ( >= 1kV e < 138 kV) e Alta Tensão ( >= 138 kV), o
valor contratado de Demanda de Energia Elétrica (kW) com a concessionária, é um dos fatores
determinantes do valor final da fatura mensal. A escolha precisa da alternativa tarifária e dos valores
contratados de Demanda de Energia Elétrica deverão ser de forma que a energia requerida esteja
disponível, sem ônus adicionais, e o valor do faturamento seja o mínimo possível. O objetivo deste estudo
é achar a alternativa tarifária ótima utilizando técnicas de algoritmos genético.
Abstract. For clients supplied in Medium Tension ( >= 1kV e < 138 kV) and High Tension ( >= 138 kV),
the Power Energy (kW) contract is one of the most important factor for monthly billing total note. The
precise evaluation of the tariffs alternatives and Power Energy (kW) contracts, must attend the required
energy and, at the same time, lead to minimal billing value. The main objective of this paper is to explore
the optimal tariff alternative using Genetic Algorithms techniques.
palavras-chave: alternativas tarifárias, otimização, minimização.
1. Introdução
Este trabalho apresenta um estudo sobre a utilização de Algoritmos Genéticos na
otimização de contratos de Demanda de Energia Elétrica, celebrados entre o cliente e a
concessionária, visando garantir a disponibilidade da energia contratada, minimizando
os custos no faturamento para o cliente e otimizando o planejamento dos Sistemas
Elétricos de Distribuição da concessionária.
O GA deverá encontrar a melhor alternativa tarifária (convencional ou horo-sazonal)
que garantam as condições acima identificadas.
2
2. O Problema das Demandas Contratuais de Energia Elétrica
O valor contratado de Demanda de Energia Elétrica com a concessionária deverá ser o
mais próximo possível do valor médio requerido, ao longo do tempo, pelas cargas da
unidade consumidora. Quando o valor máximo demandado de energia elétrica supera o
valor contratual do segmento, o valor do excedente de demanda sofre uma tarifação
onerosa de ultrapassagem contratual (Tabela 1).
Tarifas
Demanda
Ultrapassagem
Demanda
Ultrapassagem
Demanda
Ultrapassagem
Período
Único
Período Único
Ponta
Ponta
Fora
Ponta
Fora Ponta
Convencional
1.00
3.00
-- x --
-- x --
-- x --
-- x --
Azul
-- x --
-- x --
2.65
7.95
0.88
2.65
Verde
0.88
2.65
-- x --
-- x --
-- x --
-- x --
Tabela 1 – Tarifas Normalizadas
A análise periódica do comportamento da curva de carga da unidade consumidora, a
partir de seus dados históricos de demanda medida de energia elétrica, são a base de
avaliação para o ajuste ótimo da alternativa tarifária e contratual de demanda.
Na figura 1 podemos simular a contratação de três Demandas (C1, C2 e C3). Em
função dos níveis de carga requeridos, a mesma energia demandada resultará em
diferentes valores faturados. Toda a energia que exceder o limite contratual é
penalizada com uma tarifa de ultrapassagem.
3
Figura 1 – Curva de Carga e simulação de Demandas Contratadas
3. Aplicação de Algoritmos Genéticos
Algoritmos Genéticos são métodos de busca estocásticos que emulam teorias
evolucionárias biológicas para solucionar problemas de otimização, compreendendo um
conjunto de elementos individuais (a população) e um conjunto de operadores
biologicamente inspirados definidos sobre a própria população. De acordo com as
teorias evolucionárias, somente os elementos mais adequados em uma população, têm
maior probabilidade de sobrevivência e geram descendentes, assim transmitindo sua
identidade biológica hereditária às novas gerações. Em termos computacionais, um
algoritmo genético mapeia um problema em um conjunto (tipicamente) de palavras
binárias, manipulando as mais promissoras em busca de soluções melhoradas. A Figura
2 mostra a estrutura de um Algoritmo Genético básico.
início
inicialização da
população
cálculo da aptidão
solução
encontrada
?
Sim
Não
seleção
reprodução
mutação
Figura 2 – Estrutura básica de um Algoritmo Genético
fim
4
5
3.1 Inicialização da População
Uma vez conhecidos os valores mínimos e máximos das curvas de carga típicas das
unidades consumidoras, a população é inicializada com valores aleatórios entre os dois
limites.
3.2 Codificação
A codificação da população é binária.
Uma vez que o espaço de busca representado pelos limites máximo e mínimo é da
ordem de 3 x 104 e a precisão desejada é 10-1 temos que adotar codificação binária de
19 dígitos.
Para representar os três tipos possíveis de contrato temos uma representação binária de
2 dígitos.
Assim sendo, para representar um tipo de contrato e dois valores de demanda (ponta e
fora ponta), temos um cromossomo de 40 dígitos binários. (Figura 3)
Figura 3 – Representação do Cromossomo
3.3 Função de Avaliação
A função de avaliação é a função objetiva, e provém o mecanismo para avaliar o
indivíduo da população, atribuindo o conceito para cada solução potencial. Como nosso
problema é de minimização, quanto menor o valor da função objetiva, maiores serão as
chances do indivíduo sobreviver e reproduzir-se.
F
=
∑ (DPi * TDPi + CPi * TCPi + DFi * TDFi + CFi * TCFi)
j
Onde :
DP = Demanda Faturada Ponta (kW)
DF = Demanda Faturada Fora de Ponta (kW)
CP = Consumo Ponta (kWh)
CF = Consumo Fora Ponta (kWh)
TDP, TDF, TCP e TCF = Tarifas de cada segmento
j = Meses de Avaliação
6
Neste estudo utilizaremos a técnica de aptidão de Normalização linear com o objetivo
de aumentar a competição nos grupos de indivíduos com avaliação próxima.
3.4 Seleção
O mecanismo de seleção modela o mecanismo natural de sobrevivência do indivíduo
mais apto. Assim sendo, as soluções inaptas tendem a desaparecer. No esquema de
seleção proporcional, um indivíduo com maior aptidão têm maior probabilidade de
sobrevivência. Utilizamos a Regra da Roleta para seleção, onde cada indivíduo é
alocado a um setor da roleta virtual ocupando uma área proporcional à sua aptidão
(Figura 4).
Figura 4 – Regra da Roleta
3.5 Crossover (Reprodução)
Depois da seleção de genitores, ocorre o processo de crossover que consiste na
recombinação de material genético entre indivíduos da população. Pares de indivíduos
são escolhidos aleatoriamente na população, e é feita a troca de fragmentos entre os
pares de genitores, a partir de um ponto de cruzamento aleatoriamente escolhido em
cada cromossomo (Figura 5).
7
Figura 5 – Operador de Crossover de um ponto
3.6 Mutação
Após o crossover, os novos indivíduos estão sujeitos à mutação. Esta consiste em
selecionarmos aleatoriamente um gene em um cromossomo e alterar seu valor para um
outro alelo possível. No caso de representação binária, o valor do gene sorteado é
alterado, de “0” para “1”, ou vice-versa. O processo é controlado por um parâmetro fixo,
que indica a probabilidade de um gene sofrer mutação.
A mutação é um operador genético que tem a finalidade de restaurar material genético
perdido. (Figura 6)
Figura 6 – Operador de Mutação
3.7 Elitismo
Baseia-se na idéia de garantir a sobrevivência do indivíduo mais apto. Copia-se o
cromossomo mais apto para a próxima geração.
8
4. Resultados
A implementação do algoritmo genético usado nos experimentos foi feita em linguagem
C++. A listagem do código fonte é disponibilizada no Anexo 1.
Verifica-se que, sem elitismo e sem normalização linear, o algoritmo genético não
consegue convergir para a solução ótima, dentro do limite de 40 gerações. Mesmo
alterando-se os parâmetros de controle (tamanho da população, probabilidade de
crossover e mutação), não se obteve uma melhoria significativa. Todavia, quando se usa
normalização linear e elitismo, o Algoritmo Genético tem sua performance melhorada
consideravelmente, convergindo para o mínimo global desejado com extrema rapidez
(menos de 15 gerações).
A seguir apresentamos os gráficos resultantes da média dos melhores indivíduos a cada
geração para todos experimentos. (Figura 7).
Figura 7.a – Implementação de Algoritmo Genético sem normalização linear / elitismo.
9
Figura 7.b – Implementação de Algoritmo Genético com normalização linear.
Figura 7.c – Implementação de Algoritmo Genético com normalização linear e elitismo.
5. Conclusões
Os resultados obtidos neste trabalho confirmam a aplicabilidade de Algoritmos
Genéticos nos problemas de otimização.
Devido a excelente performance alcançada, a implementação estudada poderá ser
utilizada em processamento de lote (batch processing) em uma base de dados de
unidades consumidoras, visando a otimização individual de Contratos de Demanda de
Energia Elétrica.
6. Referências
D. GoldBerg,
Genetic Algorithm in Search, Optimozation and Machine Learning.
Addison-Wesley, (1989) .
Z. Michalewickz,
Genetic Algorithms + Data Structures = Evolution Programs.
Springer-Verlag (1994).
Marco Aurélio Pacheco,
Notas de Aula em Computação Evolucionária
www.ica.ele.puc-rio.br - (2001).
10
11
ANEXO 1 – Código Fonte
//--------------------------------------------------------------------------#include <vcl.h>
#pragma hdrstop
#include "Unit2.h"
//--------------------------------------------------------------------------#pragma package(smart_init)
#pragma resource "*.dfm"
TForm2 *Form2;
/* estrutura que armazena um individuo da populacao:
.value_c: armazena o valor do tipo de contrato
.value_x: armazena o valor do número real do contrato de ponta
.value_y: armazena o valor do número real do contrato fora de ponta
.string:
armazena o cromossoma do individuo
.string_c: armazena o gene do tipo de contrato
.string_x: armazena o gene da coordenada x do individuo
.string_y: armazena o gene da coordenada y do individuo
.fitness: armazena a fitness do individuo */
struct population
{
int
value_c;
double
value_x;
double
value_y;
unsigned char
string_c[2];
unsigned char string_x[(CHROM_LENGTH-2)/2];
coordenada x */
/* a primeira metade do cromossoma representa a
unsigned char string_y[(CHROM_LENGTH-2)/2];
coordenada y */
/* a segunda metade do cromossoma representa a
unsigned char
double
};
string[CHROM_LENGTH];
fitness;
/* o cromossoma inteiro */
double bestid [100] [100];
/* estruturas de armazenamento da populacao:
'pool' armazena a populacao corrente, enquanto que 'new_pool' armazena
os novos individuos criados a cada geracao; ao fim de cada geracao, os
novos individuos sao copiados de volta para 'pool' */
struct population pool[10000];
struct population new_pool[10000];
/* armazena os indices dos indivuos selecionados para reproducao */
int selected[100000];
/* parâmetros do GA */
int minimo, maximo, popsize, rodadas;
double pcross, pmut;
/* contador do numero de geracoes */
int generations;
double best [100];
int maxgen;
/* Tarifas */
double TDCT, TDAP, TDAF, TDVT, TCCT, TCAP, TCAF, TCVP, TCVF;
/*Medidas elétricas da Unidade Consumidora - Demanda e Consumo */
/* T = todos os períodos ou período único
P = Ponta
F = Fora da Ponta */
12
double DT_1, DT_2, DT_3, DT_4, DT_5, DT_6,
DT_7, DT_8, DT_9, DT_10, DT_11, DT_12;
double DP_1, DP_2, DP_3, DP_4, DP_5, DP_6,
DP_7, DP_8, DP_9, DP_10, DP_11, DP_12;
double DF_1, DF_2, DF_3, DF_4, DF_5, DF_6,
DF_7, DF_8, DF_9, DF_10, DF_11, DF_12;
double CT_1, CT_2, CT_3, CT_4, CT_5, CT_6,
CT_7, CT_8, CT_9, CT_10, CT_11, CT_12;
double CP_1, CP_2, CP_3, CP_4, CP_5, CP_6,
CP_7, CP_8, CP_9, CP_10, CP_11, CP_12;
double CF_1, CF_2, CF_3, CF_4, CF_5, CF_6,
CF_7, CF_8, CF_9, CF_10, CF_11, CF_12;
//--------------------------------------------------------------------------__fastcall TForm2::TForm2(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------void __fastcall TForm2::FormCreate(TObject *Sender)
{
Query1->Open();
}
//----------------------------------------------------------------------------
void __fastcall TForm2::RadioGroup1Click(TObject *Sender)
{
if ((RadioGroup1->Items->Strings[RadioGroup1->ItemIndex] == "normalização")||
13
(RadioGroup1->Items->Strings[RadioGroup1->ItemIndex] == "elitismo"))
{
Edit1->Enabled = true;
Edit2->Enabled = true;
}
else
{
Edit1->Enabled = false;
Edit2->Enabled = false;
}
}
//---------------------------------------------------------------------------
void __fastcall TForm2::Button2Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
{
int i, j, k, n;
double sum_fitness, avg_fitness, old_avg_fitness;
unsigned char temp_string[CHROM_LENGTH];
FILE *file, *fileb;
int flip(double);
void encode_c(int,int);
void encode_x(int, int);
void encode_y(int, int);
14
void join_xy(int);
void split_xy(int);
int decode_c(int);
double decode_x(int);
double decode_y(int);
double evaluate(int, double, double);
void initialize_population(void);
int select(double);
void crossover (int, int, int, int);
void mutation(void);
double normalize(struct population []);
void statistics(FILE *, double);
void pcrom(FILE *, int);
minimo = StrToInt(Edit1 -> Text);
maximo = StrToInt(Edit2 -> Text);
popsize = StrToInt(Edit3 -> Text);
pcross = StrToFloat(Edit5 -> Text);
pmut = StrToFloat(Edit6 -> Text);
rodadas = StrToInt(Edit7 -> Text);
maxgen = StrToInt(Edit8 -> Text);
/* Tarifas */
TDAP = StrToFloat(Edit10 -> Text);
TDAF = StrToFloat(Edit11 -> Text);
TDCT = StrToFloat(Edit4 -> Text);
TDVT = StrToFloat(Edit9 -> Text);
TCCT = StrToFloat(Edit13 -> Text);
TCAP = StrToFloat(Edit14 -> Text);
TCAF = StrToFloat(Edit15 -> Text);
TCVP = StrToFloat(Edit16 -> Text);
15
TCVF = StrToFloat(Edit17 -> Text);
/* Dados Históricos da UC
DT_12 = StrToFloat(EditDT_12 -> Text); */
DT_12 = Query1->Fields[4]->AsFloat;
DP_12 = Query1->Fields[5]->AsFloat;
DF_12 = Query1->Fields[6]->AsFloat;
CT_12 = Query1->Fields[7]->AsFloat;
CP_12 = Query1->Fields[8]->AsFloat;
CF_12 = Query1->Fields[9]->AsFloat;
16
17
/* construtor do objeto Gráfico */
TFastLineSeries *ga = new TFastLineSeries(this);
/* parametriza a barra de progresso */
18
ProgressBar1->Max = popsize*maxgen;
ProgressBar1->Position = 0;
ProgressBar1->Step = popsize;
/* abre o arquivo x2.txt, onde serao logadas as estatisticas do GA */
file = fopen("ga3.txt", "wt");
if (!file)
return;
/* abre o arquivo best.txt, onde será armazenado o melhor cromossoma de cada geração */
fileb = fopen("bga3.txt", "wt");
if (!fileb)
return;
/* estabelece a semente do gerador de numeros aleatorios (necessario antes
de se chamar rand() pela primeira vez) */
randomize();
for (n=0; n<rodadas; n++)
{
generations = 0;
avg_fitness = 1;
/* inicializa a populacao */
initialize_population();
fprintf(fileb, "\n\nRodada: %d\n", n+1);
do
{
Label9->Caption = IntToStr(n+1)+"
";
Label9->Refresh();
Label11->Caption = IntToStr(generations+1)+"
";
19
20
Label11->Refresh();
ProgressBar1->StepIt();
sum_fitness = 0;
old_avg_fitness = avg_fitness;
bestid [n] [generations] = 1000000000;
/* calcula avaliacao e fitness da populacao inteira */
for (i=0; i<popsize; i++)
{
pool[i].value_c = decode_c(i); /* Decodifica o tipo do contrato do individuo [i] */
pool[i].value_x = decode_x(i); /* Decodifica a coordenada x do individuo [i] */
pool[i].value_y = decode_y(i); /* Decodifica a coordenada y do individuo [i] */
pool[i].fitness = evaluate(pool[i].value_c, pool[i].value_x, pool[i].value_y); /* Avalia o individuo [i]
if (pool[i].fitness < bestid [n] [generations])
/* Guarda o melhor cromossoma */
{
bestid [n] [generations] = pool[i].fitness;
k = i;
Label13->Caption = FloatToStr(bestid [n] [generations])+"
";
Label13->Refresh();
}
sum_fitness +=pool[i].fitness;
}
/* normalização linear */
if ((RadioGroup1->Items->Strings[RadioGroup1->ItemIndex] == "normalização")||
(RadioGroup1->Items->Strings[RadioGroup1->ItemIndex] == "elitismo"))
{
sum_fitness = normalize(pool);
k = 0;
*/
}
/* copia o melhor indivíduo para a próxima geração */
for (j=0; j < CHROM_LENGTH; j++)
temp_string[j] = pool[k].string[j];
/* grava no arquivo o melhor cromossoma da geração */
pcrom(fileb, k);
avg_fitness = sum_fitness / popsize;
/* seleciona os individuos para reproducao */
for (i=0; i<popsize; i++)
selected[i] = select(sum_fitness);
/* realiza crossover entre os pares, sendo cada par (os pais) definido por
selected[i] e selected[i+1]; os filhos gerados serao armazenados na
estrutura 'new_pool' na posicao indicada por i e i+1 */
for (i=0; i<popsize; i=i+2)
crossover(selected[i],selected[i+1],i,i+1);
/* realiza mutacao sobre os individuos que acabaram de ser gerados,
copiando-os entao de 'new_pool' de volta para 'pool' */
mutation();
/* elitismo - copia o melhor cromossoma da geração anterior */
if (RadioGroup1->Items->Strings[RadioGroup1->ItemIndex] == "elitismo")
{
pool[popsize - 1].string[j] = temp_string[j];
split_xy(popsize - 1);
21
}
/* imprime estatisticas sobre o andamento do GA */
statistics(file, avg_fitness/old_avg_fitness);
}
while (++generations < maxgen);
/* fecha os arquivos de saida */
}
/* Acha a média da aptidão do melhor indivíduo a cada rodada de cada geração*/
for (i=0;i<maxgen;i++)
{
best[i] = 0;
for (j=0;j<rodadas;j++)
best[i] += (bestid[j] [i] / rodadas);
fprintf(fileb, "\n%f", best[i]);
}
fclose(file);
fclose(fileb);
/* Traça o gráfico do GA */
if (CheckBox1->Checked)
Chart1->RemoveAllSeries();
Chart1->Title->Text->Clear();
Chart1->Title->Text-> Add("Comparação");
Chart1->Title->Text-> Add("GA1 - GA2 - GA3");
ga->ParentChart = Chart1;
ga->AddArray(best,maxgen-1);
if (RadioGroup1->Items->Strings[RadioGroup1->ItemIndex] == "nenhum")
22
{
ga->SeriesColor = clBlue;
ga->Title = "GA1";
ga->ShowInLegend = true;
}
else
if (RadioGroup1->Items->Strings[RadioGroup1->ItemIndex] == "normalização")
{
ga->SeriesColor = clRed;
ga->Title = "GA2";
}
else
{
ga->SeriesColor = clGreen;
ga->Title = "GA3";
}
for ( int i = popsize; i < maxgen*popsize+1; i=i+popsize )
ga->XLabel[(i /popsize)-1] = i;
ProgressBar1->Position = 0;
}
//---------------------------------------------------------------------------
/*
******************************************
*
*
flip
*
Toss a biased coin
*
23
******************************************
*/
/* se um numero aleatorio [i] for menor que o numero contido em prob, ou prob
/* igual a 1, entao a funcao flip retorna verdadeiro(1), caso contrario falso(0) */
int flip(double prob)
{
double i;
i=((double)rand())/RAND_MAX;
if ((prob == 1.0) || (i < prob))
return (1);
else
return (0);
}
/*
******************************************
*
encode_c
*
* Code a integer into binary string
*
******************************************
*/
void encode_c(int index, int value)
{
int i;
/* E' recebido um indice que indica a que individuo estamos nos referenciando
e o valor que sera codificado numa string binaria. Entao para codificar este
valor e' necessario shiftar o valor fornecido por [i], obtendo-se entao um bit */
*/
24
for (i=0; i < 2; i++)
/* este bit e' colocado na estrutura s */
pool[index].string_c[1-i] = (value >> i) & 0x01;
}
/*
******************************************
*
encode_x
*
*
******************************************
*/
void encode_x(int index, int value)
{
int i;
for (i=0; i < ((CHROM_LENGTH-2)/2); i++)
pool[index].string_x[((CHROM_LENGTH-2)/2)-1-i] = (value >> i) & 0x01; /* coordenada x */
}
/*
******************************************
*
encode_y
*
*
******************************************
*/
void encode_y(int index, int value)
{
int i;
25
pool[index].string_y[((CHROM_LENGTH-2)/2)-1-i] = (value >> i) & 0x01; /* coordenada y */
}
/*
*******************************************************************************
*
join_xy
*
* Junta o tipo de contrato e as duas partes x e y em um único cromossoma
*
*******************************************************************************
*/
void join_xy(int index)
{
int i;
for (i=0; i < 2; i++)
/* tipo de contrato - 2 bits */
pool[index].string[1-i] = pool[index].string_c[1-i];
{
pool[index].string[(CHROM_LENGTH/2)-i] = pool[index].string_x[((CHROM_LENGTH-2)/2)-1-i];
pool[index].string[(CHROM_LENGTH)-1-i] = pool[index].string_y[((CHROM_LENGTH-2)/2)-1-i];
}
}
/*
26
*******************************************************************************
*
split_xy
*
* Separa o tipo de contrato e as duas partes x e y de um único cromossoma
*
*******************************************************************************
*/
void split_xy(int index)
{
int i;
for (i=0; i < 2; i++)
/* tipo de contrato - 2 bits */
pool[index].string_c[1-i] = pool[index].string[1-i];
{
pool[index].string_x[(CHROM_LENGTH/2)-1-i] = pool[index].string[(CHROM_LENGTH/2)-i];
pool[index].string_y[(CHROM_LENGTH/2)-1-i] = pool[index].string[(CHROM_LENGTH)-1-i];
}
}
/*
******************************************
*
decode_c
*
* Decode a binary string into an integer *
******************************************
*/
int decode_c(int index)
{
int i, vv;
vv = 0;
for (i=0; i < 2; i++)
/* Transforma um numero binario em decimal */
27
vv += (pool[index].string_c[1-i] << i);
return vv;
}
/*
******************************************
*
decode_x
*
* Decode a binary string into an real
*
******************************************
*/
double decode_x(int index)
{
int i, vv;
double value;
vv = 0;
for (i=0; i < (CHROM_LENGTH/2); i++)
vv += (pool[index].string_x[((CHROM_LENGTH-2)/2)-1-i] << i);
value = (vv*0.055313215853149133966701444056404) + MINDEM;
return value;
}
/*
******************************************
*
decode_y
*
* Decode a binary string into an real
******************************************
*/
double decode_y(int index)
*
28
{
int i, vv;
double value;
vv = 0;
for (i=0; i < (CHROM_LENGTH/2); i++)
vv += (pool[index].string_y[((CHROM_LENGTH-2)/2)-1-i] << i);
value = (vv*0.055313215853149133966701444056404) + MINDEM;
return value;
}
/*
******************************************
*
evaluate
*
*
Evaluation Function
*
******************************************
*/
double evaluate(int value_c, double value_x, double value_y)
{
/* retorna o valor da função f para o contrato c e as coordenadas x e y */
double df;
df=0;
switch (value_c) {
case 0 :
case 1 :
if (value_x < 1.1 * DT_1)
df += value_x * TDCT + ((DT_1 - value_x) * 3 * TDCT);
else
df += value_x * TDCT;
29
else
else
else
else
else
else
30
else
else
if (value_x < 1.1 * DT_10)
else
if (value_x < 1.1 * DT_11)
else
if (value_x < 1.1 * DT_12)
else
df += (CT_1 + CT_2 + CT_3 + CT_4 + CT_5 + CT_6 +
CT_7 + CT_8 + CT_9 + CT_10 + CT_11 + CT_12) * TCCT;
break;
case 2 :
31
if (value_y < 1.1 * DP_1)
df += value_y * TDAP + ((DP_1 - value_y) * 3 * TDAP);
else
df += value_y * TDAP;
else
else
else
else
else
32
else
else
else
if (value_y < 1.1 * DP_10)
else
if (value_y < 1.1 * DP_11)
else
if (value_y < 1.1 * DP_12)
else
if (value_x < 1.1 * DF_1)
33
df += value_x * TDAF + ((DF_1 - value_x) * 3 * TDAF);
else
df += value_x * TDAF;
else
else
else
else
else
34
else
else
else
if (value_x < 1.1 * DF_10)
else
if (value_x < 1.1 * DF_11)
else
if (value_x < 1.1 * DF_12)
else
df += (CP_1 + CP_2 + CP_3 + CP_4 + CP_5 + CP_6 +
CP_7 + CP_8 + CP_9 + CP_10 + CP_11 + CP_12) * TCAP;
35
df += (CF_1 + CF_2 + CF_3 + CF_4 + CF_5 + CF_6 +
CF_7 + CF_8 + CF_9 + CF_10 + CF_11 + CF_12) * TCAF;
break;
case 3 :
df += value_x * TDVT + ((DT_1 - value_x) * 3 * TDVT);
else
df += value_x * TDVT;
else
else
else
else
36
else
else
else
else
if (value_x < 1.1 * DT_10)
else
if (value_x < 1.1 * DT_11)
else
37
if (value_x < 1.1 * DT_12)
else
df += (CP_1 + CP_2 + CP_3 + CP_4 + CP_5 + CP_6 +
CP_7 + CP_8 + CP_9 + CP_10 + CP_11 + CP_12) * TCVP;
df += (CF_1 + CF_2 + CF_3 + CF_4 + CF_5 + CF_6 +
CF_7 + CF_8 + CF_9 + CF_10 + CF_11 + CF_12) * TCVF;
break;
}
return df;
}
/*
******************************************
*
initialize_population
*
* creates and initializes a population *
******************************************
*/
void initialize_population(void)
{
int i;
/* para cada individuo i sera codificado um numero entre 0 e 2 elevado
38
a (CHROM_LENGTH-2)/2 */
for (i=0; i < popsize; i++)
{
encode_c(i, random((int)pow(2.0, 2.0)));
encode_x(i, random((int)pow(2.0, ((CHROM_LENGTH-2)/2))));
encode_y(i, random((int)pow(2.0, ((CHROM_LENGTH-2)/2))));
join_xy(i); /* cria um único cromossoma juntando c, x e y */
}
}
/*
******************************************
*
select
*
* selects strings for reproduction
*
******************************************
*/
int select(double sum_fitness)
{
int i;
double rand_val;
/* valor randomico entre 0 e sum_fitness */
double partial_sum; /* soma parcial do fitness dos elementos */
/* gera o rand_val */
rand_val = sum_fitness*(((double)rand())/RAND_MAX);
/* inicializa partial_sum */
partial_sum = pool[0].fitness;
/* encontra o indice indicado por rand_val
39
40
isto e' feito atraves da soma de todos os fitness dos elementos da
populacao ate' que esta soma ultrapasse o valor gerado */
for (i=0; partial_sum<rand_val; i++)
partial_sum += pool[i+1].fitness;
/* retorna o indice encontrado */
return i;
}
/*
******************************************
*
crossover
*
*
Swaps 2 sub-strings
*
******************************************
*/
void crossover (int parent1, int parent2, int child1, int child2)
{
int i, site;
if (flip(pcross))
/* Se um numero aleatorio gerado por flip for menor que PCROSS */
site = random((CHROM_LENGTH));
/* determina um ponto de corte aleatorio no cromossoma, senao
*/
else
/* marca como ponto de corte o ultimo gen do cromossoma
site = (CHROM_LENGTH)-1;
/* ate' o ponto de corte, sao copiados genes de pai1 para filho1 e de pai2 para filho2 */
for (i=0; i <= site; i++)
{
new_pool[child1].string[i] = pool[parent1].string[i];
}
*/
/* apos o ponto de corte, sao copiados genes de pai2 para filho1 e de pai1 para filho2 */
/* (veja definicao de crossover de um ponto) */
for (i=site+1; i < CHROM_LENGTH; i++)
{
}
}
/*
******************************************
*
mutation
*
* Changes the values of string position *
******************************************
*/
void mutation(void)
{
int i, j;
/* Percorrendo todos os individuos de uma populacao e todos os genes de
*/
/* cada individuo. Se um numero aleatorio gerado por flip for menor que PMUT */
/* entao o gene [j] sera invertido, caso contrario nao.
*/
/* Neste ponto da execucao do programa os individuos ja' sofreram crossover
*/
/* e os filhos gerados estao em new_pool, entao fazemos mutacao sobre new_pool */
/* e aproveitamos para copiar a nova populacao para a populacao corrente, ou */
/* seja a populacao que ira para a proxima geracao
/* Note que um bit e' representado no programa por um char
for (i=0; i < popsize; i++)
{
*/
*/
41
if (flip(pmut))
{
pool[i].string[j] = !new_pool[i].string[j];
}
else
{
pool[i].string[j] = new_pool[i].string[j];
}
split_xy(i); /* divide o cromossoma em x e y */
}
}
/*
********************************************
*
normalize
*
* Técnica de Aptidão - Normalização Linear *
********************************************
*/
double normalize(struct population pop[ ])
{
int top, search;
double sumfit;
struct population temp;
/* ordena os indivíduos em ordem decrescente */
for (top = 0; top < popsize - 1; top++)
for (search = top +1; search < popsize; search ++)
if (pop[search].fitness < pop[top].fitness)
{
temp = pool[search];
42
pop[search] = pop[top];
pop[top] = temp;
}
/* normaliza a avaliação dos indivíduos */
sumfit = 0;
for (top = 0; top < popsize; top++)
{
pop[popsize -1 - top].fitness = minimo + (((maximo - minimo) / (popsize - 1)) * top);
sumfit += pop[popsize -1 - top].fitness;
}
return sumfit;
}
/*
******************************************
*
*
statistics
*
Print intermediary results
*
******************************************
*/
void statistics(FILE *file, double improvement)
{
int i, j;
fprintf(file, "\nGeneration: %d\nSelected Strings\n", generations);
/* individuos selecionados para reproducao */
for (i=0; i< popsize; i++)
fprintf(file, " %d", selected[i]);
fprintf(file, "\n");
43
/*
Imprime as seguintes informacoes para cada individuo da populacao:
X:
valor do individuo x
Y:
valor do individuo y
f(x):
aptidao do individuo
New_String: o novo individuo
X':
o novo valor x do individuo
Y':
o novo valor y do individuo
*/
fprintf(file, "\nC\tX\tY\tf(x)\t Fitness\t New_String\tC'\tX'\tY'");
for (i=0; i< popsize; i++)
{
/* X, Y e f(x) */
fprintf(file, "\n %d\t%f\t%f\t%f\t%f ; ", pool[i].value_c, pool[i].value_x, pool[i].value_y,
evaluate(pool[i].value_c, pool[i].value_x, pool[i].value_y), pool[i].fitness);
/* New_String */
for (j=0; j<CHROM_LENGTH; j++)
fprintf(file, "%d", pool[i].string[j]);
/* X' e Y' */
fprintf(file, "\t%d\t%f\t%f", decode_c(i), decode_x(i), decode_y(i));
}
fprintf(file, "\nImprovement: %f\n", improvement);
}
/*
*************************************************
*
pcrom
*
44
*
Grava o iésimo cromossoma da geração
*
*************************************************
*/
void pcrom(FILE *file, int i)
{
int j;
fprintf(file, "\nGeneration: %d\n", generations + 1);
for (j=0; j<CHROM_LENGTH; j++)
fprintf(file, "%d", pool[i].string[j]);
fprintf(file, "\t%d\t%f\t%f\t%f\t%f", decode_c(i), decode_x(i), decode_y(i),
pool[i].fitness, evaluate(pool[i].value_c, pool[i].value_x, pool[i].value_y));
}
//---------------------------------------------------------------------------
{
Query1->Close();
Query1->ParamByName("VUC")->AsInteger = StrToInt(Edit12->Text);
Query1->Prepare();
Query1->Open();
}
//---------------------------------------------------------------------------
45

Aplicação de Algoritmos Genéticos na Otimização de Contratos de

Transcrição

Documentos relacionados

Comunicado

Jornal de Negócios / Semana Informática

1 – Sinais convencionais 2 – Unidades de medida

Jornal de Negócios − Semana Informática Alinhar processos do

My Report

Simbologia Inglês

Pacto Global das Nações Unidas 3 - Defender a

Tradução de Termos de Gerenciamento do Valor Agregado

EVM - Mundo PM

ORBE VALUE FIC FIA