민족사관고등학교 학생들을 위한 시간표를 만드는 일은 매우 힘들다. 이러한 시간표를 컴퓨터가 구현하는 여러 방법 중, 본 연구에서는 유전 알고리즘을 선택하였다. 유전 알고리즘을 활용할 경우, 단순한 시간표를 짜는 것이 아니라 여러 개의 최적해를 구하는 방법을 통해 최적의 시간표를 얻을 수 있게 된다. 복잡한 변수들의 집합체인 시간표를 하나의 개체로 설정하고 세대수를 늘림으로써 주어진 조건에 적합한 시간표를 구현하는 것이다. 본 연구는 알고리즘을 구성하는 여러 변수들의 최적의 값을 구하고, 이를 통해 유전 알고리즘으로 시간표를 간단하게 작성할 수 있음을 보여준다.
유전 알고리즘은 자연 세계의 진화과정에 기초한 계산 모델로, 구하고자 하는 해를 유전자의 형식으로 표현할 수 있을 때 사용한다. 문제풀이 방법을 몰라도 적합도 점수를 통해 최적해를 구할 수 있는 장점이 있다.
유전 알고리즘이 실제로 효과가 있는지 확인하고, 복잡한 시간표 알고리즘으로 넘어가기 전에 연습용으로 알파벳 알고리즘을 만들어 보았다.
26개의 알파벳이 연속적으로 나열되어 있는 “abcdefghijklmnopqrstuvwxyz”를 최적해로 설정하고, 룰렛 휠 기법을 사용하여 기본 점수를 53점으로 하여 연구를 진행하였다. 처음 프로그램을 실행시켰을 때는 결국 59점으로 설익은 수렴을 하였다. 이는 유전자의 다양성이 부족했기에 나타난 결과로, 이후 돌연변이 연산을 추가하였다. 그래서 결국 131점으로 수렴하는 것을 확인할 수 있었지만, 동시에 돌연변이율을 너무 증가시키거나 감소시키면 프로그램 시간이 기하급수적으로 증가함을 확인할 수 있었다.
이를 통해 유전 알고리즘이 실제로 효과가 있음을 확인하였고, 설익은 수렴이 발생한 것을 통해 유전자의 다양성의 중요성을 볼 수 있었다.
연구에서는 11학년과 12학년만 고려하여 알고리즘을 짰다. 일단 개체는 11학년과 12학년을 대상으로 한 하나의 시간표로 설정하였고, 다른 요소들은 추후에 코딩을 통해 고려하기로 하였다. 이후 계열별로 모든 수업의 수업코드를 설정하여, 하나의 염색체는 각 학급의 시간표로 만들었다.
성공한 알파벳 알고리즘과 동일한 환경, 즉 개체수 5000개, 돌연변이율 0.7%, 다점 교차 기법, 룰렛 휠 선택 기법을 사용하여 진행해 보았다. 그러나 유전자 알고리즘의 적합도 점수는 80점에서 더 이상 오르지 않았기에, 선택 기법을 먼저 재설정하기로 하였다.
3가지 기법 중 하나를 선택하기로 하였다. 이를 위해 개체수 1000, 세대 수 1000으로 하여 세대별 걸리는 시간을 구한 결과, 토너먼트 기법, 룰렛 휠 선택 기법, 그리고 순위기반 선택 기법 순으로 짧게 걸렸다. 순위기반 선택 기법은 시간이 매우 오래 걸렸고, 룰렛 휠 기법은 선택압을 설정하지 못하기 때문에 가장 우수한 토너먼트 기법을 추후 실험에 사용하기로 하였다.
개체수가 많을수록 다양성을 확보할 수 있지만 시간이 급격하게 늘어나므로 적당한 개체수를 결정하기로 하였다. 이를 위해 기본 개체수인 10000과 5000, 15000을 비교하기로 하였다. 실험 결과 개체수가 약 5000 정도씩 늘 때마다 세대별 약 1초 정도 평균 시간이 늘어났다. 또한 1000세대가지 갈 동안 적합도 점수가 변하는 정도를 확인하여 10000이 적절한 개체수라고 판단하였다.
선택압을 60으로 할 경우 적합도가 너무 천천히 증가할 것으로 예상하여 70, 80, 90, 95로 나누어 실험을 진행하였다. 실험 결과, 선택압이 높으면 높을수록 최종적인 적합도가 높았지만, 95와 같이 과도할 경우 오히려 증감 폭이 낮아짐을 확인하였다. 따라서 실험 결과를 통해 선택압을 90으로 설정하여 추후 실험을 하기로 결정하였다.
돌연변이율을 1%에서 2%까지 세세하게 나누어 실험을 진행해 보았다. 처음 예상과는 달리 2%일 때 적합도 점수가 빠르게 증가하여, 이후 2%를 기준으로 나누어 진행한 결과, 2.1%일 때 적합도 점수가 가장 빠르게 증가함을 확인하였다.
연구에서 계속 설익은 수렴을 하는 이유가 기존의 돌연변이 연산의 문제라고 생각했다. 특정 세대마다 총 개체수의 20%를 새로운 개체로 바꿈으로써 유전자의 다양성을 보존하는 방법을 생각해보고 적용하였다. 처음 실험은 실패하였지만, 이후 돌연변이율을 변화시킨 후 적용한 결과 적합도 점수가 90이 성공적으로 넘어가며 효과가 있는 것으로 보였다.
연구 결과 계속 한 세대 당 개체수를 증가시켜주면 확실히 실행시간은 느려지지만 적합도 점수가 높은 곳에서 수렴하는 것을 보이며 시간과 자원이 많다면 시간표를 만들 수 있음을 암시하였다.
유전 알고리즘을 활용하여 시간표를 만들어 주는 프로그램을 만들고 변수들을 조작하여 여러 실험들을 진행하였다. 이를 통해 개체는 10000개, 선택압은 90, 돌연변이율은 2.1%일 때 가장 효과적임을 확인하였다. 첫 실험에서는 2000세대에서 79점을 넘기지 못하였지만, 마지막 실험에서는 91점까지 나오며 연구가 효과가 있음을 보였다.
이번 연구를 통해 실제로 유전 알고리즘을 활용하여 시간표를 만들 수 있음을 보여 유전 알고리즘의 효과성을 입증하였다. 변수들을 바꿈으로써 최적의 값을 확인하였고, 이를 통해 복잡한 시간표를 만들기 위한 최적의 코드를 만들어내었다. 이를 통해 변수가 많은 프로그램에서도 유전 알고리즘이 효과적임을 밝혔다.
또한 유전 알고리즘을 실생활에 적용시켜보았다는 의의가 있다. 주변의 복잡한 변수들로 인해 어려운 문제가 있을 경우, 시간표를 작성하는 데에 유전 알고리즘을 이용하였듯이 그 문제를 해결하는 데 활용할 수 있을 것이다.
마지막으로 새로운 돌연변이 기법으로 유전자의 다양성을 보장할 수 있는 독창적인 방법을 생각해 내었다. 기존의 유전 알고리즘에서는 이용되지 않았던 방법으로, 이를 통해 프로그램의 실행시간을 단축시킬 수 있을 것이라고 예상한다.
그러나 적합도 100의 실질적인 데이터를 구하지 못하였다는 한계가 존재한다. 또한 속도가 더 빠른 알고리즘으로 발전시키고, 선생님들께서 실제로 여러 요구사항들을 추가하며 사용할 수 있게 입력 정보를 직관적으로 넣을 수 있게 하고 GUI를 통해 시간표를 시각적으로 나타내야 하는 향후 과제가 있다.