Desenvolvimento de Interface para otimização da distribuição de
cargas horárias e escolha de parâmetros iniciais para SA
Rosana Maria Luvezute Kripka, Neuza Terezinha Oro
Instituto de Ciências Exatas e Geociências, ICEG, Universidade de Passo Fundo (UPF), 99001-970 - Passo Fundo/RS
[email protected]; [email protected]
Moacir Kripka
Faculdade de Engenharia e Arquitetura, FEAR, UPF
[email protected]
RESUMO
Foi desenvolvido um software
intitulado
“Programa
de
Distribuição
Otimizada de Cargas Horárias” (PRODOCH)
([2]), na Universidade de Passo Fundo (UPF),
que realiza a otimização da distribuição das
cargas horárias das áreas através do método
meta-heurístico Simulated Annealing (SA)
([1]). O desempenho do método depende da
escolha de alguns parâmetros iniciais tais
como temperatura inicial, o redutor da mesma
e o número de cálculos da função objetivo
para a mesma temperatura. O problema de
distribuição de cargas horárias nos institutos
da UPF trata-se de um problema de otimização
combinatorial, onde a complexidade cresce
exponencialmente de acordo com o número de
disciplinas e professores envolvidos e a
escolha dos parâmetros iniciais interfere
significativamente tanto na convergência do
método como no tempo de processamento dos
dados do problema. De modo geral, a
resolução de problemas desse tipo e a
obtenção de soluções ótimas exatas é
computacionalmente
intratável,
sendo
classificado como um problema NP-difícil.
Para a resolução desses tipos de problema, os
chamados
métodos
heurísticos
vêm
desempenhando importante papel, uma vez
que envolvem apenas valores das funções no
processo, não importando se existe
unimodalidade ou, mesmo, continuidade em
suas derivadas. Porém, apresentam como
desvantagem a necessidade de um grande
número de cálculos do valor da função. Essa
desvantagem é questionada por Powell [3] ao
argumentar que, ao invés de efetuar um grande
número de cálculos adicionais para a
determinação numérica do gradiente através
de técnicas de programação matemática, pode
ser de maior utilidade a utilização desses
cálculos para explorar de forma mais intensa o
espaço de busca.
Ao realizarmos testes computacionais
percebemos que variações nos parâmetros
iniciais implicavam em variações nos valores
finais da função objetivo. Assim decidimos
investigar as implicações provocadas pelas
diferentes combinações entre variações dos
parâmetros temperatura inicial do método e
seu respectivo redutor, ao longo da execução
do programa. Assim, apresenta-se um estudo
inicial para escolha de alguns parâmetros
(temperatura inicial e seu respectivo redutor)
do método SA, utilizado no processo de
otimização para obtenção da distribuição
otimizada das cargas horárias nos institutos da
UPF e apresenta-se, também, uma interface
que está sendo desenvolvida em Delphi 7.0,
para a execução do problema.
Referências
[1] Kirkpatrick, S.; Gelatt, C. D.; Vecchi,
M. P. (1983) Optimization by
Simulated Annealing. Science , 220, nº
4598, p. 671-680.
[2] Kripka, R. M. L.; Oro, N. T.; Kripka,
M.. “Distribuição de cargas horárias
em Instituições de Ensino Superior:
uma formulação para a maximização
do aproveitamento dos recursos
humanos”. Ciência & Engenharia,
Uberlândia, MG, Brasil, v. 14, n. 1, p.
65-72, 2005.
[3] Powell, M.J.D. (1998) Direct Search
Algorithms
for
Optimization
Calculations. Numerical Analysis Report,
DAMTP 1998/NA04, Department of
Applied Mathematics and Theoretical
Physics, Silver Street, Cambridge,
England CB3 9EW.