Clustering based on genetics algorithm
Dariusz Mazur · 2004
Genetic Algorithms (GAs) have been fairly successful at solving problems of this type that are too ill-behaved (such as multi modal and/or non-differentiable) for more conventional hill-climbing and derivative based techniques. They are not guaranteed to find the global optimum solution to a problem, but they are generally good at finding acceptably good solutions to problems acceptably quickly. There are controlled by several inputs, such as size of population, ways to encode a potential solution as a chromosome, choice of modification operators. Such of these choices are better suited to a particular problem than others, and no single choice is the best for all problems. GAs have had a great measure to success in search and optimization problems. The reason for a great part of this success is their ability to exploit the information accumulated about an initially unknown search space in order to bias subsequent searches info useful subspaces, i.e., their adaptation. This paper introduces an evolutionary algorithm of clustering based on decision list. There has been several proposals of genetic operators designed particularly for rule discovery. Although these genetic operators have been used mainly in the classification task, in general they can be also used in other tasks that involve rule discovery, such as dependence modeling. Mutation is a common reproduction operator used for finding new points in then search space to evaluate. When a chromosome is chosen for mutation, a random choice is made of some of the genes of the chromosome, and these genes are modified. It is proposed to introduce certain variant of mutation, which is based on random choosing two elements from the list and swapping them (there is sort of permutation). The observed feature of algorithm was used in order to increase efficiency of such mutation. Part of then rules list is inactive because during transcribing process only leading rules are taken into consideration and there is possibility to define which rule is the last and divides then list into two parts: active and inactive. The order of the rules in the second, inactive part does not matter for the transcribing process since these rule are not participate in the process. In order to use this characteristic the mutation function guarantees that one of the chosen element always comes form active part of the list. The key difference between this operator and classic mutation operator is the information which each attempts to preserve during recombination. For the clustering problem the important information would seem to be the adjacency information. This operator explicitly preserves adjacency and relative order information. Information about absolute positions appears to be relatively unimportant.