Maintaining Diversity For Genetic Algorithm: A Case Of Timetabling Problem

Abstract

Lebih sedekad, pelbagai pendekatan algoritma genetik (GA) digunakan bagi penyelesaian pelbagai jenis masalah pengoptimuman. Penyelesaian pramatang merupakan masalah utama kepada prestasi GA. Andaian umum mengatakan diversiti tinggi adalah penting untuk mengelakkan masalah ini. Gagal mengekalkan diversiti populasi mengakibatkan masalah ini dan menjejaskan kualiti keputusan yang dihasilkan. Dalam kertas kerja ini, kami menyarankan dua bentuk perwakilan masalah dan dua strategi untuk mengekalkan diversiti populasi, seterusnya menyelesaikan masalah ini. Algoritma ini kemudiannya diaplikasikan kepada masalah penjadualan dan menunjukkan keputusan yang menggalakkan. Kata kunci: Algoritma genetik, penyelesaian pramatang, diversiti, penjadualan, pengoptimuman Over the last decade, variant of genetic algorithm (GA) approaches have been used to solve various type of optimization problems. Premature convergence is the main problem for GA performance. A common hyphothesis is that high diversity is important to avoid this problem. Failure to maintain GA population diversity will lead to this problem and affected quality of result will be produced. In this paper, we proposed two-problem representation and two strategies to retain population diversity as well as preventing premature convergence. The algorithm was then applied to timetabling problem and showed promising result. Key words: Genetic algorithm, premature convergence, diversity, timetabling, optimization