Melhoramentos no algoritmo genético construtivo e novas aplicações em problemas de agrupamento / Constructivegeneticalgorithmimprovementsandnewclusteringproblemsapplications

AUTOR(ES)
DATA DE PUBLICAÇÃO

2000

RESUMO

Evolutionary Algorithms has been a research subject for decades and are based on evolving populations of possible solutions for a problem along generations. Genetic Algorithms belong to this group and many scientific works have registered their efficiency applied to combinatorial optimization problems. Recently, the Constructive Genetic Algorithm (CGA)has been studied. This algorithm works with a variable size population over the generations, the population is formed not only by complete problem solutions but also problem solutions parts. This work contributes to the study of such algorithm by introducing a CGA adaptation that works with populations composed only by solution parts, creating complete solution not only by parts combination by also by parts complementation, and finally using a local search method as a mutation process over the complete solutions. This process keeps the best solution eventually found. The study was made using three very known optimization problems: Graph Coloring, Manufacturing Cell Design and School Timetabling. The Graph Coloring problem has many practical applications. It can be applied every time a set formed by objects with some incompatibility among its elements has to be partitioned into subsets with no incompatibilities inside. The Manufacturing Cell Design problem importance resides in planning environments to produce parts using machines, forming machine cells to completely produce parts, reducing the movement of non-completely produced parts. The School Timetabling problem has obvious importance for education institutions and its cyclic demand justify automation by using algorithms. All problems considered were seen as clustering problems. The AGC code was specifically written for each problem using a common base and was executed in microcomputers and workstations, producing good results for test instances taken from the literature, instances specially created for tests, and instances taken from the real word.

ASSUNTO(S)

optimization manufatura graph theory genetic algorithms tabela de horários teoria dos grafos algoritmos genéticos otimização

ACESSO AO ARTIGO

Documentos Relacionados