Keywords: Grammatical Evolution; Similarity Function Learning; Term Networks; Text Classification
Text classification is the task of assign a document to one or more categories. As the volume of unstructured data has increased, this task has become manually impracticable. In literature, is possible to find many methods for automatic text classification. While, many algorithms require a large number of labeled documents to induce a classification model which is labeling is costly and time consuming, there are semi-supervised approaches that requires only a few number of labels to perform text classification. Following this, a semi-supervised approach based on Term Networks named TCTN makes use of a network which terms are network objects and they are linked considering some similarity function. Although, TCTN has surpassed accuracy of state-of-art methods, it is very sensitive to the similarity function chosen. As choosing the best similarity function is still a challenge, in this work it is proposed an algorithm based on Grammatical Evolution (GE) for automatically design new similarity functions for Term Networks. GE is an evolutionary algorithm for global optimization that uses a context-free grammar (CFG) for generating new individuals. In this work, individuals are similarity functions generated and optimized by a GE with a CFG manually designed for this purpose. We observed from experiments that similarity functions built from the proposed approach surpass traditional similarity functions from literature such as Support, Kappa, Mutual Information, Piatetsky-Shapiro and Yule's Q.
ResumosKeywords: Problema de Escalonamento de Enfermagem; Algoritmo Genético de Chaves Aleatórias; INRC-II; Otimização Combinatória; Meta-heurísticas.
Em um ambiente hospitalar a equipe de enfermagem impacta diretamente na qualidade operacional dos hospitais, além disso é considerada o maior setor dos hospitais, logo a geração de escalas de trabalho eficientes para os enfermeiros é o primeiro, e um dos passos mais importantes para que o setor opere com bom desempenho. O Problema de Escalonamento de Enfermagem (PEE), assim intitulado pela literatura, consiste na elaboração de escalas de trabalho visando obter uma solução viável que minimize a ocorrência de restrições como leis trabalhistas, preferências dos funcionários e demandas das instituições. Este trabalho busca encontrar escalas de enfermagem para o PEE proposto na Second International Nurse Rostering Competition (INRC-II), o evento teve 10 meses de duração e ocorreu entre os anos de 2014 e 2015. O objetivo da competição é respeitar todas as restrições classificadas como fortes e minimizar as ocorrências das restrições denominadas fracas. Como o conjunto de restrições elaboradas pela competição qualificam o problema como NP-Difícil, uma abordagem que utilize heurísticas é necessária para que seja possível encontrar soluções para o problema em tempo hábil. Desta forma, este trabalho propõe a utilização da meta-heurística populacional Algoritmo Genético de Chaves Aleatórias Viciadas para gerar soluções às instâncias do INRC-II. O início do algoritmo será marcado pela criação de uma população, representada por um conjunto de soluções do problema. Cada solução será representada por uma matriz, onde as linhas são referentes a cada enfermeiro, e as colunas aos sete dias da semana. Cada posição da matriz será composta por um par de chaves aleatórias, representando o turno que o enfermeiro deve trabalhar e a competência que irá exercer. O par de chaves será composto por números reais gerados randomicamente e pertencentes ao intervalo entre [0,1). Em seguida, um decodificador irá transformar cada solução de chaves aleatórias em uma solução real do problema que, por sua vez, será avaliada por uma função responsável por atestar sua qualidade. Após a avaliação de cada solução da população, o algoritmo dará início ao ciclo evolutivo. Nesta etapa serão aplicados os operadores genéticos de mutação e cruzamento, que tem por objetivo, intensificar e diversificar a busca por novas soluções. A seguir, tais soluções serão avaliadas e o algoritmo definirá quais soluções permanecerão para a próxima população de um novo ciclo evolutivo. Por fim, a melhor solução obtida ao longo de todo o processo será retornada. Espera-se que os resultados encontrados neste trabalho sejam superiores ou equivalentes aos resultados das sete melhores equipes que participaram da competição.
ResumosKeywords: RNC; BreakHis; momentum
O câncer de mama é o segundo tipo de câncer mais recorrente no Brasil, com um número estimado de 68.220 novos casos entre 2018 e 2019. Apesar dos diversos métodos existentes para identificação de tumores mamários como o autoexame, mamograma e ressonância magnética, a análise histopatológica do tecido por meio de microscopia é o único método que fornece um diagnóstico preciso quanto à categoria do tumor. Entretanto, tal análise exige patologistas treinados, consome muito tempo e os resultados podem ser comprometidos devido à fadiga e a diminuição da atenção durante a análise das imagens. A classificação automática dos tumores benignos ou malignos é um problema extremamente importante, pois possibilita a realização dos exames mesmo em regiões onde não existem patologistas habilitados ou ainda reduzir o tempo de diagnóstico deixando para os patologistas a supervisão do processo e as análises mais complexas. Algoritmos de processamento de imagens e de aprendizagem de máquina são comumente aplicados na solução desse tipo de problema. Recentemente, as Redes Neurais Convolucionais (RNCs) tem se mostrado eficazes em resolver tarefas de classificação automática de imagens. O conjunto de dados utilizado para a realização dos experimentos foi o BreakHis, composto por 7.909 imagens obtidas de 82 pacientes anônimos e organizadas em duas classes principais: tumores benignos e tumores malignos. Os experimentos foram realizados utilizando quatro arquiteturas de RNCs: AlexNet, VGG-16, ResNet-101 e a DenseNet-121. Para possibilitar uma comparação justa, foram utilizadas as mesmas cinco divisões (70 % das imagens para o conjunto de treinamento e 30 % para o conjunto de testes, separados por paciente) utilizadas pelo autor do conjunto de dados. Para cada uma das cinco divisões, 20 % do conjunto de treinamento foi separado para compor um conjunto de validação, utilizado para a otimização dos seguintes hiperparâmetros utilizando o método grid-search: a) tamanho do lote; b) taxa de aprendizagem inicial; c) momentum; d) tamanho do passo (atualização da taxa de aprendizagem). Os hiperparâmetros otimizados foram utilizados para treinar os RNCs considerando as seguintes estratégias de treinamento: a) a partir do zero; b) a partir do zero com aumento de dados off-line; c) a partir do zero com aumento de dados on-line; c) a partir do zero com aumento de dados off-line e on-line; d) fine-tuning; e) fine-tuning com aumento de dados off-line; f) fine-tuning com aumento de dados off-line e on-line. As redes treinadas foram testadas nos cinco conjuntos de testes fornecidos pelo autor do conjunto de dados considerando classificação por paciente e por imagem. O modelo que obteve os melhores resultados foi a arquitetura DenseNet-121 treinada usando a estratégia de fine-tuning com aumento de dados off-line e on-line, com 90% de acurácia na classificação por paciente e 92% de acurácia na classificação por imagens.
ResumosKeywords: Taxonomia de Bloom; Diretrizes curriculares; Referenciais de formação; Programas analíticos
Os cursos de graduação na área de computação no Brasil devem estar em conformidade com as Diretrizes Curriculares Nacionais (DCN) estabelecidas pelo Ministério da Educação a partir da consulta aos órgãos representativos da categoria profissional. No caso da computação este órgão é a Sociedade Brasileira de Computação (SBC). A SBC divulgou em 2017 os Referenciais de Formação (RF), que trouxe uma ênfase maior na construção de currículos baseados em competências ao invés de conteúdos e utilizando a Taxonomia Revisada de Bloom para estabelecer em que nível cada competência deve ser construída. Entretanto, nem sempre os programas analíticos das disciplinas estão em conformidade com os RF e as DCN. O desenvolvimento foi após um estudo realizado com as disciplinas de Sistemas de Informação da Universidade Federal de Viçosa – Campus Rio Paranaíba, em que os docentes compreendem o escopo de suas disciplinas, mas nem sempre conseguem perceber de que forma estas disciplinas estão integradas às outras do curso e a contribuição de cada uma no desenvolvimento das competências esperadas. Sem esta visão do todo fica difícil verificar se o conjunto de disciplinas da organização curricular de um curso atende de forma plena ao que foi estabelecido nos RF e nas DCN. Para sanar este problema propomos uma ferramenta para que permita a rastreabilidade entre os programas analíticos e as Diretrizes Curriculares. Essa ferramenta auxilia o docente na construção de programas analíticos das disciplinas de forma que seus objetivos e conteúdos possam ser relacionados às competências e níveis nas DCN. A ferramenta foi implementada como um sistema Web que permite o cadastro da organização curricular de um curso, no qual são cadastrados todos os dados dos programas analíticos acrescentando dentro dos objetivos a ligação com uma competência do referencial de formação e a classificação do mesmo, e ao incluir algum conteúdo será ligado a um dos objetivos descritos. Como às DCN’s estipularam quais níveis dentro das competências devem ser atingidos pelo egresso do curso, utilizamos ela como base para análise e geração dos relatórios, que apresentam gráficos apontando a situação atual do curso com relação às exigências. Ao conseguir encontrar pontos que são divergentes podemos utilizar o recurso de filtro para descobrir em quais disciplinas algum conteúdo ou competência está sendo trabalhado, possibilitando encontrar falhas nas disciplinas que estão fornecendo conteúdos duplicados ou que não atendem o mínimo esperado. E assim que todas as disciplinas estiverem cadastradas será possível fazer uma reforma geral da grade curricular, adaptando-se para atender melhor os professores e alunos de acordo com as exigências.
ResumosKeywords: Software para criação de questões; Banco de questões avaliativas; Taxonomia de Bloom; Referenciais de formação na computação; Avaliação por níveis de conhecimento
A elaboração das Diretrizes Curriculares Nacionais (DCN) para os cursos de computação foi iniciada em 1998 por meio de discussões realizadas no Seminário da Comissão de Especialistas da Sociedade Brasileira de Computação (SBC), em Belo Horizonte. Os currículos de referência anteriores à homologação das DCNs, em 2016, tinham foco na descrição dos conteúdos ao invés das competências e habilidades necessárias ao egresso. Em outubro de 2017, a SBC publicou o documento chamado "Referenciais de Formação para os Cursos de Graduação em Computação" (RF) alinhado às DCNs e seguindo um modelo de currículo baseado em competências utilizando os conceitos da Taxonomia Revisada de Bloom, na qual "uma competência pode expressar o conhecimento, as habilidades ou as atitudes esperadas para o egresso do curso, sob perspectiva de objetivos de aprendizagem (o que o aluno será capaz de)". A taxonomia de Bloom consiste em seis níveis: recordar, compreender, aplicar, analisar, avaliar e criar; que estão em ordem crescente de complexidade cognitiva necessária para se responder questões de avaliações, ou seja, uma questão no nível “compreender” exige operações mentais mais simples do que questões no nível “avaliar”. Mesmo com sua utilização nas DCNs, nem sempre os programas analíticos das disciplinas são formulados levando em consideração a taxonomia de Bloom em seu planejamento. Neste caso, situações de inconsistência entre o conteúdo planejado e o exigido podem ocorrer. Tendo em vista a preocupação com a adequação dos instrumentos de avaliação às normas exigidas e especificadas nas DCNs. Este presente estudo apresenta a proposta de uma ferramenta de apoio para gerência de questões de avaliações (Banco de Questões) que consideram a taxonomia de Bloom em sua criação e possibilita a rastreabilidade entre os conteúdos abordados nas disciplinas e os conteúdos, competências e eixos de formação dos Referenciais de Formação. O sistema proposto é uma plataforma web inspirada no aplicativo Moodle, visando abranger as disciplinas do curso de sistemas de informação da Universidade Federal de Viçosa. A metodologia utilizada nesse projeto consiste na modelagem dos dados necessários à construção do sistema e especificação de seus requisitos. Assim como, o estudo da taxonomia de Bloom para correta criação da estrutura das questões a serem armazenadas no banco de dados. A rastreabilidade almejada entre as questões e os referenciais de formação é estabelecida através dos níveis de conhecimento especificados nas diretrizes curriculares e informados no momento do cadastro das questões no banco de dados. Espera-se que, com o apoio dessa ferramenta de gerência dos instrumentos de avaliação, a elaboração de questões por parte dos docentes que a utilizarem seja feita de forma mais consciente em relação à coerência da complexidade cognitiva exigida pelas DCNs e planejada nos programas analíticos para o desenvolvimento das competências esperadas em cada conteúdo abordado.
ResumosKeywords: heurística; NP-difícil; VNS; VND
O problema de Balanceamento de Linhas de Produção e Designação Hierárquica de Trabalhadores (BLPDHT) é altamente presente nas indústrias que realizam produção em larga escala. O problema se resume no escalonamento de trabalhadores que realizarão determinadas tarefas de acordo uma hierarquia predefinida que leva em consideração o nível de experiência de um trabalhador para realizar tais tarefas. Desta forma, quanto mais experiente for o trabalhador, maior será o custo do mesmo, e vice-versa. Além disso, no BLPDHT, nem todos os trabalhadores estão aptos a executar todas as tarefas. Também deve-se levar em consideração a precedência entre as tarefas nas linhas de produção, ou seja, existem tarefas que para começarem a serem executadas, necessitam que outras tarefas já tenham sido concluídas. O objetivo do BLPDHT é definir um escalonamento de trabalhadores em estações de trabalho de forma que o custo total das linhas de produção seja minimizado. Ao definir tal escalonamento deve-se respeitar a precedência entre as tarefas e ainda considerar a hierarquia dos trabalhadores. Pelo fato do BLPDHT pertencer a classe NP-difícil, encontrar uma solução por métodos exatos pode demandar tempos computacionais proibitivos. Sendo assim, propõe-se o desenvolvimento de uma estratégia heurística a fim de encontrar soluções para o BLPDHT. Tal heurística, denominada VNS-BLPDHT, será baseada no algoritmo Variable Neighbourhood Search (VNS), que realiza trocas sistemáticas de estruturas de vizinhança para escapar de ótimos locais. Em seguida, o método Random Variable Neighbourhood Descent (RVND) também será incorporado ao VNS para que buscas locais em estruturas de vizinhanças sejam realizadas, visando intensificar a busca por melhores soluções. Tais estruturas de vizinhança serão exploradas a partir de movimentos de troca, substituição e realocação de trabalhadores e estações de trabalho. Para isto, o algoritmo VNS-BLPDHT representará as soluções do problema através de vetores com trabalhadores e estações de trabalho. Com a aplicação do VNS-BLPDHT, é esperada a obtenção de um algoritmo robusto, capaz de produzir soluções de qualidade para o BLPDHT, de tal forma que, ao serem comparadas com as soluções presentes na literatura, se mostrem superiores.
ResumosKeywords: Grafo; Otimização; PRAC; PRVC
O aumento das indústrias e o consumo abusivo da sociedade em produtos que são descartados, geram grandes impactos no meio ambiente e consequentemente um aumento gradativo nos gastos para o tratamento e coleta destes resíduos. Visando diminuir os gastos públicos direcionados à coleta dos resíduos, o presente trabalho apresenta uma proposta para otimizar os roteiros realizados pelos caminhões coletores de lixo, minimizando a distância e, claro, o custo total necessário para coletar todo o lixo presente na cidade. Este trabalho trata de uma aplicação real do Problema de Roteamento em Arcos Capacitados (PRAC), onde uma quantidade de veículos deve atender todas as demandas presentes nos arcos de um grafo, sem exceder a capacidade dos veículos, além de iniciar e retornar em um ponto inicial denominado como depósito sempre que estiver cheio e ao final da rota. Sabe-se que este problema pertence a classe NP-difícil, o que torna sua resolução por métodos exatos um desafio. Inicialmente uma instância real do problema, considerando o município de Rio Paranaíba - MG, foi modelada utilizando a ferramenta yED para plotar o grafo no qual as esquinas presentes no mapa representam os vértices do grafo e as ruas representam os arcos, que são direcionados a partir dos sentidos permitidos das vias. Através da ferramenta utilizada, foi possível extrair as coordenadas cartesianas de cada vértice, para serem utilizadas no cálculo das distâncias euclidianas entre os vértices. As demandas de cada arco serão geradas de forma aleatória. Para facilitar a resolução por modelos exatos do PRAC e diminuir a complexidade dos algoritmos, será aplicado um pré-processamento, assim como consta no estado da arte para o PRAC. Neste pré-processamento, são realizadas transformações no grafo original, onde para cada arco contido no grafo original serão incluídos dois novos vértices. As demandas dos arcos serão divididas em duas partes e transferidas para os vértices criados. As distâncias serão mantidas entre os vértices que já possuíam ligação direta, para os demais, serão calculados a menor distância através do algoritmo de Dijkstra. Ao final do pré-processamento, o grafo transformado será um grafo completo, ou seja, com arestas de todos os vértices para todos os outros. Com o novo grafo é possível tratar o problema como um Problema de Roteamento de Veículos Capacitados (PRVC). Através de modelos matemáticos aplicados na linguagem de modelagem OPL (Optimization Programming Language), espera-se obter resultado próximo do ótimo para a instância completa. Caso a solução desejada não for atingida, devido à alta complexidade do PRAC, a instância será fragmentada em partes para se obter o resultado esperado em escalas menores, como por exemplo em bairros da cidade.
ResumosMatheus Nohra Haddad
João Fernando Mari
Contato: joaof.mari@ufv.br