LCS & GBML Central

Abstract: The Web 2.0 technologies provide users with collaborative work-spaces over the Internet. For example, Wikipedia is an open source encyclopedia that anyone can edit articles. YouTube provides spaces where users can share videos and annotations about them. Users can put images on Flickers and collaborate each other by categorizing with tagging. These contents are created by users’ voluntary activities, which is one of the features for the Web 2.0 technology. Some services based on the Web 2.0 have well organized text-based contents on them. For example, Wikipedia has well structured contents, which is due to voluntary activities of the users trying to edit each contents so as to be sophisticated. On the other hands, other services, such as YouTube and Flickers’, only have short sentences or small number of words as annotations. Additionally these annotations are usually different according to each user because participants are not in situation of collaborations. As a result, annotations do not have meaning for videos and pictures. A system that converts annotations into meaningful texts is useful because building texts requires resources while a number of annotations are available.The purpose of this thesis is development of the text builder which is based on the Web 2.0 technology with genetic algorithms and natural language processing. A human interactions system is developed in this thesis for automatically building meaningful tags from annotations. The system consists of mainly two parts: a conceptual clustering component based on natural language processing and a sentence creating component based on genetic algorithms. The conceptual clustering component decomposes annotations into phrases with main ideas. Then, the sentence creating component builds several tags from the phrases. Thirdly created tags are evaluated by users to find better explanations for videos and pictures. Participants are supposed to collaborate through evaluations to create more organized and meaningful tags.The developed system succeed in creating tags from annotations without structures through user-machine interactions. This system is applicable to other systems which has only annotations as participants’ comments.  Because tags created by this system have meanings but short length a system building longer text as sentences is left as future works.

Abstract: We investigate rule matching in learning classifier systems for problems involving binary and real inputs. We consider three rule encodings: the widely used character-based encoding, a specificity-based encoding, and a binary encoding used in Alecsys. We compare the performance of the three algorithms both on matching alone and on typical test problems. The results on matching alone show that the population generality influences the performance of the matching algorithms based on string representations in different ways. Character-based encoding becomes slower and slower and generality increases, specificity-based encoding becomes faster and faster as generality increases. The results on typical test problems show that the specificity-based representation can halve the time require for matching but also that binary encoding is about ten times faster on the most difficult problems. Moreover, we extend specificity-based encoding to real-inputs and propose an algorithm that can halve the time require for matching real inputs using an interval-based representation. 

Abstract: This paper investigates the incorporation of restricted tournament replacement (RTR) in the extended compact genetic algorithm (ECGA) for solving problems with non-stationary optima. RTR is a simple yet efficient niching method used to maintain diversity in a population of individuals. While the original version of RTR uses Hamming distance to quantify similarity between individuals, we propose an alternative substructural distance to enforce the niches. The ECGA that restarts the search after a change of environment is compared with the approach of maintaining diversity, using both versions of RTR. Results on several dynamic decomposable test problems demonstrate the usefulness of maintaining diversity throughout the run over the approach of restarting the search from scratch at each change. Furthermore, by maintaining diversity no additional mechanisms are required to detect the change of environment, which is typically a problem-dependent and non-trivial task.