Genetic Algorithm with Center Based Chromosomal Representation to Solve New Student Allocation Problem

Abstrak

Genetic Algorithm (GA) is one of the most effective approaches for solving optimization problem. We have a problem difficulty for GA in clustering problem. It can be viewed as optimization problem, that is maximization of object similarity in each cluster. The objects must be clustered in this paper are new students. They must be allocated into a few of classes, so that each class contains students with low gap of intelligence and they must not exceed the class capacity. The intelligence gap of each class should be low, because it is very difficult to give good education service for the students in the class whose high diversity of achievements or high variation of skills. We call this problem as New Student Allocation Problem (NSAP). Initially, we apply GA with Partition Based Chromosomal Representation (PBCR). But experiments only provide a small scale case (200 students and 5 classes with same capacities). Then we try to apply GA with Center Based Chromosomal Representation (CBCR) and we evaluate it with the same data. We have successfully improved the performance with this approach. This result indicates that chromosomal representation design is the important step in GA implementation. CBCR is better than PBCR in all aspects. All classes generated by CBCR approach have largest gap of intelligence in each class less than generated by PBCR. CBCR approach can reduce these values almost a half of the values with PBCR approach.