Analisis dan Implementasi Metode Constraint Satisfaction Problem dengan Menggunakan Algoritma SPEA2 pada Penjadwalan Kuliah

ABSTRAKSI: Penjadwalan kuliah adalah masalah yang multiobjective karena banyak aspek yang menentukan baik buruknya suatu jadwal kuliah. Penjadwalan mata kuliah merupakan permasalahan yang kompleks dan banyak batasan-batasan yang harus dipenuhi seperti adanya bentrok kelas, bentrok dosen, bentrok ruangan dan lain sebagainya. Dimana batasan-batasan tersebut dibagi menjadi 2 tipe yaitu hardconstraint dan softconstraint. Pada tugas akhir ini, Algoritma SPEA2 adalah metode multiobjective optimization yang dapat digunakan untuk membangun sistem yang dapat mengatasi permasalahan penjadwalan mata kuliah tersebut. Dataset yang digunakan untuk melakukan pengujian adalah data perkuliahan S1 Teknik Informatika IT Telkom Bandung, dengan parameter yang diujikan adalah jumlah populasi, jumlah archive size, probabilitas crossover dan probabilitas mutasi. Penambahan jumlah populasi maka akan berdampak pada semakin besarnya kesempatan setiap individu untuk mendapatkan solusi yang dicari. Ukuran archive size yang semakin kecil maka mengakibatkan individu-individu terbaik yang di copy dari populasi. Dengan semakin baiknya individu maka kemungkinan terciptanya solusi untuk generasi selanjutnya semakin besar. Probabilitas crossover yang semakin besar dapat mengakibatkan pertukaran antar gen setiap individu semakin sering. Dengan semakin seringnya pertukaran gen individu, kemungkinan terciptanya solusi semakin besar. Probabilitas mutasi yang semakin besar dapat menghilangkan solusi yang mungkin ada dari gen individu sebelumnya. Dengan probabilitas mutasi yang besar, dapat mengakibatkan pergantian gen setiap individu semakin sering, yang dapat menghilangkan solusi yang mungkin didapatkan oleh gen sebelumnya.Kata Kunci : penjadwalan mata kuliah, multiobjective, SPEA2, populasi, archive size, generasiABSTRACT: College scheduling is a multiobjective problem because many aspects determine the course schedule. Course scheduling is a complex problem and have a lot of restrictions that must be filled such as a clashed class, clashed lecturer, clashed room and etcetera. The restrictions are divided into 2 types, namely hardconstraint and softconstraint. In this thesis, SPEA2 algorithm is a multiobjective optimization method that can be used to build a system that can solve the course scheduling problems. Dataset that used for testing is the data classes S1 Informatics IT Telkom Bandung, with the parameter that being tested is the number of population, number of archive size, crossover and mutation probability. The addition of the population will have an impact on the magnitude of the opportunity every individual to obtain a solution. The size of archive size that getting smaller will lead to the best individuals in the copy of the population. The better the individual, the greater the chances of solutions creation for the next generation. The greater the crossover probability can result in the exchange of genes between individuals more often. The more frequent exchange of individual genes, the greater the possibility of the creation of solutions. The greater the probability of mutations can eliminate the possible solutions of the previous individual genes. With a large probability of mutation, each individual will frequently changes the genes, which can eliminate the solutions that may be obtained by the previous gen.Keyword: course scheduling, multiobjective, SPEA2, population, archive size, generatio