KCI등재
벌칙 함수에 기반한 유전 알고리즘을 사용한 강의 시간표의 자동 작성 = Automated Generation of Lecture Timetables using Genetic Algorithms based on Penalty Function
저자
발행기관
학술지명
정보과학회 컴퓨팅의 실제 논문지(KIISE Transactions on Computing Practices (KTCP))
권호사항
발행연도
1996
작성언어
Korean
KDC
004
등재정보
KCI등재
자료형태
학술저널
수록면
317-325(9쪽)
제공처
본 논문은 여러 제약 조건 아래서 정해진 벌칙 함수를 최소화시키는 최적 강의시간표를 유전 알고리즘을 이용하여 자동적으로 생성시키는 방안을 제시한다. 고려한 제약 조건은 얻어진 시간표가 반드시 만족시킬 것이 요구되는 필수적 제약조건과 될 수 있는 대로 만족시키는 것이 요구되는 임의적 제약조건으로 나누어지고 이들을 위반시 각기 다른 값의 벌칙을 부여한다. 해집단내 한 해개체는 미리 정해진 과목의 연속으로 표현되고, 각 과목에는 임의의 시간대가 할당된다. 각 과목이 가질 수 있는 가능한 시간대를 여러 가지 알려진 정보를 이용하여 미리 결정한 뒤, 가능한 시간대의 수가 작은 과목부터 Graph Colouring과 유사한 방법에 의해 시간대를 할당하여 진화시간을 크게 단축시킨다. 유전 알고리즘은 이들 할당이 최소의 벌칙값을 가지도록 해집단을 유전학적으로 진화시키는데, 새로운 해개체의 선택은 Eliticism과 K-tournament 방법을 병행하고, 두 해개체의 교차 연산은 점진적 (Incremental) Hybrid 연산법을 사용한다. 제안한 시간표 작성법을 본 대학 1995년도 1학기 컴퓨터 공학과의 시간표 작성에 응용하여 수작업에 의해 작성한 것과 여러 가지 충돌 정도 면에서 서로 비교한다.
더보기This paper proposes an automatic making of an optimal lecture timetable that minimizes an penalty function under the various constraints using genetic algorithms. The constraints are classified into both hard and soft constraint and penalty values are differently given according to their viciousness on the penalty function when they are violated. A chromosome in the population is represented by a sequence of lectures and any timeslot can be assigned to each lecture. The iteration time is greatly reduced by predetermining the possible timeslots of each lecture from the pre-known informations and by applying graph coloring technique to the timeslot assignment in a way that the lecture having smaller number of possible timeslots is assigned first. The timetable population has been genetically evolved such that the timeslot assignment will decrease the penalty function by applying both the k-tournament selection combined with the elitism and the incremental hybrid crossover operation. The proposed method is performed to determine the lecture timetable of spring semester, 1995 in our department and compares various conflict performances with the hand-coded one.
더보기서지정보 내보내기(Export)
닫기소장기관 정보
닫기권호소장정보
닫기오류접수
닫기오류 접수 확인
닫기음성서비스 신청
닫기음성서비스 신청 확인
닫기이용약관
닫기학술연구정보서비스 이용약관 (2017년 1월 1일 ~ 현재 적용)
학술연구정보서비스(이하 RISS)는 정보주체의 자유와 권리 보호를 위해 「개인정보 보호법」 및 관계 법령이 정한 바를 준수하여, 적법하게 개인정보를 처리하고 안전하게 관리하고 있습니다. 이에 「개인정보 보호법」 제30조에 따라 정보주체에게 개인정보 처리에 관한 절차 및 기준을 안내하고, 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다.
주요 개인정보 처리 표시(라벨링)
목 차
3년
또는 회원탈퇴시까지5년
(「전자상거래 등에서의 소비자보호에 관한3년
(「전자상거래 등에서의 소비자보호에 관한2년
이상(개인정보보호위원회 : 개인정보의 안전성 확보조치 기준)개인정보파일의 명칭 | 운영근거 / 처리목적 | 개인정보파일에 기록되는 개인정보의 항목 | 보유기간 | |
---|---|---|---|---|
학술연구정보서비스 이용자 가입정보 파일 | 한국교육학술정보원법 | 필수 | ID, 비밀번호, 성명, 생년월일, 신분(직업구분), 이메일, 소속분야, 웹진메일 수신동의 여부 | 3년 또는 탈퇴시 |
선택 | 소속기관명, 소속도서관명, 학과/부서명, 학번/직원번호, 휴대전화, 주소 |
구분 | 담당자 | 연락처 |
---|---|---|
KERIS 개인정보 보호책임자 | 정보보호본부 김태우 | - 이메일 : lsy@keris.or.kr - 전화번호 : 053-714-0439 - 팩스번호 : 053-714-0195 |
KERIS 개인정보 보호담당자 | 개인정보보호부 이상엽 | |
RISS 개인정보 보호책임자 | 대학학술본부 장금연 | - 이메일 : giltizen@keris.or.kr - 전화번호 : 053-714-0149 - 팩스번호 : 053-714-0194 |
RISS 개인정보 보호담당자 | 학술진흥부 길원진 |
자동로그아웃 안내
닫기인증오류 안내
닫기귀하께서는 휴면계정 전환 후 1년동안 회원정보 수집 및 이용에 대한
재동의를 하지 않으신 관계로 개인정보가 삭제되었습니다.
(참조 : RISS 이용약관 및 개인정보처리방침)
신규회원으로 가입하여 이용 부탁 드리며, 추가 문의는 고객센터로 연락 바랍니다.
- 기존 아이디 재사용 불가
휴면계정 안내
RISS는 [표준개인정보 보호지침]에 따라 2년을 주기로 개인정보 수집·이용에 관하여 (재)동의를 받고 있으며, (재)동의를 하지 않을 경우, 휴면계정으로 전환됩니다.
(※ 휴면계정은 원문이용 및 복사/대출 서비스를 이용할 수 없습니다.)
휴면계정으로 전환된 후 1년간 회원정보 수집·이용에 대한 재동의를 하지 않을 경우, RISS에서 자동탈퇴 및 개인정보가 삭제처리 됩니다.
고객센터 1599-3122
ARS번호+1번(회원가입 및 정보수정)